-
키 배송 문제
- 송신자와 수신자가 대칭키를 사저에 비밀스럽게 공유해야 한다.
- 키가 너무 많아지는 문제가 있다.
방법
Diffie-Hellman 키 교환 -> 공개키 암호의 근간 -> RSA 응용
(블록체인 시스템에도 사용된다)
Diffie-Hellman
암호 통신을 원하는 두 송수신자 사이 비밀 정보 공유 방법
이산대수
- 생성자(generator/원시근) g를 갖는 순환군(cyclic group) G에서
- 이산대수 구하는 문제는 계산상 불가능하다는 것에 기인한다.
여기서, 군(Group)과 아벨군의 개념이 중요하다.
생성자(Generator) == 원시근(Primitive Root)
오일러의 ø-함수
== 오일러의 토이션 함수(Euler's totient function)!!!
ø(n) 함수의 의미 : |Zn*| -> 기약잉여계 집합의 원소 개수 -> n과 서로소인 원소의 개수
Diffie-Hellman 키교환 알고리즘
- 큰 소수 p 와 mod p (à Zp*)에 대한 원시근(생성자) g 를 공유
- mod p에 대한 원시근
각 사용자는 다음과 같이 공개키/개인키 쌍을 생성
비밀키 Xa를 임의적으로 선택한다. (Xa < p)
공개키 Ya를 계산 : Ya = g^t mod p (t = Xa)
- Ya를 공개 -> 공개키
사용자 A, B의 공통키(세션키) Kab :
- Kab = gt mod q (t = Xa*Xb)
- = (Ya)t mod q (t = Xb) (사용자 b 계산)
- = (Yb)t mod q (t = Xa) (사용자 a 계산)
Diffie-Hellman 키교환 : 원시근/생성자
임의의 소수 p 에 대하여 근의 멱승이 1부터 p-1까지의 모든 정수를 생성할 경우에 해당하는 원시근 g를 찾는 방법
- Zp * 의 원소 중에서 하나를 g로 선택
- g의 멱승에 대한 p modular 계산 결과: g^1 mod p, g^2 mod p, ........, g^p-1 mod p; 1부터 p-1까지의 각각 다른 정수를 생성.
예)
prime number = 소수
Generator = 군(생성자: Zp*의 모든 생성자를 만들 수 있는 숫자들 중 하나)
DH의 안전
안전하다지만, 중간자 공격에는 취약하다.
중간에 전달해 주는 값을 변경하면, 값이 달라져서, 서로 암호를 확인할 수 없다.
RSA 암호 알고리즘
a^(k× f(n) + 1) ≡ a (mod n) -> 오일러 정리
p : prime number(소수)
1버전 p : prime number(소수) a^(p-1) mod p ≡ 1 a^(p-1) ≡ 1 (mod p) 2버전 a^p mod p ≡ a a^p ≡ a (mod p) 오일러 정리
페르마의 정리를 일반화 시킨 정리이다.
- a^∅(n) ≡ 1 (mod n) (n: 모든 정수)
- a^∅(n) (mod n) ≡ 1
- a^(k * ∅(n) + 1) ≡ a (mod n) -> 가장 중요하다
이 정리를 이용해서 RSA로 발전한다.
평문 a -> 암호화/복호화 과정 -> a^(k * ∅(n) + 1) -> 평문 a
a^(k * ∅(n) + 1) = e * d <- (e * d mod ∅(n) = 1)
- e * d mod ∅(n) ≡ 1
- e: 암호호 키 (공개키)
- d: 복호화 키 (개인키)
- n: p * q 곱셈 (p와 q는 소수이다.)
이 방법을 이용해서 RSA를 만든다.
RSA
암호문으로부터 평문 구하기 (공격)
평문: 해독하려는 내용
D : 개인 키 중 적어도 D는 모른다
전사공격
D의 후보가 되는 수를 순서대로 모두 시도해서 복호화 해본다
-> D의 비트 수가 크면 어려워진다.
N의 소인수 분해
큰 수를 고속으로 소인수분해 할 수 있는 방법이 발견되면 RSA를 깰 수 있다.
하지만, 그런 방식은 아직 발견되지 않았다.
RSA Hack
방법 1 : 공개된 N 값으로부터 p, q 찾기
N = p*q (N : 512 bits)
Generated prime p : (256 bits)
Generated prime q : (256 bits)
수행 회수 : 소인수분해 과정 2(512-1)번 수행해야 함
방법 2 : 공개된 E 값으로부터 d 찾기
N = p*q (N : 512 bits)
Generated prime p : (256 bits)
Generated prime q : (256 bits)
e*d mod ø(n) ≡ 1 -> E : 256 bits. ( d ≡ e^-1 mod ø(n) )
-> ø(n) 을 계산할 수 있어야 함
수행 회수 : |Zn*| 개수를 구해야 함 -> 2^(512)-1 계산 수행해야 한다
중간자 공격
앨리스와 밥은 서로 연락한다고 생각하지만, 사실은 중간의 맬로리와 대화하고 있는 것이다.
해결방법: 공인인증서 11장 -> 인증서 + 기타 방식 확장
ElGamal 방식
