1.RSA加密
I.密码学发展
A.离散对数问题
image
3为质数17的原根，若质数17很大，则想要破解会很难，只有不断的试错
B.欧拉函数
图片.png
关于互质关系
如果两个正整数，除了1以外，没有其他公因数，
我们就称这两个数是互质关系（coprime）。注意:两个相等的数之间不构成互质关系
欧拉函数特点
一、当n是质数的时候，φ(n)=n-1。
二、如果n可以分解成两个互质的整数之积，如n=AB则：
φ(AB)=φ(A)* φ(B)
根据以上两点得到：
如果N是两个质数P1 和 P2的乘积则
φ(N)=φ(P1)* φ(P2)=(P1-1)*(P2-1)
计算这个值的方式叫做欧拉函数，使用：Φ(n)表示
如:
计算8的欧拉函数，和8互质的 1、2、3、4、5、6、7、8
φ(8) = 4
计算7的欧拉函数，和7互质的 1、2、3、4、5、6、7
φ(7) = 6
计算56的欧拉函数
φ(56) = φ(8) * φ(7) = 4 * 6 = 24
C.欧拉定理
如果两个正整数m和n互质，那么m的φ(n)次方减去1，可以被n整除。
D.费马小定理
欧拉定理的特殊情况：如果两个正整数m和n互质，而且n为质数！那么φ(n)结果就是n-1。
image
E.公式转换
图片.png
第一步到第二步存在一个定理
m**φ(n)% n = 1 ==> x = 1
==> x ** k = 1 ** k
存在一个定理:x ** k = m ** (φ(n)k)%n
即m ** (φ(n)k)%n = 1
试算
M = 4
n = 15
φ(n) = 24 = 8
E = 3 和φ(n)互质
D: 3d - 1 = φ(n) * k = 8k == > 3*d = 8k + 1
D:11,19
4(311)%15
4
4(319)%15
4
image
F.公式的意义：m^e*d mod n = m
可以先进行一次运算得到m，再次计算得到m,可以既加密又解密
G.迪菲赫尔曼密钥交换
图片.png
图片.png
H.RSA的诞生
m和n互质，m是n的原根，d是e相对于φ(n)的模反元素，等式成立
图片.png
图片.png
试算
M = 3/12
N = 3*5
φ(n) = 8
e = 3
D = 11，19
image
RSA加密效率不高，纯数学算法，m<n，n为1024个二进制位，一个大的数据要分段很多次加密，大数据用对称加密算法，用RSA加密这个key，大数据用这个RSA加密后的key进行对称加密，大数据是RSA和对称加密结合使用，https就是运用此原理
I.终端演示
图片.png
image
生成私钥，在私钥中提取公钥
image
私钥转换成明文
image
文件加密,公钥加密
加密出来的enc.txt文件无法打开，是一串二进制数据,是128个字节大小
图片.png
image
文件解密,私钥解密
解密出来dec.txt是14个字节
image
也可以用私钥加密，公钥解密
加密后penc.txt是128个字节，解密后是pdec.txt是14字节
image
image
数字签名会用到RSA,iOS不能直接用.pem文件，需要先解析，iOS中用的是p12(通过公钥生成的密钥)和der证书(需要签名),从颁发机构导出,获取证书需要请求文件，去颁发机构签名，自签的没有用,别人不认,自签得到crt证书
网友评论