[DreamHack] 'chinese what?' 문제 풀이_crypto_nabi

문제

from Crypto.Util.number import bytes_to_long, getPrime


flag = bytes_to_long(b'DH{???????????????????????????????????????????????????????}')

p1 = getPrime(420)
p2 = getPrime(420)
p3 = getPrime(420)

print(f'p1 = {p1}')
print(f'p2 = {p2}')
print(f'p3 = {p3}')
print(f'c1 = {flag % p1}')
print(f'c2 = {flag % p2}')
print(f'c3 = {flag % p3}')

output

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

---

문제 풀이

 

CRT(Chinese remainder theorem) : 중국인의 나머지 정리

정수 n을 여러 정수로 나눈 나머지를 알면 '제수는 서로소' 라는 조건에서 n을 이 정수로 나눈 나머지를 고유하게 결정할 수 있다.

ex) x를 5으로 나눈 나머지가 3이고, x을 4로 나눈 나머지가 7일 때, n의 값을 알지 못해도 추측할 수 있다.

x≡3 (mod 5) ⇢ (a)

x≡4 (mod 7) ⇢ (b)

 

x≡A+B (mod 5⋅7)

 

x≡7a+5b (mod 5⋅7)

 

x≡7a1+5a2 (mod 5)≡7a+0 (mod 5)≡A

x≡7a1+5a2 (mod 7)≡0+5b (mod 7)≡B

 

7a ≡ 3, 5b ≡ 4 이므로 a와 b를 찾아야한다. 

---

모듈러 연산에서 곱셈의 역원을 찾기 위해 페르마의 소정리 또는 확장 유클리드 알고리즘이 필요하다.

if  a=2 (mod 3),   a⋅a**−1≡1 (mod 3)

---

7a≡7⋅(7**−1⋅3)≡3 (mod 5)

5b≡5⋅(5**−1⋅4)≡4 (mod 7)

 

7a=7⋅(7−1(mod 5)⋅3)=7⋅(3⋅3)=63

5b=5⋅(5−1(mod 7)⋅4)=5⋅(10⋅4)=200

 

x=A1+A2=7a+5b=63+200=263≡18 (mod 35)

 

from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime
from functools import reduce
from sympy.ntheory.modular import crt


flag = bytes_to_long(b'DH{???????????????????????????????????????????????????????}')

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):  #모듈러 역원
    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

n = [p1, p2, p3]
a = [c1, c2, c3]
Answer = chinese_remainder(n,a)
Answer = long_to_bytes(Answer)

print(Answer)