[Crypto] Dreamhack STAGE 4

https://dreamhack.io/lecture/roadmaps/3

Cryptography

---

[ Crypto: Stage 4: 공개키 암호와 키 교환 알고리즘 ]

 

[ Diffie-Hellman 알고리즘 ]

→ 배경: 공개된 채널을 통해 키를 교환해도 외부인은 키를 알 수 없게 하는 공개 키 교환 알고리즘 고안

→ 디피헬만 알고리즘의 안전성은 이산 로그 문제의 어려움에 바탕을 둠.  키를 모르는 공격자가 키를 구하려면 m이     

     22048 정도 되는 이산 로그 문제를 풀어야 하는데, 이는 현재의 연산능력으로는 불가능함

 

* 수학적 원리

1. 모듈러 연산에서의 거듭제곱

  : 임의의 합동 항등식에 대해, 양변에 동일한 값을 곱해도 식은 성립한다. 따라서 아래와 같은 식이 성립한다.

이를 이용하여 큰 지수에 대한 합동식을 빠르게 연산하는 알고리즘을 square and multiply라고 부름

diffie-hellman 키 교환 알고리즘을 사용하려면 22048

 번 가까이 제곱된 어떤 수의 모듈러 값을 구해야 하는데, 이 방법을 사용하면 2048번 정도만 연산해도 그 값을 구할 수 있다.

 

2. 페르마의 소정리(Fermat’s Little Theorem)

 : “소수 p와 정수 a에 대해 ap-1=1(mod p)

 이 성립한다”

 à 예를 들어, 소수 37과 2,3,17은 페르마의 소정리에 따라 236=336=1736=1mod 37

 을 만족함

 

3. 이산 로그 문제(Discrete Logarithm Problem)

 : “자연수 a, m, 정수 b에 대해 ax=b(mod m)

을 만족하는 정수 x를 구하는 문제”

 

 

[ 키 교환 절차 ]

[1] 키를 교환하고자 하는 alice는 소수 p와 1≤g≤p-1을 만족하는 적당한 수 g를 정해 bob에게 전송함

    P는 보통 21024 이상의 큰 소수로 설정함

[2] 다시 alice는 1≤a≤p-1 을 만족하는 적당한 수 a를 정하여 A=g(^a)mod p를 bob에게 전송함

[3] alice로부터 g와 p를 받은 bob은 1≤b≤p-1 을 만족하는 적당한 수 b를 정해  B=g(^b)mod p를 alice에게 전송함

[4] alice는 bob이 보낸 B를 a제곱하여 K=B(^a)=(g(^b))(^a)=g(^ba) mod p 를 계산

    Bob은 alice가 보낸 A를 b제곱하여 K=A(^b)=(g(^a))(^b)=g(^ab) mod p 를 계산

[5] alice와 bob은 계산한 K를 통신의 키로 사용

 

→ 공격자는 통신을 도청하여 p, g, g(^a) mod p, g(^b) mod p 를 알아낼 수 있음.

   그러나 이산 로그 문제의 어려움으로 인해 a를 알아내거나 b를 알아내는 것은 불가능하며, 결과적으로 K를 구할 수 없다.

 

[ 중간자 공격(Man In The Middle attack(MITM) ]

 : 능동적 공격(통신을 도청하면서 중간에 데이터 위변조 가능)

 → alice와 bob이 통신할 때, 공격자는 alice에게 자신을 bob이라고 하고, 그리고 bob에게는 자신을 alice라고 속임

    그러면 alice와 bob은 통신하는 상대방이 공격자인지, 아니면 신뢰하는 상대방인지 알 수 없음

 

 

[ 공개키암호: RSA ]

→ RSA 암호 알고리즘의 안전성은 아주 큰 두 소수의 곱으로 이루어진 합성수를 인수분해하기 어렵다는

'인수분해 문제의 어려움’에 기반

 → 따라서 RSA로 암호화할 때는 합성수의 소인수분해가 어려워지도록 각 인자를 적절히 설정해야 함

 → RSA는 대칭키 암호 알고리즘보다 많은 연산이 필요하므로, 많은 데이터를 여러 번 암호화해야 하는 네트워크

      통신에서는 잘 사용되지 않음

 → 공개키: 모든 사용자에게 공개, 평문을 암호화 / 개인키: 타인에게 노출되어서는 안되며, 암호문을 복호화

 

 * 오일러 정리

: n과 서로소인 양의 정수 m이 다음의 식을 만족한다는 정리

     mφ(n)≡1 (mod n)

여기에서 φ(n) 은 오일러 파이 함수라고 하며, n 이하의 양의 정수 중에서 n과 서로소인 수의 개수를 뜻함

 

* 키 생성

[1] 서로 다른 두 소수 p와 q를 선택.

       일반적으로 1024비트 이상에서 비트 길이가 같은 수로 생성,

       그 뒤 p와 q를 곱하여 n을 구하고 φ(n)을 계산함

[2] n = p x q

   : n = pxq인데 p와 q가 소수이므로, φ(n)은 n보다 작으면서 p와 q의 배수가 아닌 수들의 개수가 된다.

    n 이하의 수 중, p의 배수는 q개, q의 배수는 p개 존재하며, 이 중 같은 수는 두 수의 최소공배수인 n뿐임

    따라서 φ(n)은 아래처럼 표현될 수 있음

[3] φn=p*q-p-q+1=(p-1)(q-1)

 φ(n)을 구한 뒤, φ(n) 보다 작은 수 중 φ(n)와 서로소인 e를 선택하고, d= e-1 mod φ(n)인 d를 구함

[4] e< φ(n), gcde,φn=1

[5] d= e-1 mod φn

 

→ 위 과정으로 생성한 값들 중, n과 e는 공개키로, d는 개인키로 사용됨

   n은 modulus, e는 공개 지수, d는 비밀지수라고 불림

 

* 암호화

 : 공개키 (n,e)로 n보다 작은 평문 m을 암호화할 때, 암호문 c는 다음 식으로 구해짐

    c =  m(^e) (mod n)

 

* 복호화

 : 암호문 c를 개인키 d로 복호화할 때, 평문 m은 다음과 같이 구해짐

    m= e(^d) (mod n)

    e(^d)= (m(^e))(^d)= m(^ed) (mod n)

오일러 정리에 따르면 d= e(^-1) mod φ(n)이므로ed=kφ(n)+1 을 만족하는 자연수 k가 존재함

따라서 아래와 같은 식이 성립함

        m(^ed) = (mφ(n))km (mod n)

오일러 정리에 따라 mφ(n)=1(mod n) 이므로 (m(^φ(n)))(^k)m=m(mod n)이다.

 

* RSA 공격

1. 작은 e

: e를 너무 작게 설정하면 Coppersmith 공격과 Hastad’s Broadcast 공격 등에 취약해질 수 있음

1) Coppersmith 공격

2) Hastad’s Broadcast 공격

     : 한 송신자가 다수의 수신자에게 동일한 평문을 전송할 때, 수신자들에게 모두 동일한 작은 e 값을 사용할 경우 가능한 공격 방법

 

2. 공통 n

   1) Common Modulus Attack

      : 같은 n과 서로소인 두 공개 지수 e1, e2를 사용하여 같은 평문 m을 암호화해서 두 암호문 c1, c2를 만들었을 때, 이를 공격하는 기법

 

3. 작은 d

   : 비밀 지수를 설정할 때는 n보다 적당히 큰 수가 되도록 해야 함