1
互质关系
如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。关于互质关系，不难得到以下结论：
任意两个质数构成互质关系，比如13和61。
一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。
如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。
1和任意一个自然数是都是互质关系，比如1和99。
p是大于1的整数，则p和p-1构成互质关系，比如57和56。
p是大于1的奇数，则p和p-2构成互质关系，比如17和15。
2
欧拉函数
在数论中，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目。
φ(n) 的计算方法：
第一种情况如果n=1，则 φ(1) = 1 。因为1与任何数（包括自身）都构成互质关系。
第二种情况如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。
第三种情况如果n是质数的某一个次方，即 n = p^k (p为质数，k为大于等于1的整数)，则
第四种情况如果n可以分解成两个互质的整数之积，
n = p1 × p2
则
φ(n) = φ(p1p2) = φ(p1)φ(p2)
即积的欧拉函数等于各个因子的欧拉函数之积。
第五种情况因为任意一个大于1的正整数，都可以写成一系列质数的积。
根据第4条的结论，得到
再根据第3条的结论，得到
也就等于
3
欧拉定理
4
模反元素
如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。
5
密钥生成步骤
φ(n) = (p-1)(q-1)
ed ≡ 1 (mod φ(n))
ed - 1 = kφ(n)
ex + φ(n)y = 1
17x + 3120y = 1
6
加密和解密
有了公钥和密钥，就能进行加密和解密了。
7
互质关系实例题目
这类题目是RSA的基础题目，往往会给出很多已知的条件，利用公式求出未知的条件，所以会和基础的算法关系比较密切。
比如题目给出了p、q、e的值，求出d，可以把已知的条件带入到基本的公式中，知道了p、q就可以利用φn = (p−1) * (q−1) 和n = p * q求出φn和n，那么知道了φn和e就可以根据e * d ≡ 1 (mod φn)求出d。当然求其它的参数也是一样的道理。
题目
已知：
p=447685307 q=2037 e=17 提交flag{d}
解密RSA的题目往往会通过编写python脚本的方式，这道题目脚本为：
import gmpy2from Crypto.Util.number import long_to_bytes,bytes_to_longp=447685307q=2037e=17fn = (p-1)*(q-1)d = gmpy2.invert(e, fn)print(d)
可得出d的值为
c1 = pow(m, e1, n) c2 = pow(m, e2, n)
(a * b) % p = (a % p * b % p) % p a ^ b % p = ((a % p) ^ b) % p
(c1^s1*c2^s2)%n = ((m^e1%n)^s1(m^e2%n)^s2)%n
(c1^s1*c2^s2)%n = ((m^e1%n)^s1(m^e2%n)^s2)%n =((m^e1%n)^s1*(m^e2%n)^s2)%n =((m^e1)^s1%n*(m^e2)^s2%n)%n //消掉%n =((m^e1)^s1*(m^e2)^s2)%n =((m^(e1*s1)*(m^(e2*s2))%n //幂的乘方，底数不变，指数相乘 =(m^(e1*s1+e2*s2))%n //同底数幂相乘，底数不变，指数相加
(c1^s1*c2^s2)%n = (m^1)%n (c1^s1*c2^s2）%n=m
所以，在相同的m、n,不同的e，进行加密后。在不需要知道d的情况下，是可以进行解密的。这就是RSA共模攻击的运算过程。
由题目条件可以得出，第一个大括号和第二个大括号中的第一个大数据是一样的，表示大整数n，后面的773和839表示的是e1和e2，c1和c2也给出了，这就满足了共模攻击的条件，输出m即为flag，以下是解题脚本：
import gmpy2import libnumn=6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249e1 = 773e2 = 839c1=3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349c2=5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535def rsa_gong_N_def(e1,e2,c1,c2,n):e2, c1, c2, n=int(e1),int(e2),int(c1),int(c2),int(n)s = gmpy2.gcdext(e1, e2)s1 = s[1]s2 = s[2]if s1 < 0:s1 = - s1c1 = gmpy2.invert(c1, n)elif s2 < 0:s2 = - s2c2 = gmpy2.invert(c2, n)m = (pow(c1,s1,n) * pow(c2 ,s2 ,n)) % nreturn int(m)m = rsa_gong_N_def(e1,e2,c1,c2,n)print(m)
原文始发于微信公众号（小草培养创研中心）：技术流丨RSA算法原理
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论