RSA 加密原理

关注顶级算法修炼内功

顶级算法后台回复 1024 有特别礼包

责编：顶级算法 | 来源：木扬音

链接：jianshu.com/p/2e90c62fdce9

上一篇精彩：HTTP1.1之后的长连接和WebSocket的长连接之间的区别

大家好，我是顶级算法。

什么是RSA加密

RSA加密是一种非对称加密。可以在不直接传递密钥的情况下，完成解密。这能够确保信息的安全性，避免了直接传递密钥所造成的被破解的风险。是由一对密钥来进行加解密的过程，分别称为公钥和私钥。公钥加密--私钥解密，私钥加密--公钥解密

RSA数学原理

离散对数问题

在整数中，离散对数是一种基于同余运算和原根的一种对数运算。而在实数中对数的定义 log_ba是指对于给定的a和b，有一个数x，使得b^x=a。相同地在任何群G中可为所有整数k定义一个幂数为b^K，而离散对数log_ba是指使得b^K=a的整数k。

当3为17的原根时，我们会发现一个规律

欧拉函数

对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目（因此φ(1)=1）。有以下几个特点

• 当n是质数的时候，φ(n)=n-1

• 如果n可以分解为两个互质的整数之积，如n=AB，则：φ(n) = φ(AB) = φ(A)φ(B) = φ(A-1)φ(B-1)

欧拉定理

• 欧拉定理
  如果两个正整数m和n互质，那么m的φ(n)次方减去1，可以被n整除。
  m^φ(n)_modn≡1

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

根据欧拉定理进行下面公式转换

迪菲赫尔曼密钥交换

服务端根据生成一个随机数15，根据3¹⁵_mod17计算出6，服务端将6传递给客户端，客户端生成一个随机数13，根据3¹³_mod17计算出12后，将12再传回给服务端，客户端收到服务端传递的6后，根据6¹³_mod17计算出10，服务端收到客户端传递的12后，根据12¹⁵_mod17计算出10，我们会发现我们通过迪菲赫尔曼密钥交换将10进行了加密传递

RSA原理

说明：

• n会非常大，长度一般为1024个二进制位（目前人类已经分解的最大整数，232个十进制，768个二进制）

• 由于需要求出φ(n)，所以根据欧拉函数特点，最简单的方式n是由两个质数相乘 -- 得到质数：p1和p2。φ(n)=φ(p1-1)*φ(p2-1)

• 最终由φ(n)得到e和d
  总共生成了6个数字：p1、p2、n、φ(n)、e、d

安全性：
除了公钥用到n和e，其余的4个数字是不公开的（p1、p2、φ(n)、d）
目前破解RSA得到的方式如下：

• 要想求出私钥d，由于ed=φ(n)k+1，要知道e和φ(n)
  -e是知道的，但是要得到φ(n)，必须知道p1、p2

• 由于n=p1*p2，只有将n因式分解才能算出

缺点
RSA加密效率不高，因为是纯粹的数学算法，大数据不适合RSA加密，所以我们在加密大数据的时候，我们先用对称加密算法加密大数据得到KEY，然后再用RSA加密KEY，再把大数据和KEY一起进行传递

OpenSSL进行RSA加密

因为Mac系统内置了OpenSSL（开源加密库），所以我们开源直接在终端进行RSA加密解密。另外，搜索公众号程序员小乐后台回复“面试题”，获取一份惊喜礼包。

常用命令

• openssl genrsa：生成并输出一个RSA密钥

• openssl rsautl：使用RSA密钥进行加密、解密、签名和验证等运算

• openssl rsa：处理RSA密钥的格式转换等问题

生成私钥

生成RSA私钥，密钥名为private.pem,密钥长度为1024bit

openssl genrsa -out private.pem 1024

从私钥中提取公钥

openssl rsa -in private.pem -pubout -out public.pem

将private.pem私钥转化成明文形式

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

通过公钥加密数据

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

通过私钥解密数据

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

通过私钥加密数据

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

通过公钥解密数据

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

因为在iOS中是无法使用.pem文件进行加密和解密的，需要进行下面几个步骤

私钥签名（没有认证的）

.csr文件

openssl req -new -key private.pem -out rsacert.csr

crt证书

生成一个10年期限的crt证书

openssl x509 -req -day
s 3650 -in rsacert.csr -signkey private.pem -out rsacert.crt

der证书

crt证书格式转换成der证书

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

p12证书

openssl pkcs12 -export -out p.p12 -inkey private.pem -in rsacert.crt

排序序列：
1、程序员必知必会的排序一：冒泡排序2、程序员必知必会的排序二：快速排序3、程序员必知必会的排序三：直接插入排序4、程序员必知必会的排序四：希尔排序5、程序员必知必会的排序五：拓扑排序6、程序员必知必会的排序六：选择排序7、程序员必知必会的排序七：归并排序8、程序员必知必会的排序八：基数排序9、程序员必知必会的排序九：堆排序

觉得不错？欢迎转发分享给更多人

最近有一些小伙伴，让我帮忙找一些 面试题 资料，于是我翻遍了收藏的 10T 资料后，汇总整理出来，可以说是程序员面试必备！所有资料都整理到网盘了，欢迎下载！

👆扫码回复【面试题】即可获取👆

公众号后台回复 算法 或者 算法心得 有惊喜礼包！顶级算法交流群

 「顶级算法」建立了读者算法交流群，大家可以添加小编微信进行加群。欢迎有想法、乐于分享的朋友们一起交流学习。

扫描添加好友邀你进算法群，加我时注明【姓名+公司+职位】

版权申明：内容来源网络，版权归原作者所有。如有侵权烦请告知，我们会立即删除并表示歉意。谢谢。

往日分享：