이 페이지의 선택한 이전 버전과 현재 버전 사이의 차이점을 보여줍니다.
the_magic_words_are_squeamish_ossifrage [2010-07-09 03:53] lifthrasiir 새로 만듦 |
the_magic_words_are_squeamish_ossifrage [2011-05-30 18:25] (현재) |
||
---|---|---|---|
줄 5: | 줄 5: | ||
이 문장의 원본은 RSA-129라 불리는, [[RSA시큐리티]]가 ([[Martin Gardner]]를 통해) 1977년 8월 [[사이언티픽아메리칸]]에 게시한 퍼즐에 등장하는 숫자로, 이 숫자는 두 커다란(각각 64, 65자리) [[소수]]의 곱인데 암호문을 풀기 위해서는 원래 숫자로부터 소인수를 얻어 와야 하기 때문에 효율적인 [[소인수분해]] 알고리즘이 필요한 퍼즐이었다. | 이 문장의 원본은 RSA-129라 불리는, [[RSA시큐리티]]가 ([[Martin Gardner]]를 통해) 1977년 8월 [[사이언티픽아메리칸]]에 게시한 퍼즐에 등장하는 숫자로, 이 숫자는 두 커다란(각각 64, 65자리) [[소수]]의 곱인데 암호문을 풀기 위해서는 원래 숫자로부터 소인수를 얻어 와야 하기 때문에 효율적인 [[소인수분해]] 알고리즘이 필요한 퍼즐이었다. | ||
- | 기술의 발전으로 지금은 이 정도의 숫자를 소인수분해하는 데 큰 어려움은 없지만, 문제가 풀린 1994년에만 해도 이 암호를 푸는 데 1400대의 컴퓨터가 필요했을 정도로 쉽지는 않은 문제였다. (초창기 [[그리드컴퓨팅]]의 예제라 할 만 하다.) 퍼즐이 풀린 뒤 상금 100[[달러]]는 [[자유소프트웨어재단]]으로 갔다고 한다. | + | 기술의 발전으로 지금은 이 정도의 숫자를 소인수분해하는 데 큰 어려움은 없지만, 문제가 풀린 1994년에만 해도 이 암호를 푸는 데 1400대의 컴퓨터가 필요했을 정도로 쉽지는 않은 문제였다. (초창기 [[그리드컴퓨팅]]의 예제라 할 만 하다.) 퍼즐이 풀린 뒤 상금 [[USD]]100는 [[자유소프트웨어재단]]으로 갔다고 한다. |
===== 퍼즐의 내용 ===== | ===== 퍼즐의 내용 ===== | ||
줄 23: | 줄 23: | ||
여기서 $$m$$은 원문 $$d$$를 [[RSA]] 암호 체계로 암호화한 암호문으로, 사용된 공개키는 $$(r,e)$$이다. 즉 $$m \equiv d^e \pmod{r}$$이 성립한다. 문제는 이 세 개의 숫자만 가지고 $$d$$를 알아 내라는 것으로, $$d$$는 영문으로 된 문장을 숫자((공백은 ''00'', A~Z까지는 ''01''부터 ''26''까지로 변환해서 그걸 죽 이어 붙인 [[십진수]] 표기))로 표현한 것임이 알려져 있고 $$r$$은 두 소수 $$p$$와 $$q$$의 곱임이 알려져 있다. | 여기서 $$m$$은 원문 $$d$$를 [[RSA]] 암호 체계로 암호화한 암호문으로, 사용된 공개키는 $$(r,e)$$이다. 즉 $$m \equiv d^e \pmod{r}$$이 성립한다. 문제는 이 세 개의 숫자만 가지고 $$d$$를 알아 내라는 것으로, $$d$$는 영문으로 된 문장을 숫자((공백은 ''00'', A~Z까지는 ''01''부터 ''26''까지로 변환해서 그걸 죽 이어 붙인 [[십진수]] 표기))로 표현한 것임이 알려져 있고 $$r$$은 두 소수 $$p$$와 $$q$$의 곱임이 알려져 있다. | ||
- | 비밀키 $$(p,q,x)$$는 알려져 있지 않기 때문에 이들의 값을 수동으로 계산해야 하는데, 사실 $$x$$는 $$ex \equiv 1 \pmod{\phi(r) = (p-1) (q-1)}$$로 계산할 수 있으므로 ([[확장유클리드알고리즘]]을 쓴다) $$p$$와 $$q$$를 알아 내는 게 관건이었다. 실제로 풀린 비밀키는 다음과 같으며: | + | 반대 관계, 즉 $$d \equiv m^x \pmod{r}$$을 만족하는 비밀키 $$(p,q,x)$$는 알려져 있지 않기 때문에 이들의 값을 수동으로 계산해야 하는데, 사실 $$x$$는 $$ex \equiv 1 \pmod{\phi(r) = (p-1) (q-1)}$$로 계산할 수 있으므로 ([[확장유클리드알고리즘]]을 쓴다) $$p$$와 $$q$$를 알아 내는 게 관건이었다. 실제로 풀린 비밀키는 다음과 같으며: |
<code> | <code> |