加密

\(y=x^e\mod n\)

其中\(x\)是明文，\(e\)是在\((1,m)\)中随机选取的一个数（常选\(65537\))，但是要满足\(gcd(m,e)=1\)

\(n\)是由随机选取的两个很大的质数\(p,q\)相乘得到的

解密

我们考虑如何根据密文等到明文

\(x=y^d\mod n\)

其中\(d\)是\(inv(e\mod phi(n))\)

这样根据\(y\)和\(e\)还有\(n\)我们就能求出明文了

phi=(p-1)*(q-1)#p,q是对n做质因子分解得到的
d=invert(e,phi)
ans=pow(c,d,n)#表示c^d mod n  c是明文 ans就是密文了

这里讲如何分解这种很大的质数，一种是利用网站factordb，或者是用yafu工具

cmd   yafu-x64 factor(n)

\(gmpy2\)是自带求欧拉函数的

eular_phi(n)

当\(n\)很大\(e\)很小时？

考虑\(x=\sqrt[3]{y+k*n}\)这个式子

我们枚举\(k\)来验证开根出来的是否为整数即可，是整数就代表我们找到了\(x\)

from gmpy2 import *
e = 3
n = big
c = big
k = 0
while 1:
	res = iroot(c+k*n,e)#开高次根号，返回值的第一个表示开出的数，第二个true/false表示是否是整数
	if(res[1] == True):
	print(long_to_bytes(int(res[0])))
	break
	k = k + 1

当\(n\)很大但有两套\(n,e,y\)时？

一般可以求两个\(n\)的\(gcd\)然后对\(n\)做质因数分解，剩下的流程一样

import gmpy2
import binascii
e = 65537
n1 =big1
c1 =big2
n2 =big3
c2 =big4
p = gmpy2.gcd(n1,n2) # 欧几里得算法
q = n1 // p
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c1,d,n1)
print(binascii.unhexlify(hex(m)[2:]))
#hex()转为16进制
#unhexlify将16进制转为2进制