rsa算法2048

‘壹’ RSA算法介绍

RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。 RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。 RSA的缺点主要有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n 至少也要 600 bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(Secure Electronic Transaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。 这种算法1978年就出现了，它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字以发明者的名字命名：Ron Rivest, AdiShamir 和Leonard Adleman。 RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。 RSA的算法涉及三个参数，n、e1、e2。 其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。 e1和e2是一对相关的值，e1可以任意取，但要求e1与(p-1)*(q-1)互质；再选择e2，要求(e2*e1)mod((p-1)*(q-1))=1。 (n及e1),(n及e2)就是密钥对。 RSA加解密的算法完全相同,设A为明文，B为密文，则：A=B^e1 mod n；B=A^e2 mod n； e1和e2可以互换使用，即： A=B^e2 mod n；B=A^e1 mod n;
[编辑本段]一、RSA 的安全性
RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解 RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前， RSA 的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解多个十进制位的大素数。因此，模数n 必须选大一些，因具体适用情况而定。
[编辑本段]二、RSA的速度
由于进行的都是大数计算，使得RSA最快的情况也比DES慢上好几倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。
[编辑本段]三、RSA的选择密文攻击
RSA在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装( Blind)，让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构： ( XM )^d = X^d *M^d mod n 前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特征--每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用One-Way HashFunction 对文档作HASH处理，或
[编辑本段]四、RSA的公共模数攻击
若系统中共有一个模数，只是不同的人拥有不同的e和d，系统将是危险的。最普遍的情况是同一信息用不同的公钥加密，这些公钥共模而且互质，那末该信息无需私钥就可得到恢复。设P为信息明文，两个加密密钥为e1和e2，公共模数是n，则： C1 = P^e1 mod n C2 = P^e2 mod n 密码分析者知道n、e1、e2、C1和C2，就能得到P。 因为e1和e2互质，故用Euclidean算法能找到r和s，满足： r * e1 + s * e2 = 1 假设r为负数，需再用Euclidean算法计算C1^(-1)，则 ( C1^(-1) )^(-r) * C2^s = P mod n 另外，还有其它几种利用公共模数攻击的方法。总之，如果知道给定模数的一对e和d，一是有利于攻击者分解模数，一是有利于攻击者计算出其它成对的e’和d’，而无需分解模数。解决办法只有一个，那就是不要共享模数n。 RSA的小指数攻击。 有一种提高 RSA速度的建议是使公钥e取较小的值，这样会使加密变得易于实现，速度有 所提高。但这样作是不安全的，对付办法就是e和d都取较大的值。

可以直接hi我
给你一些例子

‘贰’ RSA 加密算法 谈到的 1024 2048bit 是什么意思

bit中文名称是位，音译“比特”，是用以描述电脑数据量的最小单位。
二进制数系统中，每个0或1就是一个位(bit)。
单位换算
1Byte=8bit
1KB=1024Byte(字节)=8*1024bit
1MB=1024KB
1GB=1024MB
1TB=1024GB
二进制数系统中，每个0或1就是一个位(bit)，位是数据存储的最小单位。其中8bit就称为一个字节（Byte）。计算机中的CPU位数指的是CPU一次能处理的最大位数。例如32位计算机的CPU一次最多能处理32位数据。

‘叁’ RSA算法的基本含义

RSA公开密钥密码体制。所谓的公开密钥密码体制就是使用不同的加密密钥与解密密钥，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。
在公开密钥密码体制中，加密密钥（即公开密钥）PK是公开信息，而解密密钥（即秘密密钥）SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然解密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK。
正是基于这种理论，1978年出现了着名的RSA算法，它通常是先生成一对RSA 密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。这就使加密的计算量很大。为减少计算量，在传送信息时，常采用传统加密方法与公开密钥加密方法相结合的方式，即信息采用改进的DES或IDEA对话密钥加密，然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后，用不同的密钥解密并可核对信息摘要。
RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现今的三十多年里，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。
SET(Secure Electronic Transaction)协议中要求CA采用2048bits长的密钥，其他实体使用1024比特的密钥。RSA密钥长度随着保密级别提高，增加很快。下表列出了对同一安全级别所对应的密钥长度。 保密级别 对称密钥长度（bit） RSA密钥长度（bit） ECC密钥长度（bit） 保密年限 80 80 1024 160 2010 112 112 2048 224 2030 128 128 3072 256 2040 192 192 7680 384 2080 256 256 15360 512 2120 这种算法1978年就出现了，它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字以发明者的名字命名：Ron Rivest, Adi Shamir 和 Leonard Adleman。早在1973年，英国国家通信总局的数学家Clifford Cocks就发现了类似的算法。但是他的发现被列为绝密，直到1998年才公诸于世。
RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。
RSA的算法涉及三个参数，n、e1、e2。
其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。
e1和e2是一对相关的值，e1可以任意取，但要求e1与(p-1)*(q-1)互质；再选择e2，要求(e2*e1)mod((p-1)*(q-1))=1。
（n，e1),(n，e2)就是密钥对。其中(n，e1)为公钥，(n，e2)为私钥。
RSA加解密的算法完全相同，设A为明文，B为密文，则：A=B^e2 mod n；B=A^e1 mod n；（公钥加密体制中，一般用公钥加密，私钥解密）
e1和e2可以互换使用，即：
A=B^e1 mod n；B=A^e2 mod n;

‘肆’ 什么是RSA算法，求简单解释。

RSA公钥加密算法是1977年由Ron Rivest、Adi Shamirh和LenAdleman在（美国麻省理工学院）开发的。RSA取名来自开发他们三者的名字。RSA是目前最有影响力的公钥加密算法，它能够
抵抗到目前为止已知的所有密码攻击，已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。由于进行的都是大数计算，使得RSA最快的情况也比DES慢上好几倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。RSA的速度比对应同样安全级别的对称密码算法要慢1000倍左右。
基础
大数分解和素性检测——将两个大素数相乘在计算上很容易实现，但将该乘积分解为两个大素数因子的计算量是相当巨大的，以至于在实际计算中是不能实现的。
1.RSA密码体制的建立：
(1)选择两个不同的大素数p和q；
(2)计算乘积n=pq和Φ(n)=(p-1)(q-1)；
(3)选择大于1小于Φ(n)的随机整数e，使得gcd(e,Φ(n))=1；
(4)计算d使得de=1mod Φ(n)；
(5)对每一个密钥k=(n,p,q,d,e)，定义加密变换为Ek(x)=xemodn，解密变换为Dk(x)=ydmodn，这里x,y∈Zn；
(6)以{e,n}为公开密钥，{p,q,d}为私有密钥。
2.RSA算法实例:
下面用两个小素数7和17来建立一个简单的RSA算法：
(1)选择两个素数p=7和q=17；
(2)计算n=pq=7 17=119，计算Φ(n)=(p-1)(q-1)=6 16=96；
(3)选择一个随机整数e=5，它小于Φ(n)＝96并且于96互素；
(4)求出d，使得de=1mod96且d<96，此处求出d=77，因为 77 5＝385＝4 96＋1；
(5)输入明文M＝19，计算19模119的5次幂，Me＝195＝66mod119,传出密文C＝66；(6)接收密文66，计算66模119的77次幂；Cd=6677≡19mod119得到明文19。

‘伍’ RSA算法详解

总括： 本文详细讲述了RSA算法详解，包括内部使用数学原理以及产生的过程。

相濡以沫。到底需要爱淡如水。

之前写过一篇文章 SSL协议之数据加密过程 ，里面详细讲述了数据加密的过程以及需要的算法。SSL协议很巧妙的利用对称加密和非对称加密两种算法来对数据进行加密。这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述。首先先来了解下这个算法的历史：

RSA是1977年由 罗纳德·李维斯特 （Ron Rivest）、 阿迪·萨莫尔 （Adi Shamir）和 伦纳德·阿德曼 （Leonard Adleman）一起提出的。当时他们三人都在 麻省理工学院 工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

但实际上，在1973年，在英国政府通讯总部工作的数学家 克利福德·柯克斯 （Clifford Cocks）在一个内部文件中提出了一个相同的算法，但他的发现被列入机密，一直到1997年才被发表。

所以谁是RSA算法的发明人呢？不好说，就好像贝尔并不是第一个发明电话的人但大家都记住的是贝尔一样，这个地方我们作为旁观者倒不用较真，重要的是这个算法的内容：

RSA算法用到的数学知识特别多，所以在中间介绍这个算法生成私钥和公钥的过程中会穿插一些数学知识。生成步骤如下：

随意选择两个大的质数p和q，p不等于q，计算N=p*q;

什么是质数?我想可能会有一部分人已经忘记了，定义如下：

比如2，3，5，7这些都是质数，9就不是了，因为3*3=9了

r = φ(N) = φ(p)φ(q) = (p-1)(q-1) 。

这里的数学概念就是什么是欧拉函数了，什么是欧拉函数呢？

欧拉函数 的定义：

互质 的定义：

例如： φ(8) = 4 ，因为 1,3,5,7 均和 8 互质。

推导欧拉函数:

（1）如果 n = 1 , φ(1) = 1 ；(小于等于1的正整数中唯一和1互质的数就是1本身)；

（2）如果 n 为质数， φ(n) = n - 1 ；因为质数和每一个比它小的数字都互质。比如5，比它小的正整数1,2,3,4都和他互质；

(3) 如果 n 是 a 的 k 次幂，则 φ(n) = φ(a^k) = a^k - a^(k-1) = (a-1)a^(k-1) ；

(4) 若 m , n 互质，则 φ(mn) = φ(m)φ(n)

证明： 设 A , B , C 是跟 m , n , mn 互质的数的集，据 中国剩余定理 (经常看数学典故的童鞋应该了解，剩余定理又叫韩信点兵，也叫孙子定理)， A * B 和 C 可建立双射一一对应)的关系。（或者也可以从初等代数角度给出 欧拉函数积性的简单证明 ） 因此的φ(n)值使用 算术基本定理 便知。（来自维基网络）

选择一个小于r并与r互质的整数e，求得e关于r的模反元素，命名为 d （ ed = 1(mod r) 模反元素存在，当且仅当e与r互质）， e 我们通常取65537。

模反元素：

比如 3 和 5 互质， 3 关于 5 的模反元素就可能是2，因为 3*2-1=5 可以被5整除。所以很明显模反元素不止一个，2加减5的整数倍都是3关于5的模反元素 {...-3, 2,7,12…} 放在公式里就是 3*2 = 1 (mod 5)

上面所提到的欧拉函数用处实际上在于欧拉定理：

欧拉定理：

欧拉定理就可以用来证明模反元素必然存在。

由模反元素的定义和欧拉定理我们知道， a 的 φ(n) 次方减去1，可以被n整除。比如，3和5互质，而 5 的欧拉函数 φ(5) 等于4，所以 3 的 4 次方 (81) 减去1，可以被 5 整除（ 80/5=16 ）。

小费马定理：

此时我们的 (N , e) 是公钥， (N, d) 为私钥，爱丽丝会把公钥 (N, e) 传给鲍勃，然后将 (N, d) 自己藏起来。一对公钥和私钥就产生了，然后具体的使用方法呢？请看： SSL协议之数据加密过程详解

我们知道像RSA这种非对称加密算法很安全，那么到底为啥子安全呢？
我们来看看上面这几个过程产生的几个数字：

N 和 e 我们都会公开使用，最为重要的就是私钥中的 d ， d 一旦泄露，加密也就失去了意义。那么得到d的过程是如何的呢？如下:

所以得出了在上篇博客说到的结论，非对称加密的原理：

将a和b相乘得出乘积c很容易，但要是想要通过乘积c推导出a和b极难。即对一个大数进行因式分解极难

目前公开破译的位数是768位，实际使用一般是1024位或是2048位，所以理论上特别的安全。

RSA算法的核心就是欧拉定理，根据它我们才能得到私钥，从而保证整个通信的安全。

‘陆’ 品味数学之美－RSA原理浅析

在探究RSA算法的原理之前，我们先来学习一点有趣的数论知识（数学分支之一，主要研究整数的性质）。你会发现一些简单的数学知识竟然背后有如此神奇的魔力。

说起质数，想必大家不陌生了，一个大于1的整数除了其本身和1之外，不存在因数则被称为质数或者是素数。比如2、3、5、7等。在小学课堂里，我们可能只是记住了这个概念，但是这里我谈下自己的一些思考帮助大家理解，质数就好比是构成数字的基本元素，想想看，氢分子仅由两个氢原子（组成一个氢分子）构成，那么一个非质数的6=3*2 即表示为6是由两个“3”元素或3个“2”元素构成。其中“3”或者“2”是不可以继续拆分的元素（3，2都是质数）。所以对一个非质数进行因式分解过程就好比对一个物体进行深入解剖，拆分至不可拆分的元素为止。这样看来，数学家们提出这些数学概念，其实也是一种对数字世界的认识和思考的概括，和我们日常生活理解周边事物方式也是相似的。

知道了质数，我们再看看互质关系，那么什么是互质呢？就是说两个数没有相同的因数称为互质关系。我们对6进行因数分解，拆分到质数的乘积即6＝3* 2而 35=5*7,这两者没有相同的因数则称6与35互质，就好像氢气分子只是由氢原子构成，而氧气分子只是由氧原子构成，这二者这间没有相同的原子就是一种互质的体现。
所以互质只是一个数和数之间有没有相同的因数关系的体现(公约数也称公因数)，和两者是不是质数是没有关系的。当然质数之间必然是互质关系，因为它们都是构成数字的不同元素。数学上来表示a,b互质一般用gcd(a,b)=1来表示。即a和b的最大公约数是1.

质数和互质的关系是不是很容易理解？但是大数学家欧拉先生可绝不仅仅停步于此，数学家嘛总爱问一下抽象概括性的问题，希望找寻规律比如

如果能找到规律，无论数字如何千变万化10位数还是100000位数，我们都能根据准则轻易计算数互质关系的数量。你发现了没有，数字也是一片世界，真是一花一世界一叶一如来啊！好了回归正传，对于这个问题欧拉先生给出了他的答案。他是这样作答的：
首先呢上述问题可以简化为一个函数来描述即： Phi(n)
这也是数学家老毛病在他们看来任何问题就是对函数的求解。既然这个函数由欧拉提出来的，那么我们就称他为 欧拉函数 .还好这个函数简单只有一个变量，即给定的正整数n。接下来就要分析这个n

n＝1的时候这个问题极其简单：
Phi(n)＝1
因为1与任何数包含他自身都构成互质关系。1本身也是质数且不作为其他数的因数，因为任何数乘以1都是其本身

大家想想看n是质数，其自身就不存在因数了，而那些与他非互质关系(存在公约数)的数进行因式分解后一定都会有一个因数与n相等。比如n＝3为一个质数，那么6＝3*2与3是非互质关系，因为存在公约数3。所以我们发现与n非互质关系的数都是n的倍数即(kn)，因为kn>=n所以与n互质的数都小于n即
Phi(n)＝n-1

还记得我们前面提到的质数吗，他可是构成数字的元素呀，所以如果n不是质数，那么他一定可以被因式分解拆分成多个质数的乘积。比如24=6*4=3*8=2*2*2*3 比如6=2*3，这些质数因数相互乘积也可以形成如下情况：

我们把相同质数因数进行相乘，很容易将一个非质数分解为两个互质关系的数的乘积，比如24=6*4=2*2*2*3＝3*8
从简单的情况来考虑，即n被拆分为两个互质关系的数的乘积：
即

n=p*q
p与q互质，那么根据剩余定理:

Phi left( pq ight) =Phi(p)*Phi(q)

至于如何证明呢？说实话我也不清楚。在我理解看来，与24互质的数都有这样一个特点：他进行因式分解后其因数不包含有3与2（因为8=2*2*2）。所以与3互质的数定义为集合A，且个数为
Phi left( 3 ight)
与8互质的数定义为集合B，且个数为
Phi left( 8 ight)
这AB两组的数字可以在组与组间两两进行组合乘积，构成与24互质的数。所以两组数字个数相乘就可以知道乘积的组合个数，也就知道与24互质的个数了。这样的证明并不严谨但姑且可以先记住。
另外还需要记住欧拉函数是一个 积性函数 ,也就是n如果为多个互质的数构成即(n=a*b*c*d.... )，那么
Phi left( n ight)=Phi left( a ight) *Phi left( b ight)....

也就是n为某一个质数的倍数，比如27=3*3*3=3^3 27就是3的倍数。那么小于27且存在非互质关系的数一定都是3的倍数也就是：1*3、2*3,3*3...9*3 共计9个， 所以3^3 - 9 ＝3^3 - 3^2 .所以归纳一下也就是说如果p是质数，求与p^n 互质的数的个数，只要将如下的数
(1*p)、(2*p)、(3*p)、....(p^n-1 *p) 进行剔除，剩余的都将与p^n （切记p是质数）互质所以我们得出：

Phi left( p^{k} ight)=p^{k}-p^{k-1}＝p^{k}(1-dfrac {1}{p} )

当k＝1的时候即
Phi left( p ight)=p-1
又回到了之前n为质数的情况下的表达式。这里我们也看到数学追求简洁和普适性的思想，再繁杂的规律都可以变成一个简洁抽象的表达式。

比如24=6*4=3*8=2*2*2*3，因为质数之间就是互质关系而且质数的多次方也是互质关系所以
我们把24演变一下：24=2^3 * 3即把相同的质数进行合并为质数的多次方。这样2^3 与3是互质关系( 质数的多次方之间也都是互质关系 )，于是当我们求与24互质的数的个数时候，就可以套用之前公式即：

Phi left(24 ight)=Phi left( 2^{3}*3 ight)=Phi left(2^3 ight)*Phi left(3 ight)=(2^{3}-2^{3-1})(3-1) =8

再进一步归纳因为p1、 p2...pm等都是质数且
n = p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}...p_{m}^{k_{m}}

则由于欧拉函数是积性函数，那么：
Phi left(n ight)=Phi left( p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}...p_{m}^{k_{m}} ight) =Phi left( p_{1}^{k_{1}} ight)* Phi left( p_{2}^{k_{2}} ight)*...Phi left( p_{m}^{k_{m}} ight)
由上一小节n为质数的多次方的结论
Phi left( p^{k} ight)=p^{k}-p^{k-1}＝p^{k}(1-dfrac {1}{p} )
可以得出：
Phi left( p_{1}^{k_{1}} ight)* Phi left( p_{2}^{k_{2}} ight)*...Phi left( p_{m}^{k_{m}} ight)=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{m}^{k_{m}}*(1-dfrac {1}{p_{1}} )*(1-dfrac {1}{p_{2}})...(1-dfrac {1}{p_{m}} )

则
Phi left(n ight)=n*(1-dfrac {1}{p_{1}} )*(1-dfrac {1}{p_{2}})...(1-dfrac {1}{p_{m}})
此时我们仍然计算24互质个数则
Phi left(24 ight)=Phi left( 2^{3}*3 ight)=Phi left(2^3 ight)*Phi left(3 ight)=24*(1-dfrac {1}{2})(1-dfrac {1}{3})＝8

上面说的那么多其实归结起来就是这样一个道理：当我们去求小于某个数范围内与其互质的数的个数时候，无非就是把n分为质数还是非质数。

知道了欧拉函数，接下来我们再理解一个同余概念，简单来说也就是25除以3的余数为1，而1除以2的余数为1，则我们称25与1对于模3同余数，用人话来说就是25和1 除以2得到的余数都一样。求余数的过程在数学里的黑话叫取模。所以才有上面那么拗口的说法。但是不要紧，数学喜欢简单不啰嗦，于是搞出了如下的表达式来表达上述说法：
25equiv 1left( mod 3 ight)
也就是说
25 \% 3 = 1\%3=1
注意到了吗？上述表达式也可以这样表述，即25除以3得到的余数为1.围绕着同余这个概念，欧拉大师结合他的欧拉函数活脱脱就搞出了个欧拉定理，我们来看看他有什么发现？

另外根据取模运算的规则：
a^{b}\%p = ((a \% p)^{b}) \% p
我们还可以得出
（a^{Phi left(n ight)})^{k}equiv 1left( mod n ight)
因为
(a^{Phi left(n ight)})^{k} \% n=（a^{Phi left(n ight)}\%n)^{k}\%n=1^k\%n =1
我们举个例子：比如
{Phi left(10 ight)}＝{Phi left(2*5 ight)}={Phi left(2 ight)}*{Phi left(5 ight)}=(2-1)*(5-1)=4

所以根据欧拉定理：因为9与10互质所以
9^{Phi left(10 ight)}=9^4equiv 1left( mod 10 ight)
于是(9^4 )^k 除以10都余1。

如果a与n互质，则必然能够找到一个数使得
abequiv 1left( mod n ight)
则b称为a的模反元素，我们可以通过欧拉定理来给予证明
a^{Phi left(n ight)}=1left( mod n ight)
a^{Phi left(n ight)}= a*a^{Phi left(n ight)-1}equiv 1left( mod n ight)

模反元素的概念对后续在已知道公钥情况下，计算合适的私钥是有很重要的意义的。
掌握了这些数学知识，你可能觉得这些东西似乎很孤立，看不到任何作用和价值，不过接下来我们来看看RSA是怎么运作的，你就会发现这些看似毫无作用的东西是如何产生价值的。

从加解密的表达式可以看出在，数学原理上公钥和私钥其实并没有什么差异。你可以用公钥加密、私钥解密，也可以用私钥加密，公钥进行解密。但是对于密码学来说，对公钥和私钥会有不同的要求。
另外需要注意的是这里 明文数值不能大于等于N ，否则解密的结果并不会等于明文。

因为加密的公式为：
x^e mod n = y
而解密公式为
y^d mod n = x
从上面表达式可以看出在数学原理上公钥和私钥其实并没有什么差异。你可以用公钥加密、私钥解密，也可以用私钥加密，公钥进行解密。
所以根据：
y=x^e - kn
且因为Y^D mod N = x 所以
y^D equiv x (mod n)
所以确定能否加解密的过程本质就是证明：
（x^e - kn)^d equiv x (mod n) （1.1）
而根据二项式定理
[图片上传失败...(image-ca75c7-1530364603810)]

（x^e - kn)^d 展开后演变为
x^ed-m_{1}x^{e(d-1)}kn+m_{2}x^{e(d-2)}(kn)^2...m_{n}(kn)^{d}
你会发现二项式展开后，唯有x^ed 没有包含n，因此结合模运算加法运算规则(a + b) % p = (a % p + b % p) % p ，要想证明1.1的表达式，则必然证明：
x^{ed} equiv x (mod n)
由于
ed equiv 1 (mod {Phi left(n ight)})
所以
ed=h{Phi left(n ight)})+1
则从证明
x^{ed} equiv x (mod n) 演变为证明
x^{h{Phi left(n ight)}}*xequiv x (mod n)
如果x与n 互质则根据欧拉定理
x^{{Phi left(n ight)}}equiv 1 (mod n)
基于在欧拉定理中提及的，根据取模运算规则可以得出
x^{h{Phi left(n ight)}}equiv 1 (mod n)
仍然是基于取模运算乘法规则，我们又可以得出
x^{h{Phi left(n ight)}}xequiv x (mod n)
这样原式得到证明。
那么如果x与n不互质的情况下，因为n=p*q且p和q都是质数，所以n的因数只有p和q了，因为x与n不互质，那么我们可以认为：
x=k_{1}p 0 < u< q
或者
x=k_{2}q 0 < k

请注意k值的取值范围，这里要牢记一点明文值必须大于0且小于n值。
这里我们先姑且定义
x=kq
0 < k< p

那么因为p与q都是质数，根据k<p 我们可以认为k与p是互质的，而p本身就是质数，所以根据费尔马小定理（n
为质数，a与n互质，如果有所遗忘可以回到前面查看相关说明。）
a^{n-1}equiv 1left( mod n ight)
那么
(kq)^{p-1}equiv 1left( mod p ight)
根据费尔马定理我们推得出来的表达式
a^{Phi left(n ight)}equiv 1left( mod n ight)
得出
((kq)^{p-1})^{h*(q-1)}equiv 1left( mod p ight)
也就是
(kq)^{h*(q-1)(p-1)}equiv 1left( mod p ight)
根据取模运算的运算定义：

得出

(kq)^{h*(q-1)(p-1)} = 1+u*p
这里的u为任意整数，这时候两边都乘以kq
(kq)^{h*(q-1)(p-1)}*kq = 1+u*k*q*p
因为n=pq x=kq那么
(x)^{Phi left(n ight)+1} = x+u*k*n
还是根据之前取模运算定义得出
(x)^{hPhi left(n ight)+1}equiv xleft( mod n ight)
即原式得到了证明。

之所以RSA是安全的，很大程度取决于n值是否足够大以至于在已知公钥e和模数n的情况下仍然难以找出d。根据之前的谈及的密钥对计算方式：
E*D equiv 1(mod M)
要想算出D就必须计算出M 而M = (p-1)(q-1) ，n=p*q则要算出M就需要知道p和q，即从一个庞大的数中分离出两个也很大的质数。大数的素因数分解被认为是一个困难的问题，即使是现代的计算机也非常难于处理，所以许多加密系统的原理都是建基于此。
目前最安全的做法是选择使用rsa-2048，随着2009年12月12日，编号为RSA-768（768 bits, 232 digits）数也被成功分解。这一事件威胁了现通行的1024-bit密钥的安全性。这里的2048表示的是模数N
的二进制位为2048位。而一般公钥世面上普遍选择65535，这是安全性和计算速度之间的综合考虑下选择出来的一个比较妥当的数值。因为加解密函数都是在做大数的指数运算，所以在工程方面会尽量考虑公钥加解密的执行速度，毕竟公钥是被外部使用的。
此外还记得前面提到rsa加密的明文数值大小不能大于N，或者其位数不能超过N的位数的限制。一旦超过密文解密后和原文数据不相匹配，这时候就需要采用分段加密技术。而另一方面明文的值也不能为0或1，-1因为这样导致密文也是0，1或者-1。另外也有一个问题即如果用私钥解密一段非法数据，那么得到是解密失败还是一个毫无意义的解密内容呢？这时候需要采用 rsa padding技术。对这个概念理解可以参考 浅谈RSA Padding 这篇文章。

通过学习一些简单的数论知识即质数、欧拉函数、模反元素等概念后，我们也了解RSA算法大致过程，总的来说公私密钥对需要计算如下几个数据：

RSA的安全性不仅仅建立于大数质因数分解困难这一理论基础上，在工程上如何对上述这些数值的选取也是很大的学问。通过对rsa学习让我对工程和理论之间的关系理解上更进一步。理论确定了方向的可行性，而工程实践则要确保在有限资源下，理论结果是可以应用起来解决特定规模的问题。而在加密算法领域，一旦工程实践出现偏差，往往就容易产生安全漏洞，尽管算法理论证明是安全的。比如rsa中p q值的选择等。这里我罗列几个工程问题有兴趣的童鞋可以再进一步做探索：

‘柒’ rsa算法原理

RSA算法是最常用的非对称加密算法，它既能用于加密，也能用于数字签名。RSA的安全基于大数分解的难度。其公钥和私钥是一对大素数（100到200位十进制数或更大）的函数。从一个公钥和密文恢复出明文的难度，等价于分解两个大素数之积。

我们可以通过一个简单的例子来理解RSA的工作原理。为了便于计算。在以下实例中只选取小数值的素数p,q,以及e，假设用户A需要将明文“key”通过RSA加密后传递给用户B，过程如下：设计公私密钥(e,n)和(d,n)。

令p=3，q=11，得出n=p×q=3×11=33；f(n)=(p-1)(q-1)=2×10=20；取e=3，（3与20互质）则e×d≡1 mod f(n)，即3×d≡1 mod 20。通过试算我们找到，当d=7时，e×d≡1 mod f(n)同余等式成立。因此，可令d=7。从而我们可以设计出一对公私密钥，加密密钥（公钥）为：KU =(e,n)=(3,33)，解密密钥（私钥）为：KR =(d,n)=(7,33)。

英文数字化。将明文信息数字化，并将每块两个数字分组。假定明文英文字母编码表为按字母顺序排列数值。则得到分组后的key的明文信息为：11，05，25。

明文加密。用户加密密钥(3,33) 将数字化明文分组信息加密成密文。由C≡Me(mod n)得：
C1(密文)≡M1（明文）^e (mod n) == 11≡11^3 mod 33 ;
C2(密文)≡M2（明文）^e (mod n) == 26≡05^3 mod 33;
C3(密文)≡M3（明文）^e (mod n) == 16≡25^3 mod 33;
所以密文为11.26.16。

密文解密。用户B收到密文，若将其解密，只需要计算，即：
M1(明文)≡C1（密文）^d (mod n) == 11≡11^7 mod 33;
M2(明文)≡C2（密文）^d (mod n) == 05≡26^7 mod 33;
M3(明文)≡C3（密文）^d (mod n) == 25≡16^7 mod 33;
转成明文11.05.25。根据上面的编码表将其转换为英文，我们又得到了恢复后的原文“key”。

当然，实际运用要比这复杂得多，由于RSA算法的公钥私钥的长度（模长度）要到1024位甚至2048位才能保证安全，因此，p、q、e的选取、公钥私钥的生成，加密解密模指数运算都有一定的计算程序，需要仰仗计算机高速完成。