A Method for Obtaining Digital Signatures and Public-Key Cryptosystems

How to read the original

1. Read Public-Key Cryptosystems to separate correctness, efficient evaluation, and the proposed difficulty of inversion.
2. Study Our Encryption and Decryption Methods and reconstruct the modular-inverse calculation.
3. Read the signature discussion historically, then distinguish raw textbook RSA from modern encoded encryption and signature schemes.

A public operation can have a secret inverse

Rivest, Shamir, and Adleman give a modular-exponentiation construction for public-key encryption and signatures. The mathematics establishes an inverse relationship when keys are chosen correctly. Security is a different claim involving hard problems, message encoding, and implementation. Factoring the modulus is sufficient to recover private-key information, but general RSA inversion should not be stated as proved equivalent to factoring without qualification.

Use an original toy key with primes p=11 and q=17. Their product is n=187, and phi(n)=(11-1)(17-1)=160. Choose public exponent e=7, which is coprime to 160. Its modular inverse is d=23 because 7*23=161=1+160. Publish (n,e) and retain the private exponent and factorization appropriately.

Trace one message through the permutation

Represent a message as an integer m with 0<=m<n. For m=42, encryption computes c=42^7 mod 187=15. Decryption computes 15^23 mod 187=42. Repeated squaring evaluates these expressions with intermediate reductions, avoiding an enormous unreduced power. The public exponent permits encryption by anyone who has the verified public key; it does not establish that the key belongs to the claimed recipient.

Why does decryption work? Since ed=1+k*(p-1)*(q-1), consider the result modulo each prime. If m is zero modulo p, then m^(ed) and m are both zero modulo p. Otherwise Fermat’s theorem makes the extra exponent factor contribute one. The same argument holds modulo q. The Chinese remainder theorem then gives equality modulo pq. This handles messages sharing a factor with n, unlike a careless application of Euler’s theorem that assumes coprimality without checking it.

Correctness is not semantic security

Raw RSA encryption is deterministic. Encrypting the same integer under the same public key produces the same ciphertext. If the message comes from a tiny known set, an observer can encrypt every candidate and compare, without factoring n. Making n larger does not remove that structural problem.

The raw map is also multiplicative: E(m1)E(m2) modulo n equals E(m1m2 modulo n). This algebra is useful for understanding the construction but creates malleability when an application expects ciphertext modification to be detected. A system must not interpret the bare exponentiation formula as an authenticated message format.

Modern RSA encryption and signature schemes use carefully specified encodings with different security goals. Encryption padding and signature encoding are not interchangeable. A signature normally binds a structured representation or digest of a message under a defined scheme; describing it only as “encrypting with the private key” hides the required format, hashing assumptions, and verification checks.

State the surrounding trust and implementation model

Key generation needs strong randomness and suitable primes. Decryption and signing must address side channels and faults. A certificate or other trusted mechanism must associate a public key with an identity. Revocation, key storage, and application-level replay protection remain separate concerns. None is proved by the small-number example.

For learning, keep three deliverables distinct: an arithmetic trace showing inversion, a proof covering the permitted message domain, and a critique of the bare construction’s security. The historical paper made a powerful concrete proposal, but a present-day implementation should use established cryptographic schemes and maintained libraries. The toy values here are intentionally factorable and suitable only for understanding the mechanism.

Reconstruction exercise

Using n=187, e=7, and d=23, verify decryption for both m=42 and m=11. Explain why the second message requires care in a proof invoking Euler’s theorem. Then suppose the only possible plaintexts are the integers zero and one. Show how an observer distinguishes them under raw RSA without learning d. Finally derive the multiplicative relation E(2)*E(m) mod n=E(2m mod n), and explain why correct decryption alone does not guarantee ciphertext integrity.

Worked solution

For m=42, encryption gives 15 and decryption gives 42. For m=11, encryption gives 88 and decrypting 88 returns 11. The latter message is not coprime to 187, so Euler’s theorem cannot be applied to it directly using the usual coprime premise. Proving equality separately modulo 11 and 17 handles both zero and nonzero residues, then the Chinese remainder theorem combines them. Raw RSA maps zero to zero and one to one, so an observer distinguishes that two-message set immediately. More generally, multiplication of public encryptions gives 2^e*m^e=(2m)^e modulo n. An altered ciphertext can therefore correspond predictably to a different plaintext without the attacker factoring n. Inversion correctness says legitimate encodings can be recovered; it does not establish confidentiality for low-entropy messages or detection of malicious changes. Appropriate schemes add distinct protections around the raw arithmetic.

Test the limits and transfer the idea

1. Number theory and trace · allow 45 minutes

Prove inversion for a message divisible by a prime

Construct an original toy RSA key with p=7, q=11, n=77, and public exponent e=13. Find a private exponent d using the extended Euclidean algorithm modulo phi(n). Encrypt and decrypt m=7 using repeated squaring. Then prove m^(ed)=m modulo n for every 0<=m<77, explicitly handling messages divisible by 7 or 11.

Explain why applying Euler's theorem directly to every message is an incomplete proof. State which part of your work is an algebraic correctness result and which security claims it leaves unanswered. These parameters are for arithmetic education only.

Get a starting hint

13×37=481 is one more than a multiple of 60. Prove congruence separately modulo each prime.

Compare your reasoning with the worked solution

Here phi(77)=6×10=60. Euclid gives 60=4×13+8, 13=8+5, 8=5+3, 5=3+2, and 3=2+1. Back-substitution yields 1=5×60-23×13, so d=-23 modulo 60, or 37. The product ed=481=1+8×60.

For encryption, 7²=49 modulo 77, 7⁴=14, and 7⁸=42. Since 13=8+4+1, the ciphertext is 42×14×7 modulo 77=35. For decryption, 35²=70, 35⁴=49, 35⁸=14, 35¹⁶=42, and 35³²=70 modulo 77. Since 37=32+4+1, 70×49×35 modulo 77=7.

For any message m, if 7 divides m, both m and m^481 are zero modulo 7. Otherwise Fermat gives m⁶=1 modulo 7, and 480 is a multiple of 6, so m^481=m. Apply the same two cases modulo 11, using exponent 10. The Chinese remainder theorem then gives equality modulo 77 because 7 and 11 are coprime. Euler's usual premise gcd(m,77)=1 fails for m=7, so using it without a separate argument omits permitted messages.

This proves the exponentiation maps invert each other on the specified residue domain. It does not prove message confidentiality, secure padding, correct identity binding, or resistance to side channels. Factoring 77 is trivial, and raw RSA remains deterministic and malleable even with larger keys.

Check your reasoning

• Derives d and verifies the repeated-squaring residues.
• Covers zero and nonzero residues modulo both primes before applying CRT.
• Separates inversion correctness from cryptographic scheme security.

2. Counterexample and threat model · allow 40 minutes

Forge an unstructured textbook signature

Use the reading's toy public key n=187,e=7. A deliberately incomplete verifier accepts any integer message m with a purported signature s when s^7 modulo 187 equals m. It applies no hash, structure, domain label, or encoding. An adversary is allowed to choose the message after choosing the signature.

Choose s=2 and construct an accepted pair without the private key. Explain why this is an existential forgery but does not let the adversary sign an arbitrary message chosen in advance. Next prove that multiplying valid raw signatures yields a signature for the product of their raw messages modulo n. Identify the additional scheme-level requirements hidden by the slogan 'a signature is private-key encryption'. Do not implement or recommend this verifier for use.

Get a starting hint

The verifier's public arithmetic can define a message as well as test one. Be precise about who chooses the target message and when.

Compare your reasoning with the worked solution

Choose s=2 and compute m=2⁷ modulo 187=128. The pair (128,2) passes the verifier by construction. The adversary used only public arithmetic. This is an existential forgery for the stated message space: it produces some new accepted message/signature pair. It is not a method for signing an independently specified target such as m=42, because the attacker chose 128 to fit the chosen signature.

If valid pairs satisfy s1^e=m1 and s2^e=m2 modulo n, then (s1s2)^e=s1^e s2^e=m1m2 modulo n. Reducing the signature product and message product modulo n therefore produces another accepted raw pair. For a numerical illustration, choose s1=2 and s2=3. Their messages are 128 and 130 modulo 187. The product signature is 6 and the product message is 128×130 modulo 187=184; indeed 6⁷ modulo 187=184. No private exponent is needed to verify these relationships.

A real signature scheme defines which messages are represented, how hashing and encoding bind them, how verification rejects malformed encodings, and what unforgeability game is intended. Identity binding and key management remain additional obligations. These mathematical attacks target the deliberately unstructured map, not correctly implemented modern RSA signature schemes. The historical construction explains the public/private inverse relationship, while its bare permutation is not itself a complete modern signature format.

Check your reasoning

• Constructs (128,2) and states the chosen-message-order limitation.
• Proves multiplicativity and checks the numerical product pair.
• Explains why encoding and a security definition are essential.

Check your understanding

Why is a modulo-p and modulo-q proof useful for RSA correctness?

• It avoids assuming every permitted message is coprime to n.
• It proves factoring is easy.
• It removes the need for an inverse exponent.

Explanation

Messages divisible by one prime still require correct decryption, and the separate prime cases handle them.

Why is raw RSA unsafe for a known two-message plaintext set even with a large modulus?

• A large modulus cannot represent two messages.
• Its deterministic public encryption lets an observer encrypt and compare candidates.
• The private key is always transmitted with the ciphertext.

Explanation

Candidate testing exploits determinism and the small message space rather than factoring.

Original paper and sources

Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM 21(2), February 1978, pp. 120-126. Linked resource is an author-hosted reprint.

Read the original paper →

Read the primary paper: MIT CSAIL

• A Method for Obtaining Digital Signatures and Public-Key Cryptosystems: MIT CSAIL