关于 RSA 算法的疑问
网上很多 RSA 的证明都是基于欧拉定理 m ^y(n) = 1 mod n
m ^(ky(n) + 1) = 1 ^k • m mod n = m
这里,有个前提是 m 和 n 互质啊, 这里 n =p•q
现实中,我们需要加密的消息千奇百怪,很有可能 m = p 或者 p 的倍数。
这样就不满足欧拉定理条件?
在 m = k *p 的情况下,如何证明呢
/***
p = 3
q = 5
n = 15
y(n) = (3-1) * (5-1) = 8
e = 3 pulic key
d = 3 private key
e * d = y(n) + 1 = 9 ;
***/
console.log('\tM \tEuler test \tRSA test ')
for (let msg = 0; msg < 15; msg++) {
var z = msg;
var z0 = msg;
z = (z * z) % 15;
z = (z * z) % 15;
z = (z * z) % 15;
var rsa = z * z0 % 15;
console.log(`\t ${msg} \t${z}${z==1 ? ' ' : ' x'} \t${rsa} `)
}
结果
M 欧拉测试(m^8==1) Rsa 测试(m^9=m)
0 0 x 0
1 1 1
2 1 2
3 6 x 3
4 1 4
5 10 x 5
6 6 x 6
7 1 7
8 1 8
9 6 x 9
10 10 x 10
11 1 11
12 6 x 12
13 1 13
14 1 14
竟然不支持表格
结果也是正常,消息 m 需要与 n 互质欧拉公式菜鸟成立,但是 RSA 确能正常加解密
1
Citrus 2021-08-02 19:07:44 +08:00
实践中处理明文需要分块的。
|
2
GM 2021-08-02 19:25:23 +08:00
RSA 加密的数据比特数小于秘钥的比特数
那么如果要加密的数据很长,超过 1024 比特怎么办? 答案是切成小块来加密,然后再拼在一起。解密的也一样,切块后解密。 |
3
GM 2021-08-02 19:27:11 +08:00
#2 楼修改一下:“超过 1024 比特怎么办” 改为 “超过秘钥比特数怎么办”
|
4
GuuJiang 2021-08-02 19:34:24 +08:00 via iPhone 1
楼上的都在强答些什么啊,正解是,你任意搜索一篇关于 rsa 原理的文献,其中的证明部分都针对 m 与 n 互质和不互质的情况进行了分类讨论,其中互质情况的证明就是你贴出来的欧拉定理,而假如不互质,那么 m 一定整除 p 或者整除 q,由于轮换对称性,任取其中一种假设接着证明即可,最后可以证出即使 m 与 n 不互质,m^ed%n==m 仍然成立,所以加解密仍然可以工作
|
5
bootvue 2021-08-02 19:47:35 +08:00
这就触及到了我的知识盲区
|
6
liuidetmks OP @GuuJiang 感谢,我之前看到的文章都是只证明了一半的,今天仔细搜了下,确实有,证明很有技巧。👍🏻
|
8
nikan999 2021-08-03 16:25:58 +08:00
m ^(ky(n) + 1) = 1 ^k • m mod n = m
我记得书里说欧拉定理的这个公式不要求 m 是 p 的倍数 跟 费马小定理对 a^p ≡ a(mod p)的约束是一样的 |
9
liuidetmks OP @nikan999 这里写的是 m 和 n 不互质的 情况( m=kp ),m 与 n 互质的话,直接欧拉定理一步得出结论。
|
10
nikan999 2021-08-04 20:15:24 +08:00
@liuidetmks m n 不互质的情况 这个公式也是成立的
|
11
nikan999 2021-08-04 20:22:21 +08:00 1
@liuidetmks
m ^y(n) ≡ 1 mod n 欧拉公式需要 m n 互质。 m ^(y(n)+1) ≡ m mod 欧拉公式的第二个公式,n 不需要 m n 互质,对于任意 m n 成立。 参考书:CRYPTOGRAPHY AND NETWORK SECURITY PRINCIPLES AND PRACTICE 里面有提到 |
12
liuidetmks OP @nikan999 感谢,这个扩展欧拉定理,我先前不知道。
不过上面的证明也是从费马小定理出发推导出来的。 |
13
nikan999 2021-08-05 17:33:12 +08:00
@liuidetmks 是的 我看了你的证明,你手动推导了这个公式。非常棒!赞!
|