算法描述
随机选择两个大的素数 p、q ,且p ≠ q,计算n = pq、r = (p-1)(q-1),依欧拉定理,r即为与n互质的素数个数;选择一个小于r的整数e(即加密指数),求得e关于模r的逆元d(即解密指数),则{n,e}为公钥、{n,d}为私钥;根据模的逆元性质有ed ≡ 1 (mod r);设m为明文,则加密运算为m^e ≡ c (mod n), c即为密文;则解密过程 c^d ≡ m (mod n)。
证明会用到费马小定理,即
若y为素数且x不为y的倍数, 则 x^(y-1) ≡ 1 (mod y)(费马小定理的证明需先证明欧拉定理,此处略)。符号≡表示同余,^表示
幂,|表示整除,*表示相乘。
算法证明
第一种证明途径
因 ed ≡ 1 (mod (p-1)(q-1)),令 ed = k(p-1)(q-1) + 1,其中 k 是整数
则 c^d = (m^e)^d = m^(ed) = m^(k(p-1)(q-1)+1)
1.若m不是p的倍数,也不是q的倍数
则 m^(p-1) ≡ 1 (mod p) (
费马小定理)
=> m^(k(p-1)(q-1)) ≡ 1 (mod p)
m^(q-1) ≡ 1 (mod q) (
费马小定理)
=> m^(k(p-1)(q-1)) ≡ 1 (mod q)
故 p、q 均能整除 m^(k(p-1)(q-1)) - 1
=> pq | m^(k(p-1)(q-1)) - 1
即 m^(k(p-1)(q-1)) ≡ 1 (mod pq)
=> m^(k(p-1)(q-1)+1) ≡ m (mod n)
2.若m是p的倍数,但不是q的倍数
则 m^(q-1) ≡ 1 (mod q) (
费马小定理)
=> m^(k(p-1)(q-1)) ≡ 1 (mod q)
=> m^(k(p-1)(q-1)+1) ≡ m (mod q)
因 p | m
=> m^(k(p-1)(q-1)+1) ≡ 0 (mod p)
=> m^(k(p-1)(q-1)+1) ≡ m (mod p)
故 m^(k(p-1)(q-1)+1) ≡ m (mod pq)
即 m^(k(p-1)(q-1)+1) ≡ m (mod n)
3.若m是q的倍数,但不是p的倍数,证明同上
4.若m同为p和q的倍数时
则 pq | m
=> m^(k(p-1)(q-1)+1) ≡ 0 (mod pq)
=> m^(k(p-1)(q-1)+1) ≡ m (mod pq)
即 m^(k(p-1)(q-1)+1) ≡ m (mod n)
第二种证明途径
先证明m^ed ≡ m (mod p)恒成立
1.若p为m的因子,则p | m^ed - m显然成立,即m^ed ≡ m (mod p)
2.若p不为m的因子,令ed = k(p-1)(q-1) + 1,则 m^(ed-1) - 1 = m^(k(p-1)(q-1)) - 1
m^(p-1) ≡ 1 (mod p) (
费马小定理)
=> m^(k(p-1)) ≡ 1 (mod p)
=> m^(k(p-1)(q-1)) ≡ 1 (mod p)
=> m^(ed-1) ≡ 1 (mod p)
=> m^ed ≡ m (mod p)
同理可证m^ed ≡ m (mod q)
故m^ed ≡ m (mod pq),即m^ed ≡ m (mod n)
又因 c^d = m^e^d = m^(ed)
故 c^d ≡ m (mod n),证毕
总结
第二种比第一种简单直观,以上证明途径对RSA私钥签名与验签同样适合。
posted on 2016-11-18 17:05
春秋十二月 阅读(2621)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm