저는 RSA에 대한 논문을 쓰는 고등학생이며, 소수의 소수를 예로 들어 설명하고 있습니다. 나는 그 시스템이 어떻게 작동 하는지를 이해하지만, 나는 확장 된 유클리드 알고리즘을 사용하여 개인 키를 계산할 수 없다. 여기 RSA : 확장 유클리드 알고리즘을 사용한 개인 키 계산
는 지금까지 수행 한 작업은 다음과 같습니다- 나는 소수의 페이지를 선택한 = (37)와 q = 89과 계산을 N = 3293
- 내가 계산했다 (P-1) (Q -1) = 3168
- 저는 e와 3168이 상대적으로 소수가되도록 숫자 e를 선택했습니다. 나는 이것을 표준 유클리드 알고리즘으로 검사하고 있는데, 이것은 잘 작동한다. 내 전자 = 25 이제
난 그냥하도록 D를 찾기 위해 확장 유클리드 알고리즘을 사용하여 ED = 1 (모드 3168)
을 만족해야 개인 키 D를 계산해야 + tN에서 = 1 드 나는 -887 • 25 + 7 • 3168 = 1을 얻는다. 나는 7을 버리고 d = -887을 얻는다. 그러나 메시지의 암호를 해독하려고하면 작동하지 않습니다.
나는 내 책에서 d가 2281이어야하고 작동한다는 것을 알고 있지만 어떻게 그 숫자에 도달했는지 알 수 없다.
아무도 도와 줄 수 있습니까? 지난 4 시간 동안이 문제를 해결하기 위해 노력했지만 어디에서나 답을 찾았습니다. 저는 확장 유클리드 알고리즘을 직접하고 있습니다 만, 결과가 제대로 작동하기 때문에 계산이 올바르게되어야합니다. 당신은 너무 가까이있어 사전에
감사합니다,
MADS
Ninefingers가 지적했듯이 양수의 나머지 부분 만 사용하십시오. 동등하게, 부정적인 힘'x'에 무언가를 올리기 위하여는 먼저 그것의 반대를 산출하고 그 후에 그것을 ('-x') 힘 ('-x'는'x '가 부정이기 때문에 긍정적''-x)으로 올리십시오. –
"de + tN = 1"-887 • 25 + 7 • 3168 = 1을 얻는 방법에 대해 혼란스러워합니다. 나는 e = 25를 이해하지만 d, t, N은 의미가 없다. d, t, N은 무엇을 의미합니까? 왜 7을 버리도록 허락을 받았습니까? 케이시 –