# Difficult Decryption
> We intercepted communication between two VERY important people, named Alice and Bob. Can you figure out what this is supposed to mean?> > Alice: "Bob, I need to tell you something."> > Bob: "What?"> > Alice: "It's top-secret, so let's use a secure encryption method."> > Bob: "Is that really necessary? Like, who would listen?"> > Alice: "Doesn't matter. This is really serious."> > Bob: "Uh, okay then."> > Alice: >> Modulus: 491988559103692092263984889813697016406>> Base: 5> > Base ^ A % Modulus:>> 232042342203461569340683568996607232345>> -----> Bob: > Got it.> > Here's my Base ^ B % Modulus:>> 76405255723702450233149901853450417505>> -----> Alice: > Thanks. > > Here's the encoded message: > 12259991521844666821961395299843462461536060465691388049371797540470> > I encoded it using this Python command: "message ^ (pow(your_key, A, modulus))". Your_key is Base ^ B % Modulus.>> After you decode the message, it will be a decimal number. Convert it to hex. You know what to do after that.>> -----> Bob: Okay.>> Alice: Also, do NOT tell anyone what I just told you. I'll give you more information later.
## Description
We get an exchange between Alice and Bob. We can see the encoded message using a [one time pad](https://en.wikipedia.org/wiki/One-time_pad), the shared key being obtained using a [Diffie-Hellman key exchange](https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange). 
As a remainder, the exchange works as follow:
- A common modulus `p` and a generator `g` are chosen. Here `p` is the modulus and `g` the base.- Alice and Bob choose private keys `A` and `B`.- They send to each other their public keys `pA = g^A [p]` and `pB = g^B [p]`- They deduce the same shared key `K = pA ^ B = pB ^ A = g^(AB) [p]`.
Then this shared key is xored with the message to get the ciphertext.
## Solution
The idea here is to find the private key of one party. This is the Discrete Logarithm Problem (DLP).
We will be using the [Pohlig-Hellman algorithm](https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm) to solve the discrete logarithm problem. [This paper](http://anh.cs.luc.edu/331/notes/PohligHellmanp_k2p.pdf) explains it very well. The steps are as follow:- first compute `phi(p)` (Euler's totient function), decompose it in prime factors.- solve the DLP for every factor: this gives an easier subproblem.- combine all results using the Chinese Remainder Theorem.
Disclaimer: as the factors are very small, code shown here is not optimal.
### Helper functions
First we define some number theory helper functions.
#### Extended Euclid's Algorithm and Modular Inversion
```pythondef egcd(a, b):    if a == 0:        return (b, 0, 1)    else:        g, y, x = egcd(b % a, a)        return (g, x - (b // a) * y, y)
def modinv(a, m):    g, x, y = egcd(a, m)    if g != 1:        raise Exception('modular inverse does not exist')    else:        return x % m```
([Source](https://stackoverflow.com/questions/4798654/modular-multiplicative-inverse-function-in-python))
#### Very naïve factorization and phi computation
```pythondef compute_phi(N):    N_ = N    phi = 1    x = 2    while N_ != 1:        if N_ % x == 0:            N_ //= x            phi *= (x-1)            while N_ % x == 0:                N_ //= x                phi *= x        x += 1    return phi
def factorize(N):    N_ = N    factors = []    exponents = []    x = 2    while N_ != 1:        if N_ % x == 0:            N_ //= x            factors.append(x)            exponents.append(1)            while N_ % x == 0:                N_ //= x                exponents[-1] += 1        x += 1    return factors, exponents```
#### Gauss Algorithm for the CRT
```pythondef ChineseRemainderGauss(n, N, a):    result = 0    for i in range(len(n)):        ai = a[i]        ni = n[i]        bi = N // ni        result += ai * bi * modinv(bi, ni)    return result % N```
([Source](https://medium.com/@astartekraus/the-chinese-remainder-theorem-ea110f48248c))
### Implementation of Pohlig–Hellman Algorithm
Then comes the real interesting part: the implementation of Pohlig–Hellman Algorithm.
First I define a naïve brute force for solving the DLP:
```pythondef bruteforce_DLP(A, B, p, q):    for i in range(q):        if B == pow(A,i,p):            return i```
This function bruteforces the solution of the DLP `A^x = B [p]`, knowing the order of `A` is at most `q`.
Using this function, I can compute a DLP solution modulo `q^m` where `q` is prime. The following function finds `x` modulo `q^m` such that `alpha^x = beta [p]`. 
To do this, I express `x = a_0 + a_1 q + ... + a_{b-1} q^(b-1) [q^m]`, and I compute coefficients `a_i` one by one. Look at the paper cited above for more precise explanations.
```pythondef easy_DLP(q, m, alpha, beta, p):    A = pow(alpha, order//q, p)    alpha1 = modinv(alpha,p)
    q_pow = 1    x = 0    for i in range(m):        B = pow(beta, order // (q_pow*q), p)        ai = bruteforce_DLP(A, B, p, q)        x += (ai*q_pow)        beta *= pow(alpha1, ai*q_pow, N)        beta = beta % N        q_pow *= q    return x```
Finally I can produce the Pohlig–Hellman Algorithm: it finds `x` such that `alpha^x = beta [p]` where `order` is the order of `alpha` in (*Z*/p*Z*)* and `beta` belongs in the subgroup generated by `alpha`.
```pythondef pohlig_hellman(alpha, beta, p, order):    remainders = []    modulo = []    factors, exponents = factorize(order)    for q,m in zip(factors,exponents):        remainders.append(easy_DLP(q, m, alpha, beta, p))        modulo.append(q**m)
    return ChineseRemainderGauss(modulo, order, remainders)```
### Finding the flag
With all our number theory algorithms, we can find the flag.
```python# Define constantsN = 491988559103692092263984889813697016406g = 5yA = 232042342203461569340683568996607232345yB = 76405255723702450233149901853450417505
ctxt = 12259991521844666821961395299843462461536060465691388049371797540470
# Find the subgroup generated by gphi = compute_phi(N)factors_phi, _ = factorize(phi)
order = phifor p in factors_phi:    while pow(g, order // p, N) == 1:        order //= pprint("Order:", order)# Order: 39329404631756038800
# Solve the DLPxA = pohlig_hellman(g, yA, N, order)print("Alice's secret key:", xA)# Alice's secret key: 25222735067058727456
# Compute the shared key and decrypt the OTPkey = pow(yB, xA, N)print(bytes.fromhex(hex(ctxt ^ key)[2:]))```
Flag: `tjctf{Ali3ns_1iv3_am0ng_us!}`