2er0's Studio.

RSA初探

CTF Python Crypto 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

Author：Aron

原文链接：http://example.com/2020/12/08/RSA%E5%88%9D%E6%8E%A2/

发表日期：December 8th 2020, 7:41:10 pm

更新日期：December 10th 2020, 8:45:25 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

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. 参考文章：
Total : 7
2020
Invalid date
CTF Linux ctf web 漏洞利用 msf PHP Python Crypto RSA crypto 分组密码 misc
CTF OS 编程 ctf