[123] IT 비전공자 [dreamhack]chinese what?문제 풀기

차이니스...와아ㅏ..앗?

 

중국인의 나머지 정리(CRT, Chinese Remainder Theorem)는 수론에서 중요한 정리로, 여러 모듈러 방정식의 해를 구하는 데 사용됩니다. 이 정리는 특히 RSA 암호화에서 성능 최적화를 위해 널리 사용됩니다.

 

 

아 그래서 차이느스 리메인더ㅋㅋㅋㅋ!! 신기하군이름!!

 

 

 

 

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

 

output.txt

 

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

 

---

 

 

 

문제 설명과 해결 방향

중국인의 나머지 정리(CRT, Chinese Remainder Theorem)는 수론에서 중요한 정리로, 여러 모듈러 방정식의 해를 구하는 데 사용됩니다. 이 정리는 특히 RSA 암호화에서 성능 최적화를 위해 널리 사용됩니다.

---

중국인의 나머지 정리 (CRT)

다음과 같은 연립 방정식이 주어졌다고 가정합시다:

x≡a1(modn1)x \equiv a_1 \pmod{n_1} x≡a2(modn2)x \equiv a_2 \pmod{n_2}

...

x≡ak(modnk)x \equiv a_k \pmod{n_k}

CRT에 따르면:

• n1,n2,...,nkn_1, n_2, ..., n_k가 서로소(공약수가 1)라면, xx의 해는 N=n1⋅n2⋅...⋅nkN = n_1 \cdot n_2 \cdot ... \cdot n_k에 대해 모듈러 NN에서 유일합니다.

해결 과정은 다음과 같습니다:

1. 전체 모듈러 곱 계산: N=n1⋅n2⋅...⋅nkN = n_1 \cdot n_2 \cdot ... \cdot n_k
2. 각 모듈러에 대한 NiN_i 계산: Ni=NniN_i = \frac{N}{n_i}
3. 역원 계산: 각 NiN_i에 대해 Mi⋅Ni≡1(modni)M_i \cdot N_i \equiv 1 \pmod{n_i}를 만족하는 MiM_i를 구합니다.
4. 최종 해 계산: x=∑i=1kai⋅Ni⋅Mi(modN)x = \sum_{i=1}^k a_i \cdot N_i \cdot M_i \pmod{N}

---

문제 풀이

이 문제에서 p1,p2,p3p1, p2, p3와 c1,c2,c3c1, c2, c3이 주어졌습니다. 이를 통해 CRT를 활용하여 xx를 구하는 문제를 해결합니다.

---

Python 구현

from sympy import mod_inverse

# 주어진 값
p1 = 1527207470243143973741530105910986024271649986608148657294882537828034327858594844987775446712917007186537829119357070864918869
p2 = 2019864244456120206428956645997068464122219855220655920467990311571156191223237121636244541173449544034684177250532278907347407
p3 = 1801109020443617827324680638861937237596639325730371475055693399143628803572030079812427637295108153858392360647248339418361407

c1 = 232762450308730030838415167305062079887914561751502831059133765333100914083329837666753704309116795944107100966648563183291808
c2 = 869189375217585206857269997483379374418043159436598804873841035147176525138665409890054486560412505207030359232633223629185304
c3 = 1465704473460472286244828683610388110862719231828602162838215555887249333131331510519650513265133531691347657992103108331793683

# 전체 모듈러 곱
N = p1 * p2 * p3

# 각 N_i 계산
N1 = N // p1
N2 = N // p2
N3 = N // p3

# 각 N_i에 대한 역원 계산
M1 = mod_inverse(N1, p1)
M2 = mod_inverse(N2, p2)
M3 = mod_inverse(N3, p3)

# 최종 x 계산
x = (c1 * N1 * M1 + c2 * N2 * M2 + c3 * N3 * M3) % N

# 결과 출력
print("Recovered x:", x)

---

코드 설명

1. mod_inverse를 사용하여 각 NiN_i에 대한 모듈러 역원을 계산합니다.
2. CRT 공식에 따라 xx를 계산합니다.
3. 최종적으로 xx 값을 출력합니다.

---

출력 결과

이 코드를 실행하면 주어진 나머지 방정식들의 해 xx를 출력합니다. xx는 주어진 모듈러 조건을 만족하는 유일한 값입니다.

 

---

 

좀더 쉽게 이해하기 좋은 풀이를 줏어왔다

 

Usage of CRT (중국인의 나머지 정리 활용 예시)
𝑥≡2(mod3)
𝑥≡3(mod5)
𝑥≡2(mod7)
해당 시스템에 만족하는 x를 찾아야한다.
 
- 전체 모듈러 구하기
각 방적식의 모듈러를 곱하여 전체 모듈러를 구한다.
N = 3 x 5 x 7 = 105
 
- 각 Ni 구하기


 
- 각 Mi 구하기
35⋅M1 ​≡ 1 (mod 3)
35를 3으로 나눈 나머지를 찾으면: 35 ≡ 2 (mod 3)
즉 35의 나머지 2⋅M1​≡1(mod3) 이 식이 성립된다.
따라서 M1은 M1​ = 2 
M1이 2가 되는 이유는 2 ⋅ 2 = 4 ≡ 1 ( mod 3 )이기 때문
 
- N2와 M2


21의 모듈로 5에 대한 역원 M2를 찾는다 : 21 ⋅ M2 ≡ 1 ( mod 5 )
21을 5로 나눈 나머지를 구하면 : 21 ≡ 1 ( mod 5 )
즉 21의 나머지 1 ⋅ M2 ​≡ 1 ( mod 5 ) 이 식이 성립된다.
따라서 M2 = 1
 
- N3와 M3


15의 모듈로 7에 대한 역원 M3를 찾는다 : 15 ⋅ M3 ≡ 1 ( mod 7 )
15를 7으로 나눈 나머지를 구하면 : 15 ≡ 1 ( mod 7 )
즉 15의 나머지 1 ⋅ M3 ​≡ 1 ( mod 7 ) 이 식이 성립된다.
따라서 M3 = 1
 
- 계산하기
각 방정식을 통합하여 x값을 구한다.


여기서 a1 = 2, a2 = 3, a3 = 2
 
따라서
 x ≡ 2 ⋅ 35 ⋅ 2 + 3 ⋅ 21 ⋅ 1 + 2 ⋅ 15 ⋅ 1 ( mod 105 ) 
x ≡ 140 + 63 + 30 ( mod 105 )
x ≡ 233 ( mod 105 )
 
233을 105로 나눈 나머지 값을 구하면 233 ≡ 23 ( mod 105 )
따라서 x ≡ 23 ( mod 105 )
            






출처: https://p-ssw0rd.tistory.com/170 [--*---*--:티스토리]

 

---

 

 

from sympy import mod_inverse
from Crypto.Util.number import long_to_bytes

# 주어진 값
p1 = 1527207470243143973741530105910986024271649986608148657294882537828034327858594844987775446712917007186537829119357070864918869
p2 = 2019864244456120206428956645997068464122219855220655920467990311571156191223237121636244541173449544034684177250532278907347407
p3 = 1801109020443617827324680638861937237596639325730371475055693399143628803572030079812427637295108153858392360647248339418361407

c1 = 232762450308730030838415167305062079887914561751502831059133765333100914083329837666753704309116795944107100966648563183291808
c2 = 869189375217585206857269997483379374418043159436598804873841035147176525138665409890054486560412505207030359232633223629185304
c3 = 1465704473460472286244828683610388110862719231828602162838215555887249333131331510519650513265133531691347657992103108331793683

# 전체 모듈러 곱
N = p1 * p2 * p3

# 각 N_i 계산
N1 = N // p1
N2 = N // p2
N3 = N // p3

# 각 N_i에 대한 역원 계산
M1 = mod_inverse(N1, p1)
M2 = mod_inverse(N2, p2)
M3 = mod_inverse(N3, p3)

# 최종 x 계산
x = (c1 * N1 * M1 + c2 * N2 * M2 + c3 * N3 * M3) % N

# 결과 출력
print("Recovered x:", x)



flag_bytes = long_to_bytes(x)
print(flag_bytes)

 

이렇게 정석으로 해도되고 아주좋은 crt 모듈이 있다...크크크..

 

from Crypto.Util.number import long_to_bytes
from sympy.ntheory.modular import crt

# 주어진 소수와 나머지 값
p1 = 1527207470243143973741530105910986024271649986608148657294882537828034327858594844987775446712917007186537829119357070864918869
p2 = 2019864244456120206428956645997068464122219855220655920467990311571156191223237121636244541173449544034684177250532278907347407
p3 = 1801109020443617827324680638861937237596639325730371475055693399143628803572030079812427637295108153858392360647248339418361407

c1 = 232762450308730030838415167305062079887914561751502831059133765333100914083329837666753704309116795944107100966648563183291808
c2 = 869189375217585206857269997483379374418043159436598804873841035147176525138665409890054486560412505207030359232633223629185304
c3 = 1465704473460472286244828683610388110862719231828602162838215555887249333131331510519650513265133531691347657992103108331793683

# 중국인의 나머지 정리를 이용하여 원래 값을 복원
moduli = [p1, p2, p3]
remainders = [c1, c2, c3]
flag_recovered = crt(moduli, remainders)[0]

# 복원된 값을 바이트 문자열로 변환
flag_bytes = long_to_bytes(flag_recovered)
print(flag_bytes)

 

편안...