The other day I wrote my implementation of the RSA public key encryption algorithm. I also did a simple hack of this algorithm, so I wanted to write a short note on this topic. RSA’s resistance to hacking is based on the factorization problem. Factorization… What a scary word.
It’s not all that bad
In fact, at the first stage of creating keys, we take two random numbers, but the numbers should only be divisible by themselves and one – prime numbers.
Let’s call them p and q. Next, we should get the number n = p *q. It will be used for further key generation, the keys in turn will be used for encryption, decryption of messages. In the final version of the private and public key, the number n will be transmitted unchanged.
Let’s say we have one of the RSA keys and an encrypted message. We extract the number n from the key and start hacking it.
Factorize n
Factorization – decomposition of a number into prime factors. First, we extract the number n from the key (on real keys, this can be done using openssl), let’s say n = 35. Then we decompose into prime factors n = 35 = 5 * 7, this is our p and q. Now we can regenerate keys using the obtained p, q, decrypt the message and encrypt, ensuring the visibility of the original author.
Qubits are not that simple
Is it really possible to break any RSA so easily? Actually, no, the numbers p, q are taken deliberately large so that the factorization task on classical computers would take a very long time (10 years to some degree)
However, using Shor’s quantum algorithm, it is possible to factor a number in a very short time. At the moment, articles on this topic state the time of multiplication of this number, i.e., practically instantly. For Shor’s algorithm to work, it is necessary to implement quantum computers with a large number of qubits. In 2001, IBM factored the number 15 into prime factors using 7 qubits. So we will have to wait a long time for this moment, by which time we will have switched to post-quantum encryption algorithms.
Touch Shor
Peter Shor talks about his factorization algorithm
To try out Shor’s algorithm on a quantum simulator, you can install ProjectQ, whose examples include an implementation of shor.py that allows you to factorize a number entered by the user. On the simulator, the execution time is depressing, but it seems to simulate the work of a quantum computer in a fun and playful way.
Articles:
http://www.pagedon.com/rsa-explained-simply/my_programming/
http://southernpacificreview.com/2014/01/06/rsa-key-generation-example/
https://0day.work/how-i-recovered-your-private-key-or-why-small-keys-are-bad/
RSA implementation in Python:
https://github.com/demensdeum/RSA-Python
