RSA 암호 편집하기 (부분)

== 작동 원리 ==
RSA는 '''큰 소수의 곱셈은 쉽지만, 그 결과를 다시 소인수분해하는 것은 매우 어렵다'''는 수학적 난제를 기반으로 한다.

=== 기본 개념 ===
RSA는 다음과 같은 특징을 가진다:
* '''공개키'''(Public Key): 누구에게나 공개되며, 데이터를 암호화하는 데 사용
* '''개인키'''(Private Key): 자신만 가지고 있으며, 데이터를 복호화하는 데 사용
* 공개키로 암호화한 것은 대응하는 개인키로만 복호화 가능
* 개인키로 서명한 것은 대응하는 공개키로만 검증 가능

=== 키 생성 과정 ===
RSA 키를 생성하는 과정은 다음과 같다:

'''1단계: 두 개의 큰 소수 선택'''
* 서로 다른 두 개의 큰 소수 p와 q를 무작위로 선택한다.
* 예시: p = 61, q = 53<ref>실제로는 수백 자리의 소수를 사용한다. 61이나 53 같은 건 초등학생도 소인수분해할 수 있다.</ref>

'''2단계: n 계산'''
* n = p × q를 계산한다.
* 예시: n = 61 × 53 = 3233
* 이 n이 '''RSA 모듈러스'''(RSA modulus)라고 불리며, 공개키와 개인키 모두에 포함된다.

'''3단계: 오일러 함수 φ(n) 계산'''
* φ(n) = (p-1) × (q-1)을 계산한다.
* 예시: φ(3233) = 60 × 52 = 3120
* φ(n)은 n보다 작으면서 n과 서로소인 양의 정수의 개수를 의미한다.<ref>[[오일러]]가 만든 함수다. 수학자들은 그리스 문자를 정말 좋아한다.</ref>

'''4단계: 공개 지수 e 선택'''
* 1 < e < φ(n)이면서 φ(n)과 서로소인 정수 e를 선택한다.
* 보통 e = 65537 (= 2^16 + 1)을 많이 사용한다.<ref>65537은 [[페르마 소수]]다. 계산이 빠르면서도 보안성이 좋아서 자주 쓰인다.</ref>
* 예시: e = 17

'''5단계: 개인 지수 d 계산'''
* d × e ≡ 1 (mod φ(n))을 만족하는 d를 구한다.
* 즉, d는 e의 모듈러 역원이다.
* [[확장 유클리드 호제법]]을 사용하여 계산한다.
* 예시: d = 2753<ref>왜냐하면 2753 × 17 = 46801 = 15 × 3120 + 1이기 때문</ref>

'''6단계: 키 생성 완료'''
* '''공개키''': (n, e) = (3233, 17)
* '''개인키''': (n, d) = (3233, 2753)
* p, q, φ(n)은 '''반드시 폐기'''해야 한다!<ref>이걸 남겨두면 보안이 뚫린다. 마치 금고를 만든 후 설계도를 버리지 않는 것과 같다.</ref>

=== 암호화 과정 ===
평문 메시지 M을 암호화하여 암호문 C를 만드는 과정:

'''수식:''' C ≡ M^e (mod n)

'''예시:'''
* 평문: M = 123
* 공개키: (n=3233, e=17)
* 암호화: C = 123^17 mod 3233 = 855

이제 누구든 공개키 (3233, 17)을 알면 메시지를 암호화할 수 있지만, 개인키 없이는 복호화할 수 없다!

'''실제 계산 과정:'''
123^17 mod 3233을 직접 계산하는 것은 비효율적이다. 대신 '''제곱-곱셈 알고리즘'''(Square-and-Multiply)을 사용한다:
* 17 = 2^4 + 2^0 = 16 + 1
* 123^17 = 123^16 × 123^1
* 123^2 mod 3233 = 15129 mod 3233 = 1926
* 123^4 mod 3233 = 1926^2 mod 3233 = 2830
* 123^8 mod 3233 = 2830^2 mod 3233 = 2746
* 123^16 mod 3233 = 2746^2 mod 3233 = 2728
* 123^17 mod 3233 = 2728 × 123 mod 3233 = 855

=== 복호화 과정 ===
암호문 C를 복호화하여 평문 M을 복원하는 과정:

'''수식:''' M ≡ C^d (mod n)

'''예시:'''
* 암호문: C = 855
* 개인키: (n=3233, d=2753)
* 복호화: M = 855^2753 mod 3233 = 123

원래 평문 123이 복원되었다!<ref>마법같지만 수학이다.</ref>

=== 왜 작동하는가? ===
RSA가 작동하는 이유는 [[페르마의 소정리]]와 [[오일러 정리]]에 기반한다.

'''수학적 증명:'''
* M^(ed) ≡ M (mod n)임을 증명해야 한다.
* d × e ≡ 1 (mod φ(n))이므로, d × e = 1 + k × φ(n) (k는 정수)
* 따라서 M^(ed) = M^(1 + k×φ(n)) = M × (M^φ(n))^k
* [[오일러 정리]]에 의해 M^φ(n) ≡ 1 (mod n) (M과 n이 서로소일 때)
* 따라서 M^(ed) ≡ M × 1^k ≡ M (mod n)

이 증명은 '''M과 n이 서로소'''일 때 성립한다. 만약 M이 p나 q의 배수라면? 그래도 [[중국인의 나머지 정리]]를 사용하면 증명할 수 있다.<ref>수학자들은 구멍을 남기지 않는다.</ref>