Asymmetric Cryptography: From RSA to Elliptic Curves

Basic idea. Alice and Bob can arrive at the same mathematical secret even though they exchange their public values across an insecure network. An eavesdropper sees the public parameters and exchanged values, but cannot feasibly calculate the secret when the group is appropriately selected and the private exponents remain unknown.

1. Agree on a large prime modulus p and a generator g of a suitable subgroup.
2. Alice chooses a private exponent a and publishes A = g^a mod p. Bob chooses b and publishes B = g^b mod p.
3. Alice computes B^a mod p, while Bob computes A^b mod p. Both obtain g^(ab) mod p.
4. Feed the shared result and the relevant protocol context into a KDF. Use the resulting keys with authenticated symmetric encryption.

Worked example. Choose p = 23, g = 5, Alice's a = 6 and Bob's b = 15. Alice sends A = 8, and Bob sends B = 19. Both calculate K = 2. These values are trivial to attack, but reveal the symmetry of the mathematics. Try the interactive DH lab.

Further reading: NIST SP 800-56A Rev. 3.

Basic idea. RSA constructs a large composite modulus from secret prime factors. The public exponent lets anyone apply the public-key transformation, while a corresponding private exponent reverses it. The same underlying number-theory primitive can support encryption or signatures, but safe applications require distinct schemes and encodings.

1. Generate two unpredictable, sufficiently large, distinct primes p and q. Compute n = p*q and λ(n) = lcm(p-1, q-1).
2. Choose public exponent e relatively prime to λ(n) (commonly 65537). Compute private exponent d = e^(-1) mod λ(n).
3. Publish (n,e). Protect d, the primes and CRT parameters. For encryption, first use a secure randomized encoding such as RSA-OAEP.
4. Perform the RSA exponentiation on the encoded message. The receiver uses the private exponent (often accelerated using the CRT) and checks/decodes the result.

Worked example. Choose p=61, q=53, n=3233, e=17 and d=2753 (computed using φ(n)=3120; this also satisfies the needed inverse relation). Then m=65 transforms to c=2790, and private-key exponentiation recovers 65. Experiment with the RSA-family lab.

Two different safe uses. RSAES-OAEP specifies encryption with randomized encoding. RSASSA-PSS specifies probabilistic signatures over a hashed message. Simply "encrypting with the private key" is not an accurate description of a secure digital-signature protocol.

References: RFC 8017 (PKCS #1); FIPS 186-5; NIST SP 800-56B Rev. 2.

Basic idea. Ordinary RSA commonly chooses n=p*q. Multi-prime RSA chooses n=p_1*p_2*...*p_t for t >= 3. Each prime factor is smaller than it would be in a conventional two-prime modulus of the same bit length. Consequently, private-key operations can be split into more, smaller modular exponentiations and recombined using the Chinese Remainder Theorem.

1. Choose t distinct large secret primes; calculate their product n.
2. Compute λ(n)=lcm(p_1-1, ..., p_t-1) and choose an exponent e invertible modulo λ(n).
3. Compute d=e^(-1) mod λ(n), and retain the separate CRT exponents d_i=d mod (p_i-1).
4. For private-key operations, calculate m_i=c^(d_i) mod p_i in each small modulus, and combine the residues with CRT.

Worked example. Using p_1=11, p_2=13, p_3=17 yields n=2431. With e=17, the teaching example uses φ(n)=1920 and d=113. Each private calculation can be done separately modulo 11, 13 and 17 before recombination. Select "Multi-prime RSA" in the lab.

Primary specification: RFC 8017, sections 3.1-3.2 and Appendix A.1.2.

Basic idea. Unlike multi-prime RSA, which multiplies distinct primes, a multi-power construction uses at least one prime power. The commonly discussed shape is n=p^k*q, with k >= 2 and distinct secret primes p and q. The public transformation still resembles RSA exponentiation, but the private reconstruction must account for a residue modulo p^k.

1. Select secret primes p and q and a small integer k >= 2. Compute n = p^k * q.
2. For the unit group, calculate φ(n) = p^(k-1)*(p-1)*(q-1) or λ(n) = lcm(p^(k-1)*(p-1), q-1) for odd primes.
3. Choose e coprime to the relevant group exponent and find an inverse d. Use a valid randomized encryption encoding that produces an acceptable group element.
4. Recover the plaintext residues modulo p^k and q and combine them with CRT. Special algorithms can accelerate the first residue calculation.

Worked example. Let p=11, q=17 and k=2. Then n=11^2*17=2057 and φ(n)=1760. For e=17, d=1553 is an inverse modulo 1760. With m=42, the ciphertext is c=1742, and private exponentiation recovers 42. Test the p-squared RSA mode.

Related research: Takagi, CRYPTO 1998; Takagi, IEICE 2004.

Basic idea. The Takagi cryptosystem is a specific way of implementing the prime-power RSA idea. Its important innovation is a fast private-key operation when n=p^k*q. Rather than performing an unnecessarily large exponentiation modulo p^k, the decryptor first finds a root modulo the small prime p, then lifts that root to modulo p^2, and so forth.

1. Generate n=p^k*q and select an appropriate public exponent e, with the scheme's domain and invertibility conditions satisfied.
2. Encrypt a permissible message with the RSA-like map c=m^e mod n (a real secure scheme also requires appropriate encoding).
3. Find m_p, the e-th root of c modulo p; compute the residue modulo q separately.
4. Apply Hensel lifting successively, producing the corresponding root modulo p^2, p^3, ... p^k.
5. Use the CRT to combine the residues modulo p^k and q into the unique message modulo n.

Worked example. For n=11^2*17=2057, e=17, and m=42, ciphertext is 1742. The root modulo 11 is 9. Lifting gives 9+3*11=42 modulo 121. The root modulo 17 is 8. CRT combines 42 mod 121 with 8 mod 17, producing 42. The Takagi laboratory shows the actual lift.

Original research: Takagi, CRYPTO 1998 and Takagi, IEICE 2004.

Basic idea. Rabin encryption is remarkably simple: square the plaintext modulo a composite number. Its special theoretical feature is that extracting modular square roots for random inputs is closely connected to factoring the modulus. Its main practical complication is that decrypting a typical ciphertext yields four possible plaintext values, not automatically one.

1. Choose two secret, distinct Blum primes p and q, each satisfying p mod 4 = 3 and q mod 4 = 3. Publish n = p*q.
2. Represent the plaintext as a suitable integer m, typically relatively prime to n, and compute c=m^2 mod n.
3. Use secret p and q to find the two roots of c modulo each prime. For Blum primes, a square root can be found with c^((p+1)/4) mod p and similarly for q.
4. Combine the two independent sign choices using CRT. This usually produces four roots modulo n; the message encoding or protocol must disambiguate them.

Worked example. Let p=7, q=11, n=77, and m=13. Encryption gives c=15. The four square roots of 15 modulo 77 are 13, 20, 57 and 64. All four square to 15 modulo 77, so pure squaring does not identify the intended message. Run the Rabin root calculator.

Background: Handbook of Applied Cryptography, Chapter 8.

Basic idea. ElGamal turns the Diffie-Hellman idea into public-key encryption. The sender creates a temporary (ephemeral) exponent that generates a shared masking value using the recipient's public key. The message is multiplied by that mask. The recipient's secret exponent reconstructs the mask and removes it.

1. Choose a suitable cyclic group, such as a subgroup of the nonzero integers modulo a large prime p, with generator g. The recipient chooses private key x and public key y=g^x mod p.
2. The sender chooses a fresh random exponent k for each encryption.
3. Compute c_1=g^k mod p and c_2=m*y^k mod p. Transmit the ciphertext pair (c_1,c_2).
4. The recipient calculates s=c_1^x mod p and recovers m=c_2*s^(-1) mod p.

ElGamal is probabilistic: the same message encrypted twice with new values of k normally produces different ciphertexts. This addresses an important weakness of deterministic textbook RSA, but ElGamal's textbook form remains malleable. Try the ElGamal calculator.

Further reading: Handbook of Applied Cryptography, Chapter 8.

Basic idea. Paillier is a randomized encryption scheme with a special property: multiplying two ciphertexts produces an encryption of the sum of their underlying plaintexts. This is called additive homomorphism. It allows, for example, a trusted party holding the private key to decrypt an aggregate of encrypted votes or measurements without decrypting each input separately.

1. Generate secret primes p and q such that the required key-generation conditions hold. Compute n=p*q, λ=lcm(p-1,q-1) and work modulo n^2.
2. In a common simplified variant, set g=n+1 and compute μ=λ^(-1) mod n where the inverse exists. Publish (n,g) and keep (λ,μ) private.
3. Encode m as an integer from 0 to n-1, choose a fresh random r coprime to n and compute c=g^m*r^n mod n^2.
4. Decrypt using m=L(c^λ mod n^2)*μ mod n, where L(u)=(u-1)/n for values congruent to 1 modulo n.

Worked example. With p=7, q=11, n=77, λ=30, g=78 and μ=18, encrypting 9 with r=2 yields 4407; encrypting 4 with r=3 yields 2539. Multiplying the ciphertexts modulo 77^2 decrypts to 13, the sum of the messages. Run the Paillier homomorphism lab.

Original scheme: Paillier, EUROCRYPT 1999.

Basic idea. Benaloh generalizes earlier probabilistic bit-encryption ideas so that one ciphertext can encode an integer from 0 through r-1, for a chosen message modulus r. Like Paillier, it supports encrypted addition. Its performance and correctness depend sensitively on the selection of r, the secret primes and a public element y.

1. Choose an odd integer message modulus r and secret primes p,q such that r divides p-1, gcd(r,(p-1)/r)=1 and gcd(r,q-1)=1.
2. Compute n=p*q and choose a unit y mod n. Check the corrected generator condition: for every prime factor s of r, y^((p-1)/s) != 1 mod p.
3. Publish (n,r,y). Encrypt m in {0,...,r-1} with a new random unit u: c=y^m*u^r mod n.
4. To decrypt, raise c to (p-1)/r modulo p, eliminating the randomizer. Recover m by finding the exponent of the corresponding base in a subgroup of order r.

Worked example. Take r=5, p=11, q=7, n=77 and y=2. With m=2 and u=3, c=2^2*3^5 mod 77=48. Decryption uses 48^2 mod 11=5 and the fact that (2^2)^2 mod 11=5, recovering m=2. Try the Benaloh lab.

Key-generation correction: Fousse, Lafourcade and Alnuaimi, 2011.

Basic idea. Ordinary Diffie-Hellman does not tell Alice whether the other party is really Bob. SPEKE belongs to the family of password-authenticated key exchange (PAKE) protocols: parties who share a low-entropy password derive a cryptographic group generator from that password, and then perform a Diffie-Hellman-like exchange. Correctly designed PAKEs aim to prevent an eavesdropper from testing large numbers of password guesses against a captured exchange without interacting with a party.

1. Alice and Bob begin with the same password and agreed group parameters. A protocol-specified transformation maps the password to a valid generator g_pw of the intended subgroup.
2. Alice chooses a fresh private exponent a and sends A=g_pw^a mod p. Bob chooses b and sends B=g_pw^b mod p.
3. Both derive the same Diffie-Hellman group element g_pw^(ab) mod p when their passwords and group operations agree.
4. A secure protocol applies a specified KDF and performs authenticated key confirmation tied to identities, session roles and the communication transcript.

Intuition. If Alice and Bob type the same password, they begin from a consistent group base and can derive a matching secret. However, that observation alone is not a security proof. The password-to-group mapping, subgroup checks, protocol transcript and key-confirmation logic are essential parts of real SPEKE.

Original paper: Jablon, 1996; security analysis: Hao et al., 2018; comparison: RFC 9382 and RFC 9383.

Basic idea. MQV improves on unauthenticated Diffie-Hellman by combining each participant's long-term (static) key pair with a new ephemeral key pair. The goal is that both endpoints derive a session key while binding the exchange to the intended parties' identities and long-term keys. It exists in finite-field and elliptic-curve forms.

1. Alice and Bob each maintain a static private/public key pair associated with an authenticated identity.
2. For each session, each party creates a fresh ephemeral key pair and exchanges the ephemeral public key.
3. The protocol mixes static private-key material and ephemeral private-key material using specified functions of the exchanged public shares.
4. The parties compute a common group element and derive session keys with appropriate KDF/context binding and, where required, explicit key confirmation.

Why this differs from ordinary ECDH. If two strangers perform bare ECDH, they can establish a common secret but have no assurance who is at the other end of the channel. MQV integrates long-term authenticated keys into the mathematical agreement itself. HMQV uses hashing in the coefficient derivation and has its own security analysis and implementation requirements.

Normative background: NIST SP 800-56A Rev. 3.

Basic idea. ECC replaces integer exponentiation modulo a prime with a different hard mathematical problem: recovering a scalar from an elliptic-curve point multiplication. A curve defines a set of points with a special addition rule. Repeatedly adding a base point to itself is efficient; reversing that calculation for properly selected large groups is difficult.

1. Select a standardized curve and a base point G of large prime order q.
2. Select private scalar d from the allowed range and compute public point Q=d*G.
3. To add two distinct points P=(x1,y1) and Q=(x2,y2), calculate a slope using modular division and then derive a new point R=P+Q.
4. Use point multiplication in a complete protocol, such as ECDH for keys or ECDSA for signatures.

A small educational curve. Consider y^2=x^3+2x+2 mod 17 with base point G=(5,1), which has order 19. Doubling produces 2G=(6,3); five copies produce 5G=(9,16). Actual ECC standards use vastly larger fields and carefully evaluated groups. Explore the point-multiplication lab.

Standards: NIST SP 800-186; SP 800-56A Rev. 3; RFC 7748.

Basic idea. ECDH is the elliptic-curve counterpart of ordinary Diffie-Hellman. Instead of exchanging powers of a generator, the two parties exchange scalar multiples of a common point. An eavesdropper can see both public points but should not be able to determine the shared result.

1. Alice chooses private scalar a and computes A=aG. Bob chooses b and computes B=bG.
2. They exchange public points A and B, according to the curve's encoding and validation requirements.
3. Alice computes aB; Bob computes bA. Both obtain (ab)G.
4. A KDF converts the resulting shared material into keys, binding identities, algorithm choices and transcript information where required.

X25519 is a standardized function for performing Diffie-Hellman with Curve25519, specified by RFC 7748. X448 supplies a higher-strength counterpart on Curve448. X25519 produces a shared secret from a local scalar and the peer's public input; the application still needs authentication and key derivation. RFC 7748 also discusses rejecting or aborting on an all-zero shared result.

Specification: RFC 7748; key-establishment background: NIST SP 800-56A Rev. 3.

Basic idea. ECDSA lets an owner of an elliptic-curve private key sign a message. A recipient verifies the signature using only the public key, a hash of the message and the group operations. The signature provides evidence of origin and integrity; it does not encrypt or conceal the underlying message.

1. Generate a private scalar d and public point Q=dG, where the generator has order q.
2. Hash the message to an appropriately processed integer z and obtain a unique, secret per-signature scalar k.
3. Calculate R=kG, let r=x(R) mod q, and compute s=k^(-1)*(z+r*d) mod q. Retry under the scheme's rules if a required value is zero.
4. The verifier processes (r,s) with the public key and checks that a derived point's x-coordinate matches r under the standard's rules.

Security-critical rule. Reusing k on two different messages or leaking part of it can reveal the private key. Deterministic nonce-generation techniques (such as RFC 6979 for certain ECDSA profiles) reduce dependence on fresh randomness at signing time but still require a secure implementation.

Standards: FIPS 186-5; NIST SP 800-186.

Basic idea. EdDSA is a family of signature schemes built on Edwards-type elliptic curves. Ed25519 is a widely used instantiation; Ed448 is another. Their formulas are designed for efficient, robust implementations and conventionally derive a per-message nonce deterministically from private-key-derived secret material and the message.

1. Create a secret seed and derive an appropriately clamped secret scalar and additional nonce-derivation material. Compute the public point from the base point.
2. Hash the secret prefix and message to obtain a deterministic nonce scalar; compute the corresponding curve point R.
3. Hash R, the public key and the message to obtain a challenge scalar.
4. Combine the nonce and private scalar into a signature value S. Verify a corresponding elliptic-curve group equation using the public key.

Ed25519 versus X25519. The names resemble each other because the associated curves are mathematically related, but Ed25519 is a digital-signature algorithm and X25519 is a key-agreement function. They are not interchangeable. Do not assume keys can be reused across those roles without a carefully specified design.

Specifications: RFC 8032; FIPS 186-5.

Basic idea. ECC itself does not define a universal message-encryption algorithm. ECIES addresses that gap by using an elliptic-curve shared secret to derive symmetric keys, then using symmetric cryptography to encrypt the message. Different ECIES profiles specify different curve choices, KDFs, message formats and authentication methods.

1. The recipient publishes an authenticated ECC public key Q=dG.
2. The sender selects an ephemeral private scalar k and sends the corresponding public point R=kG.
3. The sender computes Z=kQ, while the recipient can later compute the same value as dR.
4. Apply an approved KDF with required context and derive keys for an authenticated symmetric encryption algorithm; transmit the ephemeral public key, ciphertext and authentication tag.
5. The recipient derives matching keys, verifies the authentication tag and only then accepts the plaintext.

ECIES illustrates a major practical pattern in cryptography: asymmetric mathematics establishes a secret, while a fast authenticated cipher protects the message itself. A receiver must know the exact algorithm profile and correctly parse, validate and authenticate all relevant fields.

Related key-establishment framework: NIST SP 800-56A Rev. 3.

Basic idea. Cramer-Shoup was designed to address an important weakness of basic ElGamal: an active attacker may modify ciphertexts and ask a decryption service how they behave. The Cramer-Shoup scheme augments an ElGamal-like construction with extra public-key components and a cryptographic hash-based consistency check.

1. Generate a suitable group and several related public-key elements derived from a collection of secret exponents.
2. Choose a fresh random exponent and compute public ciphertext components such as u1=g1^r and u2=g2^r.
3. Mask the message using another group element and compute a hash challenge from ciphertext components.
4. Construct an authentication-related group component using the challenge; append it to the ciphertext.
5. Before returning a plaintext, the decryptor verifies the ciphertext consistency equation. Invalid ciphertexts are rejected.

The resulting construction provided a foundational example of public-key encryption proved secure against adaptive chosen-ciphertext attacks (IND-CCA2) under conventional assumptions for an appropriate group and hash construction. It helped bridge a gap between abstract security definitions and practical algebraic cryptosystems.

Original paper: Cramer and Shoup, CRYPTO 1998.

Basic idea. Goldwasser-Micali is a historically pivotal probabilistic public-key encryption construction. It encrypts a single bit by hiding a mathematical property: whether a chosen number is a quadratic residue modulo a composite number. Its importance lies in showing how encryption can be formally defined to conceal information about a message.

1. Generate large secret primes p and q, compute n=p*q, and select a public element x that is a quadratic nonresidue modulo both primes while having Jacobi symbol +1 modulo n.
2. To encrypt a bit b, choose a random unit r modulo n and compute c=r^2*x^b mod n.
3. The recipient uses the secret factors to determine whether the result is a quadratic residue modulo a secret prime, thereby recovering b.
4. Encrypt a longer message by encrypting each bit separately, which is why the original construction has substantial ciphertext expansion.

Multiplying Goldwasser-Micali ciphertexts produces an encryption of the XOR (addition modulo 2) of their bits. It is therefore a simple example of a homomorphic property, though its ciphertext expansion makes it inefficient for general-purpose encryption.

Original work: Goldwasser and Micali, STOC 1982 and JCSS 1984.