(一) RSA原理

作者: 收纳箱 | 来源:发表于2020-03-22 23:29 被阅读0次

RSA算法原理（作者：阮一峰）
RSA签名认证
iOS开发之签名原理
我整理的网上讲解详细的文章
数字证书和数字签名
(一) RSA原理
iOS开发加解密算法-基础篇(4) RSA的加解密<
密码学第二次实验报告：RSA算法
RSA加密算法笔记
RSA原理

RSA

1. 数学原理

1.1 离散对数问题

我们要想一个加密容易，破解很难的数学运算。

方案：
$3^{?}\ \ mod\ \ 17 = 12$
$3^1\ mod\ 17 = 3$

$3^2\ mod\ 17 = 9$

$3^3\ mod\ 17 = 10$

$3^4\ mod\ 17 = 13$

$3^5\ mod\ 17 = 5$

$3^6\ mod\ 17 = 15$

$3^7\ mod\ 17 = 11$

$3^8\ mod\ 17 = 16$

$3^9\ mod\ 17 = 14$

$3^{10}\ mod\ 17 = 8$

$3^{11}\ mod\ 17 = 7$

$3^{12}\ mod\ 17 = 4$

$3^{13}\ mod\ 17 = 12$

$3^{14}\ mod\ 17 = 2$

$3^{15}\ mod\ 17 = 6$

$3^{16}\ mod\ 17 = 1$

我们知道?后计算出12很容易，但是知道12反推?只能通过枚举。若取模的数是质数n，那么可能性就有n-1种，比如17就有17-1=16种可能(可参考上面的列举)。如果n是特别大的质数，那么反推就基本不可能了。

1.2 欧拉函数

互质关系

如果两个正整数，除了1以外，没有其他公因数，我们就称这两个数是互质关系。
欧拉函数
$φ(n)=n\prod_{i=1}^{m}\left(1-\frac{1}{p_i}\right)$
其中 $p_i，1≤i≤m$ ，是 $n$ 的所有质因数。(质因数是一个能整除给定正整数的质数。)
1. 当n是质数的时候 $φ(n)=n-1$ 。
2. 如果n可以分解成两个互质的整数之积，如 $n=A*B$ 则 $φ(A*B)=φ(A)* φ(B)$ 。
3. 特殊的，若N是两个质数P1和P2的乘积，则 $φ(N)=φ(P1)* φ(P2)=(P1-1)*(P2-1)$ 。

任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？

计算8的欧拉函数，和8互质的1、3、5、7，则 $φ(8) = 4$ 。用公式计算8的质因数只有2， $ϕ(8）= 8(1 - 1/2) = 4$ 。

计算7的欧拉函数，和7互质的1、2、3、4、5、6，则 $φ(7) = 6$ 。

那56的欧拉函数是多少呢？ $φ(56)=φ(8) * φ(7) = 4 * 6 = 24$ 。

原根

设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。

即假设一个数a是m的原根，那么 $a^i\ \ mod\ \ m$ 的结果两两不同，且有 $1<a<m，0<i<m$ 。

刚刚举例的3就是17的原根。

1.3 欧拉定理

欧拉定理

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

费马小定理

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

我们下面进行一些推导：
$m^{φ(n)}\ mod\ n\ ≡\ 1$
由于 $1^{k}≡1$
$m^{k*φ(n)}\ mod\ n\ ≡\ 1$
由于 $1*m≡m$
$m^{k*φ(n)+1}\ mod\ n\ ≡\ m$

模反元素

如果两个正整数e和x互质，那么一定可以找到整数d，使得ed-1被x整除。那么d就是e对于x的“模反元素”。
$e*d\ \ mod\ \ x ≡ 1$

再转译一下：
$e*d ≡ k*x+1$
正整数e和x互质，假设 $x=φ(n)$ 于e互质，那么有:
$e*d ≡ k*φ(n)+1$

$m^{e*d}\ mod\ n\ ≡\ m$

2. 迪菲赫尔曼秘钥交换

假设客户端、服务端规定 $m=3,n=17$ ，两端的计算公式就是 $3^i\ \ mod\ \ 17 = ?$ 。
客户端生成一个 $key_c=13$ ，服务端生成一个 $key_s=15$ 。
客户端计算 $3^{13}\ mod\ 17 = 12$ 发送给服务端，服务端计算 $3^{15}\ mod\ 17 = 6$ 发送给客户端。
客户端通过收到的6计算 $6^{13}\ mod\ 17 = 10$ ，服务端通过收到的12计算 $12^{15}\ mod\ 17 = 10$ 。

两端就可以实现秘钥交换，而第三方很难破解。

2.1 原理

$m^e\ \ mode \ \ n = c$

$c^d\ \ mode \ \ n = m^{e*d}\ \ mod \ \ n$

那么发送端 $3^{15*13}\ \ mod\ \ 17 = 10 = 3^{13 * 15}\ \ mod \ \ 17$ 接收端。

2.2 RSA的诞生

刚刚的秘钥交换可以看成 $m^{e*d}\ \ mod \ \ n = x = m^{d*e}\ \ mod \ \ n$ ，两端可以得到相同的值。

那如果 $m^{d*e}\ \ mod \ \ n$ 满足我们第一节的推导 $m^{e*d}\ \ mod \ \ n ≡ m$ ，即满足d是e的模反元素时，又会发生什么呢？

也就是说：
$加密：m^e\ \ mode \ \ n = c$

$解密：c^d\ \ mode \ \ n = m$

e和n组成公钥，d和n组成私钥。

2.3 RSA算法

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

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

加密解密的时候，明文m、密文c，公钥(n, e)，私钥(n, d)，明文m长度小于n。
$加密：m^e\ \ mode \ \ n = c$

$解密：c^d\ \ mode \ \ n = m$

关于RSA的安全：

除了公钥用到了n和e其余的4个数字是不公开的。

目前破解RSA得到d的方式如下：

要想求出私钥d。由于 $e*d = φ(n)*k + 1$ ，就要知道e和φ(n);
e是知道的，但是要得到 φ(n)，必须知道p1和p2。
由于n=p1*p2。只有将n因数分解才能算出。

3. 终端演示

3.1 生成公钥、私钥

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

genrsa：生成并输入一个RSA私钥。
rsautl：使用RSA密钥进行加密、解密、签名和验证等运算。
rsa：处理RSA密钥的格式转换等问题。

~> openssl genrsa -out private.pem 1024
Generating RSA private key, 1024 bit long modulus
.........++++++
..++++++
e is 65537 (0x10001)

~> openssl rsa -in private.pem -pubout -out public.pem
writing RSA key

~> cat private.pem
-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQDPk+fVkhFq1gtl67yw/RseHvec/h2xV2XvZa7xQr8c5bHCSSjl
iWUEwZSBRYy6QZrfbcwuZgaIl7wTfYHFsagRDyC6r7rwYz2Ab8i2GPwFslCcugMz
uphvMJ8KsE16rbitzfS1N45yqwhHukOOg/NGRQulmCsTlBWdpfI0dIPooQIDAQAB
AoGAeDddhcfRhIEwGrfbENmVEe23U9mr0qAeLfZCygDw88hnGXELWVwoAAgofHGO
HfSOwCUzog9+ay8NQnBmbtsDzMpi3XGqJqkyUrSgS80QpkAJ/hM3TQJ7dtppZoYz
SKQBYGWCLIV8Ab3PSI2KLl0YFYNdUc3bgPEtfgeCt9OtEpECQQDo0Z6SPzEDl7B4
8gW7G3zPPm4pxWHNL83lxfPdty9ghZg1p5H+qJshQWI27TGEDOjhSwl6HenisXhp
BOorwEH1AkEA5D7o7oyBmiVNxOSl2V15S4iGoRgimNUEZtgVqI+0nQZE3QwqGPiS
IN4hSXLCeUUh3skznJ9wd/S/GCK0+mBkfQJAfPKiy5ImV+s8xmv9L2GdJgw3Syun
RVt2gO4v5rm9L2wDOChqbeVG/B3++8NoY5oaEW8X8vXC4+qi2JnOoxRXUQJAeB8v
wdQKpVB6pGPdcQ9Dtd/tUrz8AEkjnuicRXEUEgvplBhB05CGf2vIQvp1pRMgJzrm
wcgbjdYt+ArUCm1OlQJBAIRz+QSYWTjwebwhSQWwYPua1Kcohh2TG6LHLoGVWuIP
zfF4RZ6iAR5+fNTj9ppr/iaN6MOp5rnc1APz+6YFTz4=
-----END RSA PRIVATE KEY-----

~> cat public.pem
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDPk+fVkhFq1gtl67yw/RseHvec
/h2xV2XvZa7xQr8c5bHCSSjliWUEwZSBRYy6QZrfbcwuZgaIl7wTfYHFsagRDyC6
r7rwYz2Ab8i2GPwFslCcugMzuphvMJ8KsE16rbitzfS1N45yqwhHukOOg/NGRQul
mCsTlBWdpfI0dIPooQIDAQAB
-----END PUBLIC KEY-----

公钥和私钥本身是二进制，这里进行了base64编码方便我们查看而已。如果想查看原始信息可以输入：

~> openssl rsa -in private.pem -text -out private.txt

3.2 加密解密

加密

创建一个txt文档，比如msg.txt，数据为密码：123456。

~> openssl rsautl -encrypt -in msg.txt -inkey public.pem -pubin -out enc.txt
~> cat enc.txt
���MRnX

       �9��=�P��[�>�T�����b�2j oDڛ�6���u®�"*n3�K�
���[I��
        Y����w��c�@Ǔ�cb��.-��   ��x�Aa�C9;۩ ��ECd.!7%

解密

~> openssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt
~> cat dec.txt
密码：123456%

3.3 证书

csr证书

~> openssl req -new -key private.pem -out rsacert.csr
You are about to be asked to enter information that will be incorporated
into your certificate request.
What you are about to enter is what is called a Distinguished Name or a DN.
There are quite a few fields but you can leave some blank
For some fields there will be a default value,
If you enter '.', the field will be left blank.
-----
Country Name (2 letter code) []:CN
State or Province Name (full name) []:SICHUAN
Locality Name (eg, city) []:CHENGDU
Organization Name (eg, company) []:xxx
Organizational Unit Name (eg, section) []:xxx
Common Name (eg, fully qualified host name) []:xxx.com
Email Address []:xxx@email.com

Please enter the following 'extra' attributes
to be sent with your certificate request
A challenge password []:

这里无所谓，我们不拿去申请证书的话随便填。

签名

~> openssl x509 -req -days 3650 -in rsacert.csr -signkey private.pem -out rsacert.crt
Signature ok
subject=/C=CN/ST=SICHUAN/L=CHENGDU/O=xxx/OU=xxx/CN=xxx.com/emailAddress=xxx@email.com
Getting Private key

比如HTTPS的证书就可以用这个crt证书。

crt导出p12证书

这里密码输入的1234，后面代码演示会用到。

~> openssl pkcs12 -export -out p.p12 -inkey private.pem -in rsacert.crt
Enter Export Password:
Verifying - Enter Export Password:

crt导出drt证书

iOS不能使用crt证书，所以要进行转换。

~> openssl x509 -outform der -in rsacert.crt -out rsacert.der

4. 代码演示

- (void)viewDidLoad {
   [super viewDidLoad];
   //1.加载公钥
   [[RSACryptor sharedRSACryptor] loadPublicKey: [[NSBundle mainBundle] pathForResource:@"rsacert.der" ofType:nil]];
   //2.加载私钥
   [[RSACryptor sharedRSACryptor] loadPrivateKey:[[NSBundle mainBundle] pathForResource:@"p.p12" ofType:nil] password:@"123456"];
}

// 点击屏幕的时候进行加密解密
- (void)touchesBegan:(NSSet<UITouch *> *)touches withEvent:(UIEvent *)event
{
   //1.加密
   NSData * encryptData = [[RSACryptor sharedRSACryptor] encryptData:[@"hello" dataUsingEncoding:NSUTF8StringEncoding]];
   NSLog(@"加密的结果:\n%@", [encryptData base64EncodedStringWithOptions:0]);
   
   //2.解密
   NSData * decryptData = [[RSACryptor sharedRSACryptor] decryptData:encryptData];
   NSLog(@"解密的结果：%@", [[NSString alloc] initWithData:decryptData encoding:NSUTF8StringEncoding]);
}

//输出
2020-03-22 23:12:51.984584+0800 RSADemo[8902:255062] 加密的结果:
Wy0tkR0b/eA3ZT7IE0Y2x/+h2ugjYSN6ER1pPLj5hTbDF5jS1Vw4hqW0RENOeJyTPcRPcCIyV3ggvpmGFtAFTREbO5bOYtmNi7mK4v2Izber1kO9oxIQ4LSPVWS+I/QYB4Bi83hDHp/uQx6llcVsXNKN/fynYIxZAwcKApt7HBQ=
2020-03-22 23:12:51.986617+0800 RSADemo[8902:255062] 解密的结果：hello
 
2020-03-22 23:15:56.910986+0800 RSADemo[9007:259734] 加密的结果:
evJDs22zCqx5dq+0BfJ70Oevcw2UVSCzj/lJ5V8Rest5lvk6L55L/2Xo/hZBVONtZBKVIFW4oY8ezl1vPf0YJnjFYv/Tcyk1GNO/zWNz4HQP+NqcS/l6D+Ef+oc1k10vjQKKMSORrsO0/5j9/dMgQHa6PzzEKOGXgQLVg5j/YDY=
2020-03-22 23:15:56.913286+0800 RSADemo[9007:259734] 解密的结果：hello

两次加密结果不一样，这里特别说明一下。加密的时候有一个参数，这里使用了宏定义：

// 填充模式  kSecPaddingPKCS1 每次加密结果是随机变化的
//                  kSecPaddingNone  每次加密结果是固定的
#define kTypeOfWrapPadding  kSecPaddingPKCS1

5. 总结

RSA数学原理
- 欧拉
  - 欧拉函数、欧拉定理、模反元素
- 迪菲赫尔曼秘钥交换：用户交换秘钥。拆分了数学公式。
- RSA公式：加密和解密。
  - $m$ 小于 $n$ ， $d$ 是 $e$ 相对于 $φ(n)$ 的模反元素。
  - $n$ 和 $e$ 是公钥、 $n$ 和 $d$ 是私钥、 $m$ 明文、 $c$ 密文。
  - $n$ 长度1024以上(才够安全)。 $n$ 由 $P1$ 和 $P2$ 两个质数相乘得到。
- RSA特点
  - 相对来说比较安全(非对称机密的，私钥不用传递)。
  - 效率不高。
  - 加密数据小。

RSA算法原理（作者：阮一峰）
RSA算法原理（一） RSA算法原理（二） RSA C算法实现【看雪安全论坛】
RSA签名认证
RSA可汗学院第一章 RSA加密 RSA加密原理第一章 RSA加密原理第二章如何生成RSA公钥私钥生成类似支付...
iOS开发之签名原理
导读 iOS App 签名的原理RSA算法原理（一）RSA算法原理（二）对称加密过程如下：数据发送方选择一种...
我整理的网上讲解详细的文章
讲算法的 RSA算法原理（一) RSA算法原理（二) 网络协议 iOS网络协议----HTTP/TCP/IP浅析 ...
数字证书和数字签名
数字签名是什么?RSA算法原理（一）RSA算法原理（二）RSA数字签名与加密、解密间的关系在网络通信中，可以通过...
(一) RSA原理
RSA 1. 数学原理 1.1 离散对数问题我们要想一个加密容易，破解很难的数学运算。方案：我们知道?后计算...
iOS开发加解密算法-基础篇(4) RSA的加解密<
一、突然发现少写了一个RSA - -#...,加解密原理参照RSA算法原理，常规的加解算法一般都是对称加密: （...
密码学第二次实验报告：RSA算法
实验题目 RSA算法实验目的了解公钥算法基本原理和RSA算法的原理。了解RSA算法在数据加密和数字签名中的应用...
RSA加密算法笔记
阮一峰RSA算法原理一阮一峰RSA算法原理二历史1977年三位数学家Rivest、Shamir 和 Adlema...
RSA原理
http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part...

(一) RSA原理

RSA

1. 数学原理

1.1 离散对数问题

1.2 欧拉函数

1.3 欧拉定理

2. 迪菲赫尔曼秘钥交换

2.1 原理

2.2 RSA的诞生

2.3 RSA算法

3. 终端演示

3.1 生成公钥、私钥

3.2 加密解密

3.3 证书

4. 代码演示

5. 总结

相关文章

RSA算法原理（作者：阮一峰）

RSA签名认证

iOS开发之签名原理

我整理的网上讲解详细的文章

数字证书和数字签名

(一) RSA原理

iOS开发加解密算法-基础篇(4) RSA的加解密<

密码学第二次实验报告：RSA算法

RSA加密算法笔记

RSA原理

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读