RSA(Rivest, Shamir and Adleman) 암호

안녕하세요 오늘은 RSA에 대해서 알아보도록 하겠습니다. 매번 RSA에 대해서 보는데 또 까먹고 계속 까먹네요ㅠ

 

 

RSA는 비대칭키 암호입니다. 

 

비대칭키 암호 ? 

비대칭키 암호는 공개키를 이용해 암호화하고 공개키에 해당하는 비밀키를 이용해 복화하는 방식입니다. 

 

절대 공개키만 가지고 데이터를 복호화 할 수 없습니다. 

 

비대칭키의 대표적인 예로는 RSA, 타원 곡선 암호, 전자 서명 등이 있습니다.,

 

그 중에 가장 유명한 RSA 암호는 세 단계로 나누어집니다.

 

1. 키 생성

2. 암호화

3. 복호화

 

순으로 나누어 집니다.

 

 

 

1. 키 생성

 

먼저 각각의 공개키와 개인키를 생성하는 방법이 필요합니다. 

그래서 RSA에서 두 개의 큰 소수인 p와 q를 선택합니다.

ex) p = 13  q = 17

 

 

p = 13 q = 17 

 

p와 q의 곱인 N을 계산합니다

 

N =  p * q = 13 * 17  = 221

 

이제 1부터 N-1까지의 정수 중 N과 서로같은 수(서로소)인 정수의 개수를 구합니다.

 

즉, 서로소는 두 숫자의 최대 공약수가 1이 되는 수를 말합니다. 

 

N이 소수라면 N과 서로소인 정수는 N-1개,

N이 소수의 곱이라면 N과 서로소인 정수는 (p -1) * (q -1)

 

이 값을 N에 대한 오일러 파이(φ) 함수 값입니다. 

 

φ(N) = (p - 1) * (q - 1) = (13 - 1) * (17 - 1) = 192

 

그러면 1 < e < φ(N)이고 φ(N)가 서로소인 공개키 e를 생성합니다.

 

1 < e < 192, e = 7로 생성합니다. 

 

(d*e) mod φ(N) = 1 이고  o <= d <= N인 d를 구합니다.

 

(d*e) mod φ(N) = 1, (d*7) mod 192 = 1, 

d = 55로 선택합니다.

 

 

생성된 값들은 N과 e는 공개키, d는 비밀키로 사용합니다.

 

암호화 

 

M은 평문, C는 암호문, N과 e는 공개키입니다.

 

C = M^e mod N 

 

M = 123, N = 221, e = 7

C = 123^7 mod 221 = 98

 

 

복호화

 

복호화에는 비밀키인 d가 사용됩니다.

 

M = C^d mod N

 

C = 98, N = 221, d = 55

M = 98 ^^ 55 mod 221 = 123 

 

 

즉 결론적으로 N과 e는 공개키 값이며 N을 소인수 분해하면 p와 q를 구할 수 있고, 공개키 e와 두 소수 p, q를 이용하여 개인키 d를 얻을 수 있습니다. 

 

 

이론적으로 봤었을 떄는 단순하지만 소스코드로 사용했을 때나 RSA을 1024 bit 소인수 분해했을 때는 값이 너무 커져서 알아 볼 수가 없습니다. 

 

 

이상 포스터를 마치겠습니다. 감사합니다.