중간고사 프로젝트 과제

1. Diffie-Hellman 키합의를 이용한 암복호화 시뮬레이션

1.1 개요

본 과제에서는 Diffie-Hellman(DH) 키합의 알고리즘을 이용하여 송신자와 수신자가 공유 비밀키를 생성하고, 이를 활용하여 메시지를 암호화 및 복호화하는 과정을 시뮬레이션하였다. DH 키합의는 공개 채널 상에서 직접 비밀키를 교환하지 않고도 동일한 공유 비밀을 생성할 수 있는 대표적인 키 교환 방식이다.

1.2 동작 과정

본 프로그램은 Diffie-Hellman 키합의 과정을 기반으로 송신자와 수신자가 동일한 공유 비밀값을 생성하고, 이를 이용하여 메시지를 암복호화하는 방식으로 구성된다. 먼저, 공개 파라미터로 사용되는 소수 p와 생성자 g를 설정한다. 이후 송신자(Alice)와 수신자(Bob)는 각각 임의의 개인키 a와 b를 선택한다.

각 참여자는 자신의 개인키를 이용하여 공개키를 계산하는데, Alice는 A=g^a mod p, Bob은 B=g^b mod p를 계산하여 서로 교환한다. 공개키를 전달받은 이후, Alice는 Bob의 공개키를 이용하여 B^a mod p를 계산하고, Bob 역시 Alice의 공개키를 이용하여 A^b mod p를 계산한다. 이 과정에서 두 사용자는 동일한 공유 비밀값을 얻게 된다.

이렇게 생성된 공유 비밀값은 그대로 사용하지 않고, SHA-256 해시 함수를 적용하여 보다 안전한 형태의 대칭키로 변환한다. 마지막으로, 생성된 대칭키를 이용하여 송신자는 메시지를 암호화하여 전달하고, 수신자는 동일한 키를 이용하여 암호문을 복호화함으로써 원래의 메시지를 확인할 수 있다.

1.3 코드 및 실행 결과

코드

import hashlib
import random

# 간단한 Diffie-Hellman 파라미터 (시뮬레이션용)
p = 2089   # 소수
g = 2      # 생성자

# Alice / Bob 개인키 생성
a = random.randint(2, p-2)
b = random.randint(2, p-2)

# 공개키 계산
A = pow(g, a, p)
B = pow(g, b, p)

# 공유 비밀 계산
shared_by_alice = pow(B, a, p)
shared_by_bob = pow(A, b, p)

assert shared_by_alice == shared_by_bob
shared_secret = shared_by_alice

# 공유 비밀키를 바이트 키로 변환 (SHA-256)
key = hashlib.sha256(str(shared_secret).encode()).digest()

def xor_encrypt(plaintext: str, key_bytes: bytes) -> bytes:
    data = plaintext.encode('utf-8')
    return bytes([data[i] ^ key_bytes[i % len(key_bytes)] for i in range(len(data))])

def xor_decrypt(ciphertext: bytes, key_bytes: bytes) -> str:
    data = bytes([ciphertext[i] ^ key_bytes[i % len(key_bytes)] for i in range(len(ciphertext))])
    return data.decode('utf-8')

message = "Hello Bob, this is Alice."
ciphertext = xor_encrypt(message, key)
recovered = xor_decrypt(ciphertext, key)

print("=== Diffie-Hellman Key Exchange + Message Encryption Simulation ===")
print(f"Prime p                = {p}")
print(f"Generator g            = {g}")
print(f"Alice private key a    = {a}")
print(f"Bob private key b      = {b}")
print(f"Alice public key A     = g^a mod p = {A}")
print(f"Bob public key B       = g^b mod p = {B}")
print(f"Alice shared secret    = B^a mod p = {shared_by_alice}")
print(f"Bob shared secret      = A^b mod p = {shared_by_bob}")
print(f"Derived symmetric key  = SHA256(shared_secret) = {key.hex()}")
print(f"Plaintext              = {message}")
print(f"Ciphertext (hex)       = {ciphertext.hex()}")
print(f"Decrypted plaintext    = {recovered}")

실행 결과

=== Diffie-Hellman Key Exchange + Message Encryption Simulation ===
Prime p                = 2089
Generator g            = 2
Alice private key a    = 1689
Bob private key b      = 43
Alice public key A     = g^a mod p = 128
Bob public key B       = g^b mod p = 1761
Alice shared secret    = B^a mod p = 2048
Bob shared secret      = A^b mod p = 2048
Derived symmetric key  = SHA256(shared_secret) = bfa0ec8bdf2946547879d50a68687ea32e2fa628db187357415858b633d194d9
Plaintext              = Hello Bob, this is Alice.
Ciphertext (hex)       = f7c580e7b009043b1a55f57e00010d83475c8669b77110326f
Decrypted plaintext    = Hello Bob, this is Alice.

1.4 결과 분석

실행 결과에서 Alice와 Bob이 계산한 공유 비밀값이 동일함을 확인할 수 있었다. 이를 기반으로 생성된 대칭키를 이용하여 메시지가 정상적으로 암호화 및 복호화됨을 통해 DH 키합의가 실제 통신에서 안전한 키 교환 방식으로 활용될 수 있음을 확인하였다.

 

2. DLP 기반 DH와 EC 기반 DH의 수학적 파라미터 분석

2.1 개요

본 과제에서는 DLP(이산로그 문제) 기반 Diffie-Hellman과 타원곡선 기반 Diffie-Hellman(ECDH)의 키 생성 과정을 비교하고, 각각의 개인키와 공개키가 어떤 수학적 파라미터를 가지는지 확인하였다.

2.2 DLP 기반 Diffie-Hellman

DLP 기반 Diffie-Hellman 방식에서는 유한체 상의 이산로그 문제를 기반으로 키 생성이 이루어진다. 먼저 큰 소수 p와 생성자 g를 설정하고, 사용자는 임의의 정수 값을 개인키 x로 선택한다. 이후 공개키는 y=g^x mod p의 형태로 계산되며, 이 값은 외부에 공개된다.

이 과정에서 공격자가 공개키 y를 알고 있더라도 개인키 x를 직접 계산하는 것은 이산로그 문제의 계산적 어려움으로 인해 매우 어렵다. 따라서 이러한 수학적 특성에 기반하여 DLP 방식의 보안성이 유지된다.

2.3 EC 기반 Diffie-Hellman

타원곡선 기반 Diffie-Hellman(ECDH)은 이산로그 문제를 타원곡선 상으로 확장한 방식으로, 보다 효율적인 키 생성이 가능하다. 이 방식에서는 먼저 특정 타원곡선과 생성점 G가 정의되며, 사용자는 임의의 스칼라 값 d를 개인키로 선택한다.

공개키는 생성점 G에 개인키 d를 곱한 점 Q=dG로 계산되며, 이는 좌표 형태로 표현된다. 이 과정에서 개인키를 알지 못한 상태에서 공개키로부터 개인키를 역산하는 것은 타원곡선 이산로그 문제의 어려움 때문에 현실적으로 불가능하다. 따라서 ECDH는 동일한 보안 수준에서 더 짧은 키 길이를 사용할 수 있어 효율성과 보안성을 동시에 만족시키는 특징을 가진다.

2.4 코드 및 실행 결과

코드

from cryptography.hazmat.primitives.asymmetric import dh, ec

print("=== DLP-based DH Example ===")
parameters = dh.generate_parameters(generator=2, key_size=512)
params = parameters.parameter_numbers()

private_key = parameters.generate_private_key()
public_key = private_key.public_key()

priv_nums = private_key.private_numbers()
pub_nums = public_key.public_numbers()

print(f"p (prime modulus)      = {params.p}")
print(f"g (generator)          = {params.g}")
print(f"q (subgroup order)     = {params.q}")
print(f"private key x          = {priv_nums.x}")
print(f"public key y           = g^x mod p = {pub_nums.y}")
print()

print("=== EC-based DH Example (ECDH) ===")
ec_private_key = ec.generate_private_key(ec.SECP256R1())
ec_public_key = ec_private_key.public_key()

ec_priv_nums = ec_private_key.private_numbers()
ec_pub_nums = ec_public_key.public_numbers()

print(f"curve                   = {ec_public_key.curve.name}")
print(f"private scalar d        = {ec_priv_nums.private_value}")
print(f"public point Q.x        = {ec_pub_nums.x}")
print(f"public point Q.y        = {ec_pub_nums.y}")

실행 결과

=== DLP-based DH Example ===
p (prime modulus)      = 12567466676744382777739638990458139472106086060881868143062534812711550635483879405130066458117977222508029592929103551164036404668806804752301515793980199
g (generator)          = 2
q (subgroup order)     = None
private key x          = 2779200350364400583058352257262616857868432192857339742572628002209950694856147811935463284677225117192634894849649270685492378593127933151332896514005051
public key y           = g^x mod p = 4963029114910759597480799372491901843429933536221872733235559040106053771627592882792448767974335127909593900144202468724878921122321256421757687769066832

=== EC-based DH Example (ECDH) ===
curve                   = secp256r1
private scalar d        = 25264823623651873903567610914116193660333059990133405717421360125319126261704
public point Q.x        = 5849114969501012549273487454829187136715476857342874161124827209651323562050
public point Q.y        = 91879475369364963359424337113697810027230004390276580427495454706238125306585

2.5 결과 분석

DLP 기반 DH에서는 공개키가 정수 형태로 표현되는 반면, EC 기반 DH에서는 공개키가 타원곡선 상의 점으로 표현된다는 차이를 확인할 수 있었다. 또한 동일한 보안 수준에서 EC 방식이 더 짧은 키 길이를 사용함으로써 효율성이 높다는 특징을 가진다.

 

3. Schnorr Protocol에서 난수 재사용 시 개인키 탈취

3.1 개요

Schnorr Protocol은 영지식 증명 방식 중 하나로, 증명자가 자신의 비밀값을 노출하지 않고도 이를 알고 있음을 증명할 수 있다. 그러나 난수(nonce)를 재사용할 경우 심각한 보안 취약점이 발생한다.

3.2 취약점 원리

Schnorr Protocol에서는 증명자가 자신의 비밀키를 직접 공개하지 않고도 해당 값을 알고 있음을 증명할 수 있도록 설계되어 있으며, 이 과정에서 난수 t가 중요한 역할을 한다. 증명자는 먼저 난수 t를 선택하고 이를 이용하여 커밋값을 생성한 후, 검증자로부터 전달받은 챌린지 값 e에 따라 응답값 s=t+ex mod q를 계산한다.

그러나 동일한 난수 t를 두 번 이상 재사용할 경우 보안 취약점이 발생한다. 서로 다른 두 챌린지 e_1, e_2에 대해 생성된 응답값 s₁, s₂를 이용하면, 두 식의 차이를 통해 개인키 x를 직접 계산할 수 있게 된다. 이는 난수가 제거되면서 개인키에 대한 선형 관계가 드러나기 때문이다. 결국 검증자는 단순한 연산만으로 개인키를 복구할 수 있으며, 이는 Schnorr Protocol에서 난수 재사용이 매우 위험한 이유를 보여준다.

3.3 코드 및 실행 결과

코드

import random
from math import gcd

# 작은 Schnorr 파라미터 (시뮬레이션/공격 시연용)
p = 23
q = 11
g = 2  # 2^11 mod 23 = 1 이므로 order q=11 subgroup의 원소

x = random.randint(1, q - 1)  # prover secret key
y = pow(g, x, p)              # public key

t = random.randint(1, q - 1)  # 재사용된 nonce (취약점의 핵심)
r = pow(g, t, p)

# 서로 다른 challenge 2개
e1 = 3
e2 = 7
assert e1 != e2
assert gcd((e1 - e2) % q, q) == 1

# Schnorr 응답: s = t + e*x mod q
s1 = (t + e1 * x) % q
s2 = (t + e2 * x) % q

# 공격자(검증자)가 nonce 재사용을 이용해 개인키 복구
# s1 - s2 = (e1 - e2) * x mod q
numerator = (s1 - s2) % q
denominator = (e1 - e2) % q
denominator_inv = pow(denominator, -1, q)
recovered_x = (numerator * denominator_inv) % q

print("=== Schnorr Protocol Nonce-Reuse Attack Simulation ===")
print(f"p                        = {p}")
print(f"q                        = {q}")
print(f"g                        = {g}")
print(f"Prover secret key x      = {x}")
print(f"Prover public key y      = g^x mod p = {y}")
print(f"Reused nonce t           = {t}")
print(f"Commitment r             = g^t mod p = {r}")
print(f"Challenge e1             = {e1}")
print(f"Challenge e2             = {e2}")
print(f"Response s1              = (t + e1*x) mod q = {s1}")
print(f"Response s2              = (t + e2*x) mod q = {s2}")
print(f"Recovered secret key x'  = (s1-s2)/(e1-e2) mod q = {recovered_x}")
print(f"Attack success?          = {recovered_x == x}")

실행 결과

=== Schnorr Protocol Nonce-Reuse Attack Simulation ===
p                        = 23
q                        = 11
g                        = 2
Prover secret key x      = 3
Prover public key y      = g^x mod p = 8
Reused nonce t           = 4
Commitment r             = g^t mod p = 16
Challenge e1             = 3
Challenge e2             = 7
Response s1              = (t + e1*x) mod q = 2
Response s2              = (t + e2*x) mod q = 3
Recovered secret key x'  = (s1-s2)/(e1-e2) mod q = 3
Attack success?          = True

3.4 결과 분석

실행 결과에서 동일한 난수를 재사용할 경우 검증자가 증명자의 개인키를 정확히 복구할 수 있음을 확인하였다. 이는 Schnorr Protocol에서 난수의 일회성 사용이 필수적임을 의미하며, 난수 재사용은 치명적인 보안 취약점으로 이어짐을 보여준다.

 

4. 이산로그 문제에서 비트수에 따른 계산 시간 분석

4.1 개요

이산로그 문제(DLP)의 난이도를 확인하기 위해, 소수 p의 비트수를 증가시키면서 brute-force 방식으로 개인키를 찾는 시간을 측정하였다.

4.2 실험 방법

이산로그 문제의 계산 난이도를 확인하기 위해, 소수 p의 비트수를 점진적으로 증가시키면서 brute-force 방식으로 개인키를 탐색하는 실험을 수행하였다. 먼저 특정 비트수를 가지는 소수 p와 생성자 g를 설정한 후, 임의의 개인키 x를 선택하여 공개키 y=g^x mod p를 생성한다.

이후 가능한 모든 x값을 순차적으로 대입하여 공개키와 일치하는 값을 찾는 방식으로 탐색을 수행하고, 이 과정에 소요되는 시간을 측정하였다. 이러한 과정을 여러 비트수에 대해 반복함으로써, 비트수가 증가함에 따라 계산 시간이 어떻게 변화하는지를 관찰하였다.

4.3 코드 및 실행 결과

코드

import time

# 각 비트수에서 소수 p와 primitive root g를 사용해
# g^x mod p = y 를 만족하는 x를 순차탐색으로 복구하는 시간 측정
# (학습용 brute-force discrete log)
TESTS = [
    (12, 4099, 2),
    (14, 16411, 3),
    (16, 65537, 3),
    (18, 262147, 2),
    (20, 1048583, 5),
    (22, 4194319, 3),
    (24, 16777259, 2),
]

def brute_force_dlog(p, g, y):
    for x in range(1, p - 1):
        if pow(g, x, p) == y:
            return x
    return None

results = []
print("=== Discrete Log Brute-Force Timing Experiment ===")
for bits, p, g in TESTS:
    # 개인키를 중간 정도 위치에 두어 평균 탐색시간에 가깝게 설정
    x = (p - 1) // 2
    y = pow(g, x, p)

    start = time.perf_counter()
    recovered = brute_force_dlog(p, g, y)
    elapsed = time.perf_counter() - start

    results.append((bits, p, g, x, recovered, elapsed))
    print(f"bits={bits:2d}, p={p}, g={g}, recovered={recovered == x}, elapsed={elapsed:.6f} sec")

# 마지막 측정 기준으로 1시간 이내 가능 비트수 대략 추정
# brute-force 비용이 대략 O(p) ~ O(2^bits)이므로,
# 시간은 비트가 1 늘 때마다 약 2배 증가한다고 가정
one_hour = 3600.0
last_bits, _, _, _, _, last_time = results[-1]
est_bits = last_bits
est_time = last_time
while est_time * 2 <= one_hour:
    est_time *= 2
    est_bits += 1

print()
print(f"Based on the last measured point ({last_bits} bits, {last_time:.6f} sec),")
print(f"the largest bit-length expected to remain within about 1 hour is approximately {est_bits} bits.")

실행 결과

=== Discrete Log Brute-Force Timing Experiment ===
bits=12, p=4099, g=2, recovered=True, elapsed=0.002871 sec
bits=14, p=16411, g=3, recovered=True, elapsed=0.006614 sec
bits=16, p=65537, g=3, recovered=True, elapsed=0.030559 sec
bits=18, p=262147, g=2, recovered=True, elapsed=0.114075 sec
bits=20, p=1048583, g=5, recovered=True, elapsed=0.692566 sec
bits=22, p=4194319, g=3, recovered=True, elapsed=3.030382 sec
bits=24, p=16777259, g=2, recovered=True, elapsed=19.178840 sec

Based on the last measured point (24 bits, 19.178840 sec),
the largest bit-length expected to remain within about 1 hour is approximately 31 bits.

4.4 결과 분석

실험 결과 비트수가 증가할수록 계산 시간이 기하급수적으로 증가하는 것을 확인하였다. 작은 비트수에서는 brute-force 공격이 가능하지만, 비트수가 충분히 커지면 현실적으로 공격이 불가능해진다. 본 실험 환경에서는 약 30비트 전후가 1시간 이내 공격 가능한 한계로 추정되었으나, 이는 시스템 성능에 따라 달라질 수 있다.

 

5. 결론

본 프로젝트를 통해 다양한 암호 프로토콜의 원리를 실습적으로 이해할 수 있었다. Diffie-Hellman 키합의를 통해 안전한 키 교환이 가능함을 확인하였으며, DLP 기반과 EC 기반 방식의 구조적 차이를 비교하였다. 또한 Schnorr Protocol에서 난수 재사용이 개인키 유출로 이어질 수 있음을 확인하였고, 이산로그 문제의 계산 복잡도를 통해 충분한 키 길이의 중요성을 이해하였다. 이러한 결과는 실제 보안 시스템 설계 시 적절한 암호 기술 선택과 안전한 구현이 필수적임을 시사한다.