경고 : 최신판이 아닙니다. 이 문서의 오래된 판을 편집하고 있습니다. 이것을 저장하면, 이 판 이후로 바뀐 모든 편집이 사라집니다. 로그인하고 있지 않습니다. 편집하면 당신의 IP 주소가 공개적으로 기록됩니다. 계정을 만들고 로그인하면 편집 시 사용자 이름만 보이며, 위키 이용에 여러 가지 편의가 주어집니다.스팸 방지 검사입니다. 이것을 입력하지 마세요!'''RSA'''는 세계 최초의 실용적인 [[공개키 암호화]] 알고리즘으로,<ref>[[나무위키]]에서는 RSA = 공개키 암호화 방식이라 되어 있지만, '''틀린 서술이다'''. RSA ⊂ 공개키 암호화 방식이 옳다.</ref> 1977년에 [[MIT]]에서 연구를 하던 Ron Rivest, Adi Shamir, Leonard Adleman에 의해 개발된 암호 알고리즘이다. RSA라는 이름도 저 셋의 성을 순서대로 따와 붙인 것. == 역사 == 암호는 크게 대칭 암호화 방식과 비대칭 암호화 방식의 2가지로 분류된다. 대칭 암호화 방식은 암호화와 복호화의 난이도가 동일한 것을 의미하며, 비대칭 암호화 방식은 복호화의 난이도가 암호화의 난이도보다 어려운 것을 의미한다. 좀 더 자세히 말하면, 대칭 암호화 방식은 암호화를 할 수 있으면 쉽게 복호화를 할 수 있고, 반대로 복호화를 할 수 있으면 쉽게 암호화를 할 수 있는 암호 체계를 말한다. 비대칭 암호화 방식은 암호화는 쉽게 해도 복호화는 어려운 암호 체계. RSA 이전에는 비대칭 암호화 방식이 존재하지 않았기 때문에<ref>정확히 말하면 1973년부터 존재는 했다. 자세한건 후술.</ref> 대칭 암호화 방식이 대중적으로 사용되었는데, 이 대칭 암호화 방식은 [[제 2차 세계대전]] 이후로 급속도로 성장한 암호학의 기준에서 보면 뚫기가 쉽다는 문제가 있었다. 당장 독일군이 절대 뚫지 못할거라 자부했던 [[에니그마]]도 과정이 조금 복잡했을 뿐 대칭 암호화 체계였으며, 결국 연합군 측의 [[수학자]]들에게 뚫려 독일군이 전쟁에서 신나게 털리게 되는 원인이 된다.<ref>사실 에니그마는 처음에 언어학자들을 갈아서 뚫으려고 했으나, {{ㅊ|문과}} 그들의 암호학 지식의 한계 때문에 수학자를 고용하게 되었다는 일화가 있다. 하지만 해독에 가장 큰 역할을 한 것은 연합군이 독일군 잠수함에서 발견한 에니그마 기계(...).</ref> 2차 대전에서 에니그마보다도 훨씬 더 원시적인 암호표를 사용했던 일본군 역시 연합군이 자신들의 암호를 뚫지 못할 것이라 자부했으나, 에니그마보다도 훨씬 더 전에 뚫려 일본군 또한 신나게 털리게 되는 원인이 된다(...). 그리고 시대는 지나 기술은 발전하여 전자 기기의 시대가 눈 앞에 비치고 있었고, 그 시대에 맞춰 안전한 암호화 알고리즘을 개발할 필요성이 대두되고 있었다. 그동한 많은 수학자들은 추상적인 방법으로 비대칭 암호화 방식에 관한 논문을 제시하고 있었으며, 그 중 하나는 1976년에 Whitfield Diffie와 Martin Hellman이 쓴 논문이었다. 이 논문은 비대칭 암호화의 구체적인 방식을 제시하진 않았지만, [[정수론]]을 기반으로 [[모듈러 산술]]과 [[소수]]를 응용한 공개키-비밀키 방식을 구상하였다.<ref>궁금한 사람은 [https://www-ee.stanford.edu/~hellman/publications/24.pdf 여기서] 논문을 볼 수 있다 (영어).</ref> 한편, [[MIT]]의 컴퓨터 과학자 Ron Rivest와 Adi Shamir, 그리고 수학자 Leonard Adleman은 수년간 비대칭 암호화 방식을 연구하고 있었다. Rivest와 Shamir가 암호화 방식을 제시하면 Adleman이 수학적으로 취약점을 찾는 방식으로 연구가 진행되었으며, 그 노력의 결과는 '''수를 곱하는 것은 간단하지만 그걸 다시 [[소인수 분해|분해]]하는 것은 어렵다'''는 아주 간단한 수학적 사실을 기반으로한 암호 체계를 완성시키는 걸로 나타났다. 그들은 이 암호 체계의 이름을 자신들의 성을 딴 '''RSA'''로 지었고, 특허를 출원하게 된다.<ref>특허는 [https://www.google.com/patents/US4405829 여기서] 볼 수 있다 (영어).</ref> 그런데 1997년에 새로운 사실이 발표되는데, 1973년에 이미 영국의 수학자 Clifford Cocks가 RSA와 동일한 암호 체계를 만들었다는 것. 기밀 유지 때문에 그동안 공개되지 않았던 것일 뿐(...). 다만 당시에는 그 연산을 감당할만한 연산 능력을 지닌 컴퓨터가 너무 비쌌기 때문에 그냥 수학적인 사실로만 남았다. {{ㅊ|적어도 공개적으로는...}} 어쨌든 이 RSA는 그 안전성이 인정받아 지금 이순간에도 수많은 웹사이트들이 이용하고 있으며, [[양자 컴퓨터]]의 개발이 완료된다든가 소인수 분해의 새로운 알고리즘이 발견된다든가 하는 이변이 없으면 계속해서 쓰일 것이다. == 과정 == #커다란 서로 다른 두 [[소수]] <math>p,q</math>를 준비한다. 큰의 기준은 '''100자리''' (<math>10^{100}< p,q<100^{101}</math>). #두 소수를 곱한 값인 <math>n=pq</math>를 계산한다. #<math>n</math>의 [[오일러 피 함수]] 값<ref>1에서 <math>n</math>까지의 자연수 중에서 <math>n</math>과 [[서로소]]인 수의 개수.</ref> <math>\phi\left(n\right)</math>을 계산한다. <math>n=pq</math>일 경우, <math>\phi\left(n\right)=\left(p-1\right)\left(q-1\right)</math>이다. #<math>\phi\left(n\right)</math>와 서로소인 수 <math>e</math>를 준비한다. 당연하지만 <math>e\neq1</math>이어야 한다. #이제 <math>ed\equiv1\pmod{\phi\left(n\right)}</math>를 만족시키는 <math>d</math>를 찾는다. #<math>n</math>과 <math>e</math>를 공개하고, <math>d</math>는 숨겨둔다. 앞의 두 값을 '''공개키'''라 부르며, 뒤의 값을 '''개인키'''라 부른다. <math>p, q, \phi\left(n\right)</math>은 유출되면 보안에 문제가 생기니 보통 파기한다. #이제 평서문 <math>m</math>을 암호화하려면, <math>m^e\pmod n</math>을 계산하면 된다. 이 값을 <math>c</math>라 하자. 복호화하려면 <math>c^d\pmod n</math>을 계산하면 된다. [[정수론]]을 좀 공부해본 사람이라면 알겠지만, 매우 간단하다. [[수학 경시대회]]를 준비한 학생이라면 중학생이라도 이해할 수 있을 정도. 이 과정에서 문제가 될만한 부분은 큰 소수를 찾는 1번과 개인키를 만드는 5번, 그리고 큰 수의 지수 계산을 하는 7번 정도. 이 문제점들을 해결하는 방법을 포함해서, RSA의 자세한 원리를 아래에서 알아보자. 아래부터는 특별한 말이 없으면 <math>p,q</math>는 [[소수]], <math>n=pq</math>, <math>e</math>는 공개키, <math>d</math>는 개인키, <math>m</math>은 평서문, <math>c</math>는 암호문으로 가정한다. == 원리 == === 소수 찾기 === 안타깝게도, 100%의 확률로 소수를 찾는 방법은 [[에라토스테네스의 체]]를 제외하고는 아직 존재하지 않는다. 에라토스테네스의 체도 말이 좋아 방법이지, 실제로는 어떤 수를 무작정 나눠서 소인수를 찾는 노가다라는 것을 고려하면, 소수를 확실하게 찾는 방법은 없다고 해도 무방하다. 하지만 어떤 수가 소수가 아님을 보이는 것은 매우 간단한데, [[페르마의 소정리]] 덕분. 페르마 소정리는 다음 명제를 가리킨다. :소수 <math>p</math>와 [[서로소]]인 임의의 <math>a</math>에 대해, <math>a^{p-1}\equiv1\pmod p</math>가 성립한다. 우리가 관심을 가져야 할 것은, 이 명제의 대우이다. :<math>n</math>과 서로소인 어떤 수 <math>a</math>에 대해, <math>a^{n-1}\not\equiv1\pmod n</math>이면 <math>n</math>은 소수가 아니다. :만약 <math>n</math>이 소수라면 페르마 소정리에 의해 <math>a^{n-1}\equiv1\pmod n</math>이어야 하는데, 아니라고 가정했으므로 모순. 따라서 <math>n</math>은 소수가 아니다. 여기서 <math>a</math>의 값으로는 보통 2, 3, 5 등을 사용한다. 수많은 수 중 단 하나만 걸려도 소수가 아님을 판별할 수 있고, 자릿수가 100개를 넘어가면 확률적으로 소수가 아닐 확률이 매우 크기 때문에 판별하는 속도는 극히 빠르다. 문제는 <math>a^{n-1}\equiv1\pmod n</math>인 경우. 페르마 소정리의 역은 성립하지 않기 때문에,<ref>어떤 명제가 참이라고 해서 그 명제의 역까지 참이라는 보장은 없다.</ref> 이것만으로는 <math>n</math>이 소수라고는 단언할 수 없다. 다만 이 경우에는 ''높은 확률''로 <math>n</math>이 소수라고 추측할 수 있을 뿐. 만약 <math>n</math>과 서로소인 모든 <math>a</math>에 대해 <math>a^{n-1}\equiv1\pmod n</math>가 성립한다면, ''매우 높은 확률''로 <math>n</math>이 소수라고 추측할 수 있다. 물론 어느쪽이든, 그 수가 소수라는 보장은 없다. 하지만 확률적인 면에서는 소수라고 단정해도 크게 상관없기 때문에 그냥 쓴다(...). [[매스매티카]] 같은 프로그램에서 소수를 찾는 원리도 바로 이것으로, 2, 3, 5같이 작은 몇 개의 수를 가지고 지수 계산을 해서 모듈러 값이 1인지 체크하고, 전부 1로 나오면 그냥 소수로 간주한다. 그럼 몇 번의 연산을 해야 소수 하나를 찾을 수 있는가 하는 의문이 들 수 있다. 소수는 무한히 많이 존재하지만,<ref>증명은 [[소수]] 문서 참조.</ref> 소수의 분포는 수가 커질수록 줄어듦이 알려져 있다. 특히 자릿수가 100개를 넘어가면 소수의 분포는 매우 희박해져서 소수 하나를 찾는데 매우 많은 시간이 걸릴 것처럼 보인다. 하지만 [[소수 정리]]에 따르면, 자릿수가 100개인 두 소수 사이의 범위는 대략 <math>\ln{10^{100}}=100\ln{10}\approx230</math>이라 230번 정도만 연산을 하면 된다. 손으로는 터무니 없이 오래 걸릴 계산이지만, 현대의 컴퓨터라면 1초도 안걸린다. 당장 매스매티카를 키고 NextPrime 명령어를 입력한 뒤 얼마나 걸리는지 체크해보라. === 오일러 피 함수 === [[오일러 피 함수]]란, 어떤 수보다 작은 자연수 중에서 그 수와 [[서로소]]인 자연수의 개수를 나타내는 함수이다. 정수론을 공부하지 않은 사람이라면 두 수가 서로소임을 보이기 위해 두 수를 소인수 분해하고 공약수가 있는지 찾아보는 방법을 사용할텐데, 실제로 이러면 함수 값 구하는데 터무니 없이 많은 시간이 걸린다(...). 두 수가 서로소라는 것은 두 수의 [[최대공약수]]가 1이라는 것과 동치이며, 두 수의 최대공약수는 [[유클리드 호제법]]을 이용해서 소인수분해 없이 매우 빠른 속도로 계산할 수 있다. 물론 <math>n</math>이 약 200자리의 수라는 것을 고려하면 유클리드 호제법도 오래 걸릴 것 같지만, RSA를 쓰는 사람 입장에서는 유클리드 호제법이고 뭐고 없이 <math>n=pq</math>임을 이용해서 함수값을 매우 쉽게 구할 수 있다. 그냥 <math>\left(p-1\right)\left(q-1\right)</math>를 계산하면 끝이기 때문. 자세한 수학적 이론을 살펴보자. <math>p</math>가 소수라면, <math>\phi\left(p\right)=p-1</math>임을 쉽게 알 수 있고,<ref><math>p</math>가 소수라면 자기보다 작은 모든 수와 서로소야 하므로</ref> 이는 역도 성립하는 명제이다. 한편, 오일러 피 함수는 [[곱셈적 함수]]임이 알려져 있다. 즉, <math>\phi\left(n\right)=\phi\left(pq\right)=\phi\left(p\right)\phi\left(q\right)=\left(p-1\right)\left(q-1\right)</math>. 이를 일반화시키면, <math>n=\prod_{i=1}^k{p_i}^{e_i}</math>(<math>p_i</math>는 서로 다른 소수, <math>e_i</math>는 1 이상의 자연수)에 대해 <math>\phi\left(n\right)=\prod_{i=1}^k\left(1-\frac{1}{p_i}\right)</math>임이 알려져 있다. 이 일반화에 대한 증명은 곱셈적 함수임을 이용하거나, [[포함과 배제의 원리]]를 이용해서 증명할 수 있다. 어쨌든 RSA 사용자 입장에서 중요한 것은, <math>\phi\left(n\right)</math>의 계산이 간단하다는 것 뿐(...). === 유클리드 호제법 === {{각주}} [[분류:암호학]] 요약: 리브레 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 3.0 라이선스로 배포됩니다(자세한 내용에 대해서는 리브레 위키:저작권 문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요. 글이 직접 작성되었거나 호환되는 라이선스인지 확인해주세요. 리그베다 위키, 나무위키, 오리위키, 구스위키, 디시위키 및 CCL 미적용 사이트 등에서 글을 가져오실 때는 본인이 문서의 유일한 기여자여야 하고, 만약 본인이 문서의 유일한 기여자라는 증거가 없다면 그 문서는 불시에 삭제될 수 있습니다. 취소 편집 도움말 (새 창에서 열림) | () [] [[]] {{}} {{{}}} · <!-- --> · [[분류:]] · [[파일:]] · [[미디어:]] · #넘겨주기 [[]] · {{ㅊ|}} · <onlyinclude></onlyinclude> · <includeonly></includeonly> · <noinclude></noinclude> · <br /> · <ref></ref> · {{각주}} · {|class="wikitable" · |- · rowspan=""| · colspan=""| · |} {{lang|}} · {{llang||}} · {{인용문|}} · {{인용문2|}} · {{유튜브|}} · {{다음팟|}} · {{니코|}} · {{토막글}} {{삭제|}} · {{특정판삭제|}}(이유를 적지 않을 경우 기각될 가능성이 높습니다. 반드시 이유를 적어주세요.) {{#expr:}} · {{#if:}} · {{#ifeq:}} · {{#iferror:}} · {{#ifexist:}} · {{#switch:}} · {{#time:}} · {{#timel:}} · {{#titleparts:}} __NOTOC__ · __FORCETOC__ · __TOC__ · {{PAGENAME}} · {{SITENAME}} · {{localurl:}} · {{fullurl:}} · {{ns:}} –(대시) ‘’(작은따옴표) “”(큰따옴표) ·(가운뎃점) …(말줄임표) ‽(물음느낌표) 〈〉(홑화살괄호) 《》(겹화살괄호) ± − × ÷ ≈ ≠ ∓ ≤ ≥ ∞ ¬ ¹ ² ³ ⁿ ¼ ½ ¾ § € £ ₩ ¥ ¢ † ‡ • ← → ↔ ‰ °C µ(마이크로) Å °(도) ′(분) ″(초) Α α Β β Γ γ Δ δ Ε ε Ζ ζ Η η Θ θ Ι ι Κ κ Λ λ Μ μ(뮤) Ν ν Ξ ξ Ο ο Π π Ρ ρ Σ σ ς Τ τ Υ υ Φ φ Χ χ Ψ ψ Ω ω · Ά ά Έ έ Ή ή Ί ί Ό ό Ύ ύ Ώ ώ · Ϊ ϊ Ϋ ϋ · ΐ ΰ Æ æ Đ(D with stroke) đ Ð(eth) ð ı Ł ł Ø ø Œ œ ß Þ þ · Á á Ć ć É é Í í Ĺ ĺ Ḿ ḿ Ń ń Ó ó Ŕ ŕ Ś ś Ú ú Ý ý Ź ź · À à È è Ì ì Ǹ ǹ Ò ò Ù ù · İ Ż ż ·  â Ĉ ĉ Ê ê Ĝ ĝ Ĥ ĥ Î î Ĵ ĵ Ô ô Ŝ ŝ Û û · Ä ä Ë ë Ï ï Ö ö Ü ü Ÿ ÿ · ǘ ǜ ǚ ǖ · caron/háček: Ǎ ǎ Č č Ď ď Ě ě Ǐ ǐ Ľ ľ Ň ň Ǒ ǒ Ř ř Š š Ť ť Ǔ ǔ Ž ž · breve: Ă ă Ğ ğ Ŏ ŏ Ŭ ŭ · Ā ā Ē ē Ī ī Ō ō Ū ū · à ã Ñ ñ Õ õ · Å å Ů ů · Ą ą Ę ę · Ç ç Ş ş Ţ ţ · Ő ő Ű ű · Ș ș Ț ț 이 문서에서 사용한 틀: 틀:Skin (원본 보기) (준보호됨)틀:ㅊ (원본 보기) (준보호됨)틀:각주 (원본 보기) (준보호됨)틀:둘러보기 상자 (원본 보기) (보호됨)틀:둘러보기 상자/핵심 (원본 보기) (보호됨)틀:소수 (편집) 틀:참고 (원본 보기) (준보호됨)틀:취소선 (원본 보기) (준보호됨)틀:틀바 (원본 보기) (준보호됨)