[정보보호] RSA 알고리즘

RSA 공개키 알고리즘

RSA 알고리즘은 미국 MIT 의 Rivest, Shamir, Adleman 이 발표한 공개키 암호화 방식으로, 공개키 암호화의 개념을 수학 적으로 구체화 시킨 알고리즘 입니다. RSA 공개키 암호화 알고리즘은 이들 세 명 이름의 머리 글자를 딴 것입니다.

이 RSA 공개키 암호화 알고리즘은 현재 공개키 암호화에서 가장 널리 쓰이고 있는 공개키 알고리즘 입니다. 그 이유는 RSA 공개키 암호화 알고리즘이 최초로 공개키 암호화 의 개념을 구현 한 이유도 있지만, 그 안정성이 십 여년 이상을 통해 검증이 되었고, 그 동안 발표 되어온 공개키 암호화 알고리즘 중에서 이해와 구현이 쉽기 때문입니다.

앞으로 자세히 RSA 알고리즘에 관해 수학적 지식을 포함하여 자세히 설명 하겠지만, 우선 간단히 설명하면 자리 수가 많은 양의 정수에 대한 소인수 분해가 어렵다는 것에 착안 하여 이를 수학적으로 구현한 비 대칭 암호화 알고리즘 이라고 할 수 있습니다.

RSA 공개키 암호화 알고리즘 의 기본 형태는 DES 같은 대칭키 암호화와 같습니다. 키를 사용 하여 평문을 암호화 시켜 암호문을 출력 하는 것입니다. 대칭키 암호화와 다른 것은 암호화 하는 키와 복호화 하는 키가 다르다는 것 밖에 없습니다. 이런 기본 암호화 골격은 같지만 암호화 키와 복호화 키를 다르게 하기 위해 RSA 암호화 알고리즘은 DES 와 같은 대칭키 암호화 알고리즘과 확연히 다른 내부 알고리즘을 사용 하고 있습니다.

 

 

 

 

[그림 4-004.tif] DES 와 RSA 의 암호화/복호화 비교

  

 

RSA 알고리즘의 형태는 위 그림과 같이 매우 간단 합니다. 하지만 이 형태를 이용해서 키 교환이나 서명/인증 같은 메커니즘을 구현 할 수 있습니다. 다시 말하면 RSA 알고리즘 같은 공개키 알고리즘은 단순히 위 그림과 같이 서로 다른 키를 가지고 데이터 암호화/복호화를 하는 것이 기능의 전부 이지만, 이 특성을 이용해서 키 교환이나 서명/인증 알고리즘을 구현 할 수 있게 되는 것입니다.

4.3.2 일방향 함수

RSA 알고리즘도 그렇지만, 모든 공개키 암호화 알고리즘은 일방향 함수를 사용 합니다. 일 방향 함수라는 것은 한쪽으로는 계산이 용이한 반면, 그 반대쪽은 계산하기가 매우 어려운 함수를 의미 합니다.

공개키 암호화 알고리즘에서는 일방향 함수를 사용해서 평문을 암호화 합니다. 한 쪽으로는 계산하기 쉬우므로 평문을 암호화 하기는 쉽습니다. 그러나 반대쪽으로는 계산하기 어려우므로 암호문을 평문으로 바꾸는 것은 매우 어려운 일입니다. 여기서 반대쪽으로 계산 하는 것을 일방향 함수의 역변환 이라고 합니다.

만약, 자신을 포함한 모든 사람이 일방향 함수의 역변환을 할 수 없다면, 비록 공개키 암호화 에서 바라는 암호화의 기밀성은 보장이 되는 것이지만, 암호문을 복호화 해야 하는 자신도 암호문을 평문으로 바꿀 수 없을 것입니다. 그래서 공개키 암호화에서는 두 가지 키가 제공 되는 것입니다.

두 개의 키 중 어떤 키라도 평문을 암호화 할 수 있습니다.

암호화한 키는 일방향 함수를 사용해서 평문을 암호화합니다. 일방향 함수의 특징상 반대쪽으로는 계산할 수 없으므로 암호문을 평문으로 바꿀 수는 없습니다. 그렇지만, 나머지 다른 하나의 키를 이용하면 이 역 변환을 쉽게 할 수 있습니다. 즉 나머지 키는 이런 반대 쪽으로 변환 하는 역변환 함수의 열쇠 역할을 하는 것입니다.

일방향 함수로 사용될 수 있는 것은 많습니다. 하나의 예를 들어보겠습니다.

우리가 종이와 연필을 사용 하여 어떤 숫자의 제곱을 구하는 것은 어렵지 않습니다. 그러나 제곱에서 그 제곱근을 구하는 것은 어렵습니다. 78 의 제곱은 6084 입니다. 이것을 계산 하는 것은 쉽습니다. 그러나 종이와 연필로만 계산을 했을 때6084로부터 제곱근인 78을 얻어내는 것은 어렵습니다. 숫자가 커지면 커질수록 계산하는 것은 더 어려워 질 것입니다. 25의 제곱근이 5 라는 것은 쉽게 구할 수 있지만, 19053225 의 제곱근이 4365 라는 것은 쉽게 알기가 어렵습니다.

물론 계산기를 사용하면 제법 큰 숫자의 제곱근도 쉽게 구할 수 있을 것입니다. 하지만 손으로 계산해 내기는 어려울 것입니다. 이것은 일방향 함수의 간단한 하나의 예일 뿐입니다.

실제로 RSA 공개키 암호화 알고리즘에서는 계산기, 혹은 그보다 훨씬 처리 속도가 빠른 슈퍼 컴퓨터로도 쉽게 계산을 하지 못하는 일방향 함수를 사용 합니다. 그 일방향 함수는 소인수 분해의 어려움에 그 안전성을 근거로 하고 있습니다.

RSA 공개키 암호화 알고리즘 에서 사용하는 일 방향 함수는 다음의 수학적 배경을 사용 합니다.

두 개의 매우 큰 소수의 곱을 구하는 것은 용이 하지만 그 곱에서 원래의 두 개의 소수를 구하는 것은 매우 어렵습니다.

즉 p 와 q 를 매우 큰 소수라고 하면 이 두 개의 곱 n = p * q 를 구하는 것은 쉽지만 , 합성수인 n 에서 p 와 q 를 구하는 것은 아주 어렵습니다. RSA 공개키 암호화 알고리즘에서는 위와 같은 수학적 배경을 가진 일 방향 함수를 사용 하여 암호화를 합니다.

[잠깐 시작]

소수

소수란 것은 1과 자신 이외에는 나누어 지는 수가 없는 수를 말합니다.

즉 3, 5, 7, 17 과 같은 수들을 말합니다.

[잠깐 끝]

그럼 이제 RSA 공개키 암호화 알고리즘에 대하여 하나씩 단계별로 설명을 하겠습니다.

크게 키 생성을 하는 단계와 평문을 암호화 하는 단계, 그리고 암호문을 복호화 하는 단계로 나누어서 설명 하겠습니다.

4.3.3 키 생성

이번 절에서는 RSA 공개키 암호화 알고리즘에서 사용 할 수 있는 개인키와 공개키를 어떻게 생성 하는지 수학적 배경과 함께 알아 보겠습니다.

1. 서로 다른 임의의 두개의 소수 p 와 q 를 선택 합니다. p 와 q 는 클수록 암호화의 안정성이 높아 집니다.

2. p 와 q 를 곱한 값 n 을 생성 합니다

n = p * q

3. 오일러 파이 함수 φ(p) 값을 구합니다.

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

4. 오일러 파이 함수 φ(n)란 무엇일까요?

오일러 파이 함수 φ(n) 은 1부터 n-1 까지의 양의 정수 중에서 n 과 서로 소의 관계에 있는 정수들의 개수를 나타냅니다. 두개 의 정수가 서로 소 라고 하는 것은 두 숫자의 최대 공약수가 1인 것을 말 합니다. 즉 1 이외에는 두 숫자에서 공통적으로 나눌 수 있는 숫자가 없다는 것 입니다.

오일러 파이 함수 φ(n) 의 특별한 경우로서, 다음이 성립 합니다.

l 만약 n 이 소수라면 , φ(n) = n – 1 입니다.

l 또 양의 정수 n 이 두 개의 소수 p 와 q 의 곱으로 이루어져 있다면,

φ(n) = (p-1) * (q-1) 입니다.

너무 어려운 것 같으니까 예를 들어서 설명해 보겠습니다.

φ(7) 은 1 부터 6 까지의 양의 정수 중에서 7 과 서로 소의 관계에 있는 정수들의 개수를 나타냅니다. 1부터 6까지의 양의 정수 중에서 7 과 서로 소의 관계에 있는 정수는 다음과 같을 것 입니다.

1, 2, 3, 4, 5, 6

모두 6개 의 정수 입니다. 7은 소수이므로, 위에서 설명한 공식을 사용 하면 φ(7) = 7 -1 = 6 이 되며, 이는 위에서 실제로 구한 숫자들의 개수와 일치 합니다.

다른 예를 보겠습니다.

φ(15) 은 1 부터 14 까지의 양의 정수 중에서 15 과 서로 소의 관계에 있는 정수들의 개수를 나타냅니다. 1부터 14까지의 양의 정수 중에서 15 과 서로 소의 관계에 있는 정수는 다음과 같습니다.

1, 2, 4, 7, 8, 10, 11, 13, 14

모두 8개 의 정수 입니다. 15 는 소수인 3과 5 의 곱으로 볼 수 있으므로 , 위에서 설명한 공식을 사용 하면, φ(15) = (3-1) * (5-1) = 2 * 4 = 8 이 되며, 이는 위에서 실제로 구한 숫자들의 개수와 일치 합니다.

5. φ(n) 과 서로소의 관계에 있는 e를 구합니다. 단 e 는 1 < e < φ(n) 의 범위에 있는 수이어야 합니다. φ(n) 과 e 는 서로 소 이므로 둘의 최대 공약수는 1 이어야 합니다.

Gcd( e , φ(n) ) = 1

Gcd(a,b) 는 a 와 b 두 수의 최대 공약수를 나타냅니다.

6. 법 (modulus)에 대해서 알아 봅시다.

RSA 공개키 암호화 알고리즘 에는 여러 가지 어려운 수학 개념들이 많이 등장 한다고 생각 하실 것입니다. 그러나 조금만 생각하시면 그리 어렵지는 않습니다. 실제로 RSA 공개키 암호화 알고리즘은 여러 가지 암호화 알고리즘 중에서 가장 이해하기 쉬운 편에 속합니다.

법 혹은 모듈러스(modulus) 라는 것은 어떤 형식이 반복되는 경우에 그 반복되는 경계점을 말합니다.

예를 들어서 시계를 한번 봅시다. 시계의 분은 60분으로 이루어져 있죠. 시계 에서 초 바늘이 60초를 넘어가면 다시 1초로 됩니다.즉 60 을 경계로 다시 처음인 1부터 시작되는 것이죠. 이 60을 법 또는 모듈러스라고 합니다. 그리고 시계의 초 바늘은 60인 법을 따른 다고 합니다.

법의 정의에 의하여 80분을 60분인 법을 다음과 같이 수학적으로 표현 합니다.

80 ≡ 20(mod 60)

이것은 “80 은 법 60에 대해서 20 과 합동이다” 라고 읽습니다. “≡” 기호는 동치를 나타내는 “=” 기호와는 다르다는 것을 아시기 바랍니다. “≡” 는 의미상 같다는 것을 나타냅니다.

80 ≡ 20(mod 60) 을 실제 동치의 식으로 표현 하면 다음과 같습니다. 연산자 mod를 모듈러스 연산자라고 합니다.

80 mod 60 = 20

즉 80을 모듈러스 60으로 연산하면 그 결과 값은 20이 됩니다.

[잠깐 시작]

RSA 공개키 암호화 알고리즘 에서 법의 개념을 사용 하는 이유

RSA 공개키 암호화 알고리즘에서는 수학적으로 역함수 계산이 어려운 일방향 함수를 구현하기 위해 자리 수가 많은 양의 정수의 소인수 분해 문제를 사용 하고 있지만, 더욱 역방향으로의 계산을 어렵게 하기 위해 법의 개념을 소인수 분해 문제에 더해서 사용합니다.

60인 법에 대해서 80 을 연산한 값은 20임을 알기는 아주 쉽습니다. 그러나 이와 반대인 상황인 60인 법에 대해서 연산한 값이 20일 때 원래의 값인 80을 찾기는 매우 어렵습니다.

왜 그럴까요? 60인 법에 대해서 연산한 값이 20 이 나올 수 있는 수는 80 이외에도 굉장히 많기 때문입니다. 80 이외에도 140 , 200 , 260 … 등 무수히 많은 수가 있습니다. 단지 20 만으로 원래의 80이란 숫자를 찾는 것은 매우 어려운 일입니다.

따라서 법의 개념을 이용 하면 단방향으로는 값을 찾기 쉬우나, 역방향으로는 찾기 어려운 함수를 만들 수가 있습니다.

[잠깐 끝]

7. 오일러의 정리에 대해서 알아 봅시다

오일러의 정리는 위에서 소개한 법의 특수한 경우를 공식으로 만든 것입니다. 두 양의 정수 a 와 n 가 서로 소 라면 다음이 성립 합니다.

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

이것을 식으로 표현 하면 다음과 같을 것입니다.

a^ φ(n) mod n = 1

실제로 이 공식이 맞는지 한번 볼까요?

a = 3, n= 5 로 해서 계산해 봅시다.

5는 소수 이므로 φ(5) = 5-1 = 4 입니다. 따라서,

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

-> 3^4 ≡ 1(mod 5)

-> 81 ≡ 1(mod 5) 로 표현 될수 있습니다. 이것을 식으로 고치면,

-> 81 mod 5 = 1 이므로, 식의 계산이 맞다는 것을 알 수 있습니다.

8. e * d ≡ 1(mod φ(n)) 의 식이 성립하는 d 를 구합니다.

즉 (e * d) mod φ(n) = 1 이 되는 d 를 구합니다. 단 d는 d < φ(n) 의 범위에 있는 정수 입니다.

9. 이제 개인키와 공개키를 모두 구했습니다. 개인키와 공개키의 값은 다음과 같습니다.

개인키 : n, e 공개키 : n, d

이제 개인키와 공개키를 생성 했으므로 암호화와 복호화를 하는 과정을 알아 보겠습니다.

4.3.4 암호화

평문을 M 이라고 합니다.

M 은 정수 이며 , M < n 의 값 입니다.

암호문은 다음과 같이 계산 될 수 있습니다.

C = M^e (mod n)

4.3.5 복호화

암호문을 C 라고 합니다.

암호문은 다음과 같은 식에 의해서 평문으로 계산 될 수 있습니다.

M = C^d (mod n)

4.3.6 실제 적용 해보기

공식으로만 설명 했기 때문에 아마 RSA 알고리즘은 이해하기 어렵다고 생각 하실 것입니다. 그래서 이번 절에서는 실제로 숫자를 넣어 보면서 위에서 설명한 것들을 적용해 보겠습니다.

[소제목]

키 생성

[/소제목]

1. 소수 p 와 q 의 값을 p = 5, q = 7 로 하겠습니다.

2. 그럼 n 값은 다음과 같이 계산 됩니다.

n = p * q = 5 * 7 = 35

3. 오일러 파이 함수 φ(n) 의 값을 구합니다. p 와 q 는 소수 이므로 다음 과 같이 구할 수 있습니다.

φ(n) = (p-1) * (q-1) = (5-1) * (7-1) = 4 * 6 = 24

4. e 값을 정합니다. e 값은 1 < e < n 범위에 있는 값이며, φ(n) 값과는 서로 소가 되어야 합니다. 2 부터 34 까지의 수 중 φ(n) 값인24와 서로 소인 수중 임의의 수를 고르면 됩니다. 위에서 설명 했지만 여기서 고르는 e 값은 개인키로 사용될 것입니다. 임의로 7 을 고르겠습니다.

5. (e * d) mod φ(n) = 1 이 되는 d 를 구합니다. 단 d는 d < φ(n) 의 범위에 있는 정수 입니다. d 값은 공개키로 사용될 것입니다. 아까 e 값을 7로 정했고, φ(n) 가 24 이므로

(7 * d) mod 24 = 1 을 만족하며, d < 24 의 범위에 있는 정수중의 하나는 7 입니다. 따라서 7 을 d 값으로 정하겠습니다.

6. 이제 공개키와 개인키가 정해졌습니다.

개인키: n = 35, e = 7 공개키: n = 35, d = 7

[소제목]

암호화

[/소제목]

위에서 생성한 개인키를 사용 하여 암호화를 해 보겠습니다.

평문을 숫자 3 이라고 합시다.

C = M^e (mod n) 이므로, C = 3^7 (mod 35) = 2187 mod 35 = 17

평문 3이 개인키 (n = 35, e = 7)를 사용하여 암호문 17로 암호화 되었습니다.

[소제목]

복호화

[/소제목]

위에서 만든 암호문을 공개키를 사용하여 복호화 해 보겠습니다.

M = C^d (mod n) 이므로, M = 17^7 (mod 35) = 410338673 mod 35 = 2

앞에서 암호화기 전의 평문과 같은 값이 라는 것을 알 수 있습니다.