美文网首页
RSA算法过程以及正确性证明

RSA算法过程以及正确性证明

作者: M_lear | 来源:发表于2019-02-02 10:05 被阅读0次

一、生成公钥、私钥

  1. 寻找两个不相同的大质数p、q
    随意寻找两个不相同的大质数p和q，计算N=p\times q
  2. 求 N 的欧拉函数值\varphi(N)
    \varphi(N)=\varphi(p)\varphi(q)=(p-1)\cdot(q-1)
    欧拉函数\varphi(n)的定义：
    \varphi(n)是小于等于 n 的正整数中与 n 互质的数的数目。（第一次见的话肯定会觉得很奇怪，怎么还会有这么奇怪的函数(^_^)）
  3. 计算私钥中最重要的 d
    选择一个小于\varphi(N)，并与\varphi(N)互质的整数 e，通常取65537，求得 e 关于\varphi(N)的模反元素 d，e\cdot d\equiv 1(\mod\varphi(N))
    模反元素的定义：
    如果两个正整数 a 和 n 互质，那么一定可以找到整数 b，使得n|(a\cdot b-1)。（前式等价于a\cdot b-k\cdot n=1,k\in N^*，由贝祖定理易知，整数 b 一定存在）
  4. 销毁p和q
    此时我们的(N,e)是公钥，(N,d)是私钥。

RSA算法的安全性：已知N和e，是否容易得到 d

  1. 要想知道 d，就要知道e和\varphi(N)
  2. 要想知道\varphi(N)，就要根据 N 算出p和q，而大数的质数分解是目前公认的数学难题，只能暴力求解。

二、加密、解密

  1. 使用公钥(N,e)加密， 假设明文为m(m<N)，则密文c=m^e\%N。
  2. 使用私钥(N,d)解密，则明文m=c^d\%N。

三、正确性证明（证明过程使用到欧拉定理）

证明 m 经加解密后还是 m，即证明等式m=(m^e\%N)^d\%N,m<N

  1. 明文 m 与 N 互质
    (m^e\%N)^d\%N
    =m^{ed}\%N
    =m^{k\varphi(N)+1}\%N,k\in N^*
    =[m(m^{\varphi(N)}\%N)^k]\%N
    =m\%N
    =m
  2. 明文 m 不与 N 互质
    m 不与 N 互质，N=pq，p、q都为质数。则一定有m=cp或m=cq,c\in N^*
    我们假设m=cp
    (cp)^{ed}\%q
    =(cp)^{k\varphi(N)+1}\%q,k\in N^*
    =(cp)^{k(p-1)(q-1)+1}\%q
    =[cp((cp)^{q-1}\%q)^{k(p-1)}]\%q
    =(cp)\%q
    即(cp)^{ed}=cp+tq,t\in N^*
    易知(cp)^{ed}\%p=0，即(cp+tq)\%p=0，即tq\%p=0
    显然p、q互质，\therefore t=rp,r\in N^*
    \therefore (cp)^{ed}=cp+tq=cp+rpq=cp+rN
    \therefore (cp)^{ed}\%N=(cp+rN)\%N=(cp)\%N
    即m^{ed}\%N=m\%N
    故m=(m^e\%N)^d\%N，得证！
    证明部分参考的博客

相关文章

网友评论

      本文标题：RSA算法过程以及正确性证明

      本文链接：https://www.haomeiwen.com/subject/hmirsqtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|RSA算法过程以及正确性证明|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！