2er0's Studio.

RSA初探

Word count: 953Reading time: 4 min
2020/12/08 Share

RSA初探

0x01.简介:

RSA,非对称加密算法,基于大整数因式分解的难题。对一极大整数做因数分解愈困难,RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话,那么用 RSA 加密的信息的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的 RSA 钥匙才可能被强力方式破解。到目前为止,世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长,用RSA加密的信息实际上是不能被破解的。

0x02.具体实现:

假设Alice从不可靠信道接收Bob一条私人消息。她可以用以下的方式来产生一个公钥和一个私钥

1
2
3
4
5
6
1.任意两个大素数:p,q,且p != q,令n = p*q;
2.根据欧拉函数,求得r = φ(N) = φ(p)*φ(q) = (p-1)(q-1);
3.选择任意e,使得(e,r)==1,即两数互素,并有e*d == 1 mod r , 求出e关于模r的逆元d;
1 < E < φ(N)
gcd(E,φ(N)) = 1
4.(e,n)为加密公钥,(d,n)为解密私钥

此时已知公钥和私钥:
$$
加密:
c=m^e mod (n)
$$

$$
解密:
m=c^d mod (n);
$$

其中 c 为 cipheretext(密文) , m 为plaintext(明文)。

在线分解大整数N(p*q) : http://factordb.com/

0x03.小结:
求N N= p * q ;p,q为大质数
求φ(N) φ(N)= (p-1,q-1)
求E 1 < E < φ(N),gcd(E,φ(N))=1;E,φ(N)最大公约数为1(E和φ(N)互质)
求D 1 < D < φ(N),(E*D) mod φ(N) = 1
0x04.常见RSA题型

RSA题目类型

(1)已知p,q,e,求解d:

题目:

在一次RSA密钥对生成中,假设p=473398607161,q=4511491,e=17
求解出d

1
2
3
4
5
6
7
import gmpy2
p=473398607161
q=4511491
e=17
phi=(p-1)*(q-1) #求φ(N)
d=gmpy2.invert(e,phi) #求逆元d
print(d)

此处涉及python两个重要模块, gmpy2和Crypto,Ubuntu下安装教程:

gmpy2(https://blog.csdn.net/qq_28573835/article/details/86164877)

Crypto(https://blog.csdn.net/zhangpeterx/article/details/96428212)

已知p,q,e,相当于已知模φ(N)=(p-1)(q-1);,由 ed ==1 mod φ(N),即d为 e模φ(N)的逆元,gmpy2.invert()可直接求出逆元d.

(2)已知p、q、e、密文c,求明文m

SWPUCTF 一道RSA:

1
2
3
4
('c=', '0x7a7e031f14f6b6c3292d11a41161d2491ce8bcdc67ef1baa9eL')
('e=', '0x872a335')
#q + q*p^3 =1285367317452089980789441829580397855321901891350429414413655782431779727560841427444135440068248152908241981758331600586
#qp + q *p^2 = 1109691832903289208389283296592510864729403914873734836011311325874120780079555500202475594
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
from gmpy2 import *

a = 1285367317452089980789441829580397855321901891350429414413655782431779727560841427444135440068248152908241981758331600586
b = 1109691832903289208389283296592510864729403914873734836011311325874120780079555500202475594
e = 0x872a335
c = 0x7a7e031f14f6b6c3292d11a41161d2491ce8bcdc67ef1baa9e

gcd_ = gcd(a, b) # 求a,b最大公因子:q*(1+p)
p = b // gcd_
q = b // (p*(p+1))
n = p * q
phi = (p-1)*(q-1)
d = inverse(e, phi) #求解密秘钥d
#print(d)
m = pow(c, d, n) #因为pow(a,b,c)含义为a^b mod c,此处即解密公式:m = c^d mod n
print(m)
print(long_to_bytes(m)) #长整型转字节,或使用long2str(m)
#参考:https://pythonhosted.org/pycrypto/Crypto.Util.number-module.html
(3)暂定。
0x05.openssl与RSA:
(1).生成私钥:
1
2
openssl 生成并输入一个RSA私钥 输出参数 私钥名称 对应的n
openssl genrsa -out private.pem 1024
(2)提取公钥:
1
2
openssl 处理RSA密钥的格式转换等问题 提取 输出参数 公钥名称
openssl rsa -in private.pem -pubout -out public.pem
(3)使用公钥对明文加密:
1
openssl rsautl -encrypt -in message.txt -inkey public.pem -pubin -out enc.txt
(4)使用私钥对密文解密:
1
openssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt
(5)使用私钥进行签名:
1
openssl rsautl -sign -in message.txt -inkey private.pem -out enc.bin
(6)使用公钥进行验证:
1
openssl rsautl -verify -in enc.bin -inkey public.pem -pubin -out dec.txt
(7)查看证书内容:

(1)将私钥转换为文本

1
openssl rsa -in private.pem -text -out private.txt

(2)将公钥转换为文本

1
openssl rsa -in public.pem -text -pubin -out public.txt
参考文章:

https://whoamianony.top/2020/10/31/ctf/rsa-suan-fa-yuan-li/#toc-heading-15

https://www.jianshu.com/p/3e8192906ab0

CATALOG
  1. 1. RSA初探
    1. 1.1. 0x01.简介:
    2. 1.2. 0x02.具体实现:
    3. 1.3. 0x03.小结:
    4. 1.4. 0x04.常见RSA题型
      1. 1.4.1. (1)已知p,q,e,求解d:
      2. 1.4.2. (2)已知p、q、e、密文c,求明文m
      3. 1.4.3. (3)暂定。
    5. 1.5. 0x05.openssl与RSA:
      1. 1.5.1. (1).生成私钥:
      2. 1.5.2. (2)提取公钥:
      3. 1.5.3. (3)使用公钥对明文加密:
      4. 1.5.4. (4)使用私钥对密文解密:
      5. 1.5.5. (5)使用私钥进行签名:
      6. 1.5.6. (6)使用公钥进行验证:
      7. 1.5.7. (7)查看证书内容:
    6. 1.6. 参考文章: