[EasyCTF] Diffie-Cult (디피-헬만 문제)

디피-헬만 문제입니다.

최근했던 CTF에 이와 같은 문제가 나와서 비슷한 유형의 다른 CTF 문제를 가져와 풀어보겠습니다.

I just intercepted some odd messages.txt. It appears to be a Diffie-hellman protocol, but my math isn't good enough to figure out what the final shared key is. Help! g^a mod p = 421049228295820 g^b mod p = 105262307073955 p = 442101689710611

디피-헬만(Diffie–Hellman)에서의 키교환 문제이다. 문제에서 flag값은 비밀키인 g^(ab) mod p 의 값이다.

g값도 안주어진다는 점에서 꽤 어려워보이는 문제이나. p값이 작아 소인수분해가 되기 때문에 이를 이용하여 문제를 풀 수 잇다.

factorDB에서 소인수분해를 해서 가져와보았다.

A = g^a mod p = 421049228295820 = 2^2 * 5 * 17 * 19^3 * 37 * 47^4  B = g^b mod p = 105262307073955 = 5 * 17 * 19^3 * 37 * 47^4 p = 442101689710611 = 3 * 7 * 17 * 19^3 * 37 * 47^4

A와 B와 p가 공약수를 가지는 것을 알 수 있습니다. 

공약수는 k = 17 * 19^3 * 37 · 47^4 와 같습니다.

그렇다면 이제 아래와 같이 나타낼 수 있습니다.

k = 17 * 19^3 * 37 * 47^4 g^a mod p = 421049228295820 = 2^2 * 5 * k = 20k g^b mod p = 105262307073955 = 5 * k = 5k p = 442101689710611 = 3 * 7 * k = 21k

g^a mod 21k = 20k = -k [since 20k mod 21k = -k] ==> (g^a)^b mod 21k = (-k)^b ==> g^(ab) mod p = (-k)^b [since p = 21k]

자... 이제 단순화되었으니 g^ab가 될 후보들은 구하면...

(-k)^1 mod p = 421049228295820 (-k)^2 mod p = 42104922829582 (-k)^3 mod p = 357891844051447 (-k)^4 mod p = 168419691318328 (-k)^5 mod p = 105262307073955 (-k)^6 mod p = 231577075562701 (-k)^7 mod p = 421049228295820  [ same as -k ^ 1 ] ...

위와 같이 사이클이 반복됨을 알 수 있습니다. 즉 6개의 값들중 하나가 비밀키입니다.

여기선 421049228295820이 비밀키였습니다.

*같은 유형의 다른문제

p : 739626899866411020995105608928036598669313466029070991080755558690

g^a mod p : 711179711410010597110678470123112114105109101951029799116111114125

g^b mod p : 256024696107603814959844249244320361077839276702370727681800001085

p = 2 * 5 * 13 * 1804529 * 6726547 * 468719798853001437040762632814600786193829912273851

A =  5^3 * 1804529 * 6726547 * 468719798853001437040762632814600786193829912273851

B = 3^2 * 5 * 1804529 * 6726547 * 468719798853001437040762632814600786193829912273851

k = 5  *  1804529 * 6726547 * 468719798853001437040762632814600786193829912273851

p = 26k

A= 25k

B = 9k

(g^a) mod 26k = 25k  = -k mod 26k

(g^a)^b = A^b = mod 26k = (-k)^b mod 26k

CTF{711179711410010597110678470123112114105109101951029799116111114125}