[Dreamhack] chinese what?

문제 설명

CRT는 rsa에 많이 응용되는 정리입니다.
간단한 문제를 풀어보며 CRT란 무엇인지 알아보세요.

 

Source Code

output.txt

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

 

prob.py

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}')

 

소스 코드 설명

 

- 플래그 문자열을 바이트로 바꾸고, 그 바이트를 다시 정수 형태로 표현

- 각각 420비트짜리 서로 다른 소수 p1, p2, p3를 만든다.

- 플래그 정수를 각 소수로 나눈 나머지 c1, c2, c3를 구한다

 

$c_1 = \text{flag} \pmod{p_1}$

$c_2 = \text{flag} \pmod{p_2}$

$c_3 = \text{flag} \pmod{p_3}$

 

flag를 $x$라고 하면

CRT 성질에 따라서,

\[
\begin{cases}
x \equiv c_1 \pmod{p_1} \\
x \equiv c_2 \pmod{p_2} \\
x \equiv c_3 \pmod{p_3}
\end{cases}
\]

의 해는 유일하게 존재하며, 이를 통해 $x$, 즉 flag를 복원할 수 있다.

 

 

풀이 

• p1,p2,p3는 소수이므로 모듈러가 소수가 아닌 경우를 생각할 필요가 없음

from Crypto.Util.number import long_to_bytes

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


def crt(remainders, moduli):
    assert len(remainders) == len(moduli)
    x = 0
    M = 1
    for m in moduli:
        M *= m
    for r, m in zip(remainders, moduli):
        Mi = M // m
        inv = pow(Mi, -1, m)  
        x += r * Mi * inv
    return x % M

flag_num = crt([c1, c2, c3], [p1, p2, p3])
flag = long_to_bytes(flag_num)

print(flag.decode())

 

 

풀이 코드 설명

def crt(remainders, moduli):
    assert len(remainders) == len(moduli)

• remainders와 moduli의 개수가 같은지 확인

x = 0
M = 1
for m in moduli:
    M *= m

• 초기값 설정 x=0, M=1
• 모듈러들을 곱해서 전체 모듈러 M을 만든다.
• $M = p_1p_2p_3$

 for r, m in zip(remainders, moduli):
        Mi = M // m
        inv = pow(Mi, -1, m)  #Mi의 역원을 구함
        x += r * Mi * inv

 

\[
x = \sum_{i=1}^{3} c_i \cdot M_i \cdot M_i^{-1} \pmod{M}, 
\quad M_i = \frac{M}{p_i}, 
\quad M = p_1 p_2 p_3
\]

return x % M

• %M을 해서 가장 작은 해를 리턴함