[Crypto] chinese what?

문제 링크

드림핵

풀이

주어진 것들을 먼저 정리해 보자.

p1 = 1527207470243143973741530105910986024271649986608148657294882537828034327858594844987775446712917007186537829119357070864918869
p2 = 2019864244456120206428956645997068464122219855220655920467990311571156191223237121636244541173449544034684177250532278907347407
p3 = 1801109020443617827324680638861937237596639325730371475055693399143628803572030079812427637295108153858392360647248339418361407
c1 = 232762450308730030838415167305062079887914561751502831059133765333100914083329837666753704309116795944107100966648563183291808
c2 = 869189375217585206857269997483379374418043159436598804873841035147176525138665409890054486560412505207030359232633223629185304
c3 = 1465704473460472286244828683610388110862719231828602162838215555887249333131331510519650513265133531691347657992103108331793683

flag = c1 (mod p1)
flag = c2 (mod p2)
flag = c3 (mod p3)

문제 이름에서 유추할 수 있듯이, 중국인의 나머지 정리(Chinese Remainder Theorem, CRT)를 이용하면 되는 문제이다.

먼저, CRT에 대해 먼저 알아보자. 나는 정수론 과목과 현대암호기초 과목에서 배웠었다.

나무위키 설명

n1, n2, ... ni가 쌍 마다 서로소이면, 다음 연립 합동식

x = a1 (mod n1)
x = a2 (mod n2)
x = a3 (mod n3)

은 n1, n2, ... n3에 대해 유일한 해를 갖는다.

$x\ =\ \sum _{i=1}^kni\cdot Mi\cdot Ni$

위 식을 이용하면 x값, 즉 flag를 알아낼 수 있다.

n값은 주어진 p값, N값은 주어진 모든 p값의 곱에서 p값을 나눠주면 되므로 p1의 경우 p2*p3 식이다.

ni와 Ni는 주어져 있는 값으로 쉽게 구할 수 있다.

다만, Mi를 구하기 위해서는 모듈러 역연산이 필요하다.

$Mi\cdot Ni\ =\ 1\ \left(mod\ ni\right)$Mi·Ni = 1 (mod ni)

이기에 곱셈의 역원을 구해줘야 한다.

M까지 구해준 후 대입해주면 flag 값을 구할 수 있다.

from functools import reduce
from Crypto.Util.number import long_to_bytes


p1 = 1527207470243143973741530105910986024271649986608148657294882537828034327858594844987775446712917007186537829119357070864918869
p2 = 2019864244456120206428956645997068464122219855220655920467990311571156191223237121636244541173449544034684177250532278907347407
p3 = 1801109020443617827324680638861937237596639325730371475055693399143628803572030079812427637295108153858392360647248339418361407
c1 = 232762450308730030838415167305062079887914561751502831059133765333100914083329837666753704309116795944107100966648563183291808
c2 = 869189375217585206857269997483379374418043159436598804873841035147176525138665409890054486560412505207030359232633223629185304
c3 = 1465704473460472286244828683610388110862719231828602162838215555887249333131331510519650513265133531691347657992103108331793683


def chinese_remainder(n, a):
    sum = 0
    prod = reduce(lambda a, b: a * b, n)  # n 값 모두 곱하기
    for n_i, a_i in zip(n, a):
        p = prod // n_i  # bar n_i
        sum += a_i * mul_inv(p, n_i) * p
    return sum % prod


def mul_inv(a, b):  # Modular inverse
    b0 = b
    x0, x1 = 0, 1
    if b == 1:
        return 1
    while a > 1:
        q = a // b
        a, b = b, a % b
        x0, x1 = x1 - q * x0, x0
    if x1 < 0:
        x1 += b0
    return x1


if __name__ == "__main__":
    n = [p1,p2,p3]
    a = [c1,c2,c3]
    flag=chinese_remainder(n, a)
    original_flag = long_to_bytes(flag)
    print(f'Original flag : {original_flag}')

lag 값이 처음에 bytes_to_long 된 값이기 때문에 반대로 long_to_bytes 해주면 원래 형태의 flag를 얻을 수 있다.