Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Anais de XXXV Simpósio Brasileiro de Telecomunicações e Processamento de Sinais

Ataques quânticos ao gerador pseudo-aleatório de Blum-Micali

Edmar Nascimento, Nigini Oliveira, Francisco de Assis

Published Jan 1, 2007• 0 citations
Publisher

Abstract

Resumo-A utilizac ¸ão de seq üências pseudo-aleatórias é de grande importância em diversas aplicac ¸ões da criptografia.Um ataque a um gerador pseudo-aleatório objetiva reproduzir uma dada seq üência pseudo-aleatória a partir de um conjunto de termos dessa seq üência.Classicamente, esse é um problema de difícil soluc ¸ão, ou seja, não existe algoritmos conhecidos em tempo polinomial que realizem esta tarefa.Por outro lado, o desenvolvimento de algoritmos quânticos vem mostrando que determinados tipos de problemas podem ser resolvidos de modo mais eficiente.Neste artigo, é apresentado um circuito quântico que realiza um ataque ao gerador Blum-Micali apresentando um ganho no n úmero de operac ¸ões em relac ¸ão aos algoritmos clássicos conhecidos. Palavras-Chave-Gerador Blum-

DOI
10.14209/sbrt.2007.31307

Related papers

Ataques quânticos a geradores de números pseudo-aleatórios.

E. B. G. Costa, Elloá Barreto Guedes da. Costa

Este trabalho apresenta um ataque quântico de comprometimento permanente ao gerador pseudo-aleatório de Blum-Micali. A segurança deste gerador, classificado como criptograficamente seguro, baseia-se na hipótese de intratabilidade do problema do logaritmo discreto perante a Computação Clássica. O ataque proposto faz uso do algoritmo quântico de busca em conjunto com o algoritmo quântico para o logaritmo discreto para comprometer a imprevisibilidade do gerador, recuperando todas as saídas passadas e futuras do mesmo. O presente trabalho também descreve generalizações deste ataque que o adequam a uma gama mais vasta de geradores, incluindo geradores da Construção de Blum-Micali e geradores com múltiplos predicados difíceis. Tais generalizações também abrangem a realização de ataques em situações adversas, por exemplo, quando o adversário captura bits não consecutivos ou quando há menos bits que o requerido. Comparado à sua contrapartida clássica, o algoritmo quântico proposto nesse trabalho possui um ganho quadrático em relação à recuperação do representante do estado interno do gerador, seguido de um ganho superpolinomial na obtenção dos demais elementos do estado interno. Estes resultados caracterizam ameaças,elaboradas com Computação Quântica, contra a segurança de geradores utilizados em diversas aplicações criptográficas.

•Mar 25, 2011•0 citations

O algoritmo polinomial de Shor para fatoração em um computador quântico

Mário Sansuke Maranhão Watanabe

Sistemas de criptografia largamente difundidos como o RSA fundamentam a sua eficiência na suposição de que, em termos práticos, é impossível fatorar números inteiros suficientemente grandes em uma escala de tempo aceitável. Mais precisamente, não existem, até o momento, algoritmos de fatoração em tempo polinomial que possam ser implementados nos atuais computadores. Dentre os algoritmos conhecidos, o mais eficiente requer um tempo computacional de ordem exponencial na quantidade de dígitos binários do número a ser fatorado. Em 1994, baseado nos trabalhos anteriores de Benioff, Bennett, Deutsch, Feynman e Simon, dentre outros, Peter Shor apresentou um algoritmo de fatoração que requer assintoticamente uma quantidade em ordem polinomial de passos em um computador quântico para fatorar um número inteiro de tamanho arbitrário. Esse algoritmo ao invés de abordar o problema de decompor tal número em dois fatores não triviais pelo método direto de divisões sucessivas, utiliza o problema equivalente de encontrar a ordem de um certo inteiro modulo o número fatorado, onde esse inteiro é escolhido aleatoriamente relativamente primo com o número fatorado. Shor faz uso de um algoritmo quântico para calcular essa ordem. A computação quântica revela um paradigma computacional bastante adverso da computação clássica. Enquanto esta última é realizada através de operações binárias determinísticas com base na lógica booleana clássica, a computação quântica fundamenta as suas operações nos postulados que descrevem o comportamento quântico da matéria. Portanto, é probabilística no seu modus operandi. Essa diferença entre os formalismos lógicos da computação clássica e da computação quântica é um reflexo direto da natureza dos sistemas físicos que são utilizados para implementar concretamente cada uma dessas computações. Esta dissertação apresenta o algoritmo de Shor para fatoração em um computador quântico. Na seqüência, introduzimos no capítulo 1 alguns conceitos básicos da computação clássica com o objetivo de criar um ambiente de idéias favorável à apresentação da computação quântica como uma extensão, tão natural quanto possível, do modelo clássico computacional. Assim, no capítulo 2, apresentamos as bases do formalismo matemático que modela a computação quântica, atendo-nos apenas aos aspectos conceituais que são, direta ou indiretamente, aplicados na descrição do algoritmo de Shor. Os capítulos 3 e 4 são dedicados à apresentação do algoritmo de fatoração de Shor, feita em duas partes. A primeira diz respeito a parte não quântica e aborda os aspectos algébricos do algoritmo. Também é demonstrado o teorema que assegura a viabilidade probabilística da solução desse problema. No capítulo 4, apresentamos a parte quântica do algoritmo de Shor. O ponto alto da dissertação é alcançado mostrando-se como encontrar a ordem de um inteiro módulo o número a ser fatorado relativamente primo com este, conciliando o algoritmo quântico com uma interpretação clássica de seus dados de saída, mediante o uso da expansão de um número racional em frações contínuas

•Jan 1, 2003•0 citations

Busca em computadores quânticos

André Soranzzo Mota, Marcelo Terra Cunha

O objetivo do trabalho é estudar algoritmos quânticos de busca, usados em computadores quânticos. Até então, algoritmos de busca utilizados em computadores clássicos dependem da estrutura na qual os dados estão organizados para serem ou não eficientes. Para conjuntos de dados não estruturados, o único jeito é verificar cada elemento do conjunto procurando o elemento passado na entrada do algoritmo, e dependendo da quantidade de elementos nesse conjunto, pode-se levar muito tempo, mesmo para computadores muito rápidos. Portanto, algoritmos que realizem busca de maneira eficiente são um atrativo e tanto para cientistas da computação, que podem pensar em inúmeras aplicações dos mesmos e tornar vários softwares cada vez mais eficientes. Tendo isso em vista, a computação quântica traz artifícios inexistentes na computação clássica que podem acelerar esse processo, como, por exemplo, o paralelismo quântico. Basicamente, consiste na capacidade de sobrepor todos os dados do conjunto em um único registrador, ou a grosso modo, analisar todos ao mesmo tempo, apesar de não ser tão simples quanto isso. É baseado nisso que temos o Algoritmo de Grover, que utilizando o paralelismo quântico, e reflexões no conjunto de dados, através do uso de transformações unitárias feitas por portas quânticas, temos uma probabilidade alta de que quando medirmos este registrador quântico, termos como resultado o dado procurado.

Revista dos Trabalhos de Iniciação Científica da UNICAMP•Dec 4, 2018•1 citation

A utilização do algoritmo quântico de busca em problemas da teoria da informação.

N. A. Oliveira, Nigini Oliveira

Esta dissertação apresenta dois resultados da aplicação do Algoritmo Quântico de Busca (Algoritmo de Grover) em problemas da área da Teoria da Informação. O primeiro deles visa testar a qualidade de um Código de Bloco Linear dado que uma importante característica dos mesmos é a distância mínima d entre as palavras que o compõe. A solução apresentada utiliza o Algoritmo da Contagem Quântica para melhorar o desempenho do cálculo de d, para o qual algoritmos clássicos são normalmente intratáveis. Assim tal distância pode ser utilizada como comparativo entre códigos diferentes. O segundo problema estudado é denominado Ataque Quântico ao Gerador Pseudo-aleatório de Blum-Micali. Tais geradores são utilizados em simulações de sistemas físicos e criptografia, substituindo geradores de números realmente aleatórios que são de difícil implementação. Neste trabalho utiliza-se o Algoritmo de Grover para quebrar a segurança do processo de geração dos números.

•Jul 12, 2007•0 citations

Algoritmos quânticos para a geração de unitários pseudo-aleatórios

Igor Diniz

Investigamos a geração de operações unitárias quânticas aleatórias sobre certos aspectos. Mostramos que um determinado algoritmo de interação de pares gera unitários pseudo-aleatórios e mostramos como esses unitários podem substituir unitários completamente aleatórios na implementação de outros algoritmos quânticos, com economia exponencial de recursos. Investigamos em detalhe como a interação entre pares afeta o tempo de convergência do algoritmo

•Jan 1, 2009•0 citations

Ataques quânticos e os criptossistemas de McEliece

Jorge Manuel Tavares Brandão

0 algoritmo de Shor e a evolução da computação quântica trouxeram grandes ameaças à segurança dos criptossistemas atuais. Pela necessidade de se encontrar novas alternativas, surgiu a criptografia pós-quântica. Esta dissertação pode ser dividida em três partes principais. Na primeira apresentamos alguns elementos de teoria dos números e descrevemos um criptossistema clássico, o RSA, cuja segurança pode ser facilmente quebrada recorrendo a ataques quânticos. Na segunda parte descrevemos a implementação do algoritmo de Shor, que é um ataque a esse e a todos os criptossistemas cuja segurança reside no problema da fatorização ou no problema do logaritmo discreto. Na implementação deste algoritmo minimizámos o número de qubits necessários. Para isso, utilizámos transformadas de Fourier quânticas para realizar operações como a adição, a multiplicação e a exponenciação modular. Assim, segundo a nossa abordagem, precisámos de apenas Li + 2L2 + 3 qubits, para implementar o algoritmo de Shor, ou seja, para encontrar o período da função /(x) = ax mod N, onde Li corresponde ao número de qubits necessários para representar x tal que N2 < 2L1 < 2N2 e L2 corresponde ao número de qubits necessários para representar N. Por fim, na última parte desta dissertação, apresentaremos elementos da criptografia pós-quântica, em particular, um protocolo proposto por nós. Este é uma nova variante do criptossistema de McEliece, no qual se propõe o uso de códigos convolucionais em vez do uso de códigos de bloco. Assim, a parte codificadora da nossa chave pública, que denotaremos por G'(D), será ela própria convolucional. Ao estudarmos várias possibilidades de ataques para este criptossistema, verificámos que, em comparação com as restantes variantes, para uma chave pública menor conseguimos ter um fator de trabalho muito maior, o que se traduz numa maior segurança

•Jul 31, 2018•0 citations
Resumo-A utilizac ¸ão de seq üências pseudo-aleatórias é de grande importância em diversas aplicac ¸ões da criptografia.Um ataque a um gerador pseudo-aleatório objetiva reproduzir uma dada seq üência pseudo-aleatória a partir de um conjunto de termos dessa seq üência.Classicamente, esse é um problema de difícil soluc ¸ão, ou seja, não existe algoritmos conhecidos em tempo polinomial que realizem esta tarefa.Por outro lado, o desenvolvimento de algoritmos quânticos vem mostrando que determinados tipos de problemas podem ser resolvidos de modo mais eficiente.Neste artigo, é apresentado um circuito quântico que realiza um ataque ao gerador Blum-Micali apresentando um ganho no n úmero de operac ¸ões em relac ¸ão aos algoritmos clássicos conhecidos. Palavras-Chave-Gerador Blum-
Este trabalho apresenta um ataque quântico de comprometimento permanente ao gerador pseudo-aleatório de Blum-Micali. A segurança deste gerador, classificado como criptograficamente seguro, baseia-se na hipótese de intratabilidade do problema do logaritmo discreto perante a Computação Clássica. O ataque proposto faz uso do algoritmo quântico de busca em conjunto com o algoritmo quântico para o logaritmo discreto para comprometer a imprevisibilidade do gerador, recuperando todas as saídas passadas e futuras do mesmo. O presente trabalho também descreve generalizações deste ataque que o adequam a uma gama mais vasta de geradores, incluindo geradores da Construção de Blum-Micali e geradores com múltiplos predicados difíceis. Tais generalizações também abrangem a realização de ataques em situações adversas, por exemplo, quando o adversário captura bits não consecutivos ou quando há menos bits que o requerido. Comparado à sua contrapartida clássica, o algoritmo quântico proposto nesse trabalho possui um ganho quadrático em relação à recuperação do representante do estado interno do gerador, seguido de um ganho superpolinomial na obtenção dos demais elementos do estado interno. Estes resultados caracterizam ameaças,elaboradas com Computação Quântica, contra a segurança de geradores utilizados em diversas aplicações criptográficas.
Sistemas de criptografia largamente difundidos como o RSA fundamentam a sua eficiência na suposição de que, em termos práticos, é impossível fatorar números inteiros suficientemente grandes em uma escala de tempo aceitável. Mais precisamente, não existem, até o momento, algoritmos de fatoração em tempo polinomial que possam ser implementados nos atuais computadores. Dentre os algoritmos conhecidos, o mais eficiente requer um tempo computacional de ordem exponencial na quantidade de dígitos binários do número a ser fatorado. Em 1994, baseado nos trabalhos anteriores de Benioff, Bennett, Deutsch, Feynman e Simon, dentre outros, Peter Shor apresentou um algoritmo de fatoração que requer assintoticamente uma quantidade em ordem polinomial de passos em um computador quântico para fatorar um número inteiro de tamanho arbitrário. Esse algoritmo ao invés de abordar o problema de decompor tal número em dois fatores não triviais pelo método direto de divisões sucessivas, utiliza o problema equivalente de encontrar a ordem de um certo inteiro modulo o número fatorado, onde esse inteiro é escolhido aleatoriamente relativamente primo com o número fatorado. Shor faz uso de um algoritmo quântico para calcular essa ordem. A computação quântica revela um paradigma computacional bastante adverso da computação clássica. Enquanto esta última é realizada através de operações binárias determinísticas com base na lógica booleana clássica, a computação quântica fundamenta as suas operações nos postulados que descrevem o comportamento quântico da matéria. Portanto, é probabilística no seu modus operandi. Essa diferença entre os formalismos lógicos da computação clássica e da computação quântica é um reflexo direto da natureza dos sistemas físicos que são utilizados para implementar concretamente cada uma dessas computações. Esta dissertação apresenta o algoritmo de Shor para fatoração em um computador quântico. Na seqüência, introduzimos no capítulo 1 alguns conceitos básicos da computação clássica com o objetivo de criar um ambiente de idéias favorável à apresentação da computação quântica como uma extensão, tão natural quanto possível, do modelo clássico computacional. Assim, no capítulo 2, apresentamos as bases do formalismo matemático que modela a computação quântica, atendo-nos apenas aos aspectos conceituais que são, direta ou indiretamente, aplicados na descrição do algoritmo de Shor. Os capítulos 3 e 4 são dedicados à apresentação do algoritmo de fatoração de Shor, feita em duas partes. A primeira diz respeito a parte não quântica e aborda os aspectos algébricos do algoritmo. Também é demonstrado o teorema que assegura a viabilidade probabilística da solução desse problema. No capítulo 4, apresentamos a parte quântica do algoritmo de Shor. O ponto alto da dissertação é alcançado mostrando-se como encontrar a ordem de um inteiro módulo o número a ser fatorado relativamente primo com este, conciliando o algoritmo quântico com uma interpretação clássica de seus dados de saída, mediante o uso da expansão de um número racional em frações contínuas
O objetivo do trabalho é estudar algoritmos quânticos de busca, usados em computadores quânticos. Até então, algoritmos de busca utilizados em computadores clássicos dependem da estrutura na qual os dados estão organizados para serem ou não eficientes. Para conjuntos de dados não estruturados, o único jeito é verificar cada elemento do conjunto procurando o elemento passado na entrada do algoritmo, e dependendo da quantidade de elementos nesse conjunto, pode-se levar muito tempo, mesmo para computadores muito rápidos. Portanto, algoritmos que realizem busca de maneira eficiente são um atrativo e tanto para cientistas da computação, que podem pensar em inúmeras aplicações dos mesmos e tornar vários softwares cada vez mais eficientes. Tendo isso em vista, a computação quântica traz artifícios inexistentes na computação clássica que podem acelerar esse processo, como, por exemplo, o paralelismo quântico. Basicamente, consiste na capacidade de sobrepor todos os dados do conjunto em um único registrador, ou a grosso modo, analisar todos ao mesmo tempo, apesar de não ser tão simples quanto isso. É baseado nisso que temos o Algoritmo de Grover, que utilizando o paralelismo quântico, e reflexões no conjunto de dados, através do uso de transformações unitárias feitas por portas quânticas, temos uma probabilidade alta de que quando medirmos este registrador quântico, termos como resultado o dado procurado.
Esta dissertação apresenta dois resultados da aplicação do Algoritmo Quântico de Busca (Algoritmo de Grover) em problemas da área da Teoria da Informação. O primeiro deles visa testar a qualidade de um Código de Bloco Linear dado que uma importante característica dos mesmos é a distância mínima d entre as palavras que o compõe. A solução apresentada utiliza o Algoritmo da Contagem Quântica para melhorar o desempenho do cálculo de d, para o qual algoritmos clássicos são normalmente intratáveis. Assim tal distância pode ser utilizada como comparativo entre códigos diferentes. O segundo problema estudado é denominado Ataque Quântico ao Gerador Pseudo-aleatório de Blum-Micali. Tais geradores são utilizados em simulações de sistemas físicos e criptografia, substituindo geradores de números realmente aleatórios que são de difícil implementação. Neste trabalho utiliza-se o Algoritmo de Grover para quebrar a segurança do processo de geração dos números.
0 algoritmo de Shor e a evolução da computação quântica trouxeram grandes ameaças à segurança dos criptossistemas atuais. Pela necessidade de se encontrar novas alternativas, surgiu a criptografia pós-quântica. Esta dissertação pode ser dividida em três partes principais. Na primeira apresentamos alguns elementos de teoria dos números e descrevemos um criptossistema clássico, o RSA, cuja segurança pode ser facilmente quebrada recorrendo a ataques quânticos. Na segunda parte descrevemos a implementação do algoritmo de Shor, que é um ataque a esse e a todos os criptossistemas cuja segurança reside no problema da fatorização ou no problema do logaritmo discreto. Na implementação deste algoritmo minimizámos o número de qubits necessários. Para isso, utilizámos transformadas de Fourier quânticas para realizar operações como a adição, a multiplicação e a exponenciação modular. Assim, segundo a nossa abordagem, precisámos de apenas Li + 2L2 + 3 qubits, para implementar o algoritmo de Shor, ou seja, para encontrar o período da função /(x) = ax mod N, onde Li corresponde ao número de qubits necessários para representar x tal que N2 < 2L1 < 2N2 e L2 corresponde ao número de qubits necessários para representar N. Por fim, na última parte desta dissertação, apresentaremos elementos da criptografia pós-quântica, em particular, um protocolo proposto por nós. Este é uma nova variante do criptossistema de McEliece, no qual se propõe o uso de códigos convolucionais em vez do uso de códigos de bloco. Assim, a parte codificadora da nossa chave pública, que denotaremos por G'(D), será ela própria convolucional. Ao estudarmos várias possibilidades de ataques para este criptossistema, verificámos que, em comparação com as restantes variantes, para uma chave pública menor conseguimos ter um fator de trabalho muito maior, o que se traduz numa maior segurança