RSA 공개키 암호 알고리즘

RSA 암호화 알고리즘

---

  RSA는 대표적인 공개키 암호로서 Diffie Hellman의 공개키 암호 개념을 기반으로 MIT공대 연구팀 소속 Rivest, Shamir, Adleman에 의해 만들어졌다. RSA는 Rivest, Shamir, Adleman의 이름에서 앞글자를 따왔다. RSA는 큰 수의 소인수 분해가 매우 어렵다는 것에 기반을 두고 만들어 졌다.

RSA에서 사용되는 기호는 아래와 같다.

p, q	매우 큰 서로 다른 소수
n	p * q의 합성수
gcd(a, b)	a와 b의 최대 공약수
φ(n)	오일러 Totient함수로, φ(n)은 n보다 작은 자연수 중에서 n과 서로 소인 자연수의 개수
a mod n	모듈러 연산으로, a를 n로 나누었을 때 나머지 값
a ≡ r mod n	a와 r은 n으로 나누었을 때 그 나머지가 같음 (a와 r은 합동)
e	n과 함께 공개되는 공개키로 암호화 지수에 사용
d	공개되지 않는 개인키로 복호화 지수에 사용
M	평문으로 공개키를 이용하여 암호화
C	암호문으로 개인키를 이용하여 복호화
KU	공개키로 KU = {e, n}으로 표기
KR	개인키로 KR = {d, n}으로 표기

---

• RSA의 키 생성

1. 개인키 p와 q를 선택한다.

    -  p와 q는 서로 다른 큰 소수이다.

2. 개인키 p와 q를 사용하여 n과 φ(n)을 구한다.

    -  n = p * q

       φ(n) = ( p-1 ) * ( q-1 )

3. φ(n)보다 작고, φ(n)과 서로소인 임의 자연수 e를 선택한다.

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

4. 확장 유클리드 호제법(Extended Euclidian Algorithm)을 사용하여 d × e를 φ(n)으로 나누었을 때 나머지가 1인 정수 d를 구한다.

    -  de ≡ 1 ( mod φ(n) )            1 < d < φ(n)

       de mod φ(n) = 1을 사용하여 d를 구하면 된다.

5. KU = {e, n}, KR = {d, n}.

• 암호화

  평문 M을 암호문 C로 변경 할 때, 우선 M을 n보다 작은 숫자 m으로 변환한다. 변환법(padding scheme)은 미리 상대방에게도 알려져 있어야 한다.

  (ex. 평문을 나누어 하나의 평문이 일정 수의 비트를 넘지 않게 하는 방법이 있다. 그러나 실제로 이중 보안을 위해 더욱 복잡한 변환법이 사용된다.)

  
  

  C = m^e ( mod n )

• 복호화

  암호문 C를 평문 M으로 변환 할 때는 아래와 같다.

  
  

  C^d ≡ ( M^e )^d  = M^tφ(n)+1 = M^tφ(n)M ≡ M ( mod n )

  m = C^d ( mod n )

  
  

  이 때, t는 ed ≡ 1 ( mod φ(n) )에서 유도되는 ed = tφ(n) + 1을 만족하는 정수이다.

---

소수 판별법

 주어진 정수가 소수인지 판별하는 알고리즘은 '오일러 규준(Euler Criterion)' 또는 'Solovay-Strassen Primality Test', 'Miller-Rabin Primality Test'를 사용하는 방법 등이 있다. 그 중, Miller-Rabin Primality Test를 방법이다. 

• Miller-Rabin Primality Test

  n-1 = 2^km을 만족하는 홀수 m을 구한다.

  임의의 a에 대해 a^m = ±1 ( mod n )이거나 a^2m mod n, ..., a^2k-1m mod n 중 하나가 -1과 합동인지 검사한다.

  합동이면 n은 소수이다.

위 포스팅은 연구 목적으로만 사용되었으며, 악용을 위해 사용되었을 경우 법적 제재가 있을 수 있습니다.

또한, 위 포스팅을 악용하였을 경우 모든 책임은 본인에게 있음을 유의하시기 바랍니다.