Asymmetric Encryption and Key Exchange Questions

Approach

Generate two large primes $p, q$ of roughly half the target bit length each using a cryptographically secure random source and Miller-Rabin primality testing (a PROBABILISTIC primality test, run enough rounds that the probability of falsely accepting a composite number is negligible), pick a fixed public exponent $e$ (65537 is standard, chosen because it is prime, has a small Hamming weight for fast public-exponent operations, and is large enough to avoid small-exponent attacks), verify $\gcd(e, \phi(n)) = 1$ so $e$ has a modular inverse, compute the private exponent $d = e^{-1} \bmod \phi(n)$, and validate that the resulting modulus $n = pq$ actually has the requested bit length before returning the key.

"""RSA key generation with Miller-Rabin primality testing (seeded RNG for reproducibility;
production code must use a CSPRNG such as `secrets`, never a seeded PRNG)."""
import math
import random


def is_probable_prime(n, rng, rounds=20):
    if n < 4:
        return n in (2, 3)
    if n % 2 == 0:
        return False
    d, s = n - 1, 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for _ in range(rounds):
        a = rng.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = (x * x) % n
            if x == n - 1:
                break
        else:
            return False
    return True


def gen_prime(bits, rng):
    while True:
        candidate = rng.getrandbits(bits) | (1 << (bits - 1)) | 1
        if is_probable_prime(candidate, rng):
            return candidate


def gen_rsa_keypair(bits, seed):
    rng = random.Random(seed)
    e = 65537
    while True:
        p = gen_prime(bits // 2, rng)
        q = gen_prime(bits - bits // 2, rng)
        if p == q:
            continue
        n = p * q
        phi = (p - 1) * (q - 1)
        if math.gcd(e, phi) != 1:
            continue
        d = pow(e, -1, phi)
        if n.bit_length() == bits:
            return {"n": n, "e": e, "d": d, "p": p, "q": q}


if __name__ == "__main__":
    key = gen_rsa_keypair(bits=32, seed=20260901)
    print(f"generated 32-bit toy key: p={key['p']} q={key['q']}")
    print(f"n={key['n']} (bit_length={key['n'].bit_length()})  e={key['e']}  d={key['d']}")

    m = 424242
    c = pow(m, key["e"], key["n"])
    m_back = pow(c, key["d"], key["n"])
    print(f"round trip: m={m} -> c={c} -> decrypt(c)={m_back}  (matches original: {m_back == m})")

Output:

generated 32-bit toy key: p=37699 q=61031
n=2300807669 (bit_length=32)  e=65537  d=1228481753
round trip: m=424242 -> c=411332014 -> decrypt(c)=424242  (matches original: True)

Key points

• Miller-Rabin writes $n - 1 = d \cdot 2^s$ and repeatedly tests random witnesses; each round that PASSES halves the probability of a false positive, so 20+ rounds (as used here) drives the error probability low enough to be cryptographically negligible, this test can prove COMPOSITENESS with certainty on a single failing witness, but can only make PROBABILISTIC claims of primality.
• The demo above uses random.Random(seed), a SEEDED, non-cryptographic pseudo-random generator, purely so this specific worked example is reproducible; real key generation MUST use a cryptographically secure source (Python's secrets module, or the operating system's CSPRNG, cryptographically secure pseudo-random number generator, directly), since a predictable seed for prime generation is a direct path to full private-key recovery.
• Checking $\gcd(e, \phi(n)) \neq 1$ and re-drawing $p, q$ rather than adjusting $e$ keeps $e$ fixed at the standard, widely-interoperable 65537 across every generated key, some other implementations instead vary $e$, but a fixed, small, standard exponent is the common convention.
• The round-trip check (encrypt then decrypt back to the original message) in the worked example is a cheap, direct sanity check that $e$, $d$, and $n$ are mutually consistent, independent of trusting the arithmetic that derived them.

Complexity

Generating each candidate prime costs one Miller-Rabin test per candidate (dominated by modular exponentiation, $O(b^3)$-ish for a $b$-bit candidate using schoolbook modular exponentiation, better with fast multiplication), and by the prime number theorem roughly one in every $\ln(2^b) \approx 0.69b$ random $b$-bit odd candidates is prime, so expected work per prime is $O(b)$ candidates times the cost of one primality test. Computing $d = e^{-1} \bmod \phi(n)$ via the extended Euclidean algorithm is $O(b^2)$ and negligible next to prime generation, which dominates total keygen time.

Edge cases

• $p = q$. Explicitly checked and rejected (re-draw both), since $n = p^2$ would make $n$ trivially factorable by taking a square root, catastrophic for security.
• $d$ turning out too small. This implementation does NOT check the resulting $d$'s bit length anywhere, only n.bit_length() == bits is checked, that is a real gap, not a rounding error in this explanation. An unusually small private exponent is recoverable by dedicated small-private-exponent attacks (Wiener's continued-fraction attack and its lattice-based extensions, a separate concern from small PUBLIC exponent attacks). A production implementation should add an explicit lower-bound check on $d$ right after computing it and re-draw $p, q$ (which forces a fresh $d$) if the check fails, that re-draw is a cheap defense once the check actually exists in the code.
• Resulting $n$ not landing at the exact requested bit length. Multiplying two $b/2$-bit primes does not automatically guarantee an $n$ of exactly $b$ bits (it can land one bit short if both primes' leading bits happen to multiply below the boundary); the implementation checks n.bit_length() == bits and retries otherwise, silently accepting an off-by-one-bit key would subtly weaken the claimed security level.
• A composite candidate slipping through Miller-Rabin. Astronomically unlikely at 20+ rounds, but not literally impossible; this is why the round-trip encrypt/decrypt check in the worked example, and in production a check that $e \cdot d \equiv 1 \pmod{\phi(n)}$ holds exactly, are worth doing as a final belt-and-suspenders validation rather than trusting primality testing alone.

Approach

Twisted Edwards, Montgomery, and short Weierstrass curves are three different coordinate parameterizations of essentially the same underlying elliptic curve group (birationally equivalent, meaning there is a rational, invertible map between them that preserves the group structure). The task is to implement that map both directions for a curve like Ed25519's, handle the identity element and the curve's 2-torsion point (both of which break the generic formula, since it involves a division that becomes $0/0$ at those points), and confirm round-tripping through all three models returns the original point exactly.

Code

import random

def inv(x, p):
    return pow(x, p-2, p)

def legendre(a, p):
    a %= p
    if a == 0: return 0
    r = pow(a, (p-1)//2, p)
    return -1 if r == p-1 else r

def sqrt_mod(a, p):
    # p ≡ 3 mod 4 case (true for our toy prime)
    a %= p
    if a == 0: return 0
    if legendre(a, p) != 1: return None
    return pow(a, (p+1)//4, p)

# ---- toy twisted Edwards curve: a*x^2 + y^2 = 1 + d*x^2*y^2 (mod p) ----
p = 2003          # prime field (also happens to be our earlier curve's p, unrelated curve here)
a_ed = p - 1      # a = -1 mod p, same convention as Ed25519 (a = -1)
d_ed = 17         # pick some small non-square-ish d for a genuine (non-degenerate) twisted curve

def on_edwards(x, y):
    lhs = (a_ed * x*x + y*y) % p
    rhs = (1 + d_ed * x*x % p * y*y) % p
    return lhs == rhs

# Montgomery params derived from (a_ed, d_ed)
A = (2 * (a_ed + d_ed) % p) * inv((a_ed - d_ed) % p, p) % p
B = 4 * inv((a_ed - d_ed) % p, p) % p

def on_montgomery(u, v):
    return (B * v*v) % p == (u**3 + A*u*u + u) % p

# Weierstrass params derived from (A,B)
inv3 = inv(3, p)
invB = inv(B, p)
a_w = ((3 - A*A) % p) * inv(3*B*B % p, p) % p
b_w = ((2*A**3 - 9*A) % p) * inv(27*B**3 % p, p) % p

def on_weierstrass(X, Y):
    return (Y*Y) % p == (X**3 + a_w*X + b_w) % p

# --- forward map: twisted Edwards -> Montgomery ---
def edwards_to_montgomery(x, y):
    if (1 - y) % p == 0:
        return "INFINITY"          # neutral element (0,1) has y=1: maps to Montgomery point at infinity
    if x % p == 0:
        return (0, 0)              # order-2 point (0,-1): formula is 0/0, but continuity forces (0,0)
    u = (1 + y) % p * inv((1 - y) % p, p) % p
    v = (1 + y) % p * inv((1 - y) % p * x % p, p) % p
    return (u, v)

# --- inverse map: Montgomery -> twisted Edwards ---
def montgomery_to_edwards(u, v):
    if v % p == 0:
        return (0, p-1)            # Montgomery 2-torsion point (0,0)/(-1,0)-ish -> Edwards order-2 point (0,-1)
    if (u + 1) % p == 0:
        return (0, 1)              # maps to Edwards neutral element
    x = u * inv(v, p) % p
    y = (u - 1) % p * inv((u + 1) % p, p) % p
    return (x, y)

# --- Montgomery -> short Weierstrass ---
def montgomery_to_weierstrass(u, v):
    X = (u * invB + A * inv3 % p * invB) % p
    Y = v * invB % p
    return (X, Y)

def weierstrass_to_montgomery(X, Y):
    u = (B * X - A * inv3) % p
    v = (B * Y) % p
    return (u, v)

def find_curve_points(n):
    pts = []
    tries = 0
    while len(pts) < n and tries < 20000:
        tries += 1
        x = random.randrange(1, p)
        rhs = (1 - a_ed*x*x) % p
        denom = (1 - d_ed*x*x) % p
        if denom == 0:
            continue
        y2 = rhs * inv(denom, p) % p
        y = sqrt_mod(y2, p)
        if y is None:
            continue
        pts.append((x, y))
    return pts

if __name__ == "__main__":
    random.seed(20260901)  # pinned seed for reproducibility
    print(f"Toy twisted Edwards curve: {a_ed - p}*x^2 + y^2 = 1 + {d_ed}*x^2*y^2  (mod p={p}), a = -1 (Ed25519 convention)")
    print(f"Derived Montgomery params: A = {A}, B = {B}")
    print(f"Derived short-Weierstrass params: a = {a_w}, b = {b_w}\n")

    pts = find_curve_points(12)
    print(f"Sampled {len(pts)} random points on the Edwards curve; round-tripping each through")
    print("Edwards -> Montgomery -> Weierstrass -> Montgomery -> Edwards:\n")

    all_ok = True
    for (x, y) in pts:
        assert on_edwards(x, y)
        uv = edwards_to_montgomery(x, y)
        assert uv != "INFINITY"
        u, v = uv
        ok_m = on_montgomery(u, v)
        XY = montgomery_to_weierstrass(u, v)
        ok_w = on_weierstrass(*XY)
        u2, v2 = weierstrass_to_montgomery(*XY)
        ok_back = (u2, v2) == (u, v)
        x2, y2 = montgomery_to_edwards(u2, v2)
        ok_roundtrip = (x2, y2) == (x, y)
        all_ok = all_ok and ok_m and ok_w and ok_back and ok_roundtrip
        print(f"  Edwards{(x,y)} -> Montgomery{(u,v)} [on curve: {ok_m}] "
              f"-> Weierstrass{XY} [on curve: {ok_w}] -> back to Edwards{(x2,y2)} "
              f"[round-trip ok: {ok_roundtrip}]")

    print(f"\nAll {len(pts)} points verified end-to-end: {all_ok}")

    # special cases
    print("\n--- Special cases ---")
    neutral = edwards_to_montgomery(0, 1)
    print("Edwards neutral element (0,1) maps to Montgomery:", neutral, "(point at infinity, undefined by the affine formula)")
    order2 = edwards_to_montgomery(0, p-1)
    print("Edwards order-2 point (0,-1) maps to Montgomery:", order2, "-> on Montgomery curve:", on_montgomery(*order2))
    back_neutral = montgomery_to_edwards(0, 0)
    print("Montgomery 2-torsion point (0,0) maps back to Edwards:", back_neutral, "-> on Edwards curve:", on_edwards(*back_neutral))

Output:

Toy twisted Edwards curve: -1*x^2 + y^2 = 1 + 17*x^2*y^2  (mod p=2003), a = -1 (Ed25519 convention)
Derived Montgomery params: A = 1111, B = 890
Derived short-Weierstrass params: a = 1835, b = 1616

Sampled 12 random points on the Edwards curve; round-tripping each through
Edwards -> Montgomery -> Weierstrass -> Montgomery -> Edwards:

  Edwards(1641, 1420) -> Montgomery(390, 1681) [on curve: True] -> Weierstrass(1586, 1449) [on curve: True] -> back to Edwards(1641, 1420) [round-trip ok: True]
  Edwards(944, 883) -> Montgomery(703, 1416) [on curve: True] -> Weierstrass(1179, 1640) [on curve: True] -> back to Edwards(944, 883) [round-trip ok: True]
  Edwards(1037, 1850) -> Montgomery(1976, 902) [on curve: True] -> Weierstrass(458, 1950) [on curve: True] -> back to Edwards(1037, 1850) [round-trip ok: True]
  Edwards(1388, 973) -> Montgomery(712, 191) [on curve: True] -> Weierstrass(137, 142) [on curve: True] -> back to Edwards(1388, 973) [round-trip ok: True]
  Edwards(1219, 1823) -> Montgomery(331, 881) [on curve: True] -> Weierstrass(850, 1043) [on curve: True] -> back to Edwards(1219, 1823) [round-trip ok: True]
  Edwards(355, 1768) -> Montgomery(1340, 568) [on curve: True] -> Weierstrass(1317, 1450) [on curve: True] -> back to Edwards(355, 1768) [round-trip ok: True]
  Edwards(565, 1393) -> Montgomery(376, 1323) [on curve: True] -> Weierstrass(1649, 1057) [on curve: True] -> back to Edwards(565, 1393) [round-trip ok: True]
  Edwards(516, 520) -> Montgomery(1508, 1478) [on curve: True] -> Weierstrass(561, 1361) [on curve: True] -> back to Edwards(516, 520) [round-trip ok: True]
  Edwards(1191, 177) -> Montgomery(1524, 304) [on curve: True] -> Weierstrass(489, 635) [on curve: True] -> back to Edwards(1191, 177) [round-trip ok: True]
  Edwards(745, 748) -> Montgomery(1699, 1930) [on curve: True] -> Weierstrass(703, 1330) [on curve: True] -> back to Edwards(745, 748) [round-trip ok: True]
  Edwards(1267, 480) -> Montgomery(1910, 656) [on curve: True] -> Weierstrass(755, 1054) [on curve: True] -> back to Edwards(1267, 480) [round-trip ok: True]
  Edwards(402, 407) -> Montgomery(147, 105) [on curve: True] -> Weierstrass(1678, 529) [on curve: True] -> back to Edwards(402, 407) [round-trip ok: True]

All 12 points verified end-to-end: True

--- Special cases ---
Edwards neutral element (0,1) maps to Montgomery: INFINITY (point at infinity, undefined by the affine formula)
Edwards order-2 point (0,-1) maps to Montgomery: (0, 0) -> on Montgomery curve: True
Montgomery 2-torsion point (0,0) maps back to Edwards: (0, 2002) -> on Edwards curve: True

Key points

• Twisted Edwards to Montgomery: $a x^2 + y^2 = 1 + d x^2 y^2 \Rightarrow (u, v) = \left(\dfrac{1+y}{1-y}, \dfrac{1+y}{(1-y)x}\right)$, valid whenever $y \neq 1$ and $x \neq 0$.
• Montgomery to short Weierstrass: a standard linear change of variables using the Montgomery curve's $A, B$ coefficients: $X = \dfrac{u}{B} + \dfrac{A}{3B}$, $Y = \dfrac{v}{B}$, which is defined everywhere except the Montgomery point at infinity.
• Special cases that break the generic formula: the twisted Edwards neutral element $(0, 1)$ has $y = 1$, making the Edwards-to-Montgomery denominator zero; by continuity this must map to the Montgomery curve's point at infinity, and needs an explicit branch, not a division. The order-2 point $(0, -1)$ has $x = 0$, another explicit-branch case, mapping to the Montgomery 2-torsion point $(0, 0)$.

Complexity

Each direction of each map is a constant number of field operations (one modular inverse, a handful of multiplications), so $O(1)$ per point, independent of the field size beyond the usual $O(\log^2 p)$-ish cost of the modular inverse itself. There is no iteration or scalar involved; this is a pure coordinate-system change, not a group operation.

Edge cases

• The identity element on either curve model.
• The 2-torsion point (order exactly 2), which sits at the boundary where the generic Edwards or Montgomery formula divides by zero.
• Non-square or otherwise field-boundary inputs when constructing points from an $x$-coordinate alone (relevant if this function feeds a point-decompression routine); this implementation assumes it is handed a coordinate pair already known to satisfy the source curve's equation, and does not itself validate that.
• Working over the WRONG curve instance (using $Ed25519$'s $(a, d)$ pair as literals rather than deriving $A, B, a_w, b_w$ from them) is an easy way to silently produce points on the wrong curve; the implementation above derives Montgomery/Weierstrass parameters FROM the Edwards parameters rather than hardcoding separate literals for each model, so a parameter typo can only happen once, not three times independently.

Trade-offs and pitfalls

The practical reason to implement this at all: Ed25519 signing benefits from twisted Edwards' complete addition formulas (no special-casing, good for constant-time code, since the same formula handles addition, doubling, and the identity/negation cases with no branch to leak through a side channel), but some libraries or protocols expect a short-Weierstrass public key (X9.62/SEC1 encoding, common in X.509 certificates and older TLS code). Converting once at the API boundary, rather than re-deriving keys in a different model, avoids re-running key generation and keeps a single source of truth for the actual private scalar. The most common real bug in this kind of code is applying the WRONG special case (treating the 2-torsion point as the identity, or vice versa), which silently produces a point that looks plausible (it IS on the target curve) but is mathematically wrong, exactly the kind of error unit tests with known special-case vectors are meant to catch.

Direct answer

If an implementation reveals, even indirectly through a distinguishable error code, a connection reset, or a measurable timing difference, whether a submitted ciphertext decrypts to a validly PKCS#1 v1.5-padded value (PKCS, Public-Key Cryptography Standards, is the family of RSA conventions this padding format belongs to), it has handed an attacker a one-bit oracle. Bleichenbacher showed in 1998 that querying that oracle adaptively against carefully chosen, algebraically related ciphertexts, often tens of thousands of times, is enough to decrypt any target ciphertext without ever recovering the private key. Its modern descendants (such as the 2017 ROBOT disclosure) show this exact class of leak keeps resurfacing in real Transport Layer Security (TLS, the protocol behind HTTPS) deployments decades later.

Structured elaboration

Threat model. The attacker has a target ciphertext $c_0 = m_0^{e} \bmod n$ for an unknown padded plaintext $m_0$, and access to a server that will attempt to decrypt any ciphertext the attacker submits and, one way or another, reveal whether the result is validly PKCS#1 v1.5-padded (starts with the bytes 0x00 0x02, followed by nonzero padding bytes and a 0x00 delimiter).

The multiplicative property being exploited. RSA is homomorphic under multiplication: for any integer $s$ the attacker chooses, $c = c_0 \cdot s^{e} \bmod n$ decrypts to $m = s \cdot m_0 \bmod n$, without the attacker ever knowing $m_0$ or the private key.

Interval narrowing. Valid PKCS#1 v1.5 padding means the decrypted value falls in a known range:

where $B = 2^{8(k-2)}$ for a $k$-byte modulus. Each "valid" oracle response for a chosen $s$ implies there exists some integer $r$ (essentially, how many times $s \cdot m_0$ wrapped around modulo $n$) such that:

Early in the attack, $s$ is small and many candidate $r$ values are consistent with the response, giving only a modest narrowing. As the interval shrinks, larger, more carefully chosen $s$ values pin down $r$ almost uniquely, and each additional response narrows the surviving interval dramatically, until only one value of $m_0$ remains.

Worked example

A single genuine step of this interval-narrowing math, with real, pinned numbers (a small toy modulus, purely to keep the arithmetic followable; real Bleichenbacher targets need realistic modulus sizes, at least 1024-bit, both because PKCS#1 v1.5 padding needs room to exist at all, and because a real attack needs tens of thousands of adaptive queries against a genuine oracle to converge, not something a static worked example can honestly simulate end-to-end):

import math

k = 4                         # toy modulus byte-length (real attacks need >= 128 bytes / 1024-bit+)
B = 2 ** (8 * (k - 2))        # 65536
lo, hi = 2 * B, 3 * B         # the PKCS#1 v1.5 "valid padding" interval [2B, 3B)
print("k=%d bytes, B=%d, valid-padding interval [2B,3B) = [%d, %d)" % (k, B, lo, hi))

p, q = 46337, 46349
def is_prime(n):
    return n > 1 and all(n % i for i in range(2, int(math.isqrt(n)) + 1))
assert is_prime(p) and is_prime(q)
n = p * q
e = 3
d = pow(e, -1, (p - 1) * (q - 1))
print("toy modulus n=%d (p=%d, q=%d), e=%d" % (n, p, q, e))

m0 = lo + 12345               # the unknown target plaintext, assumed already validly padded
c0 = pow(m0, e, n)             # the target ciphertext (all the attacker ever sees)

# search for a multiplier s where the oracle would say "valid"
for s in range(2, 200000):
    c_s = (c0 * pow(s, e, n)) % n
    m_s = pow(c_s, d, n)        # = (s * m0) mod n, by RSA correctness; this is what the ORACLE checks
    if lo <= m_s < hi:
        break
print("first s giving a VALID oracle response: s=%d, (s*m0 mod n)=%d" % (s, m_s))

r = (s * m0 - m_s) // n         # the unique r with s*m0 - r*n = m_s
lo_bound = math.ceil((lo + r * n) / s)
hi_bound = math.ceil((hi + r * n) / s)
print("derived bound on m0 from this single response: [%d, %d), width=%d" % (lo_bound, hi_bound, hi_bound - lo_bound))
print("true m0=%d inside derived bound: %s" % (m0, lo_bound <= m0 < hi_bound))
print("original interval width was %d; this response narrowed it to width %d" % (hi - lo, hi_bound - lo_bound))

Running this prints:

k=4 bytes, B=65536, valid-padding interval [2B,3B) = [131072, 196608)
toy modulus n=2147673613 (p=46337, q=46349), e=3
first s giving a VALID oracle response: s=14976, (s*m0 mod n)=139379
derived bound on m0 from this single response: [143417, 143421), width=4
true m0=143417 inside derived bound: True
original interval width was 65536; this response narrowed it to width 4

The derived bound genuinely contains the true (otherwise unknown-to-the-attacker) plaintext, confirming the interval formula is self-consistent, and a single well-chosen query collapsed a 65536-wide candidate interval down to a width of only a few values. That collapse is dramatically tighter than an early-stage query would produce (early queries typically narrow the interval only modestly, this example deliberately used a large $s$ to illustrate what a late-stage, well-targeted query looks like).

Trade-offs and pitfalls

Defenses. Migrate to Optimal Asymmetric Encryption Padding (OAEP) for new protocols: it is provably indistinguishable-secure against chosen-ciphertext attacks under standard assumptions, removing the oracle at its root rather than patching around it. Where PKCS#1 v1.5 must remain for compatibility, the server must process every decryption identically regardless of whether the padding was valid, invalid at the very first byte, or invalid somewhere in the middle, generating a random fallback plaintext internally and continuing as if nothing were wrong, so that no observable signal (explicit error, connection behavior, or timing) distinguishes the cases.

Pitfalls. "Constant-time, uniform error handling" is notoriously easy to get subtly wrong: the 2017 ROBOT disclosure found the same class of distinguishable-error leak still alive in several major TLS implementations nearly twenty years after Bleichenbacher's original paper, often reintroduced by unrelated code changes elsewhere in the stack rather than a direct attempt to "fix padding." A defense also has to be applied consistently across an entire deployment, if even one server behind a load balancer leaks a distinguishable response, an attacker can simply target that one machine and the fleet-wide mitigation is worthless.

Direct answer

A KDF (key-derivation function, e.g. HKDF, built on HMAC, hash-based message authentication code) is a deterministic function of its inputs: the same input keying material with the same parameters always produces the same output key. If the ONLY input is a shared secret, and two different protocols happen to arrive at the same shared secret (the same two parties running the same underlying Diffie-Hellman, say), they derive the IDENTICAL symmetric key, even though the protocols intended those keys to be completely unrelated. Including explicit context (a transcript hash, a ciphersuite identifier, a role label) in the KDF's info field breaks that collision by construction, because it makes the derived key depend on WHICH protocol and WHICH exact handshake produced it, not just on the raw shared secret.

Structured elaboration

Why the collision happens at all. Two protocols, ProtoA and ProtoB, can end up performing Diffie-Hellman between the same two parties using the same long-term or ephemeral keys, particularly if a key is reused across protocols (a design smell in its own right, but a real one). If both then call something like

with an empty or missing info field, $K$ comes out byte-for-byte identical for both protocols, purely because HKDF is deterministic and the inputs happened to match.

Why this is exploitable, not just an odd coincidence. If ProtoA is a weaker or differently-audited protocol than ProtoB, an attacker who compromises a key in ProtoA's context can directly reuse that SAME key material to decrypt or impersonate within ProtoB, this is cross-protocol key confusion, and it breaks the key-separation assumption that lets each protocol be analyzed and trusted independently. It also silently invalidates security PROOFS: most formal security arguments for a KDF-based protocol implicitly assume the derived key is unique to that specific protocol run, an assumption a missing context field violates without any code obviously being "wrong" in isolation.

The fix. Bind the derivation to the exact context it should be scoped to: a transcript hash (a hash over every message exchanged so far, so the key is bound to this SPECIFIC handshake, not just this pair of parties), a ciphersuite or protocol identifier (so ProtoA and ProtoB, even given an identical shared secret, derive provably different info inputs), and a role label where the two sides play asymmetric roles (so, for instance, a client-to-server key and server-to-client key derived from the same shared secret do not collide with each other either).

Worked example

# KDF context binding: identical shared secret plus no protocol context collides across
# protocols; adding a transcript-bound info label separates the derived keys.
import hashlib, hmac

def hkdf_extract(salt, ikm):
    return hmac.new(salt, ikm, hashlib.sha256).digest()

def hkdf_expand(prk, info, length):
    t, okm = b"", b""
    counter = 1
    while len(okm) < length:
        t = hmac.new(prk, t + info + bytes([counter]), hashlib.sha256).digest()
        okm += t
        counter += 1
    return okm[:length]

if __name__ == "__main__":
    shared_secret = bytes.fromhex("2f6a91e0c8b3d4517aa9902ccf1e5b7a")  # same ECDH output, two protocols

    prk = hkdf_extract(b"", shared_secret)
    key_protoA_no_context = hkdf_expand(prk, b"", 16)
    key_protoB_no_context = hkdf_expand(prk, b"", 16)
    print("no context binding:")
    print(f"  ProtoA key = {key_protoA_no_context.hex()}")
    print(f"  ProtoB key = {key_protoB_no_context.hex()}")
    print(f"  keys identical: {key_protoA_no_context == key_protoB_no_context}")

    transcript = hashlib.sha256(b"pinned-illustrative-transcript").digest()
    info_A = b"ProtoA|ciphersuite=1|" + transcript
    info_B = b"ProtoB|ciphersuite=1|" + transcript
    key_protoA_bound = hkdf_expand(prk, info_A, 16)
    key_protoB_bound = hkdf_expand(prk, info_B, 16)
    print("with context binding:")
    print(f"  ProtoA key = {key_protoA_bound.hex()}")
    print(f"  ProtoB key = {key_protoB_bound.hex()}")
    print(f"  keys identical: {key_protoA_bound == key_protoB_bound}")

Output:

no context binding:
  ProtoA key = 104af198cb756f41f744d4de39c9b253
  ProtoB key = 104af198cb756f41f744d4de39c9b253
  keys identical: True
with context binding:
  ProtoA key = 5bf3e4b5046cfd622ef923433283add2
  ProtoB key = 74a51ddcc89f079fb385cc2affe88d19
  keys identical: False

Trade-offs and pitfalls

The fix costs essentially nothing computationally, info is just additional input bytes hashed alongside the rest, so there is no real trade-off to weigh against doing it; the pitfall is purely one of DISCIPLINE, a protocol designer who correctly implements HKDF but treats the info field as optional metadata rather than a security-critical binding. A related, subtler pitfall: including a WEAK or non-unique context (say, a fixed string literal shared by every deployment of the protocol rather than something that varies per handshake, like a real transcript hash) provides only PARTIAL protection, it separates protocol A from protocol B, but does nothing to bind the key to this specific SESSION if the transcript itself is not included, so two runs of the same protocol between the same parties could still collide if the context omits per-session randomness.

Direct answer

The Bellcore attack extracts an RSA private key from a SINGLE faulty CRT (Chinese Remainder Theorem)-based decryption or signature: if a transient fault (induced by voltage glitching, clock manipulation, or a naturally-occurring hardware error) corrupts only the mod-$p$ half of the computation while the mod-$q$ half stays correct, the faulty output $S'$ and the correct output $S$ agree modulo $q$ but disagree modulo $p$, which means their difference is a multiple of $q$ and NOTHING ELSE, so $\gcd(N, S - S')$ directly recovers the prime factor $q$.

Structured elaboration

Why CRT specifically makes this easy. Without CRT, a full-width exponentiation $S = c^d \bmod N$ mixes information about both $p$ and $q$ together inseparably at every step; a random fault anywhere in that computation corrupts the WHOLE result in a way that does not cleanly isolate one factor. CRT deliberately SPLITS the computation into two independent halves, $m_1 = c^{d_p} \bmod p$ and $m_2 = c^{d_q} \bmod q$ (computed separately, purely for a roughly 4x speed advantage over the non-CRT approach), then recombines them. A fault landing in just ONE of those two independent halves corrupts only that half's contribution, which is exactly the structural property the attack exploits, the recombination step cannot tell "this factor's contribution was wrong" from "this factor's contribution is correct," it just recombines whatever it was given.

The mechanism, precisely. If the fault hits the mod-$p$ branch, producing $m_1' \neq m_1$ while $m_2$ stays correct, then after CRT recombination, $S' \equiv S \pmod q$ (the correct half) but $S' \not\equiv S \pmod p$ (the faulted half). So $q \mid (S - S')$ but $p \nmid (S - S')$ (except in the astronomically unlikely case the fault happens to produce a value that also collides mod $p$), meaning $\gcd(N, S - S')$ is exactly $q$: not a multiple of $q$, not related to $q$, the prime factor $q$ itself, in one gcd computation, from ONE faulty signature or decryption plus knowledge of the corresponding correct one (or even just two DIFFERENT faulty outputs from the same input under different fault conditions, in variants of the attack).

Countermeasures, in order of how directly they address the mechanism:

• Result verification. Before releasing a CRT-computed signature or decrypted value, check it against the public operation: for a signature, verify $S^e \equiv c \pmod N$ using the public exponent; for decryption, re-encrypt and compare. This directly catches ANY fault, in either branch, before the faulty value ever leaves the device, closing the attack completely regardless of where the fault landed.
• Blinding. Randomizing the input before exponentiation (as in the RSA timing-attack blinding technique) does not directly stop a fault from corrupting one CRT branch, but it does prevent an attacker from correlating a specific known plaintext or ciphertext with the fault's effect across repeated attempts, reducing the attack's practicality even where full result verification is unavailable.
• Redundant computation. Performing the exponentiation twice (either literally twice, or via an algorithmically different second method) and comparing results before release catches a transient fault the same way result verification does, at roughly double the computational cost instead of one cheap public-exponent verification.
• Hardware and firmware defenses. Voltage and clock-glitch detection circuits, tamper sensors, and instruction-integrity checks aim to detect or prevent the fault from being INDUCED in the first place, a defense-in-depth layer underneath the algorithmic countermeasures above, not a replacement for them.

Worked example

# Bellcore single-fault attack on CRT-RSA: one faulty branch leaks a prime factor via gcd.
import math
p, q = 61, 53
N, phi = p * q, (p - 1) * (q - 1)
e = 17
d = pow(e, -1, phi)
dp, dq = d % (p - 1), d % (q - 1)
qinv = pow(q, -1, p)

def crt_decrypt(c, faulty_mod_p=False):
    m1 = pow(c % p, dp, p)
    if faulty_mod_p:
        m1 = (m1 + 1) % p  # simulate one transient fault in the mod-p branch only
    m2 = pow(c % q, dq, q)
    h = (qinv * (m1 - m2)) % p
    return (m2 + h * q) % N

if __name__ == "__main__":
    c = 2790  # a ciphertext/signature input
    S_correct = crt_decrypt(c, faulty_mod_p=False)
    S_faulty = crt_decrypt(c, faulty_mod_p=True)
    print(f"N={N} (p={p}, q={q}, unknown to the attacker)")
    print(f"correct CRT output S  = {S_correct}")
    print(f"faulty CRT output  S' = {S_faulty}  (one transient fault in the mod-p branch only)")

    diff = (S_correct - S_faulty) % N
    g = math.gcd(diff, N)
    print(f"gcd(N, S - S') = gcd({N}, {diff}) = {g}")
    print(f"recovered factor {g} == q ({q})? {g == q}  ->  other factor = N // {g} = {N // g}")

Output:

N=3233 (p=61, q=53, unknown to the attacker)
correct CRT output S  = 65
faulty CRT output  S' = 2079  (one transient fault in the mod-p branch only)
gcd(N, S - S') = gcd(3233, 1219) = 53
recovered factor 53 == q (53)? True  ->  other factor = N // 53 = 61

Trade-offs and pitfalls

Result verification is close to a free defense (one cheap public-exponent operation against one expensive private-exponent operation) and closes the attack completely, which is exactly why its absence in a real CRT-RSA implementation is considered a serious, not-merely-theoretical defect; several real smart-card and hardware-security-module product lines have shipped with this check missing at various points, and once known, this exact attack was demonstrated to extract full private keys with practical fault-injection equipment. A common but WRONG mitigation is assuming blinding alone is sufficient, blinding decorrelates a TIMING attack across repeated calls, but it does not stop a SINGLE fault from corrupting one CRT branch on any individual call, the fault attack and the timing attack are different threat models with an overlapping-sounding but distinct fix.