1. 비대칭 키 암호화 소개
개인 키와 공개 키를 한 쌍으로 암호 키를 구성
- Private key : 개인만 알고있는 개인 키
- Public key : 타인에게도 공개되는 공개 키
1-1. 응용 분야
- 비밀 메시지
- 누군가의 public key 로 암호화한 메시지는 그 사람의 private key 로 풀 수 있음
- 전자 서명
- 누군가의 public key 로 풀리면 그 사람의 private key 로 암호화한 것이라는 증거
1-2. 대칭 키 and 비대칭 키
- 개념의 차이
- 대칭 키 : 비밀을 서로 공유
- 비대칭 키 : 각자 비밀로 보존
- 키의 구성
- 대칭 키 : 공유되어있는 비밀 키
- 비대칭 키 : 공유되어있는 공유 키 + 공유되지 않은 개인 키
- 키의 수
- 대칭 키 : \(\frac{n(n-1)}{2}\)
- 비대칭 키 : 공유 키 \(n\) + 개인 키 \(n\)
- 평문, 암호문
- 대칭 키 : 각종 기호들의 조합
- 비대칭 키 : 정수로만 표현
- 암호 방식
- 대칭 키 : 기호를 대체하거나 치환, 키를 이용한 암호/복호화
- 비대칭 키 : 정수를 다른 정수로 표현, 공개 키로 암호화, 개인 키로 복호화
- 메시지의 길이
- 대칭 키 : 길이가 주로 긴 메시지
- 비대칭 키 : 길이가 주로 짧은 메시지, 전자 서명, 인증
1-3. Trapdoor One-Way Function
1-3-1. One-Way Function 단 방향 함수
일반적인 함수의 계산은 쉽지만, 그 함수의 역을 구하는 것은 어렵다.
→ 출력값이 주어졌을 때 입력값을 구하는 것은 어렵다.
즉, x(입력값) 과 k, n 이 주어졌을 때 \(y = x^{k}mod(n)\) 을 구하는 것은 쉽지만
y(출력값) 과 k, n 이 주어졌을 때 x 값을 구하는 것은 어렵다.
1-3-2. Trapdoor One-Way Function
Trapdoor → 비밀
Trapdoor 가 주어지면 y(출력값)을 이용한 역함수로 x(입력값)을 쉽게 구할 수 있다.
1-4. 오일러의 \(\varphi\) 함수
1-4-1. \(\varphi(n)\) 의 정의
n 보다 작으면서 n 과 서로소인 정수의 개수
$$ ex)\,\,\,\,\,n=10,\,\,\varphi(n)=4 $$
1-4-2. \(\varphi(n)\) 의 특징
- \(\varphi(1)=0\)
- \(\varphi(p)=p-1\), p = 소수
- \(\varphi(mn)=\varphi(m)*\varphi(n)\), m과n = 서로소
- \(\varphi(p^{e}) = p^{e}-p^{e-1}\), p = 소수
1-4-3. \(\varphi(n)\)에 관한 오일러 정리
- a, n이 서로소일 때, \(a^{\varphi(n)}mod\,\,n=1\)
- a<n, k가 정수일 때, \(a^{k*\varphi(n)+1}\equiv a(mod\,\,n)\)
2번의 증명
오일러 정리 1번
$$ a, n\,\,\,이\,\,서로소\,\rightarrow a^{\varphi(n)}mod(n)=1 $$
과 modulo 연산의 곱셈 분배법칙을 이용
$$ (a*b)mod\,n=((a\,mod\,n)*(b\,mod\,n))mod\,n $$
경우 1 \(a,n\,\,이\,\,서로소\)
$$ a^{k*\varphi(n)}\equiv1\ \ \ \ \ (mod\ n) $$
$$ \begin{align*} a^{k*\varphi(n)+1}&=aa^{k\varphi(n)}\ \ \ \ \ (mod\ n) \\&=a*\left\{\underbrace{a^{\varphi(n)}...a^{\varphi(n)}}_k\right\}\ \ \ \ \ (mod\ n) \\&=a\left\{\underbrace{1...1}_k\right\}\ \ \ \ \ (mod\ n) \\&=a1^k\ \ \ \ \ (mod\ n) \\&=a\ \ \ \ \ (mod\ n) \end{align*} $$
$$ \begin{align*} a^{k*\varphi(n)+1}\equiv a\,(mod\,n) \end{align*} $$
경우 2 \(\,a,\,n\,이\,서로소가\,아님\)
$$ \begin{align*} n=p*q\\a=i*p\\a,q는\,서로소\\위의\,3가지를\,가정 \end{align*} $$
$$ \begin{align*} a^{\varphi(n)}\,mod\,(q)&=a^{\varphi(p*q)}\,mod\,(q) \\&=a^{(\varphi(p)*\varphi(q))}\,mod\,(q) \\&=(a^{\varphi(q)}\,mod\,(q))^{\varphi(p)}\,mod\,(q) \\&=1^{\varphi(p)}\,mod\,(q) \\&=1 \end{align*} $$
$$ \begin{align*} a^{k*\varphi(n)}\,mod\,(q) &=(a^{\varphi(n)}\,mod\,(q))^{k}\,mod\,(q) \\&=1^{k}\,mod\,(q) \\&=1 \end{align*} $$
$$ \begin{align*} a^{k*\varphi(n)}=q*x+1 \end{align*} $$
$$ \begin{align*} a^{k*\varphi(n)+1} &=a*a^{k*\varphi(n)} \\&=a*(q*x+1) \\&=(a*q*x)+a\,\,\,\,\,(a=i*p) \\&=(i*p*q*x)+a\,\,\,\,\,(n=p*q) \\&=(n*i*x)+a \end{align*} $$
$$ \begin{align*} n*i*x\rightarrow n으로\,나눴을\,때\,몫=i*x \\a\rightarrow n으로\,나눴을\,때\,나머지=a \\전제조건\,a<n\rightarrow a=a\,mod\,n \end{align*} $$
$$ \begin{align*} a^{k*\varphi(n)+1}\,mod\,(n)&=\{(n*i*x)+a\}\,mod\,(n) \\&=\{(n*i*x)\,mod\,(n)+a\,mod\,(n)\}\,mod\,(n)\\&=a\,mod\,(n) \end{align*} $$
$$ a^{k*\varphi(n)+1}\equiv a\ \ \ \ \ (mod\ n) $$
2. RSA 암호 시스템
- Revest, Shamir, Adleman 의 이름을 딴 공개 키 알고리즘
- 가장 널리 사용되는 암호 시스템
2-1. 기본
- 공개 키 = ( e, n )
- 개인 키 = d
- 기본적으로 512bit 이상 → 무식하게 때려넣어서 맞추는게 불가능하다
- 암호문 = \(P^e\,mod\,(n)\)
- 복호문 = \(C^d\,mod\,(n)\)
2-2. 키 생성 알고리즘
- p, q → 같지 않은 두개의 큰 소수
- \(n=p*q\)
- \(\varphi(n) = (p-1)*(q-1)\)
- e → \(1<e<\varphi(n)\) 이면서 \(\varphi(n)\) 과 서로소
- \(d = e^{-1}\,mod\,(\varphi(n))\)
- \((e*d)\,mod\,(\varphi(n))=1\)
- Extended Euclidian 알고리즘 사용하여 d 값을 구한다
2-3. 정확성 증명
- 암호화될 평문 \(P\) 와 복호화된 복호문 \(P_{1}\) 가 동일함을 증명하는 과정
- 두번째 오일러 정리를 이용
$$ \begin{align*} P_{1}&=C^d\,mod\,(n) \\&=(P^e\,mod\,(n))^d\,mod\,(n) \\&=P^{e*d}\,mod\,(n) \end{align*} $$
$$ \begin{align*} &d=e^{-1}\,mod\,(\varphi(n)) \\&(e*d)\,mod\,(\varphi(n))=1 \\&결국\,e,d는\,mod\,(\varphi(n))\,에\,대해\,역원관계 \\&즉,\,ed=\varphi(n)*k(몫)+1(나머지) \end{align*} $$
$$ \begin{align*} P_{1}&=P^{e*d}\,mod\,(n) \\&=P^{\varphi(n)*k+1}\,mod\,(n) \\&=P\,mod\,(n) \\&결국\,P_{1}과\,P는\,동일 \end{align*} $$
💡 주의할 점 : 평문 P 의 길이는 n 보다 작아야 한다. 너무 긴 문자열은 제대로 전달되지 못할 가능성이 있다.
2-4. Extended Euclidean 알고리즘
공개 키의 e 와 개인 키 d 는 서로 \(\,mod\,\varphi(n)\) 에 대해 역원의 관계를 가진다.
→ e 와 Extended Euclidian 알고리즘을 사용하여 d 를 구한다.
2-4-1. Euclid 알고리즘
두 수 사이에 존재하는 최대공약수를 구하는 알고리즘
$$ \begin{align*} &gcd(a,0)=a \\&gcd(a,b)=gcd(b,a\,mod\,b) \end{align*} $$
2-4-2. Extended Eucledian 알고리즘 구현
Euclid 알고리즘을 좀 더 확장
$$ d=e^{-1}\,mod\,(\varphi(n)) $$
r1 = n; # 파이(n)
r2 = e; # d를 구하기 위한 e
t1 = 0;
t1 = 1;
while(r2>0):
q = r1/r2; # 몫
r = r1-q*r2; # r1 을 r2로 나눈 나머지
r1 = r2;
r2 = r;
t = t1-q*t2; # q 를 이용한 새로운 t2
t1 = t2;
t2 = t;
if(r1!=1):
if(t1<0): return (n+t1)
else: return t1
else:
print("e 와 d 는 서로소 관계여야 합니다.")
2-5. Fast Exponentiation
암호화 또는 복호화를 위해서는 \(A^b\,mod\,(n)\) 을 계산해야함
→ 512bit 이상의 크기를 가질 수 있는 현재 그냥 계산하기에는 너무 오랜 시간이 소요
→ Square-and-Multiply 개념 이용
$$ a^{13}=a^{1101_{2}}=a^8*a^4*1*a $$
3. 타원 곡선 암호 시스템 Elliptic Curve Cryptosystem
- 보안을 위해서는 키의 길이가 매우 커야만 함
- 보다 짧은 키의 길이로 동일한 보안 수준을 제공(256bit~)
- 일반적인 타원 곡선 방정식
- \(y^2+b_{1}xy+b_{2}y=x^3+a_{1}x^2+a_{2}x+a_{3}\) 실수 상의 타원 곡선
- 실수 상의 타원 곡선
- \(y^2=x^3+ax+b\)
- 모든 근이 실근일 경우, 좌표의 수평선과 곡선이 3지점에서 교차
3-1. 타원 곡선 상의 덧셈 연산
타원 곡선 상의 두 점 \(P=(x_1,y_1),\,Q=(x_2,y_2)\) 에 대해 \(R=P+Q\) 를 정의
- P 와 Q 를 연결하는 직선과 교차하는 곡선 상의 점에 대해 x 축으로 대칭한 점
- \(\lambda=(y_2-y_1)/(x_2-x_1)\)
- \(x_3=\lambda^2-x_1-x_2,\ y_3=\lambda(x_1-x_3)-y_1\)
- P 와 Q 가 동일 즉, P 또는 Q 를 지나는 접선을 이용
- \(\lambda=(3x_1^2+a)/(2y_1)\)
- \(x_3, y_3\) 은 동일
3-2. GF(p) 상의 타원 곡선
비대칭 키 암호화에서는 정수를 기준
→ 실수를 정수로 바꾸기 위해 modulo 연산 적용
- modulo p 연산을 적용한 타원 곡선
- x의 값 : 0~p-1 범위에 존재
- 덧셈 연산 : 덧셈 결과 modulo p
- 역원 구하기
- (x, y) 의 역원 → (x, -y)
- -y는 y의 덧셈에 대한 역원
- (4,2) 의 역원 → (4, -2) → (4, 11) (p=13 이라 가정)
3-3. 비트코인(Bitcoin)에서 사용하는 타원 곡선 : Secp256k1
- 비트코인에서는 전자 서명을 위해서 타원 곡선을 이용
- Elliptic Curve Digital Signature Algorithm
- 타원 곡선 방정식 : \(y^2=(x^3+7)\,mod\,p\)
- 매우 큰 소수를 p 의 값으로 사용
- \(p=2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1\)
- 소수이며 매우 큰 값인 p 의 값으로 modulo 연산을 진행하기에 곱셈의 역원이 항상 존재
- 공개키(public key) = 개인키(private key) * G
- G : 타원 곡선 상의 고정된 점
- 공개되어있는 점
그럼 G 를 private key 만큼 더해야하는데 256bit 의 크기를 가지는데 엄청 오래 걸리지 않을까?
→ Double and Add Algorithm
3-3-1. Double and Add Algorithm
- private key 를 2진화
- left-to-right 방향으로 1bit 씩 읽음
- 해당 자리의 bit 값이 1 이라면
- 만약 최초의 1 이라면 G 로 초기화
- aG + aG(Double) = 2aG
- 2aG + G(Add) = (2a+1)G
- 해당 자리의 bit 값이 0 이라면
- 비트를 읽는 방향 덕분에 최초의 비트는 1 즉, 첫 비트인지는 확인할 필요 없음
- aG + aG(Double) = 2aG
예제) 18*G
$$ 18=10010_{(2)} $$
$$ \begin{align*} &bit1\,(1):\,G초기화 \\&bit2\,(0):\,G+G=2G(Double) \\&bit3\,(0):\,2G+2G=4G(Double) \\&bit4\,(1):\,4G+4G=8G(Double),\,\,8G+G=9G(Add) \\&bit5\,(0):\,9G+9G=18G(Double) \end{align*} $$
