확장 된 euclid 알고리즘없이 RSA 암호화로 d 찾기

Question

어셈블리를 사용하여 PIC16 마이크로 컨트롤러에 RSA를 구현하려고합니다!
나는 덧셈, 뺄셈, 곱셈 및 모듈러 지수 화 (모두 부호없는)를 수행 할 수있는 수학 라이브러리를 작성했습니다.

하지만 지금은 "D"를 찾는 마지막 단계에 붙어있는 만족 :
d 개 * E = 1 (모드 파이 (N))
가 나는 것입니다 확장 된 유클리드 알고리즘을 구현하지 않도록 할 조금 복잡하고 서명 된 작업이 필요합니다.

내가 http://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Using_Euler.27s_theorem
하지만 그때 내가 찾을 필요가 오일러의 정리와 그것을 계산하려고 파이 (파이 p와 q가 안전 소수가되지 않는 복잡한 과정이다 (N).

내가 왼쪽으로하고있는 유일한 옵션 이 (kN + 1) mod e = 0이 될 때까지 k를 변경하면서 d = (KN + 1)/e를 반복합니다.
이제 내 마지막 질문은 d를 계산하는 유일한 다른 옵션입니까?
(그렇지 않은 경우) 다른 옵션은 무엇입니까?
및 K 제한은 무엇입니까?

Answer 1

확장 유클리드 알고리즘을 구현할 수 있습니다. 알고리즘은 Handbook of Applied Cryptography - Chapter 14.4.3에서 찾을 수 있습니다. 다중 정밀도의 더하기, 빼기 및 교대 만 필요합니다. 노트 : 14.64는이 경우에 승수 역함수 - (d)을 얻기 위해 알고리즘을 최적화하는 방법을 설명합니다.

일반적으로 (e)에 대한 해밍 가중치가 비교적 작은 비교적 작은 소수 ((65537))를 선택하는 것이 일반적입니다. gcd(65537, phi(n)) = 1부터, 곱셈 역함수는 항상 존재합니다.