RSA算法原理(二)

作者: 阮一峰

日期: 2013年7月 4日

上一次,我介绍了一些数论知识

有了这些知识,我们就可以看懂RSA算法。这是目前地球上最重要的加密算法。

六、密钥生成的步骤

我们通过一个例子,来理解RSA算法。假设爱丽丝要与鲍勃进行加密通信,她该怎么生成公钥和私钥呢?

第一步,随机选择两个不相等的质数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< e < φ(n),且e与φ(n) 互质。

爱丽丝就在1到3120之间,随机选择了17。(实际应用中,常常选择65537。)

第五步,计算e对于φ(n)的模反元素d。

所谓"模反元素"就是指有一个整数d,可以使得ed被φ(n)除的余数为1。

  ed ≡ 1 (mod φ(n))

这个式子等价于

  ed - 1 = kφ(n)

于是,找到模反元素d,实质上就是对下面这个二元一次方程求解。

  ex + φ(n)y = 1

已知 e=17, φ(n)=3120,

  17x + 3120y = 1

这个方程可以用"扩展欧几里得算法"求解,此处省略具体过程。总之,爱丽丝算出一组整数解为 (x,y)=(2753,-15),即 d=2753。

至此所有计算完成。

第六步,将n和e封装成公钥,n和d封装成私钥。

在爱丽丝的例子中,n=3233,e=17,d=2753,所以公钥就是 (3233,17),私钥就是(3233, 2753)。

实际应用中,公钥和私钥的数据都采用ASN.1格式表达(实例)。

七、RSA算法的可靠性

回顾上面的密钥生成步骤,一共出现六个数字:

  p
  q
  n
  φ(n)
  e
  d

这六个数字之中,公钥用到了两个(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),但是你没法对下面这个整数进行因数分解。

  12301866845301177551304949
  58384962720772853569595334
  79219732245215172640050726
  36575187452021997864693899
  56474942774063845925192557
  32630345373154826850791702
  61221429134616704292143116
  02221240479274737794080665
  351419597459856902143413

它等于这样两个质数的乘积:

  33478071698956898786044169
  84821269081770479498371376
  85689124313889828837938780
  02287614711652531743087737
  814467999489
    ×
  36746043666799590428244633
  79962795263227915816434308
  76426760322838157396665112
  79233373417143396810270092
  798736308917

事实上,这大概是人类已经分解的最大整数(232个十进制位,768个二进制位)。比它更大的因数分解,还没有被报道过,因此目前被破解的最长RSA密钥就是768位。

八、加密和解密

有了公钥和密钥,就能进行加密和解密了。

(1)加密要用公钥 (n,e)

假设鲍勃要向爱丽丝发送加密信息m,他就要用爱丽丝的公钥 (n,e) 对m进行加密。这里需要注意,m必须是整数(字符串可以取ascii值或unicode值),且m必须小于n。

所谓"加密",就是算出下式的c:

  me ≡ c (mod n)

爱丽丝的公钥是 (3233, 17),鲍勃的m假设是65,那么可以算出下面的等式:

  6517 ≡ 2790 (mod 3233)

于是,c等于2790,鲍勃就把2790发给了爱丽丝。

(2)解密要用私钥(n,d)

爱丽丝拿到鲍勃发来的2790以后,就用自己的私钥(3233, 2753) 进行解密。可以证明,下面的等式一定成立:

  cd ≡ m (mod n)

也就是说,c的d次方除以n的余数为m。现在,c等于2790,私钥是(3233, 2753),那么,爱丽丝算出

  27902753 ≡ 65 (mod 3233)

因此,爱丽丝知道了鲍勃加密前的原文就是65。

至此,"加密--解密"的整个过程全部完成。

我们可以看到,如果不知道d,就没有办法从c求出m。而前面已经说过,要知道d就必须分解n,这是极难做到的,所以RSA算法保证了通信安全。

你可能会问,公钥(n,e) 只能加密小于n的整数m,那么如果要加密大于n的整数,该怎么办?有两种解决方法:一种是把长信息分割成若干段短消息,每段分别加密;另一种是先选择一种"对称性加密算法"(比如DES),用这种算法的密钥加密信息,再用RSA公钥加密DES密钥。

九、私钥解密的证明

最后,我们来证明,为什么用私钥解密,一定可以正确地得到m。也就是证明下面这个式子:

  cd ≡ m (mod n)

因为,根据加密规则

  me ≡ c (mod n)

于是,c可以写成下面的形式:

  c = me - kn

将c代入要我们要证明的那个解密规则:

  (me - kn)d ≡ m (mod n)

它等同于求证

  med ≡ m (mod n)

由于

  ed ≡ 1 (mod φ(n))

所以

  ed = hφ(n)+1

将ed代入:

  mhφ(n)+1 ≡ m (mod n)

接下来,分成两种情况证明上面这个式子。

(1)m与n互质。

根据欧拉定理,此时

  mφ(n) ≡ 1 (mod n)

得到

  (mφ(n))h × m ≡ m (mod n)

原式得到证明。

(2)m与n不是互质关系。

此时,由于n等于质数p和q的乘积,所以m必然等于kp或kq。

以 m = kp为例,考虑到这时k与q必然互质,则根据欧拉定理,下面的式子成立:

  (kp)q-1 ≡ 1 (mod q)

进一步得到

  [(kp)q-1]h(p-1) × kp ≡ kp (mod q)

  (kp)ed ≡ kp (mod q)

将它改写成下面的等式

  (kp)ed = tq + kp

这时t必然能被p整除,即 t=t'p

  (kp)ed = t'pq + kp

因为 m=kp,n=pq,所以

  med ≡ m (mod n)

原式得到证明。

(完)

珠峰培训

简寻

留言(127条)

数学乃万物之源呐

第一时间过来感谢阮先生无私奉献如此易懂的算法原理!

终于体会到什么叫“深入浅出”

受益匪浅,谢谢!

又一篇好文,感谢阮兄的无私分享!

如果量子计算机实现的话是不是就能破解了?

引用Du的发言:

如果量子计算机实现的话是不是就能破解了?

RSA的困难性是基于大整数因子分解在计算上不可行,如果计算能力上去的话,当然是可以破解现有的密码。

引用杨琪的发言:

数学乃万物之源呐

数学自有其独特的魅力。

的子标题(2)m与n不是互质关系

考虑到这时k与q必然互质

应该是“m与q必然互质”。

另外,数学公式用mathjax会更好看一些。

[(kp)q-1]h(p-1) × kp ≡ kp (mod q)
可以直接一步得到结论了,何必之后那几步推导?

没看懂好伤心。

不太明白,继续琢磨一下!

第四步计算模反元素下面这俩式子貌似符号弄错了~

ex + φ(n)y = 1
已知 e=17, φ(n)=3120,
   17x + 3120y = 1

当年数学没学好,看得快哭了。

只看懂了个大概,不过对RSA算法有一个很好的印象了。这真是一篇好文章呀,阮兄的文章没有白付费呀。

别说DES……这个加密算法因为太容易被破解早就被废除了,建议改成3DES或AES.

精彩啊,这两篇文章

精彩!!!

谢谢你的文章。想问个问题,那个鲍勃向爱丽丝发消息的例子是单向的,如果爱丽丝想回复的话该怎么办呢?这时候是不是必须先协商一个密钥然后对称加密?

引用asdf的发言:

[(kp)q-1]h(p-1) × kp ≡ kp (mod q)
可以直接一步得到结论了,何必之后那几步推导?

为了让mod作用于n,而不是q。

引用STL的发言:

谢谢你的文章。想问个问题,那个鲍勃向爱丽丝发消息的例子是单向的,如果爱丽丝想回复的话该怎么办呢?这时候是不是必须先协商一个密钥然后对称加密?

根本没有协商过程啊。都是用对方的公钥加密

谢谢博主的文章。
请问一下,
m^e ≡ c (mod n)这公式怎么来的?
只是e跟φ(n)互质啊

想到这个算发的人太伟大了,这是一个回答纯数学有什么用的最好案例。还有没有其他的像RSA这样简单有效的非对称加密方法呢?恐怕像找外星人一样难了。

引用felix021的发言:

别说DES……这个加密算法因为太容易被破解早就被废除了,建议改成3DES或AES.

DES废除的原因一个是密钥位数太少,在现在的计算能力下,已经无法保证安全,第二个原因是,DES是为硬件加密设计的,对于现在软件来说计算效率不够好,第三个原因是,一直有人怀疑DES的S盒中隐藏着后门,而这个后门被美国安全局掌握。所以提出了AES

3DES理论密钥长度为56*3=168bits,但是,在受到中间人攻击的条件下,退化为112bits。其安全性仍然不够好

写的很不错,浅显易懂,但看完,觉得最后一段有个疑惑,请教一下:(kp)ed = tq + kp
这时t必然能被p整除,即 t=t'p,这个必然性是如何证明的?请指导下~~谢谢

为什么公匙不能猜测的进行解密呢。。。

正在做加密产品,以应对来自霉国的窃听威胁,感谢楼主的理论分析。

这两篇文章写的太好了,对RSA算法浅入深出,让我明白很多。但有一个地方没看明白:博主写道

加密就是算出 me ≡ c (mod n)中的c

我想问一下,为什么要这样做?和上篇文章中什么地方有联系?还是就是这么规定的?

此时,由于n等于质数p和q的乘积,所以m必然等于kp或kq

這個怎麼得來的?
m不是明文嗎,明文爲什麽一定等於kp或者kq?

引用STL的发言:

谢谢你的文章。想问个问题,那个鲍勃向爱丽丝发消息的例子是单向的,如果爱丽丝想回复的话该怎么办呢?这时候是不是必须先协商一个密钥然后对称加密?

想双向通信的话肯定要定义两套公钥和秘钥了,都用对方的公钥加密发送,然后接收方用自己的秘钥解密就OK了!

终于明白rsa是怎么一回事了,thanks!!

引用Ray的发言:

RSA的困难性是基于大整数因子分解在计算上不可行,如果计算能力上去的话,当然是可以破解现有的密码。

量子计算机是并行的,1024位的密码用1024个量子处理单元做计算,只要1秒。只是现在技术最多能做到8位量子处理单元的级别。so...

引用Martin.Hsuching的发言:

写的很不错,浅显易懂,但看完,觉得最后一段有个疑惑,请教一下:(kp)ed = tq + kp
这时t必然能被p整除,即 t=t'p,这个必然性是如何证明的?请指导下~~谢谢

两边同时整除p,又p、q互质,于是t必定是p的整数倍。

引用哇哈哈的发言:

此时,由于n等于质数p和q的乘积,所以m必然等于kp或kq

這個怎麼得來的?
m不是明文嗎,明文爲什麽一定等於kp或者kq?

数学角度:m、n不是互质关系,说明m、n必定含有非1公因子,而n等于质数p和q的乘积,因此m必然等于kp或kq。

一直在使用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、to Martin.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、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、

帮我理解了不少,感谢!还有一点向您请教下: 1.“(1)m与n互质。 根据欧拉定理,此时mφ(n) ≡ 1 (mod n) 得到(mφ(n))h × m ≡ m (mod n)”这个是怎么得到啊?(mφ(n))h≡1(mod n)这样写,对吗?接着,后面又多乘以个m,就能变成这样啦(mφ(n))h × m ≡ m (mod n),这个是为什么呢? 2.这个跟1.应该是同样的问题“(kp)q-1 ≡ 1 (mod q) 进一步得到[(kp)q-1]h(p-1) × kp ≡ kp (mod q)”这个也是,左右都乘以kp,这是为什么呢? 3.这个是我看RSA算法原理(一)中的疑问:“因此,7的任意次方的个位数(例如7的222次方),心算就可以算出来”这是怎么得到的呢?我只想到了:7的222次方=7的2次方*7的(4*55)次方,下面就不知道了。还望解惑,不胜感激~

引用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、

帮我理解了不少,感谢!还有一点向您请教下:

1.“(1)m与n互质。

根据欧拉定理,此时mφ(n) ≡ 1 (mod n)

得到(mφ(n))h × m ≡ m (mod n)”这个是怎么得到啊?(mφ(n))h≡1(mod n)这样写,对吗?接着,后面又多乘以个m,就能变成这样啦(mφ(n))h × m ≡ m (mod n),这个是为什么呢?

2.这个跟1.应该是同样的问题“(kp)q-1 ≡ 1 (mod q)

进一步得到[(kp)q-1]h(p-1) × kp ≡ kp (mod q)”这个也是,左右都乘以kp,这是为什么呢?

3.这个是我看RSA算法原理(一)中的疑问:“因此,7的任意次方的个位数(例如7的222次方),心算就可以算出来”这是怎么得到的呢?我只想到了:7的222次方=7的2次方*7的(4*55)次方,下面就不知道了。还望解惑,不胜感激~

如果量子计算机可以破解1024bit的RSA,那么可以用量子计算机做更长bit位的加密,比如2048bit...,直到无法破解

to:赵三

1,(mφ(n))h≡1(mod n)这样写是对的,这个可以通过≡的含义,然后通过一个推导(也就是从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

证明
  (m^e - kn)^d ≡ m (mod n)
等同于证明
  m^ed ≡ m (mod n)

卡住在这里了,麻烦帮忙解释一下。

相当详实生动,非常感谢,,,,就是举例子的数字有点大了,,普通计算机直接正无穷大了,,,

问个问题,
1,这个巨大的质数或那两个相乘质数从哪来的,2048位的从哪来的。RSA算法的可靠性依赖于大整数的因数分解,是一件非常困难的事情,那大整数现在最大到多少了,2048位以上的现在有么,好像还有什么美国输出限制。
2,如果分解困难,用现在产生大质数的算法,是否可以反推出来大质数,产生一个对应列表,就像md5的彩虹表,是否就可以破解。

谢谢

你好,我觉得第五步骤里面:
所谓"模反元素"就是指有一个整数d,可以使得ed被φ(n)除的余数为1。

这句话后半句,应该是使得 φ(n) 被ed除的余数为1。

这是来自wiki的除法举例:
15 可以被 5 整除,记作 5|15。

文章中本意应该是ed除以φ(n)的余数是1的逻辑。

其它都很清晰,第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 (mod n)
等同于证明
 m^ed ≡ m (mod n)

卡住在这里了,麻烦帮忙解释一下。

唉,我也卡在这里了。求高人继续。

引用luke的发言:

唉,我也卡在这里了。求高人继续。

想通了。 (m^e - kn)^d 等同于 m^(ed)-kn

而 (m^e - kn)^d ≡ m (mod n)

意味着,(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 (mod n)

引用ssapym的发言:

问个问题,
1,这个巨大的质数或那两个相乘质数从哪来的,2048位的从哪来的。RSA算法的可靠性依赖于大整数的因数分解,是一件非常困难的事情,那大整数现在最大到多少了,2048位以上的现在有么,好像还有什么美国输出限制。
2,如果分解困难,用现在产生大质数的算法,是否可以反推出来大质数,产生一个对应列表,就像md5的彩虹表,是否就可以破解。

谢谢

2^1024大约是10^308这个数量级,包含的素数可以由素数定理知道大约是x/ln(x)这个数量级,可选的素数p和q太多了,p*q的组合就更多了,怎么做彩虹表?
彩虹表是基于有一些常用的密码(比如password, 123456)算出来的,你随机选一个密码,多半不会出现在彩虹表中。同理,你随机选两个p,q,怎么查彩虹表?

找到高人了,写得清楚,有例子,每步都写出原理。

谢谢阮老师深入浅出的讲解,我知道了RSA算法是怎么回事儿了。
我感觉那些严谨的证明过程不必细致追究,主要是搞清楚RSA算法是什么,除非那些数学专业的。

我无法读懂上面的数学公式.
请问,高中水平的我,需要学习那些书本,才能看懂上面的公式呢?
谢谢各位.

我懂质数

引用介木的发言:

我无法读懂上面的数学公式.
请问,高中水平的我,需要学习那些书本,才能看懂上面的公式呢?
谢谢各位.

我懂质数

高中确实不涉及这方面的知识。找点关于余数的数论书看,知道基本的同余定理就行了。

我有个问题

根据   c^d ≡ m (mod n)

加密者不知道私钥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?

您好,以前看过你的这篇文章了,最近在看一个系统teamcity的登录过程,它会先给用户发一个公钥,然后用这个公钥对密码进行加密,发给服务器,从我看来,好像每次它发过来的公钥都是同一个串,是不是说只要有足够的计算力和足够的时间,我从这个公钥推出了其中的私钥,就可以破解用户发给它的所有密码?
我比较困惑的是,如果一个系统的安全系数要求很高的话,不需要经常更换公钥吗?
有没有可能一个经常破解密码的人,在一个地方看到一个公钥正好是他之前破解过的,那他也就能轻易破解新系统的密码? 我们所能使用的公钥理论上市无限的吗?

希望能够解答,谢谢

第四步,随机选择一个整数e,条件是1

e不一定要小于φ(n)吧,根据欧拉定律,e只要跟φ(n) 互质就可以了

求大神解惑

引用袁定平的发言:

您好,以前看过你的这篇文章了,最近在看一个系统teamcity的登录过程,它会先给用户发一个公钥,然后用这个公钥对密码进行加密,发给服务器,从我看来,好像每次它发过来的公钥都是同一个串,是不是说只要有足够的计算力和足够的时间,我从这个公钥推出了其中的私钥,就可以破解用户发给它的所有密码?
我比较困惑的是,如果一个系统的安全系数要求很高的话,不需要经常更换公钥吗?
有没有可能一个经常破解密码的人,在一个地方看到一个公钥正好是他之前破解过的,那他也就能轻易破解新系统的密码? 我们所能使用的公钥理论上市无限的吗?

希望能够解答,谢谢

个人观点:
1,公钥本来就是公开的,没有必要更换;
2,公钥不可能(所需时间和计算力无比的巨大)推算出私钥;
3,首先一个人不可能破解过一个公钥。其次是简单的算法,私钥对应一个确定的公钥,这是有风险的,所以现在的加密算法还使用了随机数,破解不可能,运气更不可能。

引用STL的发言:

谢谢你的文章。想问个问题,那个鲍勃向爱丽丝发消息的例子是单向的,如果爱丽丝想回复的话该怎么办呢?这时候是不是必须先协商一个密钥然后对称加密?

每个个体都有自己的公钥和私钥,在通信中,故爱丽丝也有自己的公钥和私钥。

引用Martin.Hsuching的发言:

写的很不错,浅显易懂,但看完,觉得最后一段有个疑惑,请教一下:(kp)ed = tq + kp
这时t必然能被p整除,即 t=t'p,这个必然性是如何证明的?请指导下~~谢谢

(kp)^ed = tq + kp => tq = (kp)(kp^ed-1 - 1)
因为p,q是互质,所以kp必然不能整除q,那么就必然整除t,t=t'p

引用ssapym的发言:

问个问题,
1,这个巨大的质数或那两个相乘质数从哪来的,2048位的从哪来的。RSA算法的可靠性依赖于大整数的因数分解,是一件非常困难的事情,那大整数现在最大到多少了,2048位以上的现在有么,好像还有什么美国输出限制。
2,如果分解困难,用现在产生大质数的算法,是否可以反推出来大质数,产生一个对应列表,就像md5的彩虹表,是否就可以破解。

谢谢

引用mine260309的发言:

2^1024大约是10^308这个数量级,包含的素数可以由素数定理知道大约是x/ln(x)这个数量级,可选的素数p和q太多了,p*q的组合就更多了,怎么做彩虹表?
彩虹表是基于有一些常用的密码(比如password, 123456)算出来的,你随机选一个密码,多半不会出现在彩虹表中。同理,你随机选两个p,q,怎么查彩虹表?

我的看法:
p*q的积的二进制的位数如果固定并确定为1024,则p和q的取值只能在一定范围内取,这在RSA密钥生成软件中自然会有指定。如果所有的密钥生成机制都按同一规定,那么由于素数资源不是随机无限的(有素数生成机制的限制,有随意取两个素数的乘积的二进制位数的限制),设素数资源的个数为n,在有限的素数资源中取出两个数的可能组合将是C|(2,n)。将每个组合的乘积一一列出,就可以组成彩虹表,可以从乘积列表中查找出对应的素数组合,进而推出公钥和私钥。素数资源不够的软件产生的密钥,尤其具有这样的隐患,看似很安全,实际上人家大的机构很容易破解出私钥来。所以,生产大素数的机构就像开矿公司,也像数字银行,拥有的素数资源越多越安全。不知是否可以这样理解?

不同机构产生的证书(包括私钥、公钥)的质量(指安全保证)是良莠不齐的。

我想ssapym彩虹表的本意即在如此。

引用luke的发言:

唉,我也卡在这里了。求高人继续。


  (m^e - kn)^d ≡ m (mod n)
分解下左边公式
(m^e - kn)^d = m^ed + [(m^e)^d-1]*kn + [(m^e)^d-2]*kn^2 + ....
除了第一个m^ed,后面的数都含有XXX*kn,所以都能被n整除

 

受益匪浅

大哥,那个模反元素有问题
一说:
a* a的[φ(n)-1] % n = 1
二说:
a* a的[φ(n)-1] % φ(n) = 1
明显不一样了丫、。。。。

这步mφ(n) ≡ 1 (mod n)

(mφ(n))h × m ≡ m (mod n)
实在看不懂,能否详细解释下?

引用shindo的发言:

这步mφ(n) ≡ 1 (mod n)

(mφ(n))h × m ≡ m (mod n)
实在看不懂,能否详细解释下?

我懂了, mφ(n) ≡ 1 (mod n) => mφ(n) = K n +1 , k为自然数
(kn + 1)^h 展开多项式,除了1以外,全部含有kn, 所以其他项都能被n整除而余1..
也就是能推出 (mφ(n))h ≡ 1 (mod n)
然后m 这个中间数学gap还是挺大的...

调理清晰,把一个复杂难懂的数学问题,一步一步分解,深入浅出,容易理解,学习了!

文章超赞……
要是你能加上怎么快速生成的方法,相信对读者更有帮助,因为我找到这篇文章是因为我想快速生成公钥私钥来用,而我又是刚接触linux:
ssh-keygen -t rsa

RSA加密解密算法中,已知公钥和密匙n,e,d,是否能将合数n=p*q分解?

先温故一下RSA算法:
1、两个大质数p,q。
2、模数n=p*q。
3、欧拉函数f=(p-1)(q-1)。
4、随机数e,1 5、模逆d,即最小整数d,e*d=1 mod f。
也就是说:
知道了p,q也就知道了n,f;
知道了f,e也就知道了d。

下面温故一下加密解密算法:
已知明文m,满足m 加密:密文c=m^e mod n。
解密:明文x=c^d mod n。

证明一下解密得到的明文x=m:
由c=m^e mod n,得c=m^e+k*n。
代入x=c^d mod n,得x=(m^e+k*n)^d mod n。
于是x=m^e^d mod n,即x=m^(e*d) mod n。
由于e^d=1 mod f,得e*d=k*f+1。
代入得x=m^(kf+1) mod n,x=m*m^(kf) mod n。
当m与n互质时,x=m*(m^f)^k mod n,由欧拉定理可知x=m mod n。
又m 当m与n不互质时,由于n=p*q且m 若m=kp,则m^(q-1)=(k*p)^(q-1)=1 mod q。
接着[(k*p)^(q-1)]^[k*(p-1)]*kp=kp mod q,即(k*p)^(e*d)=k*p mod q。
又由于(k*p)^(ed)=k*q+k*p,(k*p)^(ed)=k*q*p+k*p,。
所以m^(ed)=m mod n,x=m。
即证。

现在考虑以下问题:
已知n和d,是否能将n分解?
可将这个问题分为几个问题:
1、已知n和f,是否能将n分解?
2、已知n,e和d,是否能得到f?
3、已知n和d,是否能得到e?
4、已知d和f,是否能得到e?
对于问题1的回答是肯定的。
n-f+1=sum=p+q,用二分法厉遍p,得p(sum-p)和n比较大小,即可快速确定p,q的值。
所以知道了n,f,就知道了p和q。也就是说,p,q,n,f四个数知道任意两个就可以知道全部。
那么,问题2就来了。如果p,q,n,f只知其一,又知道了e和d,是否能知道其它三个数呢?
最常见的情况就是知道了n,e和d。
由e*d=1 mod f,知e*d=k*f+1。
根据的同余方程定理可以知道存在k 并且d,k始终互质,由e,f互质又可推出e,k互质和f,d互质。
现在的问题又变为,e,d,f三个数各知道两个,能否知道第三个数?在已知n的情况下又是如何呢?
已知e,f可知道d,已知e,d不可知道f。
已知d,f,因为d,f互质,所以模逆e必存在,e必然在f的同余类中。又e 也就是说,e,f求d和d,f求e的过程是相同的。
这样,问题4的回答就是肯定的。
我们还可以发现,问题3的回答是否定的。
e和d对于f的地位是等价的,我们显然不可能用公匙n,e得到密匙n,d,所以反之亦然。
于是我们发现,f是十分重要的。知道了f,那么e和d就能互求。知道了f,那么n,p,q就能互求。
最后我们回到问题2。由于n,p,q的地位是等价的,我们可以换个死路考虑。
在已知p,e,d的情况下能否知道f和n?由e*d=k*f+1可以算出k*f。
然后又知道了p,可以算出k*(p-1)(q-1)/(p-1)=k*(q-1)。
然而这样组合的数量是很多的,如果不知打k,我们不可能知道q。所以知道p,e,d不能知道f或n。
那么知道n,e,d,也就是知道n和k*f,也就是知道p*q和k(p-1)(q-1)的情况下呢?
由于k是不可知的,k值的不同会导致f产生很大的变化。
我们虽然知道上限n,但直接拿f去除以n显然不能得到正确的k。
由于p和q的差值可能很大也可能很小,所以除出来的结果可能十分接近k也可能和k差很多。
于是无法缩小搜索p和q的范围,也无从使用二分法。
所以我认为,已知n,e,d是无法得到f的,同样也无法得到p和q。

如果大家有办法分解n的话,求详细的算法。

正在查rsa的资料,又回到了这里,想自己实现一个简易的rsa。

引用Leon的发言:

两边同时整除p,又p、q互质,于是t必定是p的整数倍。


这种解释说法就是“鸡生蛋,蛋生鸡”问题,拿着要证明的结果作为证明的已知条件来证明问题!!!

第一次看懂了rsa算法, 真是好文章

引用shindo的发言:

我懂了, mφ(n) ≡ 1 (mod n) => mφ(n) = K n +1 , k为自然数
(kn + 1)^h 展开多项式,除了1以外,全部含有kn, 所以其他项都能被n整除而余1..
也就是能推出 (mφ(n))h ≡ 1 (mod n)
然后m
这个中间数学gap还是挺大的...


去看数论中同余性质吧,

性质5:若a≡b(mod m),c≡d(mod m),那么ac≡bd(mod m)(可乘性)。
性质6:若a≡b(mod m),那么an≡bn(mod m)(其中n为自然数)。

可以看成是
由h个式子相乘,然后再与m≡m(mod n)相乘,这里m 得到。。。

引用asdf的发言:

[(kp)q-1]h(p-1) × kp ≡ kp (mod q)
可以直接一步得到结论了,何必之后那几步推导?

对头,到这就可以截止了,况且后面证明的很乱

好像和CLRS算法差不多,但是各有各的特点及其长处.

突然发现,双方的公钥和私钥对换,还是能够顺利加密和解密的。

以 m = kp为例,考虑到这时k与q必然互质。

这句话不对吧,比如说m=3n=3qp不行吗,那么k=3q,哪来必然互质?应该再细分

引用NeroLee的发言:

以 m = kp为例,考虑到这时k与q必然互质。

这句话不对吧,比如说m=3n=3qp不行吗,那么k=3q,哪来必然互质?应该再细分

根据RSA规范,要加密的信息m,范围为0~n-1,所以你说的不成立。

5.1.1 RSAEP
RSAEP ((n, e), m)
Input: (n, e) RSA public key
m message representative, an integer between 0 and n– 1
Output: c ciphertext representative, an integer between 0 and n– 1

引用zoudaokou2006的发言:

根据RSA规范,要加密的信息m,范围为0~n-1,所以你说的不成立。

5.1.1RSAEP
RSAEP ((n, e), m)
Input: (n, e) RSA public key
m message representative, an integer between 0 and n– 1
Output: c ciphertext representative, an integer between 0 and n– 1

Thanks. 现在懂了。

我看到了未来的密钥是1mb起码。。。。。。

65^17 ≡ c (mod 3233)
说等于
65^17 ≡ 2790 (mod 3233)
即c等于2790
想请问下,这里的2790是怎么算出来的??

引用t.k.的发言:

九的子标题(2)m与n不是互质关系中

应该是“m与q必然互质”。

另外,数学公式用mathjax会更好看一些。

“m与q必然互质”没错,因为m=kq

65^17 ≡ c (mod 3233)
说等于
65^17 ≡ 2790 (mod 3233)
即c等于2790
想请问下,这里的2790是怎么算出来的??
我指的是口算或者笔算 不是利用计算机算65的17次方除以3233
有没有简单算法 如果笔算65的17次方 会死人的。。。

一口气看完两篇, 果然精彩

k与q必然互质
卡在这里了

你好,请教一下:像12306这样的网站,在使用时要下载他的证书并导入,这时下载的证书是证书请求文件CSR吗?还是已经经过签名的公钥了?

终于搞懂了,非常感谢!

刚接触RSA时看过其他网上的微博,要么是粘贴过来的,要么是片面不详细。今天看了阮先生描写的原理,顿时醍醐灌顶,把我所有没有搞懂的、有疑问的统统说清楚了,特别是数论原理,推导的过程描述的很详细。还结合实际中的密钥的长度、实际当中的数值,这些是刚接触加密算法的时候都有的疑问,这两篇文章都描写的非常详细,真的受益匪浅,而且特别欣赏这种写作风格,严谨、有据。真的谢谢

博主写的文章让人涨知识!

这是我见过的最通俗易懂的解释!!

谢谢lz。
但有个问题,“如果私钥被攻破,那么消息就会被破解”。这里是不是隐含了解密算法或者是加密算法,可以认为是公开的了,至少是容易获得的。
如果是这样,为什么不能从加密算法和已知的公钥已经加密后的信息,反推出原始信息呢?

您好,我看了网易公开课中的现代密码学,再看了您的文章感觉清晰很多,但有一点一直不大懂,求d时用到“拓展欧几里得算法”具体应该怎么算?
我对这方面很有兴趣,高中数学竞赛也学过一些数论知识(现在大一),但受专业限制接触不到这方面知识,打算通过网易公开课自学,纯粹出于兴趣。希望有机会与您多交流学习。

引用傅琦佳的发言:

您好,我看了网易公开课中的现代密码学,再看了您的文章感觉清晰很多,但有一点一直不大懂,求d时用到“拓展欧几里得算法”具体应该怎么算?
我对这方面很有兴趣,高中数学竞赛也学过一些数论知识(现在大一),但受专业限制接触不到这方面知识,打算通过网易公开课自学,纯粹出于兴趣。希望有机会与您多交流学习。

百度百科里关于扩展欧几里得算法有讲具体怎么做。

豁然开朗,十分感谢

有一个疑问,就是在加密的时候 用的这个式子:m的e次方 ≡ c (mod n) 来计算出的c ,然后之后是把c给了爱丽丝让爱丽丝拿私钥去解m,我想问的是这时候知道c,可不可以还用之前那个得出c的式子: m的e次方 ≡ c (mod n) 再反过去解出m,因为这时候n,c,e都已知。m就等于 c (mod n)再开e次方了。 大神快粗来,急,在线等~~

第二次看了,还是没看太懂。下次继续学习。谢谢阮老师

65^17 ≡ 2790 (mod 3233) 这个式子成立吗?

2790 mod 3233 = 2790

65^17 mod 3233 = 887 (matlab得到的结果)

另外 2790^2753 ≡ 65 (mod 3233) 这个式子中的 2790^2753 这个值,计算机可以算出来吗?

谢谢

还是有个疑问:
alice 回信的时候,咋整?

bob发信: bob(公钥加密) -> alice (私钥解密),这个逻辑我明白

alice 回信, 这个怎么处理?求解!!

引用luke的发言:


想通了。
(m^e - kn)^d 等同于 m^(ed)-kn

而 (m^e - kn)^d ≡ m (mod n)

意味着,(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 (mod n)

把(m^e - kn)^d 完全展开后只有一项不包含n的项 m^ed m^ed对n取余就等于 (m^e - kn)^d 对n取余

引用Codisan的发言:

还是有个疑问:
alice 回信的时候,咋整?

bob发信: bob(公钥加密) -> alice (私钥解密),这个逻辑我明白

alice 回信, 这个怎么处理?求解!!


bob给alice发信,用的是Alice的公钥,Alice用自己的私钥解密;如果Alice要给bob回信,就换成bob的公钥加密,bob用自己的私钥解密。

怒赞!!!!

引用王军的发言:

65^17 ≡ c (mod 3233)
说等于
65^17 ≡ 2790 (mod 3233)
即c等于2790
想请问下,这里的2790是怎么算出来的??
我指的是口算或者笔算不是利用计算机算65的17次方除以3233
有没有简单算法 如果笔算65的17次方 会死人的。。。

模幂法:
依次计算65^2 mod 3233, 65^4 mod 3233, 65^8 mod 3233, 65^16 mod 3233,最后再将65^16 mod 3233的结果和65相乘再mod 3233,这样可以保证最多只要做2*log3(n)次大数乘法和大数取模运算就可以得出结果了。

感谢博主,虽然对数学的还没有完全搞懂,但是基本上能浅显理解RSA的理论基础了,感谢感谢。

阮先生好,我在看的时候也会有@袁宇阳 的问题,可以直接拿公钥和加密后的数据反推出加密之前的数据吗?

"以 m = kp为例,考虑到这时k与q必然互质,则根据欧拉定理,下面的式子成立:"

这一句疑似应为

"考虑到这时kp与q必然互质"

引用王军的发言:

65^17 ≡ c (mod 3233)
说等于
65^17 ≡ 2790 (mod 3233)
即c等于2790
想请问下,这里的2790是怎么算出来的??
我指的是口算或者笔算不是利用计算机算65的17次方除以3233
有没有简单算法 如果笔算65的17次方 会死人的。。。

请自行百度快速幂取模算法,这是CS算法中一个比较基本的算法。

太棒!!!!逻辑清晰,描述清楚!感谢博主!真的是三言两语我完全看懂了!还有当时一直就在想能不能由n反推私钥的问题,还有私钥一定能解的证明,真是好感谢!
教材和老师巴拉了一堆我什么都不知道

以 m = kp为例,考虑到这时k与q必然互质这块为什么??

如果事先能找到的目前发现的质数数据集,进行计算出数据库,这样的数据库会有多大。

引用nkAmerica的发言:
根本没有协商过程啊。都是用对方的公钥加密


你的意思是在我们生成的密钥对里,并将公钥给了鲍勃,然后鲍勃也将自己生成的密钥对里的公钥给了爱丽丝?
但我们在用 SSH-KEYGEN生成密钥对时,给了鲍勃公钥,鲍勃是怎么将自己的密钥对里的公钥给爱丽丝的?

文章很好,学到了,真心感谢,但里面一些图片显示不出来,是否是来源网站被墙的问题呢?

引用我谁也不是的发言:


bob给alice发信,用的是Alice的公钥,Alice用自己的私钥解密;如果Alice要给bob回信,就换成bob的公钥加密,bob用自己的私钥解密。

如果ALice用自己的私钥加密给Bob回信,bob可以用ALice的公钥来解密么?

博主高人也!

引用zz的发言:

第四步计算模反元素下面这俩式子貌似符号弄错了~

ex + φ(n)y = 1
已知 e=17, φ(n)=3120,
  17x + 3120y = 1


应为: 17x-3120y=1

引用zzzp的发言:


应为: 17x-3120y=1




d=2753 k=15.

引用zzzp的发言:



d=2753 k=15.

y = -k
两项相加的话好像才可以满足扩展欧几里德算法的要求 ax+by = gcd(a, b)

引用scateu的发言:

"以 m = kp为例,考虑到这时k与q必然互质,则根据欧拉定理,下面的式子成立:"

这一句疑似应为

"考虑到这时kp与q必然互质"

k与q必然互质,

原因是m小于n,m取整数,所以m必然为kp或是kq

同时得到m为kp(k小于q),n为kq(k小于p)

取m为kp,由于q是质数,k小于q,k与q互质

我的理解

阮老师,你看云文档有处公式写错了:使用公钥加密的公式.

有个问题:
  因为决定是否能够破解的关键在分解n=p×q,而您提到目前最大的是破解到768位,是否意味着768位(包括768)位以下RSA加密的都已经是不安全的了?

看懂了原理,数论知识也看懂了大概,不过博主真牛!

引用Caleb的发言:

65^17 ≡ 2790 (mod 3233) 这个式子成立吗?

2790 mod 3233 = 2790

65^17 mod 3233 = 887 (matlab得到的结果)

另外 2790^2753 ≡ 65 (mod 3233) 这个式子中的 2790^2753 这个值,计算机可以算出来吗?

谢谢

我用python算 65^17 mod 3233 = 2790 你matlab用错了吧
2790^2753 这个值计算机当然算的出来,python算了一下,结果占了我半个屏幕。。。

这个不对称算法绝对是有漏洞的!根据已知e17和n模3233可以算得d=1193 虽然我不知道真的d为3233但是可以等效算出加密值!其实这个基于的是素数的耦合!既自然数的n次幂mod一个素数=自然数本身 而求出那个幕与素数的关系的这个数学推论我感觉可以写个猜想

好文章,感谢。

引用colde的发言:

证明
  (m^e - kn)^d ≡ m (mod n)
等同于证明
 m^ed ≡ m (mod n)

卡住在这里了,麻烦帮忙解释一下。

你可以把 (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不互质的前提条件。

(me - kn)d ≡ m (mod n) 它等同于求证 med ≡ m (mod n)
有大神可以解释一下吗?

哦,我看到了

引用samaritan的发言:

如果事先能找到的目前发现的质数数据集,进行计算出数据库,这样的数据库会有多大。


你可以百度一下《100万以内的质数》这篇文档,word文档有几十页。而100万大约是20位左右的样子。自行想象1024位的质数有多少个。大概会是那篇文档的2^1000倍

我要发表看法

«-必填

«-必填,不公开

«-我信任你,不会填写广告链接