首页
论坛
专栏
课程

公钥私钥公式并非质数独有

2019-8-2 18:45 2703

公钥私钥公式并非质数独有

2019-8-2 18:45
2703
  最近研究RSA小质数加密,偶然发现非指数乘积也能算出符合加密解密公式的公钥和私钥。加密解密公式是:
密文 = 明文^公钥%模数 
明文 = 密文^公钥%模数
两个数101 和 221 前者是质数后者不是质数,221 = 17乘13,他们算出的数据:
公钥 = 12383  私钥 = 18047 模数 = 22321
设明文为 2 
2^12383%22321 = 19559 这是密文
19559^18047%22321 = 2 明文被还原了
又例
明文为127
127^12383%22321 = 7648 这是密文
7648^18047%22321 = 127 明文被还原了
这样的情况很多,并非特例。提请研究者注意。
  


[公告]安全服务和外包项目请将项目需求发到看雪企服平台:https://qifu.kanxue.com

打赏 + 1.00
打赏次数 1 金额 + 1.00
收起 
赞赏  mb_ovrzbwwl   +1.00 2019/08/07
最新回复 (5)
看场雪 3 2019-8-2 21:23
2
2
不错不错!
即使是玩RSA很多年的人,也未必知道这个细节。
事实上,不光是‘由多个素数构成的RSA’有这种现象,就连‘经典的由2个大素数构成的RSA’也有同样的问题。只是很少有人注意到而已。

一般认为,c=m^e(mod n), m'=c^d(mod n), 要想让m=m',就需要满足:ed=1(mod phi(n)), 其中phi是欧拉函数
但其实上述条件只是充分条件,而非必要条件。
在一定条件下,只要满足ed=1 (mod lcm(p-1,q-1))即可(假如n=p*q,且p、q为素数)

在LZ举的例子中,n=13*17*101,则phi=19200
但是lcm却只有1200
所以 并不需要ed=1(mod 19200),才能使得m=m'
而只需要ed=1(mod 1200)就够了

而LZ的例子中 12383*18047=7201 (mod 19200),貌似不满足RSA的经典生成私钥的公式
但是 12383*18047=1 (mod 1200)
因此加密解密是正确的。

同理,能够使得m=m'的解密密钥是不止一个的!
最后于 2019-8-3 08:31 被看场雪编辑 ,原因:
菜就一个字 2019-8-2 23:05
3
0
学习学习 感谢分享
Dstlemoner 2019-8-2 23:59
4
0
0.0 不管,直接调用,加密所有文件,给钱。
孤山散人 2019-8-6 22:46
5
0
非质数很容易被分解,从而反推出p,q。  密钥强度太低了。
两个大质数保证了密钥强度。
sjdkx 2019-8-7 00:48
6
0
确实如此,小质数也是如此,但是加密时每个字节都用不同的密钥,数量众多,您能破解吗?在帖子【RSA小质数加密】里面有文件加密程序,随便找点东西加密后破解试试,希望给予指导。
游客
登录 | 注册 方可回帖
返回