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

Question

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

我用米勒-拉宾测试选择了两个素数，p和q

运行代码后，我能够获得Kpub和e，但是Kpr返回为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

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

第一：使用公共指数pf65537（质数），这是所有RSA实现的默认值（请参见浏览器证书），而不是查找随机值。然后，在计算用于求模逆的扩展欧几里德算法后，您不必再进行任何计算（如果GCD为1，只需返回此值，否则会产生错误或其他任何情况）

以下是删除一些不需要的（函数、导入和随机公共指数）阅读注释后的完整代码

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)))