我的Miller-Rabin实现存在问题？基于NIST FIPS186-4的RSA加解密验证失败

Hey there, let's dig into why your RSA decryption isn't matching the original message. When you see the decrypted plaintext being way larger than the original and plain == message returning False, it's almost always a breakdown in the key generation pipeline—here are the most likely culprits to check:

1. Verify Your Miller-Rabin Prime Generation #

First off, make sure the primes p and q you're generating are actually valid primes. Even though you're following FIPS186-4 C.3.1, small implementation mistakes here can produce pseudoprimes that break RSA's math:

• Test your Miller-Rabin function against known values: Feed it small primes like 61 or 53 to confirm it correctly identifies them as prime, and throw a pseudoprime like 341 at it to ensure it flags it as composite.
• Double-check you're adhering to FIPS186-4's requirements: For primes of 512 bits or longer, the spec mandates specific base values or sufficient test rounds to meet security standards. Cutting corners here is a common way to end up with bad primes.

2. Check Private Key d Calculation #

The private key d needs to be the multiplicative inverse of e modulo φ(n) = (p-1)*(q-1). This step has two common failure points:

• Wrong φ(n) calculation: If you accidentally used p*q instead of (p-1)*(q-1), or messed up the subtraction, your inverse will be completely wrong.
• Broken Extended Euclidean Algorithm: If your implementation of the algorithm to compute the inverse has bugs, d won't actually satisfy (e*d) % φ(n) == 1. Always verify this condition—if it's not true, that's your problem right there.
• Also, ensure e is coprime with φ(n) (i.e., gcd(e, φ(n)) == 1). If they share a common divisor, no valid inverse exists, and your d is useless.

3. Validate n = p*q #

It sounds simple, but double-check that n is correctly calculated as the product of p and q. Overflows, bit truncation, or endianness issues when storing n can all throw off your modular arithmetic, leading to garbage decryption results. Manually compute p*q and compare it to the n your code generates to rule this out.

4. Test Encryption/Decryption with Known Good Keys #

Isolate your encryption/decryption logic to confirm it works independently of your key generator. Use a set of proven RSA parameters:

• Let p=61, q=53, so n=61*53=3233, φ(n)=60*52=3120
• Choose e=17 (since gcd(17, 3120)=1)
• The inverse d=2753 (because 17*2753 % 3120 = 1)

Run your encryption and decryption code with these values:

n, e, d = 3233, 17, 2753
message = 1234567890
cipher = pow(message, e, n)
plain = pow(cipher, d, n)
print(plain == message % n)  # Should return True

If this works, your encryption/decryption logic is solid—all problems are in your key generation. If it fails, you've got a bug in how you're using modular exponentiation.

Quick Debug Tip #

Modify your generating_Pairs() function to spit out all intermediate values so you can spot anomalies:

def generating_Pairs():
    p = generate_prime()
    q = generate_prime()
    phi = (p-1)*(q-1)
    e = choose_e(phi)
    d = mod_inverse(e, phi)
    
    # Print debug info
    print(f"p: {p}")
    print(f"q: {q}")
    print(f"φ(n): {phi}")
    print(f"e: {e}")
    print(f"d: {d}")
    print(f"e*d mod φ(n): {(e*d) % phi}")
    print(f"n: {p*q}")
    
    return p*q, e, d

For example, if e*d mod φ(n) isn't 1, you know immediately that d was calculated incorrectly.

内容的提问来源于stack exchange，提问作者GenXGer