已知质数p,q，公钥（指数）e，求私钥d。
利用欧拉定理解私钥d，利用扩展欧几里得求逆元。
python代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | def CPPDiv(a,b): return int(a/b) def CPPMod(a,b): quotient = CPPDiv(a,b) return a-b*quotient def ExGCD(a,b,x,y): # Return GCD,x,y if b==0: return a, 1, 0 d, y, x = ExGCD(b, CPPMod(a,b), y ,x) y -= CPPDiv(a,b)*x return d, x, y def ExGCD_Cal(a,b): return ExGCD(abs(a),abs(b),0,0)[1:] def QuickPow(a,b,MOD): if b==0: return 1 result = QuickPow(a,b//2,MOD) % MOD result *= result if b&1==1: result *= a result %= MOD return result def solveRSAd(n,phi,e): u, v = ExGCD_Cal(e, phi) if v>0: u += phi v = e-v return u def Main(): p = int(input("Prime p:")) q = int(input("Prime q:")) phi = (p-1)*(q-1) n = p * q print("Mod N: %d" % n) e = int(input("Public Key e:")) d = solveRSAd(n, phi, e) print("Private Key d: %s" % d) if __name__ == '__main__': Main() |
已知质数p,q，公钥（指数）e，和密文c，解出私钥d和明文m。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | def CPPDiv(a,b): return int(a/b) def CPPMod(a,b): quotient = CPPDiv(a,b) return a-b*quotient def ExGCD(a,b,x,y): # Return GCD,x,y if b==0: return a, 1, 0 d, y, x = ExGCD(b, CPPMod(a,b), y ,x) y -= CPPDiv(a,b)*x return d, x, y def ExGCD_Cal(a,b): return ExGCD(abs(a),abs(b),0,0)[1:] def QuickPow(a,b,MOD): if b==0: return 1 result = QuickPow(a,b//2,MOD) % MOD result *= result if b&1==1: result *= a result %= MOD return result def solveRSAd(n,phi,e): u, v = ExGCD_Cal(e, phi) if v>0: u += phi v = e-v return u def Main(): p = int(input("Prime p:")) q = int(input("Prime q:")) phi = (p-1)*(q-1) n = p * q print("Mod N: %d" % n) e = int(input("Public Key e:")) d = solveRSAd(n, phi, e) print("Private Key d: %s" % d) c = int(input("Cipher c:")) m = pow(c,d,n) print("Plain m: %s" % str(hex(m))) if __name__ == '__main__': Main() |
参考链接：
https://www.freebuf.com/sectool/163781.html
还有一本数论概论:)