• 对称密码体制(例如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)。
欧拉函数性质：
，因为除了p的倍数外，其他数都跟n互质
，φ§称为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？
结论：如果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 binasciie = 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 = 1212112637077862917192191913841phi = (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问题，要理解费马小定理，欧拉函数，同余类
