证明RSA算法在明文和公私钥中N不互质情况下仍然成立
下文中的 k 代表自然数常数,不同句子,公式中不一定代表同一个数
之前接触RSA,没有过多的思考证明过程,今天有感而发,推到了一遍
假设公钥 (e, N) , 私钥 (d, N) ,那么 ed = k * g (N) + 1 , g是欧拉函数,假设 N = p * q ,p 和 q 都是 大素数, 那么 g (N) = ( p - 1 ) * ( q - 1 ) , k 是自然数
假设明文是 M , 那么 密文 C = M ^ e (mod N)
密文再次运算的结果是明文,即使明文 R = C ^ d ( mod N ) = ( M ^ e ) ^ d ( mod N ) = M ^ (ed) (mod N)
最后 明文 R = M ^ (ed) (mod N) = M ^ ( k * g(N) + 1 ) ( mod N )
要从 R 推出明文,就要证明 R 和 明文 M 模N 同余,也就是 R = k * N + M (k 为自然数)
很简单的一种情况是 明文 M 和 N 是互质的,因为根据欧拉定理 :
如果 下图的 a 和 n 互质,则有
如果 M 和 N 互质,则两边乘 M
M ^ ( k * g(N)) 1 (mod N ) =》 [ M ^ ( k * g(N)) ] * [ M ] = M ^ ( k * g(N) + 1 ) = R M ( mod N )
如果 M 和 N 不是互质,就比较难证明了
M 和 N 不互质,那么 M 和 N 必然有一个非1的公因子 , 假设为 g , 则 N = k1 * g , M = k2 * g (k1, k2 均是常数)
两个素数相乘的积,只有四个因子,分别是 两个乘起来的素数,1,还有积本身。
那么 g 就应该是 这四个因子中的一个,前提已经假设 g 非1,那么 g 可能是剩下三个中的一个。
但是根据 RSA 规范:
5.1.1RSAEP
RSAEP ((n, e), m)
Input: (n, e) RSA public key
m message representative, an integer between 0 and n– 1
Output: c ciphertext representative, an integer between 0 and n– 1
M 应该小于 N,那么 g 就不能取 N,否则 M = k * g = k * N > N
在当前上下文,N = p * q , p 和 q 就是 那两个大素数, N 就是乘积,那么 g 就应该是 p 或 q ,可以推出 M = k0 * g = k * q 或者 M = k * p (k0,k 是自然数)
(g是M和N的非1公因子,所以可以写成 M = k0 * g 的形式)
因为 M < N , 假如 M = k * p , 那么 k = M / p < N / p = q ,也即 k < q ,那么 k 必然和 q 互质,因为 q 是素数 (原因见下图)。M = k * q 时同理
(k 和 q) 与 p 都互质,则有 k * q 与 p 互质。(因为 q 是素数,那么 k * q 分解的话只能分解出 k 和 q,必然没有 p 的因子,下同理)
或者 (k 和 p) 与 q 都互质,则有 k * p 与 q 互质。
再用一次欧拉定理,下面假设 M = k * p
(k * p) ^ (g(q)) 1 (mod q)
因为 q 是素数,比 q 小的数都和 q 互质,所以有 q - 1 个数 和 q 互质,也就是 q 的欧拉函数运算结果 g (q) = q - 1
也就是:
(k * p) ^ (q - 1) 1 (mod q)
下面还要用到一个推到:
假如 A 1 (mod q) (公式1),那么 ( A ) ^ h 1 (mod q) (公式2)
推到: 由公式1得到 A = k * q + 1 , 将 A 代入公式2, ( k * q + 1 ) ^ h 在展开后,只有最后一项是1,不带 k * q,其他都带 k * q , 所以 A^h = ( k * q + 1 ) ^ h 在 mod q 之后还是等于1
所以公式2成立
把 A 换成 (k * p) ^ (q - 1) , h 换成 k0 * (p - 1)
(k * p) ^ (q - 1) 1 (mod q)
可以转化成
[ ( k * p ) ^ ( q - 1) ] ^ ( k0 * ( p - 1 )) 1 (mod q)
[ ( k * p ) ] ^ [ k0 * ( q - 1) * ( p - 1 )] 1 (mod q)
根据 ed = i * g(N) + 1 = i * (p - 1) * (q - 1) + 1
[ ( k * p ) ] ^ (ed - 1) 1 (mod q)
两边同乘 k * p
[ ( k * p ) ] ^ (ed) (k * p) (mod q)
可以写成:
[ ( k * p ) ] ^ (ed) = (k * p) + k1 * q (k1 是自然数常数)
那么
[ ( k ) ^ (ed) ] * [ p ^ (ed ) ] = (k * p) + k1 * q
[ ( k ) ^ (ed) ] * [ p ^ (ed ) ] - k * p = k1 * q
[ [ (k) ^ (ed) ] * [ p ^ (ed - 1) ] - k ] * p = k1 * q
左边是 p 的倍数,右边应该也是 p 的倍数,又 p 和 q 互质,那么只能 k1 是 p 的倍数
回到之前的公式,把 k1 = k2 * p 代入
[ ( k * p ) ] ^ (ed) = (k * p) + k1 * q =》 [ ( k * p ) ] ^ (ed) = (k * p) + k2 * p * q
因为 N = p * q,继续代入
[ ( k * p ) ] ^ (ed) = (k * p) + k2 * N
[ ( k * p ) ] ^ (ed) ( mod N ) = [(k * p) + k2 * N ] (mod N) = (k * p) (mod N)
M = k * p 也就是
M ^ (ed) (Mod N) = M (mod N)
也就是 M ^ (ed) 和 M 模 N 同余
也即,R = M ^ (ed) 和 M 同余
证毕
最新文章
- Kafka vs RocketMQ—— Topic数量对单机性能的影响-转自阿里中间件
- Application.Run()和Form.Show()以及Form.ShowDialog()
- 并发编程 12—— 任务取消与关闭 之 shutdownNow 的局限性
- 【转】15个无比华丽的HTML5/CSS3动画应用
- 如何让我们的VMware虚拟机上网——转载
- XPath 元素及属性查找
- hibernate对象关系实现(三)多对多实现
- VI使用的小白教程
- 【BZOJ3262】 陌上花开
- Oracle ABP(Autotask Background Process)
- Python 基础 字符串拼接 + if while for循环
- js call方法
- 2017-12-19python全栈9期第四天第二节之列表的增删改查之切片
- HDU 1426(数独 DFS)
- 两个队列实现栈&;两个栈实现队列(JAVA)
- 【Python3练习题 017】 两个乒乓球队进行比赛,各出三人。甲队为a,b,c三人,乙队为x,y,z三人。已抽签决定比赛名单。有人向队员打听比赛的名单。a说他不和x比,c说他不和x,z比。请编程序找出三队赛手的名单。
- 小型网站使用高德地图开发定位模块需要的php代码
- RDMA技术解析
- 多校寒训TaoTao要吃鸡dp
- vs2017 C4996 错误