Shared Secrets picoCTF 2026 Solution

Description

1. Step 1Analyse the encryption scheme

   Observation

   The description says one side of the exchange leaked something, and encryption.py is provided. Read it first and sort out which Diffie-Hellman parameters were published from which value leaked.

   The source shows a Diffie-Hellman exchange with g=2 and a large prime p. Both parties publish their public key (g^priv mod p). The shared secret is A^b mod p where A is one party's public key and b is the other's leaked private key.

   Learn more

   Diffie-Hellman key exchange (1976) was the first published public-key cryptographic protocol, enabling two parties to establish a shared secret over an insecure channel without having met before. Each party generates a private key (a random integer) and computes a public key as g^private mod p. They exchange public keys, and each can compute the same shared secret: shared = other_public^my_private mod p. An eavesdropper who sees both public keys cannot compute the shared secret without solving the discrete logarithm problem - finding x such that g^x = A mod p.

   The security of DH depends entirely on the private keys remaining secret. If either party leaks their private key, the shared secret is immediately compromised: anyone can compute A^b mod p from the public key A and the leaked private b. This is a fundamental lesson in cryptographic key management - even a mathematically secure protocol is broken by implementation failures like logging private keys or storing them insecurely.

   In modern systems, DH is used in TLS (as DHE or ECDHE cipher suites), Signal protocol, and WireGuard VPN. The "E" in DHE stands for "Ephemeral" - a new key pair is generated for every session, providing forward secrecy: compromising the server's long-term key does not expose past session keys. ECDH uses elliptic curve groups instead of multiplicative groups, providing equivalent security with smaller key sizes.

2. Step 2Compute the shared secret

   Observation

   encryption.py leaks one private key alongside the other side's public key and the prime. That is enough to compute the shared secret directly, with no discrete logarithm involved.

   Pull p, A, b, and the ciphertext (verify the encoding - hex, base64, or raw - from encryption.py rather than guessing). Validate 1 < A,B < p as a sanity check, compute shared = pow(A, b, p), then try the obvious key derivations until one yields a printable picoCTF{...} prefix.

   python

   python3 << 'EOF'
   import hashlib
   
   # Confirm the ciphertext encoding by reading encryption.py:
   #   - hex string  -> bytes.fromhex(...)
   #   - base64      -> base64.b64decode(...)
   #   - raw bytes   -> open(..., "rb").read()
   p = YOUR_PRIME
   A = YOUR_PUBLIC_KEY   # g^a mod p
   b = YOUR_LEAKED_PRIV  # leaked private key
   
   # Sanity check on the public values
   assert 1 < A < p, "A must satisfy 1 < A < p"
   
   shared = pow(A, b, p)
   ct = bytes.fromhex("YOUR_CIPHERTEXT_HEX")
   
   # Try the obvious key derivations in order:
   candidates = [
       ("low byte",  bytes([shared & 0xFF])),
       ("byte 1",    bytes([(shared >> 8) & 0xFF])),
       ("sha256[:1]", hashlib.sha256(str(shared).encode()).digest()[:1]),
       ("sha256[:16]", hashlib.sha256(str(shared).encode()).digest()[:16]),
   ]
   
   for name, key in candidates:
       pt = bytes(c ^ key[i % len(key)] for i, c in enumerate(ct))
       if pt.startswith(b"picoCTF{"):
           print(name, "->", pt.decode(errors="replace"))
           break
   EOF

   Copied!

   Expected output

   low byte -> picoCTF{dh_s3cr3t_...}

   What didn't work first

   Tried: Compute the shared secret using both public keys (pow(A, B, p)) instead of one public key and the leaked private key

   That raises one public key to the other public key, which is not the shared secret. The exponent has to be the leaked private key from the message file. Substitute the public key for it and you get a different number entirely, which XORs to garbage: the math only closes when the exponent is the private key that generated the other party's public value.

   Tried: Try SHA-256 of the full shared integer as the decryption key before checking the low-byte derivation

   Hashing the shared secret would give a 32-byte key, but the source uses a single-byte XOR against its low byte. A 32-byte key cycles on a 32-byte period instead of one, so the plaintext never starts correctly even if the occasional byte lines up. Read the source and confirm the derivation before improvising.

   Learn more

   What pow(A, b, p) actually does. Python's three-argument pow runs square-and-multiply modular exponentiation: scan the bits of the exponent b from MSB to LSB, square the running result mod p on every step, and multiply by A mod p when the current bit is 1. That is O(log b) multiplications, each of which is at most a 1048x1048-bit modular multiply for this challenge (encryption.py calls getPrime(1048)). A 1048-bit b means roughly 1570 mod-mul operations. Done in microseconds. Naively computing A**b first would produce a number with ~10^308 digits and never finish.

   Validate inputs. A real DH stack rejects values where A <= 1, A == p-1, or A >= p; a leaked private key paired with a degenerate public value can collapse the shared secret into a small set. Check 1 < A < p and 1 < B < p before doing anything else.

   Entropy collapse. A 1048-bit prime p means the shared secret has roughly 1048 bits of entropy. Reducing to shared % 256 throws away the other 1040 bits and gives you 256 candidate keys total - already brute-forceable without DH. A real KDF (HKDF) would absorb the whole shared secret and expand into a full-size key; this protocol throws all that work away in one line.

   If shared % 256 doesn't produce a flag, read encryption.py more carefully and try the next-most-likely derivations: high byte (shared >> 8 & 0xFF), the SHA-256 of str(shared) truncated to 1 or 16 bytes, or the raw shared bytes via shared.to_bytes((shared.bit_length()+7)//8, 'big'). The brute snippet above tries the common ones in order.

   See RSA attacks for CTF for the broader public-key attack catalogue and AES for CTF for symmetric KDF practice.

   Diffie-Hellman walkthrough (toy parameters):
     Public params:  p = 23,  g = 5
   
     Alice picks a = 6 (private)
       Computes A = g^a mod p = 5^6 mod 23
                 = 15625 mod 23
                 = 8
     Bob picks b = 15 (private)
       Computes B = g^b mod p = 5^15 mod 23
                 = 30517578125 mod 23
                 = 19
   
     Public exchange: Alice sends A=8, Bob sends B=19.
   
     Alice computes shared = B^a mod p = 19^6 mod 23
                                       = 47045881 mod 23
                                       = 2
     Bob computes   shared = A^b mod p = 8^15 mod 23
                                       = 35184372088832 mod 23
                                       = 2
   
   Both arrive at the same shared = 2 without exchanging it.
   
   Now suppose Bob's private key b = 15 LEAKS.
   An eavesdropper sees A = 8 (from the public network) and learns
   b = 15 from the leak. They compute:
     shared = A^b mod p = 8^15 mod 23 = 2
   
   The shared secret is recovered without ever solving the discrete
   log problem.
   
   In this challenge, p is a 1048-bit prime, but the principle is
   identical: pow(A, b, p) recovers shared in microseconds.
   
   Then key = shared % 256 reduces to one byte. XOR each ciphertext
   byte with this byte:
     ct[i] XOR key  -->  pt[i]
   
   For the toy: if ct = [0x70, 0x69, 0x63, 0x6f] XOR 0x02 = [0x72, 0x6b, 0x61, 0x6d],
   then "rkam" is the wrong recovery (toy params lack proper byte semantics);
   in the real challenge the recovered byte XOR produces "pico..." and the
   flag emerges.

Flag

Diffie-Hellman with a leaked private key b. Compute shared = A^b mod p, then key = shared % 256. XOR each ciphertext byte with key to decrypt the flag. The flag is shown abbreviated on this page; work the steps above to recover the full value.