로그인하고 있지 않습니다. 편집하면 당신의 IP 주소가 공개적으로 기록됩니다. 계정을 만들고 로그인하면 편집 시 사용자 이름만 보이며, 위키 이용에 여러 가지 편의가 주어집니다.스팸 방지 검사입니다. 이것을 입력하지 마세요!=== 개인키 유출 === 공격 방법이라고 하기에는 뭐하지만, 비공개 키에 해당하는 <math>p,q,\phi\left(n\right),d</math> 중 단 하나라도 유출되면 나머지 모든 개인키를 취득할 수 있다. 편의상 <math>\phi\left(n\right)=\phi</math>라 하자. #<math>p</math> (또는 <math>q</math>) #:소인수중 하나를 알고 있으므로, <math>n\div p</math>를 계산하여 나머지 소인수를 찾을 수 있다. 두 소인수를 알고 있으므로 <math>\phi</math>를 구할 수 있고, 유클리드 호제법을 사용해서 <math>d</math>를 구할 수 있다. #<math>\phi</math> #:<math>\phi=\left(p-1\right)\left(q-1\right)=pq-p-q+1=n-p-q+1</math>이므로, <math>p+q=n-\phi+1</math>. 또한, <math>pq=n</math>. 따라서, <math>p,q</math>는 이차 방정식 <math>x^2-\left(n-\phi+1\right)x+n=0</math>의 두 근이다. 근의 공식을 이용하면, <math>p,q=\frac{\left(n-\phi+1\right)\pm\sqrt{\left(n-\phi+1\right)^2-4n}}{2}</math>. 한편, <math>d</math>는 유클리드 호제법을 이용하면 된다. #<math>d</math>: 두 가지 방법이 알려져 있다. ##<math>r=de-1</math>이라 하자. 그럼, 적당한 홀수 <math>m</math>에 대해 <math>r=2^km</math>로 나타낼 수 있다. 이제 적당한 <math>a</math>에 대해, <math>b_0\equiv a^m\pmod n</math>이라 하자. 이제 <math>b_0</math>을 연속 제곱하여 <math>b_{u+1}\equiv{b_u}^2\pmod n</math>를 1이 나올 때까지 구한다. <math>k</math>번 연속 제곱하면 반드시 1이 나오게 되어 있으므로 1이 나오지 않을 염려는 할 필요 없다 (이유는 직접 생각해보자). 만약 1이 나오지 않았다면 <math>a</math>와 <math>n</math>이 서로소가 아니라는 뜻이므로, <math>n</math>의 인수를 찾은 셈. 만약 <math>b_{u+1}\equiv1\pmod n</math>이고, <math>b_u\equiv-1\pmod n</math>이면, <math>a</math>의 값을 바꿔 다시 시도한다. 만약 <math>b_{u+1}\equiv1\pmod n</math>이고 <math>b_u\not\equiv\pm1\pmod n</math>이면, <math>\gcd\left(b_u-1,n\right)</math>가 <math>n</math>의 한 인수가 된다. <math>n</math>의 한 인수를 찾았으므로 나머지 인수를 쉽게 찾을 수 있고, <math>\phi</math>도 쉽게 찾을 수 있다. ##<math>de=1+k\phi</math>에서, <math>k</math>를 찾을 수 있다면 <math>\phi</math>를 찾을 수 있다. 우선 양변을 <math>n</math>으로 나누면, <math>\frac{de}{n}=\frac{1}{n}+k\frac{\phi}{n}</math>인데, <math>n</math>이 200자리 숫자고 소인수가 2개밖에 없으므로, <math>\phi\approx n</math>이다. 즉, <math>\frac{de}{n}\approx k</math>. 이제 <math>k</math>를 찾았으므로 <math>\phi</math>를 계산할 수 있고, <math>\phi</math>를 알고 있으므로 <math>n</math>의 두 소인수를 찾을 수 있다. RSA 암호화 과정에서 <math>p,q,\phi</math>를 파기한다고 되어있는데, 실제 복호화에 필요한 것은 <math>d</math>뿐이고, 나머지 값은 유출되면 위 서술한 방법으로 <math>d</math>를 찾는 것이 가능해 놔두면 위험하기 때문이다. 한편, <math>d</math>를 알고 있는데 왜 굳이 소인수 분해를 시도하냐고 생각할 수 있는데, RSA에서 사용하는 소수는 완전한 랜덤이 아니기 때문이다. 인간의 기술로는 완벽한 난수를 생성해낼 방법이 없으며, 뒤에 복잡한 계산식이 있는데,<ref>이를 pseudo-random이라 한다.</ref> 결과물이 많을 수록 그 뒤의 계산식을 유추하는데 도움이 되기 때문이다. 과거 ARPANET을 사용하던 때 위성 시간을 이용해서 난수 키를 생성했던 경우가 있었는데, 시간 별로 생성된 난수키를 분석한 어떤 사람이 취약점을 발견해서 결국 난수 생성 함수가 수정된 전적이 존재한다(...). RSA에서 사용하는 소수도 언젠가는 생성 방식이 밝혀질 수도 있다는 것을 알아두자. 요약: 리브레 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 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: Ă ă Ğ ğ Ŏ ŏ Ŭ ŭ · Ā ā Ē ē Ī ī Ō ō Ū ū · à ã Ñ ñ Õ õ · Å å Ů ů · Ą ą Ę ę · Ç ç Ş ş Ţ ţ · Ő ő Ű ű · Ș ș Ț ț