区块链中的数学 - RSA算法加解密过程及原理

本节主要介绍了RSA算法加解密过程及原理,RSA还有很多相关内容,包括签名,具体运算过程,背景知识,安全性等。后续几篇将分别介绍,以求知识系统的完备性。

写在前面

上一节介绍了数论中的费马小定理,这一节继续讲RSA算法。RSA算法依赖的数论知识点较多,除了上篇说的费马小定理,还包括欧拉定理(欧拉函数)等。关于RSA知识点打算分三个章节讲解。采取知其然再深究所以然的方法来说明。

预备知识

RSA算法是1977年由Ron Rivest、Adi Shamir 和 Leonard Adleman三人共同提出。原始论文A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,感兴趣可以搜索查阅。下面先说下RSA算法预备知识

  1. 费马小定理 上一节说过,可自行查看

  2. 欧拉定理 这里简要说明一下,后续专门章节详细说明。 若n,a为正整数,且n,a互质,则 $a^{\varphi (n)} \equiv 1\ mod\ n$ 上式中$\varphi(n)$代表欧拉函数:是1到n−1中(也就是[1,n−1])且与n互质的整数的个数. RSA算法中涉及到的欧拉函数性质如下: (1) 若n是素数,$\varphi(n) = n-1$; (2) 若m,n互质, $\varphi(mn)=\varphi(m)\varphi(n)$; (3) 若m,n互质且都是素数,$\varphi(mn) =\varphi(m)\varphi(n) = (m-1)*(n-1)$ 更多性质以及证明后面专门介绍,以上列出的是本节需要用到的知识点。

密钥生成过程

用户按照以下步骤生成公私钥:

  1. 秘密选取两个大的素数𝑝和𝑞。

  2. 计算𝑝和𝑞的乘积:𝑛 = 𝑝 × 𝑞。

  3. 随机选取一个与𝜙(𝑛)=(𝑝−1)×(𝑞−1)[注:欧拉函数性质(3)]互质的数𝑒,应用中通常选取𝑒=65537【注:这是有原因的】。

  4. 计算𝑒模𝜙(𝑛)的模反元素𝑑,也即是计算满足: 𝑒⋅𝑑 = 1(𝑚𝑜𝑑𝜙(𝑛)) = 𝑒⋅𝑑 =1(𝑚𝑜𝑑(𝑝−1)⋅(𝑞−1))。【求模逆元可参考历史文章

  5. 将(𝑒,𝑛)作为公开的公钥;𝑑作为私钥,秘密保存。

可见,在RSA加密算法中,公钥以一个正整数对的形式出现,同理私钥也是如此。这与前面说过的椭圆曲线加密算法有所不同。椭圆曲线加密算法中公钥是一个点坐标。

加密解密过程

总体来说,加解密过程操作比较简单. 假设A与B通信:

  1. 加密过程 (1) A首先将明文分解成若干块,每个块可以表示为一个整数(基于n的大小分块),以𝑀表示,使得1⩽𝑀⩽𝑛−1。为方便起见,只考虑对一个明文数据块进行加密的流程。 (2)A用B的公钥(n,e)进行如下运算得到密文 $C=M^e\ mod\ n$

  2. 解密过程 B收到密文C后,做如下运算: $M =c^d\ mod\ n$ 得到原始消息M。

解密验证

我们反推一下为什么这样解密就能得到原始消息M呢? 解密运算: $C^d\ mod n =M^{ed}\ mod\ n$ 由于 𝑒⋅𝑑 = 1(𝑚𝑜𝑑𝜙(𝑛)) 可得: e*d = k𝜙(𝑛) +1 代入上式得:$C^d\ mod\ n =M^{k\varphi(n)+1}\ mod\ n$ 由于M也是一个整数,所以有以下两种情况:

  1. M与n互质

  2. M与n不互质

下面分情况证明$M^{k\varphi(n)+1}\ mod\ n = M$ 。

  1. M与n互质 这种情况下,由欧拉定理得:

$M^{\varphi(n)}\equiv 1(𝑚𝑜𝑑\ 𝑛)$ 所以: $M^{k\varphi(n)+1}\equiv(M^{\varphi(n)})^k*M \equiv M (mod\ n)$。得证。

  1. M与n不互质 由于𝑛的素因子分解只能是𝑛=𝑝×𝑞 [见上述密钥生成过程],所以M,n最大公因子𝑔𝑐𝑑(𝑀,𝑛)或者是𝑝或者是𝑞, 也即是𝑀 = ℎ𝑝或者𝑀 = ℎ𝑞。 假设𝑀 = ℎ𝑞,此时𝑀必然与𝑝互质[由p.q互质可得]。 由费马小定理可到下式: $M^{k\varphi(n)+1}\equiv(M^{p-1)})^{k_{(q-1)}}\cdot M \equiv M (mod\ p)$ 代入𝑀 = ℎ𝑞, 得:

    $(hq)^{k\varphi(n)+1} = jp + hq$ 式子左边是q的倍数,右边也必然是q的倍数,即jp也是q的倍数。由于p,q互质所以j是q的倍数,可表示为 j=kq 所以上式变为: $(hq)^{k\varphi(n)+1} = jp + hq = kqp + hq = kn + hq$ 两边对n 取模得到 :

    mod n = M mod n 。得证

    同理,𝑀=ℎ𝑝时可以得到相同的结论。大家可自行推导。

综合1和2两种情况,可以得出结论: $M^{k\varphi(n)+1}≡ 𝑀(𝑚𝑜𝑑\ 𝑛)$总是成立的,所以$𝑀= C^d\ 𝑚𝑜𝑑\ 𝑛 $也是成立的,证毕。

小结

本节主要介绍了RSA算法加解密过程及原理,RSA还有很多相关内容,包括签名,具体运算过程,背景知识,安全性等。后续几篇将分别介绍,以求知识系统的完备性。

好了,下一节讲背景知识中的欧拉定理和欧拉函数

欢迎关注公众号:blocksight

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2020-06-09 12:13
  • 阅读 ( 162 )
  • 学分 ( 0 )
  • 分类:入门/理论

0 条评论

请先 登录 后评论
blocksight
blocksight

53 篇文章, 954 学分