给我留言 | 加入收藏 | 设为首页 | 会员中心 | 我要投稿 | RSS
| PHP | ASP | JAVA | .NET | FLASH | AJAX | MYSQL | PGSQL | MSSQL | DB2 | ORACLE | SYBASE | Html/Css | 服务器相关 | IOS |
您当前的位置:首页 > WEb开发 > 服务器相关

3个著名加密算法(MD5、RSA、DES)的解析

时间:2016-12-07 15:28:01  来源:  作者:

若 p, q 是相异质数, rm == 1 mod (p-1)(q-1), 
a 是任意一个正整数, b == a^m mod pq, c == b^r mod pq, 
则 c == a mod pq 

证明的过程, 会用到费马小定理, 叙述如下: 
m 是任一质数, n 是任一整数, 则 n^m == n mod m 
(换另一句话说, 如果 n 和 m 互质, 则 n^(m-1) == 1 mod m) 
运用一些基本的群论的知识, 就可以很容易地证出费马小定理的........ 

<证明> 
因为 rm == 1 mod (p-1)(q-1), 所以 rm = k(p-1)(q-1) + 1, 其中 k 是整数 
因为在 modulo 中是 preserve 乘法的 
(x == y mod z and u == v mod z => xu == yv mod z), 
所以, c == b^r == (a^m)^r == a^(rm) == a^(k(p-1)(q-1)+1) mod pq 

1. 如果 a 不是 p 的倍数, 也不是 q 的倍数时, 
则 a^(p-1) == 1 mod p (费马小定理) => a^(k(p-1)(q-1)) == 1 mod p 
a^(q-1) == 1 mod q (费马小定理) => a^(k(p-1)(q-1)) == 1 mod q 
所以 p, q 均能整除 a^(k(p-1)(q-1)) - 1 => pq | a^(k(p-1)(q-1)) - 1 
即 a^(k(p-1)(q-1)) == 1 mod pq 
=> c == a^(k(p-1)(q-1)+1) == a mod pq 

2. 如果 a 是 p 的倍数, 但不是 q 的倍数时, 
则 a^(q-1) == 1 mod q (费马小定理) 
=> a^(k(p-1)(q-1)) == 1 mod q 
=> c == a^(k(p-1)(q-1)+1) == a mod q 
=> q | c - a 
因 p | a 
=> c == a^(k(p-1)(q-1)+1) == 0 mod p 
=> p | c - a 

来顶一下
返回首页
返回首页
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表
推荐资讯
相关文章
    无相关信息
栏目更新
栏目热门