RSA는 무엇인가?

RSA

RSA 암호화 알고리즘은 대표적인 공개키 암호화 기법 중 하나입니다.

송신자와 수신자는 모두 n과 e를 알고 있어야하고, 오직 수신자만이 d를 가집니다

1. 키 생성 RSA 알고리즘에서는 먼저 공개키와 개인키를 생성해야 합니다.
   • 소수 p와 q를 무작위로 선택합니다.
   • n = pq를 계산합니다. n은 매우 큰 수이며, 공개키와 개인키의 생성에 사용됩니다.
   • φ(n) = (p-1)(q-1)을 계산합니다.
     • φ(n)은 오일러 피 함수(Euler’s totient function)로 불립니다
     • 또한, n보다 작은 양의 정수 중 n과 서로소인 수의 개수를 나타냅니다.
   • 1 < e < φ(n)를 만족하는 e를 선택합니다. e는 공개키의 일부로 사용됩니다.
   • d * e ≡ 1 (mod φ(n))을 만족하는 d를 계산합니다. d는 개인키의 일부로 사용됩니다.
   • 이렇게 생성된 공개키와 개인키는 각각 (n, e), (n, d) 형태로 표현됩니다.
2. 암호화
   • 암호화하고자 하는 평문을 숫자로 변환합니다.
   • 암호문 C = M^e mod n을 계산합니다. C는 암호문이 됩니다.
3. 복호화
   • 암호문 C를 복호화하려면 개인키 (n, d)를 사용해야 합니다.
   • 평문 M = C^d mod n을 계산합니다. M은 원래의 평문이 됩니다.

이렇게 RSA 암호화 알고리즘은 매우 간단하지만, 소인수분해 문제의 난해성을 이용해 안전성이 보장됩니다.

• 컴퓨터 네트워킹 하향식 접근 풀이
  • 

RSA 암호화 요구 조건

1. n 보다 작은 모든 정수 M 에 대해서 M^ed = M mod n 을 만족하는 값 e, d, n 을구할 수 있어야 한다.
2. n 보다 작은 모든 정수 M 에 대해서 Me와 Cd를 구하는 것이 비교적 쉬워야 한다.
3. e 와 n 이 주어졌을 때 d 를 구하는 것이 불가능해야 한다.

3번 째 조건의 경우 e와 n이 큰 정수 일 경우 충족 시킬 수 있습니다.

RSA Modulo-n 연산에서 항등식 추출하는 방법

• (a mod n)^d mod n = a^d mod n
• 주의 사항
  • 메시지는 단지 비트열이며, 모든 비트는 하나의 정수로 나타낼 수 있음

RSA 알고리즘 예시

1. 두 소수 p = 17과 q = 11을 선택한다.
2. n = pq = 17×11 = 187을 계산한다.
3. ϕ(n) = (p-1)(q-1) = 16×10 = 160을 계산한다.
4. ϕ(n) = 160보다 작으면서 ϕ(n) 과 서로소인 수 e 를 선택한다.
   • 여기서는 e =7을 선택한다.
5. d＜160이면서 de mod 160 = 1인 수 d 를 결정한다.
   • 여기에 적합한 수는 d =23이다.
   • 왜냐하면 23×7 = 161 = 1×160 + 1이기 때문이다.

RSA 공격 방법 : 보안 관점

• 수학적 공격
  • 인수분해
  • 방어방법: 키의 길이를 길게 선택
• 타이밍 공격
  • 복호화 알고리즘 실행시간 관측
  • 방어방법: 랜덤 지체
• 선택 암호문 공격
  • 데이터 블록 선택후 RSA 약점 악용
  • 방어방법: 평문에 패딩 추가
• 최적 비대칭 암호화 패딩(OAEP) 활용