문제

소수 p,q를 얻기 위해 다음 방정식을 재배열하세요.

$N = p * q$
$c1 = (2p + 3q)^{e1}\,mod\,N$
$c2 = (5p + 7*q)^{e2}\,mod\,N$

풀이

이번 문제는 제공되는 $N, e1, e2, c1, c2$ 값을 가지고 $p, q$ 값을 구하는 문제입니다.

문제를 풀기위해 아래 개념을 알아야합니다.

$(a + b)^2\,mod\,p = a^2 + b^2\,mod\,p$

위 식은 Modular Binomal Theorem입니다.

Modular Binomal Theorem이란 Modular 값이 소수인 p거나, 소수의 곱인 합성수 $N = p * q$일때, $(a + b)^2 (mod\ p) = a^2 + b^2 (mod\ p)$를 만족한다는 정리입니다.

이 정리를 사용해서 문제를 풀 수 있습니다.

1. Modular Binomal Theorem을 이용해 식을 정리

   $c_1 ≡ 2p^{e1} + 3q^{e1}\,(mod\,N)$
   $c_2 ≡ 5p^{e2} + 7q^{e2}\,(mod\,N)$

2. 연립 합동식 풀이

   1. 지수를 맞추기 위해 $e^1, e^2$ 제곱

      ${c_1}^{e_2} \equiv 2p^{e_1e_2} + 3q^{e_1e_2}\,(mod\,N)$
      ${c_2}^{e_1} ≡ 5p^{e_1e_2} + 7q^{e_1e_2}\,(mod\,N)$

   2. 계수 맞춰주기 ($p$ 기준)

      ${c_1}^{e_2} * (5^{e_1e_2}) ≡ 10p^{e_1e_2} + 15q^{e_1e_2}\,(mod\,N)$
      ${c_2}^{e_1} * (2^{e_1e_2}) ≡ 10p^{e_1e_2} + 14q^{e_1e_2}\,(mod\,N)$

   3. $p$를 소거

      ${c_1}^{e_2} * (5^{e_1e_2}) - {c_2}^{e_1} * (2^{e_1e_2}) ≡ q^{e_1e_2}\,(mod\,N)$

   4. GCD를 이용하여 $q$값을 구하기

      $N(p * q)$과 $q$ 를 GCD 연산하면 $gcd(p * q, q)$이기 때문에 결과는 $q$가 나옵니다. 이 원리를 이용해서 $gcd(p * q,\,q^{e_1e_2})$를 계산하면 결과가 $q$가 나올 것입니다.

   5. $p$ 구하기

      $q$를 구했으니 $N$에서 $q$를 나누면 됩니다.

결과적으로 ${c_1}^{e_2} * (5^{e_1e_2}) - {c_2}^{e_1} * (2^{e_1e_2}) ≡ q^{e_1e_2}\,(mod\,N)$을 이용해서 $q$를 구하고 $p$를 구하면 됩니다.

def import_data():
    global N, e1, e2, c1, c2

    with open('data.txt', 'r') as file:
        data = file.readlines()

    N = None
    e1 = None
    e2 = None
    c1 = None
    c2 = None
    
    for line in data:
        parts = line.strip().split(' = ')
        if len(parts) == 2:
            var_name = parts[0].strip()
            var_value = int(parts[1].strip())
            if var_name == 'N':
                N = var_value
            elif var_name == 'e1':
                e1 = var_value
            elif var_name == 'e2':
                e2 = var_value
            elif var_name == 'c1':
                c1 = var_value
            elif var_name == 'c2':
                c2 = var_value

if __name__=="__main__":
    import math
    import_data()
    q_e1e2 = ((pow(c1, e2, N) * pow(5, e1*e2, N)) - (pow(c2, e1, N) * pow(2, e1*e2, N))) % N
    q = math.gcd(N, q_e1e2)
    p = N // q

    print('crypto{'+str(p) + ',' + str(q) +'}')