知识卡片

普通读书笔记卡 · 3702.c.1

RSA证明覆盖非互素消息

理解等级:高级

RSA取不同素数p、q,令n=pq,并选择e、d满足ed≡1 (mod φ(n))。要证明任意消息M都能由指数ed还原,分别考察模p和模q。

以模p为例:若p不整除M,由费马小定理和p−1整除φ(n),可得Mᵉᵈ≡M (mod p);若p整除M,则两边本来都同余0,不需要费马小定理。模q同理。最后由中国剩余定理,两个模下都相等推出Mᵉᵈ≡M (mod pq),所以证明也覆盖与n不互素的消息。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第31章 数论算法 · 查看原书依据

      Theorem 31.36 (Correctness of RSA) The RSA equations (31.37) and (31.38) define inverse transformations of ℤn satisfying equations (31.35) and (31.36). Proof From equations (31.37) and (31.38), we have that for any M ∈ ℤn, P(S(M)) = S(P(M)) = Med (mod n). Since e and d are multiplicative inverses modulo ϕ(n) = (p – 1)(q – 1), ed = 1 + k(p – 1)(q – 1) for some integer k. But then, if M ≠ 0 (mod p), we have Med = M(Mp–1)k(q–1) (mod p) = M((M mod p)p–1)k(q–1) (mod p) = M

    参考来源

    - 位置:《算法导论(第4版)》第31章《数论算法》(OEBPS/chapter031.xhtml,文本字符[65000,70000))。 - 结论依据:原书第31.7–31.8节的公钥、RSA或素数定理推导,结合对应图式核对。 - 原始内容:Theorem 31.36 (Correctness of RSA) The RSA equations (31.37) and (31.38) define inverse transformations of ℤ n satisfying equations (31.35) and (31.36). Proof From equations (31.37) and (31.38), we have that for any M ∈ ℤ n , P ( S ( M )) = S ( P ( M )) = M ed (mod n ). Since e and d are multiplicative inverses modulo ϕ ( n ) = ( p – 1)( q – 1), ed = 1 + k ( p – 1)( q – 1) for some integer k . But then, if M ≠ 0 (mod p ), we have M ed = M ( M p –1 ) k ( q –1) (mod p ) = M (( M mod p ) p –1 ) k ( q –1) (mod p ) = M