공개키 암호화와 RSA 알고리즘 – 수학으로 이해하는 암호화 원리

[대칭키 암호화 구조]

송신자                          수신자
  │                               │
  │  평문 + 비밀키 K → 암호문      │
  │──────── 암호문 전송 ──────────→│
  │                               │
  │                 암호문 + 비밀키 K → 평문
  │
  └── ⚠️ 문제: 비밀키 K를 어떻게 안전하게 전달하는가?

[비대칭키 암호화 구조]

키 생성: (공개키 Kpub, 개인키 Kpriv) ← 수학적으로 연관된 쌍

송신자                               수신자
  │   수신자의 공개키 Kpub 획득        │
  │   (누구나 알아도 됨)               │
  │                                   │
  │  평문 M + Kpub → 암호문 C          │
  │──────────── 암호문 C 전송 ────────→│
  │                                   │
  │                    암호문 C + Kpriv → 평문 M
  │
  ✅ 공개키는 누구에게나 공개 가능
  ✅ 개인키는 수신자만 보관
  ✅ 키 배송 문제 해결

기본 표기: a ≡ b (mod n)
→ a를 n으로 나눈 나머지가 b임을 의미

예시:
  17 ≡ 2  (mod 5)   → 17 = 5×3 + 2
  23 ≡ 2  (mod 7)   → 23 = 7×3 + 2
  100 ≡ 0 (mod 10)  → 100 = 10×10 + 0

시계 비유:
  지금 10시. 27시간 후는?
  (10 + 27) mod 12 = 37 mod 12 = 1시

[페르마 소정리 (Fermat's Little Theorem)]
p가 소수이고, gcd(a, p) = 1이면:
  aᵖ⁻¹ ≡ 1 (mod p)

예시 (p=7, a=3):
  3⁶ = 729
  729 mod 7 = 1  ✅

[오일러 정리 (Euler's Theorem) – RSA의 직접적 기반]
gcd(a, n) = 1이면:
  aᵠ⁽ⁿ⁾ ≡ 1 (mod n)

여기서 φ(n)은 오일러 피 함수:
  1부터 n까지 중 n과 서로소인 수의 개수

→ RSA는 이 성질을 이용해 암호화→복호화가 원래 메시지로 돌아오도록 설계됨

[소인수분해의 비대칭성]

곱하기 (쉬움 → 단방향):
  p = 61,  q = 53
  n = p × q = 3,233          → 순식간에 계산

인수분해 (어려움 ← 역방향):
  n = 3,233 → p = ?, q = ?   → 시도해봐야 알 수 있음

실제 RSA에서 사용하는 크기:
  RSA-2048: n이 2048비트 (약 617자리 십진수)
  현재 기술로 인수분해 시 수백만 년 이상 소요 (추정)

[RSA-2048 크기 감각]
n ≈ 3,107....(617자리)....2871
    ← 우주의 원자 수가 약 80자리 수 →
    → 그보다 훨씬 큰 수를 인수분해해야 개인키 획득 가능

[RSA 키 생성 예제: p=61, q=53 사용]

─────────────────────────────────────────────
Step 1. 두 개의 큰 소수 p, q 선택
─────────────────────────────────────────────
  p = 61
  q = 53
  (실제: 1024비트 이상의 소수 2개 선택)

─────────────────────────────────────────────
Step 2. n 계산 (공개키와 개인키 공통 사용)
─────────────────────────────────────────────
  n = p × q = 61 × 53 = 3,233
  → n은 공개키와 개인키 모두에 포함
  → n의 인수분해(p, q 역산)가 불가능해야 안전

─────────────────────────────────────────────
Step 3. 오일러 피 함수 φ(n) 계산
─────────────────────────────────────────────
  φ(n) = (p-1)(q-1) = 60 × 52 = 3,120
  → p, q가 소수이므로 φ(pq) = (p-1)(q-1) 성립
  → φ(n)은 절대 공개하지 않음 (개인키 핵심 정보)

─────────────────────────────────────────────
Step 4. 공개 지수 e 선택
─────────────────────────────────────────────
  조건: 1 < e < φ(n), gcd(e, φ(n)) = 1
  → e = 17 선택 (17과 3,120은 서로소: gcd(17, 3120) = 1)
  → 실제 RSA에서 e = 65,537 (2¹⁶+1) 가장 많이 사용
     이유: 이진수로 10000000000000001 → 제곱 반복이 효율적

  공개키 = (e, n) = (17, 3233)  ← 공개해도 됨

─────────────────────────────────────────────
Step 5. 개인 지수 d 계산 (핵심!)
─────────────────────────────────────────────
  조건: d × e ≡ 1 (mod φ(n))
  → 17 × d ≡ 1 (mod 3,120)
  → 확장 유클리드 알고리즘으로 d 계산
  → d = 2,753

  검증: 17 × 2,753 = 46,801
        46,801 mod 3,120 = 1 ✅

  개인키 = (d, n) = (2753, 3233) ← 절대 공개 금지

─────────────────────────────────────────────
Step 6. p, q, φ(n) 삭제
─────────────────────────────────────────────
  → p, q로부터 φ(n) 재계산 가능 → 개인키 d 복원 가능
  → 키 생성 후 p, q, φ(n)은 메모리에서 완전 삭제

# 확장 유클리드 알고리즘 – d 계산
def extended_gcd(a, b):
    """gcd(a, b)와 ax + by = gcd(a, b)를 만족하는 x, y 반환"""
    if b == 0:
        return a, 1, 0
    gcd, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return gcd, x, y

def mod_inverse(e, phi_n):
    """e의 mod φ(n) 역원 계산 → 이것이 개인키 d"""
    gcd, x, _ = extended_gcd(e, phi_n)
    if gcd != 1:
        raise ValueError("역원이 존재하지 않습니다 (e와 φ(n)이 서로소가 아님)")
    return x % phi_n

# 키 생성 전체 과정
def generate_rsa_keys(p, q):
    n = p * q                          # Step 2
    phi_n = (p - 1) * (q - 1)         # Step 3
    e = 17                             # Step 4 (실제론 소수성 검증 후 선택)
    d = mod_inverse(e, phi_n)          # Step 5
    print(f"공개키: (e={e}, n={n})")
    print(f"개인키: (d={d}, n={n})")
    print(f"검증: e×d mod φ(n) = {(e * d) % phi_n}")  # 반드시 1
    return (e, n), (d, n)

public_key, private_key = generate_rsa_keys(61, 53)
# 공개키: (e=17, n=3233)
# 개인키: (d=2753, n=3233)
# 검증: e×d mod φ(n) = 1 ✅

암호화: C ≡ Mᵉ (mod n)

M = 평문 메시지 (숫자로 표현, 반드시 M < n)
e = 공개 지수
n = 두 소수의 곱
C = 암호문

M = 65  (평문)
e = 17  (공개 지수)
n = 3,233

C = 65¹⁷ mod 3,233

65¹⁷을 직접 계산하면 어마어마하게 큰 수가 되지만,
"고속 모듈러 거듭제곱(Fast Modular Exponentiation)" 알고리즘으로
중간 결과를 mod 3,233으로 계속 줄이면서 계산:

C = 65¹⁷ mod 3,233 = 2,790
→ 암호문 C = 2,790

복호화: M ≡ Cᵈ (mod n)

C = 암호문
d = 개인 지수 (개인키)
n = 두 소수의 곱
M = 복원된 평문

C = 2,790 (암호문)
d = 2,753 (개인 지수)
n = 3,233

M = 2,790²⁷⁵³ mod 3,233 = 65 ✅
→ 원래 평문 M = 65 복원 성공!

[수학적 증명]

복호화 결과:
  Cᵈ mod n
= (Mᵉ)ᵈ mod n        [C = Mᵉ mod n 대입]
= Mᵉᵈ mod n

d의 정의: e × d ≡ 1 (mod φ(n))
→ e × d = k × φ(n) + 1  (어떤 정수 k에 대해)

따라서:
  Mᵉᵈ = Mᵏᵠ⁽ⁿ⁾⁺¹ = M¹ × (Mᵠ⁽ⁿ⁾)ᵏ

오일러 정리에 의해: Mᵠ⁽ⁿ⁾ ≡ 1 (mod n)

→ Mᵉᵈ ≡ M × 1ᵏ ≡ M (mod n)  ✅

결론: 암호화(Mᵉ) → 복호화(Cᵈ) = M  항상 성립

# RSA 암호화/복호화 직접 구현 (교육용 – 소규모 소수 사용)

def mod_pow(base, exp, mod):
    """고속 모듈러 거듭제곱 (Fast Modular Exponentiation)
    직접 base^exp를 계산하지 않고 이진 분할로 효율적 계산
    시간복잡도: O(log exp)
    """
    result = 1
    base = base % mod
    while exp > 0:
        # 지수의 마지막 비트가 1이면 현재 base를 곱함
        if exp % 2 == 1:
            result = (result * base) % mod
        exp //= 2          # 지수를 절반으로
        base = (base * base) % mod  # base를 제곱
    return result

def rsa_encrypt(message: int, e: int, n: int) -> int:
    """RSA 암호화: C = M^e mod n"""
    if message >= n:
        raise ValueError(f"메시지({message})는 반드시 n({n})보다 작아야 합니다")
    cipher = mod_pow(message, e, n)
    print(f"암호화: M={message} → C={cipher}")
    return cipher

def rsa_decrypt(cipher: int, d: int, n: int) -> int:
    """RSA 복호화: M = C^d mod n"""
    message = mod_pow(cipher, d, n)
    print(f"복호화: C={cipher} → M={message}")
    return message

# 키 설정 (p=61, q=53으로 생성한 키)
public_key  = (17,   3233)   # (e, n)
private_key = (2753, 3233)   # (d, n)

# 테스트
original_message = 65
e, n = public_key
d, _ = private_key

# 암호화 (누구나 수행 가능 – 공개키 사용)
cipher = rsa_encrypt(original_message, e, n)   # C = 2790

# 복호화 (수신자만 수행 가능 – 개인키 사용)
decoded = rsa_decrypt(cipher, d, n)            # M = 65

print(f"원본 복원 성공: {original_message == decoded}")  # True ✅

# 실제 텍스트 메시지 암호화 (각 문자를 ASCII 코드로 변환)
def rsa_encrypt_text(text: str, e: int, n: int):
    return [rsa_encrypt(ord(ch), e, n) for ch in text]

def rsa_decrypt_text(cipher_list: list, d: int, n: int):
    return ''.join(chr(rsa_decrypt(c, d, n)) for c in cipher_list)

msg = "Hi"
encrypted = rsa_encrypt_text(msg, e, n)
decrypted  = rsa_decrypt_text(encrypted, d, n)
print(f"원문: {msg} → 암호: {encrypted} → 복호: {decrypted}")

[암호화 vs 디지털 서명 비교]

암호화 (기밀성 목적):
  송신자 → 수신자의 공개키로 암호화 → 수신자의 개인키로 복호화
  목적: "오직 수신자만 읽을 수 있게"

디지털 서명 (인증·무결성 목적):
  송신자 → 자신의 개인키로 서명 → 수신자가 송신자의 공개키로 검증
  목적: "이 메시지가 정말 내가 보냈음을 증명"

[디지털 서명 생성 – 송신자]

원본 메시지 M
    │
    ▼ SHA-256 해시
해시값 H = SHA256(M)         예: H = "a3f9..."
    │
    ▼ 개인키(d, n)로 RSA 연산
서명값 S = Hᵈ mod n          예: S = 1847...
    │
전송: (메시지 M, 서명 S)

─────────────────────────────

[디지털 서명 검증 – 수신자]

수신한 (메시지 M', 서명 S)
    │
    ├── M'를 직접 SHA-256 해시
    │   H' = SHA256(M')
    │
    ├── 서명 S를 송신자 공개키(e, n)로 복원
    │   H_from_sig = Sᵉ mod n
    │
    └── 비교: H' == H_from_sig?
           ✅ 일치: 메시지 무결성 + 송신자 인증 성공
           ❌ 불일치: 위변조 또는 다른 송신자

import java.security.*;
import java.security.spec.*;
import java.util.Base64;

public class RsaSignatureExample {

    /**
     * RSA 키 쌍 생성 (2048비트 – 현재 권장 최소 크기)
     */
    public static KeyPair generateKeyPair() throws Exception {
        KeyPairGenerator generator = KeyPairGenerator.getInstance("RSA");
        generator.initialize(2048, new SecureRandom());
        return generator.generateKeyPair();
    }

    /**
     * 메시지에 디지털 서명 생성
     * 내부 동작: SHA-256 해시 → 개인키로 RSA 암호화
     */
    public static byte[] sign(String message, PrivateKey privateKey) throws Exception {
        Signature signature = Signature.getInstance("SHA256withRSA");
        signature.initSign(privateKey);
        signature.update(message.getBytes("UTF-8"));
        return signature.sign();
    }

    /**
     * 디지털 서명 검증
     * 내부 동작: 공개키로 RSA 복호화 → SHA-256 해시와 비교
     */
    public static boolean verify(String message, byte[] signatureBytes,
                                  PublicKey publicKey) throws Exception {
        Signature signature = Signature.getInstance("SHA256withRSA");
        signature.initVerify(publicKey);
        signature.update(message.getBytes("UTF-8"));
        return signature.verify(signatureBytes);
    }

    public static void main(String[] args) throws Exception {
        // 1. 키 쌍 생성
        KeyPair keyPair = generateKeyPair();
        PublicKey  publicKey  = keyPair.getPublic();
        PrivateKey privateKey = keyPair.getPrivate();

        // 2. 서명 생성 (개인키 사용)
        String message = "이 계약서는 홍길동이 작성했습니다.";
        byte[] signatureBytes = sign(message, privateKey);
        System.out.println("서명 생성 완료: "
                + Base64.getEncoder().encodeToString(signatureBytes).substring(0, 40) + "...");

        // 3. 서명 검증 (공개키 사용) – 원본 메시지
        boolean valid = verify(message, signatureBytes, publicKey);
        System.out.println("원본 메시지 검증: " + valid);  // true ✅

        // 4. 변조된 메시지 검증
        String tampered = "이 계약서는 이순신이 작성했습니다.";
        boolean tamperedResult = verify(tampered, signatureBytes, publicKey);
        System.out.println("변조 메시지 검증: " + tamperedResult);  // false ❌
    }
}

① HTTPS 인증서
   → CA가 서버 인증서에 CA 개인키로 서명
   → 브라우저가 CA 공개키로 검증 → 인증서 신뢰

② Git 커밋 서명 (GPG)
   → 개발자 개인키로 커밋에 서명
   → GitHub에서 공개키로 검증 → "Verified" 뱃지 표시

③ JWT (JSON Web Token)
   → 서버가 개인키로 payload 서명 (RS256 알고리즘)
   → 클라이언트/API가 공개키로 검증 → 위변조 방지

④ 코드 서명 (Code Signing)
   → 소프트웨어 배포 시 개발사 개인키로 서명
   → OS가 설치 전 공개키로 검증 → 악성코드 삽입 방지

⑤ 전자 계약서 (공인 전자서명)
   → 법적 효력을 가진 디지털 서명
   → 서명자 개인키 → 공개키 검증으로 신원 확인

[RSA 키 크기와 보안 연도 추정]
RSA-1024: 2010년 이전까지 안전 (현재 사용 금지 권고)
RSA-2048: 2030년까지 안전 (현재 표준)
RSA-3072: 2031년 이후 권장
RSA-4096: 장기 보안용

[고전 컴퓨터 vs 양자 컴퓨터: RSA-2048 인수분해]

고전 컴퓨터 (최고 성능):  수백만 년 이상
양자 컴퓨터 (쇼어 알고리즘): 수 시간 ~ 수 일 (충분한 큐비트 확보 시)

현재 양자 컴퓨터 수준 (2024년 기준):
  IBM Osprey: 433 큐비트 (노이즈 문제로 RSA 해독 불가)
  RSA-2048 해독에 필요한 논리 큐비트: 약 4,000개 이상 (오류 수정 포함 수백만)
  → 현재는 위협 수준 아님, 10~20년 후 잠재적 위협

[RSA vs ECC 보안 동등성 비교]

보안 강도    RSA 키 크기    ECC 키 크기    비율
80 bit       1,024 bit      160 bit       1:6.4
112 bit      2,048 bit      224 bit       1:9.1
128 bit      3,072 bit      256 bit       1:12
192 bit      7,680 bit      384 bit       1:20
256 bit     15,360 bit      521 bit       1:29

→ ECC-256 = RSA-3072와 동등한 보안
→ 키 크기가 작아 연산 속도 빠름 (TLS, 모바일에 유리)
→ TLS 1.3에서 ECDHE가 기본 키 교환 방식으로 채택

[NIST PQC 표준 (2024년 기준)]

최종 표준화 알고리즘:
  ① ML-KEM (CRYSTALS-Kyber)  → 키 캡슐화 (키 교환 목적)
  ② ML-DSA (CRYSTALS-Dilithium) → 디지털 서명
  ③ SLH-DSA (SPHINCS+)          → 해시 기반 서명

기반 수학 문제:
  격자(Lattice) 문제 → 양자 컴퓨터로도 다항 시간 풀이 불가 (현재까지)

현재 전환 전략 (Hybrid 방식):
  TLS 1.3: ECDHE + ML-KEM 동시 사용
  → 고전 컴퓨터 공격 AND 양자 컴퓨터 공격 모두 방어