RSA公钥密码体制的简介及例题

传统密码体制

传统的对称密码体制

• 对称密码体制(例如DES, AES) 允许两个用户利用提前共享的 秘密来建立“安全信道”
• 通信双方共享秘密并不容易…

密钥管理

• 考虑一个具有N个用户的团体，如果用户两两之间都需要进行 安全通信：
• 采用对称密码体制来保护用户之间的通信: • 每个用户需要与其余的N -1个用户共享私钥 • 整个系统需要管理N(N -1)/2个密钥

密钥分发

• 用户之间如何在安全通信前共享秘密? • 需要一个安全信道来共享密钥…
• 尽管密钥分发可以采用如下方式解决… • 例如, 物理接近, 可信“快递”

不支持“开放系统”

• 如果两个没有预先建立关系的用户需要建立安全通信， • 他们什么时候共享密钥呢？
• 这个场景并不遥远! • 顾客发送信用卡信息给商家 • 用户发送电子邮件给单位中的所有同事
“传统的”对称密码体制无法解决上述问题!

公钥密码体制

主要思想:

• 一些问题呈现出“非对称性”– 从一个方向计算非常容易，而从另一 个方向计算则很困难
• 例如：计算任意给定整数的乘积很容易，而计算给定大整数的因子则 非常困难
• 每个用户生成一个密钥对：一个公钥pk和一个对应的私钥 sk • 公钥将在系统内被公开 • 私钥由用户本人安全保管
• 私钥由用户本人使用，而公钥则由系统中其他用户使用 • 公钥密码体制也被称为：非对称密码体制

公钥密码体制的优势：

密钥分发：

• 公钥能够采用公开（认证的）信道进行传输；

密钥管理：

• 在用户N个用户的系统中，每个用户只需安全保管自己的私钥和N-1 个其他用户的公钥。整个系统仅仅需要维护N个公钥；

开放系统：

算法原理

(1）随机生成两个质数p和q

(2) 大整数 n=p*q

(3)欧拉函数 φ(n)=φ( p )*φ(q) = (p - 1)(q - 1)

​ 欧拉函数是求小于x并且和x互质的数的个数。其通式为：φ(x) = x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)……(1-1/pn)。

​ 欧拉函数性质：

• 若n是素数p的k次幂，，因为除了p的倍数外，其他数都跟n互质
• 欧拉函数是积性函数——若m,n互质，
• 当n为奇数时，
• p是素数，，φ§称为p的欧拉值

(4)随机选择一个整数e,满足1<e<φ(n)且gcd(e,φ(n))=1

(5)模反元素 e*d≡ 1 (mod φ(n));等价于ed - 1 = kφ(n) (k∈Z)；于是，找到模反元素d，实质上就是对下面这个二元一次方程求解。

ex + φ(n)y = 1 求解此二元一次方程使用“扩展欧几里得算法”,算法自行研究；

（6）公钥（n,e）,私钥（n,d）；

​ 总共六个数据：p,q,e,d,φ(n),n;只有公钥（n,e）对外公开，其他数据不公开；其中最关键的是d，因为n和d组成了私钥，一旦d泄漏，就等于私钥泄漏。实际上就是计算n,e,d的过程;

那么，有无可能在已知n和e的情况下，推导出d？

• ed=1 (mod φ(n))。只有知道e和φ(n)，才能算出d。
• φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
• n=pq。只有将n因数分解，才能算出p和q。

结论：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。

可是，大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。维基百科这样写道："对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。

（7）加密明文m,密文c

加解密原则：公钥加密，私钥解密。

加密算法：m^e ≡ c (mod n)

解密算法：c^d ≡ m (mod n)

• 即使是没有预先建立关系的用户也能通过对方的公钥建立 安全通信
简单来说就是：每位用户都会有自己的公钥和私钥，公钥在公开信道，私钥自己保管。Bob可以获取Alice的公钥，并用Alice的公钥加密信息后发送给Alice，Alice拥有的私钥可以解密。这样就完成了在不安全信道条件下，安全传输信息。

练习

https://ctf.show/challenges

crypto4

​ exp

import gmpy2
p = 447685307
q = 2037
e = 17
nn = (p-1)*(q-1)
d = gmpy2.invert(e,nn)
print(d)

crypto5

​ exp

import gmpy2
import binascii

e = 17
c = 704796792
p = 447685307
q = 2037
n=pq
phi = (p-1)(q-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)

print(m)

easyrsa1

​ 分解大整数n

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nWTNQN1s-1602503795097)(C:\Users\董玉\AppData\Roaming\Typora\typora-user-images\image-20201009174710573.png)]

​ exp

import gmpy2
import binascii //binascii模块包含很多在二进制和ASCII编码的二进制表示转换的方法

e = 65537
n = 1455925529734358105461406532259911790807347616464991065301847
c = 69380371057914246192606760686152233225659503366319332065009
p = 1201147059438530786835365194567
q = 1212112637077862917192191913841

phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi) //e mod phi的逆元
m = gmpy2.powmod(c,d,n) //c的d次方对n取余

print(binascii.unhexlify(hex(m)[2:]))

在线分解大整数n网站：http://www.factordb.com/index.php

安装gmpy2模块及其依赖库gmp mpfr mpc：https://blog.csdn.net/qq_28573835/article/details/86164877

解决rsa问题，要理解费马小定理，欧拉函数，同余类