대칭 키의 한계
빠르게 키를 암호화할 수 있고 안전하지만, 당사자 간에 안전하게 키를 공유할 방법을 마련하기 어렵다. 또한 사람이 많아질수록 관리해야 하는 키의 개수도 늘어난다.
Public key cryptosystem
공개 키 암호화 시스템은 diffie-hellman key exchange 라고도 부른다.
공개 키와 비밀 키는 항상 쌍으로 존재한다. 공개 키는 당사자가 아닌 대상에게 공개해도 된다.
- 공개 키를 알더라도 비밀 키를 유추할 수 없어야 한다.
- 현재의 컴퓨터 수준으로 해결하기 어려운 문제(DLP 등)에 기반을 두고 있어야 한다.
PQC란
post quantum cryptography(양자내성암호), 양자컴퓨터로 풀어도 효율적으로 해결하기 어려울 만큼 복잡한 문제를 말한다.
public key infrastructure
공개 키를 사용하기 위해 필요한 인프라(정책, 소프트웨어, 프로세스 등)를 말한다.
- Digital Certificate(X.509) 인증서
사이트를 검증해주는 인증서이다.
Root CA
웹사이트의 인증서 중 최상단에 있는 인증서를Root CA라고 한다.
인증서는 한 가지만 존재하는 것이 아니고 계층 구조로 존재하는데, 이 중 root CA는 운영체제 등 신뢰할 수 있는 곳에서 발급받는다.
따라서 인증서는 웹사이트에 종속적인 것은 아니다.
asymmetric cryptography
public-key cryptography
누구나 공개키를 쓸 수 있지만, 공개 키에 대응되는 private key를 가진 당사자면 데이터를 복원할 수 있다. (computationally infeasible)
따라서 기밀성을 지키기 위해 공개키로 암호화하고 비밀키로 복호화한다. 비밀키로 암호-공개키로 복호하는 전자서명과는 반대이다.
공개 키를 암호화할 때 RSA를 사용하면 암호, 복호 알고리즘을 하나로 통일할 수 있다. 차이점은 암호화 시 인풋은 공개 키, 복호화 시 인풋은 비밀 키라는 점이다.
public-key cryptosystem
공개 키 암호화에는 여러 가지 알고리즘이 쓰인다.
| 알고리즘 이름 | 암호화/복호화 | 전자서명 | 키 교환 |
|---|---|---|---|
| RSA | yes | yes | yes |
| 타원곡선 | no | yes | yes |
| 디피헬만 | no | no | yes |
| DSS | no | yes | no |
공개 키에는 다음과 같은 요구사항이 따른다.
- 암호를 만들어내기 쉬워야 한다.
- computationally infeasible
- trap-door one-way function
Y = f(x)의 Y값은 쉽게 알아낼 수 있지만 Y값과 f의 역함수로 x를 알아내기 어려워야 한다.
RSA
n이라는 숫자가 큰 소수 두 개의 곱으로 이루어졌을 때 해당 소수를 찾아내는 문제를 factoring problem 이라고 한다. RSA는 이 문제의 어려움에 기반하여 만들어졌다.
RSA 계산
공개키는 상수 n과 카 e, 비밀 키는 d로 나타낸다.
e는 1보다 크고 Φ(n)보다 작은 서로소 중 아무거나
d는 e^(-1) mod Φ(n)
암호화 시 M < n 인 평문 M에 대하여 cipher text C = M^e mod n,
복호화 시 M = C^d mod n 으로 계산한다.
계산 예제
p=7, q=11 -> n=77
Φ(n) = (p-1)(q-1) = 6*10 = 60
e는 1보다 크고 Φ(n)보다 작으면서 Φ(n)과 서로소인 수를 정한다.
예시로는 7이라고 하고 계산해보자.
d = e^(-1) mod Φ(n) = 7^(-1) mod 60
7^(-1) mod 60 구하기
역원을 x라고 할 때 7x mod 60 = 1이다.
이것을 베주 항등식으로 나타내면 7x + 60k = 1이 된다.
확장 유클리드 호제법을 활용해서 gcd(7, 60)을 구해보자.
유클리드 계산
60 = 8 * 7 + 4 (7을 살림)
7 = 1 * 4 + 3 (이전 차수의 나머지 4를 가져온다)
4 = 1 * 3 + 1
3 = 3 * 1 + 0(나머지가 0이므로 종료한다, 이 식은 쓰지 않음)
3 = 7 - 4 이므로 4 = (7 - 4) + 1, 1 = 2*4 - 7
또한 4 = 60 - 8*7 이므로 이를 다시 대입하면
1 = 2(60 - 8*7) - 7 = 2*60 - 16*7 - 7 = -17 * 7 + 2 * 60
따라서 역원은 -17이고, 이를 양수로 고치면 43이 된다.
따라서 d = 43
m은 8이라고 가정하면 cipher c = 8^7 mod 77 = 57
복호화 시 m = 57^43 mod 77 = 8 이 된다.
RSA의 구조
RSA는 sender라는 구조로 이루어진다.
sender에서는 p, q 선정, 공개키와 비밀키 선정, 이후 암호화 작업 등을 맡는다.
RSA 정확성 검증
m = C^d mod n 에 대해 m = m^(e*d) 가 증명되어야 한다.
m = C^d mod n 에서 gcd(m, n) = 1인 경우와 아닌 경우로 나누어 검증할 수 있다. 공개키 암호화(1) 영상 참고.
모듈러에서 지수 연산을 효율적으로 하는 방법
모듈러 연산에서 대상이 되는 수가 거듭제곱일 경우 거듭제곱을 2의 제곱 단위로 끊어서 계산하면 편하다.
예를 들어 7^5 mod n 이라면 7^4 * 7^1 mod n 으로 계산한다.
square and multiply
초기 f값은 1로 두고 지수를 binary로 변환한 다음 각 비트값을 이용하여 이미지의 for loop를 돌리는 방법이다.
예를 들어 7^5 mod 11 을 구한다고 해보자. 5 = 101(2)이므로
- f=1, k(i)=1 -> f=1*1*7 = 7
- f=7, k(i)=0 -> f=7*7 = 49 = 5 (mod 11)
- f=5, k(i)=1 -> f=5*5*7 = 10 (mod 11)
a^k mod n 에서 k를 2진수로 나타낸 후
f*f*(각 자리의 비트가 1인 경우에는 a) 를 반복해서 계산을 간략하게 할 수 있다.
Diffie-Hellman 키 교환
가장 처음으로 만들어진 공개 키 알고리즘이다.
Alice와 Bob이 서로 공개 키를 주고받는다고 하자.
앨리스는 비밀 키 a, 공개 키 g^a를 가진다.
밥은 비밀 키 b, 공개 키 g^b를 가진다.
두 사람이 서로 공개 키를 주고받은 다음 각각 자신의 비밀 키만큼 제곱해주면 둘 모두 같은 값인 g^ab를 얻는다.
만약 공격자가 이 둘 사이에서 공개 키를 빼돌리고 다른 값을 전달한다면 두 사람은 값이 달라졌다는 사실을 알아차릴 수 없다.
이를 위해 필요한 것이 인증서인데, 자신이 전달받은 공개 키가 인증서 내에 기록된 것과 다를 경우 보안이 지켜지지 않은 것으로 판단한다.
ElGamal
DLP의 어려움과 랜덤성을 기반으로 한 암호화 방식. 암호화와 전자서명에 모두 활용할 수 있다.
