[Blitzs CTF] d + 파이썬 itertools!!

문제 설명.. 당황1

문제 코드... 당황2

- 플래그(byte)를 long으로 바꾼 후 prime인지 확인

- q에 256bit 크기의 랜덤한 prime 넣음

- φ(n) = (p-1)(q-1)  /  e = 65537  /  d = 228001~~~20490241918976205665073 인 RSA 암호화 같다

 

푸는 방향은

d * e ≡ 1 (mod φ(n))   ☞  d * e ≡ 1 (mod (p-1)(q-1))   ☞  d*e-1 ≡  0 (mod (p-1))   ☞   d*e-1 = k (p-1) 형태

d와 e를 알기 때문에 d*e-1 의 약수들을 잘 살펴보면 p-1 구할 수 있겠다!

 

- 무작정 브포 돌리면 케이스 너무 많기 때문에

https://www.alpertron.com.ar/ECM.HTM

이런 곳에서 먼저 num=d*e-1를 소인수분해해 약수 구한 다음에 브포 돌리자 (약수 13개 = 브포 2^13(8192)번)

 

exploit 코드는

from Cryptodome.Util.number import *
from itertools import product

d = 22800184635336356769510601710348610828272762269559262549105379768650621669527077640437441133467920490241918976205665073
e = 65537
num = d*e-1

num_factors = [2, 2, 2, 2, 3, 5, 5, 37, 1117, 4029461, 1403014978139, 284368748316481195117, 18741210882440665187461519398960291465361283084482741278982029639876282810203]

for exp in product([0,1], repeat=len(num_factors)):
    p = 1
    for i in range(len(num_factors)):
        p *= (num_factors[i] ** exp[i])
    p += 1
    # DH{} 에서 '}'로 끝나므로
    if p%256==125:
        print(long_to_bytes(p))

이렇게 수많은 문자열들 속에서 DH{ } 형태의 플래그를 찾을 수 있다

 

파이썬 itertools 라이브러리

- 효율적인 looping을 위한 iterator를 만드는 함수

- 조합, 순열, 데카르트곱 등을 쉽게 계산할 수 있다 // crypto나 algorithm 문제 풀 때 도움될 듯

combinations(iterable, rounds)

lst = [1,2,3,4]
for i in combinations(lst, r=3):
    print(i)

조합

combinations_with_replacement(iterable, r)

lst = [1,2,3,4]
for i in combinations(lst, r=3):
    print(i)

중복조합 (이하 생략)

permutations(iterable, r)

lst = [1,2,3,4]
for i in permutations(lst, 2):
    print(i)

순열, 순서 고려 o

product(* iterables, repeat=1)

lst1 = [0,1]
lst2 = [2,3]
for i in product(lst1, repeat=3):
    print(i)

lst1 = [0,1]
lst2 = [2,3]
lst3 = [4,5]
for i in product(lst1, lst2, lst3, repeat=1):
    print(i)

iterables 여러개 넣을 때는 주로 repeat=1 하겠지?

데카르트 곱이 가장 유용하게 쓰일 것 같긴하다