密码学：RSA（一）

2021-04-14  本文已影响0人  HotPotCat

1.密码学概述

密码学是指研究信息加密，破解密码的技术科学。密码学的起源可追溯到2000年前。相传古罗马名将凯撒大帝为了防止敌方截获情报，用密码传送情报。凯撒的做法很简单，就是对二十几个罗马字母建立一张对应表。这样，如果不知道密码本，即使截获一段信息也看不懂。

密码本.png
密码本存在两个问题：
1.密码本泄漏。
2.如果截取足够多的密文可以看字母出现的频率，也可以破解。

从凯撒大帝时代到上世纪70年代这段很长的时间里，密码学的发展非常的缓慢，因为设计者基本上靠经验。没有运用数学原理。当今的密码学是以数学为基础的。

1.1发展历史

2.RSA数学原理

上世纪70年代产生的一种加密算法。其加密方式比较特殊，需要两个密钥：公开密钥简称公钥（publickey）和 私有密钥 简称私钥（privatekey）。公钥加密，私钥解密；私钥加密，公钥解密。这个加密算法就是伟大的RSA。

2.1离散对数问题

要实现加密和解密，那么就应该用一种加密容易，破解很难的数学运算。这个时候就用到了mod运算（时钟算法）。

image.png

如果用质数做模数（17），找一个比这个模数小的数3，那么有如下算法：

image.png
对应有如下结果：
image.png

3的x次方模以17结果永远在1~16之间，在这里3为17的原根。由于知道结果反推x需要一个一个实验并且不唯一，所以很难反推出原来的值。这里模数变大反推破解难度就很大。这就是离散对数问题。

2.2欧拉函数

任意给定正整数n，在<= n的正整数之中，有多少个与n构成互质关系？

关于互质关系
如果两个正整数，除了1以外，没有其他公因数，就称这两个数是互质关系（coprime）。

计算这个值的方式叫做 欧拉函数，使用：φ(n)表示

2.2.1欧拉函数特点

  1. 当n是质数的时候φ(n)=n-1。
  2. 如果n可以分解成两个互质的整数之积，如n=A*B则：
    φ(A*B)=φ(A)* φ(B)

根据以上两点得到：如果N是两个互质数P1和 P2的乘积则:
φ(N)=φ(P1)* φ(P2)=(P1-1)*(P2-1)

2.2.2欧拉定理

如果两个正整数m和n互质，那么m的φ(n)次方减去1，可以被n整除。

欧拉定理

2.2.3费马小定律

欧拉定理的特殊情况：如果两个正整数m和n互质，而且n为质数！那么φ(n)结果就是n-1。

费马小定律
验证：m = 6，n = 5 ：64%5
image.png

2.3公式转换

2.3.1 mk*φ(n) % n ≡ 1 （m和n互质）

欧拉定律mφ(n) % n ≡ 1(m和n互质)
由于1k % n ≡ 1，可以得到：

image.png
验证：
image.png

2.3.2 mk*φ(n)+1 % n ≡ 1（m和n互质 && m < n）

由于 1*m ≡ m，可以得到：

image.png

验证：


image.png

⚠️注意：换算的过程中，m 要小于 n 才会成立。大于则相当于多饶了一圈。

2.3.3模反元素

如果两个正整数e和x互质，那么一定可以找到整数d，使得 ed-1 被x整除。
那么:d就是e对于x的 模反元素
则可以得到以下公式：

image.png

假设商为k则可以得到以下公式：

image.png

2.3.4 me*d % n ≡ m

当φ(n)为x时，则：

m^e*d^ % n ≡ m

验证：M：4 ， N：15， φ(n): 8 。
通过模反元素假设 E：3， D？
3d -1 = 8k 则 d = (8k + 1)/3 k = 4 则 D = 11，k=7 则 d = 19


image.png

整个推导过程如下：


image.png

3迪菲赫尔曼密钥交换

解决密钥传递的保密性问题

image.png
1.取随机数15（保密，不告诉任何人），315%17得到的结果（6）发送给客户端。中间三方可能截获6
2.客户端取随机数13，313%17得到12发送给服务端。
3.客户端拿到服务端发送的6进行613%17得到数据10。
4.服务端拿到客户端发送的12进行1215%17也能得到10。
在这个过程中客户端和服务端得到了相同的值，这就是 迪菲赫尔曼密钥交换。客户端和服务端实际想交换的是数据10。

原理：

image.png
找到了3和17的原根，这个时候就相当于进行了拆分。

4.RSA

4.1RSA诞生

通过迪菲赫尔曼密钥交换拆分了me*d % n ≡ m。

image.png
加密：me % n = c
解密：cd % n = m
公钥：n和e
私钥：n和d
明文: m
密文: c

说明

  1. n会非常大，长度一般为1024个二进制位。（目前人类已经分解的最大整数，232个十进制位，768个二进制位）
  2. 由于需要求出φ(n)，所以根据欧函数特点，最简单的方式n由两个质数相乘得到: 质数p1、p2
    Φ(n) = (p1 -1) * (p2 - 1)
  3. 最终由φ(n)得到e 和 d。

总共生成6个数字：p1、p2、n、φ(n)、e、d

验证
M ：3 、12 ，N： 3 * 5 = 15，φ(n)：8，
假设E：3，则通过模反元素计算得到 D：11，19


image.png

关于RSA的安全

除了公钥用到了n和e 其余的4个数字是不公开的。
目前破解RSA得到d的方式如下：
1、要想求出私钥 d 。由于e*d = φ(n)*k + 1。要知道e和φ(n);
2、e是知道的，但是要得到 φ(n)，必须知道p1 和 p2。
3、由于 n=p1*p2。只有将n因数分解才能算出。
这个时候就需要穷举了，很难破解。

RSA由于m要小于n，所以每次加密数据小，需要分段加密，效率不高。一般情况下用来加密大数据对称加密的key。

4.2 RSA终端命令

由于Mac系统内置OpenSSL(开源加密库)，我们可以直接在终端上使用命令进行RSA操作。OpenSSL中RSA算法常用指令主要有三个：

生成RSA私钥,密钥长度为1024bit

openssl genrsa -out private.pem 1024
image.png
从私钥中提取公钥 
openssl rsa -in private.pem -pubout -out public.pem
image.png
将私钥转换成为明文 
openssl rsa -in private.pem -pubout -text -out private.txt

Private-Key: (1024 bit)
modulus:
    00:b8:10:27:32:89:7d:01:ab:94:b7:7d:c5:03:35:
    51:f6:22:a4:9c:a9:54:59:81:a9:7c:6b:5f:76:ed:
    86:01:b1:85:4b:b8:e1:5f:b3:38:1a:0e:4e:6d:59:
    a7:5a:1f:b8:88:d8:da:4e:e8:cc:c5:df:37:ad:2e:
    cb:18:ae:e5:7b:da:05:85:2c:5c:81:f5:8d:4d:2e:
    d1:d1:e4:76:d4:ec:e7:1a:dd:0e:a7:79:21:dc:b3:
    8c:3e:a0:81:8e:66:85:6f:9c:7c:96:f7:e6:09:37:
    45:20:b9:73:f6:7a:ee:ab:89:bf:7a:32:c7:5c:ee:
    23:71:3c:a7:44:41:4f:48:23
publicExponent: 65537 (0x10001)
privateExponent:
    70:a7:f2:55:cc:30:e6:c4:cd:d1:40:f9:44:6d:6e:
    2c:e8:27:38:7b:ab:54:dd:37:8f:1f:68:de:b1:a2:
    43:87:13:be:b4:f9:bc:49:45:1d:2d:84:73:09:5c:
    94:9c:b5:a5:8c:94:91:97:8b:3d:d0:d1:92:fe:00:
    f0:aa:9b:69:97:8a:01:88:a6:95:e9:7d:d2:9e:be:
    07:13:49:49:91:7c:ed:3c:f1:79:01:f9:b0:f9:8f:
    2d:66:13:da:1c:90:e0:3e:90:a3:22:ce:fc:13:eb:
    e3:5d:56:19:1c:23:8b:c4:c4:52:ca:33:af:9f:64:
    10:06:8b:ea:b4:07:18:81
prime1:
    00:ef:ea:34:1a:1c:0f:11:8b:95:9f:cf:bd:1c:f3:
    da:7e:bf:01:ef:12:0c:68:fd:14:1b:21:68:5c:a2:
    46:83:92:eb:5e:cb:b3:2f:03:8c:3d:7a:da:64:f1:
    96:31:10:f4:25:c7:e6:e7:52:83:ce:84:70:dc:ce:
    7e:8e:34:e8:c5
prime2:
    00:c4:67:55:71:fb:a2:11:1e:07:06:7a:3b:78:e1:
    a8:77:4e:31:ae:2c:75:90:b0:26:85:03:c2:6b:e4:
    96:eb:8e:91:36:89:90:a4:50:78:df:64:d4:35:b6:
    69:c5:57:e5:7e:35:b6:f1:25:71:5b:21:4d:81:43:
    93:5b:94:6b:c7
exponent1:
    00:a0:2f:f2:25:d4:c2:42:e6:be:3a:7c:4c:3a:be:
    9f:0e:ad:9e:2e:f0:10:15:31:95:71:1f:f7:3c:92:
    a5:1e:48:c4:9b:00:cb:5d:02:b3:6a:81:52:bc:bf:
    89:96:ad:49:36:c8:a8:65:9f:74:9e:39:53:da:3a:
    8d:c9:89:8e:39
exponent2:
    7b:e5:2b:b3:91:a7:34:e1:1a:51:6d:be:22:8d:47:
    76:ab:6f:0f:8e:a0:43:3b:bb:b0:e1:24:3e:67:9f:
    04:cd:94:b1:30:aa:7b:dc:ff:c2:fc:9a:19:a0:0e:
    ad:1c:bb:7a:98:6b:e5:47:57:70:c3:5b:5f:15:bf:
    d9:5f:91:75
coefficient:
    73:08:65:dc:ef:a1:76:46:e4:ac:a9:6b:d9:a2:2f:
    02:6e:a6:66:34:53:a3:cd:6f:ad:1c:69:ee:a9:95:
    5f:24:9d:d0:2a:9e:a7:22:37:9a:67:aa:c4:cc:5d:
    48:2a:9a:40:37:16:67:34:01:fc:c3:84:20:bc:22:
    62:db:2c:cd
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQC4ECcyiX0Bq5S3fcUDNVH2IqSc
qVRZgal8a1927YYBsYVLuOFfszgaDk5tWadaH7iI2NpO6MzF3zetLssYruV72gWF
LFyB9Y1NLtHR5HbU7Oca3Q6neSHcs4w+oIGOZoVvnHyW9+YJN0UguXP2eu6rib96
Msdc7iNxPKdEQU9IIwIDAQAB
-----END PUBLIC KEY-----

e:65337(publicExponent)

通过公钥加密数据,私钥解密数据
加密：

openssl rsautl -encrypt -in message.txt -inkey public.pem -pubin -out  enc.txt

解密：

openssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt

完整命令:

➜  rsa vi message.txt
➜  rsa cat message.txt
 密码：HoptotCat
➜  rsa openssl rsautl -encrypt -in message.txt -inkey public.pem -pubin -out  enc.txt
➜  rsa cat enc.txt
z�����0�]���Z�b��07_�&��W�[� Ƹ@���ahD*�%�,�~$]��=�g�_a����"oj� t#�ZP����L� �Hd�V�WrT��ja�1��O��H�䩃���O�v00t�d%
➜  rsa openssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt
➜  rsa cat dec.txt
 密码：HoptotCat

enc.txt文件128字节，dec.txt文件20字节。

通过公钥加密数据,私钥解密数据
这个时候就变成了签名和验证了。
签名:

openssl rsautl -sign -in message.txt -inkey private.pem -out sign.txt

验证:

openssl rsautl -verify -in sign.txt -inkey public.pem -pubin -out verify.txt

整个文件目录如下：


image.png

总结

上一篇 下一篇

猜你喜欢

热点阅读