Packed(Rev)

• DIE로 확인 결과, 패킹 정보 확인 가능
• UPX로 언패킹
• 이후 IDA로 탐색 진행했으나 단서 확인 불가
• 시간을 너무 썼다...

reiwa_rot13(Crypto)

chall.py

from Crypto.Util.number import *
import codecs
import string
import random
import hashlib
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from flag import flag

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q
e = 137

key = ''.join(random.sample(string.ascii_lowercase, 10))
rot13_key = codecs.encode(key, 'rot13')

key = key.encode()
rot13_key = rot13_key.encode()

print("n =", n)
print("e =", e)
print("c1 =", pow(bytes_to_long(key), e, n))
print("c2 =", pow(bytes_to_long(rot13_key), e, n))

key = hashlib.sha256(key).digest()
cipher = AES.new(key, AES.MODE_ECB)
print("encyprted_flag = ", cipher.encrypt(flag))

Output.txt

n = 105270965659728963158005445847489568338624133794432049687688451306125971661031124713900002127418051522303660944175125387034394970179832138699578691141567745433869339567075081508781037210053642143165403433797282755555668756795483577896703080883972479419729546081868838801222887486792028810888791562604036658927
e = 137
c1 = 16725879353360743225730316963034204726319861040005120594887234855326369831320755783193769090051590949825166249781272646922803585636193915974651774390260491016720214140633640783231543045598365485211028668510203305809438787364463227009966174262553328694926283315238194084123468757122106412580182773221207234679
c2 = 54707765286024193032187360617061494734604811486186903189763791054142827180860557148652470696909890077875431762633703093692649645204708548602818564932535214931099060428833400560189627416590019522535730804324469881327808667775412214400027813470331712844449900828912439270590227229668374597433444897899112329233
encyprted_flag =  b"\xdb'\x0bL\x0f\xca\x16\xf5\x17>\xad\xfc\xe2\x10$(DVsDS~\xd3v\xe2\x86T\xb1{xL\xe53s\x90\x14\xfd\xe7\xdb\xddf\x1fx\xa3\xfc3\xcb\xb5~\x01\x9c\x91w\xa6\x03\x80&\xdb\x19xu\xedh\xe4"

---

Analysis

• RSA 암호화

  • 제공된 c1과 c2는 각각 key와 rot13_key를 RSA로 암호화한 값
  • n은 두 개의 강력한 소수 p,qp, qp,q의 곱으로 생성됨
  • e는 137로 주어짐

• ROT13

  • rot13_key는 key를 ROT13으로 변환한 값
  • ROT13은 알파벳 문자들을 13글자씩 순환시키는 간단한 대칭 암호

• AES 암호화

  • key를 SHA-256으로 해싱한 값을 AES의 키로 사용함
  • AES.MODE_ECB를 사용하여 플래그를 암호화함

• 목표

  • c1, c2, n, e를 활용하여 원본 key를 복구
  • 복구한 key를 통해 플래그를 복호화

chall.py 분석

모듈 임포트

from Crypto.Util.number import *  # 숫자 관련 유틸리티 (RSA 암호화, 바이트 변환 등)
import codecs  # 문자열 변환 (ROT13)
import string  # 알파벳 문자열 처리
import random  # 랜덤 값 생성
import hashlib  # 해싱 함수 (SHA-256)
from Crypto.Cipher import AES  # AES 암호화
from Crypto.Random import get_random_bytes  # 랜덤 바이트 생성
from flag import flag  # 플래그를 포함한 외부 파일

• Crypto.Util.number: RSA 암호화와 관련된 숫자 변환 유틸리티를 제공
• codecs: 문자열을 특정 변환(예: ROT13)으로 처리하는 모듈
• string: 알파벳 문자열을 처리하기 위해 사용
• random: 랜덤 문자열이나 값 생성을 위해 사용
• hashlib: 암호학적 해싱 함수 (SHA-256)를 제공
• Crypto.Cipher.AES: AES 암호화를 구현
• flag: 문제의 플래그가 정의된 외부 파일

RSA 파라미터 생성

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p * q
e = 137

• getStrongPrime(512)

  • 크기가 512비트인 강한 소수 p와 q를 생성
  • 강한 소수는 소인수분해 공격에 강한 특성을 가짐

• n = p * q

  • 두 소수 p와 q의 곱으로 RSA 모듈러 n을 생성
  • 이는 공개키의 핵심 구성 요소

• e = 137

  • 공개 지수 e로, 137이라는 값이 고정
  • 이 값은 e와 $ϕ(n)$이 서로소 관계($gcd(e,ϕ(n))=1$)임을 보장

랜덤 키 생성 및 ROT13 변환

key = ''.join(random.sample(string.ascii_lowercase, 10))
rot13_key = codecs.encode(key, 'rot13')

• key

  • 길이가 10인 랜덤 소문자 문자열을 생성
  • 이는 AES 암호화 키로 사용
  • 예: key = "abcdefghij"

• rot13_key

  • 생성된 key에 ROT13 변환을 적용한 값
  • ROT13은 알파벳을 13자리 순환하는 간단한 대칭 암호
  • 예: key = "abcdefghij" → rot13_key = "nopqrstuvw"

키를 바이트로 변환

key = key.encode()
rot13_key = rot13_key.encode()

• 문자열 형태의 key와 rot13_key를 바이트 문자열로 변환
• 이는 RSA 암호화 및 해싱에 사용

RSA 암호화

print("n =", n)
print("e =", e)
print("c1 =", pow(bytes_to_long(key), e, n))
print("c2 =", pow(bytes_to_long(rot13_key), e, n))

• bytes_to_long

  • 바이트 문자열(key, rot13_key)을 정수로 변환
  • RSA 암호화는 정수 연산을 기반으로 작동하기 때문

• pow(m, e, n)

  • RSA 암호화 공식: $c=m^e mod n$
  • key와 rot13_key를 각각 공개키 n,e 로 암호화한 결과를 출력
  • c1: key를 암호화한 결과
  • c2: rot13_key를 암호화한 결과

SHA-256 해시를 통한 AES 키 생성

key = hashlib.sha256(key).digest()

• RSA 암호화에 사용된 원본 key를 SHA-256으로 해싱하여 32바이트 길이의 키를 생성
• 생성된 키는 AES 암호화에서 대칭키로 사용

AES 암호화를 통한 플래그 암호화

cipher = AES.new(key, AES.MODE_ECB)
print("encyprted_flag = ", cipher.encrypt(flag))

• AES.new(key, AES.MODE_ECB)

  • AES를 전자 코드북(ECB) 모드로 초기화
  • ECB 모드는 각 블록을 독립적으로 암호화하지만, 동일한 입력 블록에 대해 동일한 암호문을 생성하는 단점

• cipher.encrypt(flag)

  • 플래그를 AES 암호화
  • 플래그는 16바이트 블록 단위로 암호화되며, 입력 크기가 맞지 않으면 패딩이 필요

출력 내용

• n: RSA 모듈러 (공개키의 일부)
• e: RSA 공개 지수
• c1: RSA로 암호화된 key
• c2: RSA로 암호화된 rot13_key
• encyprted_flag: AES로 암호화된 플래그

전체 흐름

• RSA 파라미터 생성

  • 512비트 소수 p,q를 생성하고 $n = p \times q$를 계산
  • e = 137 을 공개 지수로 설정

• 랜덤 키 생성

  • 길이가 10인 랜덤 문자열 key 생성 및 ROT13 변환

• RSA 암호화

  • key와 rot13_key를 RSA 암호화하여 c1과 c2를 출력

• SHA-256 해시

  • key를 SHA-256으로 해싱하여 AES 대칭키 생성

• 플래그 AES 암호화

  • AES ECB 모드를 사용해 플래그를 암호화하고 암호문 출력

---

Sol

from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib
import codecs
from sympy import factorint

# output.txt에서 제공된 값
n = 105270965659728963158005445847489568338624133794432049687688451306125971661031124713900002127418051522303660944175125387034394970179832138699578691141567745433869339567075081508781037210053642143165403433797282755555668756795483577896703080883972479419729546081868838801222887486792028810888791562604036658927

e = 137

c1 = 16725879353360743225730316963034204726319861040005120594887234855326369831320755783193769090051590949825166249781272646922803585636193915974651774390260491016720214140633640783231543045598365485211028668510203305809438787364463227009966174262553328694926283315238194084123468757122106412580182773221207234679

c2 = 54707765286024193032187360617061494734604811486186903189763791054142827180860557148652470696909890077875431762633703093692649645204708548602818564932535214931099060428833400560189627416590019522535730804324469881327808667775412214400027813470331712844449900828912439270590227229668374597433444897899112329233

encrypted_flag = b"\xdb'\x0bL\x0f\xca\x16\xf5\x17>\xad\xfc\xe2\x10$(DVsDS~\xd3v\xe2\x86T\xb1{xL\xe53s\x90\x14\xfd\xe7\xdb\xddf\x1fx\xa3\xfc3\xcb\xb5~\x01\x9c\x91w\xa6\x03\x80&\xdb\x19xu\xedh\xe4"

# 1. 소인수분해
factors = factorint(n)
p, q = list(factors.keys())
print("p =", p)
print("q =", q)

# 2. d 계산
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

# 3. key 복구
key_long = pow(c1, d, n)
key = long_to_bytes(key_long).decode()

# 4. rot13_key 확인 (ROT13 변환)
rot13_key = codecs.encode(key, 'rot13')

# 5. SHA-256 해시로 AES 키 생성
aes_key = hashlib.sha256(key.encode()).digest()

# 6. AES 복호화
cipher = AES.new(aes_key, AES.MODE_ECB)
flag = cipher.decrypt(encrypted_flag).decode()

print("Recovered key:", key)
print("Recovered rot13_key:", rot13_key)
print("Flag:", flag)

• 너무 오래 걸림
• Pollard's Rho 방식으로 수정

from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib
import codecs
from math import gcd
from random import randint

# output.txt에서 제공된 값
n = 105270965659728963158005445847489568338624133794432049687688451306125971661031124713900002127418051522303660944175125387034394970179832138699578691141567745433869339567075081508781037210053642143165403433797282755555668756795483577896703080883972479419729546081868838801222887486792028810888791562604036658927
e = 137
c1 = 16725879353360743225730316963034204726319861040005120594887234855326369831320755783193769090051590949825166249781272646922803585636193915974651774390260491016720214140633640783231543045598365485211028668510203305809438787364463227009966174262553328694926283315238194084123468757122106412580182773221207234679
c2 = 54707765286024193032187360617061494734604811486186903189763791054142827180860557148652470696909890077875431762633703093692649645204708548602818564932535214931099060428833400560189627416590019522535730804324469881327808667775412214400027813470331712844449900828912439270590227229668374597433444897899112329233

encrypted_flag = b"\xdb'\x0bL\x0f\xca\x16\xf5\x17>\xad\xfc\xe2\x10$(DVsDS~\xd3v\xe2\x86T\xb1{xL\xe53s\x90\x14\xfd\xe7\xdb\xddf\x1fx\xa3\xfc3\xcb\xb5~\x01\x9c\x91w\xa6\x03\x80&\xdb\x19xu\xedh\xe4"

# Pollard's Rho 소인수분해 알고리즘
def pollards_rho(n):
    x = randint(2, n - 1)
    y = x
    c = randint(1, n - 1)
    d = 1
    while d == 1:
        x = (x * x + c) % n
        y = (y * y + c) % n
        y = (y * y + c) % n
        d = gcd(abs(x - y), n)
    if d == n:
        return None  # 실패하면 None 반환
    return d

# 1. 소인수분해
p = pollards_rho(n)
if not p:
    raise ValueError("소인수분해 실패!")
q = n // p
print("p =", p)
print("q =", q)

# 2. RSA 개인 키 d 계산
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

# 3. key 복구
key_long = pow(c1, d, n)
key = long_to_bytes(key_long).decode()

# 4. rot13_key 확인 (ROT13 변환)
rot13_key = codecs.encode(key, 'rot13')

# 5. SHA-256 해시로 AES 키 생성
aes_key = hashlib.sha256(key.encode()).digest()

# 6. AES 복호화
cipher = AES.new(aes_key, AES.MODE_ECB)
flag = cipher.decrypt(encrypted_flag).decode()

print("Recovered key:", key)
print("Recovered rot13_key:", rot13_key)
print("Flag:", flag)

• 일단 소인수분해 과정 빼고, p와 q를 안다는 가정 하에 코드 작성

from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib
import codecs

# 주어진 값들
n = 105270965659728963158005445847489568338624133794432049687688451306125971661031124713900002127418051522303660944175125387034394970179832138699578691141567745433869339567075081508781037210053642143165403433797282755555668756795483577896703080883972479419729546081868838801222887486792028810888791562604036658927
e = 137
c1 = 16725879353360743225730316963034204726319861040005120594887234855326369831320755783193769090051590949825166249781272646922803585636193915974651774390260491016720214140633640783231543045598365485211028668510203305809438787364463227009966174262553328694926283315238194084123468757122106412580182773221207234679
c2 = 54707765286024193032187360617061494734604811486186903189763791054142827180860557148652470696909890077875431762633703093692649645204708548602818564932535214931099060428833400560189627416590019522535730804324469881327808667775412214400027813470331712844449900828912439270590227229668374597433444897899112329233
encrypted_flag = b"\xdb'\x0bL\x0f\xca\x16\xf5\x17>\xad\xfc\xe2\x10$(DVsDS~\xd3v\xe2\x86T\xb1{xL\xe53s\x90\x14\xfd\xe7\xdb\xddf\x1fx\xa3\xfc3\xcb\xb5~\x01\x9c\x91w\xa6\x03\x80&\xdb\x19xu\xedh\xe4"

# 소인수분해 결과: p, q (Factordb나 소인수분해 도구로 구해야 함)
p = 123456789012345678901234567890123456789  # 예시 값 (실제 p 사용)
q = n // p

# RSA 복호화에 필요한 값 계산
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)  # 비밀 키 계산

# RSA 복호화로 key 복구
key_long = pow(c1, d, n)
key = long_to_bytes(key_long).decode()

# ROT13로 rot13_key 확인
rot13_key = codecs.encode(key, 'rot13')
rot13_key_long = pow(c2, d, n)
assert rot13_key == long_to_bytes(rot13_key_long).decode(), "ROT13 key does not match!"

# SHA-256 해시로 AES 키 생성
aes_key = hashlib.sha256(key.encode()).digest()

# AES 복호화
cipher = AES.new(aes_key, AES.MODE_ECB)
flag = cipher.decrypt(encrypted_flag).decode()

# 결과 출력
print("Recovered key:", key)
print("Recovered rot13_key:", rot13_key)
print("Decrypted Flag:", flag)