首页
社区
课程
招聘
[求助]rsa算法疑问
发表于: 2011-6-24 06:21 9227

[求助]rsa算法疑问

2011-6-24 06:21
9227
在 google code 里搜到一代码
http://www.google.com/codesearch/p?hl=zh-CN#cZwlSNS7aEw/bootable/recovery/verifier_test.c&q=0xc926ad21&type=cs

RSAPublicKey test_key =
    { 64, 0xc926ad21,
      { 1795090719, 2141396315, 950055447, -1713398866,
        -26044131, 1920809988, 546586521, -795969498,
        1776797858, -554906482, 1805317999, 1429410244,
        129622599, 1422441418, 1783893377, 1222374759,
        -1731647369, 323993566, 28517732, 609753416,
        1826472888, 215237850, -33324596, -245884705,
        -1066504894, 774857746, 154822455, -1797768399,
        -1536767878, -1275951968, -1500189652, 87251430,
        -1760039318, 120774784, 571297800, -599067824,
        -1815042109, -483341846, -893134306, -1900097649,
        -1027721089, 950095497, 555058928, 414729973,
        1136544882, -1250377212, 465547824, -236820568,
        -1563171242, 1689838846, -404210357, 1048029507,
        895090649, 247140249, 178744550, -747082073,
        -1129788053, 109881576, -350362881, 1044303212,
        -522594267, -1309816990, -557446364, -695002876},
      { -857949815, -510492167, -1494742324, -1208744608,
        251333580, 2131931323, 512774938, 325948880,
        -1637480859, 2102694287, -474399070, 792812816,
        1026422502, 2053275343, -1494078096, -1181380486,
        165549746, -21447327, -229719404, 1902789247,
        772932719, -353118870, -642223187, 216871947,
        -1130566647, 1942378755, -298201445, 1055777370,
        964047799, 629391717, -2062222979, -384408304,
        191868569, -1536083459, -612150544, -1297252564,
        -1592438046, -724266841, -518093464, -370899750,
        -739277751, -1536141862, 1323144535, 61311905,
        1997411085, 376844204, 213777604, -217643712,
        9135381, 1625809335, -1490225159, -1342673351,
        1117190829, -57654514, 1825108855, -1281819325,
        1111251351, -1726129724, 1684324211, -1773988491,
        367251975, 810756730, -1941182952, 1175080310 }
    };

typedef struct RSAPublicKey {
    int len;                  /* Length of n[] in number of uint32_t */
    uint32_t n0inv;           /* -1 / n[0] mod 2^32 */
    uint32_t n[RSANUMWORDS];  /* modulus as little endian array */
    uint32_t rr[RSANUMWORDS]; /* R^2 as little endian array */
} RSAPublicKey;

下面这句什么意思,咋根我的理解不一样
uint32_t n0inv;           /* -1 / n[0] mod 2^32 */
我的理解是n[0]n[0]' - 2^32*k = 1
用上面的数值代进去却是n[0]n[0]'  + 1 =  2^32*k
-1 / n[0] mod 2^32
这句的意思是不是N[0]对2^32求模逆呀?

谢谢!可能我还没真懂其中的意思吧……哎!

[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

收藏
免费 0
支持
分享
最新回复 (13)
雪    币: 768
活跃值: (530)
能力值: ( LV13,RANK:460 )
在线值:
发帖
回帖
粉丝
2
来点基础的:)
参考:http://bbs.pediy.com/showthread.php?t=101391
RSA的算法涉及三个参数,n、e、d。
    其中,n是两个大质数p、q的积。n的二进制表示时所占用的位数,就是所谓的密钥长度。
    e和d是一对相关的值,e可以任意取,但要求满足e<(p-1)*(q-1)并具 e与(p-1)*(q-1)互质(就是最大公约数为1);
  再选择d,要求(d*e)mod((p-1)*(q-1))=1。
    (n及e),(n及d)就是密钥对。
    RSA加解密的算法完全相同,设M为明文,c为密文,则:
       加密:C=M^e mod n;
       解密:m=c^d mod n;
    注:上面两式中的e和d可以互换。  
      n d两个数构成公钥,可以告诉别人;
      n e两个数构成私钥,e自己保留,不让任何人知道。
2011-6-24 07:47
0
雪    币: 206
活跃值: (53)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
3
谢谢 ……!原理我是看了,但还是一知半解……哎!
2011-6-24 08:58
0
雪    币: 193
活跃值: (64)
能力值: ( LV3,RANK:30 )
在线值:
发帖
回帖
粉丝
4
rsa位数多的想也别想!很难跑出来!
2011-6-24 09:05
0
雪    币: 206
活跃值: (53)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
5
n d两个数构成公钥,可以告诉别人;
      n e两个数构成私钥,e自己保留,不让任何人知道。
2011-6-24 09:06
0
雪    币: 206
活跃值: (53)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
6
谁帮我看看上面的那个NOINV是咋算出来的……谢谢
2011-6-24 09:11
0
雪    币: 443
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
7
你似乎没注意那个负号

uint32_t n0inv;           /* -1 / n[0] mod 2^32 */

n0inv = -1/n[0] (mod 2^32)
n0inv*n[0] = -1/n[0] (mod 2^32)
n0inv*n[0] + 1 = 0 (mod 2^32)
即 n0inv*n[0] + 1 = 2^32 * k
2011-6-24 10:06
0
雪    币: 2015
活跃值: (902)
能力值: ( LV12,RANK:1000 )
在线值:
发帖
回帖
粉丝
8
inv不是逆元的意思吗?这里貌似代表负的逆元,e应该是公开的,d通常是私钥,rsa其实就是大指数的模幂运算,计算量很大,适合用来加密对称加密过程中使用的通用密钥。
2011-6-24 11:07
0
雪    币: 206
活跃值: (53)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
9
[QUOTE=njreds;973088]你似乎没注意那个负号

uint32_t n0inv;           /* -1 / n[0] mod 2^32 */

n0inv = -1/n[0] (mod 2^32)
n0inv*n[0] = -1/n[0] (mod 2^32)
n0inv*n[0] + 1 = 0 (m...[/QUOTE]

谢谢~明白了……
2011-6-24 11:22
0
雪    币: 206
活跃值: (53)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
10
[QUOTE=njreds;973088]你似乎没注意那个负号

uint32_t n0inv;           /* -1 / n[0] mod 2^32 */

n0inv = -1/n[0] (mod 2^32)
n0inv*n[0] = -1/n[0] (mod 2^32)
n0inv*n[0] + 1 = 0 (m...[/QUOTE]

那这样的意思是什么样 n[0]对2^32求负模逆?
2011-6-24 11:30
0
雪    币: 62
活跃值: (27)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
11
n0inv是用来为模幂运算加速的一个常数,显然是使用了Montgomery乘法。
使用Montgomery乘法需要用到-n[0]^(-1)。
不要用数去理解,用剩余类理解。
不要用普通乘法、除法去理解,用群运算理解。
2011-6-25 18:29
0
雪    币: 62
活跃值: (27)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
12
去找找我之前在论坛上写的Montgomery乘法的文章吧,也许对你有用。
2011-6-25 18:34
0
雪    币: 67
活跃值: (30)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
13
http://en.wikipedia.org/wiki/Montgomery_reduction
Montgomery reduction
2011-6-26 14:57
0
雪    币: 62
活跃值: (27)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
14
注意以下过程即可得出简便快速的计算方法:
若x*y=1 + 2^k,则x*y-2 = 2^k -1,所以(x*y)*(x*y-2) = 2^(2k) - 1,即y*(x*y -2)为x的模2^(2k)的负逆元。
也即是说,知道了一个数模2^k的乘法逆元,使用上述2次乘法即可得出其模2^(2k)的乘法逆元。所以,只需要一组互为逆元的数,多次迭代,即可快速计算出更高位的互为逆元的数。
2011-6-27 13:27
0
游客
登录 | 注册 方可回帖
返回
//