[Dream Hack - Crypto] chinese what?

풀이 과정

1. M 계산: M은 모든 pi (여기서는 p1, p2, p3) 값을 곱한 값입니다. M = p1 * p2 * p3
2. mi 계산: mi는 M을 해당 소수 pi로 나눈 몫입니다. m1 = M // p1,  m2 = M // p2,  m3 = M // p3
3. 역원 계산: mi의 역원 yi는 mi를 모듈로 pi로 나눈 나머지와 곱했을 때 1이 되는 값입니다. 역원은 모듈로 연산에서 나눗셈의 역할을 합니다. 역원은 확장된 유클리드 알고리즘 등을 사용하여 계산할 수 있습니다.
4. 복원: 이제 역원과 mi 값을 사용하여 flag 값을 복원합니다. flag = (c1 * y1 * m1 + c2 * y2 * m2 + c3 * y3 * m3) % M

 

풀이 코드

from Crypto.Util.number import long_to_bytes

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

def modInverse(a, m):
    m0 = m
    y = 0
    x = 1
    if (m == 1):
        return 0
    while (a > 1):
        q = a // m
        t = m
        
        m = a % m
        a = t
        t = y
        
        y = x - q * y
        x = t
    if (x < 0):
        x = x + m0
    return x

M = p1 * p2 * p3

m1 = M // p1
m2 = M // p2
m3 = M // p3

y1 = modInverse(m1, p1)
y2 = modInverse(m2, p2)
y3 = modInverse(m3, p3)

flag = (c1*y1*m1 + c2*y2*m2 + c3*y3*m3) % M
print(long_to_bytes(flag))

 

실행 결과