打算学习一下RSA,说不定以后会用到

我对RSA的理解

RSA是一种非对称加密方法,加密解密时需要两个密钥–公钥和私钥,加密的时候用公钥,解密的时候用私钥

公钥就是可以公开的密钥,可以被任何人得知;私钥就是要自己保存好的密钥,一旦泄露私钥,加密后的数据安全就得不到保障

我们上网时使用的HTTPS就采用了对称加密(典型的对称加密算法有DES、3DES、AES)和非对称加密(一般是RSA)混合,举这个例子只是想说明RSA随处可见,当然其它非对称加密算法如DSA、ECC也非常经典

RSA加密

RSA在如今算力还不足以强行破解的情况下非常安全,所以借用网上两句话总结RSA(这两句话可以先不看,毕竟是总结):

RSA算法所依赖的是对极大整数做因数分解,所以对极大整数做因数分解的难度决定了RSA算法的可靠性。今天只有短的RSA钥匙才可能被强力方式破解。但目前为止,世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长,用RSA加密的信息实际上是不可能被破解的。

这种算法非常可靠,密钥越长,它就越难破解。根据已经披露的文献,目前被破解的最长RSA密钥是768个二进制位。也就是说长度超过768位的密钥,还无法破解(至少没人公开宣布)。因此可以认为,1024位的RSA密钥基本安全,2048位的密钥极其安全(网络通信中一般都是2048位的)。

用一些程序简单体验加密解密

首先是Shell-Linux环境openssl直接演示一下

openssl的genrsa用于生成密钥对( 生成并输入一个RSA私钥)

生成一个私钥

在终端输入

1
openssl genrsa -out rsa.pem -aes128 -passout pass:12345678 2048

rsa.pem意思是输出的文件名

-aes128意思是指定加密算法aes128,方法还有-aes128, -aes192, -aes256

-passout意思是指定密钥文件的加密口令

pass:12345678意思是指定密码12345678

2048意思是指定密钥长度2048

openssl-gen

1
ls

可以看到生成了一个文件(私钥文件)

打开以后可以发现里面就是公钥(这个密钥文件可以看到加密算法信息)

openssl的rsa用于处理RSA密钥的格式转换等问题

用rsa指令提取公钥
1
openssl rsa -in rsa.pem -passin pass:12345678 -pubout -out pub.pem 

rsa.pem意思是输入的文件名,因为前面有个参数-in

-passin意思是输入加密口令

pass:12345678意思是密码12345678

-pubout意思是输出公钥

-out意思是输出到文件,后面的pub.pem 是文件名

打开生成的文件看一看(这个就是公钥)

image-20210210151711996

openssl的rsaut用于处理加密和解密操作

由于公钥私钥都有了,现在到了激动人心的加密解密步骤

先创个txt文件,里面随便输入一些信息再保存

cat一下txt可以看到现在txt里面是明文

用rsautl给它加密一下
1
2
openssl rsautl -encrypt -in 1.txt -inkey rsa.pem -passin pass:12345678 -out encrypt.txt //这样写就是用私钥文件提取公钥再进行加密
openssl rsautl -encrypt -in 1.txt -inkey pub.pem -pubin -out encrypt1.txt //这样写就是直接用公钥文件加密

命令我就不解释了,和前面差不多

都执行一下,也不知道为什么输出的文件不一样

图一(文件encrypt.txt)

图二(文件encrypt1.txt)

加密操作完成,下面就是解密操作了(解密的话就必须要用私钥了)

用rsautl给它解密一下
1
2
openssl rsautl -decrypt -in encrypt.txt -inkey rsa.pem -passin pass:12345678 -out out.txt //文件encrypt.txt
openssl rsautl -decrypt -in encrypt1.txt -inkey rsa.pem -passin pass:12345678 -out out1.txt //文件encrypt1.txt,可以不管这行,毕竟是一样的

可以看到解密出来的文件都是一样的

然后是易懂的Python3程序

是Python3哦

参考了这篇博客:这里

首先先安装所需模块

1
2
pip3 install pycryptodome
pip3 install rsa

生成公钥和私钥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import rsa

bit = 2048 #2048位加密


pubkey, privkey = rsa.newkeys(bit) # 生成公钥、私钥

privkey = privkey.save_pkcs1() # 保存为 .pem 格式
with open("privkey.pem", "wb") as x: # 保存私钥
x.write(privkey)#私钥写入privkey.pem

pubkey = pubkey.save_pkcs1() # 保存为 .pem 格式
with open("pubkey.pem", "wb") as x: # 保存公钥
x.write(pubkey)#公钥写入pubkey.pem

这里的公钥和私钥可以直接拿去openssl用哦

这个例子是为了说明pem文件是通用的

例如我拿这里的私钥来提取公钥

1
openssl rsa -in privkey.pem  -pubout -out pub.pem 

得到

新建一个txt,存点信息

如下1.txt

再拿公钥加密1.txt

1
openssl rsautl -encrypt -in 1.txt -inkey pub.pem -pubin -out encrypt.txt

加密内容如下

再拿私钥解密

1
openssl rsautl -decrypt -in encrypt.txt -inkey privkey.pem -out 2.txt

解密出的2.txt内容和1.txt相同

拿公钥加密和拿私钥解密

直接上程序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import rsa


#载入要加密的文件(原文)
with open("1.txt", "rb") as x:
text_read = x.read()

#载入私钥
with open("privkey.pem", "rb") as x:
privkey = x.read()
privkey = rsa.PrivateKey.load_pkcs1(privkey)

#载入公钥
with open("pubkey.pem", "rb") as x:
pubkey = x.read()
pubkey = rsa.PublicKey.load_pkcs1(pubkey)


with open("encrypt1.txt", "wb") as x: # 保存加密后的文件(密文)
cipher_text = rsa.encrypt(text_read, pubkey) # 使用公钥加密
x.write(cipher_text)

with open("3.txt", "wb") as x: # 保存解密后的文件(原文)
with open("encrypt1.txt", "rb") as y:#读取密文
cipher_text = y.read()#读取密文字符串到cipher_text变量
text = rsa.decrypt(cipher_text, privkey) # 使用私钥解密
x.write(text)

生成密文

可以看到生成了密文如下

解出的原文与原文一致

深入分析加密解密过程

前面RSA加密解密小试已经完成,接下来要开始了解RSA的原理了

分析式子

我们直接看式子

1
2
C ≡ M^e * (mod N) //加密
M ≡ C^d * (mod N) //解密

先确定一下表层意思:

M为原文,C为加密后得到的密文

N和e为公钥,d、N为私钥

那么它们代表什么呢?

N实际上是一个大整数,d、e则是互为无反数的两个指数

加密式子

1
C ≡ M^e * (mod N)

解释:密文 = 明文的e次幂乘以N的模

解密式子

1
M ≡ C^d * (mod N)

解释:明文 = 密文的d次幂乘以N的模

这样是不是好理解一些呢?

分析原理

接下来我们来分析加密原理,这一步是为了理解它

待更新

比较简单的例题

CTFshow crypto4

题目给出了p、q和e

360截图17960322110124105

我们只需要按照公式来就好,这道题只需要下面三个公式

1
2
3
(Φ(n) * k  + 1 ) / e = d
Φ(n)= (p-1)*(q-1)
n=p*q

k是整数,只需要使用整数进行遍历求解就可以了

下面是python3的解题程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#Edit by lx
#公式参考:https://blog.csdn.net/qq_38313548/article/details/85387466
#Φ(n) * k + 1 =ed和(Φ(n) * k + 1 )/ e = d
p=447685307
q=2037
e=17
n=p*q
nn=(p-1)*(q-1)

k=1
while True:
d = ((nn * k) + 1) / e
dd = int(d)
if dd == d:
break
else:
k += 1

print("CTF.show crypto4: flag{d} is ", "flag{0}{1}{2}".format("{", int(d), "}"))

CTFshow crypto5

题目提供了p、q、e、c

360截图18720121376746

需要下面的公式,求d的公式上面已经给出,这里不再赘述

1
m = c ** d mod n

python3解题程序如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#Edit by lx
#公式参考:https://www.jianshu.com/p/de710ef3b3e6
# m = c ** d mod n
import math
p=447685307
q=2037
e=17
c=704796792
n=p*q
nn=(p-1)*(q-1)

k=1
while True:
d = ((nn * k) + 1) / e
dd = int(d)
if dd == d:
break
else:
k += 1


print("CTF.show crypto5: flag{m} is ", "flag{" + "{}".format(pow(c, int(d), n)) + "}")

文章待写,先到这里

未完。。。