Minglei Yin

I eat alone. I sleep alone. I cry alone. Sooooo...cool.

加密和RSA算法

RSA

本文是一篇关于RSA的详细介绍，你可以在这里几乎发现RSA的所有细节，以至于你看完本文后，自己就可以写一个RSA的加密算法了．

1.加密介绍

我们知道在github上创建了账户后，也许第一件事情是，你要上传一个叫public key的数据，只有在上传了该数据之后，你才可以从你的本地端推送你的代码到github的repository中。那么这个public　key的具体作用是什么呢？你可以在本文中获得一个大致的了解。文中所述若有谬误，敬请联系我，希望可以一起学习，谢谢！

简单来说，public key是作为数据传输过程中为数据加密而设计的。那么这就牵扯到加密的一些知识。我们先来大致看一下加密的一个简单介绍。没有深奥的理论。所以，请继续看下去。

通常，加密算法可以大致分为两种，对称加密算法和非对称加密算法。这样的分类中的一个关键人物叫密钥，这个东西可以认为就是加密与解密的规则。比如你要对字符串“hello world”加密，我们使用简单的规则，让字符串中每个字母的ASCII码值加一，然后进行传输，那么这个“ASCII码值加一”我们就可以称之为密钥。当然，这只是一个简单的例子帮助你理解，真正的密钥可能是一个数字，也可能是一个矩阵。在对称加密算法中，加密和解密使用的密钥是同一个，但是在非对称加密中加密和解密使用的则是不同的密钥，这就是区别。

在对称加密算法中，由于加密和解密使用相同的密钥，所以这个密钥要妥善保管，绝对不能被人知道。其实，对称加密算法的一个弊端也体现在这里，就是密钥的分发是比较困难的，因为在对称加密算法中，除了加密方需要知道这个密钥，解密方也需要知道这个密钥用来解密，如果把密钥一起发送，则就存在泄露的风险。对称加密算法的一个明显优势是加密速度非常快，通常领先于非对称加密算法几个数量级。常见的对称加密算法有：DES, AES等。

symmetry encryption

在非对称加密算法中，密钥是成对出现的，分别被称为公钥和密钥，其特点如下：

  • 公钥和私钥成对出现
  • 用公钥加密的数据只有对应的私钥可以解密
  • 用私钥加密的数据只有对应的公钥可以解密
  • 如果可以用公钥解密，则必然是对应的私钥加密的
  • 如果可以用私钥解密，则必然是对应的公钥加密的

公钥和私钥其实是相对的，两者本身并没有绝对的规定。

non-symmetry encryption

２.非对称加密与解密过程

非对称加密与解密的一个简单过程如下：

  1. 首先接收方生成一对密钥，即公钥和私钥
  2. 然后，接收方将公钥发送给发送方
  3. 发送方用收到的公钥对数据加密，再发送给接收方
  4. 接收方收到数据后，使用私钥进行解密

encryption & decryption

非对称加密除了可以保证数据的安全性，还可以对数据进行签名。“数字签名”是用来验证发送方的身份并帮助保护数据的完整性。例如：一个发送者A想要给大家传送文件，他可以用自己的私钥对资料加密，即签名。所有收到文件的人都可以用发送者的公钥进行验证，变可以确认资料是由A发送的，因为A使用自己的密钥加密的文件也只有A的公钥可以解密。所以数字签名可以确认的两点信息：

  • 保证信息是由签名者自己签名后发送的，签名者不能否认
  • 保证信息自签发以后到收到为止没有被其他人修改过

3.非对称加密的弊端

非对称加密优点我们都知道是安全性比较高，但是它的最主要的一个弊端就是效率非常低，即加密与解密需要大量的计算资源，比通常用的对称加密算法如DES和AES通常要慢上几个数量级。所以面对如此低的效率，我们不可能用其加密大量的数据，而只能加密少量的数据。现实中通常的做法是将非对称加密算法与对称加密算法结合起来使用。即使用效率比较高的对称加密算法来加密原始数据，而使用非对称加密算法来加密对称加密算法的密钥，保证对称加密算法的密钥安全性就保证了原始数据的安全性。

assembled en & de

4.RSA

在非对称加密算法中，最著名的就是RSA了。RSA是创建该算法的三位数学家名字的首字母。下面我们就来看看RSA的实现过程。

4.1 几点必要的数学知识

我们先来看几个RSA中可能用到的几点数学知识，只列出几个重要的，如果其中有部分名词(比如互质)你没有见过，可以google一下，相信看一下就会明白的。

欧拉函数：任意给定正整数n，在小于等于n的正整数中，与n构成互质关系的整数的数目。可以记为：$$\varphi(n)$$。如$ \varphi(8)=4 $,因为与８形成互质关系的是１，３，５，７。

欧拉函数的几个性质：

  • $\varphi(1)=1$
  • 如果n是质数，则$\varphi(n)=n-1$
  • 如果n是某个质数的幂，即$n=p^k$，（p为质数,k为大于等于１的整数）则： 　　$\varphi(n)=\varphi(p^k)=p^k-p^{k-1}=p^k(１－\frac{1}{p})$
  • 若$p1$与$p2$互质，则$\varphi(p1p2)=\varphi(p1)\varphi(p2)$
  • 任何一个大于１的正整数，都可以写成一系列质数的积: $n=p1^{k1}p2^{k2}\ldots pr^{kr}$ $\varphi(n)=\varphi(p1^{k1})\varphi(p2^{k2})\ldots \varphi(pr^{kr})$ $=p1^{k1}p2^{k2} \ldots pr^{kr}(1-\frac{1}{p1})(1-\frac{1}{p2}) \ldots (1-\frac{1}{pr})$ $=n(1-\frac{1}{p1})(1-\frac{1}{p2}) \ldots (1-\frac{1}{pr}) $

欧拉函数的用处在于欧拉定理： 设整数a和n互质，则n的欧拉函数$\varphi(n)$可以使得下面的等式成立: $a^{\varphi(n)} \equiv 1( mod\ \ n)$

模反元素：如果两个正整数a和n互质，那么一定可以找到整数b，使得ab-1可以被n整除，或者说ab被n除的余数是1。 $ab\equiv 1(mod\ \ n)$,b叫做a的模反元素。

而欧拉定理的出现则可以用来证明模反元素必然存在： $a^{\varphi(n)}=a\times a^{\varphi(n)-1}\equiv 1(mod\ \ n)$ 可以看到$a^{\varphi(n)-1}$就是a的模反元素。

可能用到的几点数学知识已经全列出来了，其中可能并没有给出详细的证明，有几个的证明其实是很简单的，如果你真的想知道，这里我给出阮一峰老师写的关于RSA的一篇博客，里面有简单的证明。下面就可以一窥RSA的细节了。

4.2 RSA流程

产生公钥与私钥流程

这里引用一下wiki中关于RSA的操作过程。假设Alice想要给Bob发送信息，她可以用以下方式来产生一对公钥和私钥。

  1. 随意选择两个大的质数p和q，p不等于q，令N=pq.
  2. 根据欧拉函数，求得$r=\varphi(N)=\varphi(p)\varphi(q)=(p-1)(q-1)$
  3. 选择一个小于r的整数e，求得e关于r的模反元素(隐含e与r要互质)，设为d。(扩展欧几里得算法可求解，参考我的前一篇博文)
  4. 将p和q的记录销毁

(N,e)是公钥，(N,d)是私钥。实际应用中公钥与私钥数据的封装采用ASN.1格式表达。现在Alice将她的公钥(N,e)传给Bob,而将她的私钥(N,d)藏起来

加密消息流程

假设Bob想给Alice发送消息m，他知道了Alice产生的(N,e)，即公钥．他使用起先与Alice约好的格式将m转换为一个小于N的整数n，比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为n。用下面这个公式他可以将n加密为c：

[n^e\equiv c(mod \ N)]

这里要说明几点细节，这也是在看RSA的时候很困扰我的：第一，由于我们在加密之前要先使用一定的规则处理加密的原始消息，其中一条规则是加密的单个数据大小要小于N，所以加密之后的c也是小于N的，上面的式子就等同于求解$c=n^e \ mod \ N$．第二，通常 $n^e$这个数是很大的，已经远远超过了一般计算机所能表示的范围，所以我们不能直接计算$n^e$的值．幸好数学家们为我们研究好了一种叫模幂运算的快速计算$n^e \ mod \ N$的算法．具体过程见我的早前的一篇博文，是我在学习RSA的过程中记录下来的．

解密消息流程

Alice得到Bob的消息c后就可以利用她的密钥d来解码。她可以用以下这个公式来将c转换为n：

[c^d \equiv n(mod \ N)]

解码的过程中同样需要快速模幂运算．

4.３ RSA终极解释

如果你只是想学会怎么用RSA，那么你可能需要再看一个4.4的例子就大功告成了．本小结只是想把RSA的本质说的更透彻一些．另外，限于本人的数学水平，可能所述不尽完善，让看的人心生疑惑．所以，如果你是使用主义者，可能跳过本小节也是个不错的选择．但是，我还是尽自己的努力讲述RSA的尽可能多的细节问题，当然包含本小节的原理性描述．这里向大家推荐一个不错的RSA视频吧，如果你有兴趣也可以看一下，讲的还是挺不错的，深入浅出．

RSA当时被构建之初，数学家们的想法就是：构建一种单向函数．这种单向函数表现为，从一个方向计算是容易的，但是反向确是困难的，除非你拥有一个＂后门＂．后面我们再述这里的后门的具体含义．那么到底如何寻找这样的一种函数不易被破解呢？这时候需要求助于一种叫做时钟算术(Clock arithmetic)的数学计算方法，也就是我们说的模指运算．像这样的形式　$3^{14}\ mod \ 17 \equiv 2$.

现在，我们假设我们有个数据m，我们为其做一次时钟算术$m^e\ mod\ N \equiv c$,做这个运算是及其容易的．那么如果反过来，我们现在知道c，想要求解这个式子$?^e\ mod\ N \equiv c$，还容易计算吗？答案是NO！除非你拥有一个"后门"，所以，这里＂后门＂的具体含义就是key，他使反向运算(即解密)变得容易．假设有这个＂后门＂，如何反向运算得到m呢？你可以这么做$c^d \ mod \ N \equiv m$，这将逆反原来对m的操作，并且找回原始的数据m.所以这里的d就是＂后门＂，也同时是key.

通过观察，我们发现，上述其实我们只做了两个步骤，加密和解密：

[ m^e\ mod \ N \equiv c] [ c^d \ mod \ N \equiv m]

两次操作合在一起的效果等同于 $m^{ed} \ mod \ N \equiv m$．e是加密操作(encryption)，d是解密操作(decryption)，经过这样两部操作后可以还原原来的信息．（如果你看不懂这个结论，那么我告诉你一个公式，$a^b \ mod \ n \equiv (a\ mod\ n)^b\ mod \ n$. 这样利用代入法一代换就得到结论了．）

现在要做的工作就是找到一个方法来构建e和d，并且使任何人都很难找到d．被找到的这个方法就是基于欧拉函数和欧拉定理所构建的．根据欧拉定理我们有这个式子的成立：

[ m^{\varphi(n)} \equiv 1 (mod\ n)]

然后我们需要两个基本的准则作用于欧拉定理上 $$ \begin{cases} １^k=1 \ 1m=m \end{cases} $$ 分别先后*应用这两条规则，我们可以得到下面的式子：

[m^{k\cdot \varphi(n)} \equiv 1\ mod\ n] [m^{k\cdot\varphi(n)+1} \equiv m\ mod\ n]

终于，找到了: $ed=k\cdot\varphi(n)+1$ [ d=\frac{k\cdot\varphi(n)+1}{e}]

多说一点的是，这里根据$ed=k\cdot\varphi(n)+1$计算d，即为求e的关于$\varphi(n)$的模反元素，所以这个式子其实等价于$ed \equiv 1\ mod\ \varphi(n)$求解d．(求解仍然需要扩展欧几里得哦^_^)

4.4 An example

产生公钥与私钥

  • 选择两个质数p=61,q=53(实际中这两个质数要选择大一些)
  • 计算n=pq=61*53=3233,n的长度就是密钥的长度，指转化为二进制的位数．实际应用中RSA一般是1024位，重要场景下需要2048位．
  • 计算n的欧拉函数$\varphi(n)=(p-1)(q-1)=3120$.
  • 随机选择一个整数e，条件是$1<e<\varphi(n)$,且e与$\varphi(n)$互质．本例中选择范围为1到3120之间，假设为17.(实际应用中常选择65537)
  • 计算e对于$\varphi(n)$的模反元素d. $ed\equiv1(mod\ \varphi(n))$,即$17d\equiv1(mod\ 3120)$，求解d=2753

计算完成，(3233,17)为公钥，(3233,2753)为私钥．

加密

加密需要用到公钥(3233,17).直接进行加密的对象一定是整数(如果数据表现为其他形式，比如字符串，需要转换为整数，可以取unicode的值)，并且m要小于n．按照加密的式子计算：

[ m^e \equiv c\ mod\ n　\Longrightarrow　65^{17} \equiv c\ mod\ 3233]

解出c=2790,于是可以发送已经加密过的数据2790

解密

解密需要用到私钥(3233,2753)．然后按照解密的式子计算：

[c^d \equiv m\ mod\ n \Longrightarrow　2790^{2753} \equiv m \ mod\ 3233]

解出m=65，于是就得到原始的数据为65．

至此，整个加密和解密的过程全部完成了．

5.RSA的安全性

RSA从出现为止就收到了极大的关注，原因就是其表现出的安全性让人比较满意．迄今为止，大家认为攻破RSA的一个方式就是对n进行因数分解，如果可以分解出n变可以知道p与q，进一步可以得到$\varphi(n)$，根据$ed\equiv 1\ mod\ \varphi(n)$就可以算出私钥d，进而破解得到加密数据．这其中的关键步骤即为对一个大整数进行因式分解，而这是到目前为止没有有效的方法做到的．现在已经分解的最大整数为768个二进制位（232个十进制位），所以目前RSA一般密钥都在1024位，有的甚至是2048位．

6. python中rsa库用法

说明：rsa需要自行安装

import rsa

(pubkey,prikey) = rsa.newkeys(1024)

#print pubkey
#print prikey

pub = pubkey.save_pkcs1()
pubfile=open('public.pem','w+')
pubfile.write(pub)
pubfile.close()


pri = prikey.save_pkcs1()
prifile = open('private.pem','w+')
prifile.write(pri)
prifile.close()

# load public-key and private-key

message = 'hello'
with open('public.pem') as publicfile:
    p = publicfile.read()
    pubkey = rsa.PublicKey.load_pkcs1(p)

with open('private.pem') as privatefile:
    p = privatefile.read()
    privkey = rsa.PrivateKey.load_pkcs1(p)

# encryption with public-key and decryption with private-key

crypto = rsa.encrypt(message, pubkey)

message = rsa.decrypt(crypto, privkey)

print message

# sinature with private-key
# Hashes the message, then signs the hash with the given key
signature = rsa.sign(message, privkey, 'SHA-1')
rsa.verify('hello', signature, pubkey)