[Dream Hack - Crypto] ICM2022

풀이 과정

1. enc 함수에서 q 값은 다음과 같은 식을 만족한다.

2. n = 3, key2 = 95 일때, q = -200640142664324295933714 을 만족하는 p, key1 을 구하자!

3. key1 < key2 이므로 0 ≤ key1 < 95 이고, 임의의 key1 값에 대한 p 값을 확인하여 flag를 추론하자!!

4. p 값을 확인하는 dec 함수는 다음과 같은 식을 만족한다.

 

5. dec 를 통해 p 를 구하고, enc 에 p 를 대입하여 q_test 구한 후 기존 p 값과 비교한다.

 

풀이 코드

import random
from fractions import Fraction

# 주어진 값 p를 n, key1, key2를 사용하여 암호화하는 함수
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

# 암호화된 결과 q를 복호화하는 함수 (코드 내용이 누락되어 있음)
def dec(q, n, key1, key2):
    temp = key1**(n+1) - key2**(n+1)
    p = int((n+1) * q / temp)
    print("[OK] cipher is decrypted : ", p)
    return p

# n, key1, key2를 랜덤하게 생성
n, key2 = 3, 95
q = -200640142664324295933714

# 브루트 포스로 의미 있는 문자열이 나올 때까지 실항을 시켜보자!!
for key in range(0,95) :
    p = dec(q, n, key, key2)
    print("key : ", key)
    q_test = enc(p, n, key, key2)
    if q_test == q :
        print("p : ", p)
        print("YEAH!!!!! here!!!!!")
        break

 

실행 결과

flag는 DH{10112210997116104} 이다. 아스키 코드를 변환해보니 ezmath라고 한다!!ㅎㅎ