[Cryptography] stage4_공개키암호: RSA

RSA암호의 안전성 기반은 아주 큰 두 소수의 곱으로 이루어진 합성수를 인수분해하기 어렵다는 사실에 있다. -> 거꾸로 말하면, RSA로 암호화 할 땐 합성수의 소인수분해가 어려워지도록 각 인자를 적절히 설정해야 안정성을 보장받을 수 있다는 것이다. 

 

그리고 이전 현대 암호 파트에서 말했듯이, 공개키 암호의 특성상 대칭키 암호 만큼의 안전성을 보장받기 위해서는 긴 키가 필요하며, RSA암호의 경우 2048비트 이상의 키가 권장된다. -> 그만큼 훨씬 많은 연산량이 요구되며, 많은 데이터를 여러 번 암호화해야하는 네트워크 통신에는 적절하지 않다. 

 

 

 

*RSA암호 알고리즘

RSA암호는 공개키 암호로, 공개키(public key)와 개인키(private key) 두 개가 이용된다. 공개키의 경우 암호화 시 사용되는 키로 모든 사용자에게 공개되며, 개인키의 경우 복호화 할 때 이용되며 타인에게 노출되어서는 안 되는 키이다.

 

 

오일러 정리: 

m^φ(n) ≡ 1 (modn)

 

위 식은 오일러 정리이다. (gcd(m, n) = 1, φ는 오일러 파이 함수)

 

 

키 생성: 

대칭키 암호의 경우 임의의 난수를 선택하면 됐지만, 공개키 암호의 경우 공개키와 개인키를 생성하는 과정이 필요하다. 안전성을 감안하면 복잡한 연산이 불가피한 과정이다. 

 

 

-> 먼저 두 소수 p와 q를 선택한다. (일반적으로 비트 수가 같은 두 소수를 선택하며, 1024비트 이상의 수를 고른다.)

 

-> p와q의 곱 n에 대해 φ(n)을 계산한다. (이 값은 (p - 1)(q - 1)이다.)

 

-> gcd(φ(n), e) = 1이고 e < φ(n)인 e에 대해 d ≡ e ^ (−1) (mod φ(n))인 d 값을 구한다. 

 

 

여기서 n과 e는 공개키로, d는 개인키로 사용된다. (n은 modulus, e는 공개 지수(public exponent), d는 비밀 지수(private exponent))

 

 

암호화:

공개키(n, e)로 n보다 작은 평문 m을 암호화 할 때, 암호문 c는 아래와 같은 식으로 연산된다.

 

c ≡ m^e (modn)

 

 

복호화: 

암호문 c를 개인키(d)로 복호화 할 때, 평문 m은 아래와 같은 식으로 연산된다.

 

m ≡ c^d (modn)

c^d ≡ (m^e)^d ≡ m^(ed) (modn)

 

여기서 d ≡ e^(−1) (modφ(n)) (오일러 정리)이므로 ed = kφ(n) + 1을 만족하는 자연수 k가 존재한다. 

 

m^(ed) ≡ ((m^φ(n))^k)*m (modn)

 

여기서 m^φ(n) ≡ 1 (mod n).이니까 (오일러 정리) ((m^φ(n))^k)*m ≡ m (mod n)이 된다.

 

 

 

*RSA공격

앞서 말했듯 RSA는 많은 연산량이 요구된다. 이 연산량을 줄이고 빠른 암호화를 하기 위해 공개 지수 e를 작게 설정할 수 있는데, 그렇게 되면 줄어든 연산량만큼 안전성 역시 줄어들게 된다. -> Coppersmith공격, Hasrad`s Broadcasr공격 등에 취약해짐

 

Coppersmith공격:

차수가 e인 함수 f(x)에서 찾고자 하는 근이 n^(1/e)보다 작을 경우, 복잡도가 O(log n)인 알고리즘을 이용해 근을 구할 수 있다. (Coppersmith정리)

 

이를 RSA에 적용할 경우 근이 n^(1/e)보다 작은 함수 f(x)를 만들 수 있다면 평문을 얻어낼 수 있다. 가령, e = 3이고, 평문의 비트 중 상위 2/3이상을 알고 이를 a라고 한다면, f(x) = (a + x)^3을 만들어 위와 같은방법으로 전체 평문을 얻어낼 수 있다.

 

 

Hastad`s Broadcast 공격:

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

 

공개키 e = 3을 가진 3명의 수신자들에게 같은 평문 m의 암호화 결과를 송신한다고 가정하자. 수신자들은 n1, n2, n3를 사용한다. (gcd(n1, n2, n3) = 1) 그럼 각 수신자가 얻은 암호문을 c1, c2, c3라고 했을 때 다음과 같다. ->  

 

m^3 ≡ c1 ​(mod n1​)

m^3 ≡ c2 ​(mod n2​)

m^3 ≡ c3​ (mod n3​)

 

여기서 CRT에 의해 m^3 ≡ c (mod n1*n2*n3) 인데, m < ni이므로 m^3 < n1*n2*n3라서 m^3 = c이다. -> 평문 m을 구할 수 있게 되는 것.

 

 

공개 지수가 작으면 위의 두 공격 외에도 Coppersmith의 짧은 패드 공격(Short Pad Attack)등에 취약하게 된다. -> 그렇다고 너무 크게 설정하면 연산량이 늘어나 암호의 효율성이 떨어진다. -> 적당한 밸런스가 필요한 부분인데, 그래서 보통 공개 지수값으로 2^16 + 1 = 65537을 이용한다고 한다.

 

 

Common Modulus Attack:

같은 n과 두 공개 지수 e1, e2(gcd(e1, e2) = 2)를 사용해 동일한 평문 m의 암호화 결과 c1, c2를 얻었을 때 이를 공격하는 기법이다.

 

gcb(e1, e2) = 1이므로 re1 + se2 = 1, r < 0인 (r, s)들을 확장 유클리드 알고리즘으로 구할 수 있다.

 

그리고 c1^(-1) (mod n)을 구하고

 

(c1^(-1))^(-r) * c2^s = (m^(-e1))^(-r) * m^(e2 * 8) = m^(re1 + se2) = m -> 평문 m을 구할 수 있다.

 

위와 같이 수신자들이 같은 n을 사용해도 공격받기 쉼다. -> 무작위의 n을 사용해야 함

 

 

그 밖에 d가 너무 작아도 공격에 취약해진다. d < (1/3) * n^(0.25) 일 경우 Wiemmer`s attack을 이용해 d를 복구해낼 수 있다. Boneh Durfee attack을 이용하면 d < n^(0.292)일 경우에도 d를 복구할 수 있다. -> 비밀 지수(d) 설정 시 n보다 적당히 큰 수가 되도록 해야 한다.

 

 

 

 

공개키 암호 알고리즘 안전성의 기반은 문제의 어려움에서 온다. -> 이를 해결할 수 있는 알고리즘이 등장하거나 컴퓨터의 연산 능력이 향상될 경우 안전하지 않음 ->  RSA암호의 경우도 양자 컴퓨터가 등장할 경우 쇼어 알고리즘으로 쉽게 풀릴 수 있다고 한다. -> PQC에 대해서도 많은 연구가 이루어지는 중