It's our wits that make us men.

2019/5/10 《图解密码技术》第五章

Posted on May 10, 2019 By LuLu

《图解密码技术》第五章

  • RSA：Rivest-Shamir-Adleman,最小公倍数：least common multiplt,lem，最大公约数greatest commom divisor，gcd

时钟运算

为更好理解RSA算法，介绍一下时钟运算。

加法

img

当指针指向7，向右转20个刻度指向几的计算：

（7+20）/12=27/12=2余3

“除法求余数的运算”定义为一个运算符：mod

  • 27 mod 12 = 3 :27除以12的余数是3，即27与3以12为模同余
    • 除以12求余数称为以12取模

我们可以用求余数的方法来获得指针的位置

  • （7+6）mod12=1：指针指向的是1

总结：

  1. 时钟指向右旋转相当于做加法
  2. 不是单纯的加法，而是除法求余数mod

减法

暂时规定时钟的指针是不能向左转动的。

  • 如果指针指向7，怎样回到0，即（7+？）mod12=0，得到（7+5）mod12=0
  • 所以向右转动5，便回到0，所以5这个数字与-7这个数字是等价的

img

从上表可以看出，减去X与加上Y的运算是等价的

乘法

7*4可以理解为指针向右转7个刻度，重复四次，通过以下运算得到位置：

（7*4）mod 12 =28 mod 12 =4

所以指针会指向4

除法

除法可以看做是乘法的逆运算:

  • 7*？mod12=1：向右转动7个刻度重复几次，指针能指到1
    • 将0,1，.尝试之后，发现7*7mod12=1
  • 在mod12的世界里，1/7等于几是有的，但是在一般地整数世界中，这是不存在的

在时钟运算中，“某个数是否存在倒数这个问题，与公钥算法RSA中”一个公钥是否存在对应的私钥”是直接相关的

  • 0*？mod12=1，没有满足的
  • 以此类推，得到在mod12的世界中，存在倒数的数，他们和12之间的公约数都只有1，也就是说，某个数是否存在倒数，可以通过这个数和12的最大公约数是否为1这个条件来判断，即和12互质的数在mod12的世界里，存在倒数。

乘方

实际计算很简单，先进行一般的乘方运算之后，再求余数就可以：

7*7*7*7 mod 12=2401 mod 12=1=((7*7 mod 12)*(7*7 mod 12))mod 12=1 moo 12=1

可以简化计算大整数的乘积，也是在RSA的加密和解密算法中所使用的方法。

img

对数

时钟运算中的对数称为离散对数。

当数字很大时，求离散对数非常困难，非常耗时。能快速求出离散对数的算法到现在还没有被发现。

Diffie-Hellman密钥交换协议以及ElGamal公钥算法中就运用了离散对数

RSA

使用最广泛的公钥密码算法：RSA

什么是RSA

RSA是一种公钥密码算法，名字是由三位开发者姓氏的首字母组成的

RSA可用于公钥密码和数字签名

RSA加密

  • 在RSA中，明文(明文必须小于N)、密钥和密文都是数字。

  • RSA加密过程用一个公式表示：

  • 只要知道E(encryption)、N(number)这两个数，任何人都可以完成加密，所以RSA密钥：E、N，所以E和N的组合就是公钥,一般写成“公钥是{E,N}”

RSA的解密

  • RSA解密过程用一个公式表示：

  • 这里加密和解密使用的数字N是相同的，

  • 只有知道D(dencryption)、N(number)这两个数的人才可完成解密。RSA密钥：D、N，所以D和N的组合就是公钥,一般写成“私钥是{D,N}”
  • 作为解密密钥的D，和数字E有着紧密的联系

img

img

生成密钥对

求E、N、D这三个数就是生成密钥对，步骤如下：

  1. 求N
  2. 求L(L是尽在生成密钥对的过程中使用的数)
  3. 求E
  4. 求D
  • 求N
    • 先准备两个很大的质数p和q，一般为512比特（不大不小），用伪随机数生成器，在用数学方法判断是否为质数，直到生成一个质数。
    • N=p*q
  • 求L
    • L是p-1和q-1的最小公倍数(lem),可写成L=lem(p-1,q-1)
  • 求E
    • E是一个比1大，比L小的数，此外，E和L的最大公约数gcd必须为1，可写成gcd（E，L）=1
    • 用为伪随机数生成一个比1大，比L小的数，再判断gcd（E，L）=1
    • gcd（E，L）=1是为了保证，一定存在解密时需要使用的数D
  • 求D
    • 1<D<L
    • E*D mod L=1
    • 只要D满足上述两个条件，通过E和N加密的密文，就可以通过D和N进行解密