[정보보안] RSA Algorithm

실제로 앱 개발할때도 써본 RSA 알고리즘!!

정보보호이론 시간에 배워서 너무 좋았다...

 

RSA는 가장 유명한 공개키(비대칭키)암호이다. 

 

비대칭키 암호는 좀 느리지만, 인증, 디지털서명 등 분야에서 중요하게 사용된다. 

 

RSA라는 이름은 Rivest, Shamir, Adleman의 줄임말로 발명한 사람들 이름 앞자를 딴 것이다. 

 

 

 

 

 

모든 유저는 e, n, d를 계산해서 e,n은 공개하고 d는 갖고 있는다. 

각각 생성했으니까 각자 값이 다 다르다 

 

RSA Key Generation

1. 두 소수 $p$, $q$를 생성한다. $p$와 $q$는 달라야한다. $p$와 $q$는 Miller-Rabin 방식으로 홀수 하나를 만들어서 소수인지 확인하는 방식으로 선택한다. 

2. $n = p \cdot q$를 계산한다. 

3. $ \phi(n) = (p-1) \cdot (q-1) $

4. $e$ 선택:  $1 < e < \phi(n)$이고, $e$와 $\phi(n)$이 서로소이어야 함. (주로 $e$는 $2^{16} + 1$을 자주쓴다. $65537$이 소수라서!)

5. $d = e^{-1}$ mod $\phi(n)$ 계산

곱셈역 관계이니까, $d \cdot e$ mod $\phi(n)$ = 1이어야 한다. 

extended euclidean algorithm을 쓰면 된다. 

 

그러면 $e$, $n$, $d$, $p$, $q$, $\phi(n)$이 계산되는데, $e,n$은 공개하고 $d$는 개인키로 들고 있는다. 

나머지 값들은 비밀 폐기한다. 

RSA에서는 $p$랑 $q$는 512비트 이상, $n$은 1024비트 이상이어야 한다고 한다. 

 

증명

 

Euler's Theorem #2 를 이용했다. 

If $n = p  q$ and $a < n$, then $a ^{k \phi(n) +1} $ mod $n = a$.

 

 

취약점 찾기

Factorization attack

n = p*q 이니까 n을 가지고 p와 q를 구한다. 근데 이게 쉽지 않다... n이 1024비트 이상이기 때문에 소인수 분해를 하는 과정이 굉장히 오래걸린다. 따라서 n을 크게 고르면 안전하다. 

 

OAEP(Optimal Asymmetric Encryption Padding)

RSA알고리즘은 deterministic했다. C = P^e mod n이니까 P가 같으면 항상 C도 같았다. 

이에 랜덤성을 추가해서 P가 같아도 C가 다를 수 있게 해주는것이 OAEP이다. 

 

 

 

특징

메세지가 길면 되게 느리다. => 짧은 메세지에 유용하다

주로 디지털 서명같은 곳에서 사용된다. 

 

 

one-way function

y = f(x)는 구하기 쉽지만 y를 알고 x를 구하기에는 어려운 함수이다. 

trapdoor one-way function

모든 공개키 암호는 trapdoor one-way function을 사용한다!!!

y랑, trapdoor(secret)이 주어지면 x가 계산하기 쉬워진다.