DEV BLOG

[알고리즘] RSA 암호화

2018-06-11 | 알고리즘 RSA 암호화
Contents

RSA 암호화란?

  • 이름이 왜 RSA인가?
    • Ron Rivest, Adi Shamir, Leonard Adleman 의 세 사람의 한글자 씩 따서 만들어짐.
  • 공개키 알고리즘
  • 공개키와 개인키 2개의 키를 가지고 암복호화를 함

기본 아이디어

  • 큰 수의 소인수분해는 어렵다
  • 따라서, 공개키만으로 소인수분해하여 개인키를 알아내기 어렵다

키 생성 알고리즘

  1. 두 개의 소수를 선택한다. p, q
  2. N을 구한다. N = p * q
  3. φ ( N ) = (p - 1)(q -1)을 구한다.
  4. 1 < e < φ ( N ) 범위 내에서 φ ( N ) 서로소인 e 를 선택한다.
  5. 아래 조건을 만족하는 개인키인 d를 구한다.
    • d ⋅ e ≡ 1 (MOD φ ( N ) )
    • 확장된 유클리드 호제법을 이용하여 구할 수 있다.

예제

  1. p = 3, q = 11를 선택한다
  2. N = 3 * 11 = 33
  3. φ ( 33 ) = (3 - 1)(11 - 1) = 2 * 10 = 20
  4. 1 < e < 20 범위 내에서 φ ( 33 )와 서로소인 집합 {1, 3, 6, 7, … 19} 중 하나를 선택한다. 7를 선택
  5. d를 구한다. 7d mod *φ ( 33 ) = 7d mod 20 = 1 를 만족하는 d는 3이다

여기서 공개키는 e, n 을 사용하고 개인키는 d이다.

암호화와 복호화

암호화

암호화할 대상을 m이라 하면 아래 공식을 통해 암호화된 메시지인 c를 구할 수 있다

c \ equiv m ^ e \ pmod {n}

m= 18이고, 위 예제에서 나온 값을 대입하면

c = 18 ^ 7  mod 33 = 612220032 mod 33 = 6

복호화

개인키 d를 이용하여 암호화된 메시지인 c에서 암호 해독하여 m을 구할 수 있다.

{\ displaystyle c ^ {d} \ equiv (m ^ {e}) ^ {d} \ equiv m {\ pmod {n}}}

m = c^d = 6^3 mod 33 = 1728 mod 33 = 18

개인키를 구하는 방법

확장된 유클리드 호제법이란?

정수 m, n 의 최대공약수(Greatest Common Divisor)를 gcd(m,n)와 나타낼 때, 확장된 유클리드 호제법을 이용하여, am + bn = gcd(m,n)의 해가 되는 정수 a, b 짝을 찾아낼 수 있다

개인키 공식

개인키는 d * e ≡ 1 (MOD φ ( N ) ) 를 만족하는 d 이다

d * e mod φ ( N ) = 1 MOD φ ( N ) = 1 mod 20 = 1

위 식에서 아래 식을 도출할 수 있다.

d * e = k * mod  φ ( N ) + 1 
d * e - k * mod φ ( N )  = 1

확장된 유클리드 호제법 이용

유클리드 호제법의 확장에서 본 am + bn = gcd(m, n)과 같지 않은가?

gcd(e, φ ( N ) ) = 1 = a * e + b * φ ( N )

e와 φ ( N )은 서로소이기 때문에 최대공약수가 1이며

이 식에서 a는 d, b = -k로 생각한다면 확장된 유클리드 호제법을 이용하여 d를 구할 수 있다.

예제

위 예제에서는 e = 7, φ ( N )=20이므로

20 = 7 * 2 + 6  —> 6 = 20 * 1  + 7 * (-2) …(i)
7 = 6 * 1 + 1 —>  1 = 7 + 6 * (-1) … (ii)

(ii)식에 6대신 i를 대입

1 = 7 + 6 * (-1)
  = 7 + (20 * 1  + 7 * (-2)) * (-1)
  = 7 + 20 * (-1) + 7 * 2
  = 7 * 3 + 20 * (-1)

따라서 a = 3, b = -1이며 d는 3이 된다.

reference