RSA 암호화 컨텍스트에서 숫자의 모듈 곱셈 역함수를 계산하는 방법은 무엇입니까?

Question

RSA 암호화 컨텍스트에서 숫자의 모듈 곱셈 역함수를 계산하는 방법은 무엇입니까?

Answer 1

직접 누승 잉여 다음

직접 멱승 잉여에있어서, 상기 확장 된 유클리드 알고리즘의 대안으로된다 같이

자료 : http://en.wikipedia.org/wiki/Modular_multiplicative_inverse

Answer 2

두 알고리즘을 상세히 설명있다 Modular multiplicative inverse 위키 백과 문서.

Answer 3

실제로 직접 모듈화 지수보다 훨씬 빠른 Extended Euclidean Algorithm을 사용하십시오. 당신은 DSA의 alghoritm에 대한 w을 계산해야하는 경우

Answer 4

, 당신은이를 사용할 수 있습니다

w = s^-1 mod q 

은 실제로

w = s^(q-2) mod q 

참조 : 나는 간단한 역 기능을했다 http://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Using_Euler.27s_theorem

Answer 5

def privateExponent(p,q,e): 
    totient=(p-1)*(q-1) 
    for k in range(1,e): 
     if (totient*k+1) % e==0: 
      return (totient*k+1)/e 
    return -1 # shouldnt get here 

방정식 d * e = 1 (mod totient)은 d * e = 1 + k * totient (k의 일부 값)로 재 작성 될 수 있으며 프로그램은 e로 나눌 수있는 방정식을 만드는 k의 첫 번째 값을 검색합니다 (공개 지수). e가 작은 경우 (보통 권장 됨) 작동합니다.

성능 향상을 위해 모든 bignum 연산을 루프 밖으로 이동할 수 있습니다.

def privateExponent(p,q,e): 
    totient=(p-1)*(q-1) 
    t_mod_e=totient % e 
    k=0 
    total=1 
    while total!=0: 
     k+=1 
     total=(total+t_mod_e) % e 
    return (k*totient+1)/e 

그것은 전자 = 3, 우리가 정말 답으로 검색하지 않아도 밝혀 항상 2 * ((P-1) * (Q-1) +1)/3

입니다