[Dreamhack] chinese what?

풀이

CRT (중국인의 나머지 정리, Chinese Remainder Theorem)

- 정수론에서 중요한 정리 중 하나

- 소수로 나눈 나머지 연산에서 유용하게 사용

출처 : 나무위키

제공된 문제 파일을 살펴보면 prob.py와 output.txt 파일이 있다.

prob.py는 flag를 정수로 변환하고, CRT를 적용할 수 있도록 3개의 소수와 이를 이용한 연립합동식을 생성하는 코드이다.

output.txt는 prob.py 코드의 실행결과이다.

 

위 코드를 수식으로 바꿔보면
flag = c1 (mod p1)
flag = c2 (mod p2)
flag = c3 (mod p3) 이다.

 

from sympy.ntheory.modular import solve_congruence
from Crypto.Util.number import long_to_bytes
    
def chinese_remainder_theorem(c1, c2, c3, p1, p2, p3):
    # CRT를 사용하여 주어진 나머지로부터 원래의 정수 x를 찾습니다.
    x = solve_congruence((c1, p1), (c2, p2), (c3, p3))
    return x[0]

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

# CRT를 사용하여 원래의 정수 x를 찾습니다.
result = chinese_remainder_theorem(c1, c2, c3, p1, p2, p3)
print(long_to_bytes(result))

gpt의 도움을 받아 연립합동식을 푸는 코드를 작성했다.

sympy.ntheory.modular모듈을 사용하는 코드를 작성해주었다.

이를 사용하여 flag의 interger값을 구하고 이를 다시 바이트로 변환하는 코드를 추가하였다.

 

작성한 코드를 실행하면 flag를 얻을 수 있다,. 

 

* 공부할 것

sympy.ntheory.modular모듈 - 암호학 관련해서 유용할 듯!