Cryptography Reference
In-Depth Information
than without being given the ciphertext). It has been shown that the notion of non-
malleability is equivalent to the notion of semantic security against adaptive chosen-
ciphertext attacks [4]. This means that an asymmetric encryption system that is non-
malleable is also semantically secure against adaptive chosen-ciphertext attacks, and
vice versa. Consequently, the two notions of security are often used synonymously
and interchangeably in the literature. For the purpose of this topic, however, we use
the term semantic security against adaptive chosen-ciphertext attacks most of the
times.
14.2
BASIC SYSTEMS
A couple of asymmetric encryption systems were developed and proposed in the late
1970s and early 1980s (when public key cryptography was discovered and started
to take off). We overview and briefly discuss the RSA, Rabin, and ElGamal asym-
metric encryption systems. For all of these systems, we address the key generation,
encryption, and decryption algorithms, and we provide a brief security analysis.
For the sake of simplicity, we assume that public keys are always published
in certified form (we discuss the implications of this assumption at the end of this
chapter and in Section 19.5).
14.2.1
RSA
The RSA public key cryptosystem was jointly invented by Ronald L. Rivest, Adi
Shamir, and Leonard M. Adleman at MIT in 1977. A U.S. patent application
was filed on December 14, 1977, and a corresponding article was published in
the Communications of the ACM in February 1978 [5]. 2 On September 20, 1983,
the U.S. patent 4,405,829 entitled “Cryptographic Communications System and
Method” was assigned to MIT. It was one of the most important patents ever
granted for an invention related to cryptography. 3 After 17 years, the patent expired
in September 2000. Recognizing the relevance of their work, Rivest, Shamir, and
Adleman were granted the prestigious ACM Turing Award in 2002.
2
The RSA public key cryptosystem was first described in Martin Gardner's column in the August
1977 issue of the Scientific American . In this article, a 129-digit (i.e., 426-bit) number was
introduced to illustrate the computational intractability of the IFP, and the security of the RSA public
key cryptosystem accordingly. This number was referred to as RSA-129. In 1991, RSA Security,
Inc., used it to launch an RSA Factoring Challenge. RSA-129 was successfully factored in March
1994 (see Section 7.3).
3
Note that the RSA patent was a U.S. patent, and that the RSA public key cryptosystem was not
patented outside the U.S.
Search WWH ::




Custom Search