RSA

Posted by Jerry Wang on 2016-12-09

密码学是一个天才辈出的领域。这学期修了密码学,很抱歉,我基本没有听懂。偶尔还会翘翘课。不过张老师在最后一节课的总结中,回顾了整个学期的课,讲了一些有意思的topic,竟然勾起了我对密码学的兴趣…

RSA

在加密领域中,非对称加密思想毋庸置疑是个革命性的idea。RSA是第一个实现非对称加密的算法,非常值得研究一下。

现在有两个人,Alice和Bob。如果使用RAS,Alice和Bob的通信过程大致是这样的。

  1. Alice随机选择两个n比特的质数p和q,并计算他们的乘积N=p*q。
  2. Alice计算r=(p-1)*(q-1),然后在(1, r)范围中选择一个质数e。
  3. 接着,有了r和e,Alice计算e对于r的模反元素d。(e*d%r == 1)

上述三个步骤,就产生了公钥=(N,e)和私钥=(N,d)。然后呢?

公钥(N, e)是公开的,Bob和其他人都可以知道。假设Bob想发送消息m给Alice。(要求m<n,费马小定理决定)这个明文m使用公开的密钥(N,e)加密后就是,
$$
c \equiv m^e (mod\ N)
$$
(课堂上,张老师直接写=号)然后,Bob将加密好的密文c发送给Alice,Alice拿到m以后,使用私钥(N,d)对其进行解密,
$$
c^d \equiv m \ (mod\ N)
$$
基本过程就是这样,数学证明暂时就不写了。