The RSA cryptosystem, a cornerstone of modern secure communication, emerged from a period of intense cryptographic research in the 1970s. Its development was not a singular event but rather a culmination of ideas, challenges, and breakthroughs by several brilliant minds. The system's security is fundamentally linked to the mathematical difficulty of factoring the product of two very large prime numbers, a concept known as the "factoring problem."
While the RSA problem, which involves breaking the encryption, is related to this, whether it is equally difficult remains an open question. Nevertheless, with sufficiently large keys, there are no publicly known methods to defeat the system.
Early Concepts and Unsung Pioneers
The idea of an asymmetric public-private key cryptosystem, a foundational concept for RSA, is often attributed to Whitfield Diffie and Martin Hellman. They published this concept in 1976, introducing the notion of digital signatures and attempting to apply number theory to cryptography. Their formulation involved a shared-secret-key created through the exponentiation of a number, modulo a prime number. However, they left open the challenge of realizing a one-way function, possibly because the difficulty of factoring was not extensively studied at the time. Interestingly, an English mathematician named Clifford Cocks, working for the British intelligence agency Government Communications Headquarters (GCHQ), described a similar system in an internal document as early as 1973. Due to the high cost of computers needed to implement such a system at the time, it was largely considered a curiosity and, as far as is publicly known, was never deployed. Cocks's ideas remained classified as top-secret until 1997, long after RSA had become widely known.
The MIT Breakthrough: Rivest, Shamir, and Adleman
It was at the Massachusetts Institute of Technology (MIT) that Ron Rivest, Adi Shamir, and Leonard Adleman embarked on a year-long endeavor to create a function that was difficult to invert. Rivest and Shamir, both computer scientists, proposed numerous potential functions, while Adleman, a mathematician, was tasked with identifying their weaknesses. They explored various approaches, including those based on "knapsacks" and "permutation polynomials." For a period, they believed their goal was unattainable due to what seemed like contradictory requirements. The pivotal moment arrived in April 1977. After spending Passover at a student's house and consuming a considerable amount of wine, Rivest, unable to sleep, lay on a couch with a math textbook. He began contemplating their one-way function, spending the remainder of the night formalizing his idea. By daybreak, much of the paper outlining the algorithm was ready. This algorithm became known as RSA, an acronym formed from the initials of their surnames in the order they appeared on their paper.
Patenting and Public Release
A detailed description of the RSA algorithm was first published in August 1977 in Scientific American's Mathematical Games column. This publication predated the patent's filing date of December 1977. Consequently, the patent for RSA had no legal standing outside the United States. Had Cocks's earlier work been publicly known, a patent in the United States would not have been legal either. A patent describing the RSA algorithm was eventually granted to MIT on September 20, 1983, under U.S. patent 4,405,829, titled "Cryptographic communications system and method." The terms of the patent were 17 years. However, RSA Security, the company associated with the algorithm, released it to the public domain on September 6, 2000, shortly before its scheduled expiration on September 21, 2000. This move ensured the widespread and unencumbered use of the algorithm in various applications.
The Core Principle of RSA
The fundamental principle behind RSA lies in the observation that it is practical to find three very large positive integers: e, d, and n. These integers are chosen such that for any integer x (where 0 ≤ x < n), both (x^e)^d and x have the same remainder when divided by n; in mathematical terms, they are congruent modulo n: (x^e)^d ≡ x (mod n). The critical aspect is that while e and n are publicly known, it is computationally infeasible to compute e-th roots modulo n. This means that for a uniformly random y (where 0 ≤ y < n), it is extremely difficult to find x such that x^e ≡ y (mod n). This asymmetry between the ease of encryption and the difficulty of decryption without the private key forms the basis of RSA's security.
