Authors: R.L. Rivest, A. Shamir, and L. Adleman
An encryption (or decryption) procedure typically consists of a general method and an encryption key. The general method, under the control of the key, enciphers a message
Mto obtain the enciphered form of the message, called the ciphertext
C. Everyone can use the same general method; the security of a given procedure will rest on the security of the key.
Sfor the message
Musing his decryption key
S = DB(M). (Deciphering an unenciphered message: each message is the ciphertext for some other message.)
Susing Alice’s public encryption key
EA(for privacy), and sends the result
Mas well; it can be computed from
M = EB(S).
Mto a different version
M′, since then she would have to create the corresponding signature
S′ = DB(M′)as well.
M= Message to encrypt
n) = Pair of positive integers = the public encryption key.
Mas an integer between
n − 1. (Break a long message into a series of blocks, and represent each block as such an integer.)
C= Raise the numeric representation of the message to the
C ≡ E(M) ≡ Mᵉ (mod n), for a message
n − 1.
C, raise it to another power
n) = Pair of positive integers = the private decryption key.
D(C) ≡ Cᵈ (mod n), for a ciphertext
n = p · q; where:
qare private, “random” and very large primes.
n = p · q.
qhave 100 digits; hence
nwill have 200 digits.
3.8 × 10⁹years.
d= large, random integer which is relatively prime to
(p − 1) · (q − 1). That is, check that
gcd(d, (p − 1) · (q − 1)) = 1
eis finally computed from
dto be the “multiplicative inverse” of
(p−1)·(q−1). That is:
Although this problem of “computing
n” is not a well-known difficult problem like factoring, we feel reasonably confident that it is computationally intractable.
It may be possible to prove that any general method of breaking our scheme yields an efficient factoring algorithm. This would establish that any way of breaking our scheme must be as difficult as factoring. We have not been able to prove this conjecture, however.
Our method should be certified by having the above conjecture of intractability withstand a concerted attempt to disprove it.