Rivest–Shamir–Adleman-Germain[crypto]

1. 문제 설명

rsa 암호 알고리즘을 바탕으로 생성된 값을 복호화하면 되는 문제같다.

(RSA 잘 정리된 블로그: https://gngsn.tistory.com/96)

---

2. 문제 분석

import os
from Crypto.Util.number import getPrime
from Crypto.Util.number import isPrime
from Crypto.Util.number import bytes_to_long

 

 

<소수 생성 함수: generate_primes()>

def generate_primes():
    while True:
    #512 bits 소수 p 그리고 p를 기반으로 q,r,s 생성
        p = getPrime(512), 
        q = (2*p) + 1
        r = (2*q) + 1
        s = (2*r) + 1

		#q, r, s가 모두 소수이면 while 무한루프 종료
        if isPrime(q) and isPrime(r) and isPrime(s): 
            break
            
    #p,q,r,s 값 반환
    return (p, q, r, s)

getPrime() 함수는 소수를 구하는 함수이고, isPrime() 함수는 소수인지 판별하는 함수이다.

소인수분해 문제가 어렵다는 사실에 기반한 RSA 암호화 알고리즘은, 키를 알아내기 어렵게 하기 위해 큰 소수가 필요하다. 이 함수를 통해 큰 수의 소수를 얻을 수 있다.

 

현재 512 bits의 소수를 만들고 있는데, 이 부분에서 해당 rsa 암호화 알고리즘이 깨질 수 있는 것을 알 수 있다. 현재 컴퓨팅 파워로 1024 bits 이하의 소수는 예측이 가능하기 때문이다.

 

 

<메인 함수>

def main() -> int:
	#gernerate_primes() 함수를 호출해 p,q,r,s를 생성
    #p,q,r,s를 이용해 개인키의 일부인 N을 생성
    (p, q, r, s) = generate_primes()
    N = p * q * r * s
    e = 0x10001 

    with open("flag.txt", "r") as flag_file:
    
    #read()를 통해 파일의 내용을 읽어오고, strip()을 사용해 양쪽 끝 공백을 제거한다
        flag = flag_file.read().strip()
	
	#pow() 제곱근 함수를 사용해 암호문 CT를 계산한다.
    CT = pow(bytes_to_long(flag.encode()), e, N)

    print(f"{N = }")
    print(f"{CT = }")

e-> 16진수: 0x10001, 10진수: 65537, 8진수: 20001, 2진수: 10000000000000001

---

3. 문제 풀이

<시도 1>

output.txt 파일에 N값과 CT(암호문)값이 주어져있다. 

N = 489654925303072532553659432557377999607856370197579144782976005904927235244321459117898721690940319487769632950077647476152880207627385231603017537961906244964117707813500615680799967895028255666319186794462243666159201392490299439947399915406223652423977002396844720487588735149486903743362109592536081726574342051928022071576485169655694281378301551060632699138055044915993078059902577590451519251321215765308977494770310317350866241246677761542212605478044672014913289740381478940929584556588858045439572693806615268502627912952686133840081188641597461343817750411035667135310831687533531094008308185320371643348451
CT = 58535947031303233853656030097871859886777764034955095086618901763996192727846608049414977429851683454541344096765319691912454768331685486037922533236779909508856486986528041125267338846421238077083738092020495236946742989769815669001100361743526446503248639704900983287986142636083524250650662602975802778548032518674346903013262799229594298599457623347987250272218522320743415393958131916181915804368140008312975210397791293701839101635851486434802271100141743496402698229558250485987421664294229816166263965806962242894230766553316312608696594536239328785792283453559549564751529321240567418095487324718881437825650

 

1. 충분히 큰 소수  p와 q 설정

현재 p와 q는 알지 못한다.

 

2. N 구하기

현재 N의 값이 주어져있고, p가 512bits이기 때문에 p를 구할 수 있다.

 

from sympy import isprime

def factorize_n(n):
    # 512비트 소수의 범위 계산
    min_p = 2**511
    max_p = 2**512 - 1

    # 512비트 범위 내에서 소수 `p` 찾기
    for p in range(min_p, max_p + 1):
        if n % p == 0:  # `p`가 `N`의 인수라면
            q = n // p  # `q` 계산
            if isprime(q):  # `q`가 소수인지 확인
                return p, q
    return None, None  # 실패 시 반환

# 주어진 `N` 값
N = 489654925303072532553659432557377999607856370197579144782976005904927235244321459117898721690940319487769632950077647476152880207627385231603017537961906244964117707813500615680799967895028255666319186794462243666159201392490299439947399915406223652423977002396844720487588735149486903743362109592536081726574342051928022071576485169655694281378301551060632699138055044915993078059902577590451519251321215765308977494770310317350866241246677761542212605478044672014913289740381478940929584556588858045439572693806615268502627912952686133840081188641597461343817750411035667135310831687533531094008308185320371643348451

# 소인수분해 실행
p, q = factorize_n(N)

if p and q:
    print(f"p = {p}")
    print(f"q = {q}")
else:
    print("소인수분해 실패")

-> 파이썬 코드를 작성해 p값을 구하려 했는데, N값이 너무 커서 생각 이상으로 시간이 너무 오래걸린다...3시간 이상 코드를 돌렸지만 값이 나오지 않아 다른 코드를 찾아보기로 했다.

 

 

 

 

<시도 2-write up 참고>

(참고한 라이트업: https://johan6337.github.io/posts/write-up-glacierctf-2024/)

N의 값이 주어졌으니, p를 알수 있는 상황이다. 그리고 아마 암호문을 복호화하면 flag가 나올것이다.참고한 라이트업에서는 sage를 사용해 문제를 풀이했는데, 나는 다른 파이썬 모듈로 sage를 대체해서 코드를 변경했다.

SageMath
SageMath 또는 Sage는 컴퓨터용 수학 소프트웨어 중 하나이다. 다양한 기능이 구현되어 있고, Python 위에서 동작하도록 구현된 소프트웨어이며 자체적인 문법이 Python과 유사하여 쉽게 사용 가능하다.

from sympy import symbols, Eq, solve
from Crypto.Util.number import inverse, long_to_bytes

N = 489654925303072532553659432557377999607856370197579144782976005904927235244321459117898721690940319487769632950077647476152880207627385231603017537961906244964117707813500615680799967895028255666319186794462243666159201392490299439947399915406223652423977002396844720487588735149486903743362109592536081726574342051928022071576485169655694281378301551060632699138055044915993078059902577590451519251321215765308977494770310317350866241246677761542212605478044672014913289740381478940929584556588858045439572693806615268502627912952686133840081188641597461343817750411035667135310831687533531094008308185320371643348451
CT = 58535947031303233853656030097871859886777764034955095086618901763996192727846608049414977429851683454541344096765319691912454768331685486037922533236779909508856486986528041125267338846421238077083738092020495236946742989769815669001100361743526446503248639704900983287986142636083524250650662602975802778548032518674346903013262799229594298599457623347987250272218522320743415393958131916181915804368140008312975210397791293701839101635851486434802271100141743496402698229558250485987421664294229816166263965806962242894230766553316312608696594536239328785792283453559549564751529321240567418095487324718881437825650

# 변수 정의. sympy 라이브러리에서 사용되는 함수를 사용하여 변수 x를 정의한다.
x = symbols('x')

# 다항식 정의. f가 0이 되는 값을 찾는것이 목표이다. 즉 x(=p)를 찾는 부분이다.
f = x * (2 * x + 1) * (2 * (2 * x + 1) + 1) * (2 * (2 * (2 * x + 1) + 1) + 1) - N

# 근 구하기
roots = solve(Eq(f, 0), x) #Eq(f,0)=f가 0인 경우. 즉 f가 0이 되는 x를 찾는다.
p = int(roots[0]) #정수로 형변환

phi = (p - 1) * 2 * p * 2 * (2 * p + 1) * 2 * (2 * (2 * p + 1) + 1)

# 공개키 & 비밀키 계산
e = 0x10001 #문제에서 주어짐
d = inverse(e, phi) #e와 phi값을 가지고 비밀키를 계산한다.

# 복호화
PT = pow(CT, d, N)
print(long_to_bytes(int(PT)))

gctf{54dly_50ph13_63rm41n_pr1m35_wh3r3_n07_u53d_53curly}