首页
论坛
课程
招聘
[原创]公钥密码RSA算法优化分析
2009-5-21 10:44 12653

[原创]公钥密码RSA算法优化分析

2009-5-21 10:44
12653
摘要: 本文首先对RSA公钥密码体制基本思想计算方法进行阐述,并举例说明其算法过程。详细介绍对快速指数算法的研究、改进方法。最后详细介绍孙子剩余定理。
This paper first elaborates the principle of RSA algorithm and the implementation process. Fast exponential algorithm which the author improves for promoting the efficiency of RSA is introduced. Finally, the paper explains the Chinese remainder theorem.
关键词:RSA、快速指数算法、孙子剩余定理

因为论文里面有很多数学符号,无法复制出来,故只把摘要展示,具体论文可以下载附件查看

/*-------------------------------------------------------------------------
* 版权所有:jxccy,引用请注明出处
* 作者:jxccy
* QQ:524733264
* 完成时间: 2008年4月
-------------------------------------------------------------------------*/

[2022冬季班]《安卓高级研修班(网课)》月薪三万班招生中~

上传的附件:
收藏
点赞0
打赏
分享
最新回复 (14)
雪    币: 265
活跃值: 活跃值 (44)
能力值: ( LV13,RANK:350 )
在线值:
发帖
回帖
粉丝
moonife 活跃值 8 2009-5-21 12:54
2
0
学习了 以后不懂的向你请教了 嘿嘿
雪    币: 269
活跃值: 活跃值 (10)
能力值: ( LV5,RANK:60 )
在线值:
发帖
回帖
粉丝
jxccy 活跃值 1 2009-5-21 13:11
3
0
共同学习,一起提高,呵呵!
雪    币: 1806
活跃值: 活跃值 (39)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
rockinuk 活跃值 8 2009-5-21 15:11
4
0
請教...jxccy 大大...
在解密階段, (5) 及 (6)
當解密者不知道 p 及 q 時,
他/她怎麼去 mod p 或是  mod q ?
雪    币: 269
活跃值: 活跃值 (10)
能力值: ( LV5,RANK:60 )
在线值:
发帖
回帖
粉丝
jxccy 活跃值 1 2009-5-21 17:50
5
0
p和q是我们在加密过程中随机选取的大素数,它是保密的,然后在选取一个加密密钥e,加密者通 过这几个数字可以得到一个解密密钥,发送给解密者。
在整个过程中,对于加密者把信息发给接收信息的人,接收信息的人只会得到一个密文,解密密钥和一个(p*q)的结果n,然后接收者再通过得到的信息进行解密。

R大可能是想破解RSA加密,对于我们来说我们是不可能知道解密密钥,p和q当然也不可能知道,我们只会知道n和密文,而想破解的关键其实也就是想得到p和q,这样才能计算得到解密密钥。这就得看我们想办法如何把n分解出两个大素数相乘了,这个是比较难的,如果容易破解的话,那么RSA也就没什么价值了,这就是为什么破解别人加密后的东西难的原因了.
雪    币: 1806
活跃值: 活跃值 (39)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
rockinuk 活跃值 8 2009-5-26 16:38
6
0
To jxccy 大大,
因為在您的【公钥密码RSA算法优化分析】 的 page 4 ,【4.1 孙子定理优化算法分析】裏,有用到~
=====
=   mod q      (3)
可由剩余定理得  = (  pq/p +   pq/q) mod pq
= (x1y1 q + x2y2p) mod n = x mod n        (4)
其中  =  mod p                (5)
  =  mod q               (6)
=====
在解密時,沒人知道 p ,q 自然就無法用 mod p 或  mod q 來運算。
不是嗎?

我的疑問是,不知道 p 及 q ,怎麼去 mod p 及 mod q 呢!?
這是我不理解的地方。
不是對孫子算法(CRT)不理解。
雪    币: 392
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
nicetom 活跃值 2009-5-27 10:03
7
0
关注中,期待 jxccy 大大的回复
雪    币: 269
活跃值: 活跃值 (10)
能力值: ( LV5,RANK:60 )
在线值:
发帖
回帖
粉丝
jxccy 活跃值 1 2009-5-27 12:55
8
0
最近有点忙碌,这几天在外面不能上网了,过几天回来后将会回复!
雪    币: 11
活跃值: 活跃值 (49)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
ywqjwq 活跃值 2009-5-28 14:09
9
0
貌似很高深啊 我顶之~~也学习了~
雪    币: 45969
活跃值: 活跃值 (168323)
能力值: (RANK:10 )
在线值:
发帖
回帖
粉丝
linhanshi 活跃值 2009-5-28 14:45
10
0
Thanks for share.
雪    币: 269
活跃值: 活跃值 (10)
能力值: ( LV5,RANK:60 )
在线值:
发帖
回帖
粉丝
jxccy 活跃值 1 2009-6-2 10:34
11
0
正如rockinuk大大说的一样,我们在解密过程中不知道p和q,怎么能够mod p, mod q ,确实是没有办法的。所以这个孙子定理优化算法只有在知道p和q的前提下才能用。也就是说私有密钥(d,n)用(d,P,q)代替,接收者必须知道p和q才行,这样其实在使用过程中将会带来很大的安全隐患。
    所以在使用孙子定理优化算法必须小心谨慎,当你数据要求安全性不是太高的时候可以使用,如果安全性要求很高,这个算法最好是不要用。
    这个其实也是给大家一个思路,共同探讨,一个东西在使用的过程中利弊都会有,主要是看我们什么时候去用。
雪    币: 1806
活跃值: 活跃值 (39)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
rockinuk 活跃值 8 2009-6-2 18:30
12
0
謝謝解說,現在有一點瞭解。
其實,在使用「孙子定理优化算法」時, modulo n 也不能重複。
雪    币: 1225
活跃值: 活跃值 (35)
能力值: (RANK:680 )
在线值:
发帖
回帖
粉丝
jackozoo 活跃值 14 2009-6-3 18:56
13
0
感谢LZ分享.
雪    币: 200
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
hsa 活跃值 2011-6-30 19:00
14
0
准备学习中!!!
雪    币: 56
活跃值: 活跃值 (12)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
publickey 活跃值 2011-7-5 11:34
15
0
两个问题:
1、快速指数优化方法中,从指数低位遍历的算法正确吗?应该从指数高位遍历。
2、显然CRT是不需要使用N的,你推理的CRT还不完全。

目前关于模幂的优化算法通常是Montgomery乘法加上NF编码,基本都是成熟结论。
游客
登录 | 注册 方可回帖
返回