V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
liuidetmks
V2EX  ›  程序员

关于 RSA 算法的疑问

  •  
  •   liuidetmks · 2021-08-02 18:37:11 +08:00 · 2147 次点击
    这是一个创建于 1192 天前的主题,其中的信息可能已经有所发展或是发生改变。

    关于 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 条附言  ·  2021-08-03 10:02:20 +08:00
    感谢 @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/) 有错误请指正 :)
    13 条回复    2021-08-05 17:33:12 +08:00
    Citrus
        1
    Citrus  
       2021-08-02 19:07:44 +08:00
    实践中处理明文需要分块的。
    GM
        2
    GM  
       2021-08-02 19:25:23 +08:00
    RSA 加密的数据比特数小于秘钥的比特数

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

    答案是切成小块来加密,然后再拼在一起。解密的也一样,切块后解密。
    GM
        3
    GM  
       2021-08-02 19:27:11 +08:00
    #2 楼修改一下:“超过 1024 比特怎么办” 改为 “超过秘钥比特数怎么办”
    GuuJiang
        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 仍然成立,所以加解密仍然可以工作
    bootvue
        5
    bootvue  
       2021-08-02 19:47:35 +08:00
    这就触及到了我的知识盲区
    liuidetmks
        6
    liuidetmks  
    OP
       2021-08-02 20:32:25 +08:00 via iPhone
    @GuuJiang 感谢,我之前看到的文章都是只证明了一半的,今天仔细搜了下,确实有,证明很有技巧。👍🏻
    Citrus
        7
    Citrus  
       2021-08-03 10:05:30 +08:00
    @GuuJiang 我的错,我以为楼主是在研究实践想到的问题,原来是研究理论的时候的发散想法=。=
    nikan999
        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)的约束是一样的
    liuidetmks
        9
    liuidetmks  
    OP
       2021-08-03 23:10:12 +08:00 via iPhone
    @nikan999 这里写的是 m 和 n 不互质的 情况( m=kp ),m 与 n 互质的话,直接欧拉定理一步得出结论。
    nikan999
        10
    nikan999  
       2021-08-04 20:15:24 +08:00
    @liuidetmks m n 不互质的情况 这个公式也是成立的
    nikan999
        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 里面有提到
    liuidetmks
        12
    liuidetmks  
    OP
       2021-08-05 14:44:35 +08:00
    @nikan999 感谢,这个扩展欧拉定理,我先前不知道。
    不过上面的证明也是从费马小定理出发推导出来的。
    nikan999
        13
    nikan999  
       2021-08-05 17:33:12 +08:00
    @liuidetmks 是的 我看了你的证明,你手动推导了这个公式。非常棒!赞!
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3222 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 12:36 · PVG 20:36 · LAX 04:36 · JFK 07:36
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.