개발
RSA 비대칭 키
마지막 수정
학부시절에 비대칭키에 대해서 배운적이 있었는데, 수학 공식을 외우기만 했지 왜 이렇게 사용했는지는 몰랐다.
클립보드 공유 시스템을 만드는 도중에 갑자기 비대칭 키 알고리즘에 대해서 호기심이 생겼고, 코덱스 선생님께 물어보면서 어떻게 구현되었는지 이해해보았다.
RSA의 목표
RSA는 암호화 하는 쪽과 복호화 하는 쪽의 키를 다르게 지정하고자 하는 것이 목표이다. 키 하나만 가지고 있으면 절대 암/복호화를 할 수 없고 암호화나 복호화중 하나만 할 수 있도록 하는 것이다.
이를 위해 RSA는 아래와 같은 방식을 취한다.
'원문'을 A번 곱해서 C로 나눈 값이 '암호화된 값'.
'암호화된 값' 을 B번 곱해서 C로 나눈 값이 '원문'.
수식으로 보자면 아래와 같다(원문 = N, 암호화된 값 = E)
- 암호화 : E = N^A;(mod;C)
- 복호화 : N = E^B;(mod;C)
위 수식을 보면 결론적으로 N^{AB} mod C=N 이다.
이를 만족하는 A, B, C를 찾기 위해 많은 수학적 원리가 들어간다.
오일러 정리
RSA에는 오일러 정리가 핵심이다.
오일러 정리는 오일리거 발견한 법칙이고, 아래와 같다.
두 소수 p, q가 있다. 두 소수를 곱한 C가 있고, 각 소수에서 1을 빼서 곱한 (p-1)(q-1)가 있다고 하자.
이때 N에 (p-1)(q-1)만큼 거듭제곱한 후 C로 나누어서 나온 나머지는 1이다.
N^{(p-1)(q-1)};(mod;C)=1
잘 생각해보면 나머지가 1이라는 말은, 해당 값에 N만큼 한 번더 곱하면 나머지가 N이 나온다는 말과 같다.
N^{(p-1)(q-1)}\times N;(mod;C)=1 \times N = N
그렇다는 건 d에 + 1을 한 후 C로 나눈 나머지를 구하면 N이 나오게 된다.
N^{(p-1)(q-1)+1};(mod;C)= N
이것이 오일러 정리이다.
이 내용을 보면, 오일러 정리를 활용해서 RSA를 구현할 수 있을 것 같지 않은가?
우리가 구해야 할 것
우리는 아래 수식에서 A, B, C를 구해야 한다.
- 암호화 : E = N^A;(mod;C)
- 복호화 : N = E^B;(mod;C)
오일러 정리를 통해 나온 수식은 이것이다.
- N^{(p-1)(q-1)+1};(mod;C)= N
그렇다면,
- C : 소수 p, q를 곱해서 금방 만들 수 있다.
- A, B : 위 소수 p, q를 이용한 (p-1)(q-1)+1 의 값에서 A, B를 만들어 내야 한다.
C는 구했고, A와 B를 구해야 한다.
A, B를 어떻게 구할까?
(p-1)(q-1)+1과 서로소인 값을 하나 찾아내면 된다.
왜 서로소여야 하는지 알아보자.
A\times B = (p-1)(q-1)+1
A\times B - (p-1)(q-1) = 1
이 상태에서는 A\times B와 (p-1)(q-1)의 차이가 1이 나야한다.
그렇다면 만약 A가 (p-1)(q-1) 와 최소공약수를 2를 가지고 있다고 가정해보자.
그렇다면 A\times B는 2의 배수이고, (p-1)(q-1)도 2의 배수이다. 그래서 A\times B와 (p-1)(q-1)의 차이는 항상 2의 배수가 된다.
하지만 A가 서로소 일 때만 A\times B가 (p-1)(q-1)와의 차이가 1이되는 B를 찾을 수 있다.
이 방법을 이용해 (p-1)(q-1)와 서로소인 A를 찾고 \frac{(p-1)(q-1)+1}{A}를 통해 B를 찾을 수 있다.
공개키, 비밀키
자, 이제 우리가 구하고자 하는 값은 다 더했다.
이제 우리가 구한 A, B, C를 암호화 용인 공개키와 복호화 용인 비밀키로 분류해야한다.
- 공개키 : C(나누는 수), A(지수)
- 비밀키 : C(나누는 수), B(지수)
혹시, 공개키를 통해서 B를 유추할 수는 없을까?
컴퓨터는 소수를 곱하는 것은 쉽지만, 곱해진 수에서 어떤 소수가 곱해졌는지 찾기는 매우 어렵다.
C는 이미 곱해진 수이기에 두 소수를 찾아내기는 매우 어렵다. 특히 A, B는 C를 만들어낸 소수를 통해 만들어지고, 소수에 대한 정보도 없기 때문에 C를 구성한 소수를 찾기 어렵다.
이를 통해 공개키는 모두에게 공개해도 되는 키가 되게 된다.
서명
서명할 때는 데이터는 공개되어도 되지만, 데이터의 출처를 확실하게 하는 것이 목표이다.
이때는 비밀키로 암호화하고 공개키로 복호화한다. 비밀키는 한 곳에만 존재하므로 데이터의 출처가 명확해지고, 공개키는 노출되어 있으므로 누구나 이 데이터의 출처를 검증할 수 있다.