RSA (cryptosystem)
The initialism "RSA" comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publicly described the algorithm in 1977.
An equivalent system was developed secretly in 1973 at Government Communications Headquarters (GCHQ), the British signals intelligence agency, by the English mathematician Clifford Cocks.
An RSA user creates and publishes a public key based on two large prime numbers, along with an auxiliary value.
The idea of an asymmetric public-private key cryptosystem is attributed to Whitfield Diffie and Martin Hellman, who published this concept in 1976.
Ron Rivest, Adi Shamir, and Leonard Adleman at the Massachusetts Institute of Technology made several attempts over the course of a year to create a function that was hard to invert.
Rivest and Shamir, as computer scientists, proposed many potential functions, while Adleman, as a mathematician, was responsible for finding their weaknesses.
[5] In April 1977, they spent Passover at the house of a student and drank a good deal of wine before returning to their homes at around midnight.
[6] Rivest, unable to sleep, lay on the couch with a math textbook and started thinking about their one-way function.
[7] Clifford Cocks, an English mathematician working for the British intelligence agency Government Communications Headquarters (GCHQ), described a similar system in an internal document in 1973.
Some people feel that learning Kid-RSA gives insight into RSA and other public-key ciphers, analogous to simplified DES.
The possibility of using Euler totient function results also from Lagrange's theorem applied to the multiplicative group of integers modulo pq.
[1][18][19][failed verification][20][failed verification] Note: The authors of the original RSA paper carry out the key generation by choosing d and then computing e as the modular multiplicative inverse of d modulo φ(n), whereas most current implementations of RSA, such as those following PKCS#1, do the reverse (choose e and compute d).
To avoid these problems, practical RSA implementations typically embed some form of structured, randomized padding into the value m before encrypting it.
RSA padding schemes must be carefully designed so as to prevent sophisticated attacks that may be facilitated by a predictable message structure.
Furthermore, at Eurocrypt 2000, Coron et al.[25] showed that for some types of messages, this padding does not provide a high enough level of security.
[26] For efficiency, many popular crypto libraries (such as OpenSSL, Java and .NET) use for decryption and signing the following optimization based on the Chinese remainder theorem.
Full decryption of an RSA ciphertext is thought to be infeasible on the assumption that both of these problems are hard, i.e., no efficient algorithm exists for solving them.
[29] By 2009, Benjamin Moody could factor an 512-bit RSA key in 73 days using only public software (GGNFS) and his desktop computer (a dual-core Athlon64 with a 1,900 MHz CPU).
Rivest, Shamir, and Adleman noted[1] that Miller has shown that – assuming the truth of the extended Riemann hypothesis – finding d from n and e is as hard as factoring n into p and q (up to a polynomial time difference).
[30] However, Rivest, Shamir, and Adleman noted, in section IX/D of their paper, that they had not found a proof that inverting RSA is as hard as factoring.
[34] A theoretical hardware device named TWIRL, described by Shamir and Tromer in 2003, called into question the security of 1024-bit keys.
Michael J. Wiener showed that if p is between q and 2q (which is quite typical) and d < n1/4/3, then d can be computed efficiently from n and e.[35] There is no known attack against small public exponents such as e = 3, provided that the proper padding is used.
In October 2017, a team of researchers from Masaryk University announced the ROCA vulnerability, which affects RSA keys generated by an algorithm embodied in a library from Infineon known as RSALib.
An analysis comparing millions of public keys gathered from the Internet was carried out in early 2012 by Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung and Christophe Wachter.
In 2003, Boneh and Brumley demonstrated a more practical attack capable of recovering RSA factorizations over a network connection (e.g., from a Secure Sockets Layer (SSL)-enabled webserver).
[40] This attack takes advantage of information leaked by the Chinese remainder theorem optimization used by many RSA implementations.
Due to flaws with the PKCS #1 scheme, Bleichenbacher was able to mount a practical attack against RSA implementations of the Secure Sockets Layer protocol and to recover session keys.
In their paper, "On the Power of Simple Branch Prediction Analysis",[43] the authors of SBPA (Onur Aciicmez and Cetin Kaya Koc) claim to have discovered 508 out of 512 bits of an RSA key in 10 iterations.
There are many details to keep in mind in order to implement RSA securely (strong PRNG, acceptable public exponent, etc.).
This makes the implementation challenging, to the point the book Practical Cryptography With Go suggests avoiding RSA if possible.
