这次来聊聊rsa的原理和规范。
原理
引理
- 本次讨论的数都是自然数
- 若两个数a，b的最大公因数为1，则称"a和b互质"
- 欧拉函数\(\varphi(a)\)：给定一个数a, [1, a]中和a互质的数的个数。比如\(\phi(10)\),和在[1,10]中和10互质的数有1, 3, 7, 9。则\(\varphi(10) = 4\)。欧拉函数有以下性质
- 若a, b互质，那么\(\varphi(ab) = \varphi(a)\varphi(b)\)。证明:互质的传递性。a, b, c, a和b互质，b和c互质，则a和c互质
- 若a为质数，则\(\phi(a) = a - 1\)
- 费马小定理,驾驶p为质数，则\(a^p\)和\(a\)对\(p\)同余。即\(a^pmodp = amodp\)
- 模的逆元， a和b对c互为逆元。其中a,b,c互质
密钥生成
- 选择两个质数a, b，计算N = ab。则\(r = \varphi(N)=(a-1)(b-1)\)
- 选则一个数e,e满足[1, r]，且e和r互质。
- 求e对r的模逆元d，即\(ed \equiv 1(mod \quad r)\)
- 销毁a, b。
这时，我们得到了非对称密钥(e, N)和(d, N)
加密解密
给定消息m，由于同余性，为了防止二义性，要求m小于N，因此常常对m进行分段。这里假设N为32bit,则N最大为\(2^{32}-1\)，m小于N
则密文\(en=m^{e} (mod \quad N)\)
根据非对称性，解密则是\(m=en^{d} (mod \quad N)\)
破解
中间人如果知道了e，N，如果要破解信息就必须知道d。那么就必须知道r
- 计算欧拉函数，\(O(\sqrt{n})\)
- 通过质因数分解, 依旧是\(O(\sqrt{n})\)
当N超过一定长度，地球上上的所有计算机将无法破解密钥
现阶段主流的rsa密钥长度为1024， 2048
主流规范
考虑到大范围的传播和使用，人们制定了一系列的标准
公钥&私钥
理论上两者的地位相等，一般通过rsa进行单向加密，即允许中间人知道其中一个钥匙，故区分了公钥和私钥(理论上从公钥方到私钥方的信息也可以不用加密，但是为了防止中间人替换需要公钥验证签名)
私钥: 需要生成公钥分发和加密解密，因此需要知道两个质数，以及N，e, d
私钥格式:
Private-Key: (1024 bit, 2 primes)
modulus:
00:b1:27:69:5f:a1:8e:d0:8c:81:c1:e0:79:da:98:
67:98:70:5c:9f:20:90:da:e2:86:b5:e8:f8:a1:8f:
90:b2:c8:2a:09:9e:10:a4:b3:92:10:fc:79:8b:5f:
f6:7a:b6:bd:19:5d:55:38:0a:79:20:74:5b:c3:cd:
59:dd:f4:db:29:07:d5:d2:38:2a:b2:73:e8:78:d9:
16:39:c6:86:91:1c:36:98:19:58:22:1a:d2:36:81:
9e:37:bd:a5:c7:e1:bd:27:68:00:09:0a:23:90:3e:
aa:aa:49:07:f7:0c:65:f9:0a:10:eb:d9:f4:52:7b:
0c:9c:78:53:ad:e4:61:01:4b
publicExponent: 65537 (0x10001)
privateExponent:
00:ae:25:38:08:b2:20:5a:12:45:5b:f8:f6:d0:54:
11:42:60:f2:2b:db:2f:8a:7c:34:40:8e:8c:1b:05:
ae:10:91:84:01:80:48:8c:1f:99:ee:e8:c1:f2:a8:
9a:fb:76:b7:dd:3f:4a:8e:94:7d:0d:d2:54:82:de:
53:01:45:ba:49:b0:96:0f:d9:af:eb:41:1b:e1:2f:
02:36:b3:e0:03:9f:b2:59:61:e1:78:c9:0a:7d:ed:
eb:c9:94:0d:a7:3b:f0:d0:a7:f3:4c:1d:bc:18:b5:
34:b3:ce:65:ed:8c:65:62:df:c9:8f:a4:23:6b:18:
11:a4:90:13:c5:f1:28:2e:81
prime1:
00:d8:11:3b:16:74:46:72:ae:a1:43:c3:81:ae:eb:
28:16:1a:75:2e:91:12:ef:5c:48:77:75:25:a0:e6:
3f:12:bc:e0:fd:04:69:51:48:e0:34:29:8b:59:a1:
a3:da:61:21:1c:ce:91:55:75:bd:3f:56:c3:d7:ee:
ad:f0:3a:c1:89
prime2:
00:d1:e5:13:cf:89:b4:d4:88:93:49:c7:2c:39:f9:
fc:56:4a:73:02:73:07:7f:a0:3e:e0:e4:16:fa:09:
86:ed:3b:8b:45:4b:f8:aa:2a:ad:0c:33:12:e8:0c:
a9:c7:cc:83:fb:73:90:da:d2:82:8f:1b:5c:f5:7e:
4f:e2:6b:1b:33
exponent1:
00:a8:dc:d6:94:16:ed:93:e5:5d:0d:8b:b7:47:90:
6b:34:d3:1a:af:f9:1b:96:4c:46:2a:6e:38:a9:46:
29:17:28:dc:a1:81:98:19:b9:dd:d7:86:7c:6c:e1:
82:20:42:f6:d0:ff:b3:df:d9:73:bd:13:bf:5d:7c:
21:1e:75:9d:19
exponent2:
13:46:e9:b9:de:d8:d7:c8:2f:56:d0:4f:14:88:0c:
0f:d4:c8:99:49:fd:3f:50:75:55:ec:3c:db:fb:f2:
03:69:bb:91:c2:b7:74:d1:74:91:31:43:a4:42:3d:
79:97:23:eb:fd:22:29:a6:b9:cc:f0:e3:69:bc:8f:
13:a9:68:97
coefficient:
0d:4a:b8:13:fd:5c:f4:f9:1b:5b:e8:03:91:33:e6:
0c:fa:c5:58:0c:be:6a:0c:59:b5:09:d9:73:2a:61:
9b:76:be:0a:3e:69:aa:bd:0e:bd:ce:00:7b:b8:21:
1c:ed:0b:2f:c4:c5:9e:e8:a7:54:d8:e7:76:68:c3:
39:47:83:4c
公钥: 只需要加密解密，所有只需要知道(e,N)或(d, N)
公钥格式:
Public-Key: (1024 bit)
Modulus:
00:b1:27:69:5f:a1:8e:d0:8c:81:c1:e0:79:da:98:
67:98:70:5c:9f:20:90:da:e2:86:b5:e8:f8:a1:8f:
90:b2:c8:2a:09:9e:10:a4:b3:92:10:fc:79:8b:5f:
f6:7a:b6:bd:19:5d:55:38:0a:79:20:74:5b:c3:cd:
59:dd:f4:db:29:07:d5:d2:38:2a:b2:73:e8:78:d9:
16:39:c6:86:91:1c:36:98:19:58:22:1a:d2:36:81:
9e:37:bd:a5:c7:e1:bd:27:68:00:09:0a:23:90:3e:
aa:aa:49:07:f7:0c:65:f9:0a:10:eb:d9:f4:52:7b:
0c:9c:78:53:ad:e4:61:01:4b
Exponent: 65537 (0x10001)
密钥格式规范
以密钥(e, N)为例子，假设为公钥，定义e为exponet, N为modulus。这里定义N的长度为512字节,则按如下格式编写:
Modulus: 297,056,429,939,040,947,991,047,334,197,581,225,628,107,021,573,849,359,042,679,698,093,131,908,015,712,695,688,944,173,317,630,555,849,768,647,118,986,535,684,992,447,654,339,728,777,985,990,170,679,511,111,819,558,063,246,667,855,023,730,127,805,401,069,042,322,764,200,545,883,378,826,983,730,553,730,138,478,384,327,116,513,143,842,816,383,440,639,376,515,039,682,874,046,227,217,032,079,079,790,098,143,158,087,443,017,552,531,393,264,852,461,292,775,129,262,080,851,633,535,934,010,704,122,673,027,067,442,627,059,982,393,297,716,922,243,940,155,855,127,430,302,323,883,824,137,412,883,916,794,359,982,603,439,112,095,116,831,297,809,626,059,569,444,750,808,699,678,211,904,501,083,183,234,323,797,142,810,155,862,553,705,570,600,021,649,944,369,726,123,996,534,870,137,000,784,980,673,984,909,570,977,377,882,585,701
Exponent: 65,527
转16进制:
Modulus: EB506399F5C612F5A67A09C1192B92FAB53DB28520D859CE0EF6B7D83D40AA1C1DCE2C0720D15A0F531595CAD81BA5D129F91CC6769719F1435872C4BCD0521150A0263B470066489B918BFCA03CE8A0E9FC2C0314C4B096EA30717C03C28CA29E678E63D78ACA1E9A63BDB1261EE7A0B041AB53746D68B57B68BEF37B71382838C95DA8557841A3CA58109F0B4F77A5E929B1A25DC2D6814C55DC0F81CD2F4E5DB95EE70C706FC02C4FCA358EA9A82D8043A47611195580F89458E3DAB5592DEFE06CDE1E516A6C61ED78C13977AE9660A9192CA75CD72967FD3AFAFA1F1A2FF6325A5064D847028F1E6B2329E8572F36E708A549DDA355FC74A32FDD8DBA65
Exponent: 010001
使用ASN.1格式对这个字符串打包,打包格式为pkcs1
SEQUENCE (2 elements)
INTEGER (2048 bit): EB506399F5C612F5A67A09C1192B92FAB53DB28520D859CE0EF6B7D83D40AA1C1DCE2C0720D15A0F531595CAD81BA5D129F91CC6769719F1435872C4BCD0521150A0263B470066489B918BFCA03CE8A0E9FC2C0314C4B096EA30717C03C28CA29E678E63D78ACA1E9A63BDB1261EE7A0B041AB53746D68B57B68BEF37B71382838C95DA8557841A3CA58109F0B4F77A5E929B1A25DC2D6814C55DC0F81CD2F4E5DB95EE70C706FC02C4FCA358EA9A82D8043A47611195580F89458E3DAB5592DEFE06CDE1E516A6C61ED78C13977AE9660A9192CA75CD72967FD3AFAFA1F1A2FF6325A5064D847028F1E6B2329E8572F36E708A549DDA355FC74A32FDD8DBA65
INTEGER (12 bit): 010001
为了减小体积，将ASN转为二进制
3082010A0282010100EB506399F5C612F5A67A09C1192B92FAB53DB28520D859CE0EF6B7D83D40AA1C1DCE2C0720D15A0F531595CAD81BA5-D129F91CC6769719F1435872C4BCD0521150A0263B470066489B918BFCA03CE8A0E9FC2C0314C4B096EA30717C03C28CA29E678E63D78ACA1E9A63BDB1261EE7A0B041AB53746D68B57B68BEF37B71382838C95DA8557841A3CA58109F0B4F77A5E929B1A25DC2D6814C55DC0F81CD2F4E5DB95EE70C706FC02C4FCA358EA9A82D8043A47611195580F89458E3DAB5592DEFE06CDE1E516A6C61ED78C13977AE9660A9192CA75CD72967FD3AFAFA1F1A2FF6325A5064D847028F1E6B2329E8572F36E708A549DDA355FC74A32FDD8DBA650203010001
最后用base64将上面的二进制串编码，并打上头部和尾部，形成PEM
----BEGIN RSA PUBLIC KEY----
EB506399F5C612F5A67A09C1192B92FAB53DB28520D859CE0EF6B7D83D40AA1C1DCE2C0720D15A0F531595CAD81BA5-D129F91CC6769719F1435872C4BCD0521150A0263B470066489B918BFCA03CE8A0E9FC2C0314C4B096EA30717C03C28CA29E678E63D78ACA1E9A63BDB1261EE7A0B041AB53746D68B57B68BEF37B71382838C95DA8557841A3CA58109F0B4F77A5E929B1A25DC2D6814C55DC0F81CD2F4E5DB95EE70C706FC02C4FCA358EA9A82D8043A47611195580F89458E3DAB5592DEFE06CDE1E516A6C61ED78C13977AE9660A9192CA75CD72967FD3AFAFA1F1A2FF6325A5064D847028F1E6B2329E8572F36E708A549DDA355FC74A32FDD8DBA65
----END RSA PUBLIC KEY----
随后又有其他非对称加密算法被发现，因此重新设计了打包格式(pkcs8):
SEQUENCE (2 elements)
SEQUENCE (2 elements)
OBJECT IDENTIFIER 1.2.840.1113549.1.1.1
NULL
BIT STRING (1 elements)
SEQUENCE(2 elements)
INTEGER (2048 bit):
EB506399F5C612F5A67A09C1192B92FAB53DB28520D859CE0EF6B7D83D40AA1C1DCE2C0720D15A0F531595CAD81BA5D129F91CC6769719F1435872C4BCD0521150A0263B470066489B918BFCA03CE8A0E9FC2C0314C4B096EA30717C03C28CA29E678E63D78ACA1E9A63BDB1261EE7A0B041AB53746D68B57B68BEF37B71382838C95DA8557841A3CA58109F0B4F77A5E929B1A25DC2D6814C55DC0F81CD2F4E5DB95EE70C706FC02C4FCA358EA9A82D8043A47611195580F89458E3DAB5592DEFE06CDE1E516A6C61ED78C13977AE9660A9192CA75CD72967FD3AFAFA1F1A2FF6325A5064D847028F1E6B2329E8572F36E708A549DDA355FC74A32FDD8DBA65
INTEGER (12 bit): 010001
序列化的方式和pkcs1一致
注: openssl 3.0不再支持pkcs1打包格式，默认为pkcs8
消息规范
rsa默认对字节流进行加密
- 字符串：只需要将字符串转成字节流，接着rsa将字节流看作无符号整数。比如ascii编码的字符串"abcd",字节流为<0x61><0x62><0x63><0x64>, 无符号整数为0x61626364,十进制为1633837924, 接下来进行取模运算
- 数字：区分小端机和大端机实现统一的字节流即可，由应用层自己实现，openssl只支持字符串
rust的openssl
rust中的openssl的加密函数，消息格式就是字节流
openssl::Rsa::rsa.public_encrypt(&data: &[u8], &mut buf: &mut [u8], Padding::NONE)
貌似这个data字节流是小端表示的16进制，即从左到右由高位到低位，和我们日常中使用的bigInt大端表示相反
参考
Are OpenSSL byte sequences in little endian or big endian order?
标签：bd,10,00,实现,rsa,规范,0c,90,互质 From： https://www.cnblogs.com/www159/p/17261737.html