RSA 加密原理
责编：顶级算法 | 来源：木扬音
链接：jianshu.com/p/2e90c62fdce9
什么是RSA加密
RSA加密是一种非对称加密。可以在不直接传递密钥的情况下，完成解密。这能够确保信息的安全性，避免了直接传递密钥所造成的被破解的风险。是由一对密钥来进行加解密的过程，分别称为公钥和私钥。公钥加密--私钥解密，私钥加密--公钥解密
RSA数学原理
离散对数问题
在整数中，离散对数是一种基于同余运算和原根的一种对数运算。而在实数中对数的定义 logba是指对于给定的a和b，有一个数x，使得bx=a。相同地在任何群G中可为所有整数k定义一个幂数为bK，而离散对数logba是指使得bK=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
mn-1modn≡1
根据欧拉定理进行下面公式转换
迪菲赫尔曼密钥交换
服务端根据生成一个随机数15，根据315mod17计算出6，服务端将6传递给客户端，客户端生成一个随机数13，根据313mod17计算出12后，将12再传回给服务端，客户端收到服务端传递的6后，根据613mod17计算出10，服务端收到客户端传递的12后，根据1215mod17计算出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 资料后，汇总整理出来，可以说是程序员面试必备！所有资料都整理到网盘了，欢迎下载！
「顶级算法」建立了读者算法交流群，大家可以添加小编微信进行加群。欢迎有想法、乐于分享的朋友们一起交流学习。
扫描添加好友邀你进算法群，加我时注明【姓名+公司+职位】
版权申明：内容来源网络，版权归原作者所有。如有侵权烦请告知，我们会立即删除并表示歉意。谢谢。
往日分享：
一位大佬用了算法刷题宝典，进阿里了！
算法分析的正确姿势图解抖音推荐算法
面试时写不出排序算法？看这篇就够了
红黑树详细分析，看了都说好这些书，真tm肝……一张图理解数据结构与算法的关系
一致性哈希算法一篇搞懂TCP、HTTP、Socket、Socket连接池揭秘今日头条、抖音的推荐算法原理！