0
私は非常に単純なRSA暗号化/復号化プログラムを作成しようとしています。 1つの問題を除いて、すべて正常に動作します。暗号化された番号（メッセージ）が元の番号（暗号化と復号化に必要なメッセージ）と一致しないことがあります。これは、入力された数字（メッセージ）が自分の「n」変数（n = p * q、pとqは素数）の数字に近いときに発生するようです。私は今少しStackoverflowを閲覧し、RSAアルゴリズムが 'n'より大きいメッセージを適切に復号化できないことを発見しました。しかし、私の場合は、 'n'に近いメッセージの復号化に失敗します。 n = 35で、入力番号（暗号化/復号化する番号）が32の場合、プログラムは32が35よりも小さいにもかかわらず、32に正しく復号化されません。どうして？Python - RSA解読で元のメッセージが返されない（非常に単純で短いプログラム）
コード：
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()
'^'は*ではありません* Pythonの指数演算子で、 '**'はです。いずれにせよ、べき乗剰余演算は、単に引数の3つの引数を持つ組み込み[pow]（https://docs.python.org/3/library/functions.html#pow）関数を使うべきです。 '^'は排他的OR演算子です。それは、（32^5）％35がpow（32,5,35）に等しいという陽気な偶然の一致です。 –
ああ、ハハ。 OK。私はPythonを使って以来、ずっとずっと続いていたので、私は '^'が "シンボルの力に"あると仮定しました。しかし、コードの残りの部分はうまくいきますよね？ – Schytheron
いいえ、実際にはありません。あなたが 'encrypt（m、e、n）'メソッドを持っているなら、あなたの解読メソッドは 'decrypt（M、d、n）'のように見えるはずです。 –