[드림핵] AbCD

ShinboTinBBO·2025년 1월 25일

드림핵 암호학

cryptography

목록 보기

5/10

문제 설명을 보고, 도대체 어떤 말을 하고 싶으셨던 걸까 정말 궁금해서 풀게 된 문제...

아직도 궁금하다

친구들한테 더 효율적인 풀이가 있을까해서 정리해서 사진을 보내줬는데, 분야가 겹치는 친구들이 없어서... 묵묵부답이다

코드 분석

from random import randint
import gmpy2
from Crypto.Util.number import bytes_to_long

def generate(p_bits=768, q_bits=768, rho_bits=30, num=2):
    p = gmpy2.next_prime(randint(2**(p_bits-1), 2**p_bits))
    
    q0 = gmpy2.next_prime(randint(2**(q_bits-1), 2**q_bits))
    N = p * q0
    
    samples = []
    r = []
    
    for _ in range(num):
        qi = randint(2**(q_bits-1), 2**q_bits)
        ri = randint(-2**(rho_bits-1), 2**(rho_bits-1))
        ai = p * qi + ri
        samples.append(ai)
        r.append(ri)
    
    return N, p, samples, r

p, q는 각각 768bits의 엄청 큰 소수이다.
이들을 곱해서 N을 만드는 것으로 보아 아주 전형적인 RSA의 공개키 생성 방식임을 알 수 있다.
generate 함수는 총 네개의 반환 값을 가진다.

N : p와 q0의 곱
p : 바꾸지 않는소수
samples : q를 계속 바꿔가면서 생성되는 값, p와 곱하고 랜덤값을 더해줌
ri : 매 라운드의 랜덤값

generate 함수의 파라미터로 num=2가 디폴트로 설정되어 있으므로 samples, ri 리스트의 길이는 2이다.

def main():
    FLAG = bytes_to_long(open('flag', 'rb').read())
    e = 65537

    N, p, samples, r_values = generate()
    
    print(f"N = {hex(N)}")
    while True:
        print("Menu:")
        print("1. Get another N")
        print("2. Get flag")
        print("3. Exit")
        inp = int(input(">"))
        if inp==1:
            print("I'll give you another N generated with same p")
            for sample in samples:
                print(hex(sample))
        if inp==2:
            print("Encrypted flag:")
            print(hex(pow(FLAG, e, N)))
        if inp==3:
            break
            

if __name__ == "__main__":
    main()

서버를 통해서 기존 N, p*q1+r1, p*q2+r2를 확인할 수 있다.
r1, r2가 더해져 있는 것은 이것이 안 더해져 있으면 세 수가 모드 p의 배수가 된다는 점을 없애기 위한 것인 것 같다.

e로 암호화 되어 있는 flag를 복호화 하면 된다.

생각 정리

궁극적인 목표는 암호화된 flag를 복원하는 것이므로 아래와 같은 큰 세개의 목표 중 하나를 이뤄내면 답을 구할 수 있다.

RSA의 개인 키 d를 구하면 된다.
d를 구하기 위해서는 phi(n) = (p-1)*(q-1)를 구해서 역원을 구하면 된다.
p나 q를 구한다.

문제 정리

$p, q, q_1, q_2$ 는 모두 $2^{767}$ 보다 크고 $2^{768}$ 보다 작은 정수이다.
$p, q$ 는 소수이다.
$r_1, r_2$ 는 절댓값이 $2^{29}$ 보다 작은 정수이다.

아래와 같이 세 개의 값이 주어졌을 때, $N_0$ 를 소인수분해 하는 방법은?

$N_0 = p \times q$
$N_1 = p \times q_1 + r_1$
$N_2 = p \times q_2 + r_2$

이러한 문제로 환원하여 볼 수 있다고 생각했다.
또한, 문제에서 1, 2 옵션을 이용하여 고정된 N, p에 대한 값을 구할 수 있으므로 이를 저장해 놓으면 서버가 닫히는 시간에 압박 받지 않고 문제 풀이를 할 수 있다.

풀이

r1, r2만 N1, N2로부터 제외시킬 수 있다면 아무거나 gcd(N0, N1) 연산으로 빠르게 p를 구할 수 있다고 생각했다.

분명 간단한 계산을 통해서 r1, r2을 제외시킬 수 있을 것이라고 생각해서 여러 방향으로 고민해보았는데 결론이 나지 않았다.

그래서 그냥 samples의 첫 원소인 N1에 대해서 2**(q_bits-1), 2**q_bits 범위를 전수 조사기로 했다.

for r in trange(-2**(random_bits-1), 2**(random_bits-1)):
    temp = math.gcd(N1-r, N0)
    if(temp == 1):
        continue
    if(temp == N0):
        continue
    if(N0%temp == 0):
        real_p = temp
        break