Ataques quânticos e os criptossistemas de McEliece

Abstract

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

Shor’s algorithm and the evolution of quantum computing brought big threats to the security of the current cryptosystems. The need to find new alternatives created what is known as post-quantum cryptography. This dissertation can be splitted into three main parts. In the first one, we present elements of number theory and we describe a classical cryptosystem, the RSA, whose security can be easily broken using quantum attacks. In the second part, we describe the implementation of Shor’s algorithm, which is an attack to RSA but also to all the cryptosystems whose safety lies in the factorization problem or in the discrete logarithm problem. In the implementation of this algorithm we minimized the number of qubits required. For this, we used quantum Fourier transforms to perform operations such as addition, multiplication and modular exponentiation. Thus, according to our approach, we need only Li + 2L% + 3 qubits to implement the Shor’s algorithm, that is, to find the period of the function f(x) = ax mod N, where Z] is the number of bits needed to represent x such that N2 < 2L1 < 2N2, and L2 is the number of bits needed to represent N. Finally, in the last part of this dissertation, we present elements of post-quantum cryptography, in particular, a new protocol proposed by us. This is a new variant of the McEliece cryptosystem, on which we propose the use of convolutional codes instead of block codes. Thus, the encoder part of our public key, which we will denote by G'(D), will be itself convolutional. By studying several possibilities of attacks for this cryptosystem, we verified that, compared to the other variants, for a smaller public key we can have a much larger work factor, which can be translated in a greater security