암호화 - RSA 암호화 알고리즘

암호화에 대한 내용을 찾다가 좋은글을 찾았습니다.

이글을 쓰신분은 너무 정리를 잘해요 ㅡㅡ;

전 이렇게 정리를 할 자신은 없어 그냥 긁어 왔습니다.

출처는 이곳입니다. : http://horensic.tistory.com/109

RSA에 관해서 정리가 잘된 다른 블로그들도 많이 있지만, 직접 이해한 내용을 정리를 해서 보관하려고 합니다. 

일단 RSA 알고리즘은 비대칭키 암호화 알고리즘입니다. 암호화, 복호화를 하기위해 두 개의 키가 필요한데, 하나는 공개를 하고 하나는 개인이 비밀로 가지고 있습니다. 공개를 하는 키는 공개키, 개인이 비밀로 가지고 있는 키는 개인키라고 합니다. 암호화키(공개키)는 , 복호화키(개인키)는 라고 합니다. 이 두 개의 키를 어떻게 만드는 지가 중요합니다. 

1. 암호화 키 생성

먼저 서로 다른 큰 소수 와 를 선택을 합니다. 그리고 이 와 를 곱해서 을 구합니다. 

이   을 가지고   를 찾아야 하는데   을 계산해야 합니다.   은 오일러 파이 함수라고 하는데,   부터   까지 양의 정수에서  과 서로 소의 관계에 있는 정수들의 개수를 구하는 함수입니다. 

예를 들어,  이 6일 때 오일러 파이 함수의 값은 1, 2, 3, 4, 5 중에서 6과 서로 소인 정수의 개수이므로 1, 2, 3, 5 로 4가 됩니다.  이 5라면 1, 2, 3, 4 중에서 5와 서로 소인 정수는 1, 2, 3, 4 이므로 4라는 값이 나오게 됩니다. 특징은 소수   에 대한    의 값은   입니다.

다시 돌아와서 인데, 오일러 파이 함수 특성상  가 성립합니다. 따라서   을 계산하기위해  와 를 알고 있다면 쉽게 구할 수 있는 것입니다. 그래서  입니다. 

이제  를 찾아야 하는데  는   보다는 작고,   과 서로 소인 정수이여야 합니다. 

 를 찾았으면, 메시지  에 대해 암호화를 할 수 있습니다. 암호화된 메시지는 라고 했을 때 암호화 식은 

으로 표현할 수 있습니다. 이렇게 계산하는 이유는  를 가지고  를 계산해 내는 것이 매우 어렵기 때문입니다. 거기다 모듈로  까지 수행을 해주므로 찾기가 더욱 어렵습니다. 

즉 메시지   을 암호화하기 위해서는 공개키  가 필요합니다. 

2. 복호화 키 생성

암호화를 했으므로 복호화를 해야합니다. 개인키 로 어떻게 구하고, 복호화를 할 수 있을까요?

복호화를 하려면 결국 위와 같은 형태로 계산을 해서   이 나와야 하므로  이면 됩니다. 

 와 를 곱했을 때 1이 되는  를 어떻게 구할 수 있을까요? 확장된 유클리드 호제법을 통해서 구할 수 있습니다. 

확장된 유클리드 호제법을 이용하면,  에 대해서  와  의 값을 구할 수 있습니다. 

를 구하기 위한 식을 보여드리겠습니다. 

처음에  를 구할 때  와 서로 소인 정수로 선택을 했습니다. 그렇기 때문에 두 수의 최대 공약수는 1 입니다. 

그러면 확장된 유클리드 호제법을 통해서   와  를 구할 수 있습니다. 

 는 필요 없으니 날려버리면   를 얻을 수 있습니다. 이  는 모듈로  상에서  의 역원입니다. 

이렇게 를 구해서 복호화 계산을 해도 되는 이유는 오일러 정리에 의해서 와 이 서로 소이고 이 자연수 일 때 다음 식이 성립하기 때문입니다. 

이 오일러 정리를 기억하고 복호화 하는 과정을 일단 보겠습니다. 

아마 가장 이해가 안되는 부분이   가 되는 부분일 것입니다. 이것은 확장된 유클리드 호제법에서 변형을 한 것입니다. 

 이 되어야 할 것 같지만  는 임의의 값이므로  로 생각하면 됩니다. 

 은 오일러 정리를 통해서 처리가 되는 부분입니다. 

이렇게 RSA 암호화 알고리즘의 키생성과 암/복호화 과정이 어떤 원리로 고안이 되었는지 살펴보았습니다. 여기서 계산을 빠르게 해주기 위해서 중국인의 나머지 정리(CRT)나 중국인의 나머지 정리에서도 쓰이는 제곱의 반복법이 사용이 됩니다. 

+ 소수의 선택

소수(Prime number)는 양의 약수가 1과 자기 자신 뿐인 1보다 큰 자연수 입니다. 2, 3, 5, 7과 같은 수는 소수입니다. 합성수는 1과 자기 자신이 아닌 다른 자연수의 곱으로 나타낼 수 있는 자연수를 의미 합니다. 소수를 곱하면 합성수가 됩니다. 

큰 합성수를 만들기 위해 큰 소수 두 개를 먼저 선택해야 합니다. 선택한 두 개의 수가 소수인 것은 어떻게 판단할 수 있을까요? 라빈-밀러 소수판별법을 이용하면 됩니다. 라빈-밀러 소수판별법에 대한 수학적 개념은 다루지 않겠습니다. 다만 라빈-밀러 소수판별볍을 통해서 큰 소수 두 개를 선택할 수가 있습니다.