[toc] RSA加密算法属于公钥加密算法,是一种非对称密码算法 非对称加密算法:
数论基础
质数(素数)
在大于1的自然数中,除了1和它本身以外不再有其他因数的数称为质数,也叫素数。
互质数
公因数只有1的两个数,叫做互质数。维基百科上的解释是:互质,又称互素。若N个整数的最大公因子是1,则称这N个整数互质。
欧拉函数
在数论中,对于正整数N,小于或等于N([1,N]),且与N互质的正整数(包括1)的个数,记作φ(n)。 任意两个数p、q,如果p、q存在互质关系,有φ(p_q)=(p-1)_(q-1)。
欧拉定理
如果两个正整数a和n互质,则n的欧拉函数 φ(n) 可以让下面的等式成立:a^φ(n)%n=1
费马小定理
假设正整数a与质数p互质,因为质数p的φ(p)等于p-1,则欧拉定理可以写成:a^(p-1)%n=1
模反元素
两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1:a*b%n=1,这时,b就叫做a的”模反元素”。
算法实现
RSA算法基于一个事实:将两个大素数相乘十分容易,但是想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥。RSA算法三个参数:N、e1、e2 (1)选择一对不同的、足够大的素数p,q。 (2)计算n=pq。 (3)计算f(n)=(p-1)(q-1),同时对p, q严加保密,不让任何人知道。 (4)找一个与f(n)互质的数e1,且1<e1<f(n)。 (5)计算e2,使得e1*e2≡1 mod f(n)。这个公式也可以表达为e2 ≡e1-1 mod f(n),≡是数论中表示同余的符号。 (6)公钥KU=(n,e1),私钥KR=(n,e2)。 (7)加密时,先将明文变换成0至n-1的一个整数M。若明文较长,可先分割成适当的组,然后再进行交换。设密文为C,则加密过程为:C≡M^e1(mod n)。 (8)解密过程为:M≡C^e2(mod n)。 (N,e1)是公钥,(N,e2)是私钥。
签名消息
RSA也可以用来为一个消息署名。假如甲想给乙传递一个署名的消息的话,那么她可以为她的消息计算一个散列值,然后用她的密钥(private key)加密这个散列值并将这个“署名”加在消息的后面。这个消息只有用她的公钥才能被解密。乙获得这个消息后可以用甲的公钥解密这个散列值,然后将这个数据与他自己为这个消息计算的散列值相比较。假如两者相符的话,那么他就可以知道发信人持有甲的密钥,以及这个消息在传播路径上没有被篡改过。
算法公式
假设: A:明文 B:密文 — —公钥加密私钥解密公式— — A=B^e2 mod n B=A^e1 mod n — —私钥加密公钥解密公式— — A=B^e1 mod n B=A^e2 mod n
题目
1 | 公钥{920139713,19} |
已知公钥和明文,即已知A,e1,n。套公式B=A^e1 mod n即可。
1 | # coding=utf-8 |
还可以用密文和公钥将flag生成明文
1 | Flag="Wpsec{xxx}" |
深入学习
RSA中的参数
1 | p: 第一个大素数 |
RSA的密钥是公钥或私钥,密钥长度通常指模数n的位数。现用RSA的密钥长度1024位、2048位及以上 如果RSA的密钥长度过短,则可以通过分解模数n来获得p和q,获得私钥,从而获得明文。 题目中模数n=920139713,二进制=110110110110000011011111000001,密钥长度只有30位。利用现在的pc,很容易就破解出来了。 分解模数:http://factordb.com/ 手工:
1 | def moder(n): |
得到 p = 18443 q = 49891 欧拉函数 f(n) = (p-1)(q-1)= 18442 × 49890= 920071380 又已知 e1= 19,e1 x e2 ≡ 1 (mod f(n)),求e2 即 (19 x e2) mod 920071380 = 1 欧几里德算法(辗转相除法)求e2 先用小的一个数除大的一个数,得第一个余数;再用第一个余数除小的一个数,得第二个余数;又用第二个余数除第一个余数,得第三个余数;这样逐次用后一个数去除前一个余数,直到余数是0为止。
1 | e1位置 f(n)位置 |
e1=1,结束,令k=0,得e2=1。 e2=1,带入B式,得k=2。 k=2,带入A式,得e2=96849619
1 | 公钥 = {n ,e1} |