[Security] RSA에 대한 정의와 개념에 대한 설명

이번 포스팅에서는 보안 알고리즘의 가장

강력한 알고리즘이자 널리 사용되고 있는

RSA(Rivest Shamir Adleman)에 대해서 알아보는

포스티이에 대해 다뤄보도록 하겠습니다.

 

일단 RSA에 대한 사전적 정의에 대해서

알아보도록 하겠습니다.

 

1977년 론 리베스트(Ron Rivest)와 아디 셰미르(Adi Shamir),

레오나르트 아델만(Leonard Adleman) 등 3명의 수학자에 의해

개발된 알고리즘을 사용하는 인터넷 암호화 인증 및 시스템이다.

3명의 이름 가운데 첫 글자를 모아 붙인 용어이다. Microsoft Window,

Netscape Browser를 비롯해 로터스 등 수백 개의 소프트웨어와 연동이

가능하며, 국제표준화기구(ISO)를 비롯하여, ITU/ANSI/IEEE 등 여러

국제기구에 암호표준으로 제안되어 있다. 소유권은 RSA Security가 가지고 있다.

 

압축 요약하자면 공개키와 개인키를 세트로 만들어서 암호화 / 복호화를

하는 인터넷 암호화 및 인증 시스템의 하나이다.

위의 정의로는 조금 이해하기 어려움이

존재합니다. 그렇기 때문에 저만의 방식으로

쉽게 풀어서 설명을 해보도록 하겠습니다.

 

기본적인 정의부터 다시 저의 방식으로 설명하고

그 뒤에 RSA에 대한 원리와 설명을 이어가도록

해보겠습니다.

 

간단하게 설명하자면 RSA는 정말 풀기 어려운

암호화 / 복호화 알고리즘 입니다.

 

왜 풀기 어려운 알고리즘인가 하냐면,

바로 소인수 분해라는 수학을 사용하기 때문입니다.

 

 

그럼 원리에 대해서 설명을 해보도록 하겠습니다.

 

중학교 때 배운 것으로 기억되는 소인수 분해는

쉽게 설명하자면 숫자 11로 예를 들어 설명하겠습니다

11은 1 * 11 말고는 다른 수 들을 곱하고 지지고 볶고 삶아도

다른 수 2개로 곱해 11이 나올 수가 없습니다.

 

이때, 1과 자기 자신으로 밖에 구할 수 없는 수를

바로 '소수'라고 부릅니다. RSA가 이 소수를 구하는

소인수 분해를 이용하는 이유는 바로

1,079,588,533와 같은 이런 큰 수를 툭 던져놓고

"소인수분해를 통해 소수인지 아닌지를 판별해봐라"

라고 했을 때 막막함을 이용한 암호/복호화

알고리즘입니다. 왜냐하면 저 큰 수를 소인수 분해로

결과를 얻을 때까지 컴퓨터 수백대를 써도 한참의 시간이

걸리기 때문입니다.

 

 

허나 사람 A가 사람 B에게 미리 1,079,588,533이란 수의

힌트로 28,669라는 숫자를 던져준다면, 말은 달라집니다

왜냐하면 1,079,588,533라는 숫자는

28,669 와 37,657의 곱으로 나오는 숫자로서,

소수가 아니기 때문이죠(28,669 * 37,657 = 1,079,588,533)

 

허나 이 힌트를 받지않는 사람은 1,079,588,533이란

숫자를 소인수 분해로 소수인지 아닌지 판별하는데

상당한 어려움을 느끼고 상당한 시간과 노력을 낭비하게

될 수 밖에 없습니다.

 

바로 이 점을 암호화 알고리즘에 이용한 것이 바로

RSA 알고리즘 입니다.

 

한결 쉽게 이해가 되셨을지 모르겠지만,

이제 정말 어려운 실제 원리에 대해서 설명을

이어가보려고 합니다.

 

미리 멘탈 나가지 않도록 꽉 동여메 주시기

바랍니다.

 

 

자 그럼 지금부터, RSA 알고리즘의 원리와 방식에

대해서 설명해보도록 하겠습니다.

 

이건 아직까지 저의 실력이 미숙하여

능수능란하게 쉽게 설명이 불가능하니

양해부탁드립니다.

 

1. 일단 크기가 비슷한 두 소수를 생성합니다.

- 간단하게 a, b라고 정하겠습니다.(임의로)

ex) a = 13, b = 11

 

2. 그럼 이 수를 곱해서 결과 값을 얻을 수가 있습니다.

- a * b = 143

ex)13 * 11 = 143

 

3. 143이란 숫자를 n이라고 이름 붙이겠습니다.

- n = 143

 

4. 그리고 다음 과정을 거칩니다.

- Φ(n) = (a - 1)(b - 1)

ex)120 = 12 * 10

 

5. 다음 조건을 만족하는 e를 선택합니다.

- gcd(e, 120) = 1

ex) 여기서 gcd는 최소공약수를 말합니다.

e, 120 이 두 수가 갖는 가장 큰 공약수인 최대 공약수가

1이어야 하기 때문입니다.

e는 1 < e < Φ(n)의 조건을 성립하여야 합니다.

쉽게 식으로 정리하면 아래와 같습니다.

e = 1 < e < 120

 

여기까지가 암호화 입니다.

 

6. 이제 복호화를 위한 값을 구해보도록 하겠습니다.

구할 값을 미리 d라고 정하겠습니다.

 

d의 조건을 정리하면 아래와 같습니다.

- e.d = 1modΦ(n) and 0 < d < n

여기서 e.d = 1modΦ(n)의 의미는

e.d를 modΦ(n)로 나누고 나머지 값이 1이 될 수있는

수를 구해야한다는 의미입니다.

 

7. Φ(n)는 위에서 구한 값처럼,

- Φ(n) = (a - 1)(b - 1)

ex) 120 = 12 * 10이 됩니다.

또한 d는 0보다 크고 n = 143보다 작아야 합니다.

 

따라서!

∴ (23 * d) / mod120의 나머지가 1이어야 한다.

이라는 결론을 얻을 수 있게 됩니다.

 

8. 이 다음 과정은 인터넷에 mod 구하는 계산기가

수두루 빽빽하게 존재하니 검색하셔서 계산기로 계산하시는

방법을 추천드립니다;;

 

9. 그럼 d = 47 이라는 결과를 얻게 됩니다.

 

10. 이제 보내는 문장과 여태 구한 수식을 종합하자면

아래와 같습니다.

- Text = T, Public Key(n, e)

는 아래의 결과물을 만들어 냅니다.

 

그리고 암호문자 c를 Private Key(n, d)를 이용해

복호화 하는 수식은 아래와 같습니다

 

 

 

 

 

 

여기까지 RSA에 대한 정의와 개념에 대한

설명을 마무리하도록 하겠습니다.

 

제가 많이 부족하여 원리와 방식에 대해

쉽게 설명하기가 어려웠습니다.

이후에 더 많이 공부해서 쉽게 설명할 수 있도록

하겠습니다.

 

 

 

혹시 다른것에 대해 궁금하신게

있으시다면

댓글에 달아주세요

 

아는것이면 친절하게 쉽게

모르는것이면 또 제가 알아내서

친절하게 쉽게 포스팅해서

설명해드리겠습니다