A method for obtaining digital signatures and public-key cryptosystems

By R. Rivest, Adi Shamir, L. Adleman. 1978

An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences: (1) Couriers or other secure means are not needed to transmit keys, since a message can be enciphered using an encryption key publicly revealed by the intented recipient. Only he can decipher the message, since only he knows the corresponding decryption key. (2) A message can be “signed” using a privately held decryption key. Anyone can verify this signature using the corresponding publicly revealed encryption key. Signatures cannot be forged, and a signer cannot later deny the validity of his signature. This has obvious applications in “electronic mail” and “electronic funds transfer” systems. A message is encrypted by representing it as a number M, raising M to a publicly specified power e, and then taking the remainder when the result is divided by the publicly specified product, n, of two large secret primer numbers p and q. Decryption is similar; only a different, secret, power d is used, where e * d ≡ 1(mod (p - 1) * (q - 1)). The security of the system rests in part on the difficulty of factoring the published divisor, n.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

A Comprehensive Comparison of Multiparty Secure Additions with Differential Privacy (2015, background): “However, a few partially homomorphic schemes are efﬁcient enough to achieve both security and performance goals, e.g., multiplicatively homomorphic ElGamal [25] and RSA [48] schemes.”
A Survey on Homomorphic Encryption Schemes (2017, methodology): “There are several useful PHE examples [Rivest et al. 1978b; Goldwasser and Mi-cali 1982; ElGamal 1985; Benaloh 1994; Naccache and Stern 1998; Okamoto and Uchiyama 1998; Paillier 1999; Damgård and Jurik 2001; Kawachi et al. 2007] in the literature.”
The BiBa one-time signature and broadcast authentication protocol (2001, methodology): “Periodically, the sender broadcasts a message containing the hash of all SEALs and the salt of one time period, signed with a traditional digital signature scheme, for example RSA [22].”
Secure and Efficient Asynchronous Broadcast Protocols (2001, methodology): “A practical scheme that satisfies these definitions in the random-oracle model was proposed by Shoup [42] and is based on RSA [40].”
BAR fault tolerance for cooperative services (2005, background): “We assume that a trusted authority controls which nodes may enter the system, that each such member has a unique identity corresponding to a cryptographic public key, that each member can determine whether a public key belongs to a specific member, and that no set of nodes has the computational powe”
Privacy Preserving Deep Computation Model on Cloud for Big Data Feature Learning (2016, methodology): “Homomorphic encryption was first introduced by Rivest, Adleman and Dertouzous shortly after the invention of RSA [36], [37].”
Threshold Ring Signatures and Applications to Ad-hoc Groups (2002, methodology): “Finally, we assume that each user Pi uses a regular signature scheme built on a trapdoor one-way permutation fi such as RSA [27] and that the modulus has length `b < `; typically, we choose `− `b ≥ 160.”
The Elliptic Curve Digital Signature Algorithm (ECDSA) (2001, unknown): “ANSI X Public Key Cryptography for the Financial Services Industry Elliptic Curve Key Agreement and Key Transport Protocols working draft August D Ash I Blake and S Vanstone Low complexity normal bases Discrete Applied Mathe matics R Balasubramanian and N Koblitz The improbability that an elliptic c”
Efficient authentication and signing of multicast streams over lossy channels (2000, methodology): “To bootstrap this scheme, the first packet needs to be authenticated with a regular digital signature scheme, for example RSA [27].”
Privacy-Preserving Machine Learning for Speech Processing (2012, methodology): “Even et al. [1985] proposed the construction for the above problem using RSA primitives [Rivest et al., 1978a], which proceeds as follows.”
A Decentralized Security Framework for Data Aggregation and Access Control in Smart Grids (2013, background): “different homomorphism, like multiplicative homomorphism (RSA [24]), additive homomorphism (Paillier [10], Boneh-Goh-Nissim [25]), or recently proposed fully homomor-”