DLPoly - InCTF Internationals 2020

Crypto
, , ,

TL;DR

  1. Change the Field of g and h to prime modulus from composite modulus.
  2. Solve the DLP using pohlig-hellman attack.
  3. Wrap it with flag format.

Challenge

D L Poly

Challenge Points: 676

Description

RSA is easy. DLP is hard. Challenge files: out.txt.

Challenge Author: pyr0

Attachment

- out.txt

given file

By looking at this, we can say that the challenge is about polynomial DLP, as mentioned in the name D L Poly.

1
2
3
4
5
6
7
8
9
10
11
sage: p
35201
sage: len(flag)
14
sage: X = int.from_bytes(  flag.strip(b'inctf{').strip(b'}') ,  'big')
sage: n
1629*x^256 + 25086*x^255 + 32366*x^254  + ... + 16286*x + 12050
sage: g
x
sage: g^X
10254*x^255 + 11436*x^254 + 9453*x^253 + ... + 549*x + 1468

We know the upper bound of X is 256^7.

Factoring

If we see the n, we can notice that it is not a prime polynomial. It has many factors.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
sage: P.<x> = PolynomialRing(GF(p))
....: n = P(n)
....: list(n.factor())
....:
[(x^6 + 6522*x^5 + 30239*x^4   + ... + 8797*x + 1288, 1),
(x^10 + 892*x^9 + 21744*x^8   + ... 7980*x + 25558,1),
(x^10 + 3448*x^9 + 17391*x^8  + ... 29448*x + 5415,1),
(x^10 + 4097*x^9 + 21262*x^8  + ... 1018*x + 7369,1),
.
.
.
(x^10 + 25254*x^9 + 1035*x^8  +  ... 20868*x + 13941,1),
(x^10 + 26554*x^9 + 33072*x^8 + ... 34044*x + 34664,1),
(x^10 + 34596*x^9 + 19833*x^8 + ... 28425*x + 25916,1),
(x^10 + 35044*x^9 + 26290*x^8 + ... 32131*x + 4231,1)]

So we can change the modulus to any of these factors of n, but if we notice phi for the polynomials having degree 10, it is factorable, and thus we can make a pohlig-hellman attack to recover X.

1
2
3
4
5
6
7
phi = p^10-1
P.<x> = PolynomialRing(GF(p))
n = P(n)
q = n.factor()[1][0]
R.<x> = P.quotient(q)
g = R(g)
h = R(h)`

Now the ring of g and h is an irreducible polynomial, and we can perform a pohlig-hellman attack.

pohlighellman

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def pohlighellman(g,y,p,phi):

    factors = ecm.factor(phi)
#ignoring the smallest factors    
    factors = { i : factors.count(i) for i in sorted(list(set(factors)))[2:]}

    a,n = [],[]
    for q,e in factors.items():
        x = 0
        G = g^(phi//q)
        Y = y

        for i in range(e):
            h = Y^(phi//q**(i+1))
            X = discrete_log(h,G,ord = phi)
            assert X != None, f'Got None for brute{G,h,p}'
            x += q^i*X
            Y = Y * g^-X

        a.append(x)
        n.append(q^e)

    x = crt(a,n)
    assert g^x == y
    return x

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#given:
load('given.sage')


#pohlig-hellman:
def pohlighellman(g,y,p,phi):

    factors = ecm.factor(phi)
#ignoring the smallest factors
    factors = { i : factors.count(i) for i in sorted(list(set(factors)))[2:]}

    a,n = [],[]
    for q,e in factors.items():
        x = 0
        G = g^(phi//q)
        Y = y

        for i in range(e):
            h = Y^(phi//q**(i+1))
            X = discrete_log(h,G,ord = phi)
            assert X != None, f'Got None for brute{G,h,p}'
            x += q^i*X
            Y = Y * g^-X

        a.append(x)
        n.append(q^e)

    x = crt(a,n)
    assert g^x == y
    return x


#make the modulus as prime:
phi = p^10-1
P.<x> = PolynomialRing(GF(p))
n = P(n)
q = n.factor()[1][0]
R.<x> = P.quotient(q)
g = R(g)
h = R(h)


#finding flag:
X = pohlighellman(g,h,p,phi)
flag = b'inctf{'+int.to_bytes(int(X),6,'big')+b'}'
assert flag == b'inctf{bingo!}'

Conclusion

Polynomials are easy to break even if they have a large order than integer order.

I hope you enjoyed the challenge!