일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- h4ckinggame
- 디지털 포렌식 트랙
- BoB 12기 최종합격 후기
- 자살론
- CodeEngn
- BoB 12기
- malware
- 코드엔진 베이직
- 논문리뷰
- codeengn basic rce 01
- bob
- CodeEngn Basic 5
- CodeEngn Basic 01
- 에밀 뒤르켐
- 철학
- 리버싱
- 사회적 사실
- 사회분업론
- Best of the Best
- 코드엔진
- 코드엔진 basic 5
- Today
- Total
woonadz :)
[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)
'IT > DreamHack' 카테고리의 다른 글
[DreamHack] palm 문제 풀이_forensic_nabi (2) | 2024.04.01 |
---|---|
[DreamHack] Batch Checker II 문제 풀이_reversing_nabi (1) | 2024.03.15 |
[DreamHack] basic_rev_9 문제 풀이_reversing_nabi (0) | 2024.03.09 |
[DreamHack] basic_rev_5 문제 풀이_reversing_nabi (0) | 2023.04.13 |
[DreamHack] basic_rev_4 문제 풀이_reversing_nabi (0) | 2023.04.05 |