페르마의 소정리
페르마의 소정리는 정수론의 기본 정리 중 하나로, 소수를 법으로 하는 모듈러 연산에서 거듭제곱의 특별한 성질을 다룹니다.
정리 정의
-
첫 번째 형태:
p가 소수이고, 정수a가p의 배수가 아닐 때 (즉,gcd(a, p) = 1), 다음 관계가 성립합니다:a^(p-1) ≡ 1 (mod p) -
두 번째 형태: 임의의 정수
a와 소수p에 대해, 다음이 항상 성립합니다:a^p ≡ a (mod p)
암호학적 응용 예제: CTF 문제 분석
주어진 암호학 문제에서 플래그(flag_value)를 찾아야 하는 시나리오를 통해 페르마의 소정리 활용법을 살펴보겠습니다. 다음은 문제의 핵심 부분에서 사용된 Python 코드입니다.
from Crypto.Util.number import getPrime, bytes_to_long
from random import randint
from flag import FLAG # 실제 플래그는 여기서 로드됩니다.
KEY_BITS = 1024
flag_value = bytes_to_long(FLAG)
# 두 개의 큰 소수 p와 q를 생성하여 모듈러스 n을 만듭니다.
prime_p = getPrime(KEY_BITS)
prime_q = getPrime(KEY_BITS)
modulus_n = prime_p * prime_q
# 임의의 생성자 base_val 및 지수 rand_a1, rand_a2를 생성합니다.
base_val = randint(1, modulus_n)
rand_a1 = randint(1, modulus_n)
rand_a2 = randint(1, modulus_n)
# k1과 k2는 페르마의 소정리 형태와 유사하게 생성됩니다.
# secret_k1 = base_val^(rand_a1 * (prime_p - 1)) mod modulus_n
secret_k1 = pow(base_val, rand_a1 * (prime_p - 1), modulus_n)
# secret_k2 = base_val^(rand_a2 * (prime_q - 1)) mod modulus_n
secret_k2 = pow(base_val, rand_a2 * (prime_q - 1), modulus_n)
# 임의의 값 rand_b1, rand_b2 생성
rand_b1 = randint(1, modulus_n)
rand_b2 = randint(1, modulus_n)
# 암호문 encrypted_c1, encrypted_c2 생성
# encrypted_c1 = (secret_k1^rand_b1 * flag_value) mod modulus_n
encrypted_c1 = (pow(secret_k1, rand_b1, modulus_n) * flag_value) % modulus_n
# encrypted_c2 = (secret_k1^rand_b2 * flag_value) mod modulus_n
encrypted_c2 = (pow(secret_k1, rand_b2, modulus_n) * flag_value) % modulus_n
# 플래그 값은 n보다 작다는 조건이 주어집니다.
assert flag_value < modulus_n
print(f"n = {modulus_n}")
print(f"k1 = {secret_k1}")
print(f"c1 = {encrypted_c1}")
# 다른 값들 (k2, c2)도 제공될 수 있습니다.
우리의 목표는 제공된 modulus_n, secret_k1, encrypted_c1 값을 사용하여 flag_value를 복구하는 것입니다. 먼저 secret_k1의 생성 방식을 분석해 봅시다.
secret_k1 = pow(base_val, rand_a1 * (prime_p - 1), modulus_n)
이 식은 secret_k1 = (base_val^rand_a1)^(prime_p - 1) mod modulus_n으로 해석할 수 있습니다. 페르마의 소정리 (첫 번째 형태)에 따르면, prime_p를 법으로 할 경우, (base_val^rand_a1)^(prime_p - 1) ≡ 1 (mod prime_p)이 성립합니다. 이 성질을 활용하기 위해 secret_k1을 prime_p로 나눈 나머지를 고려합니다.
modulus_n = prime_p * prime_q이므로, 임의의 정수 X에 대해 X mod modulus_n은 X mod prime_p와 관련이 있습니다.
따라서, secret_k1 ≡ (base_val^rand_a1)^(prime_p - 1) (mod prime_p)입니다.
페르마의 소정리에 의해 (base_val^rand_a1)^(prime_p - 1) ≡ 1 (mod prime_p)이므로,
secret_k1 ≡ 1 (mod prime_p)가 됩니다.
이는 secret_k1 - 1이 prime_p의 배수임을 의미합니다. 즉, prime_p는 secret_k1 - 1의 약수입니다. 동시에 prime_p는 modulus_n의 약수이기도 합니다. 따라서 prime_p는 secret_k1 - 1과 modulus_n의 최대공약수(GCD)를 통해 찾을 수 있습니다.
prime_p = gcd(secret_k1 - 1, modulus_n)
이제 prime_p를 얻었으므로, encrypted_c1 식을 prime_p를 법으로 하여 다시 분석합니다.
encrypted_c1 = (pow(secret_k1, rand_b1, modulus_n) * flag_value) % modulus_n
양변에 mod prime_p 연산을 적용하면:
encrypted_c1 ≡ (pow(secret_k1, rand_b1, modulus_n) * flag_value) (mod prime_p)
여기서 pow(secret_k1, rand_b1, modulus_n) 부분을 mod prime_p로 변환하면 다음과 같습니다:
pow(secret_k1, rand_b1, modulus_n) % prime_p ≡ pow(secret_k1 % prime_p, rand_b1, prime_p)
앞서 secret_k1 ≡ 1 (mod prime_p)임을 확인했으므로,
pow(secret_k1 % prime_p, rand_b1, prime_p) ≡ pow(1, rand_b1, prime_p) ≡ 1 (mod prime_p)
결과적으로 encrypted_c1 ≡ 1 * flag_value (mod prime_p), 즉 encrypted_c1 ≡ flag_value (mod prime_p)가 됩니다.
문제에 assert flag_value < modulus_n 조건이 있었으며, 대부분의 CTF 문제에서 flag_value는 prime_p보다 작은 것이 일반적입니다. 만약 flag_value < prime_p라면, flag_value % prime_p는 flag_value 그 자체입니다. 따라서 flag_value = encrypted_c1 % prime_p로 복호화할 수 있습니다.
복호화 코드
import gmpy2
import libnum # 정수-바이트 변환을 위해 사용
# 주어진 문제 값들
N_VALUE = 9858036118742475059433629759400140149605427966433887001108914046633590983713890376353399251885596714047941627222518567515364827340623251995233155278723954926352575221234142199002389819918370754455018819109203109519495493316781422680537687252828642561153832774006286448224016306003631037545643746379044035822029246823483754854602215035869280453855199171915302879406862793807947285344105991067005185493038370882005106069286893165426035453262949739088328689761676541415552066845538243916687080015277379248062286846119847500455125785281216888979581104100416760176854106890525904804003871967844912776926419778292365918733
K1_VALUE = 4961356980843219227031667558158760111429474781353239042846946454889308337426649950562701556812878479419482114480334396560017050901408543482904510839046375272618911899662922000275482705215097956326853000314956770940510205507508883917322367747195211326932972446951696070952604655668087834669239815290687449340666091764203568518066586476150861542456340936303824392273004883320273039066213750777751436497551151274574369325153858390731248298056433816285354182588883715211738843801326831297181947562239993323202961410530072969013398669658073337273085171642258091164822631807295793886169033827781164115751086585872189121242
C1_VALUE = 4115578106197062017294044310891024039554438131787269391154862526142866937938155870549829472424386226484625850457327387070755337288822640509004443484397234720914851433620556887385729540499953724033259937785600491548446806766462413179765702810698096381537513314758346885921106310631278002150697458246447235914052771405341899822588463120295331632180131956205362147784798497203957828308109092025630961803808101730731656980785388965672073473370194469269645377465298620585379296063436880502566076330461976785816470877632107769103280243111778113065038163250625042092690628478547757779278811188187028242267396799577953511519
# secret_k1 - 1과 modulus_n의 최대공약수를 계산하여 소수 prime_p를 찾습니다.
found_prime_p = gmpy2.gcd(K1_VALUE - 1, N_VALUE)
# flag_value는 encrypted_c1을 prime_p로 나눈 나머지입니다.
decrypted_flag_value = (int)(C1_VALUE % found_prime_p)
# 복호화된 정수 값을 바이트 문자열로 변환하여 출력합니다.
print(libnum.n2s(decrypted_flag_value))
오일러의 정리
오일러의 정리는 페르마의 소정리를 확장하여, 소수가 아닌 임의의 양의 정수 모듈러에 대해서도 거듭제곱의 성질을 정의하는 중요한 정리입니다.
정리 정의
m이 양의 정수이고, a가 m과 서로소일 때 (즉, gcd(a, m) = 1), 다음 관계가 성립합니다:
a^φ(m) ≡ 1 (mod m)
여기서 φ(m)은 오일러 파이 함수 (Euler's Totient Function)를 나타냅니다. φ(m)은 m보다 작거나 같으면서 m과 서로소인 양의 정수의 개수를 셉니다.
오일러 파이 함수의 주요 성질
-
곱셈적 함수: 두 양의 정수
m과n이 서로소 (gcd(m, n) = 1)일 때,φ(mn) = φ(m) * φ(n)이 성립합니다.- 특히,
n이 홀수일 경우φ(2n) = φ(n)입니다.
- 특히,
-
소수의 거듭제곱:
p가 소수이고k가 양의 정수일 때,φ(p^k) = p^k - p^(k-1)입니다.
확장 오일러 정리
오일러의 정리는 a와 m이 서로소가 아닌 경우에도 적용될 수 있도록 일반화된 확장 오일러 정리가 존재합니다. 그러나 본 글에서는 기본적인 오일러 정리의 주요 응용에 초점을 맞춥니다.
암호학적 응용 예제: RSA 복호화 시나리오
오일러의 정리는 RSA 공개키 암호화 알고리즘의 핵심 수학적 기반 중 하나입니다. 다음은 RSA 복호화 문제의 특정 상황을 분석하는 예시입니다.
문제에서 제공된 값들:
# 공개 지수 (e)
public_exponent = 65537
# RSA 모듈러스 (n = p * q)
modulus_n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
# d_p 값 (비밀 지수 d mod (p-1))
dec_exp_p_value = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
# 암호화된 메시지 (c)
encrypted_message = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
RSA의 핵심 관계는 e * d ≡ 1 mod φ(n)입니다. 여기서 φ(n) = (p-1)(q-1)입니다. 또한, dec_exp_p_value는 d ≡ dec_exp_p_value (mod (p-1))이라는 관계를 가집니다. 이 두 관계를 조합하면 e * d ≡ 1 mod (p-1)이 유도되고, 따라서 e * dec_exp_p_value ≡ 1 mod (p-1)이 성립합니다.
이는 e * dec_exp_p_value - 1이 (p-1)의 배수임을 의미합니다. 즉, e * dec_exp_p_value - 1 = k * (p-1)을 만족하는 정수 k가 존재합니다. 우리는 소수 p를 찾아야 하므로, p-1 = (e * dec_exp_p_value - 1) / k라는 관계를 활용할 수 있습니다.
k는 e * dec_exp_p_value - 1의 약수이며, 이 예제에서는 k의 범위가 1부터 public_exponent까지인 경우가 많습니다. p-1을 찾으면 p = (p-1) + 1이 됩니다.
이렇게 찾은 p 값이 modulus_n의 약수인지 확인하여 올바른 p를 확정합니다. p를 찾으면 q = modulus_n / p를 계산하고, φ(n) = (p-1)(q-1)을 이용하여 최종 복호화 지수 d를 계산한 후 메시지를 복호화할 수 있습니다.
복호화 코드
import gmpy2
import binascii
# 주어진 RSA 매개변수들
E_VAL = 65537
N_VAL = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
DP_VAL = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
C_VAL = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
# e * dp - 1이 (p-1)의 배수라는 성질을 이용합니다.
# (E_VAL * DP_VAL - 1) / k_factor = p-1을 만족하는 k_factor를 찾습니다.
# k_factor는 일반적으로 E_VAL보다 크지 않은 작은 정수일 가능성이 높습니다.
for k_factor in range(1, E_VAL + 1): # E_VAL까지 탐색
if (E_VAL * DP_VAL - 1) % k_factor == 0:
p_minus_1_candidate = (E_VAL * DP_VAL - 1) // k_factor
p_candidate = p_minus_1_candidate + 1
# p_candidate가 N_VAL의 약수인지 확인 (N = p * q)
if N_VAL % p_candidate == 0:
found_p = p_candidate
found_q = N_VAL // found_p
# 오일러 파이 함수 φ(N) = (p-1)(q-1) 계산
phi_n = (found_p - 1) * (found_q - 1)
# 복호화 지수 d 계산 (e의 φ(N)에 대한 역원)
decryption_d = gmpy2.invert(E_VAL, phi_n)
# 암호화된 메시지를 복호화
decrypted_message = gmpy2.powmod(C_VAL, decryption_d, N_VAL)
# 복호화된 메시지를 16진수에서 바이트 문자열로 변환하여 출력
print(binascii.unhexlify(hex(decrypted_message)[2:]))
break # 올바른 p를 찾았으므로 루프를 종료합니다.