Alice and Bob Solution

by Soumil Mukherjee

FLAG: 1715359156632385906

The trick to solving this problem is realizing that the encryption system used by Alice and Bob is the Diffie-Hellman Key Exchange. In the DH Key Exchange, Alice and Bob each pick a private key (which I will call a and b). Alice and Bob do not share their private keys, not even with each other. Then, they collectively decide on a prime p, and a base number g. At this point, any eavesdropper (such as Keith) can easily find out what p and g are, but does not know the private keys of either individual. Once Alice and Bob have agreed on the values of p and g, each person calculates the modular power of their private key mod p. In simpler terms, Alice calculates $$g^a (mod\ p)$$ and Bob calculates $$g^b (mod\ p)$$. These are now their public keys, which I will refer to as A and B respectively. Alice sends A to Bob, and Bob sends B to Alice, on reliable, but not necessarily secure communication channels. In practice, g and p will be so large that even the fastest supercomputers would take an extraordinary amount of time to solve a from A, or b from B, so it is not necessary to hide A or B. However, this is where Alice and Bob falter, since their g and p are extremely small, which is hinted at by Bob's comment "Aren't those numbers too small?". Once Bob receives A, he can find the shared message (in this case, the secret number) by calculating $$A^b (mod\ p)$$, which is equivalent to $$g^{ab} (mod\ p)$$. Similarly, Alice can find the same number by calculating $$B^a (mod\ p)$$. For Keith to find the secret message, he needs to solve for either a or b, and use one of the public keys to find the secret message. He can do this by taking advantage of the small numbers used, which enables him to use a simple brute-force method to find either private key.

The Java program below solves for both private keys, and uses one of them to solve for the secret number. Since Alice and Bob use a p that is close to the maximum value of the Long class, the program uses BigInteger. Also, as an additional advantage, BigInteger has a method for modular exponentiation, which greatly simplifies the algorithm.

The complete program can be found below:

import java.math.BigInteger;
public class DHDecrypter {
  BigInteger g; // Base used
  BigInteger p; // Modulus used
  BigInteger A; // Alice's Public Key
  BigInteger B; // Bob's Public Key
  public DHDecrypter(BigInteger base, BigInteger mod, BigInteger alice, BigInteger bob) {
    g = base;
    p = mod;
    A = alice;
    B = bob;
  }
  public BigInteger getAlicePrivateKey() {
    BigInteger i = BigInteger.ZERO;
    while (!g.modPow(i, p).equals(A)) {
      i = i.add(BigInteger.ONE);
    }
    return i;
  }
  public BigInteger getBobPrivateKey() {
    BigInteger i = BigInteger.ZERO;
    while (!g.modPow(i, p).equals(B)) {
      i = i.add(BigInteger.ONE);
    }
    return i;
  }
  public BigInteger getMessage() {
    return A.modPow(getBobPrivateKey(), p);
    // return B.modPow(getAlicePrivateKey(), p);
  }

  public static void main(String[] args) {
    BigInteger g = new BigInteger("987");
    BigInteger p = new BigInteger("8911991767204557841");
    BigInteger a = new BigInteger("731665363559374475");
    BigInteger b = new BigInteger("1317032838957486192");
    DHDecrypter keith = new DHDecrypter(g, p, a, b);
    System.out.println("Secret Number: " + keith.getMessage());
  }
}

results matching ""

    No results matching ""