Editing RSA cryptosystem (section)

==History==
[[File:Adi Shamir 2009 crop.jpg|thumb|upright=0.7|[[Adi Shamir]], co-inventor of RSA (the others are [[Ron Rivest]] and [[Leonard Adleman]])]]
The idea of an asymmetric public-private key cryptosystem is attributed to [[Whitfield Diffie]] and [[Martin Hellman]], who published this concept in 1976. They also introduced digital signatures and attempted to apply number theory. Their formulation used a shared-secret-key created from exponentiation of some number, modulo a prime number. However, they left open the problem of realizing a one-way function, possibly because the difficulty of factoring was not well-studied at the time.<ref>{{Cite journal |title = New directions in cryptography |journal = IEEE Transactions on Information Theory |date = November 1976 |issn = 0018-9448 |pages = 644–654 |volume = 22 |issue = 6 |doi = 10.1109/TIT.1976.1055638 |first1 = W. |last1 = Diffie |first2 = M. E. |last2 = Hellman |citeseerx = 10.1.1.37.9720}}</ref> Moreover, like [[Diffie–Hellman key exchange|Diffie-Hellman]], RSA is based on [[modular exponentiation]].

[[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. They tried many approaches, including "[[Knapsack problem|knapsack]]-based" and "permutation polynomials". For a time, they thought what they wanted to achieve was impossible due to contradictory requirements.<ref>{{Cite web |url = https://people.csail.mit.edu/rivest/pubs/ARS03.rivest-slides.pdf |title = The Early Days of RSA – History and Lessons |last = Rivest |first = Ronald}}</ref> 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.<ref>{{Cite web |url = http://www.math.uchicago.edu/~may/VIGRE/VIGRE2007/REUPapers/FINALAPP/Calderbank.pdf |title = The RSA Cryptosystem: History, Algorithm, Primes |date = 2007-08-20 |last = Calderbank |first = Michael}}</ref> Rivest, unable to sleep, lay on the couch with a math textbook and started thinking about their one-way function. He spent the rest of the night formalizing his idea, and he had much of the paper ready by daybreak. The algorithm is now known as RSA{{snd}} the initials of their surnames in same order as their paper.<ref name="SIAM">{{cite journal |url=http://www.msri.org/people/members/sara/articles/rsa.pdf |journal=SIAM News |volume=36 |issue=5 |date=June 2003 |title=Still Guarding Secrets after Years of Attacks, RSA Earns Accolades for its Founders |first=Sara |last=Robinson }}</ref>

[[Clifford Cocks]], an English [[mathematician]] working for the [[United Kingdom|British]] intelligence agency [[Government Communications Headquarters]] (GCHQ), described a similar system in an internal document in 1973.<ref>{{Cite web |url=https://www.gchq.gov.uk/sites/default/files/document_files/Cliff%20Cocks%20paper%2019731120.pdf |title=A Note on Non-Secret Encryption |last=Cocks |first=C. C. |author-link=Clifford Cocks |date=20 November 1973 |website=www.gchq.gov.uk |access-date=2017-05-30 |archive-url=https://web.archive.org/web/20180928121748/https://www.gchq.gov.uk/sites/default/files/document_files/Cliff%20Cocks%20paper%2019731120.pdf |archive-date=28 September 2018 |url-status=dead}}</ref> However, given the relatively expensive computers needed to implement it at the time, it was considered to be mostly a curiosity and, as far as is publicly known, was never deployed. His ideas and concepts were not revealed until 1997 due to its top-secret classification.

Kid-RSA (KRSA) is a simplified, insecure public-key cipher published in 1997, designed for educational purposes. Some people feel that learning Kid-RSA gives insight into RSA and other public-key ciphers, analogous to [[Data Encryption Standard#Simplified DES|simplified DES]].<ref>
Jim Sauerberg.
[https://ww2.amstat.org/mam/06/Sauerberg_PKC-essay.html "From Private to Public Key Ciphers in Three Easy Steps"].
</ref><ref>
Margaret Cozzens and Steven J. Miller.
[https://books.google.com/books?id=GbKyAAAAQBAJ "The Mathematics of Encryption: An Elementary Introduction"].
p. 180.
</ref><ref>
Alasdair McAndrew.
[https://books.google.com/books?id=9lTRBQAAQBAJ "Introduction to Cryptography with Open-Source Software"].
p. 12.
</ref><ref>
Surender R. Chiluka.
[https://web.archive.org/web/20220319203917/https://www.cs.uri.edu/cryptography/publickeykidkrypto.htm "Public key Cryptography"].
</ref><ref>
Neal Koblitz.
[https://sites.math.washington.edu/~koblitz/crlogia.html "Cryptography As a Teaching Tool"].
Cryptologia, Vol. 21, No. 4 (1997).
</ref>