Rsa encryption

Cassia Calaço

November 19, 2014

CompSci 469

Assignment #3

Understanding Common Factor Attacks: An RSA-Cracking Puzzle

Two groups of researches brought the conclusion that large numbers of RSA encryption in use today in the internet are not security because they can be cracked very easy. The study say that the keys are vulnerable because of the small number of possibilities that the keys can be, and also because of the random system used. The objective of this puzzle is show how this can happen and why it can happen.

RSA is a technique to encrypt and decrypt messages, and the main principle to trust this technique is that the prime numbers selected can be only cracked down by one way. To generate a key, you have to found two numbers p and q, and multiplying this two will generate the key n. RSA should be trusted because is easy to multiply this numbers and generate n, but it’s too hard to find p and q just knowing n.

But have some techniques to discovery the numbers p and q. One of them is to factoring the numbers, but this is too hard because the numbers that should be used by RSA should be at least 1024 bits, so factoring this large numbers will be hard. Beside the public and private key p and q the RSA algorithm needs numbers d and e (e to encrypt and d to decrypt). The key n should be a given/public key, to make sure the receiver of the message will decrypt the message right.

The point of the RSA is to keep p and q in secret, so will be really hard for someone to guess p and q just factoring n. But if you can find the factors of any of the three numbers, so the key it’s not security anymore. You can crack a RSA algorithm just with the method of “gcd” (the largest integer that both of numbers are divisible by).

If they are 2 numbers  and, and   and, so the gcd () = 1, but this can’t be nothing if you don’t know no information about a, b, c or d. And this is a point for RSA algorithm. [pic 1][pic 2][pic 3][pic 4][pic 5]

But if someone re-used a prime between two different RSA keys, so we lost one different number and now we have a, b and c. And  and, so in this case the gcd () will be b (the common number that divided  and). So if someone was looking for this public values and discovery b, they can crack the two RSA keys, revealing the private keys from the privates.[pic 6][pic 7][pic 8][pic 9][pic 10]

That means that RSA key can’t be re-used, because the two keys are not secure anymore. In the theory, the prime numbers are generated by random algorithms and the numbers should be at least size, so two prime numbers will generate an n key with. The theorem called prime number can estimate how many prime numbers around this size can exist. The result is 0.28%, and this result also include numbers which are never prime. This experiment shows that are a lot of numbers that can be chosen, so is incredibly that even humans will choose the same twice by accident.[pic 11][pic 12]