[암호] 비대칭키 암호화

1. 대칭키 암호화의 문제점

대칭키 암호화의 경우 사전에 암·복호와하는 이들끼리 서로 같은 키를 나눠가지는 ‘키분배/교환‘이 이루어져야 한다.
따라서 대칭키의 경우 통신자가 n명일 때 n(n-1)/2개의 키가 필요하다. 반면 비대칭키의 경우 2n개의 키가 필요하다.

 

 

2. 키분배 방법

첫번째 방법.  키 관리 기관인 TA가 사전에 두 사용자에게 비밀스럽게 대칭키를 전달한다.
두번째 방법.  두 사용자가 KDC에게 key를 요청하면 암호화된 key를 두 사용자에게 전달한다.
세번째 방법.  디피-헬만(Diffie-Hellman) 키교환으로, 두 사용자 각자가 가진 개인키로 대칭키를 계산한다. (공개키 암호화 계산과 유사)

 

 

 

3. 키분배: 디피-헬만 키교환

두 사용자 사이에 대칭키를 나누어 갖는 방식을 “각자 계산”으로 바꾸는 혁신적인 키교환 방법이다.
(A개인키, B공개키) or (A공개키, B개인키)를 이용해서 둘 사이의 대칭키를 계산한다. 풀기 어려운 수학이어야 하겠다.

그게 이산로그문제이다. $y=g^x mod p$에서 g,x,p를 알면 y를 구하기 쉽지만 g,y,p를 알면 x를 구하기는 어렵다는 성질을 이용한다.
1024bit 소수 p를 이용한 mod(나머지) 연산을 사용한다.

 

디피-헬만 키교환 과정	예시

 

디피-헬만도 100% 안전하지는 않다.

- 이산로그 문제를 풀면 공격이 가능하다.
- 지수함수에 기초한 이산로그는 계산이 복잡해서 많은 장치와 동시에 통신하는 경우 계산에 오랜 시간이 걸린다. 이 때 공격 대상 server에 대해 IP spoofing으로 키생성을 동시에 엄청 요청해서 server를 마비시킬 수 있다.
- 중간자(MITM) 공격도 있다.

두 사용자가 서로 A,B 값을 교환할 때, 중간에 끼어들어서 A와 T랑 대칭키를 만들고, B와 T랑 대칭키를 만드는 것이다.
A가 B로 메세지를 보낼 때 T가 A랑 만들어둔 대칭키로 풀어보고 내용을 조작한 뒤에 B한테 보낼 수도 있다. 답을 B가 보내면 T가 B랑 만들어둔 대칭키로 풀어서 보고 … 를 반복할 수 있다.
이런 것들을 다양한 프로토콜을 추가 적용함으로 막을 수 있다.

 

 

 

 

 

 

 

4. RSA

비대칭 암호화 중 제일 유명한 것이 RSA이다. 1977년에 만들어졌지만 현재까지 실제 산업계의 표준으로 사용된다.
암복호화 뿐 아니라 전자서명 등 다양한 기능도 제공한다. 각자 공개키와 개인키의 한 쌍을 가지고 암호화, 전자서명에 쓴다.

공개키로 암호화하고 개인키로 복호화하는 방식이다.
(기밀 보장) A가 보내는 메세지를 B만 열 수 있게 하고싶다면, A는 B의 공개키로 암호화를 해야한다.
(부인 방지) A가 작성한 문서를 B에게 내가 한게 맞아라고 증명하고 싶다면, A의 개인키로 암호화하면 A의 공개키로 열수있다. (전자서명)

대칭키는 데이터 암복호화 목적이고, 굳이 추가하자면 메세지 인증코드에 필요하다.
비대칭키는 암복호화보다도 전자서명에 더 많이 쓰인다. 송금에도 쓰인다. 공인인증서가 내 개인키이고 공개키는 은행이 가지고 있다.

큰 수는 소인수분해가 굉장히 어렵다는 수학적 난제에 기반한 기법이다.
1) 큰 소수 p,q를 정한다. 최소 512bit여야 한다. 십진수로는 약 154자리이다.
2) N = p*q
3) 중간숫자인 L을 계산한다. L = (p-1)과 (q-1)의 최소공배수
4) L을 이용해서 공개키를 위한 E를 찾는다. 1<E<L이면서 E와 L은 서로소여야 한다.
5) L과 E를 이용해 개인키를 위한 D를 찾는다. 1<D<L이면서 E*D mod L = 1이어야 한다.

결과적으로 공개키 PU는 {E,N}이고, 개인키 PR은 {D,N}이다.
예를 살펴보자.

예시	검증

RSA도 100% 안전하지는 않다.
- 소인수분해 공격이 가능하면 뚫린다. 키의 길이를 충분히 길게 설정해야 한다.
- 복호화 알고리즘을 돌리는 데에 걸리는 시간을 추적해서 키 길이를 추측할 수 있다. 그래서 Random delay 방식으로 방어한다.
- 공격자가 위조된 암호문을 server에 보내어 받는 응답을 여러번 시도해서 key와 plain text 정보를 얻는 선택암호문(CCA)공격이 있다. 이는 OAEP로 plain text를 수정하여 분석에 어려움을 가중시킨다.

 

 

5. ECC

최근 타원곡선암호인 ECC가 상당히 많이 쓰이고 있다. 최근에는 암호화폐에도 적용이 됐다.
RSA에 비해서 key 크기를 약 1/6 정도 작게 하면서도 암호 강도를 RSA와 비슷한 수준으로 제공하기 때문이다.
계산도 더 단순하고 속도도 빠르다. HW SW적으로 구현도 쉬워서 작은 하드웨어에도 많이 적용되고 있다.

위의 사진이 타원 그림인데, a와 b에 따라서 타원 곡선이 굉장히 다양하게 나온다.

 

타원 곡선이 결정되면, 특정 점을 하나 선택하고 접선을 그렸을 때 교점의 x축 대칭점을 찾는다.
이 x축 대칭점의 접선을 그렸을 때 교점의 x축 대칭점을 찾는다.
이 x축 대칭점의 접선을 그렸을 때 교점의 x축 대칭점을 찾는다.
이 x축 대칭점의 접선을 그렸을 때 교점의 x축 대칭점을 찾는다.
… 이걸 굉장히 여러번 한다. random number generator로 횟수를 결정한다. 횟수가 개인키이고 최종 x축 대칭점으로 공개키를 만든다.
공개키값을 알고있다고 한들 몇 번을 거쳐서 갔는지 찾기가 굉장히 어렵다.

6. 대칭암호화 vs. 비대칭암호화

대칭암호화는 암복호화(기밀성)에 많이 쓰인다. 그 기법으로는 substitution, permutation이 있다.
비대칭암호화는 수학적 함수를 이용해서 원래의 수를 예측하기 어렵게 큰 수와 복잡한 계산을 통해 다른 숫자로 변경하는 것이다.

두 암호화 방식의 차이