RSA 암호 편집하기 (부분)

=== 키 생성 과정 ===
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>