< 암호학 > RSA 암호화 시스템의 구조

RSA란?

RSA는 1977 MIT에서 Rivest / Shamir / Adleman이 만들어낸 암호화 구조입니다.

1. 가장 많이 알려지고, 쓰이는 공개키 암호화 방식

2. 모듈로 연산을 포함한 정수론을 기반으로 한 지수 연산을 사용 (GF에서의 지수연산)

3. 2048 비트와 같은 매우 큰 정수 사용으로 느린 속도 (AES보다 느림)

4. 매우 큰 정수의 곱을 사용하기 때문에 소인수분해의 어려움을 가지고, 이를 기반으로 보안을 유지

 

RSA 암호화 / 복호화

암호화

암호화하여 보낼 송신자는, 암호문을 받을 수신자의 공개키 PU = {e,n} 이용

 

암호문 C 

C는 암호문, M은 메세지

복호화

암호문을 받은 수신자는, 본인의 개인키 PR = {d,n} 이용

 

복호화 결과 메세지 M

M은 메세지, C는 암호문

* 이때 mod n을 적용하기 때문에 구분 가

능하도록,

메세지 M을 0 <= M < n 크기로 사용합니다. ( 혹시 더 길면, n보다 짧게 만들어야 합니다. )

* RSA key의 길이 = n의 길이

 

RSA KEY 세팅하기

1. p, q 정하기

     두 개의 서로 다르고, 1024비트 이상인 매우 큰 소수를 랜덤 으로 구합니다

 

2. n 구하기

     modulus n = p * q

 

3. 오일러 함수 계산 

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

 

     >>> 이 값은 p,q를 알고 있다면 구하기 매우 쉽습니다.

              하지만 p와 q를 모른다면 p와 q의 곱인 n은 매우 큰 수입니다.

              따라서 매우 큰 수의 소인수분해 결과와 관련된 곱인, 오일러 함수 값은 매우 구하기 어려운 값입니다. ( -> 보안 유지 )

 

4. 랜덤 암호화 키 e 선택

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

 

      >>> e는 n의 오일러 함수값보다 작고, 그와 서로소인 랜덤 수

              보안을 위해, 일반적으로 65537과 같은 값이 많이 쓰입니다.

 

5. 복호화 키 d 계산

      e * d = 1 mod φ(n)

 

      >>> d는 e의 φ(n) 모듈로 역원

               즉, 확장 유클리드 알고리즘을 사용하여 구할 수 있습니다.

 

Public Key인 PU = {e,n} 은 공개하고,

Private Key인 PR = {d,n} 은 비공개로 소유합니다.

 

RSA가 암/복호화 동작한다는 증명

1. n = p*q

• p,q는 소수

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

• 소수 x의 오일러 함수 값 φ(x) 은 x-1
  • 오일러 피 함수 - φ(x) 는, 정수 n과 서로소인 1부터 n까지의 수의 개수를 의미하기 때문입니다.
  • 소수라면, 약수가 1과 자신뿐이므로 자신을 제외한 개수를 셉니다.
• 따라서, n과 서로소인 수의 개수는 ϕ(n)=(p−1)(q−1)
• 이는 두 소수 p와 q가 서로 배수 관계가 아니기 때문에 가능합니다.

3. e*d = 1 + k*φ(n)

• k는 임의의 수
• e*d = 1 mod φ(n) 이기 때문에, e*d는 나머지 + 몫과의 곱으로 표현됨

 

즉,

C에 d를 제곱하여 n으로 모듈러 계산하면, 기존의 메세지(평문)으로 복호화가 가능하다는 걸 의미합니다.

 

개인적으로 이전 강의안 내용에 있었는데 기억에서 날아가 있었어서 이해가 잘 안 되었던 부분입니다.

 

바로 이 식이 성립하는 이유는 오일러 정리에 있는데 ..

https://dxwny.tistory.com/25
RSA에 대해 적용하여 유도해본 식이 정확하게 맞는 식인지는 검증이 된 후에 다시 업데이트 하도록 하겠습니다 ..