암호학 6주차 - RSA

0. 서론

RSA 암호 알고리즘은 공개키 암호시스템 중 하나로 가장 보편적으로 사용되는 암호 및 인증 알고리즘이다.

1978년 Ronald L.Rivest, Adi Shamir, Leonard Adleman의 연구로 체계화된 알고리즘이다.

RSA 암호 알고리즘의 안전성은 아주 큰 두 소수의 곱으로 이루어진 합성수를 인수분해하기 어렵다는 인수분해 문제의 어려움에 기반한다. 암호화할 때 합성수의 소인수분해가 어려워지도록 인자를 설정해야 한다.

암복호화 과정에서 훨씬 많은 연산을 필요로 하므로 네트워크 통신에서는 잘 사용되지 않는다.

​

---

1. RSA 암호 알고리즘과 키 생성

RSA암호 알고리즘은 공개키와 개인키를 사용한다.

- 공개키(Public key): 모든 사용자에게 공개되며 평문을 암호화할 때 사용

- 개인키(Private key): 타인에게 노출되어서는 안 되며 공개키로 암호화된 암호문을 복호화할 때 사용

​

• 오일러 정리

: n과 서로소인 양의 정수 m이 있을 때 m ^ φ(n) ≡1(modn) 을 만족한다.

+ φ(n) 은 오일러 파이 함수(Euler's phi function)이라고 하고 n 이하의 양의 정수 중 n과 서로소인 수의 개수를 의미한다.

소수 p에 대해서 φ(p)=p-1 이다. 1부터 p-1까지 모두 p와 서로소이기 때문이다.

​

• 키 생성

방법)

1. 서로 다른 두 소수 p와 q를 선택한다. 일반적으로 1024비트 이상에서는 비트 길이가 같은 수로 생성
2. p와 q를 곱하여 n을 구하고 φ(n)을 계산한다.

(1) n=p x q

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

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

---> φ(n) = p x q - p - q + 1 = (p-1)(q-1) 로 표현할 수 있다.

​

(2) φ(n) = p x q - p - q + 1 = (p-1)(q-1)

 

3. φ(n)을 구한 후 φ(n)보다 작은 수 중 φ(n)과 서로소인 e를 선택하고 d≡e^(-1) mod φ(n) 인 d를 구한다.

​

(3) e < φ(n), gcd(e, φ(n))=1

 

(4) d≡e^(-1) mod φ(n)

​

여기에서 나온 n과 e는 공개키로 사용하고 d는 개인키로 사용한다.

n은 modulus, e는 공개 지수(public exponent), d는 비밀 지수(private exponent)라고 한다.

​

---

2. RSA 암호 알고리즘의 암호화와 복호화

• 암호화

공개키 (n, e)로 n보다 작은 평문 m을 암호화할 때 암호문 c는

c ≡ m^e(mod n)

​

​

• 복호화

암호문 c를 개인키 d 로 복호화할 때 평문 m은 다음의 과정을 통해 구한다.

​

1. m≡ c^d(mod n)
2. c^d≡ (m^e)^d≡ m^(ed)(mod n)

이 때 d ≡ e^(-1) mod φ(n) 이므로 ed = kφ(n)+1을 만족하는 자연수 k가 존재하고, 다음의 등식이 성립한다.

m^(cd) ≡ (m^φ(n))^k x m (mod n)

오일러 정리에 의해 m^φ(n) ≡ 1 (mod n) 이므로 (m^φ(n))^k x m ≡ m (mod n)

​

---

3. RSA 공격 - 작은 e 설정

e 를 너무 작게 설정하면 다음의 공격에 취약해질 수 있다.

​

• Coppersmith 공격

차수가 e인 함수 f(x)에서 찾고자 하는 근이 n^{1/e} 보다 작을 경우, 복잡도가 O(logn)인 알고리즘을 이용하여

근을 구할 수 있다.

이를 RSA에 적용할 경우 근이 n^{1/e} 보다 작은 함수 f(x)를 만들 수 있다면 평문을 얻어낼 수 있다.

​

예시)

e=3이고 평문의 비트 중 상위 2/3 이상을 알고 있고 이를 a라고 한다면 f(x) = (a+x) ^ 3 을 만들어

Coppersmith 정리를 사용해 전체 평문을 얻어낼 수 있다.

​

​

• Hastad's Broadcast 공격

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

가능한 공격방법

​

예시)

공개키 e=3을 가진 3명의 수신자들에게 같은 평문 m을 암호화해서 보내는 경우 수신자들은 서로 서로소인 n을 사용하고, 이를 n1,n2,n3라고 하자. 각 수신자가 얻은 암호문을 c1,c2,c3 라고 했을 때

​

m^3≡c1(modn1)

m^3≡c2(modn2)

m^3≡c3(modn3)

​

각 n이 서로 서로소이기 때문에 위 3개의 수식을 중국인의 나머지 정리를 이용해 합치면

m^3≡c(modn1n2n3)

​

여기서 각 n의 값이 모두 m보다 크기 때문에 m^3 <n1n2n3 가 성립한다.

이를 통해 m^3 = c 라는 등식을 얻을 수 있다.

​

c는 위에서 중국인의 나머지 정리를 이용해 구한 값이므로 위 등식으로 평문 m을 구할 수 있다.

​

​

+ 공개 지수가 작으면 이 두 개의 공격 외에도 Coppersmith의 짧은 패드 공격(Short Pad Attack) 등에 취약하다.

그런데 그렇다고 공개 지수를 너무 큰 값으로 설정하게 되면, RSA 알고리즘의 효율성이 떨어지게 된다.

일반적으로는 공개 지수로 2^{16} + 1 = 65537을 사용한다.

​

​

+ 중국인의 나머지 정리

: 쌍마다 서로소인 자연수 n1,n2,⋯,nk와 정수 a1,a2,⋯,ak 에 대하여 x≡ai(modni)(1≤i≤k)를 만족하는

x는 mod(n1×n2×⋯×nk)에서 유일하게 존재한다는 정리

 

조건:

x ≡ a1M1N1+a2M2N2+⋯+akMkNk (modM)

 

이 때

M=n1×n2×⋯×nk 이고, Mi=M/ni ,Ni는 modni에서 Mi에 대한 역원 (Ni≡Mi^(−1)(modni))

​

이를 이용하면 연립 합동식이 주어졌을 때 조건을 만족하는 해가 유일하게 존재하게 된다.

​

---

3. RSA 공격 - 공통 n 사용

• Common Modulus Attack

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

​

공격)

1. 공격자는 두 공개 지수가 서로소라는 점을 활용해 re1 + se2 = 1이고 r이 음수인 (r, s) 쌍을

확장 유클리드 알고리즘을 통해 구할 수 있다.

2. 확장 유클리드 알고리즘을 사용해 c1^(-1)(mod n)을 구한다.

​

3. 계산된 값을 바탕으로 m을 구한다.

계산: (c1^(-1))^-r x c2^s = ((m^(-e1))^(-r) x m^(e2 x s)

= m^(re1 + se2) = m

​

--> 같은 n을 사용하면 쉽게 공격받을 수 있으므로 수신자들은 n을 무작위 값으로 생성해 사용해야 한다.

​

---

3. RSA 공격 - 작은 d사용

비밀 지수 d가 작아도 공격에 취약하다.

​

• Wiener's attack

: d< 1/3 x n^(0.25)일 경우 Wiener's attack을 이용해 d를 복구해낼 수 있다.

​

​

• Boneh Durfee attack

: wiener's attack 보다 넓은 범위인 d<n^(0.292)일 경우 d를 복구해낼 수 있다.

​

--> 비밀 지수를 설정할 때는 n보다 적당히 큰 수가 되도록 해야 한다.