3.RSA加密

一.RSA加密

     质数：一个大于1的自然数，除了1和它本身外，不能被其他自然数整除（除0以外）的数称之为质数（素数）；否则称为合数

    互质数：公约数只有1的两个数，叫做互质数。

    模运算：让m去被n整除，只取所得的余数作为结果，就叫做模运算。m mod n = x

    同余：给定一个正整数m，如果两个整数a和b满足a-b能被m整除，即(a-b)modm=0，

那么就称整数a与b对模m同余，记作a≡b(modm)，同时可成立amodm=b

    欧拉函数：在数论，对正整数n，小于n的正整数中与n互质的数的数目（φ(1)=1，φ(8)=4，1,2,3,4,5,6,7与8互质）

    通式：​=，其中p1, p2……pn为x的所有质因数，x是不为0的整数。比如12=2*2*3那么=12*（1-1/2）*(1-1/3)=4。​​​

    1.若n是质数，则  ​2.若m,n互质，​

    欧拉定理：在数论，是一个关于同余的性质。欧拉定理表明，若m,n为正整数，且m,n互质，则:​mod n = 1

    费马小定理：欧拉定理中，若n为质数,​mod n = 1

    模反元素：​mod n = m

    根据以上介绍的定义和数学知识，先来看一个真实的例子加深印象。假设甲要发送一串秘密数字m=65给乙，乙发送了一个公钥(n,e)=(3233,17)给甲，甲根据以下公式及公钥对密文m加密成c，​mod n = c，代入得，c=​mod n =​mode 3233 = 2790，甲将使用公钥加密的密文c=2790发送给乙，乙收到c=2790的密文后，使用私钥(n,d)=(3233,2753)根据以下公式进行解密，代入得，m=​mod n =​​mode 3233 = 65，乙使用与公钥不同的私钥成功计算出密文m，发现了吗？从始至终，用来解密的私钥(n,d)=(3233,2753)一直都在乙处，从未泄露乙给甲的仅仅是用来加密的公钥(n,e)=(3233,17)，这个公钥并不能用来解密，即使被他人截获，也没有任何泄密的风险。那么，乙是如何计算出给甲的公钥(n,e)=(3233,17)和私钥(n,d)=(3233,2753)的呢？

    1.随机选择两个不相等的质数p和q（乙选择了61和53）

    2.计算p和q的乘积n=p×q=61×53=3233

    3.根据本文“欧拉函数”介绍过的公式,φ(n)=(p-1)(q-1),代入计算n的欧拉函数值,φ(3233)=(61-1)×(53-1)=60×52=3120

    4.随机选择一个整数e，条件是1,乙就在1到3120之间，随机选择了17

    5.因为e与φ(n)互质，根据求模反元素的公式计算e，对于e的模反元素d有：ed≡1(modφ(n)),这个式子等价于(ed-1)/φ(n)=k（k为任意正整数）即ed-kφ(n)=1，代入数据得：17d-3120k=1,实质上就是对以上这个二元一次方程求解,得到一组解为：(d,k)=(2753,-15)

    6.将n和e封装成公钥，n和d封装成私钥,n=3233，e=17，d=2753,所以公钥就是(3233,17)，私钥就是(3233,2753)

    7.其中，n的长度就是密钥长度，3233写成二进制是110010100001，一共有12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位

二.密钥组成和加解密公式

     公钥KU：n：质数p和质数q的乘积（p和q必须保密）    e：与(p-1)×(q-1)互质

     私钥KR：n：质数p和质数q的乘积（p和q必须保密）    d：e-1(mod(p-1)(q-1))

     加密：c=m mod​ 

     解密：m= ​mod n

三.OpenSSL使用RSA

       1.生成 private.pem   |    openssl genrsa -out private.pem 1024

       2.私钥中提取公钥    |    openssl rsa -in private.pem -pubout -out public.pem writing RSA key

       3.公钥加密    | openssl rsautl -encrypt -in message.txt -inkey public.pem -pubin -out enc.txt

       4.密钥解密    |  openssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt