Why are "large primes" used in RSA / encryption?

Question

I have studied the theory of public key encryption, but I lack communication with the physical world. eg.

I was told that good RSA encryption should be based on primes with 300 decimal digits, but why? who invented this number? How long will it take to break such encryption (statistics about different machines).

I tried Google, but could not find what I wanted. is anyone

thanks

Answer 1

The key to asymmetric cryptography is to have an asymmetric function that allows you to decrypt a message encrypted with an asymmetric key, without allowing you to find another key. In RSA, the function used is based on factorization of primes, but this is not the only option (the Elliptic curve is another example).

So basically you need two primes to generate the RSA key pair. If you can split the public key and find these primes, you can find the private key. All RSA security is based on the fact that it is not easy to decompose large composite numbers , so the key length greatly changes the reliability of the RSA algorithm.

There are competitions on factorization of large prime numbers with calculators every year with a good price. The final step of factoring the RSA key was made in 2009 by marking up 768 bit keys. That's why now you need to use at least 2048 bit keys.

As usual, Wikipedia is a good reference to RSA.

Answer 2

All public key algorithms are based on the trapdoor function , that is, mathematical constructs that are "easily" calculated in one way, but "difficult" if you do not have additional information (used as a private key), in which case the opposite becomes "easy" .

“Easy” and “hard” are simply high-quality adjectives that are always more formally defined in terms of computational complexity . "Hard" very often refers to calculations that cannot be solved in polynomial time O (n ^x ) for some fixed x and where n is the input.

In the case of RSA, the “light” function is a modular exponentiation of C = M ^e mod N, where factors N are kept secret. The “tough” problem is to find the e-th root of C (i.e., M). Of course, “hard” does not mean that it is always difficult, but (intuitively) that increasing the size of N by a certain factor increases complexity by a much larger factor.

The sizes of the recommended module (2048 bits or 617 decimal digits) refer to the available computing power at the moment, so if you stick to them, you are sure that it will be extremely expensive for an attacker to break it. For more details, I should direct you to a brilliant answer to .SE cryptography (go and upvote: -)).

Finally, in order to have a hatch, N is constructed to be a composite number. This theory, in order to increase productivity, N can have more than two factors, but the general safety rule is that all factors must be balanced and have approximately the same size. This means that if you have K factors and N bits are B bits, each factor is approximately B / K bits longs.

This problem to solve is not the same as the problem of the whole factorization problem . The two are related in that if you can determine the factor N, you can calculate the private key by repeating what the side that generated the key did. As a rule, the exponent e used is very small (3); it cannot be ruled out that someday someone will develop an algorithm for calculating the e-th without factoring N.

EDIT: Fixed number of decimal digits for RSA key module with a length of 2048 bits.

Answer 3

RSA uses the idea of ​​unidirectional mathematical functions, so it’s easy to encrypt and decrypt if you have a key, but hard (since it requires many, many processor cycles) to decrypt if you do not have a key. Even before they thought about using prime numbers, mathematicians determined the need for a one-way function.

The first method they aimed at was that if your “key” is a prime number and your message is a different number, then you can encrypt by multiplying them together. Someone with a key can easily split a prime number and receive a message, but for someone who does not have a prime number, finding the key of a prime number is difficult.