[dreamhack] ICM2022

 

 

문제를 다운 받으면 다음과 같이 두개의 파일이 있는데

 

 

이때 readme.txt 를 먼저 읽어줄게여

뭔가 변수값들을 주고 있는것 같으니 main.py 파일을 한번 살펴보겠습니다

 

 

import random
from fractions import Fraction


def enc(p, n, key1, key2):
    q = (Fraction(p, n+1)*key1**(n+1)) - (Fraction(p, n+1)*key2**(n+1))
    print("[OK] plain is encrypted : ", q)
    return q


def dec(q):
    # cencored


def key_make():
    n, key1, key2 = 0, 1, 0
    while key2 < key1:
        n = random.randrange(1, 10)
        key1 = random.randrange(1, 100)
        key2 = random.randrange(1, 100)
    return n, key1, key2


p = ""
emp = input("plain text: ")
for character in emp:
    p += str(ord(character))
n, key1, key2 = key_make()

print(f"[WAR]p = {p} n = {n} key1 = {key1} key2 = {key2}")

q = enc(int(p), n, key1, key2)
dec(q)

 

요렇게 q를 계산(암호화, encrypt)하는 enc() 함수가 존재하고 얘를 다시 복호화 하는 함수 dec() 는 역시나 주어지지 않앗네용!! (당연함. 왜냐면 우리가 알아내야하기 때문)

 

자 그러면 q를 만드는 계산 과정을 한번 살펴보겠습니다.

p = ""

emp = input("plain text: ")

for character in emp:      

p += str(ord(character))        -------------------------------(1)

n, key1, key2 = key_make()      -----------------------------(2)

 

print(f"[WAR]p = {p} n = {n} key1 = {key1} key2 = {key2}")

q = enc(int(p), n, key1, key2)    ----------------------------(3)

dec(q)    --------------------------------------------------(4)

 

(1) p는 plaintext로 사용자에게 입력받는 값인걸 알 수 있습니다

(2) n, key1, key2의 값은 key_make() 라는 함수를 통해 만드는 것을 알 수 있습니다.

(3) q를 만든 함수 enc()입니다.

(4) q를 dec() 하게 된다면 p 값이 나오겠죠?! -> 플래그값!!

 

 

그럼 key_make() 함수를 보겠습니다!!

def key_make():

    n, key1, key2 = 0, 1, 0

    while key2 < key1:     ----------------------------------(1)

        n = random.randrange(1, 10)

        key1 = random.randrange(1, 100)

        key2 = random.randrange(1, 100)

    return n, key1, key2   ----------------------------------(2) 

 

(1) 만약 key2가 key1보다 작다면 계속 밑의 랜덤 함수를 작동시켜 무조건 key2가 key1보다 커야지만 반복문이 중단되는 것을 알 수 있습니다.

(2) key2가 key1보다 큰 상태에서 나온 값을 리턴합니다.

 

--> 여기서 key2가 95라는 값을 알았으니 key1은 1~94의 값을 가질 수 있다는 것을 알 수 있습니다!!

 

 

그럼 이제 enc() 함수를 보도록 합시다!!

 

def enc(p, n, key1, key2):

q = (Fraction(p, n+1)*key1**(n+1)) - (Fraction(p, n+1)*key2**(n+1))  ------------(1)

print("[OK] plain is encrypted : ", q)

return q

 

(1) 이 부분이 이제 q의 계산인데, 이 식에서 p값을 구하려면 아래와 같이 계산하면 됩니다

key1이랑 key2는 그냥 k1,k2라고 했습니다...

이때 p = Fraction(4q, (k1**4) - (k2**4)) 이므로 이 식을 활용하여 복호화 함수를 만들면 될 것 같네요!!

 

but, k1을 모르지만 어쨌든 1~94 사이의 숫자이기 때문에 k1을 bruteforce로 구해서 하면 될 것 같습니다.

 

저는 아래와 같이 파이썬 코드를 만들어서 p 의 값을 구했습니다.

from fractions import Fraction

n = 3
k2 = 95
q = -200640142664324295933714
k1 = 0

for k1 in range(1, 96):
    up = 4*q
    down = ((k1**4) - (k2**4))
    p = Fraction(up,down)
    if up % down == 0:
        print("")
        print("wow!")
        print("k1: " + str(k1))
        print("p: " + str(p))
        break
    else:
        print(str(k1) + "   Nope...")
        k1 += 1
        continue

 

 

그러면 다음과 같은 결과가 나옵니다!!

 

1   Nope...
2   Nope...
3   Nope...
4   Nope...
5   Nope...
6   Nope...
7   Nope...
8   Nope...
9   Nope...
10   Nope...
11   Nope...
12   Nope...
13   Nope...
14   Nope...
15   Nope...
16   Nope...
17   Nope...
18   Nope...
19   Nope...
20   Nope...
21   Nope...
22   Nope...
23   Nope...
24   Nope...
25   Nope...
26   Nope...
27   Nope...
28   Nope...
29   Nope...
30   Nope...
31   Nope...
32   Nope...
33   Nope...
34   Nope...
35   Nope...
36   Nope...
37   Nope...

wow!
k1: 38
p: 10112210997116104

 

 

굳 ^^