Chinaunix首页 | 论坛 | 博客
  • 博客访问: 15339603
  • 博文数量: 2005
  • 博客积分: 11986
  • 博客等级: 上将
  • 技术积分: 22535
  • 用 户 组: 普通用户
  • 注册时间: 2007-05-17 13:56
文章分类

全部博文(2005)

文章存档

2014年(2)

2013年(2)

2012年(16)

2011年(66)

2010年(368)

2009年(743)

2008年(491)

2007年(317)

分类:

2010-02-21 22:10:11

提问:
RSA 算法中的MOD运算疑问? 
《加密与解密》书中第207页RSA算法的私钥计算公式如下:
d=e的负1次方mod((p-1)(q-1))
而后举例选取e=17 p=37 ,q=41
d=17的负1次方mod1440=593

我的问题是:
1、不知道593是怎样得出来的?
2、17的负1次方是17分之1吗?是17的反码吗?
3、mod是什么运算呢?是求余吗?

回答:
mod是求余运算符。 
如果x与y的积除以z所得的余数为1,即xy = 1 (mod z),则称x和y对于模数z来说互为逆元,这种互为逆元的关系用符号表示为:
x         = y的-1次方   (mod z)
x的-1次方 = y           (mod z)

其中,-1次方只是个逆元的表示记号而已,是仿照以前的“倒数”的表示法,并非真的就是-1次方。

17 * 593 mod (37-1)(41-1) = 1
17 * 593 mod 1440 = 1

求逆元用扩展欧基里德算法,初等数论书都有讲。
========================
比如
(123456的17次)%(37*41)
%:mod运算,就是求余数,
如,5%3=2
7%6=1
m^n%(q*p)
其 中q,p是两个不相等的素数,一般使用的是时候都是选8位那么大的素数
常用的n有3、17、65537(2^16+1)……都是2的多少次+1
据 说这取这些数有简便方法,要是真直接算
1234^65537%(8503*9907)电脑非卡死不可,可是用人家给出的运算工具,非常快,我想知 道,有没有简便的方法。
8503*9907这两个素数取的已经是相当保守了
阅读(7681) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~