[알고리즘] RSA 공개키 알고리즘

RSA 알고리즘은 1977년

Ron Rivest
Adi Shamir
Leonard Adleman

이 3사람의 연구에 의해 체계화 됬고
RSA 는 이 3명의 이름 앞글자를 따서 만들었습니다.

RSA 암호의 특징은 두 소수를 통한 합성수를
만들기는 쉽지만 반대로 합성수를 다시 소인수 분해 하기는
어렵다는 것을 기반으로 합니다.

: 참조 :
http://ko.wikipedia.org/wiki/RSA_%EC%95%94%ED%98%B8

RSA 알고리즘을 조금 더 쉽게 이해 하기 위해서는
알아야 할 개념이 몇가지 있는데,
알아야 할 몇가지 개념들은 다음과 같습니다.

소수

일방향 함수

오일러 파이 함수 φ

모듈러스(mod)

 간단하게 위의 개념들을 정리해 보자면..

************************ 소수 ************************

소수는 쉽게 말해서 1과 자기 자신으로만
나누어 지는 1보다 큰 정수를 말합니다.

예) 2, 3, 5, 7, 11, 13

: 참조 :
http://terms.naver.com/entry.nhn?docId=1113970&mobile&categoryId=200000449

******************************************************

********************* 일방향 함수 *********************

일방향 함수는 쉽게 말해서 계산을 했을 때
결과값을 구하는건 쉽지만
그 입력한 값을 구하기는 어려운 함수를 말합니다.

: 참조 :
http://ko.wikipedia.org/wiki/%EC%9D%BC%EB%B0%A9%ED%96%A5%ED%95%A8%EC%88%98

******************************************************

****************** 오일러 파이 함수 ******************

일반적으로 φ(n) 이런 식으로 표기를 하며
오일러 파이 함수는 1부터 n 까지 양의 정수 중에
n 과 서로소인 숫자들의 갯수를 나타내는 함수입니다.

n 이 소수 라면 φ(n) = n-1 로 표현 됩니다.
( 또한 n 이 두개의 소수 a, b 로 곱해진 수라면
φ(n) = (a-1) * (b-1) 로 표현 됩니다. )

예를 들면,

– 1, 2, 3, 4, 5, 6 중에서 6과 서로소인 수는
1, 5 이므로 φ(6) = 2 로 표현 할 수 있습니다.

– 1, 2, 3, 4, 5, 6, 7 중에 7은 소수 이므로
φ(n) = n-1 을 해서 φ(7) = 6 으로 표현 할 수 있습니다.

– 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 에서 10은
2×5 로 표현할 수 있으므로
φ(10) = (2-1) * (5-1) = 1 * 4 = 4 로
표현 할 수 있습니다.

: 참조 :
http://ko.wikipedia.org/wiki/%EC%98%A4%EC%9D%BC%EB%9F%AC_%ED%94%BC_%ED%95%A8%EC%88%98

******************************************************

******************** 모듈러스 계산 ********************

Modular arithmetic 이라고도 하고
Modular Math 라고도 합니다.

1750 년에 스위스 수학자
Leonhard Euler 가 발견 했다고 합니다.

프로그래머로써 정말 쉽게 말하면
% 연산자의 기능입니다.

5 % 3 = 2 인것 처럼
이렇게 계산 하는 방법입니다.

계산식은 다음과 같습니다.

a equiv b pmod n

예를들면,

5 ≡ 2 (mod 3)

-8 ≡ 7 (mod 5)

2 ≡ -3 (mod 5)

와 같이 표현 합니다.

: 참조 :
http://en.wikipedia.org/wiki/Modular_arithmetic

******************************************************

위의 설명한 개념들로
두 양의 정수 m, n 이 서로소 일 때
다음과 같이 오일러 함수 공식이 성립 됩니다.

m^φ(n) ≡ 1(mod n)

위의 식은 아래와 같이

m^φ(n) mod n = 1

로 변경 할 수 있습니다.

예를들면,

서로소인 2, 3 을 가지고 공식에 대입을 해 보면
3은 소수 이므로 φ(3) = 3-1 = 2 가 됬을때

2^2 ≡ 1(mod 3)

4 ≡ 1(mod 3)

4 mod3 = 1 을

만족하므로위의 식이 성립 됩니다.

위의 식을 토대로 개인키, 공개키를
구할 수 있는 공식을 알아 보면 다음과 같습니다.

a * b ≡ 1(mod φ(n))

이고 이는 다음과 같이 변경 할 수 있습니다.

(a * b) mod φ(n) = 1

여기서 a 의 값은 1 < a < n 의 값이고
φ(n) 과는 서로소가 되야 합니다.

b 는 b < φ(n) 범위에 있는 정수를 선택 하면 됩니다.

이렇게 해서 개인키와 공개키를 구하면 됩니다.

개인키 – (n, a)
공개키 – (n, b)

암호화

위의 식들을 토대로 암호화 하는 과정을 알아 봅시다.
위의 식을 가지고 개인키와 공개키를 구하면
다음과 같이 구할 수 있습니다.

개인키 – (n, a)
공개키 – (n, b)

여기서 암호화를 하려고 하는 값을 x,
암호화 된 값을 y 라고 한다면
다음 식이 성립 합니다.

Y = X^a (mod n)

( ex )

일단 두 소수의 합성수인 n 을 구하기 위해서
두 소수를 각각 p = 3, q = 5 로 정하면
n 은 다음과 같습니다.

n = p * q = 3 * 5 = 15
n = 15

그 다음 오일러 파이 함수식에 의해서 φ(n) 의 값을 구하면
3과 5가 각각 소수 이기 때문에 다음과 같이 구할 수 있습니다.

φ(n) = (p-1) * (q-1) = (3-1) * (5-1) = 2 * 4
φ(n) = 8

그다음 개인키와 공개키를 각각 구해 봅시다.
위에서 개인키와 공개키를 구하는 식을 토대로 볼 때

(a * b) mod φ(n) = 1

a 는 1 < a < n 의 값이고 φ(n) 과는
서로소가 되야 하므로

1 < a < 15 이고 φ(n) 과 서로소가
되는 값 중에 하나는 5 입니다.

그러므로 a = 5, φ(n) = 8 이므로
다음 식이 성립 됩니다.

(5 * b) mod 8 = 1

이를 토대로 b 값을 구해 볼 때
b 는 b < φ(n) 범위에 있는 정수 이므로

b = 3 이 됩니다.

따라서 개인키와 공개키를 다음과 같이 구해졌습니다.

개인키 – (15, 5)
공개키 – (15, 3)

이 값들을 가지고 암호화 식에 의해서 암호화를 해 봅시다.
암호를 하고자 하는 값이 5 라고 한다면..

Y = X^a (mod n)
Y = 5^5 (mod 15) = 5
Y = 5 가 됩니다.

복호화

암호화 된 값을 복호화 하는 식은 다음과 같습니다.
위에서 처럼 암호화를 하려고 하는 값을 x,
암호화 된 값을 y 라고 한다면 다음 식이 성립 합니다.

X = Y^b (mod n)

( ex )

위에 암호화 에서 암호화 했던 값들을 가지고
다시 복호화 한다면 다음과 같습니다.

X = Y^b (mod n)
X = 5^3 (mod 15) = 5
X = 5

 이므로 위의 식이 성립 하는걸 볼 수 있습니다.