Grupos pseudo-livres, primos seguros e criptografia RSA

AUTOR(ES)

Marcelo Gama da Silva

DATA DE PUBLICAÇÃO

2007

RESUMO

When a cryptographic scheme is defined over a group, encrypting messages is equivalent to assigning values in this group to variables of some equation, whereas breaking this scheme is âto discoverâ which values were assigned to those variables. Therefore, the security of such schemes is connected to the hardness to solve equations over groups. The use of free groups would be a possible solution to this problem; however, only âtrivialâ equations can be solved over free groups. Moreover, free groups are infinite and this is not interesting from a computational perspective. An alternative solution was proposed by Susan Hohenberger in 2003, originating the notion of âpseudo-free groupsâ, wich was improved by R. Rivest. Informally, a pseudo-free group is characterized by the fact that it cannot be distinguished, in an efficient way, from a free group. From a computational point of view, this implies that the probability of solving a non-trivial equation over a pseudo-free group is negligible. So, this is a suitable environment to deal with questions about security of cryptographic schemes. Two notions deserve to be pointed. The notion of pseudo-free groups is essential to modern cryptography whereas the notion of safe primes is relevanto to the RSA cryptosystem. Our work has three main objectives. We start studying some of so called computationally hard problems and its use to develop safe cryptosystems. The second objective is the detailed study of the Micciancioâs theorem on the pseudo-freeness of the RSA groups. Finally, we will study the generation of safe primes, because these numbers are related to the RSA security. In particular, we propose a new algorithm to generate safe primes wich uses a theorem from Euler and Lagrange and the Gaussâs quadratic reciprocity law to avoid most primality tests

ASSUNTO(S)

grupos pseudo-livres primos seguros safe primes ciencia da computacao rsa pseudo-free groups rsa

Documentos Relacionados

• Ideais fechados e primos em anéis de polinômios e extensões livres centralizantes
• ESPAÇOS LIVRES "ESQUECIDOS" E GRUPOS SOCIAIS "OMITIDOS"
• Extensões cíclicas de grupos pro-p livres e representações inteiras p-ádicas
• Ideais fechados e primos em skew anéis de grupos parciais
• Torção no complemento pró-finito de grupos livres de torção