Shared Secrets picoCTF 2026 Solution

Description

1. Step 1Analyse the encryption scheme
   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
   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!
   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 1024x1024-bit modular multiply for this challenge. A 1024-bit b means roughly 1500 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 1024-bit prime p means the shared secret has roughly 1024 bits of entropy. Reducing to shared % 256 throws away the other 1016 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 1024-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.

Alternate Solution

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.