Editing Public-key cryptography (section)

== History ==
During the early [[history of cryptography]], two parties would rely upon a key that they would exchange by means of a secure, but non-cryptographic, method such as a face-to-face meeting, or a trusted courier. This key, which both parties must then keep absolutely secret, could then be used to exchange encrypted messages. A number of significant practical difficulties arise with this approach to [[key distribution|distributing keys]].

=== Anticipation ===
In his 1874 book ''The Principles of Science'', [[William Stanley Jevons]] wrote:<ref name=TPS_1>{{cite book| title=The Principles of Science: A Treatise on Logic and Scientific Method| author=Jevons, W.S.| url=https://archive.org/details/principlesofscie00jevorich/principlesofscie00jevorich/page/n166/mode/1up?view=theater| publisher=[[Macmillan & Co.]]| page=141| date=1874| access-date=18 January 2024}}</ref><blockquote>
Can the reader say what two numbers multiplied together will produce the number [[William Stanley Jevons#Jevons' number|8616460799]]?<ref name=JN_1>{{cite web| title=Jevons' Number| author=Weisstein, E.W.| url=https://mathworld.wolfram.com/JevonsNumber.html| publisher=[[MathWorld]]| date=2024| access-date=18 January 2024}}</ref> I think it unlikely that anyone but myself will ever know.<ref name=TPS_1/></blockquote>
Here he described the relationship of [[one-way function]]s to cryptography, and went on to discuss specifically the [[factorization]] problem used to create a [[trapdoor function]]. In July 1996, mathematician [[Solomon W. Golomb]] said: "Jevons anticipated a key feature of the RSA Algorithm for public key cryptography, although he certainly did not invent the concept of public key cryptography."<ref>{{cite journal |doi=10.1080/0161-119691884933 |year=1996 |last=Golob |first=Solomon W. |journal=Cryptologia |volume=20 |issue=3 |page=243|title=On Factoring Jevons' Number |s2cid=205488749 }}</ref>

=== Classified discovery ===
In 1970, [[James H. Ellis]], a British cryptographer at the UK [[Government Communications Headquarters]] (GCHQ), conceived of the possibility of "non-secret encryption", (now called public key cryptography), but could see no way to implement it.<ref>{{cite web| last=Ellis| first=James H.| title=The Possibility of Secure Non-secret Digital Encryption| date=January 1970|url=https://cryptocellar.org/cesg/possnse.pdf| publisher=CryptoCellar| access-date=18 January 2024}}</ref><ref>{{cite news |last=Sawer |first=Patrick |title=The unsung genius who secured Britain's computer defences and paved the way for safe online shopping |journal=The Telegraph |date=11 March 2016 |url=https://www.newindianexpress.com/world/2016/mar/12/the-anonymous-researcher-who-held-the-key-to-cyber-security-910751.html}}</ref> 

In 1973, his colleague [[Clifford Cocks]] implemented what has become known as the [[RSA (cryptosystem)|RSA encryption algorithm]], giving a practical method of "non-secret encryption", and in 1974 another GCHQ mathematician and cryptographer, [[Malcolm J. Williamson]], developed what is now known as [[Diffie–Hellman key exchange]]. 
The scheme was also passed to the US's [[National Security Agency]].<ref name="zdnet"/> Both organisations had a military focus and only limited computing power was available in any case;  the potential of public key cryptography remained unrealised by either organization:
<blockquote>
I judged it most important for military use ... if you can share your key rapidly and electronically, you have a major advantage over your opponent. Only at the end of the evolution from [[Tim Berners-Lee|Berners-Lee]] designing an open internet architecture for [[CERN]], its adaptation and adoption for the [[Arpanet]] ... did public key cryptography realise its full potential.

—[[Ralph Benjamin]]<ref name="zdnet">{{cite web |url=https://www.zdnet.com/article/gchq-pioneers-on-birth-of-public-key-crypto/ |title=GCHQ pioneers on birth of public key crypto |first=Tom |last=Espiner |date=26 October 2010 |website=[[ZDNet]]}}</ref>
</blockquote>
These discoveries were not publicly acknowledged for 27 years, until the research was declassified by the British government in 1997.<ref name=singh>{{cite book |last=Singh |first=Simon |author-link=Simon Singh |title=The Code Book |publisher=Doubleday |year=1999 |pages=[https://archive.org/details/codebookevolutio00sing/page/279 279]–292|title-link=The Code Book }}</ref>

=== Public discovery ===
In 1976, an asymmetric key cryptosystem was published by [[Whitfield Diffie]] and [[Martin Hellman]] who, influenced by [[Ralph Merkle]]'s work on public key distribution, disclosed a method of public key agreement. This method of key exchange, which uses [[Finite field#Applications|exponentiation in a finite field]], came to be known as [[Diffie–Hellman key exchange]].<ref name="Diffie 1976">{{cite journal |last1=Diffie |first1=Whitfield |author-link1=Whitfield Diffie |last2=Hellman |first2=Martin E. |author-link2=Martin Hellman |date=November 1976 |title=New Directions in Cryptography |url=http://ee.stanford.edu/%7Ehellman/publications/24.pdf |url-status=live |journal=[[IEEE Transactions on Information Theory]] |volume=22 |issue=6 |pages=644–654 |doi=10.1109/TIT.1976.1055638 |archive-url=https://web.archive.org/web/20141129035850/https://ee.stanford.edu/%7Ehellman/publications/24.pdf |archive-date=2014-11-29 |citeseerx=10.1.1.37.9720 }}</ref> This was the first published practical method for establishing a shared secret-key over an authenticated (but not confidential) communications channel without using a prior shared secret. Merkle's "public key-agreement technique" became known as [[Merkle's Puzzles]], and was invented in 1974 and only published in 1978. This makes asymmetric encryption a rather new field in cryptography although cryptography itself dates back more than 2,000 years.<ref>{{cite web |title=Asymmetric encryption |url=https://www.ionos.com/digitalguide/server/security/public-key-encryption/ |access-date=2022-06-09 |website=IONOS Digitalguide |language=en }}</ref>

In 1977, a generalization of Cocks's scheme was independently invented by [[Ron Rivest]], [[Adi Shamir]] and [[Leonard Adleman]], all then at [[MIT]]. The latter authors published their work in 1978 in [[Martin Gardner]]'s [[Scientific American]] column, and the algorithm came to be known as [[RSA (cryptosystem)|RSA]], from their initials.<ref name="rsa">
{{cite journal
 | last1 = Rivest | first1 = R.
 | last2 = Shamir | first2 = A.
 | last3 = Adleman | first3 = L.
 | url = http://people.csail.mit.edu/rivest/Rsapaper.pdf
 | title = A Method for Obtaining Digital Signatures and Public-Key Cryptosystems
 | journal = [[Communications of the ACM]]
 | volume = 21
 | issue = 2
 | pages = 120–126
 | date = February 1978
 | doi = 10.1145/359340.359342
 | citeseerx = 10.1.1.607.2677
 | s2cid = 2873616
 | access-date = 15 November 2019
 | archive-date = 17 December 2008
 | archive-url = https://web.archive.org/web/20081217101831/http://people.csail.mit.edu/rivest/Rsapaper.pdf
 | url-status = dead
}}</ref> RSA uses [[modular exponentiation|exponentiation modulo]] a product of two very large [[prime]]s, to encrypt and decrypt, performing both public key encryption and public key digital signatures. Its security is connected to the extreme difficulty of [[integer factorization|factoring large integers]], a problem for which there is no known efficient general technique. A description of the algorithm was published in the [[List of Martin Gardner Mathematical Games columns|Mathematical Games]] column in the August 1977 issue of [[Scientific American]].<ref>{{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>

Since the 1970s, a large number and variety of encryption, digital signature, key agreement, and other techniques have been developed, including the [[Rabin cryptosystem]], [[ElGamal encryption]], [[Digital Signature Algorithm|DSA]] and [[Elliptic-curve cryptography|ECC]].