第一步，随机选择两个不相等的质数p和q。
爱丽丝选择了61和53。（实际应用中，这两个质数越大，就越难破解。）
第二步，计算p和q的乘积n。
爱丽丝就把61和53相乘。
n=61×53=3233
n的长度就是密钥长度。3233写成二进制是110010100001，一共有12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。
第三步，计算n的欧拉函数φ(n)。
根据公式：
φ(n)=(p-1)(q-1)
爱丽丝算出φ(3233)等于60×52，即3120。
第四步，随机选择一个整数e，条件是1
爱丽丝就在1到3120之间，随机选择了17。（实际应用中，常常选择65537。）
第五步，计算e对于φ(n)的模反元素d。
ed≡1(modφ(n))
这个式子等价于
ed-1=kφ(n)
于是，找到模反元素d，实质上就是对下面这个二元一次方程求解。
ex+φ(n)y=1
已知e=17,φ(n)=3120，
17x+3120y=1
至此所有计算完成。
第六步，将n和e封装成公钥，n和d封装成私钥。
在爱丽丝的例子中，n=3233，e=17，d=2753，所以公钥就是(3233,17)，私钥就是（3233,2753）。
七、RSA算法的可靠性
回顾上面的密钥生成步骤，一共出现六个数字：
pqnφ(n)ed
这六个数字之中，公钥用到了两个（n和e），其余四个数字都是不公开的。其中最关键的是d，因为n和d组成了私钥，一旦d泄漏，就等于私钥泄漏。
那么，有无可能在已知n和e的情况下，推导出d？
（1）ed≡1(modφ(n))。只有知道e和φ(n)，才能算出d。
（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
（3）n=pq。只有将n因数分解，才能算出p和q。
结论：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。
可是，大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。维基百科这样写道：
"对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。
假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。
只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。"
举例来说，你可以对3233进行因数分解（61×53），但是你没法对下面这个整数进行因数分解。
1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413
它等于这样两个质数的乘积：
33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489×36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917
事实上，这大概是人类已经分解的最大整数（232个十进制位，768个二进制位）。比它更大的因数分解，还没有被报道过，因此目前被破解的最长RSA密钥就是768位。
八、加密和解密
有了公钥和密钥，就能进行加密和解密了。
（1）加密要用公钥(n,e)
假设鲍勃要向爱丽丝发送加密信息m，他就要用爱丽丝的公钥(n,e)对m进行加密。这里需要注意，m必须是整数（字符串可以取ascii值或unicode值），且m必须小于n。
所谓"加密"，就是算出下式的c：
me≡c(modn)
爱丽丝的公钥是(3233,17)，鲍勃的m假设是65，那么可以算出下面的等式：
6517≡2790(mod3233)
于是，c等于2790，鲍勃就把2790发给了爱丽丝。
（2）解密要用私钥(n,d)
爱丽丝拿到鲍勃发来的2790以后，就用自己的私钥(3233,2753)进行解密。可以证明，下面的等式一定成立：
cd≡m(modn)
也就是说，c的d次方除以n的余数为m。现在，c等于2790，私钥是(3233,2753)，那么，爱丽丝算出
27902753≡65(mod3233)
因此，爱丽丝知道了鲍勃加密前的原文就是65。
至此，"加密--解密"的整个过程全部完成。
我们可以看到，如果不知道d，就没有办法从c求出m。而前面已经说过，要知道d就必须分解n，这是极难做到的，所以RSA算法保证了通信安全。
九、私钥解密的证明
最后，我们来证明，为什么用私钥解密，一定可以正确地得到m。也就是证明下面这个式子：
因为，根据加密规则
ｍe≡c(modn)
于是，c可以写成下面的形式：
c=me-kn
将c代入要我们要证明的那个解密规则：
(me-kn)d≡m(modn)
它等同于求证
med≡m(modn)
由于
所以
ed=hφ(n)+1
将ed代入：
mhφ(n)+1≡m(modn)
接下来，分成两种情况证明上面这个式子。
（1）m与n互质。
根据欧拉定理，此时
mφ(n)≡1(modn)
得到
(mφ(n))h×m≡m(modn)
原式得到证明。
（2）m与n不是互质关系。
此时，由于n等于质数p和q的乘积，所以m必然等于kp或kq。
以m=kp为例，考虑到这时k与q必然互质，则根据欧拉定理，下面的式子成立：
(kp)q-1≡1(modq)
进一步得到
[(kp)q-1]h(p-1)×kp≡kp(modq)
即
(kp)ed≡kp(modq)
将它改写成下面的等式
(kp)ed=tq+kp
这时t必然能被p整除，即t=t'p
(kp)ed=t'pq+kp
因为m=kp，n=pq，所以
（完）
杨琪说：
数学乃万物之源呐
会林说：
我叫小井说：
终于体会到什么叫“深入浅出”
Black说：
受益匪浅，谢谢！
joymufeng说：
Du说：
如果量子计算机实现的话是不是就能破解了
Ray说：
引用Du的发言：如果量子计算机实现的话是不是就能破解了
RSA的困难性是基于大整数因子分解在计算上不可行，如果计算能力上去的话，当然是可以破解现有的密码。
RayJoy说：
引用杨琪的发言：数学乃万物之源呐
数学自有其独特的魅力。
t.k.说：
九的子标题（2）m与n不是互质关系中
应该是“m与q必然互质”。
另外，数学公式用mathjax会更好看一些。
asdf说：
[(kp)q-1]h(p-1)×kp≡kp(modq)可以直接一步得到结论了，何必之后那几步推导？
iljyya说：
没看懂好伤心。
zhangyuqin说：
不太明白，继续琢磨一下！
zz说：
第四步计算模反元素下面这俩式子貌似符号弄错了～
ex+φ(n)y=1已知e=17,φ(n)=3120，17x+3120y=1
软件局局长说：
当年数学没学好，看得快哭了。
邹邹说：
felix021说：
别说DES……这个加密算法因为太容易被破解早就被废除了，建议改成3DES或AES.
waveacme说：
wusuopubupt说：
精彩！！！
STL说：
nkAmerica说：
引用asdf的发言：[(kp)q-1]h(p-1)×kp≡kp(modq)可以直接一步得到结论了，何必之后那几步推导？
为了让mod作用于n，而不是q。
根本没有协商过程啊。都是用对方的公钥加密
Lynx说：
李华说：
想到这个算发的人太伟大了，这是一个回答纯数学有什么用的最好案例。还有没有其他的像RSA这样简单有效的非对称加密方法呢？恐怕像找外星人一样难了。
frank说：
引用felix021的发言：别说DES……这个加密算法因为太容易被破解早就被废除了，建议改成3DES或AES.
DES废除的原因一个是密钥位数太少，在现在的计算能力下，已经无法保证安全，第二个原因是，DES是为硬件加密设计的，对于现在软件来说计算效率不够好，第三个原因是，一直有人怀疑DES的S盒中隐藏着后门，而这个后门被美国安全局掌握。所以提出了AES
3DES理论密钥长度为56*3=168bits，但是，在受到中间人攻击的条件下，退化为112bits。其安全性仍然不够好
Martin.Hsuching说：
写的很不错，浅显易懂，但看完，觉得最后一段有个疑惑，请教一下：(kp)ed=tq+kp这时t必然能被p整除，即t=t'p，这个必然性是如何证明的？请指导下~~谢谢
LCS说：
为什么公匙不能猜测的进行解密呢。。。
锦衣卫加密顾问说：
正在做加密产品，以应对来自霉国的窃听威胁，感谢楼主的理论分析。
Chil说：
加密就是算出me≡c(modn)中的c
哇哈哈说：
此时，由于n等于质数p和q的乘积，所以m必然等于kp或kq
這個怎麼得來的m不是明文嗎,明文爲什麽一定等於kp或者kq
guanwh说：
想双向通信的话肯定要定义两套公钥和秘钥了，都用对方的公钥加密发送，然后接收方用自己的秘钥解密就OK了！
明天有风吹说：
终于明白rsa是怎么一回事了，thanks！！
L说：
引用Ray的发言：RSA的困难性是基于大整数因子分解在计算上不可行，如果计算能力上去的话，当然是可以破解现有的密码。
量子计算机是并行的，1024位的密码用1024个量子处理单元做计算，只要1秒。只是现在技术最多能做到8位量子处理单元的级别。so...
Leon说：
引用Martin.Hsuching的发言：写的很不错，浅显易懂，但看完，觉得最后一段有个疑惑，请教一下：(kp)ed=tq+kp这时t必然能被p整除，即t=t'p，这个必然性是如何证明的？请指导下~~谢谢
两边同时整除p，又p、q互质，于是t必定是p的整数倍。
引用哇哈哈的发言：此时，由于n等于质数p和q的乘积，所以m必然等于kp或kq
数学角度：m、n不是互质关系，说明m、n必定含有非1公因子，而n等于质数p和q的乘积，因此m必然等于kp或kq。
Gavin说：
一直在使用RSA，但是不是很清楚RSA的数学原理，今天一看，胜读几年书！！！
1、to哇哈哈：此时，由于n等于质数p和q的乘积，所以m必然等于kp或kq因为m与n不是互质关系，说明m与n有共同的公因子g，假设m=hg，由于n=pq，p与q互质，n只有p和q两个因子，所以g和h必然有一个等于q或者p，所以才有结论“m必然等于kp或kq”
2、toMartin.Hsuching：因为(kp)ed=tq+kp,=>(p)ed*(k)ed=tq+kp,=>(p)ed*(k)ed-kp=tq,=>p[(p)(ed-1)*(k)ed-k]=tq,左边是p的倍数，那右边必然也是p的倍数。因为p与q互质，所以t必然是p倍数，即t=t'p
3、
赵三说：
引用Gavin的发言：一直在使用RSA，但是不是很清楚RSA的数学原理，今天一看，胜读几年书！！！
帮我理解了不少，感谢！还有一点向您请教下：
1.“（1）m与n互质。
根据欧拉定理，此时mφ(n)≡1(modn)
得到(mφ(n))h×m≡m(modn)”这个是怎么得到啊？(mφ(n))h≡1(modn)这样写，对吗？接着，后面又多乘以个m,就能变成这样啦(mφ(n))h×m≡m(modn)，这个是为什么呢？
2.这个跟1.应该是同样的问题“(kp)q-1≡1(modq)
进一步得到[(kp)q-1]h(p-1)×kp≡kp(modq)”这个也是，左右都乘以kp，这是为什么呢？
3.这个是我看RSA算法原理（一）中的疑问：“因此，7的任意次方的个位数（例如7的222次方），心算就可以算出来”这是怎么得到的呢？我只想到了：7的222次方=7的2次方*7的（4*55）次方，下面就不知道了。还望解惑，不胜感激~
dongxf说：
如果量子计算机可以破解1024bit的RSA,那么可以用量子计算机做更长bit位的加密,比如2048bit...,直到无法破解
none说：
to:赵三
1，(mφ(n))h≡1(modn)这样写是对的，这个可以通过≡的含义，然后通过一个推导（也就是从h-1到h的推导）可以看出是正确的。比如设(mφ(n))h=r1*n+1,然后(mφ(n))h*m=(r1*n+1)*m,这个和n的余数就是m。
2，RSA算法原理（1）中回复里面有这个问题。7的（4*55）的余数就是1，然后7的2次方的余数为9，那结果就是9
colde说：
证明(m^e-kn)^d≡m(modn)等同于证明m^ed≡m(modn)
卡住在这里了,麻烦帮忙解释一下。
八戒说：
相当详实生动，非常感谢，，，，就是举例子的数字有点大了，，普通计算机直接正无穷大了，，，
ssapym说：
问个问题，1，这个巨大的质数或那两个相乘质数从哪来的，2048位的从哪来的。RSA算法的可靠性依赖于大整数的因数分解，是一件非常困难的事情，那大整数现在最大到多少了，2048位以上的现在有么，好像还有什么美国输出限制。2，如果分解困难，用现在产生大质数的算法，是否可以反推出来大质数，产生一个对应列表，就像md5的彩虹表，是否就可以破解。
谢谢
王为雄说：
你好，我觉得第五步骤里面：所谓"模反元素"就是指有一个整数d，可以使得ed被φ(n)除的余数为1。
这句话后半句，应该是使得φ(n)被ed除的余数为1。
这是来自wiki的除法举例:15可以被5整除，记作5|15。
luke说：
其它都很清晰，第5步跳的太快了：ed≡1(modφ(n))怎么就得到ed-1=kφ(n)K从哪里来？是不是从第一篇中这里来（b+kn都是a的模反元素）？再变成ex+φ(n)y=1，这时候K是不是就是Y了？X就是D了？
引用luke的发言：其它都很清晰，第5步跳的太快了：ed≡1(modφ(n))怎么就得到ed-1=kφ(n)K从哪里来？是不是从第一篇中这里来（b+kn都是a的模反元素）？再变成ex+φ(n)y=1，这时候K是不是就是Y了？X就是D了？
问了一下同事，明白了！！！ed≡1(modφ(n))意味着，ed除以φ(n)余1，于是，ed-1就能被φ(n)整除。能被整除就意味着ed-1=kφ(n)，k是任意一个整数。
引用colde的发言：证明(m^e-kn)^d≡m(modn)等同于证明m^ed≡m(modn)
唉，我也卡在这里了。求高人继续。
引用luke的发言：
而(m^e-kn)^d≡m(modn)
意味着，(m^e-kn)^d-m=kn
所以，m^(ed)-kn-m=kn
得到，m^(ed)-m=2kn=>m^(ed)-m=kn（这里k只是代表一个整数倍的关系，值并不重要）
而m^(ed)-m=kn正意味着m^(ed)≡m(modn)
mine260309说：
引用ssapym的发言：问个问题，1，这个巨大的质数或那两个相乘质数从哪来的，2048位的从哪来的。RSA算法的可靠性依赖于大整数的因数分解，是一件非常困难的事情，那大整数现在最大到多少了，2048位以上的现在有么，好像还有什么美国输出限制。2，如果分解困难，用现在产生大质数的算法，是否可以反推出来大质数，产生一个对应列表，就像md5的彩虹表，是否就可以破解。
2^1024大约是10^308这个数量级，包含的素数可以由素数定理知道大约是x/ln(x)这个数量级，可选的素数p和q太多了，p*q的组合就更多了，怎么做彩虹表？彩虹表是基于有一些常用的密码（比如password,123456）算出来的，你随机选一个密码，多半不会出现在彩虹表中。同理，你随机选两个p,q，怎么查彩虹表？
鹿说：
找到高人了，写得清楚，有例子，每步都写出原理。
gk说：
谢谢阮老师深入浅出的讲解，我知道了RSA算法是怎么回事儿了。我感觉那些严谨的证明过程不必细致追究，主要是搞清楚RSA算法是什么，除非那些数学专业的。
介木说：
我无法读懂上面的数学公式.请问,高中水平的我,需要学习那些书本,才能看懂上面的公式呢谢谢各位.
我懂质数
David说：
引用介木的发言：我无法读懂上面的数学公式.请问,高中水平的我,需要学习那些书本,才能看懂上面的公式呢谢谢各位.
高中确实不涉及这方面的知识。找点关于余数的数论书看，知道基本的同余定理就行了。
llxxtnt说：
我有个问题
根据c^d≡m(modn)
加密者不知道私钥d，但是他知道明文m，密文c，以及n，是否可以推算出私钥d
还有一个问题，我是做金融的，在金融领域经常用到转加密这个概念1.老张先用公钥e1对明文m加密得到密文c1，然后将密文c1传递给老王2.老王收到密文c1后，用公钥e2替换公钥e1，得到密文c2
我想知道公钥e2替换公钥e1的具体过程是先用私钥d1解密密文c1，还原出明文m以后，再用公钥e2对明文m加密得到密文c2还是在一个原子过程中，直接就可以用私钥d1，公钥e2，密文c1计算出新密文c2，在计算过程中可以避免出现明文m？
袁定平说：
希望能够解答，谢谢
tommyqian_2008说：
第四步，随机选择一个整数e，条件是1e不一定要小于φ(n)吧，根据欧拉定律，e只要跟φ(n)互质就可以了
求大神解惑
hai说：
啊啊说：
每个个体都有自己的公钥和私钥，在通信中，故爱丽丝也有自己的公钥和私钥。
jimohou说：
(kp)^ed=tq+kp=>tq=(kp)(kp^ed-1-1)因为p,q是互质,所以kp必然不能整除q,那么就必然整除t,t=t'p
引用mine260309的发言：
我的看法：p*q的积的二进制的位数如果固定并确定为1024，则p和q的取值只能在一定范围内取，这在RSA密钥生成软件中自然会有指定。如果所有的密钥生成机制都按同一规定，那么由于素数资源不是随机无限的（有素数生成机制的限制，有随意取两个素数的乘积的二进制位数的限制），设素数资源的个数为n，在有限的素数资源中取出两个数的可能组合将是C|（2，n）。将每个组合的乘积一一列出，就可以组成彩虹表，可以从乘积列表中查找出对应的素数组合，进而推出公钥和私钥。素数资源不够的软件产生的密钥，尤其具有这样的隐患，看似很安全，实际上人家大的机构很容易破解出私钥来。所以，生产大素数的机构就像开矿公司，也像数字银行，拥有的素数资源越多越安全。不知是否可以这样理解？
不同机构产生的证书（包括私钥、公钥）的质量（指安全保证）是良莠不齐的。
我想ssapym彩虹表的本意即在如此。
alphaqcode说：
(m^e-kn)^d≡m(modn)分解下左边公式(m^e-kn)^d=m^ed+[(m^e)^d-1]*kn+[(m^e)^d-2]*kn^2+....除了第一个m^ed,后面的数都含有XXX*kn,所以都能被n整除
xidactw说：
受益匪浅
lbs说：
大哥，那个模反元素有问题一说：a*a的[φ(n)-1]%n=1二说：a*a的[φ(n)-1]%φ(n)=1明显不一样了丫、。。。。
shindo说：
这步mφ(n)≡1(modn)到(mφ(n))h×m≡m(modn)实在看不懂，能否详细解释下？
引用shindo的发言：这步mφ(n)≡1(modn)到(mφ(n))h×m≡m(modn)实在看不懂，能否详细解释下？
我懂了，mφ(n)≡1(modn)=>mφ(n)=Kn+1,k为自然数(kn+1)^h展开多项式，除了1以外，全部含有kn，所以其他项都能被n整除而余1..也就是能推出(mφ(n))h≡1(modn)然后m这个中间数学gap还是挺大的...
nan说：
调理清晰，把一个复杂难懂的数学问题，一步一步分解，深入浅出，容易理解，学习了！
Jayce说：
ax_pokl说：
RSA加密解密算法中，已知公钥和密匙n,e,d，是否能将合数n=p*q分解？
先温故一下RSA算法：1、两个大质数p,q。2、模数n=p*q。3、欧拉函数f=(p-1)(q-1)。4、随机数e，15、模逆d，即最小整数d，e*d=1modf。也就是说：知道了p,q也就知道了n,f；知道了f,e也就知道了d。
下面温故一下加密解密算法：已知明文m，满足m加密：密文c=m^emodn。解密：明文x=c^dmodn。
证明一下解密得到的明文x=m：由c=m^emodn，得c=m^e+k*n。代入x=c^dmodn，得x=(m^e+k*n)^dmodn。于是x=m^e^dmodn，即x=m^(e*d)modn。由于e^d=1modf，得e*d=k*f+1。代入得x=m^(kf+1)modn，x=m*m^(kf)modn。当m与n互质时，x=m*(m^f)^kmodn,由欧拉定理可知x=mmodn。又m当m与n不互质时，由于n=p*q且m若m=kp，则m^(q-1)=(k*p)^(q-1)=1modq。接着[(k*p)^(q-1)]^[k*(p-1)]*kp=kpmodq，即(k*p)^(e*d)=k*pmodq。又由于(k*p)^(ed)=k*q+k*p，(k*p)^(ed)=k*q*p+k*p，。所以m^(ed)=mmodn，x=m。即证。
如果大家有办法分解n的话，求详细的算法。
陈佳说：
正在查rsa的资料，又回到了这里，想自己实现一个简易的rsa。
卢磊说：
引用Leon的发言：
这种解释说法就是“鸡生蛋，蛋生鸡”问题，拿着要证明的结果作为证明的已知条件来证明问题！！！
link说：
引用shindo的发言：
我懂了，mφ(n)≡1(modn)=>mφ(n)=Kn+1,k为自然数(kn+1)^h展开多项式，除了1以外，全部含有kn，所以其他项都能被n整除而余1..也就是能推出(mφ(n))h≡1(modn)然后m这个中间数学gap还是挺大的...
去看数论中同余性质吧，
性质5：若a≡b（modm），c≡d（modm），那么ac≡bd（modm）（可乘性）。性质6：若a≡b（modm），那么an≡bn（modm）（其中n为自然数）。
可以看成是由h个式子相乘，然后再与m≡m(modn)相乘，这里m得到。。。
对头，到这就可以截止了，况且后面证明的很乱
电小弟说：
好像和CLRS算法差不多，但是各有各的特点及其长处.
突然发现，双方的公钥和私钥对换，还是能够顺利加密和解密的。
NeroLee说：
以m=kp为例，考虑到这时k与q必然互质。
这句话不对吧，比如说m=3n=3qp不行吗，那么k=3q,哪来必然互质？应该再细分
zoudaokou2006说：
引用NeroLee的发言：以m=kp为例，考虑到这时k与q必然互质。
根据RSA规范，要加密的信息m，范围为0~n-1，所以你说的不成立。
5.1.1RSAEPRSAEP((n,e),m)Input:(n,e)RSApublickeymmessagerepresentative,anintegerbetween0andn–1Output:cciphertextrepresentative,anintegerbetween0andn–1
引用zoudaokou2006的发言：
Thanks.现在懂了。
番石榴说：
我看到了未来的密钥是1mb起码。。。。。。
王军说：
65^17≡c(mod3233)说等于65^17≡2790(mod3233)即c等于2790想请问下，这里的2790是怎么算出来的？？
Lin说：
引用t.k.的发言：九的子标题（2）m与n不是互质关系中
“m与q必然互质”没错，因为m=kq
65^17≡c(mod3233)说等于65^17≡2790(mod3233)即c等于2790想请问下，这里的2790是怎么算出来的？？我指的是口算或者笔算不是利用计算机算65的17次方除以3233有没有简单算法如果笔算65的17次方会死人的。。。
Jecvay说：
一口气看完两篇,果然精彩
wfade说：
k与q必然互质卡在这里了
君升说：
你好，请教一下：像12306这样的网站，在使用时要下载他的证书并导入，这时下载的证书是证书请求文件CSR吗？还是已经经过签名的公钥了？
kellen_yan2014说：
终于搞懂了，非常感谢！
漠上花开说：
tim说：
tomas说：
这是我见过的最通俗易懂的解释！！
Jack说：
谢谢lz。但有个问题，“如果私钥被攻破，那么消息就会被破解”。这里是不是隐含了解密算法或者是加密算法，可以认为是公开的了，至少是容易获得的。如果是这样，为什么不能从加密算法和已知的公钥已经加密后的信息，反推出原始信息呢？
傅琦佳说：
小史说：
百度百科里关于扩展欧几里得算法有讲具体怎么做。
陈睿说：
豁然开朗，十分感谢
袁宇阳说：
有一个疑问，就是在加密的时候用的这个式子：m的e次方≡c(modn)来计算出的c，然后之后是把c给了爱丽丝让爱丽丝拿私钥去解m，我想问的是这时候知道c，可不可以还用之前那个得出c的式子：m的e次方≡c(modn)再反过去解出m，因为这时候n，c，e都已知。m就等于c(modn)再开e次方了。大神快粗来，急，在线等~~
杨国宝说：
第二次看了，还是没看太懂。下次继续学习。谢谢阮老师
Caleb说：
65^17≡2790(mod3233)这个式子成立吗？
2790mod3233=2790
65^17mod3233=887(matlab得到的结果)
另外2790^2753≡65(mod3233)这个式子中的2790^2753这个值，计算机可以算出来吗？
Codisan说：
还是有个疑问：alice回信的时候，咋整？
bob发信：bob(公钥加密)->alice(私钥解密)，这个逻辑我明白
alice回信，这个怎么处理？求解！！
我大哥海鹏说：
引用luke的发言：想通了。(m^e-kn)^d等同于m^(ed)-kn
把(m^e-kn)^d完全展开后只有一项不包含n的项m^edm^ed对n取余就等于(m^e-kn)^d对n取余
我谁也不是说：
引用Codisan的发言：还是有个疑问：alice回信的时候，咋整？
bob给alice发信，用的是Alice的公钥，Alice用自己的私钥解密；如果Alice要给bob回信，就换成bob的公钥加密，bob用自己的私钥解密。
骆驼说：
怒赞！！！！
引用王军的发言：65^17≡c(mod3233)说等于65^17≡2790(mod3233)即c等于2790想请问下，这里的2790是怎么算出来的？？我指的是口算或者笔算不是利用计算机算65的17次方除以3233有没有简单算法如果笔算65的17次方会死人的。。。
模幂法：依次计算65^2mod3233,65^4mod3233,65^8mod3233,65^16mod3233，最后再将65^16mod3233的结果和65相乘再mod3233，这样可以保证最多只要做2*log3(n)次大数乘法和大数取模运算就可以得出结果了。
悟空说：
感谢博主，虽然对数学的还没有完全搞懂，但是基本上能浅显理解RSA的理论基础了，感谢感谢。
lingjie_ding说：
阮先生好，我在看的时候也会有@袁宇阳的问题，可以直接拿公钥和加密后的数据反推出加密之前的数据吗？
scateu说：
"以m=kp为例，考虑到这时k与q必然互质，则根据欧拉定理，下面的式子成立："
这一句疑似应为
"考虑到这时kp与q必然互质"
嘿嘿说：
请自行百度快速幂取模算法，这是CS算法中一个比较基本的算法。
mentos说：
太棒！！！！逻辑清晰，描述清楚！感谢博主！真的是三言两语我完全看懂了！还有当时一直就在想能不能由n反推私钥的问题，还有私钥一定能解的证明，真是好感谢！教材和老师巴拉了一堆我什么都不知道
哈哈说：
以m=kp为例，考虑到这时k与q必然互质这块为什么？？
samaritan说：
如果事先能找到的目前发现的质数数据集，进行计算出数据库，这样的数据库会有多大。
路人甲说：
引用nkAmerica的发言：根本没有协商过程啊。都是用对方的公钥加密你的意思是在我们生成的密钥对里，并将公钥给了鲍勃，然后鲍勃也将自己生成的密钥对里的公钥给了爱丽丝？但我们在用SSH-KEYGEN生成密钥对时，给了鲍勃公钥，鲍勃是怎么将自己的密钥对里的公钥给爱丽丝的？
Conleyfree说：
lambda说：
引用我谁也不是的发言：
iamzken说：
zzzp说：
引用zz的发言：第四步计算模反元素下面这俩式子貌似符号弄错了～
应为:17x-3120y=1
引用zzzp的发言：
qwer说：
引用zzzp的发言：d=2753k=15.
y=-k两项相加的话好像才可以满足扩展欧几里德算法的要求ax+by=gcd(a,b)
braintaust说：
引用scateu的发言："以m=kp为例，考虑到这时k与q必然互质，则根据欧拉定理，下面的式子成立："
k与q必然互质，
原因是m小于n,m取整数，所以m必然为kp或是kq
同时得到m为kp（k小于q），n为kq（k小于p）
取m为kp，由于q是质数，k小于q，k与q互质
我的理解
matcloud说：
阮老师，你看云文档有处公式写错了:使用公钥加密的公式.
ｒａｍｓｅｙ说：
有个问题：因为决定是否能够破解的关键在分解ｎ＝ｐ×ｑ，而您提到目前最大的是破解到７６８位，是否意味着７６８位（包括７６８）位以下ＲＳＡ加密的都已经是不安全的了？
hacker说：
看懂了原理，数论知识也看懂了大概，不过博主真牛！
sherlook说：
引用Caleb的发言：65^17≡2790(mod3233)这个式子成立吗？
我用python算65^17mod3233=2790你matlab用错了吧2790^2753这个值计算机当然算的出来，python算了一下，结果占了我半个屏幕。。。
李耀东说：
这个不对称算法绝对是有漏洞的！根据已知e17和n模3233可以算得d＝1193虽然我不知道真的d为3233但是可以等效算出加密值！其实这个基于的是素数的耦合！既自然数的n次幂mod一个素数＝自然数本身而求出那个幕与素数的关系的这个数学推论我感觉可以写个猜想
Bruce说：
HuKeping说：
你可以把(m^e-kn)^d这个等式展开，形式为：C(d,0)*m^ed*(kn)^0+C(d,1)*m^e(d-1)*(kn)^1+...
所以只有一项是不包含kn的，而所有包含n的项在对n取余的操作中都可以消掉。因此得出了那个结论
胡帆说：
在第二种m与n不互质的情况下，只有当m小于n时，才会有k与q互质。否则若m大于n，则k值可取成q的倍数，这时却也依然满足m与n不互质的前提条件。
neo1218说：
(me-kn)d≡m(modn)它等同于求证med≡m(modn)有大神可以解释一下吗？
哦，我看到了
Solid说：
引用samaritan的发言：如果事先能找到的目前发现的质数数据集，进行计算出数据库，这样的数据库会有多大。
你可以百度一下《100万以内的质数》这篇文档，word文档有几十页。而100万大约是20位左右的样子。自行想象1024位的质数有多少个。大概会是那篇文档的2^1000倍
地狱鬼才说：
m^e=c(modn)不应该是m^e=n*k+c么？65^17=2790(mod3233)k=1才是2790纠结
yy说：
这个不对啊，，如果kp大于q呢？？
这里只能是m和N互质，也就是m的域最好选定为m
程亮说：
看完后懂RSA的加密原理了，感谢！
请详细解答说：
在：“（2）m与n不是互质关系”这段中，
[(kp)^q-1]^(h(p-1))×kp≡kp(modq)
请问这是如何得到的？
drel说：
写的很明了：步骤很清晰，不便详细讲述的方法性的步骤也提供了链接！非常感谢！
Algeron说：
好文，由浅入深，公钥和密钥的生成大概理解了。可还是不懂，具体是怎么加密的。比如，现在甲要给乙发送一串字符串：“hello”，具体是怎么使用生成的公钥加密这段字符串，又是怎么使用私钥解密的。
Algernon说：
引用Algeron的发言：好文，由浅入深，公钥和密钥的生成大概理解了。可还是不懂，具体是怎么加密的。比如，现在甲要给乙发送一串字符串：“hello”，具体是怎么使用生成的公钥加密这段字符串，又是怎么使用私钥解密的。
明白了，最后的部分没仔细看。
Colorful说：
关于d的求法那里应该有无数个解这里取的是特解吧，那到底应该如何算出d呢
余半仙说：
都看懂了，学渣大学考试周路过
斯文一派说：
请问一下，在加密过程中，通过m^e≡c(modn)来找到c，
则6517≡2790(mod3233)==>c=2790。
那么，根据同余的性质，c肯定不唯一，kc也能满足结果，（传递性，a≡b(modm)，b≡c(modm)，则a≡c(modm)）
为何确定c为2790呢？
frozone说：
引用请详细解答的发言：在：“（2）m与n不是互质关系”这段中，
这是为了下一步构造出来的，问题倒不大；倒是下一步(kp)^ed≡kp(modq)是不严谨的，写成(kp)^h(ed)≡kp(modq)更好。
bianchx说：
反过来也是单向的。只是人物的昵称换了
maicss说：
公钥和私钥的数据都采用ASN.1格式表达
这个表达的实例链接失效了
ffbh说：
eureka说：
由这个式子：ed-1=kφ(n)推导出的应该是：ex-φ(n)y=1而不是：ex+φ(n)y=1的呀？
Sha说：
牛逼，附上代码就更好啦
cfzhang说：
精彩！！我看到原来破根据rsa的公钥破解私钥本质上是一个大整数的质因数分解问题！我惊呆了！吓的我赶紧去分解质因数了，发现没软用。。。目前能破768bit二进制对应的整数。更别说某些场合用的是2048位bit二进制数。。
正纳闷，我拿到私钥加密的数字，怎么解出我的秘钥m，然后果然是一个加密一个解密规则，密不可分，学习了！
引用mentos的发言：太棒！！！！逻辑清晰，描述清楚！感谢博主！真的是三言两语我完全看懂了！还有当时一直就在想能不能由n反推私钥的问题，还有私钥一定能解的证明，真是好感谢！教材和老师巴拉了一堆我什么都不知道
qy_jasmine说：
引用袁宇阳的发言：有一个疑问，就是在加密的时候用的这个式子：m的e次方≡c(modn)来计算出的c，然后之后是把c给了爱丽丝让爱丽丝拿私钥去解m，我想问的是这时候知道c，可不可以还用之前那个得出c的式子：m的e次方≡c(modn)再反过去解出m，因为这时候n，c，e都已知。m就等于c(modn)再开e次方了。大神快粗来，急，在线等~~
奔跑西红柿说：
@qy_jasmine：
不需要那么多次计算啊，知道e=17、n=3233、c=2790、设m从1开始++，只需要实验65次，就能找到对应c=2790这个m值了，不需要私匙也可以截获信息m啊。只要知道他们发送的每次是什么值，并且知道公匙就行了啊。大神给解释一下，还是感觉似懂非懂呢？
sharmin说：
爱丽丝回复，即是爱丽丝发送信息给鲍勃。因此，你反过来看，即是爱丽丝使用鲍勃的公钥加密，鲍勃使用自身私钥解密。你需要知道，通信双方都应邮寄一对密钥，即公钥和私钥。
焰说：
引用sharmin的发言：
不需要邮寄私钥，两人互相邮寄公钥就可以了（公钥被监听到也没关系），然后彼此用对方的公钥加密信息传送给对方，收到信息的人用自己的私钥解密信息就可以了。
xucg说：
小马说：
m与n互质时，mφ(n)≡1(modn)怎么推导出(mφ(n))h×m≡m(modn)
hello说：
模不一样!
卡卡说：
m^ed=m(modn)这一步的希望帮忙推理.谢谢
马甲嘎嘎说：
hi，我有个疑问：程序要计算大数的幂次方，是怎么计算的？比如本文中的例子2790的2753次方（2790^2753）是怎么计算的呢？我用ptyhon，js，c都计算不出来，希望解惑！
q说：
請問2790**2753≡X(mod3233)要如何算X，都給出無窮大沒辦法計算
wuxx说：
阮老师好，请问根据上一篇的公式，不是φ（pq)=pq吗，为什么φ（61x53)=60x52
流氓兔说：
lw说：
引用wuxx的发言：阮老师好，请问根据上一篇的公式，不是φ（pq)=pq吗，为什么φ（61x53)=60x52
φ（pq)=φ(q)*φ(P)φ(q)=q-1φ(p)=p-1
状说：
那么服务端加密，客户端如何解密？
Hz说：
“数学是万物之源”的别走，你这句话是唯心主义好吗。。
擦蝌蚪说：
@shindo：
总算看懂了，看样子大家都对这一块有问题
Jackxwb说：
引用状的发言：那么服务端加密，客户端如何解密？
服务器使用客户端产生的公钥跟模加密就可以了
RainyH2O说：
有一点没懂，为什么e常常选用65537，网上查到的资料是为了减少加密运算次数，但如果φ(n)恰好是65537的倍数，也就是说φ(n)与e不互质该怎么办？换一个质数么？但是我看网上某些RSA的实现直接就用了65537，没加上检测和替换的步骤，还是说有什么理论保证了φ(n)一定不是65537的倍数呢？
温酒斩近平说：
服务端发送的加密数据，客户端如何解密？
nafe说：
引用alphaqcode的发言：
Phper说：
sunhk说：
通过程序的辗转相除法来计算：17x+3120y=1方程解为：(-367,2)
ywqqqqq说：
引用sunhk的发言：通过程序的辗转相除法来计算：17x+3120y=1方程解为：(-367,2)
你把解代入进去验证等式了吗？
KB260说：
就算没看到具体的证明过程，但还是受益良多。。。
边宏飞说：
沈琦斌说：
您好，我刚开始想的时候也没有想明白，还自己计算φ（222）了，后来想明白了。7的222次方=7的220次方*7的2次方；7的220次方各位是1,7的平方各位是9，相乘个位是9。再往后的数学证明就不太明白了。
jiahe说：
引用Jack的发言：为什么不能从加密算法和已知的公钥已经加密后的信息，反推出原始信息呢？
你这是对称密码的攻击方式
tbswang说：
这个二元方程的解是不唯一的,辗转相除法只是算出了其中的一个解.wiki的解释,
x一般取最小正整数解,所以,x=x+kn=-367+1*3120=2753,所以,y=-15.
tomix说：
'''将c代入要我们要证明的那个解密规则：
(m^e-kn)^d≡m(modn)
m^(ed)≡m(modn)'''
我一开始没懂，百度了一下，这里面应该是用到了这个公式(a^b)%p=((a%p)^b)%p
张延勇说：
前端技术中无法做到私钥加密，公钥解密吗？求阮大大帮帮忙，有点急。。。很是感谢..
小囧子说：
这个方程可以用"扩展欧几里得算法"求解，此处省略具体过程。总之，爱丽丝算出一组整数解为(x,y)=(2753,-15)，即d=2753。
扩展欧几里得的解不是有无数个吗，我要是选一个d很大，不也可以防止破解吗，这也只能暴力破解吧
Nisen说：
abigail说：
赞！写的真好！跟看精彩的小说一样过瘾！
HW说：
[(kp)q-1]h(p-1)×kp≡kp(modq)这个部分我想了一下貌似有点问题，
前面一步提到
（kp）^(q-1)modq=1---费马小定理然后可以得到[(kp)^(q-1)]^(h(p-1))modq=1--因为取模运算的运算规则，很容易得到这个部分
但是，这个怎么推出
[(kp)^(q-1)]^(h(p-1))*kpmodq=kp这个成立的前提条件是kpmodq=kp,我们只知道gcd(kp,q)=1,但这个不等于kpmodq=kp吧
这步不是很理解，希望有人解释一下
这里我把我当M与n不是互质的情况的证明写一下，有不对的地方可以讨论，虽然我以后可能不会回来看了
当M与n不互质时，由于n=p*q,那么gcd(M,n)=p或者gcd(M,n)=q,跟阮老师在这里假设的一样，我假设M=k1*p此时，k1必然与q互质，不然M会变成pq*k,这样M会被n直接整除
(1)根据费马小定理，当M与q互质时，我们可以得到M^(q-1)%q=1
(2)由取模运算的运算规则a^b%q=(a%q)^b%q[M^(q-1)]^[k2(p-1)]%q=1
(3)因为(p-1)(q-1)=φ(n),ed=k2φ(n)+1这个不懂的请往上翻到φ(n)的推导处，很清楚所以我们得到M^(ed-1)%q=1
(4)改写这个等式到：
M^(ed-1)=k3*q+1两边乘上M,得到M^(ed)=k3*qM+M
(5)我们在之前假设M=k1p所以，得到M^(ed)=k3*q*k1*p+MM^(ed)=k1k3*(pq)+M因为p*q=n所以M^(ed)=k1k3*n+M也就是M^edmodn=M得证！
乔则铈说：
第九个的子标题（2）“m必然等于kp或kq”不对啊，根据举例，m是65，p是61，q是53，不对啊？
qing说：
看到有留言说客户端如果要发消息给服务端怎么办？怎么保证加密，当然，客户端可以发公钥给服务端，但是不是通常的做法。以HTTPS中ssl的做法为例子，其实通信的主体还是以对称加密为主，1.客户端拿到服务器的公钥x2.客户端随机生成一串字符串y，并用x加密变成y`发送给服务器。3.服务器端拿到加密之后的y`用私钥q解密，得到y。4.此时服务器和客户端都拿到了一个y，而且是在安全的状态下交换了这个y。5.之后的通信都是用这个y做对称加密。
bobjiao说：
引用jimohou的发言：(kp)^ed=tq+kp=>tq=(kp)(kp^ed-1-1)因为p,q是互质,所以kp必然不能整除q,那么就必然整除t,t=t'p
为什么不设t=t'k
zxy说：
为什么m必须小于n
了解了。为什么m必须小于n在第二种m与n不互质的情况下，只有当m小于n时，才会有k与q互质。否则若m大于n，则k值可取成q的倍数，这时却也依然满足m与n不互质的前提条件。
高中生说：
写成
ex-φ(n)y=1
更好吧.
arainer说：
引用乔则铈的发言：第九个的子标题（2）“m必然等于kp或kq”不对啊，根据举例，m是65，p是61，q是53，不对啊？
lyman说：
为什么私钥d必须为正整数才行
jsee说：
引用arainer的发言：
弄懂同余再说吧朋友
代文朱说：
因为mn是不是互质关系并且n是两个两个质因数的乘积，那么m的因数必然包含n的质因数p或者q
Peng说：
这个（2）引用的是不是不对啊，应该是根据a≡1mod(n),所以a^b≡1mod(n)吧所以M^(q-1)≡1mod(n)时，(M^(q-1))^(p-1)≡1mod(n)
(2)由取模运算的运算规则a^b%q=(a%q)^b%q[M^(q-1)]^[k2(p-1)]%q=1
jonkee说：
m不是表示待加密的數據嗎？待加密的數據不是完全不可預測的嗎？為什麼說“m必然等于kp或kq”？
PPD说：
我可能太笨```m与n互质。根据欧拉定理，此时mφ(n)≡1(modn)得到(mφ(n))h×m≡m(modn)```这个推导都没搞懂。请小伙伴解释一下，谢谢~
lizhifeng说：
引用PPD的发言：我可能太笨```m与n互质。根据欧拉定理，此时mφ(n)≡1(modn)得到(mφ(n))h×m≡m(modn)```这个推导都没搞懂。请小伙伴解释一下，谢谢~
设m^$(n)=kn+1则m^($(n)h+1)%n=(kn+1)^h*m%n=m%n。多项式展开你不会么？
ChenJianhui说：
对于（2）m和n不是互质的情况，是不是需要考虑m是n的倍数的情况尽管m^ed≡m(modn)也是成立的
另外后面的证明可不可以这样，(kp)^ed≡kp(modq),(kp)^ed≡kp(modp)=>(kp)^ed≡kp(mod[p,q])=>m^ed≡m(modn),[p,q]表示p和q的最小公倍数。
大熊有点飘说：
等式左边是kp的ed次方，tq=kp的ed-1次方，p是tq的因数，q与p互质，所以t必然是p的倍数
根据欧拉定理，mφ(n)可以表示为kn+1，mφ(n)的h次方为kn+1的h次方，然后把左边的多项式展开后，发现为m加上n的各种倍数，被n除，余数只能是m
young说：
峰哥，我利用拓展欧几里得算法求得17x+3120y=1，x=-367,y=2，想问下，私钥一对整数都必须是正整数吗？
zl说：
[(kp)q-1]h(p-1)×kp≡kp(modq)这个是怎么得出来的啊
Dani说：
第五步，计算e对于φ(n)的模反元素d。---是不是意味了已知公钥(e,n)可以算出私钥(d,n)
引用Dani的发言：第五步，计算e对于φ(n)的模反元素d。---是不是意味了已知公钥(e,n)可以算出私钥(d,n)
是的，服务端然后用私钥解密即可
才搞懂说：
同一把公钥，对相同的数据，进行加密操作，发现每次加密的最终的密文是不一样的。
CHJ吉吉说：
d是不是可以有多个解？d能有多个解不就等于密钥可以有多个
testqqqq说：
有个问题，关于ed，e是随机生成，但是d是e的模反，那么（e，d）这一对就不是唯一的咯？根据第一部分RSA算法原理的来说，b+kn都是a的模反？
zerolei说：
n说：
查了下RSA算法，加密通信需要双方交换公钥的呀。没想明白客户端是怎么做的，成千上万的客户端都跟服务端交换公钥感觉不现实。对于这种一对多的服务，RSA在实际中是怎么应用的呢？
WhXcjm说：
完全理解，受益匪浅，感谢
liuzx说：
n一定得是两个质数之积吗？我看算法原理好像只要能求出φ(n)=(p-1)就可以实现
拉边说：
引用liuzx的发言：n一定得是两个质数之积吗？我看算法原理好像只要能求出φ(n)=(p-1)就可以实现
ked1876说：
ed≡1(modφ(n))正确的应该是ed≡1(modn)
XornTan说：
hys说：
应该是m与q必然互质
RSA的好处：坏处：
Stan说：
因数分解应该改为质因数分解吧！只有分解成质因数才有意义
CCHL说：
像这样的高质量的blog难寻，我自己也写了些blog向前辈学习
顺说：
lizhi说：
引用n的发言：查了下RSA算法，加密通信需要双方交换公钥的呀。没想明白客户端是怎么做的，成千上万的客户端都跟服务端交换公钥感觉不现实。对于这种一对多的服务，RSA在实际中是怎么应用的呢？
这就涉及到PKI认证体系,可以参考HTTPS
zff2023说：
第一步，随机选择两个不相等的质数p和q。爱丽丝选择了61和53。（实际应用中，这两个质数越大，就越难破解。）
有个问题，这里两个质数p和q从哪里取，是需要先保存一批质数然后随机获取吗