[보안] 비대칭 암호화, ElGamal, RSA

이 블로그는 개인의 공부 목적으로 작성된 블로그입니다. 왜곡된 정보가 포함되어 있을 수 있습니다

앞 포스팅과 이어집니다~

https://bluesparrow.tistory.com/18

[보안] 공개키와 비대칭 암호화 알고리즘

1. Discrete Logarithm Problem

$g$ 가 $Z^*_n$의 generator이고, 어떠한 $a$에 대해서 $g^z \equiv a(mod\ n)$를 만족하는 $z$를 찾는 문제

$z$를 찾는것이 매우 힘들다고 함(다 계산해보는 수 밖에 없음)

https://www.youtube.com/watch?v=SL7J8hPKEWY&t=7s

쉽게 설명한 영상을 찾았다.

정수론을 잘 모르겠지만 $mod$ 연산을 하는 순간부터 $g^z$가 어떤 숫자 인지 파악하기 어려워진다(자릿수, 약수등등)

또한 우리는 전 포스팅에서 페르마의 소정리를 이용하여 prime number를 사용하면 $0$ 부터 $n-1$까지의 숫자를 표현가능하다고 알고있다. 실제로도 소수로 $Z^*_n$ 을 만든다고 한다.

2. Primality Test(소수 찾기)

그러면 소수를 사용해야하는데 이때 매우 큰 소수를 찾아야한다(1024 비트 정도)

그러면 소수를 찾는것도 우리가 해결해야하는 문제가 된다.

이것도 페르마의 소정리를 사용하여 다른 문제로 치환이 가능하다

$a^{n-1} \equiv 1(mod\ N)$ 이므로 다음 조건을 만족하면 소수일수 있는 것이다.(충분조건이기 때문에 소수가 아닌 경우도 존재함)

Carmichael number: 소수가 아니지만 $a^{n-1} \equiv 1(mod\ N)$을 만족하는 숫자

Carmichael number을 해결하기 위해서는 여러 $a$에 대해서 계산을 해야한다.

매 계산에 마다 Carmichael number가 찾아질 확률 $\frac{1}{2}$ 반대의 경우는 참과 거짓을 판단할수 있음

따라서 검사한 원소의 개수가 $k$라고 할때 prime number인지 확인하지 못하는 확률은 $\frac{1}{2^k}$ 으로 극히 희박하다

 

비대칭 암호화 방식

 

출처: https://www.ssl2buy.com/wiki/symmetric-vs-asymmetric-encryption-what-are-differences

그러면 돌아와서 비대칭 암호화 방식에 대해 알아보자.

우리의 목표는 데이터 송신자만 데이터를 암호화할 수 있고, 수신자만 해당 데이터를 복호화 할 수 있어야한다.

따라서 기존에는 대칭키를 사용했던 것과 달리, 사용자가 공개키와 개인키를 하나씩 가지고 있다.

그런데 공개키는 뭐고 개인키는 뭔데?

이전 포스팅처럼 이름으로 이해해보자

공개키: 공개되도 상관없는 키로 사용자가 개인이 소유하는 비대칭키

개인키: 공개되선 안되는 사용자가 개인이 소유하는 비대칭키

송신자는 수신자의 공개키를 통해 데이터를 암호화하고 수신자는 개인키를 통해 복호화한다.

대칭키의 단점을 비대칭키는 해결할 수 있을끼?(어느정도 안전하지만 개인키가 유출되면 결국 소용없는 것이 아닌가?)

 

3. ElGamal 암호화

Discrete Logarithm를 이용한 비대칭 암호화 방법

1. 공개키

공개키는 총 3가지 $<g,p,Y>$

$ p$: prime number (소수)

$ g $ : generator $g<p,g\in Z^*_p$ (generator값)

$ Y \equiv g^x \ mod \ p$ (모듈려 연산값)

2. 개인키

$x, \ x<p$

Discrete Logarithm Problem에 의해 안전성이 보장

3. 암호화

그러면 개인키를 얻기 어렵다는 것은 이해했다

암호화는 어떻게 이루어질까?

안전한 암호화는 같은 데이터에 대해서도 매번 다른 암호문이 생성되야한다

$<a,b>$ 두가지의 값을 만들어 전달

$k$: random 값(소수일 필요가없나? -> 하면 더 찾기 어렵지만 소수를 사용하지 않아도 찾기 어려운 값이다)

$a=g^k \ mod \ p $ 에 해당하는 $a$를 생성($k$을 찾기 어렵다)

$b=Y^kM \ mod \ p$ 에 해당하는 $b$를 생성($M$은 전달할 데이터)

4. 복호화

수신사도 사실 $k$를 알지 못한다.

하지만 $g^x$를 알고 있기 때문에 복호화를 할 수 있다고 한다. 자세히 보자

수신자는 $k$는 알지 못하지만 $Y^{k}$ 는 알 수 있다! ($Y^{k}=(g^x)^k= (g^k)^x $인데 이는 $a^x$이기 때문에

따라서 $M=b/(a^x)(mod\ p)=y^kM / g^{kx}=g^{xk}M/g^kx=M$으로 $M$을 구할 수 있다.

 

4. RSA Encryption 

또다른 비대칭 암호화 방법

이제부터는 다른 이야기가 시작되니 이전내용들은 어느정도 지워도 괜찮다.

1. 공개키

$n=p\cdot q$ 이때 $p,q$는 prime

$e$ random 값인데 $(p-1)(q-1)$와 서로소 관계

2. 개인키

$d \equiv e^{-1} mod (p-1)(q-1)$ $d$는 $ (p-1)(q-1)$에 대한 역원

역원을 구하기 위해서는 $ (p-1)(q-1)$ 를 알아야함&

그런데 $(p-1)(q-1)$ 를 알기 위해서는 $n$을 prime의 곱의 형태로 소인수분해를 해야한다.

두개의 prime 으로 소인수 분해하는 것이 결국 RSA에서의 보안을 책임지는 문제가 된다.(1024비트의 숫자에서는 난제이다. 마찬가지로 역원을 구하는 것 또한 매우 어렵다고 한다.)

3. 암호화

$C \equiv M^e mod n$

4. 복호화

$M \equiv C^d \ mod \ n$

5. 생각 해 볼 문제

$(M^e)^d \equiv M^{ed} mod \ n $인데 이때 $ed$는 $(p-1)(q-1)$에 관련되어 있고 $n=pq$이므로 우리가 알던 문제와 다른 문제가 된다. 과연 저런 계산이 맞는건가?

6. 증명 $M\equiv C^d \ mod \ n$

$ed\equiv 1\ mod(p-1)(q-1)$ 는 $ed-1\equiv 0\ mod(p-1)(q-1)$ 이고, 배수의 관계에 따라

$ed-1\equiv 0\ mod(p-1)$, $ed-1\equiv 0\ mod(q-1)$ 이고 ,$ed$를 다음과 같이 표현가능하다.

$ed= k(p-1)+1$, $ed= l(q-1)+1$

이제 $M\equiv C^d \ mod \ n $이 만족하는지 살펴보자

 

$C^d =M\ mod\ p$에서 ---1)

$c^d=M^{ed}=M^{k(p-1)+1}$이므로

1)에 대입하면 $M^{k(p-1)+1}mod\ p \equiv M^{k(p-1)}\cdot M \ mod \ P$이고, ---2)

페르마의 소정리에 의해 $M^{k(p-1)}= (M^{p-1}) ^k=1 $ 이다 ($a^P-1 \equiv 1$이므로)($p$가 prime이므로 사용가능)

2)식에 대입하면 $M^{k(p-1)}\cdot M \ mod \ p \equiv M\ mod\ p$

$C^d mod \ q =M \ mod\ n $ 도 동일한 방법으로 증명가능(생략)

$C^d =M\ mod\ p$ 에서

$C^d -M =0 \ mod\ p$ 이므로 $C^d-M=kp$

$q$ 도 동일하게 계산하면 $C^d-M=lq$ ($k,q$는 상수)

따라서 $C^d-M=mp\cdot q$이고

$C^d-M\equiv mod \ pq$ 인데 $pq=n$이므로

$C^d =M\ mod\ n$ 이다 (증명완료)

5. 공개키 암호 알고리즘의 장단점

장점: 보안 강도가 높고 키분배및 관리에 효율적

단점: 대칭키에 비해 시간이 오래걸림, 공개키에 대한 관리 방법이 필요함(중간에 위 변조될수 있기 때문에)

6. Diffie-Hellman Key exchange

공개키와 대칭키 암호화 방법중 둘다 사용하는 방법(하이브리드)

송신자 수신자간의 대칭키가 생성된다.

$ p$: prime number (소수)

$ g $ : generator $g<p,g\in Z^*_p$ (generator값)

$a,b<p$ (각각 송신자 수신자의 비밀키)

step 1

송신자는 $A=g^a mod\ p$ 생성

수신자에게 $g,p,A$를 전달(공개키)

step 2

수신자는 $B=g^b mod\ p$, $K=A^b mod\ p$ 생성

송신자에게 $B$를 전달(공개키)

$K=g^{ab} mod\ p $

step 3

송신자는 $K=B^a mod\ p$ 생성

$K=g^{ba} mod\ p$

$K$ 가 대칭키로 공개키를 통해 생성(와우)

7. 하이브리드 암호화

공개키 암호화는 너무 느려서 Diffie-Helleman Key와 같이 하이브리드 방식으로 많이 사용한다고 한다.

다른 하이브리트 암호화 방법으로는 비밀키를 통해 공개키로 암호화하여 전달하여 비밀키(대칭키)로 데이터를 교환하는 방법