사전지식 (정수론)
대칭키 시스템
Key
$p$ : 큰 소수
$e$ : 암호화 키 (홀수)
$d$ : 복호화 키 (홀수)
$ed \equiv 1 \mod p-1$
$\gcd(e, p-1) = 1$
이렇게 3개의 키를 사용한 암호화 알고리즘을 사용한다.
$p$는 큰 소수이기 때문에 홀수임이 자명하다.
$C \equiv m^e \mod p$으로 암호화된 $C$를 구할 수 있다. ($m$은 원본 데이터)
반대로 $m \equiv C^d \mod p$로 복호화할 수 있다.
$m = C^d = (m^e)^d = m^{ed} = m$임을 사용한 심플한 알고리즘이다.
문제점은 메시지를 보내는 sender와 그 메시지를 받는 receiver사이에 $p, e$라는 두개의 키를 공유하면서 남들에겐 공개되면 안된다. ($d$는 $e, p$만 있으면 구할 수 있다.)
이렇게 서로 같은 키를 가지고 있는 것을 대칭키 시스템이라고 한다.
그런데 여기에서 sender가 2명의 receiver에게 메시지를 보내려고 한다면?
$(p_1, e_1), (p_2, e_2)$의 두 쌍의 키가 필요하다.
이를 일반화하면 sender가 $N$명, receiver가 $M$명 있으면 생성해야하는 키는 $2NM$개가 되고 이는 굉장히 많다.
전세계에 컴퓨터가 수십억대가 있는걸 생각하면 현실성이 떨어진다.
게다가 각 키는 적어도 2000bit는 돼야 안전하므로 용량도 많이 차지하게 된다. ($2^{2000}$은 $10^{600}$정도 되는 굉장히 큰 수이다.)
Public Key System
위의 키 개수 문제를 해결하기 위해 Public Key System(공개키 시스템)이 등장했다.
암호화 키 $e$를 대중에게 공개하고 복호화 키 $d$만 개인이 비밀로 가지고 있는 것이다. ($e$로부터 $d$는 알 수 없음)
그렇게 되면 1개의 키로 많은 사람들과 암호화 통신을 할 수 있다.
RSA System
RSA는 이런 Public Key System을 사용한 알고리즘이다.
$p, q$ : 큰 소수 (비밀 키)
$e$ : 암호화 키 (공개 키)
$d$ : 복호화 키
$n = pq$ : 공개 키
$ed \equiv 1 \mod (p-1)(q-1)$ 여기에서 $(p-1)(q-1) = \phi (n)$
RSA도 위의 알고리즘과 유사하게 작동한다.
$C \equiv m^e \mod n$ (암호화)
$m \equiv C^d \mod n$ (복호화)
이렇게 소수를 2개만 쓰더라도 공격하기 굉장히 어려운 암호 시스템이 된다.
$e, n$가 공개돼 있으면 $\phi (n)$을 알아내면 $d$를 알 수 있는거 아닌가요?
$n=pq$으로부터 $(p-1)(q-1)$을 알아낸다는 것과 같다.
$(p-1)(q-1) = pq-p-q+1 = n-p-q+1$
$pq = n$
식 2개에 미지수 $p,q$로 2개이므로 위의 주장이 성립하면 $n$을 소인수분해 할 수 있다는 것과 같다.
소인수분해는 $NP$에 속한다고 했으므로 그런일이 일어나기는 힘들다.
즉 RSA를 공격하기 위해서는 소인수분해 문제를 해결해야한다.
남은 문제
RSA는 상당히 좋은 암호시스템인데 당연하다고 생각하고 넘어간 사실이 있다.
1. 거듭제곱
2. 큰 소수 구하는 법
1번은 암호화 과정중 $m^e$연산을 해야하는데 $e > 2^{2000}$이므로 상당히 큰 수를 제곱해야한다.
이 문제는 사전지식에 있는 분할정복을 이용한 거듭제곱을 사용해서 해결할 수 있다.
2번으로 2000비트가 넘는 큰 소수를 구하는 방법이 있어야한다.
이는 다음시간에 알아볼 예정이다.
'기타 > 암호학' 카테고리의 다른 글
[암호학] 21. Massey-Omura (0) | 2023.02.07 |
---|---|
[암호학] 20. 소수 판정 (Primality Test) (0) | 2023.02.03 |
[암호학] 18. NP-Complete (0) | 2023.01.27 |
[암호학] 17. P, NP (0) | 2023.01.24 |
[암호학] 16. Complexity Classes (0) | 2023.01.20 |