Prime numbers: an easy way to make a message undecryptable

This is the second part of the narrative rooted in one thesis. For the first part, please read previous post.


In 1977, Ron Rivest, Adi Shamir and Leonard Adleman[1] introduced RSA algorithm that was one of the first practical example of asymmetric cryptography. This property it derived from the difficulty of factoring the product of two large prime numbers. It works as follows: a user creates and then publishes a public key based on two large prime numbers, which are kept secret. The whole procedure is described below:

  1. It should be taken two large prime numbers p and q;
  2. Then, the n is formulated as a multiplication of p and q (n = p * q);
  3. The random number d is taken so that it doesn’t have the same factors (except 1) with (p-1)*(q-1);
  4. Then, the e is formulated so that the equation (e*d) mod ((p-1) * (q-1)) = 1 takes place;
  5. Finally, we call pair (e,n) the public key, and (d,n) the private key.

The first step — search for large prime numbers — is the crucial one because the strength of cryptography (it’s resistance to cryptanalysis) of RSA is backed by the complexity of factoring the product of primes mentioned above. In fact, in 1978 it was almost impossible to derive them from n if we take, say, 100-digit primes p and q (in a sum making n a 200-digit number). The following table is the one the authors of RSA presented in 1978, where they assumed that the Schroeppel factoring algorithm takes one microsecond to compute, and so the time for “cracking” their cryptosystem will be (recall that they proposed 200-digit n):

However, currently the things go differently. Today, the n no longer than 300-digit can be factored on a regular PC in just several hours, this the key should be 4–7 times longer. It becomes clear that with the increase in computational capacities it becomes harder to secure the message or create a trustful signature without increasing the length of the n. Although it’s seemingly close to impossible to crack a 4096-bit keys, it’s inefficient to use such a system because it requires large storage volumes.

As already mentioned, Bitcoin uses different public key cryptography system backed by the specific features of elliptic curves. Because of its features, it becomes possible to use lower amounts of storage and its essentially facilitate CPU used. Coupled with hash function (it’s to be presented later) it is the solid ground of the extreme effectiveness of Bitcoin so it’s worth presenting here.

[1] Rivest R., Shamir A., Adleman L. A method for obtaining digital signatures and public-key cryptosystems // Commun. ACM — New York City: ACM, 1978. — Vol. 21, Iss. 2. — P. 120–126.

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.