关于 RSA 算法的疑问

[liuidetmks]

关于 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 确能正常加解密

感谢 @Gugujiang

m n 不互质情况,
n = pq
ed = k1 * y(n) + 1
m = k2 * p

根据费马小定理

m ^ (q-1) = 1 mod q

两边 k1(p-1)次方

m ^ (k1(p-1)(q-1)) = 1 mod q

也就是
m ^(ed - 1) = 1 mod q

m ^(ed - 1) = 1 + k3 * q

两边乘以 m

m ^ (ed) = m + k3 * q * m = m + k3 * q (k2 * p)

由于 n = pq;

所以
m ^(ed) = m mod n

RSA 在 m 和 n 不互质的情况下也能正常工作。

v 站不支持公式, [具体可以看看这里]( https://vitock.github.io/2021/08/02/e68ed72c802a/) 有错误请指正 :)

[Citrus]

实践中处理明文需要分块的。

[GM]

RSA 加密的数据比特数小于秘钥的比特数

那么如果要加密的数据很长，超过 1024 比特怎么办？

答案是切成小块来加密，然后再拼在一起。解密的也一样，切块后解密。

[GM]

#2 楼修改一下：“超过 1024 比特怎么办” 改为 “超过秘钥比特数怎么办”

[GuuJiang]

楼上的都在强答些什么啊，正解是，你任意搜索一篇关于 rsa 原理的文献，其中的证明部分都针对 m 与 n 互质和不互质的情况进行了分类讨论，其中互质情况的证明就是你贴出来的欧拉定理，而假如不互质，那么 m 一定整除 p 或者整除 q，由于轮换对称性，任取其中一种假设接着证明即可，最后可以证出即使 m 与 n 不互质，m^ed%n==m 仍然成立，所以加解密仍然可以工作

[bootvue]

这就触及到了我的知识盲区

[liuidetmks]

@GuuJiang 感谢，我之前看到的文章都是只证明了一半的，今天仔细搜了下，确实有，证明很有技巧。👍🏻

[Citrus]

@GuuJiang 我的错，我以为楼主是在研究实践想到的问题，原来是研究理论的时候的发散想法=。=

[nikan999]

m ^(ky(n) + 1) = 1 ^k • m mod n = m
我记得书里说欧拉定理的这个公式不要求 m 是 p 的倍数
跟 费马小定理对 a^p ≡ a(mod p)的约束是一样的

[liuidetmks]

@nikan999 这里写的是 m 和 n 不互质的 情况（ m=kp ），m 与 n 互质的话，直接欧拉定理一步得出结论。

[nikan999]

@liuidetmks m n 不互质的情况 这个公式也是成立的

[nikan999]

@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 里面有提到

[liuidetmks]

@nikan999 感谢,这个扩展欧拉定理,我先前不知道。
不过上面的证明也是从费马小定理出发推导出来的。

[nikan999]

@liuidetmks 是的 我看了你的证明，你手动推导了这个公式。非常棒！赞！