and drank a good deal of Manischewitz wine before returning to their homes at around midnight. 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 the initials of their surnames in same order as their paper. Clifford Cocks, an English mathematician working for the British intelligence agency Government Communications Headquarters (GCHQ), described an equivalent system in an internal document in 1973. 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 discovery, however, was 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 simplified DES. Patent A patent describing the RSA algorithm was granted to MIT on 20 September 1983: "Cryptographic communications system and method". From DWPI's abstract of the patent: A detailed description of the algorithm was published in August 1977, in Scientific American's Mathematical Games column. This preceded the patent's filing date of December 1977. Consequently, the patent had no legal standing outside the United States. Had Cocks's work been publicly known, a patent in the United States would not have been legal either. When the patent was issued, terms of patent were 17 years. The patent was about to expire on 21 September 2000, but RSA Security released the algorithm to the public domain on 6 September 2000. Operation The RSA algorithm involves four steps: key generation, key distribution, encryption, and decryption. A basic principle behind RSA is the observation that it is practical to find three very large positive integers , , and , such that with modular exponentiation for all integers (with ): and that knowing and , or even , it can be extremely difficult to find . The triple bar (≡) here denotes modular congruence (which is to say that when you divide by and by , they both have the same remainder). In addition, for some operations it is convenient that the order of the two exponentiations can be changed and that