Cryptography Lab (1)

---

Intro

RSA (Rivest–Shamir–Adleman)암호는 초창기에 개발 된 공개키 암호 중 하나로, 암호화 통신에 널리 사용되고 있다. RSA 알고리즘은 두 개의 큰 소수를 생성하고, 이를 이용하여 공개키와 비밀키를 생성, 암호화, 복호화 및 전자서명과 검증에 사용한다. RSA 는 정수론에 기반하고 있으며, 큰 수를 연산 라이브러리를 통해서 쉽게 구현할 수 있다. 본 과제에서는 직접 RSA 알고리즘을 구현해 보는 것을 목표로 한다. 수업시간에 배운 RSA 알고리즘의 원리를 그대로 구현하는 것이 목표이다. 구현을 통해 RSA 알고리즘을 더 깊이 이해하고 실제로 사용되는 암호문에 적용해 본다. 본 Lab에는 아래의 내용을 포함한다.

-  공개키암호

-  RSA 알고리즘과 키 생성

-  큰수연산

-  RSA의암호화및복호화

-  전자서명

-  X.509 인증서

---

큰수 다루기

일반적인 프로그래밍 언어에서는 32-bit 혹은 64-bit 정수를 표준으로 사용한다. 이러한 수에 대한 연산은 CPU에서 매우 효율적으로 동작한다. 그러나, 각각 2^32 – 1, 2^64 – 1까지의 수 밖에 표현할 수 없으며, RSA 에서는 이보다 훨씬 큰 정수가 필요하여 integer overflow 문제가 발생한다. 따라서, 실제로 RSA 를 사용하기 위해서는 큰 수를 다룰 수 있는 라이브러리가 (arbitrary-precision arithmetic libraries) 필요하다. 몇 가지 훌륭한 라이브러리는 다음과 같다.

-  Openssl/bn: https://linux.die.net/man/3/bn 

-  GMP(GNU Multi-Precision Library): https://gmplib.org

-  NTL: https://libntl.org

본 실험에서는 편의를 위하여 python 을 사용한다. Python 에서는 64 비트 이상 정수 연산을 자연스럽게 지원한다. (그러나, 부동소수점 연산은 IEEE 754 표준의 64 비트 배정밀도(Double Precision)를 사용하기 때문에 정밀한 부동소수점 연산이 필요하면 다른 라이브러리를 써야한다.) 아래는 Python 에서 큰 수를 다루는 몇 가지 방법의 예시이다.

 

from math import log, ceil 
import random

# Assign a value from a decimal number string
decimal_number = int("12345678901112231223") 
print(decimal_number)
print(f"length: {ceil(log(decimal_number, 2))}-bits")

# Assign a value from a hex number string
hex_number = int("2A3B4C55FF77889AED3F", 16) 
print(hex_number)
print(f"length: {ceil(log(hex_number, 2))}-bits")

# Print a number as hex string
number = 12345678901112231223 hex_string = hex(number) 
print(hex_string)

# Generate a random number of 128 bits
random_number_128 = random.getrandbits(128) 
print(random_number_128)

# Generate a random prime number of 128 bits
random_number_128 = random.getrandbits(128) prime_number_128 = nextprime(random_number_128) 
print(prime_number_128)

아래 코드는 a, b, n을 생성하고, a*b와 a^b mod n을 계산한다.

from math import log, ceil
import random
from sympy import nextprime  # sympy의 nextprime 함수 사용

NBITS = 256

# Find a random prime number a
a = random.getrandbits(NBITS)
a = nextprime(a)

# Assign a large integer b
b = int('273489463796838501848592769467194369268')

# Define a large modulus n
n = random.getrandbits(NBITS)  # 또는 적절한 큰 정수로 정의
n = nextprime(n)  # n도 소수로 정의

# Print a * b
print(f"a * b: {a * b}")

# Print a^b mod n
print(f"a^b mod n: {pow(a, b, n)}")

 

a * b: 29465488494545362712046398861335344180509517736233042819902030515521650332266085662677104477562626843807590512279004
a^b mod n: 3130232423929134363190370216796079890890420520965500018809411292578052451620

pow(a, b, n) 대신 a**b%n 으로 대체해 보자. 어떠한 차이가 있는가?

import random
from sympy import nextprime
import time

NBITS = 256

# Generate large random numbers
a = random.getrandbits(NBITS)
a = nextprime(a)
b = random.randint(1, 1000)  # 지수를 작게 설정 (큰 지수는 ** 사용 시 위험)
n = nextprime(random.getrandbits(NBITS))

# Using pow(a, b, n)
start_time = time.time()
res_pow = pow(a, b, n)
end_time = time.time()
print(f"Result using pow(a, b, n): {res_pow}")
print(f"Time taken using pow(): {end_time - start_time:.6f} seconds")

# Using a ** b % n
start_time = time.time()
res_exp_mod = (a ** b) % n
end_time = time.time()
print(f"Result using a ** b % n: {res_exp_mod}")
print(f"Time taken using a ** b % n: {end_time - start_time:.6f} seconds")

# Validate if both methods yield the same result
if res_pow == res_exp_mod:
    print("Both methods give the same result!")
else:
    print("Results differ!")

위처럼 코드를 구성해서 결과와 수행시간을 확인해봤다. 결과는 똑같이 나왔고 수행시간은 pow()가 확실히 짧았다.

Result using pow(a, b, n): 56225665985167604306618815369520849802796572303399830136522685477533194134297
Time taken using pow(): 0.000007 seconds
Result using a ** b % n: 56225665985167604306618815369520849802796572303399830136522685477533194134297
Time taken using a ** b % n: 0.001160 seconds
Both methods give the same result!

---

Lab Task

3.1. Private key
소수 p, q, e 를 상정하고, n = p * q 라고 하자. 공개키로는 (e, n)을 사용한다. 이 때 비밀 키 d 를 찾아라. 소수 p, q, e 의 값은 아래에 16 진수 값으로 주어진다. 참고) 본 실험에서 사용되는 p, q 값은 큰 값이긴 하지만, 암호 알고리즘의 안전성을 보장할 만큼 큰 수는 아니다. 실험을 간단히 하기 위해서 작게 만든 숫자이며, 실제로는 (128 비트 안전성을 위해서) 적어도 512 비트가 넘는 수를 사용해야 한다.

p = F7E75FDC469067FFDC4E847C51F452DF 
q = E85CED54AF57E53E092113E62F436F4F 
e = 0D88C3

from sympy import mod_inverse

# Given values (hexadecimal to integer)
p = int("F7E75FDC469067FFDC4E847C51F452DF", 16)
q = int("E85CED54AF57E53E092113E62F436F4F", 16)
e = int("0D88C3", 16)

# Calculate n
n = p * q

# Calculate phi(n) = (p - 1) * (q - 1)
phi_n = (p - 1) * (q - 1)

# Calculate d (modular inverse of e mod phi(n))
d = mod_inverse(e, phi_n)

# Print results
print(f"p: {p}")
print(f"q: {q}")
print(f"n: {n}")
print(f"phi(n): {phi_n}")
print(f"e: {e}")
print(f"d: {d}")

 

공개키: (e,n) 여기서 n=p×q

비밀키 d: d×e≡1(modϕ(n)), 즉 e의 모듈러 역원(modular inverse)

위 값을 고려해서 연산작업을 코딩하였다.

 

3.2. 메시지를 암호화 하기

(e, n)이 공개키로 주어진다. 메시지 “A top secret!”를 암호화 하라. (따옴표는 포함하지 않음.) 이를 위하여 ASCII 문자열을 16 진수 문자열로 변환해야 한다. 아래의 파이썬 코드를 이용해서 16 진수 문자열과 ASCII 문자열간의 변환을 할 수 있다.

hex_string = "A top secret!".encode("utf-8").hex() print(hex_string)
# >>> 4120746f702073656372657421
reverted_string = bytes.fromhex(hex_string).decode('utf-8') print(reverted_string)
# >>> A top secret!

공개키는 아래와 같다. 본 실험에서는 암호화가 잘 되었는지 확인하기 위해서 비밀키 d 도 함께 제공한다.

n = DCBFFE3E51F62E09CE7032E2677A78946A849DC4CDDE3A4D0CB81629242FB1A5 
e = 010001 (this hex value equals to decimal 65537)
M = A top secret!
d = 74D806F9F3A62BAE331FFE3F0A68AFE35B3D2E4794148AACBC26AA381CD7D30D

 

# RSA 암호화 예제
from sympy import mod_inverse

# 주어진 공개키와 비밀키
n = int("DCBFFE3E51F62E09CE7032E2677A78946A849DC4CDDE3A4D0CB81629242FB1A5", 16)  # n 값 (16진수 -> 정수 변환)
e = int("010001", 16)  # 공개키 e (16진수 -> 정수 변환, 65537)
d = int("74D806F9F3A62BAE331FFE3F0A68AFE35B3D2E4794148AACBC26AA381CD7D30D", 16)  # 비밀키 d (16진수 -> 정수 변환)

# 원본 메시지
message = "A top secret!"

# 메시지를 16진수 문자열로 변환한 후 정수로 변환
hex_string = message.encode("utf-8").hex()  # 메시지를 UTF-8로 인코딩 후 16진수로 변환
M = int(hex_string, 16)  # 16진수 문자열을 정수로 변환

# 메시지 암호화: C = M^e % n
C = pow(M, e, n)  # Python의 pow() 함수로 지수와 모듈러 연산 수행

# 결과 출력
print(f"원본 메시지: {message}")
print(f"16진수 표현: {hex_string}")
print(f"정수 표현: {M}")
print(f"암호화된 메시지: {C}")

# 메시지 복호화: M_decrypted = C^d % n
M_decrypted = pow(C, d, n)  # 비밀키 d를 사용해 암호문 복호화

# 복호화된 정수를 다시 16진수로 변환한 후 문자열로 변환
decrypted_hex = hex(M_decrypted)[2:]  # 정수를 16진수로 변환 (접두어 '0x' 제거)
decrypted_message = bytes.fromhex(decrypted_hex).decode("utf-8")  # 16진수를 UTF-8 문자열로 변환

# 복호화된 메시지 출력
print(f"복호화된 메시지: {decrypted_message}")

잘 암호화 복호화가 되는 것을 확인하였다.

 

3.3. 암호문을 복호화 하기

주어진 아래의 암호문을 복호화 하라. 복호화 한 평문을 ASCII 로 변환하면 무슨 값이 되는가? 

C = 8C0F971DF2F3672B28811407E2DABBE1DA0FEBBBDFC7DCB67396567EA1E2493F

# RSA Decryption for the given ciphertext

# 복호화에 필요한 값들
n = int("DCBFFE3E51F62E09CE7032E2677A78946A849DC4CDDE3A4D0CB81629242FB1A5", 16)
d = int("74D806F9F3A62BAE331FFE3F0A68AFE35B3D2E4794148AACBC26AA381CD7D30D", 16)
C = int("8C0F971DF2F3672B28811407E2DABBE1DA0FEBBBDFC7DCB67396567EA1E2493F", 16)

# 암호문 복호화: M = C^d % n
M_decrypted = pow(C, d, n)

# 복호화된 정수를 16진수로 변환한 후 ASCII로 변환
decrypted_hex = hex(M_decrypted)[2:]  # 16진수 문자열로 변환 (접두어 '0x' 제거)
decrypted_message = bytes.fromhex(decrypted_hex).decode("ascii")  # 16진수를 ASCII 문자열로 변환

# 결과 출력
print(f"복호화된 정수: {M_decrypted}")
print(f"16진수 표현: {decrypted_hex}")
print(f"복호화된 메시지: {decrypted_message}")

위 코드를 수행하여 복호화하고 ASCII로 변환하니 아래와 같은 결과가 나왔다.

Password is dees라는 결과가 나온다.

 

3.4.전자 서명

Task 3.2 에서 사용한 비밀키와 공개키를 이용하여, 아래의 메시지를 서명해라. (수업시간에는 M 을 해시하여 사용한다고 배웠으나, 여기서는 M 을 hash 할 필요는 없다.)

M = I owe you $2000.
메시지를 살짝 바꾸어서 다시 서명해 보라. 예를 들어 $2000 대신에 $3000으로 바꾸어 볼 수 있다. 두 서명을 비교해 보고 분석하여 보고서에 작성해라.

# RSA Digital Signature Example

# 주어진 공개키와 비밀키
n = int("DCBFFE3E51F62E09CE7032E2677A78946A849DC4CDDE3A4D0CB81629242FB1A5", 16)
e = int("010001", 16)  # 공개키 (65537)
d = int("74D806F9F3A62BAE331FFE3F0A68AFE35B3D2E4794148AACBC26AA381CD7D30D", 16)

# 메시지 정의
message1 = "I owe you $2000."
message2 = "I owe you $3000."

# 메시지를 정수로 변환
M1 = int(message1.encode("utf-8").hex(), 16)
M2 = int(message2.encode("utf-8").hex(), 16)

# 메시지 서명 생성: S = M^d % n
S1 = pow(M1, d, n)
S2 = pow(M2, d, n)

# 서명 검증: M' = S^e % n
M1_verified = pow(S1, e, n)
M2_verified = pow(S2, e, n)

# 결과 출력
print(f"Original message 1: {message1}")
print(f"Signed message 1: {S1}")
print(f"Verified message 1: {M1_verified}")

print(f"Original message 2: {message2}")
print(f"Signed message 2: {S2}")
print(f"Verified message 2: {M2_verified}")

# 메시지 비교
if S1 == S2:
    print("The signatures are the same (not expected).")
else:
    print("The signatures are different as expected.")

아래와 같이 두가지 메세지를 전자서명으로 만들었고 두값을 비교해서 일치하지 않는 것을 확인하는 간단한 코드도 추가해보았다.

 

3.5.서명 검증

Bob 은 Alice 동무로 부터 메시지 M = "Launch a missile."와 서명 S 를 받았다. Alice 의 공개키가 (e, n)이라는 사실은 이미 알고있다. 해당 메시지가 Alice 의 것인지 아닌지 검증하라. 공개키와 서명은 다음과 같다.

M = Launch a missile.
S = 643D6F34902D9C7EC90CB0B2BCA36C47FA37165C0005CAB026C0542CBDB6802F 
e = 010001 (this hex value equals to decimal 65537)
n = AE1CD4DC432798D933779FBD46C6E1247F0CF1233595113AA51B450F18116115

위 서명이 손상되어 마지막 바이트가 2F에서 3F로 바뀌었다고 치자. 즉, 딱 1비트가 변한 것이다. 이 작업을 다시 해보고, 검증 과정에서 무슨 일이 벌어지는지 설명해라.

# RSA Signature Verification Example

# 주어진 공개키
e = int("010001", 16)  # 공개키 (65537)
n = int("AE1CD4DC432798D933779FBD46C6E1247F0CF1233595113AA51B450F18116115", 16)

# 메시지와 서명
message = "Launch a missile."
S_original = int("643D6F34902D9C7EC90CB0B2BCA36C47FA37165C0005CAB026C0542CBDB6802F", 16)
S_corrupted = int("643D6F34902D9C7EC90CB0B2BCA36C47FA37165C0005CAB026C0542CBDB6803F", 16)  # 마지막 바이트 변경

# 메시지 ASCII -> 정수 변환
M = int(message.encode("utf-8").hex(), 16)

# 서명 검증 함수
def verify_signature(S, e, n, original_message):
    # 복호화: M' = S^e % n
    M_decrypted = pow(S, e, n)
    
    # 복호화된 메시지를 16진수 -> ASCII로 변환
    try:
        decrypted_message = bytes.fromhex(hex(M_decrypted)[2:]).decode("utf-8")
    except Exception as ex:
        decrypted_message = f"Decoding error: {ex}"
    
    # 메시지 검증 결과 출력
    print(f"복호화된 메시지: {decrypted_message}")
    print(f"원본 메시지와 일치: {decrypted_message == original_message}")
    return decrypted_message

# 원본 서명 검증
print("원본 서명 검증:")
verify_signature(S_original, e, n, message)

# 손상된 서명 검증
print("\n손상된 서명 검증:")
verify_signature(S_corrupted, e, n, message)

아래와 같은 결과를 기반으로 전자 서명은 매우 민감하다는 것을 알 수 있다. 서명의 단 1비트만 변경되어도 원본 메시지와 일치하지 않게 되어 결과가 일치하지 않다고 나오는 것을 볼 수 있다. 손상된 서명은 검증에 실패하며 이를 통해 데이터 위조나 전송 오류를 감지할 수 있다.

 

---