已知常规RSA算法原理可由以下五个式子表达
$$m^e\equivc(mod~~n)\tag{1}$$
$$c^d\equivm(mod~~n)\tag{2}$$
$$n=p\timesq\tag{3}$$
$$φ(n)=(p-1)\times(q-1)\tag{4}$$
$$e\timesd\equiv(mod~~phi)\tag{5}$$
而非常规RSA算法原理与常规RSA算法原理仅(4)(5)式不同
(4)式改为
$$n=p^{p'}\timesq^{q'}\timesr^{r'}\timess^{s'}\times···\tag{6}$$
而(5)式改为
$$φ(n)=p^{p'-1}\times(p-1)\timesq^{q'-1}\times(q-1)\timesr^{r'-1}\times(r-1)\timess^{s'-1}\times(s-1)\times···\tag{7}$$
由上述式子可得到当n可以被分解时，很容易得到p,q,r,s,p',q',r',s'的值
可以通过(4)计算得到φ(n)
进而求e在模φ(n)条件下的模逆d
即可获取明文
那么如合通过实际可行的办法分解n
e:加密钥整数集合或列表
yin:n分解得到的所有因数的集合或列表
\(e_1\):加密钥举例1
\(c_1\):用加密钥举例1加密m得到的密文
\(e_2\):加密钥举例2
\(c_2\):用加密钥举例1加密m得到的密文
假设e1,e2互质，即：
$$gcd(e_1,e_2)=1\tag{1}$$
即存在：
$$e_1*s_1+e_2*s_2~=~1\tag{2}$$
$$\becausec_1=m^{e_1}(\modn),c_2=m^{e_2}(\modn)\tag{3}$$
$$\thereforec_1^{s_1}\timesc_2^{s_2}\equiv(m^{e_1})^{s_1}\times(m^{e_2})^{s_2}(\modn)\tag{4}$$
由(2)式与(4)式得：
$$c_1^{s_1}\timesc_2^{s_2}\equivm^1(\modn)\tag{5}$$
由此可得，当求出\(s_1\)和\(s_2\)时，即可解得获得明文
如何求\(s_1\)与\(s_2\)
fromCrypto.Util.numberimportlong_to_bytes,bytes_to_longfromgmpy2importinvertfromegcdimportegcd#RSA共模攻击defRSA_mo(n,e1,c1,e2,c2):'''#RSA共模攻击'''s,s1,s2=egcd(e1,e2)ifs1<0:s1,s2=s2,s1e1,e2=e2,e1c1,c2=c2,c1ifs!=1:return'不能进行共模攻击'c2=invert(c2,n)m=(pow(c1,s1,n)*pow(c2,-s2,n))%nreturnm,long_to_bytes(m)2.代码说明1.输入说明2.输出说明返回m的数值与字符值
m:明文
$$phi=(p-1)\times(q-1)=p\timesq-p-q+1\tag{1}=n-(p+q)+1$$
$$\becausep\timesq>>p+q\tag{2}$$
$$\thereforephi\approxn\tag{3}$$
$$e\timesd\equiv1(\modphi)\newlinee\timesd-1=k\timesd\tag{4}$$
由(2)两边同时除\(d\timesphi\)可得：
$$\dfrac{e}{phi}-\dfrackd=\dfrac1{d\timesphi}\tag{5}$$
$$\because\dfrac1{d\timesphi}\approx0\tag{6}$$
$$\therefore\dfrac{e}{phi}\approx\dfrackd\tag{7}$$
$$(p+q)=n-phi+1\tag{8}$$
再通过构造方程
$$x^2-(p+q)+p\timesq=0\tag{9}$$
求解方程即可得到p,q的值
fromCrypto.Util.numberimportlong_to_bytesfromgmpy2importinvert,isqrtfromlibnumimportn2s,s2n#低解密指数攻击#条件：d dp:d对(p-1)取模 当dp泄露时，n可分解成的素数种类大大降低，变得“可预测” $$dp\equivd\mod(p-1)\tag{1}$$ \(dp\timese\equivd\timese\mod(p-1)\) \(d\timese=k\times(p-1)+dp\timese\) \(d\timese\equiv1\mod(p-1)\times(q-1)\) \(k\times(p-1)+dp\timese\equiv1\mod(p-1)\times(q-1)\) \(k\times(p-1)+dp\timese=k_1\times(p-1)\times(q-1)+1\) \(dp\timese=(k_1\timesq+k_1-k)\times(p-1)+1\) 设：\(X=(k_1\timesq+k_1-k)\) \(dp\timese=X\times(p-1)+1\tag{2}\) \(dp<(p-1)\) \(e>X\) \(X\in[0,e]\) 遍历[0,e]即可找出X，进而通过上述公式求得p，从而达到n分解的目的 fromCrypto.Util.numberimportlong_to_bytesfromgmpy2importinvertfromfactordb.factordbimportFactorDB#dp泄露攻击defRSA_dp_reveal(dp,e,n,c):forXinrange(2,e):if(dp*e-1)%X==0:p=(dp*e-1)//X+1ifn%p==0:q=n//pbreakphi=(p-1)*(q-1)d=invert(e,phi)ci=long_to_bytes(pow(c,d,n))returnci