为什么我的 RSA 密钥函数返回 nan？

Question

我目前正在从事一个项目，该项目使用欧几里德算法复制 RSA 密钥生成和测试，扩展欧几里德算法以找到值的模逆。

我使用 Miller-Rabin 测试选择了两个素数 p 和 q。

在运行代码之后，我能够获得 Kpub 和 e，但是 Kpr returns 作为 nan。

请帮忙！

#Euclidean Algorithm func

def EucAlgo(a, b):
  if a==0:
    return b
  return EucAlgo(b % a,a)

def ExEucAlgo(a,b):
  if a==0:
    return b,0,1
  gcd, s1, t1 = ExEucAlgo(b%a,a)
  #gcd of a,b
  s = t1 - (b/a) * s1
  t = s1
  return gcd, s, t

def ExEucAlgo_modInverse(a,b):
  gcd, s, t = ExEucAlgo(b,a)
  if (gcd == 1):
    i = t % a
  elif (gcd !=1):
    print("There is no inverse modulo for the input.")
  return i

def SqMul_ModularExpo(b, exp, n):
  bin_exp = bin(exp)
  base = b
  for i in range (3, len(bin_exp)):
    base = (base ** 2) % n
    if(bin_exp[i]=='1'):
      i+=1
      base = (base * b) %n 
  return base

#RSA Key generation
p=9054583561027584891319616491815785011595937977633787663340258672121877196627062461308487615739189212918799813327175451021729047602129396754172486202100997 
q=10115395220079214686776355235686624745626962891667413288473649946208213820942557513105240135405981494333016032659525466362014175268953946332375459648688023
n= p * q
phi_n= (p-1) * (q-1)
e= randint(1, phi_n - 1)
while((EucAlgo(e,phi_n)) !=1):
  e = randint(1, (phi_n-1))
d = ExEucAlgo_modInverse(e,phi_n)
print(f"\nKpr={d}")
print(f"\nKpub=(n={n})\n \ne={e}")

Answer 1

问题是您正在使用浮点除法，这将导致 return 浮点，在处理大 int 时会导致 python 无法处理的非常大的浮点数所以解决方案是使用整数除法，这意味着 5//2=2 而不是 2.5。问题是现在加密和解密数据会导致错误的解密。（你不会再得到 2）因为你的函数中有一些错误。

首先：使用 public 指数 pf 65537（质数），这是所有 RSA 实现的默认值（请参阅您的浏览器证书），而不是随机寻找一个。然后在计算用于查找模逆的扩展欧几里德算法后，您不必再进行任何计算（如果 GCD 为 1，则只需 return 此值，否则会引发错误或其他任何问题）。

这是删除一些不需要的（函数、导入和随机 public 指数）后有效的完整代码阅读评论。

def EucAlgo(a, b):
    if a == 0:
        return b
    return EucAlgo(b % a, a)

def ExEucAlgo(a,b):
  if a==0:
    return b, 0, 1
  gcd, s1, t1 = ExEucAlgo(b%a, a)
  
  # You dont use / use // to make integer division
  s = t1 - (b//a) * s1
  t = s1
  return gcd, s, t

def ExEucAlgo_modInverse(a,b):
    gcd, s, t = ExEucAlgo(a, b)
    if (gcd == 1):
        # Just return s which is the inverse of public exponent
        return s
    elif (gcd != 1):
        # I think it's better to raise an error but it's up to you
        print("There is no inverse modulo for the input.")

#RSA Key generation
p = 9054583561027584891319616491815785011595937977633787663340258672121877196627062461308487615739189212918799813327175451021729047602129396754172486202100997
q = 10115395220079214686776355235686624745626962891667413288473649946208213820942557513105240135405981494333016032659525466362014175268953946332375459648688023
n = p * q
phi_n = (p-1) * (q-1)

# Just use fixed prime public exponent rather than trying fixed ones
e = 65537
d = ExEucAlgo_modInverse(e, phi_n)
print(f"\nKpr={d}")
print(f"\nKpub=(n={n})\n \ne={e}")

# Try to encrypt and decrypt 36
ciphertext = pow(36, e, n)
print("Encrypted data {}".format(ciphertext))
print("Decrypted data is {}".format(pow(ciphertext, d, n)))

为什么我的 RSA 密钥函数返回 nan？

Why is my RSA key function returning nan?

python

cryptography

rsa