파이썬 - RSA 암호 해독은 원래 메시지를 반환하지 않습니다. (매우 간단하고 짧은 프로그램입니다.)

Question

그래서 정수 만 암호화/해독하는 아주 간단한 RSA 암호화/암호 해독 프로그램을 만들려고합니다. 하나의 문제를 제외하고 모두 정상적으로 작동합니다. 때로는 암호 해독 된 번호 (메시지)가 원래 번호 (암호화 및 해독해야하는 메시지)와 일치하지 않는 경우가 있습니다. 이것은 내 입력 된 숫자 (메시지)가 내 'n'변수 (n = p * q, 여기서 p와 q는 소수)에있는 숫자에 가까울 때마다 발생합니다. 나는 지금 Stackoverflow를 탐색했고 RSA 알고리즘이 'n'보다 큰 메시지를 적절하게 해독 할 수 없다는 것을 알아 냈습니다. 하지만 제 경우에는 'n'에 가까운 메시지의 암호를 해독하지 못합니다. n = 35이고 입력 번호 (암호화/암호 해독 번호)가 32 인 경우 프로그램은 32가 35보다 낮지 만 32로 다시 해독하지 않습니다 (31, 30 ...). 왜?

코드 :

import math 

def isPrime(n): 
    if n>=2: 
     for m in range(2, int(math.sqrt(n)+1)): 
      if n%m == 0: 
       return False 
     return True 
    else: 
     return False 

def gcd(x, y): 
    while y != 0: 
     (x, y) = (y, x % y) 
    return x 


def phi(n): 
    amount = 0 
    for k in range(1, n + 1): 
     if gcd(n, k) == 1: 
      amount += 1 
    return amount 

def findPubE(n, phiN): 
    for e in range(3, n, 2): 
     if gcd(e,phiN)==1: 
      return e 
    else: 
     raise AssertionError("cannot find 'e'") 


def multiplicative_inverse(a, b): 
    """Returns a tuple (r, i, j) such that r = gcd(a, b) = ia + jb 
    """ 
    # r = gcd(a,b) i = multiplicitive inverse of a mod b 
    #  or  j = multiplicitive inverse of b mod a 
    # Neg return values for i or j are made positive mod b or a respectively 
    # Iterateive Version is faster and uses much less stack space 
    x = 0 
    y = 1 
    lx = 1 
    ly = 0 
    oa = a # Remember original a/b to remove 
    ob = b # negative values from return results 
    while b != 0: 
     q = a // b 
     (a, b) = (b, a % b) 
     (x, lx) = ((lx - (q * x)), x) 
     (y, ly) = ((ly - (q * y)), y) 
    if lx < 0: 
     lx += ob # If neg wrap modulo orignal b 
    if ly < 0: 
     ly += oa # If neg wrap modulo orignal a 
    # return a , lx, ly # Return only positive values 
    return lx 

def encrypt(m,e,n): 
    return (m^(e)) % n 

def decrypt(M, d): 
    return M^(d) 




def main(): 
    p=int(input("Input first prime number (p): ")) 
    q=int(input("Input second prime number (q): ")) 
    n=p*q 
    print("n = ",n) 
    msg= int(input("Input message: ")) 
    assert msg < n 
    phiN=(p-1)*(q-1) 
    e = findPubE(n,phiN) 
    d = multiplicative_inverse(e,phiN) 
    encryptedMsg = encrypt(msg,e,n) 
    decryptedMsg = decrypt(encryptedMsg,d) 



    assert isPrime(p) and isPrime(q) 

    print("phi(n) = ",phiN) 
    print("e = ",e) 
    print("d = ",d) 
    print("Encrypted message: ",encryptedMsg) 
    print("Decrypted message: ",decryptedMsg) 


main() 

Answer 1

그것을 해결! 내 코드에서 두 번 조금 실수했다. 첫 번째 것은 "^"기호가 파이썬에서 "힘의 대상"(올바른 기호는 "**")이고 두 번째 기호는 "mod n"을 줄에 추가하는 것을 잊었다 고 생각한 것입니다. decrypt() 함수 (따라서 return M^(d) 대신 return M**(d) % n).