RSA 암호 알고리즘과 정보이론

1. 기초적인 암호화 방법

• 암호화란 전달하고 싶은 평문을 다른 기호로 변환하는 등의 다양한 조치를 통해 평문의 내용을 숨기는 것을 말한다. 이 과정을 거꾸로 하면 복호화다.
• 직관적이며 기초적인 암호화 방법에는 전치나 매핑을 사용하는 방법이 있다. 전치란 문자 기호들의 재배열을 말한다. 매핑은 한 기호를 다른 기호로 바꾸는 것을 말한다.
• 어린 시절 누구나 암호를 만들며 놀아본 기억이 있을 것이다. 나 또한 초등학교 시절, 한글의 원리를 그대로 사용하는 대신 새로운 문자 기호를 만들어 암호를 만든 기억이 있었다. 어떤 친구는 글자만 재배열해 암호를 만들었다. 우리는 암호화의 원리를 몰랐지만 누구나 알 수 있는 직관적인 방법을 이미 알고 있었던 것이다. (물론 모두 복호화에는 실패했다..)

 

2. 정보 이론에 따른 암호의 도(道)

• 현대 암호화의 종류에는 언뜻 복잡해보이는 기술들이 많다. AES, RSA, ... 이름도 복잡하고 계산식도 복잡하다. 물론 아주 고급 수학이 사용되는 것은 아니다. 개념 자체는 중학교 수준이다. 하라면 할 수는 있다. 그러나 왠지 계산식을 보면 하기 굳이 하고 싶은 마음이 싹 사라지게 만들 정도는 된다. 예전에 RSA 공개키 암호의 원리를 이해하려고 했으나 기술 자체의 생소함과 귀차니즘(?) 때문에 이해를 했음에도 불구하고 결국 시간이 지나 계산식을 까먹은 기억이 있다.
• 그러나 RSA 암호화, 아니 모든 암호화의 궁극적 원리, 목표(道) 자체는 언제나 같다. 그것은 1)암호문에서 정보량을 제거하고, 암호를 푸는 복호화의 경제성을 악화시킨다. 즉, 푸는 것을 어렵게 만드는 것이 아니라 2)푸는 것이 오래 걸리도록 하는 것이다.
• 모든 암호는 풀리기 마련이다. 왜냐하면 암호라는 것이 정보의 내용 자체를 바꾸는 것은 아니기 때문이다. 정보 자체를 바꾸는 것이 아니라, 그 정보를 어떤 기호와 상징으로 표현할 것인가가 관건이다.
• 때문에 아무리 복잡한 기호 변환이나 전치 방법을 마련한다고 해도 그렇게 암호화한 기호에는 "정보 자체의 법칙"이라는 정보가 들어있기 마련이다.
• 예를 들어, 어떤 영어 문장의 기호를 열심히 다른 기호로 바꾼다고 해도, 그 기호가 영어의 원리를 따르는 이상 영어 알파벳의 조합 원리 자체와 호응될 것이다. 영어에서 통계적으로 자주 등장하는 a, e, i, ... 가 많이 등장할 것이다. 또한 ht, rg와 같은 불가능한 조합은 나오지 않을 것이다. z나 q는 빈도가 매우 적을 것이며, 나온다고 하면 z와 q를 사용하는 단어의 개수 자체가 많지 않으므로 함께 쓰인 문자와 비교를 통해 다른 문자의 정체도 알아낼 수 있다... 이런 식이다.

 

• 암호학의 선구자, 클로드 섀넌의 정보 이론의 우수한 통찰은 정보에서 그 의미론적 맥락을 분리해낸 것에 있다. 순수한 정보의 본질을 밝혀낸 것이다. 섀넌은 정보란 불확실성을 감소 시키면 정보량이 많다고 했다. 누구나 알 수 있는 진실이라면 굳이 알아봤자다. 정보량은 없다. 그러나 확률이 가미되는 순간, 정보는 정보량을 갖추게 된다.
• 암호화된 기호들이 나열되어 평문을 알아낼 수 없다고 해서 정보가 없는 것은 아니다. 정보는 다시 말하지만 그것을 알아냄으로 인해 불확실성을 줄여줄 수 있는가다. 암호문 자체의 평문이 어떻든, 그 안에 기호 자체의 구성 원리가 숨어 있다면, 암호문을 확보하면 할수록 정보를 얻게 된다. 많은 데이터를 얻어 통계 분석을 해 어떤 관계나 확률분포를 알아낸다면 평문을 다른 기호로 변환했다고 한들 곧 밝혀질 뿐이다.
• 따라서 암호화의 궁극의 경지는 암호문이 해커에게 빼앗겨도 정보량이 전혀 늘지 않는 것이다. 얻어낸 정보량이 사실상 제로에 가까우려면 어떻게 해야 할까? 암호문끼리 서로 관련이 없으며, 암호문 자체의 기호 서열 또한 거의 랜덤에 가까워 전혀 새로운 정보를 얻어낼 수 없도록 만드는 것이다.
• 암호의 기술 자체는 매번 달라지고 발전한다. 그러나 원리 자체는 한결같이 암호문 자체에서 정보량을 없애버리는 것이다. 암호키를 사용해 복호화한다는 사실, 그리고 그러한 암호키가 어떻게 만들어지는지는 모든 개발자들에게 이미 알려져 있다.
• 공개키 암호화의 핵심은 그걸 풀려고 하면 시간이 너무 오래 걸린다는 점을 이용한다. 즉, 암호문을 복호화하려면 암호키를 알아내야 하는 방법밖에 없도록 만들었으나, 그 방법에 시간이 오래 걸리게끔 만든 것이다. 큰 소수를 활용하는 식으로 암호화된 수열의 무작위성을 증가시켜 암호문 자체에서 정보량을 제거한다. 그리고 큰 소수를 활용한다는 점에서 복호화 과정의 경제성을 의도적으로 악화시킴으로서 암호문의 신뢰도를 높인 것이다.

 

#. 참고

[수학 영재교육] 소수를 활용한 RSA암호 원리, 수학적 원리를 중학생도 이해할 수 있게 설명합니다. / 소수의 실생활 활용 - YouTube