RSA 암호화 알고리즘
Javascript로 구현하기
RSA의 암호화 순서도는 간단히 다음과 같습니다.
공개키와 개인키는 다음과 같은 과정을 거칩니다.
- 두개의 큰 소수 p와 q를 선택하고, 이들의 곱 n = pq를 계산한다.
- φ(n) = (p-1)⋅(q-1)
- n과 서로소인 e를 선택하고 d⋅e ≡ 1 mod φ(n) 을 만족하는 수 d를 계산한다.
- (n, e)는 공개키로 공개하고, d는 개인키로 보관한다.
그럼 소수는 어떻게 구할까요?
에라토스테네스의 체
- 2부터 구할 값 (위에서는 120) 까지 배수값들을 지웁니다.
- 그런데 지운값은 검사할 필요가 없겠지요?
- 추가로 m = a*b 일 때 a와 b 둘 중 하나는 √n 이하입니다. 즉, √n까지 검사하면 됩니다.
즉, 이전에 지워진 값은 제외하고 2부터 √n까지 배수값들을 지우면 됩니다.
d값을 구하는 방법은?
유클리드 호제법
우선 확장 유클리드 호제법 전에 유클리드 호제법부터..
우선 유클리드 호제법의 정의는 다음과 같습니다.
두 양의정수 a, b ( b > a )에 대하여 b = a⋅q + r, (0 ≤ r < a) 이라 하면 gcd(a, b) = gcd(a, r)
그럼 증명해 보겠습니다.
G = gcd(a, b)
a = G⋅A
b = G⋅B
A 와 B는 서로소
b = a⋅q + r (0 ≤ r < a)
GB = GA⋅q + r
G⋅(B — A⋅q) = r
G⋅A = a
즉, G는 a와 r의 공약수.
B-A⋅q 와 A가 서로소이면 증명 끝
gcd(A, B-A⋅q) = m
m = 1 을 보이면 증명 끝 (m = 1 이면 B-A⋅q 와 A가 서로소)
적당한 정수 k, i
A = m⋅k
B — A⋅q = m⋅i
B = m⋅i + A⋅q = m⋅i + m⋅k⋅q = m⋅(i + k⋅q)
즉, A와 B의 공약수는 m
A, B는 서로소 이므로 m = 1
확장 유클리드 호제법
확장 유클리드의 호제법의 정의는 다음과 같습니다.
두 양의정수 a, b ( b > a )에 대하여 b = a⋅q + r, (0 ≤ r < a) 이라 하면 gcd(a, b) 일때 a⋅x + b⋅y = gcd(a, b) 인 x, y를 구하는 방법
그럼 한번 구해봅시다. 위, 유클리드 호제법을 기억하며 식을 따라갑니다.
gcd(240, 47)
240 = 47⋅5 + 5
5 = 240 + 47⋅(-5)
47 = 5⋅9 + 2
2 = 47 + 5⋅(-9)
= 47 + (240 + 47⋅(-5))⋅(-9)
= 47 + 240⋅(-9) + 47⋅45
= 240⋅(-9) + 47⋅46
5 = 2⋅2 + 1
1 = 5 + 2⋅(-2)
= (240 + 47⋅(-5))+(240⋅(-9) + 47⋅46)⋅(-2)
= 240 + 47⋅(-5) + 240⋅18 + 47⋅(-92)
= 240⋅19 + 47⋅(-97)
1 = 240⋅19 + 47⋅(-97)
x = 19 , y= -97
확장된 유클리드 호제법을 이용하여 (결국 유클리드 호제법에 의한 반복적인 장난질..?에 불과하지만) x, y를 구하는 방법을 알았으니 이걸 그대로 코드로 옮겨봅시다.
다만, 조금 순서가 복잡하여 앞에 왜 이러한 코드가 나왔는지 적은 식을 순서대로 주석에 달았습니다.
암호화와 복호화
고속 누승 알고리즘
암호화 방법은 다음과 같습니다
c = m^e ⋅ mod n
복호화 방법은 다음과 같구요.
m = c^d ⋅ mod n
여기서 c는 복호화된 값. m은 암호화 전의 값이라고 보면 됩니다.
그런데 여기서 문제되는건 m^e 혹은 c^d 입니다.
이 수들은 너무 커서 오버플로우가 일어나고 우선적으로 그냥 계산시 속도가 너무 느립니다.
이를 위해 두가지 방법을 병행합니다.
우선 계산횟수를 줄이는것. 알고리즘적 용어로는 O(n)을 최적화 하는건데.. 지금은 저도 잘 모르기에 그냥 계산횟수를 줄인다고 말하겠습니다~
예시로 3³⁰을 들겠습니다.
- 3³⁰ 은 29번 곱
- (3¹⁵)²은 15번 곱
- ((3⁷)²*3)²은 9번 곱
- (((3³)²*3)²*3)²은 7번 곱
- (((3²*3)²*3)²*3)²은 7번 곱
이런 방법으로 점점 게산횟수를 줄입니다.
그럼 오버플로우를 해결하는 방법은?
모듈러의 성질을 이용합니다.
- (a + b) mod n = (a mod n + b mod n)mod n
- (a — b) mod n = (a mod n — b mod n)mod n
- (a x b) mod n = (a mod n x b mod n)mod n
- 10n mod n = (10 mod n)n mod n
여기서 3번째 곱셈성질을 이용합니다.
예시로 3³⁰mod5를 들겠습니다.
3³⁰mod5 ≡ (((3²*3)²*3)²*3)²mod5
≡ (((3²mod5 ⋅ 3mod5)² ⋅ 3mod5)² ⋅ 3mod5)²mod5
이렇게 계산된다면 오버플로우 걱정도 줄어들지요.
자 이제 소스입니다.
끝 ^^b
