RSA는 큰 수의 소인수분해가 어렵다는 점을 이용했으며 현재 https를 포함해 전자상거래에서 가장 널리 쓰이는 알고리즘입니다. 로널드 라이베스트(Ron Rivest), 아디 샤미르(Adi Shamir), 레너드 애들먼(Leonard Adleman)의 연구에 의해 체계화되었으며, RSA라는 이름은 이들 3명의 이름 앞글자를 딴 것입니다.
먼저 RSA가 뭔지 순서대로 알아가 봅시다.
공개키와 개인키는 각각 두 정수 n, e와 n, d로 이루어져 있는데
n, e, d를 구하는 방법은 아래와 같습니다.
n
임의의 두 소수 p, q를 정합니다.
n은 p와 q의 곱입니다. n = p * q
Φ(n)은 p와 q에서 각각 1을 뺀 값의 곱입니다. Φ(n) = (p-1) * (q-1)
e
e는 1과 Φ(n)사이의 Φ(n)과 서로소인 값입니다.
d
e * d한 값이 Φ(n)로 나눴을 때 1과 합동인 수가 d입니다. 즉 e mod Φ(n)의 모듈러 역수가 d입니다.
정수론에서 합동이란 어떤 수로 나눴을 때 나머지가 같은 두 수를 합동이라 합니다.
키에 이용될 n, e, d를 모두 구했습니다.
이제 이 정수들이 어떻게 키로 이용되는지 알아봅시다.
암호화
먼저 암호화의 수식은 아래와 같습니다
c = m^e mod n
mod는 modulo연산으로써 나머지연산입니다.
m은 보내고 싶은 메시지입니다. 컴퓨터상의 모든 정보는 정수로 표현할 수 있단 것은 다들 아시겠죠?
하지만 이때 중요한 건 m은 n보다 작은 숫자여야 한단 겁니다. 이를 위해 따로 변환법도 있는데 이 변환법은 복호화를 하는 쪽에게도 미리 알려져 있어야 합니다. 이중보안을 위해 변환법도 상당히 복잡하게 이루어져 있다네요.
위에서 나온 결과인 c를 상대에게 보냅니다.
복호화
식은 아래와 같습니다
m = c^d mod n
practice
이제 직접 정수를 대입해 실제로 잘 작동하는지 확인해 봅시다.
p와 q를 각각 7,11이라 하겠습니다.
그럼 n은 77, Φ(n)은 60이겠네요.
e는 17이라 하겠습니다.
d는 17 * d mod 60 의값이 1이 나오게 하는 값이니 53이 되겠네요
필요한 n, e, d를 모두 구했습니다.
이제 보내고 싶은 메시지가 4라 정수화 됐다고 가정하고 암호화해 보죠.
4^17 mod 77
계산하면 16이네요.
그럼 이제 이를 복호화 해봅시다.
16 ^53 mod 77
암호화했던 4가 잘 나오는 모습이네요.
그럼 위 방식이 작동하는 이유를 수학적으로 증명하고 통신보안에 써도 될 만큼 안전한 지에 대해 이야기해 봅시다.
증명에 필요한 정리들
아마 이 글을 읽고 계신 분들이 궁금한 점은 d를 구하는 방법, 암호화를 복호화로 풀 수 있는 이유 등이 있을 텐데 이를 알기 위해 아래와 같은 순서를 통해 설명해 보겠습니다.
- 확장 유클리드 호제법으로 소수 모듈로 연산에서 곱하기 역원 찾기
- 페르마 소정리를 이용하여 소수 모듈로의 지수 연산 역원 찾기
- 오일러 정리를 이용하여 일반 모듈로에서 지수 역원 찾기
모듈러 역원 d구하는 법
d를 구하는 방법은 아래와 같은 코드로도 구해볼 수 있을 겁니다.
d = 0
while True
if e*d % phi_n == 1:
break
d += 1하지만 이렇게 하면 e와 n이 큰 수 일 때는 연산량이 정말 많아질 것입니다. 위 practice에서도 p와 q를 7,11로 했을 때 d가 53이 나왔던 것과 일반적으로 p와 q가 512bit 사이즈인 것을 생각한다면 키하나 만드는데 몇 백 년을 기다려야 합니다.
위에서도 말했듯이 d는 e의 Φ(n)에 대한 모듈러 역수입니다.
즉 위 세 가지 방법 중 첫 번째 방법을 안다면 쉽게 구할 수 있습니다.
어떻게 하는건지 알아봅시다.
미션 : a mod Φ(n)의 역원 x를 구해봅시다.
ax mod Φ(n) = 1 이여야 할 겁니다.
위 식은 아래와 같이 나타낼 수 있습니다.
ax = kΦ(n) + 1
ax는 Φ(n)로 나눴을 때 나머지가 1이 나오므로 당연하죠.
그럼 식을 다시 아래와 같이 바꾸고 편의상 Φ(n)를 N라 적겠습니다.
ax - kN = 1
한번더 -k를 y로 치환하면,
ax + Ny = 1
위 식을 보면 베주 항등식처럼 보입니다.(베주항등식이 무엇인지는 다음 포스트 참고 https://dimenchoi.tistory.com/47)
이 식이 정수해(x, y)를 가지려면 우변이 a와 N의 최대공약수의 정수 배여야 합니다. 하지만 어떤 정수를 곱해서 결과가 1이 나오는 값은 1*1 밖에 없죠.
즉 gcd(a, N) = 1 일 때만 다른 말로 a와 N이 서로소 일 때만 모듈러 곱셈의 역원이 존재합니다.(x가 a의 역원 즉 우리가 구하려는 d이므로)
a에 e를 x에 d를 대입해봅시다.
그러면 gcd(a, N) -> gcd(e, Φ(n)) 가 되죠
그리고 위 e값의 조건을 설명할 때 e와 Φ(n)은 서로소였죠. 즉 gcd(e, Φ(n)) = 1 입니다. 이에 e의 모듈러 역원 d가 존재한다는게 입증 됐네요.
그러면 ed + Φ(n)y에서 e와 Φ(n)는 알고있고 d,y를 구해야합니다.(실제론 d만 알면되죠)
그리고 이는 확장된 유클리드 호제법을 사용해 구할 수 있습니다.
그럼 저희는 처음의 알고리즘보다 훨씬 적은 연산만으로 e mod Φ(n)의 역수 즉 d를 얻을 수 있습니다.
암호화 된 값이 복호화 되는 이유
다음은 암호화한 걸 복호화 식으로 풀 수 있는 이유를 알아봐야겠죠.
식으로 빠르게 알아봅시다.
먼저 암호화 복호화 식을 다시 가져오겠습니다.
c = m^e mod n
m = c^d mod n
이제 증명하자면
c^d ≡ (m^e)^d ≡ m^(ed) ≡ m ^ (1 + kΦ(n)) ≡ m mod n
식을 보면 두 가지 의문이 드실 겁니다.
"암호화 복호화식에선 등호고 증명식에선 합동기호인데 괜찮나?"
이 때문에 위에서 m은 n보다 작아야 한다고 했던 겁니다.
위 증명식에 의하면
m ≡ c^d mod n
가 되는데 m이 n보다 작다면 m의 값이 합동식이든 등식이든 달라질 일은 없으니 말이죠.
다음으로 막히실 부분이
m ^ (1+kΦ(n)) ≡ m mod n 이 식일 텐데요.
이를 위 3가지 정리 중 2,3번째 줄 정리를 이용해 각각 증명할 수 있습니다.
증명에 필요한 정리들은 아래에 기술되어있습니다.
m ^ (1+kΦ(n)) ≡ m mod n 증명
페르마 정리를 사용해 먼저 증명해 보겠습니다.
페르마 정리를 이용하려면 mod n을 mod p, mod q로 각각 나눠 증명해야 하는데요.
m ^ (1+kΦ(n))를 풀어보면
m * m ^ k(p-1)(q-1)
m * (m^(p-1))^(k(q-1))이 됩니다.
여기서 페르마 정리를 통해 m^(p-1) ≡ 1 mod p 이므로 페르마 정리식에서 양변에 k(q-1) 제곱을 하고 m을 곱하면
(모듈러 연산의 성질에는 "합동인 두수에 같은 수를 거듭제곱해도 그대로 합동이다." 가 있습니다.)
m * (m^(p-1))^(k(q-1)) ≡ m * 1^(k(q-1)) ≡ m mod p 가 성립하게 됩니다. 이를 q에 대해서도 똑같이 진행하면
m * (m^(q-1))^(k(p-1)) ≡ m * 1^(k(p-1)) ≡ m mod q 가 됩니다.
그리고 여기서 위에 rsa를 증명하던 부분을 상기시켜 드리면 아래와 같습니다.
c^d ≡ (m^e)^d ≡ m^(ed) ≡ m ^ (1 + kΦ(n)) ≡ m mod n
m^(ed) ≡ m ^ (1 + kΦ(n)) ≡ m mod n
m * (m^(p-1))^(k(q-1)) ≡ m * 1^(k(q-1)) ≡ m mod p
m * (m^(q-1))^(k(p-1)) ≡ m * 1^(k(p-1)) ≡ m mod q
이므로
m^(ed) ≡ m mod p, m^(ed) ≡ m mod q가 됩니다.
p | m^(ed) - m 이고 q | m^(ed) - m이고 gcd(p, q)=1이므로("|"기호는 우항이 좌항의 배수라는 뜻입니다.)
pq도 m^(ed) - m을 나눈다는 것은 자명하죠.
어떤 수 a가 p와 q의 배수인데 p와 q가 서로소이면 a는 pqk와 같이 표현할 수 있고 이는 pq | a라는 뜻이니 말이죠.
이에 따라 m^(ed) ≡ m mod pq 가 됩니다. 하지만 pq = n이었죠.
즉 c^d ≡ (m^e)^d ≡ m^(ed) ≡ m ^ (1 + kΦ(n)) ≡ m mod n가 성립하므로 rsa의 증명이 끝나게 됩니다.
정리
페르마의 소정리부터 뭔지 알아보면
a가 정수이고 p가 소수이고 p가 a의 배수가 아닐 때
and
a^p 가 a와 p에 대해 합동이며 a 가 0이 아닐 때a^(p-1)은 1과 p에 대해 합동이다.
간단히 말해 p가 소수이고 a와 p가 서로소일 때
a^(p-1) ≡ 1 mod p라는 말입니다
차례대로 증명해 보죠
<정리 1>
a,2a,3a,4a,..., (p-1) a
총 (p-1) 개의 정수가 있을 때 위 수들을 p로 나눴을 때 나머지는 모두 다릅니다.<증명 1>
귀류법을 이용해 보죠
p로 나눴을 때 나머지가 같은 두수 ma, na이 있다 합시다.
이 말인즉슨, ma = pQ + r. , na = pQ` + r과 같이 표현할 수 있겠죠.
두식을 빼면
a(m-n) = p(Q-Q`)
따라서 a(m-n)은 p의 배수이죠.
하지만 위 정리의 조건에서 a는 p의 배수가 아니고 m-n이 p보다 작다는 사실은 자명하므로 m-n 역시 p의 배수가 아니죠.
이는 모순이므로, 나머지가 같은 ma, na는 존재하지 않습니다.<정리 2>
(p-1)! * a^(p-1) 은 (p-1)! 과 p에 대해 합동입니다.<증명 2>
정리 1에서 a,2a,3a,4a,..., (p-1) a를 p로 나눴을 때 나머지가 전부 다르다 했죠. 이는 다르게 해석하면 해당 수들을 p로 나눴을때 나머지가 1부터 p-1까지 전부 나타낸다고 이해할 수 있습니다.
따라서 a,2a,3a,4a,..., (p-1) a 즉, (p-1)! * a^(p-1)과 (p-1)! 이 서로 p에 대해 합동이란 것은 자명하죠.<정리 3>
a^p는 a와 p에 대해 합동입니다.<증명 3>
p와 (p-1)! 은 공통된 소인수가 없으므로 서로소이죠.
따라서 합동식의 양변을 (p-1)로 나눌 수 있습니다.그럼 결과적으로 a^(p-1)와 1은 p에 대해 합동이라는 식이 나옵니다.
다음은 오일러 정리입니다. 오일러 정리는 페르마의 소정리의 일반화한 버전이라고 생각하시면 됩니다.
a와 m이 서로소일 때
a^(Φ(m)) ≡ 1 mod m
Φ(m) : m과 서로소인 수의 개수
증명입니다.
<정리 1>
m과 서로소인 모든 수를 모아둔 집합 N이 있습니다. N : {x_1, x_2,.. x_n | 1 <=x_i <m}
그리고 n의 각 원소에 a를 곱한 집합 aN이 있습니다. aN {x_1*a, x_2*a,... x_n*a | 1 <=x_i*a <=m}
두 집합은 순서를 무시하면 mod m의 관점에서 같은 집합입니다.(즉 합동입니다.)
x_n! * a^n ≡ x_n! mod m<증명 1>
N의 모든 원소는 m으로 나눠지지 않는 것은 자명합니다. m과 서로소만 모아둔 집합이기 때문이죠.
a 또한 m과 서로소입니다.
따라서 m과 x_i * a는 서로소입니다.
즉 aN 또한 m과 서로소만 모아둔 집합입니다.
따라서 N과 aN과 순서만 다른 mod m의 관점에서 같은 집합입니다.<정리 2>
aN의 원소들 중 합동인 두 원소는 없다.
x_i * a!≡ x_j * a mod m<증명 2>
귀류법을 이용하겠습니다.
x_i * a ≡ x_j * a mod m 라 가정합시다.
위 합동식은 즉 m | x_i * a - x_j * a를 의미하고 a로 묶으면
m | a(x_i - x_j)가 됩니다.
a와 m은 서로소이므로
m | x_i - x_j가 되는데
x_i와 x_j는 모두 1 이상 m미만인 수 이므로 x_i - x_j가 m미만의 수라는 것은 자명하죠.
즉 x_i-x_j의 값은 0이 될 수밖에 없는데 x_i와 x_j는 서로 다른 수를 집합에서 뽑은 것이므로 모순이 발생합니다.
그럼 이제 의문이 생기죠.
"그럼 서로소의 개수는 어떻게 구하는데?"
그것이 바로
위에서 사용한 함수 Φ, 오일러의 phi함수입니다.오일러는 서로소의 개수를 아래와 같이 정의했습니다.
p가 소수일 경우
1 Φ(p) = p-1
2 Φ(p^k) = p^k - p^(k-1)p가 합성수 일경우
3 if gcd(m, n) = 1, Φ(mn) = Φ(m)Φ(n)
물론 범위는 1부터 인자값입니다.증명해 보죠.
1,2번은 아마 쉽게 이해하실 거라 생각합니다.
1번의 경우 당연히 1~p사이의 p와 서로소인 수는 p를 제외한 전부이니 p-1이고
2번의 경우 p는 소수이므로 p와 서로소가 아닌 수는 다음과 같은 수이겠죠. p,2p,3p,4p,5p,6p..
저 수는 어디까지 이어질까요? 저 수는 p^(k-1) p까지 이어질 겁니다. p^(k-1) p가 바로 p^k이기 때문이죠.
저 수들을 제외한 모든 수들은 p^k와 서로소이겠죠.3번이 아마 이해하기 어려운 부분이실 겁니다.
3번을 증명하는 방법에는 여러 가지가 있는데, 이해하기 쉬운 거로 설명하자면
1부터 mn까지 있는 집합을 아래와 갗이 테이블 형태로 표현해 보겠습니다.
1 m+1 2m+1 . . . (n-1)m
2 m+2 2m+2 . . . (n-1)n + 2
3 m+3 2m+3 . . . (n-1)n + 3
.
.
.
m 2m 3m . . . nm테이블에서 r번째 행의 값은 전부 km + r의 형태입니다.(0 <= k <= n-1).
이때 m과 r의 최대 공약수를 g라 하겠습니다. g = gcd(m, r)
g가 2 이상일 때 즉 m과 r이 서로소가 아니면 유클리드 호제법에 의해 gcd(km+r, m)도 공약수가 있다 할 수 있습니다.
km+r % m = r 이기 때문이죠. 그럼 km+r과 m이 서로소가 아니란 뜻이니, 해당 행의 값들은 모두 mn과 서로소가 아니게 됩니다.
이러한 행은 m - Φ(m), 즉 m과 서로소가 아닌 수만큼 있겠죠.반대로 m과 r이 서로소 즉 g가 1이면 바로 위에서 말했 듯 km + r과 은 서로소입니다.
그럼 해당 행에서 n과 서로소인 수는 mn과도 서로소이겠죠.
그런데 저희는 m과r이 서로소인 행이 Φ(m)만큼 있단 걸 압니다. 그럼 해당 행들에서 n과 서로소인 값이 n게임을 보인다면 오일러 phi함수의 세번째 줄이 설명되겠죠.
그럼 저희는 이제 해당 행에서 n과 서로소인 수가 n개임을 보여야 합니다.먼저 m과 r이 서로소인 행의 형태는 아래와 같습니다.
r, m+r, 2m+r, ... , (n-1)m+r
m과 n이 서로소이므로 위 수들을 mod n 하면 0부터 n-1까지의 수가 하나씩 나오게 됩니다.
이는 페르마 정리에서 증명 1을 통해 증명할 수 있습니다.gcd(x+kn, n) = gcd(x, n)이므로 mod n 한 값이 n과 서로소라면 원래 값도 n과 서로소입니다.
mod n한 값이 0부터 n-1까지의 수였으므로 n과 서로소한 값이 Φ(n) 개란 것은 자명하죠.따라서 오일러 정리의 세 번째 줄 Φ(mn) = Φ(m)Φ(n)이 성립하게 됩니다.
이제 신뢰성에 대해 얘기해 보자면 먼저 해커는 n과 e를 알고 있습니다.
n은 pq이고 e는 e는 1과 Φ(n) 사이의 Φ(n)과 서로소인 값이었죠.
해커가 알면 안 되는 값은 d였죠.
d는 e의 Φ(n)에 대한 모듈러 역원이었고요.
하지만 저희가
- 확장 유클리드 호제법으로 소수 모듈로 연산에서 곱하기 역원 찾기
부분을 할 때 일일이 d를 찾아보는 것을 찾아보는 것은 몇백 년이 걸린 다했죠.
확장 유클리드 호제법으로 찾을 때는 Φ(n)값도 알아야 하니 당연히 불가능하고요.
그럼 n이 pq이므로 그냥 이 둘을 소인수분해하면 안 되냐고요?
뭐 작은 수라면 가능하겠지만 위에서 말했듯 p와 q는 각각 512비트의 수입니다. 즉 2^512의 크기라는 것이죠. 물론 최대치가 저 값이니 그보다는 조금 더 작겠지만요. 구글창에 소수 개수를 치면 아래와 같이 나오는데
뭐 저는 10^27과 2^512 중 뭐가 더 큰지는 모르겠지만, 2^512가 더 크다는 가정하에 컴퓨터에 모든 소수를 입력하고
(2^512 = 16^128 이므로 2^512가 훨씬 크네요)
어떤 두 수를 곱해 값이 n인지 확인하는 알고리즘을 이용한다면 16352460426841680446267399^2만큼 곱을 해봐야 하는데 얼마나 걸릴지는 잘 모르겠지만 엄청 오래 걸리니 rsa를 사용하겠죠?
마무리
증명하는 데에만 해도 엄청 어려웠는데 무에서 이 아이디어를 떠올렸다는 것이 정말 경이롭네요..
틀린 부분이 있으면 지적해 주시면 감사드리겠습니다.
추가로 오일러 정리 세 번째 줄에서 여러 가지 방법이 있다 했는데 나머지 하나는
위 영상에서 설명하는데 수학지식이 부족한 저는 bijection함수를 선언하는 데에 있어 저렇게 막 선언해도 되는지가 이해가 안돼서 설명해드리지 않았습니다. 만약 아시는 분이 있으시면 설명부탁드립니다.
또 제가 이 글을 쓰는데 많이 참고한 채널이라 같이 시청하시면 이해하는데 한결 수월하실겁니다.
'수학' 카테고리의 다른 글
| 유클리드 호제법 증명 (0) | 2023.02.23 |
|---|