crypto (500 points, 1 solve)

In this challenge, the goal was to compute $x$ given $ (g,g^{69^x}) $ in the binary field $\mathbb F_{2^{127}}$.

TLDR: Magma solves DLPs in $\mathbb F_{2^{127}}$ fast.

For completeness, here’s the entire challenge (sage) source code:

from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
load('secret.sage')
M = x^127 + x^126 + x^125 + x^124 + x^122 + x^120 + x^118 + x^117 + x^115 + x^108 + x^107 + x^104 + x^103 + x^100 + x^99 + x^98 + x^96 + x^95 + x^94 + x^91 + x^88 + x^85 + x^83 + x^82 + x^81 + x^77 + x^74 + x^72 + x^70 + x^66 + x^65 + x^64 + x^57 + x^56 + x^55 + x^54 + x^50 + x^49 + x^48 + x^46 + x^44 + x^43 + x^37 + x^36 + x^34 + x^33 + x^28 + x^25 + x^22 + x^19 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^11 + x^10 + x^8 + x^7 + x^4 + x^2 + 1

K.<x> = GF(2^127, 'x', M)
z = x + 1

# for _ in range(n):
#     z = z**69
z = z**ZZ(pow(69, n, z.multiplicative_order()))

print(z)

aes = AES.new(long_to_bytes(n), AES.MODE_ECB)
print(aes.encrypt(flag.encode()).hex())

The following output was given:

x^126 + x^124 + x^123 + x^120 + x^119 + x^118 + x^117 + x^116 + x^115 + x^114 + x^111 + x^109 + x^108 + x^107 + x^105 + x^103 + x^100 + x^99 + x^98 + x^95 + x^92 + x^87 + x^84 + x^83 + x^82 + x^80 + x^79 + x^76 + x^74 + x^73 + x^71 + x^70 + x^69 + x^67 + x^64 + x^62 + x^61 + x^56 + x^52 + x^51 + x^48 + x^47 + x^45 + x^44 + x^41 + x^40 + x^36 + x^35 + x^34 + x^30 + x^29 + x^27 + x^25 + x^24 + x^18 + x^17 + x^16 + x^15 + x^14 + x^12 + x^11 + x^10 + x^8 + x^6 + x^5 + x^4 + x
55bd2e97c4efb27b8352ae7e4bcba2b566a9c6f645e4e59312f1945a461c71035a2396a72c3099cd39ec88d238be73992505436068f3f5a416a1bb72d59e2b74

---

Alright, so the obvious path to solving this task is to first solve a DLP in the field $\mathbb F_{2^{127}}$ to recover the exponent $e=69^x \bmod {}$$\lambda$$(2^{127}-1)$, then solve another DLP in the ring $\mathbb Z/(2^{127}-1)$ to recover $x$ from $e$.

Algorithms for DLP in small-characteristic fields are asymptotically quasi-polynomial, but it appears that even older, subexponential-time methods such as Coppersmith’s 1984 algorithm should be good enough for the given instance. Although it doesn’t appear very hard to implement this algorithm on our own, let’s first try to find someone else’s code. A little bit of internet search reveals that Magma apparently uses the algorithm, so we decided to give it a shot in the online calculator. Magma’s irreducible polynomial to define $\mathbb F_{2^{127}}$ is different from the one in the challenge, so we need to do a little bit of converting:

M = x^127 + x^126 + x^125 + x^124 + x^122 + x^120 + x^118 + x^117 + x^115 + x^108 + x^107 + x^104 + x^103 + x^100 + x^99 + x^98 + x^96 + x^95 + x^94 + x^91 + x^88 + x^85 + x^83 + x^82 + x^81 + x^77 + x^74 + x^72 + x^70 + x^66 + x^65 + x^64 + x^57 + x^56 + x^55 + x^54 + x^50 + x^49 + x^48 + x^46 + x^44 + x^43 + x^37 + x^36 + x^34 + x^33 + x^28 + x^25 + x^22 + x^19 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^11 + x^10 + x^8 + x^7 + x^4 + x^2 + 1

K.<x> = GF(2^127, 'x', M)
z0 = x + 1
zn = x^126 + x^124 + x^123 + x^120 + x^119 + x^118 + x^117 + x^116 + x^115 + x^114 + x^111 + x^109 + x^108 + x^107 + x^105 + x^103 + x^100 + x^99 + x^98 + x^95 + x^92 + x^87 + x^84 + x^83 + x^82 + x^80 + x^79 + x^76 + x^74 + x^73 + x^71 + x^70 + x^69 + x^67 + x^64 + x^62 + x^61 + x^56 + x^52 + x^51 + x^48 + x^47 + x^45 + x^44 + x^41 + x^40 + x^36 + x^35 + x^34 + x^30 + x^29 + x^27 + x^25 + x^24 + x^18 + x^17 + x^16 + x^15 + x^14 + x^12 + x^11 + x^10 + x^8 + x^6 + x^5 + x^4 + x

R.<Y> = GF(2)[]
P = Y**127 + Y + 1              # polynomial chosen by Magma
L.<z> = GF(2^127, 'z', P)
iso_imx = list(sorted(K.modulus()(polygen(L)).roots(multiplicities=False)))[0]
iso = lambda el: K(el).polynomial()(iso_imx)
print(iso(z0))
print(iso(zn))

(Here, z0 and zn are the generator x+1 and the given target power of x+1, respectively.) This prints:

z^121 + z^118 + z^116 + z^111 + z^110 + z^107 + z^104 + z^100 + z^99 + z^97 + z^96 + z^93 + z^92 + z^90 + z^89 + z^87 + z^83 + z^78 + z^74 + z^70 + z^66 + z^64 + z^63 + z^61 + z^58 + z^57 + z^55 + z^50 + z^49 + z^48 + z^46 + z^44 + z^39 + z^37 + z^36 + z^35 + z^34 + z^27 + z^26 + z^25 + z^24 + z^22 + z^21 + z^20 + z^19 + z^18 + z^15 + z^13 + z^12 + z^11 + z^10 + z^8 + z^7 + z^3 + z^2
z^124 + z^123 + z^121 + z^118 + z^115 + z^112 + z^109 + z^108 + z^107 + z^106 + z^100 + z^99 + z^95 + z^94 + z^93 + z^92 + z^91 + z^90 + z^88 + z^84 + z^83 + z^80 + z^78 + z^75 + z^68 + z^66 + z^65 + z^63 + z^61 + z^60 + z^58 + z^57 + z^55 + z^54 + z^47 + z^44 + z^43 + z^42 + z^40 + z^38 + z^37 + z^32 + z^31 + z^30 + z^25 + z^24 + z^23 + z^22 + z^21 + z^20 + z^19 + z^18 + z^16 + z^15 + z^13 + z^11 + z^8 + z^5 + z^4 + z

So, we proceed to type

F<z> := GF(2,127);
CharacteristicPolynomial(z);
g := z^121 + z^118 + z^116 + z^111 + z^110 + z^107 + z^104 + z^100 + z^99 + z^97 + z^96 + z^93 + z^92 + z^90 + z^89 + z^87 + z^83 + z^78 + z^74 + z^70 + z^66 + z^64 + z^63 + z^61 + z^58 + z^57 + z^55 + z^50 + z^49 + z^48 + z^46 + z^44 + z^39 + z^37 + z^36 + z^35 + z^34 + z^27 + z^26 + z^25 + z^24 + z^22 + z^21 + z^20 + z^19 + z^18 + z^15 + z^13 + z^12 + z^11 + z^10 + z^8 + z^7 + z^3 + z^2;
h := z^124 + z^123 + z^121 + z^118 + z^115 + z^112 + z^109 + z^108 + z^107 + z^106 + z^100 + z^99 + z^95 + z^94 + z^93 + z^92 + z^91 + z^90 + z^88 + z^84 + z^83 + z^80 + z^78 + z^75 + z^68 + z^66 + z^65 + z^63 + z^61 + z^60 + z^58 + z^57 + z^55 + z^54 + z^47 + z^44 + z^43 + z^42 + z^40 + z^38 + z^37 + z^32 + z^31 + z^30 + z^25 + z^24 + z^23 + z^22 + z^21 + z^20 + z^19 + z^18 + z^16 + z^15 + z^13 + z^11 + z^8 + z^5 + z^4 + z;
Log(g);
Log(h);

into the free online Magma calculator, which takes only a second or so and returns the following solution:

$.1^127 + $.1 + 1
40483060082070127030444832815647636291
19597093303200477157781664624163126769

With this, the rest of the challenge is easy:

from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from sage.crypto.util import carmichael_lambda

# <thx Magma>
e0 = 40483060082070127030444832815647636291
en = 19597093303200477157781664624163126769
# </thx>

sz = 2**127-1
e = Mod(en / e0, sz)
assert z0**int(e) == zn
print('69^n =', e)

n = int(e.log(Mod(69, sz)))
assert zn == z0**ZZ(pow(69, n, z0.multiplicative_order()))
print('n =', n)

while n < 2**128:
    aes = AES.new(long_to_bytes(n), AES.MODE_ECB)
    cipher = '55bd2e97c4efb27b8352ae7e4bcba2b566a9c6f645e4e59312f1945a461c71035a2396a72c3099cd39ec88d238be73992505436068f3f5a416a1bb72d59e2b74'
    print('-->', aes.decrypt(bytes.fromhex(cipher)))
    n += carmichael_lambda(sz)

This script prints the flag:

69^n = 41636555456588999509085539311953869253
n = 162438082867510830452760297714517768659
--> b'T\xe0\xe3\xc8-V\xda<@,\xd6\xc6^vLGi\xc2\x16\xbf}\x10$i\xb5VNC\xa8\xbf\x0e\xb8\x9f\xe1\x05C\xdcW\x12}\xe2\xf2\xfb{\n\x1c2o<f\x9f\xd8DbK.\tb\xd1\no\xab\xd9\xd0'
--> b'p4{C0pp3rsm1th_sur3_1s_a_c0mmon_nam3_in_th3_fie1d_afa33fe479188}'