认识达内从这里开始

数字加密算法的出现，可以说大大提高了我们访问互联网的安全性。今天，我们就通过案例分析来简单了解一下，加密算法等技术是如何实现的以及他们的原理都有哪些。

一、概述

RSA算法是1977年由RonRivest、AdiShamir和LeonardAdleman三人组在论文AMethodforObtainingDigitalSignaturesandPublic-KeyCryptosystems提出的公钥加密算法。由于加密与解密使用不同的秘钥，从而回避了秘钥配送问题，还可以用于数字签名。

原论文可以说思路非常清晰、浅显易懂，是学习该算法非常不错的英文资料。原文先梳理了公钥加密系统和数字签名的特性和需满足的要求(这部分是实际上是借鉴了WhitfieldDiffie和MartinHellman的思想);然后阐述如何利用不同的加密秘钥和解密秘钥实现加解密流程，这是RSA算法工作的核心部分;接着介绍其背后的数学原理并证明算法的正确性，主要涉及基础数论知识(例如欧拉函数，费马定理，欧拉定理等);为了使算法更具有操作性，还介绍了如何利用"反复平法"算法进行快速的计算幂取模，从而快速的进行加解密运算，以及算法中涉及到其他参数选取(例如大素数p,qp,q选取，ee和dd的选取和计算);同时也用一个简单的小实例模拟算法的流程;后一个重要的话题是讨论该算法的安全性，通过考虑不同方法尝试破解该算法，并从计算量的角度解释了破解该算法的困难程度，以及其他的细节blablabla。。。。

所以原论文几乎是比较全地阐述了RSA算法的方方面面且不失可读性，非常值得借鉴。一些中文书籍也对该算法做了浅显易懂的解释，比如密码编码学与网络安全原理与实践和图解密码技术两本书的相关章节，都是很好的学习资料。

二、公钥加密系统

公钥加密系统主要特点是采用不同的加密秘钥和解密秘钥。在该系统中每个用户均生成自己的加密秘钥和解密秘钥，其中加密秘钥需公开出去，任何人都可以获得，加密秘钥也称为公钥;解密秘钥必须保密妥善保管，解密秘钥也称为私钥。在进行通信的时候，发送方先用接收方的加密秘钥(也就是公钥)加密消息，得到密文消息，发送给接收方;接收方收到消息用自己的解密秘钥(也就是私钥)可以解密得到明文。采用这样的加解密方式从而规避了传统加密系统中秘钥配送问题。

在密码学中，加密算法往往都是公开的，尝试通过保密加密算法来获得加密安全性的做法都是不值得推荐的(此所谓隐蔽式安全)。事实上，发明一个可行的加密算法并非易事，将其公之于众经受时间和广大使用者的检验是很好的做法。加密算法在秘钥的配合使用下进行加密和解密。因此在加密算法是公开的前提下，保证加密的安全依赖于秘钥的安全性。

将加密过程(encryption)和解密过程(decryption)分别视为一种处理程序，分别用EE和DD表示表示。明文消息和密文消息分别用MM和CC表示。则公钥加密系统有如下四种特性：

(a)对于加密后的密文C=E(M)C=E(M)，对应的解密程序能够处理得到明文：D(C)=D(E(M))=MD(C)=D(E(M))=M。

(b)加密过程EE和解密过程DD是容易计算的。

(c)由公开的加密程序EE不能轻易的得到解密程序DD，这样可以保证由EE加密的消息只能由DD解密。

(d)对明文消息先解密处理在做加密处理仍可以得到明文，也即保证逆向处理的可行性：E(D(M))=ME(D(M))=M。

特性(a)保证了加密的原始目的，如果加密后的密文不能由接受者解密还原回明文，那彼此就不能正常通信了。特性(a)和(b)在传统的对称加密系统中也是成立的。特性(d)用于数字签名，之所以能够对明文进行解密处理这实际上并不奇怪：抛开加密与机密的概念，EE和MM实际上就是一个从输入到输出的映射，明文和密文的概念是站在人的立场行划分的，对于计算机，无论是明文还是密文，都是比特序列，并没有其他任何差别，因此对明文做加密无非是进行一次函数运算。

三、秘钥生成与加密解密流程

1、秘钥生成

每一个用户都会生成自己的公钥和私钥，其流程如下：

1)选取两个大的素数pp和qq。

2)计算pp和qq的乘积n=p×qn=p×q。

3)随机选取一个与ϕ(n)=(p−1)×(q−1)ϕ(n)=(p−1)×(q−1)互质的数ee，也即是gcd(d,(p−1)×(1−1))=1gcd(d,(p−1)×(1−1))=1，应用中通常选取e=65537e=65537。

4)计算ee模ϕ(n)ϕ(n)的模反元素dd，也即是计算满足e⋅d=1(modϕ(n))=e⋅d=1(mod(p−1)⋅(q−1))e⋅d=1(modϕ(n))=e⋅d=1(mod(p−1)⋅(q−1))的dd。

5)将(e,n)(e,n)公开作为公钥，任何人都可以获取;将(d,n)(d,n)作为私钥，自己妥善保存。

可见，在RSA加密算法中，公钥以一个正整数对的形式出现，同理私钥也是如此。

在秘钥生成过程中，会产生如下的信息：

p,q,n,ϕ(n),d,ep,q,n,ϕ(n),d,e

但是需要公开的信息仅仅是e,ne,n两个整数，其他信息都应该严格的保密。

(以上流程实际上与原论文中有细微差别：原论文中是选取dd然后来计算ee，但是在现在的许多公钥证书中，ee基本都是相同的，也就是说现在的应用中实际是选取ee然后计算dd。)

2、加密和解密

还是以Alice和Bob这两个密码学中的两个网红为角色，述阐RSA算法加密和解密的流程。假设Alice向Bob发起通信，且已经获取到Bob公钥对(e,n)(e,n)。

1)Alice先将明文分解成若干块，每个块可以表示为一个整数(也就是将长比特序列分解成若干短的比特序列，每个序列自然可表示为一个整数)，以MM表示，使得1⩽M⩽n−11⩽M⩽n−1。为方便起见，只考虑对一个块进行加密的流程。

2)Alice用Bob的公钥(e,n)(e,n)做如下运算，得到密文CC，将密文通过公网通道发送到Bob。

C=MemodnC=Memodn

3)Bob收到密文，用自己的私钥(d,n)(d,n)做如下运算，可得到明文MM.

M=CdmodnM=Cdmodn

至此，加解和解密的流程已经结束，流程也非常简单清晰。

作者：Github

节选：博客园

【免责声明】：本内容转载于网络，转载目的在于传递信息。文章内容为作者个人意见，本平台对文中陈述、观点保持中立，不对所包含内容的准确性、可靠性与完整性提供形式地保证。请读者仅作参考。