RSA原理探究及命令行实践

发表于 | 分类于

RSA算法是非对称加密算法,在1977年被罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的,故取名为RSA非对称加密算法,而今在计算机数据加密领域以及电子商业中广泛使用。

RSA数学原理及推导流程

离散对数——欧拉函数——欧拉定理——模反元素——迪菲赫尔曼密钥交换——RSA诞生。

1.离散对数

离散对数其实是一种数学规律，即存在一个数m，m的k次方模以n，会存在一个规律，那就是值在1在n-1之间，此时我们就称m为n的原根。
比如：3^k mod 17 的值会在1~16这个范围，所以3是17的原根。

2.欧拉函数

求一个正整数，比它小的正整数中，有多少个与它构成互质关系，这个值就是欧拉函数。用φ()表示.
互质关系：如果两个正整数，除了1之外没有，没有其它共同的公因数。

特点：

  • 当n为质数时，φ(n) = n-1
  • 如果n可以分解为两个质数的乘积时，φ(ab) = φ(a) φ(b)
    以上可得：
1
φ(n) = φ(a)*φ(b) = (a-1)*(b-1)
3.欧拉定理

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

1
m^φ(n) mod n = 1

==>推导：

1
2
3
4
1、等式两边同时乘以K，得：
m^k*φ(n) mod n = 1
2、等式两边同时乘以m，得：
m^(k*φ(n)+1) mod n = 1

费马小定理：在欧拉函数条件下，加上m和n都是质数的条件。
即上述公式可表示为：

1
m^(n-1) mod n = 1
4.模反元素

如果两个正整数e和x互质，一定存在整数d，使得ed-1被x整除，即d就是e相对于x的模反元素。如下表示：

1
2
3
4
//e、x互质
//d是e相对于x的模反元素。
e*d mod x = 1  
==> e*d = kx+1

==>分析
模反元素的推导结果对比欧拉定理的推导结果:

1
e*d = kx+1     <==>    m^(k*φ(n)+1) mod n = m

替换k*φ(n)+1 为e*d 得：

1
2
3
//m<n
//d是e相对于φ(n)的模反元素。
m^(e*d) mod n = m
5.迪菲赫尔曼密钥交换

用于将上述公式拆分，具体过程如图所示

WX20181207-142741@2x.png

==>由上推导：m^e mod n = c –> c^d mod n = m^e*d mod n = m，得：

6.RSA加密公式

公式成立条件：
m<n
d是e相对于φ(n)的模反元素。

1
2
m^e mod n = c //公钥加密
c^d mod n = n //私钥解密

公钥：n和e （公开）
私钥：n和d
安全说明：
根据公式：e*d = kφ(n)+1，目前n和e公开，要想求出d，就得知道φ(n)，所以需要将n因式分解才行。为了避免被破解，所以n会取很大很大的整数。一般为1024个二进制位（目前已知人类破解极限是768位），所以公式成立需要六个数:

1
p1、p2、n、φ(n)、e、d

终端操作RSA加密

  • 生成私钥
1
openssl genrsa -out privite.pem 2048

查看私钥信息：cat privite.pem ，得到如下Base64编码。（因为base64是按照6个比特位来加密的，所以最后不足6个比特位的时候就用=表示）
catPrivate.png

  • 输入明文
1
openssl rsa -in privite.pem -text -out privite.txt

打开txt：open private.txt，可见下图框中标识publicExponent: 65537 (0x10001)，其中65537代表RSA加密公式中的e.
WX20181207-110007@2x.png

  • 通过私钥生成对应公钥
1
openssl rsa -in privite.pem -pubout -out public.pem
  • 通过公钥加密数据，私钥解密数据。
1
2
3
4
//公钥加密
openssl rsautl -encrypt -in message.txt -inkey public.pem -pubin -out enc.txt
//私钥解密
openssl rsautl -decrypt -in enc.txt -inkey privite.pem -out dec.txt
  • 通过私钥加密数据(签名),公钥解密。
1
2
3
4
//加密。
openssl rsautl -sign -in message.txt -inkey privite.pem -out enc.txt
//解密
openssl rsautl -verify -in enc.txt -inkey public.pem -pubin -out dec.txt
RSA特点:
  • 相对安全。由于是非对称加密，密钥不用传递。
  • 加密效率低。
  • 加密数据小。

终端生成证书

1.生产csr文件（mac公钥）
1
openssl req -new -key private.pem -out rsacert.csr
2.生成crt文件（base64）

根据上述csr文件及私钥文件而来

1
openssl x509 -req -days 3650 -in  rsacert.csr -signkey private.pem -out rsacert.crt
3.生成der文件(公钥)

根据上述crt文件而来。

1
openssl x509 -outform der -in rsacert.crt -out rsacert.der
4.生成p12文件

这里会提示输入p12证书的密码。

1
pkcs12 -export -out p.p12 -inkey privite.pem -in rsacert.crt

补充：

ios系统不直接支持rsa，但是支持x509(一种证书标准,主要定义了证书中应该包含哪些内容)的支持认证。
同样的X.509证书,可能有不同的编码格式。PEM编码和 DER编码
相关文件扩展名：CRT，CER，KEY，CSR（证书签名请求，相当于一个公钥，私钥是放在服务端的 ）

Xcode代码演示

通过上述生成的.der和.p12文件，用RSA加密及解密文件。

将der证书和p12证书导入到xcode项目中，通过rsa第三方工具类，完成加解密过程。

1
2
3
4
5
//1、加载公钥
    [[RSACryptor sharedRSACryptor] loadPublicKey:[[NSBundle mainBundle] pathForResource:@"rsacert.der" ofType:nil]] ;
    
//2、加载私钥
    [[RSACryptor sharedRSACryptor] loadPrivateKey:[[NSBundle mainBundle] pathForResource:@"p.p12" ofType:nil] password:@"123456"];
1
2
3
4
5
6
7
8
9
10
11
-(void)touchesBegan:(NSSet<UITouch *> *)touches withEvent:(UIEvent *)event
{
    //加密
    NSData * ret = [[RSACryptor sharedRSACryptor] encryptData:[@"hello" dataUsingEncoding:NSUTF8StringEncoding]];
    //编码
    NSString * base64 = [ret base64EncodedStringWithOptions:0];
    NSLog(@"%@",base64);
    //解密
    NSData * jiemi = [[RSACryptor sharedRSACryptor] decryptData:ret];
    NSLog(@"%@",[[NSString alloc] initWithData:jiemi encoding:NSUTF8StringEncoding]);
}
参考资源链接

Objective-C-RSA
那些证书相关的玩意儿(SSL,X.509,PEM,DER,CRT,CER,KEY,CSR,P12等)