第3章〓物联网安全密码学基础


密码学概论(密码发展史、密码系统、密码分类)

典型对称密码算法AES

典型非对称密码算法RSA

国产密码算法




为中国革命胜利发挥重要作用的“豪密”


1929年末，中国共产党在上海的第一部秘密地下电台建立。同年12月，香港电台建立。1930年1月，上海与香港电台之间第一次通报成功，这是党历史上第一次无线电通报成功。当时使用的是一种“明码颠倒”的加密方式，香港电台很快被英国殖民政府破坏。周恩来得到电报被破译的消息后，非常震惊，立刻决定重新编制密码。周恩来提出编码思想后，汇总集体智慧，亲自动手，终于编制出了一套密码，也是中共第一部高级密码，因周恩来在党内代号是“伍豪”，这套密码便被称作“豪密”。

周恩来亲自编制的这套密码，从未被敌人破译。因为在密码破译上，全世界都有一个共同的破译规律，就是寻找重复，当无法破译的时候，就把各封电报搜集在一起，然后通过重复的码来寻找规律。而一次一密的“豪密”是不会重复的。“豪密”只是一种简单的密码，是一种“底本”加“乱数”的密码。所谓的“底本”就是类似明码一样的单表代替式密码本，而“乱数”是编成的表，若干随机编排的数字。然后再加上“加减法”一样的“算法”进行加密。例如，“我在等你”的电码是“1234234534564567”，如果后面加上一组乱码“9876876576546543”，用上加法之后，则发送的时候就是“0000000000000000”。换言之，这就好比现在的支付工具，除了要有支付密码外，还要有短信发来的“验证码”，尽管支付密码是固定的，但是验证码是随机的，两个密码同时发挥作用才能成功。

周恩来创造的这套密码体制为中国革命的胜利发挥了特别的作用，一直到解放战争结束，国民党方面的专家也未能破译“豪密”。正是在它的帮助下，“龙潭三杰”才能一次次将宝贵的情报安全传递到党中央，使得我党在对敌无线电斗争中始终掌握主动权，为党的战略布局赢得先机。

基于此背景材料，你是否对密码学产生了浓厚兴趣，那让我们开启本章的学习之旅吧！


3.1密码学概述

密码学(Cryptography)是一种为信息安全提供解决方案的学科，是数学的一个分支，在物联网诸多应用场景中发挥巨大作用。物联网中广泛采用的加密、消息认证、数字签名等都是基于密码学的。例如，大多数物联网终端设备都处于开放的网络环境下，为确保安全性，需要利用加密算法，对物联网设备之间传输的数据进行加密，防止攻击者窃取数据，从而保证信息的保密性； 通过消息认证技术，可以判断物联网设备之间传输的消息是否被篡改，从而保证信息的完整性； 验证收到的消息是否真的来自发送设备，保证消息的可认证性等。Cryptography一词来源于古希腊语的crypto和graphen，意思是密写，它以认识密码变换为本质，以加密与解密基本规律为研究对象，包括密码编码学和密码分析学。其中，密码编码学是研究各种加密方案的科学； 密码分析学是研究密码破译的科学。






3.1.1密码发展史

密码技术最早源于战争需求，从某种意义上说，战争是科学技术进步的催化剂。人类自从有了战争，就面临着通信安全的需求，许多古代文明，包括埃及人、希伯来人、亚述人都在实践中逐步发明了密码系统。存于石刻或史书中的记载表明，密码技术源远流长。密码学的发展历史大致经历了四个阶段： 古代加密方法、古典密码、现代密码和量子加密。

1. 古代加密方法(手工阶段)

古代加密方法大约起源于公元前440年，出现在古希腊战争中的隐写术，当时为了安全传送军事情报，奴隶主剃光奴隶的头发，将情报写在奴隶的光头上，待头发长长后将奴隶送到另一个部落，再次剃光头发，原有的信息复现出来，从而实现这两个部落之间的秘密通信。我国古代也早有以藏头诗、藏尾诗、漏格诗及绘画等形式，将要表达的真正意思或“密语”隐藏在诗文或画卷中特定位置，一般人只注意诗或画的表面意境，而不会去注意或很难发现隐藏其中的“话外之音”。比如，我画蓝江水悠悠，爱晚亭上枫叶愁。秋月溶溶照佛寺，香烟袅袅绕轻楼。(藏头诗)。

最早的密码技术来源于公元前2000年。希伯来人的一种加密方法是把字母表调换顺序，这样的字母表的每一个字母就被映射成调换顺序后的字母表中的另一个字母，这种加密方法被称为Atbash。例如，单词security就被加密成hvxfirgb，这是一种代换密码，因为一个字母被另一个字母所代替。这种代换密码被称为单一字母替换法，因为它只使用一个字母表，而其他加密方法一次用多个字母表，则称为多字母替换法。

公元前400年，斯巴达人发明了“塞塔式密码”，即把长条纸螺旋形地斜绕在一个多棱棒上，将文字沿棒的水平方向从左到右书写，写一个字旋转一下，写完一行再另起一行从左到右写，直到写完。解下来后，纸条上的文字消息杂乱无章、无法理解，这就是密文，但将它绕在另一个同等尺寸的棒子上后，就能看到原始的消息。

后来，朱利叶斯·恺撒发明了一种近似于Atbash替换字母的方法。当时，没多少人能够第一时间读懂，这种方法提供了较高的机密性。中世纪，欧洲人不断利用新的方法、新的工具和新的实践优化自己的加密方案。在19世纪晚期，密码学已经被广泛地用作军事上的通信方法。

2. 古典密码(机械阶段)

古典密码的加密方法是以单个字母为作用对象的加密法，一般是文字置换，使用手工或机械变换的方式实现。古典密码系统已经初步体现出近代密码系统的雏形，它比古代加密方法复杂，其变化较小。



图31Enigma密码机

随着机械和电子技术的发展，电报和无线通信的出现，加密装置得到了突飞猛进的提高，转子加密机是军事密码学上的一个里程碑，这种加密机是在机器内用不同的转子来替换字母，它提供了很高的复杂性，从而很难攻破。德国的Enigma密码机是历史上最著名的加密机，如图31所示。这种机器有三个转子、一个线路连接板和一个反转转子。在加密开始之前，消息产生者将Enigma密码机配置成初始设置，操作员把消息的第一个字母输入加密机，加密机用另一个字母来代替并把这个字母显示给操作员看。Enigma密码机的加密机制是： 通过把转子旋转预定的次数，用另一个不同的字母来代替原来的字母。因此，如果操作员把T作为第一个字符敲入机器中，Enigma密码机可能会把M作为密文，操作员就把字母M写下来，然后他可以加快转子的速度再输入下一个字符，每加密一个字符操作员就加快转子的速度作为一个新的设置。继续这样下去，直到整个消息被加密。然后，加密的密文通过电波传输，大部分情况是传到潜水艇。这种对每个字母有选择性地替换依赖于转子装置，因此这个过程的关键和秘密的部分(密钥)在于在加密和解密的过程中操作员是怎样加速转子的。两端的操作员需要知道转子的速度增量顺序以使得德国军事单位能够正确地通信。尽管Enigma密码机的装置在当时非常复杂，但还是被一组波兰密码学家攻破，从而使得英国知道了德国的进攻计划和军事行动。有人说，Enigma密码机的破译使第二次世界大战缩短了两年。


3. 现代密码(计算机阶段)

前面介绍的古代加密方法和古典密码，对它们的研究还称不上是一门科学。直到1949年香农发表了一篇题为“保密系统的通信理论”的著名论文，该论文首先将信息论引入了密码，从而把已有数千年历史的密码学推向了科学的轨道，奠定了密码学的理论基础。该论文利用数学方法对信息源、密钥源、接收和截获的密文进行了数学描述和定量分析，提出了通用的密钥密码体制模型。需要指出的是，由于受历史的局限，20世纪70年代中期以前的密码学研究基本上是秘密地进行，而且主要应用于军事和政府部门。密码学的真正蓬勃发展和广泛应用是从20世纪70年代中期开始的。1977年美国国家标准局颁布了数据加密标准（Data Encryption standard,DES）用于非国家保密机关。该系统完全公开了加密、解密算法。此举突破了早期密码学的信息保密的单一目的，使得密码学得以在商业等民用领域广泛应用，从而给这门学科以巨大的生命力。

在密码学发展进程中的另一件值得注意的事件是，在1976年，美国密码学家迪菲和赫尔曼在一篇题为“密码学的新方向”一文中提出了一个崭新的思想，即不仅加密算法本身可以公开，甚至加密用的密钥也可以公开。但这并不意味着保密程度的降低。因为如果加密密钥和解密密钥不一样。而将解密密钥保密就可以。这就是著名的公钥密码体制。若存在这样的公钥密码体制，就可以将加密密钥像电话簿一样公开，任何用户当他想向其他用户传送一个加密信息时，就可以从这本密钥簿中查到该用户的公开密钥，用它来加密，而接收者能用只有他所具有的解密密钥得到明文。任何第三者不能获得明文。1978年，美国麻省理工学院的李维斯特、萨英尔和阿德曼提出了RSA公钥密码体制，它是第一个成熟的、迄今为止理论上最成功的公钥密码体制。它的安全性是基于数论中的大整数因子分解，该问题是数论中的一个困难问题，至今没有有效的算法，这使得RSA公钥密码体制具有较高的保密性。关于RSA公钥密码体制将在3.3节详细介绍。

按照人们对密码的一般理解，密码是用于将信息加密而不易破译，但在现代密码学中，除了信息保密外，还有另一方面的要求，即信息安全体制还要能抵抗对手的主动攻击。所谓主动攻击指的是攻击者可以在信息通道中注入他自己伪造的消息，以骗取合法接收者的相信。主动攻击还可能篡改信息，也可能冒名顶替，这就产生了现代密码学中的认证体制。该认证体制的目的就是保证用户收到一个信息时，他能验证消息是否来自合法的发送者，同时还能验证该信息是否被篡改。在许多场合中，如电子汇款，能对抗主动攻击的认证体制甚至比信息保密还重要。在密码学的发展过程中，数学和计算机科学至关重要，数学中的许多分支如数论、概率统计、近世代数、信息论、椭圆曲线理论、算法复杂性理论、自动机理论、编码理论等都可以在其中找到各自的位置。密码学形成一门新的学科是受计算机科学蓬勃发展刺激和推动的结果。快速电子计算机和现代数学方法一方面为加密技术提供了新的概念和工具，但另一方面也给破译者提供了有力武器。计算机和电子学时代的到来给密码设计者带来了前所未有的自由，他们可以轻易地摆脱原先用铅笔和纸进行手工设计时易犯的错误，也不用再面对用电子机械方式实现的密码机的高额费用。总之，利用电子计算机可以设计出更为复杂的密码系统。

4. 量子加密

量子加密技术，是利用量子原理，进行密钥的生成、明文的混淆加密、密文的还原解密、密文的通信、反窃听等一系列加密技术。量子加密利用量子力学中测量对粒子物理状态产生不可逆影响的属性，也就是量子不可测量的特性，来确保通信密钥的安全传递。所以它不仅可以解决一次一密的密码本传输问题，还能确保在传输密钥时不会被第三方窃听和复制，是未来加密技术发展的重要方向。第一次真实的量子加密系统，是1988年在IBM的实验室开发出来的。1995年，日内瓦大学可以做到相距23km完成量子加密通信。2012年，我国潘建伟院士团队把这个数字推进到了一百千米这个级别。现在这个团队正在尝试在空间轨道上卫星和地面接收站间，实现量子加密信息的传输，距离就已经达到千千米的级别。2016 年中国发射了“墨子”号量子通信卫星，并于 2018 年成功实现了跨洲际的量子保密信息传输。只不过实验中符合条件的光量子态数量实在太少，只有几个到十几个数位，远远不能承载信息的正文，所以到目前为止，量子加密只适合给密钥加密，离大规模应用还有一定距离。

3.1.2密码系统

密码系统又称为密码体制，是指能完整地解决信息安全中的机密性、数据完整性、认证、身份识别及不可抵赖等问题中的一个或几个的一个系统，其目的是让人们能够使用不安全信道进行安全的通信。

1. 密码系统组成

一个完整的密码系统包括如下五个要素{明文M，密文C，密钥K，加密算法E，解密算法D}，示意图如图32所示。



图32密码系统组成


(1) 明文： 是加密输入的原始信息，通常用m表示。全体明文的集合称为明文空间，通常用M表示。

(2) 密文： 是明文经过加密变换后的结果，通常用c表示。全体密文的集合称为密文空间，通常用C表示。

(3) 密钥： 是参与信息变换的参数，通常用k表示。全体密钥的集合称为密钥空间，通常用K表示。

(4) 加密算法： 是将明文变成密文的变换函数，即发送者加密消息时所采用的一组规则，通常用E表示。

(5) 解密算法： 是将密文变成明文的变换函数，即接收者解密消息时所采用的一组规则，通常用D表示。

加密： 是将明文M用加密算法E在加密密钥Ke的控制下变换成密文C的过程，表示为C=EKe(M)。

解密： 是将密文C用解密算法D在解密密钥Kd的控制下变换成明文M的过程，表示为M=DKd(C)，并要求M=DKd(EKe(M))，即用加密算法得到的密文用一定的解密算法总能够恢复成为原始的明文。

【思考】

思考1. 密码系统哪些要素是必须保密的？哪些要素是可以公开的？

思考2. 加密/解密算法能否公开？请说明你的理由。

2. 密码系统的设计要求

1883年2月，巴黎HEC商学院的德国籍语言学家和教授奥古斯特·柯克霍夫(August Kerckhoffs)在《军事科学报》(Journal of Military Science)上发表了一篇文章，提出了“柯克霍夫原则”，奠定了现代密码学的基础，而他也因此被世人誉为“计算机安全之父”。柯克霍夫原则明确了密码系统的设计要求，显示了密钥在密码系统中的重要性，而这一原则最早被应用于电报加密。

表述1： 密码系统中的算法即使为密码分析者所知，也无助于用来推导出明文和密文。

表述2： 即使密码系统的任何细节已为人所知，只要密钥没有泄露，它也应该是安全的。

表述3： 密码系统应该就算被所有人知道系统的运作步骤，仍然是安全的。

美国数学家、信息论的创始人克劳德·艾尔伍德·香农(Claude Elwood Shannon)提出的香农公理是对柯克霍夫原则的又一诠释： 敌人知道系统。

在密码学中通常假定加密密钥和解密算法是公开的，密码体制的安全性只系于密钥的安全性，这就要求加密算法本身要非常安全。如果提供了无穷的计算资源，依然无法攻破，则称这种密码体制是无条件安全的。除了一次一密之外，无条件安全是不存在的，因此密码系统应尽量满足以下两个条件： 

(1) 破译密码的成本超过密文信息的价值； 

(2) 破译密码的时间超过密文信息有用的生命周期。

如果满足上面两个条件之一，则密码系统可被认为是安全的。

3. 密码设计原则

1949年，信息理论的创始人香农发表论文： Common Theory of Secrecy System证明了如下原则。

1) 混淆

混淆是指明文与密钥以及密文之间的统计关系尽可能复杂化，使破译者无法推导出相互间的依赖关系，从而加强隐蔽性。实现混淆的典型方法： 替代。

2) 扩散

扩散是让明文中的每一位(包括密钥中的每一位)直接和间接影响输出密文中的许多位，或者让密文中的每一位受制于输入明文以及密钥中的若干位，以便达到隐蔽明文的统计特性。即明文中任何一点小变动都会使得密文有很大的差异。实现扩散的典型方法： 换位。

3.1.3密码分类

密码除了隐写术以外可以分为古典密码和现代密码两大类，如图33所示。古典密码一般是以单个字母为作用对象的加密法，现代密码则以明文的二元表示作为基础的加密法。


1. 古典密码

古典密码可细分为替代密码和换位密码。

1) 替代密码

替代密码是指先建立一个替换表，加密时将需要加密的明文依次通过查表，替换为相应的字符，明文字符被逐个替换后，生成无任何意义的字符串，即密文，替代密码的密钥就是其替换表。即明文中的每一个字符(比特、字母、比特组合或字母组合)被映射为另一个字符，简单地说，就是将一个符号替换成另一个符号来形成密文。该操作主要达到非线性变换的目的。


根据密码算法加解密时使用替换表数量的不同，替代密码又可分为单表替代密码和多表替代密码。

① 单表替代密码。

单表替代密码的密码算法加解密时使用一个固定的替换表。单表替代密码又可分为一般单表替代密码、移位密码、仿射密码、密钥短语密码。

② 多表替代密码。

多表替代密码的密码算法加解密时使用多个替换表。多表替代密码有弗吉尼亚密码、希尔密码、一次一密钥密码、Playfair密码。


2) 换位密码

换位密码是一种早期的加密方法，不是用其他字母来代替已有字母，而是重新排列文本中的字母，类似于拼图游戏，所有的图块都在一个框中，只是排列的位置不同。换位加密法一般是利用几何图形(正方形、矩形)，按一个方向填写构造明文，按另一个方向读取形成密文。即明文中字符的位置被重新排序，这是一种线性变换，对它们的基本要求是不丢失信息(即所有操作都是可逆的)。

例如，将明文： Youmustdothatnow按图34逐行排列，按列读取得到密文： tuhosaYuttmdnoow。



图33密码的分类




图34逐行排列



替代和换位是加密算法的基本操作，所有加密算法都是基于这两个操作。

2. 现代密码

按密钥特征对现代密码进行分类，可以分为对称密码算法和非对称密码算法。

1) 对称密码算法

对称密码算法也称为对称密码体制、传统密码算法，是指加密和解密使用相同密钥，或加密密钥能够从解密密钥中推算出来的密码算法。在大多数的对称密码算法中，加密密钥和解密密钥是相同的，所以也称这种加密算法为秘密密钥算法或单密钥算法。按明文加密方式分，对称密码算法可以分为流(序列)密码和分组密码。

① 流(序列)密码。

流(序列)密码是将明文流以一个元素(一般是一个字母或一个比特)作为基本的处理单元，加密过程中是在密钥的控制下，将密钥流(密钥的二进制位)与等长的明文的二进制位进行模2运算输出密文，在解密过程中将密钥流与密文进行逐位模2运算输出明文(模2运算详见附录)。典型的流(序列)密码有A5/1和RC4算法。目前，A5/1算法在很多应用中已经被分组密码所替代，基于软件实现的流密码RC4算法的应用仍较为广泛。

② 分组密码。

分组密码是将明文分为固定比特长度的分组，在密钥的控制下，用固定加密算法对一组一组明文分组进行加密，再输出对应的一组一组密文； 最后一组明文长度小于分组长度时，应对最后一组进行填充。一个分组的比特数就称为分组长度。分组密码共有5种工作模式： 电码本模式、密文分组链接模式、密文反馈模式、输出反馈模式和计数器模式。典型的分组密码算法有： DES、TDES/3DES(Triple DES，三重数据加密标准)、高级加密标准(Advanced Encryption Standard，AES)、国际数据加密算法(International Data Encryption Algorithm，IDEA)和RC5。其中，DES算法因安全问题，已退出了历史舞台，但其算法思想仍具有研究价值，是密码学研究的入门级算法。TDES/3DES因效率问题，使用领域越来越少，逐步被AES算法取代。

分组密码的加解密速度快、安全性好并得到许多密码芯片的支持，可用于数据加密、数字签名、认证和密钥管理，在计算机通信和信息系统安全领域有广泛的应用。一般而言，分组密码比流（序列）密码的应用范围更广，绝大部分的基于网络的常规加密应用都使用分组密码。

对称密码算法的安全性主要取决于以下两个因素： 

① 加密算法必须足够强大，不必为算法保密，仅根据密文就能破译出消息是不可行的。

② 对称密码算法的安全性依赖于密钥的保密，泄露密钥就意味着任何人都可以对发送或接收的消息解密，所以密钥必须保密并保证有足够大的密钥空间，且要求基于密文和加密/解密算法能破译出消息的做法是不可行的。

对称密码算法的密钥长度相对较短，计算量小，加密、解密处理速度快，具有很高的数据吞吐率(硬件加密可达到每秒几百兆字节，软件加密也可以达到每秒兆字节的吞吐率)，效率高，适合大数据的加密。密文与明文的长度相同或扩张较小，是目前用于信息加密的主要算法。

由于在使用对称密码算法时，每对收发双方都需要使用唯一密钥。当发送方需要与多人通信时，发送方所拥有的密钥数量将呈几何级数增长，密钥的分发、传输和管理成为了用户负担。密钥是对称密码算法的关键，如何才能把密钥安全地送到接收方，是对称密码算法的突出问题。在使用中客户端不能直接存储对称密码算法的密钥，因为被反编译之后，密钥就泄露了，数据安全性就得不到保障，所以在实际使用中，通信双方在每一次通信中都使用一个一次性密钥，并用公钥对这个密钥进行加密，这样就免去了频繁的密钥维护以及更新过程，即使是密钥被窃取或者发生损坏，那么也只影响一次的通信过程，可以将受攻击的损失降到最低。因此，对称密码算法在分布式网络系统上使用较为困难，主要是体现在密钥传输、管理困难，使用成本较高。

2) 非对称密码算法

为解决对称密码算法中如何安全地分发、管理和传输密钥的问题，1976年，两位美国计算机学家Whitfield Diffie和Martin Hellman提出了一种崭新构思，可以在不直接传递密钥的情况下，完成加解密，这就是“Diffie Hellman密钥交换算法”。这个算法启发了其他科学家。人们认识到，加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就避免了直接传递密钥。这种新的加密模式被称为“非对称密码算法”，也叫公开密钥密码体制、双密钥密码体制。非对称密码算法基于数学问题求解的困难性，而不再是基于替代和换位方法。非对称密码算法的设计必须遵循“三公”原则，即公钥公开、密文公开和算法公开。典型的非对称密码算法有椭圆曲线密码(Elliptic Curve Cryptography，ECC)算法、RSA算法和ElGamal算法。

非对称密码算法使用具有配对关系的两个不同密钥，一个可公开，称为公钥； 另一个只能被密钥持有人自己秘密保管，且不能基于公钥推导出，称为私钥。用公钥对明文加密后，仅能使用与之配对的私钥解密，才能恢复出明文，反之亦然。因为公钥加密的信息只有私钥解得开，那么只要私钥不泄露，明文就是安全的。

3) 对称密码算法和非对称密码算法的混合使用

非对称密码算法虽然解决了对称密码算法的密钥分发问题，但存在密钥生成和加解密速度较慢，同等安全强度下，需要的密钥位数多、即密钥的长度大等问题，常用于小块数据加密。因此在实际应用中，一般将对称密码算法和非对称密码算法混合使用，即用对称密码算法加密明文，应用非对称密码算法加密对称密码算法的密钥，如应用于军队后勤管理系统、核应急安全数据通信系统的数据加密和汽车防盗等。如图35所示，当用户A想与用户B构建通信联系时，可按照如下步骤交换获得对称密钥K。



图35基于非对称密码算法的对称密码算法密钥分发



① 用户A用非对称密码算法产生一个公私钥对，其中{e，n}为公钥，{d，n}为私钥。

② 用户A将公钥{e，n}及其标识符发送给想要构建通信联系的用户B。

③ 用户B生成对称密码算法的密钥K。

④ 用户B使用用户A的公钥{e，n}对密钥K进行加密，发送给用户A。

⑤ 因为只有用户A掌握了公钥{e，n}对应的私钥{d，n}，故用户A将解密获得密钥K。至此用户A、用户B都获得了对称密码算法的私钥K作为会话密钥用于通信。


3.2典型对称密码算法AES
3.2.1AES算法的数学基础
1. 有限域

有限域亦称伽罗瓦域，是仅含有限个元素的域，它是伽罗瓦于18世纪30年代研究代数方程根式求解问题时引出的，在近代编码、计算机理论、组合数学等各方面有着广泛的应用。通常用GF(pn)表示pn元的有限域。

有限域GF(2n)——包含2n个元素。

(1) 加法、减法、乘法、除法都不能脱离该域。

(2) 乘法逆元： 对于GF中的任意元素a(除0外)，GF中存在一个元素a-1使a·a-1=1，这样的a-1被称为乘法逆元。

【思考】

整数集合是不是一个有限域？

答： 不是。因为整数集合中不是所有元素均有乘法逆元。实际上，只有元素1和－1有乘法逆元。

2. 既约多项式

既约多项式又被称为不可约多项式，其特点是不能再进行因式分解了。在AES算法中选用的既约多项式是m(x)=x8+x4+x3+x+1。该多项式可以被其他既约多项式替代。

关于既约多项式的选择。在参考文献［1］中列举了30个既约多项式，上式位列这30个既约多项式的第一个。

3. 多项式表示

{57}=01010111的多项式表示为x6+x4+x2+x+1，其中{}内的数字表示字节。


4. GF(28)的运算

1) 加法/减法

有限域GF(28)上的加法/减法即为二进制数的按位异或。

课堂练习： 

{57}+{83}={D4}

(x6+x4+x2+x+1)(x7+x+1)=x7+x6+x4+x2

2) 乘法


对于一个8位的二进制数A=a7a6a5a4a3a2a1a0来说，有如下结果：

① a7=0时，{02}·A=a6a5a4a3a2a1a00；

② a7=1时，{02}·A=(a6a5a4a3a2a1a00)(00011011)；

③ {03}·A=A({02}·A)。

3) 模运算


模运算定义是： 如果a是一个整数，n是一个正整数，定义
amodn为a除以n的非负余数。其数学符号为“mod”。例如，11mod4=4，－11mod7=3等。模运算就像普通的运算一样，它是可交换、可结合、可分配的，具有如下性质： 

① (amodn±bmodn)modn=(a±b)modn(31)

② (amodn×bmodn)modn=(a×b)modn(32)

③ ［(a×b)modn+(a×c)modn］modn=［a×(b+c)］modn(33)

④ abmodn=(amodn)bmodn(34)

式(31)的证明： 

令a=k1×n+r1，b=k2×n+r2

∴amodn=r1，bmodn=r2

(a±b)modn=((k1±k2)×n+(r1±r2))modn

=(r1±r2)modn

=(amodn±bmodn)modn

式(32)的证明：

令a=k1×n+r1，b=k2×n+r2

∴amodn=r1，bmodn=r2

(a×b)modn=(k1×k2×n2+(k1×r2+k2×r1)×n+r1×r2)modn

=(r1×r2)modn

=(amodn×bmodn)modn

式(33)的证明：

令a=k1×n+r1，b=k2×n+r2，c=k3×n+r3

∴amodn=r1，bmodn=r2，cmodn=r3

［a×(b+c)］modn

=((k1×(k2+k3)×n2+(k1×(r2+r3)+r1×(k2+k3))×n+

r1×(r2+r3))modn

=(r1×(r2+r3))modn

=(r1×r2+r1×r3)modn

=(amodn×bmodn+amodn×cmodn)modn

=［(a×b)modn+(a×c)modn］modn

式(34)的证明：

设amodn=r

∴abmodn=(a×a×…×a)modn

=(amodn×amodn×…×amodn)modn

=rbmodn

=(amodn)bmodn

3.2.2AES算法概述
1. 产生的背景


在AES算法之前，美国广泛使用的是1972年由IBM公司研发的DES算法。由于DES算法破译的不断发展，DES算法的安全性与应用前景面临非常大的挑战。随后推出的TDES/3DES是DES算法的一个更安全的变形，但由于需要进行三重DES，速度较慢。因此，美国需要设计一个不用保密的、公开的、免费的分组密码算法，用来保护21世纪政府、金融等核心部门的敏感信息，并期望用这个新算法取代渐进没落的DES算法，成为新一代数据加密标准。

因此美国对AES算法的要求有以下三点： 

(1) 安全方面： 至少和3DES算法一样安全。

(2) 速度方面： 比3DES算法快。

(3) 成本方面： 免费使用。

1997年4月15日，NIST发起征集AES算法的活动，并专门成立了AES算法工作组。1997年9月12日，联邦政府发布了征集AES算法候选算法的通知。截至1998年6月15日，NIST共收到21个提交的算法。1998年8月10日，NIST召开第一次AES算法候选会议，公布了15个候选算法。1999年3月22日，NIST召开第二次AES算法候选会议，公开了15个AES算法候选算法的讨论结果，并从里面选了5个算法进一步讨论。2000年10月2日，在进一步分析与讨论这5个算法后，正式公布由比利时密码学家Joan Daemen与Vicent Rijmen设计的Rijndael算法成为AES算法。同时，NIST发表了一篇16页的报告，总结了选择Rijndael算法作为AES算法的原因： 

(1) 不管用反馈模式还是用无反馈模式，Rijndael算法在普遍计算环境的硬件与软件实现上性能一直保持优秀； 

(2) Rijndael算法的密钥建立时间非常短，灵敏性好； 

(3) Rijndael算法的内部循环结构易于并行处理，运算容易，极低的内存需求让它特别适合在存储器有限的环境里使用； 

(4) Rijndael算法能抵抗强力与时间选择攻击。

此外，由于在AES算法的选拔过程中，参加者必须提交密码算法的详细规格书、以ANSIC和Java编写的实现代码以及抗密码破译强度的评估等材料，这就彻底杜绝了隐蔽式安全性。

2. 特点

1) 安全性好

AES算法中，每轮使用不同的常数消除了密钥的对称性，使用了非线性的密钥扩展算法消除了相同密钥的可能性，能够抵抗线性攻击。加密和解密使用不同的变换，从而消除了弱密钥和半弱密钥存在的可能性。因为AES算法的密钥长度可变，针对128/192/256位的密钥，密钥量分别为2128/2192/2256，足以抵抗穷举搜索的攻击。尽管AES128密钥的弱化版本已经受到了攻击，Niels Ferguson等在2000年实现了对加密7轮的AES128的攻击，但迄今为止尚未出现对完整AES算法的成功攻击。实践证明AES算法能抵抗穷举攻击、线性攻击、差分攻击、相关密钥攻击、插值攻击等。

2) 对资源需求小

AES算法不需要特殊的硬件加解密，所需要的软件资源少，因此非常适合应用在资源紧张的感知设备、智能终端、智能卡等物联网设备中，例如，物联网网络设备路由器、手机等智能终端、信息管理系统、无人机数据链传输、汽车防盗系统、校园卡和公交卡等的数据加密中。图36和图37分别给出了某无线路由器安全设置和手机无线局域网络（Wireless Local Area Networks,WLAN）热点上网的信息加密就是采用AES算法的实例。



图36某无线路由器安全设置




图37手机WLAN热点参数设置


3) 执行效率高

由于AES算法效率较高，因此适用于对效率有要求的实时数据加密通信。比如在使用虚拟专用网络(Virtual Private Network，VPN)或者代理进行加密通信时，既要保证数据的保密性，又要保证不能有高的延迟，所以通常会使用AES算法进行通信加密。例如，ZigBee技术中，为确保MAC帧的完整性、机密性、真实性和一致性，其MAC层使用AES算法进行加密，并且生成一系列的安全机制。在无人机数据链传输过程中，为了解决军事的数据安全问题，也常采用AES算法对其数据进行加解密。

4) 适应性强

AES算法适应性强，广泛适用于不同的CPU架构，在不同软件或硬件平台上均易实现。因此在各行各业中被广泛应用，除了逐渐取代DES算法在IPSee、SSL和ATM中的应用外，而且在远程访问服务器、移动通信、卫星通信、财政保密等方面也得到广泛使用。



3.2.3AES算法原理

AES算法是一种典型的对称密码算法、分组密码算法，分组长度为128位，而密钥长度可以为128、192或256位，对应的迭代轮数分别为10轮、12轮或14轮，分别被记作AES128算法、AES192算法和AES256算法。这里的“位”是指二进制的位数。“轮”是指加密过程中需要循环进行的所有步骤。AES算法的整个加密过程就是进行若干次轮的循环迭代。AES算法系列相关参数如表31所示。



表31AES算法相关参数





AES密钥长度（32位比特字）分组长度（32位比特字）加 密 轮 数


AES1284410
AES1926412
AES2568414


整个加密过程包括初始变换、轮变换、密钥变换三大变换。本书将以AES128算法为例进行说明，算法流程如图38所示。AES128算法每次变换处理的基本单位是一个4×4矩阵，该矩阵的每个元素是一个8位二进制数(为阅读方便，一般书写为十六进制数)。AES192算法和AES256算法的原理与AES128算法一样，只是每次加解密的数据和密钥大小分别为192位和256位。AES算法的解密算法与加密算法类似(称为逆加密算法)，主要区别在于轮密钥要逆序使用，四个基本运算都有对应的逆变换，在此不再赘述。



图38AES128算法流程


1. 初始变换

初始变换是将明文转化为明文矩阵，其流程如图39所示。




图39初始变换示意图



1) 明文转化为4×4矩阵

AES算法处理的基本单位是字节，因此首先需将输入的128位明文和128位密钥转换成以字节为基本单位的4×4矩阵。

具体变换如图310所示。



图310输入信息变为4×4矩阵



① 将128位明文P和128位密钥K分别按字节分成16字节，分别记为P=P0P1…P15和K=K0K1…K15。例如，P的十六进制表示： ABABCDCDEFEF0101ABABCDCDEFEF0101，前两个字符AB对应字节P0，最后两个字符则对应字节P15。

② 将生成的16字节按列排序为4×4矩阵，称此矩阵为状态矩阵。在算法的每一轮中，状态矩阵的内容将不断发生变化，最后的结果作为密文输出。


在实际应用中，由于明文一般不是以十六进制或二级制表示的。因此，还需对明文进行编码处理。鉴于明文可能是英文、中文、阿拉伯数字等各种形式，一般选择Unicode字符集的UTF8编码方式进行编码。

2) 矩阵异或

将明文和密钥变换得到的4×4矩阵按字节进行异或，输出一个新的4×4矩阵。初始变换在AES算法中主要起到混淆的作用。

2. 轮变换

轮变换又包括字节替换（ByteSub）、行移位变换（ShiftRow）、列混淆变换(最后一轮无列混淆替换)（MixColumn）和轮密钥加变换（AddRoundKey）四个步骤。

1) 字节替换

字节替换又被称为“S盒变换”，替换规则是： 以初始变换输出矩阵的元素为最小处理单位，把字节的高4位作为行值，低4位作为列值，以该行列值为索引从S盒(如表32所示)的对应位置取出元素作为输出。经过字节替换后的输出仍是一个4×4矩阵。

S盒变换是AES算法中唯一的非线性变换，体现在输入位和输出位之间的相关性很低，且输出值不是输入值的线性数学函数，这是保障AES算法安全的关键。优点是可查表完成，计算速度快。




表32S盒





y

0123456789ABCDEF


x
0637C777BF26B6FC53001672BFED7AB76
1CA82C97DFA5947F0ADD4A2AF9CA472C0
2B7FD9326363FF7CC34ASE5F171D83115
304C723C31896059A071280E2EB27B275
409832C1A1B6ESAA0523BD6B329E32F84
553D100ED20FCB15B6ACBBE394A4C58CF
6D0EFAAFB434D338545F9027F503C9FA8
751A3408F929D38F5BCB6DA2110FFF3D2
8CD0C13EC5F974417C4A77E3D645D1973
960814FDC222A908846EEB814DE5E0BDB
AE0323A0A4906245CC2D3AC629195E479
BE7C8376D8DD54EA96C56F4EA657AAE08
CBA78252E1CA6B4C6E8DD741F4BBD8B8A
D703EB5664803F60E613557B986C11D9E
EE1F8981169D98E949B1E 87E9CE5528DF
F8CA1890DBFE6426841992D0FBO54BB16


【练习】

初始变换中某明文的十六进制数为{EA}，请写出该字节经字节替换后的输出是什么。

2) 行移位变换

行移位变换的具体步骤如图311所示。经过字节替换的输出矩阵S的第0行不变，第1行循环左移1字节，第2行循环左移2字节，第3行循环左移3字节，形成新的矩阵S′，S′i.j表示行移位变换输出矩阵S′第i行、第j列元素，i∈［0，3］，j∈［0，3］。行移位变换属于置换，是一种线性变换，本质上是把数据打乱重排，起到扩散的作用。



图311行移位变换示意图



3) 列混淆变换

列混淆变换是通过矩阵相乘来实现的，具体方式是： 行移位变换的输出矩阵S′与固定系数矩阵C做乘法后模多项式x4+1。计算过程如下： 

根据有限域GF(28)上多项式的表示规则，行移位变换输出矩阵S′第j(j∈［0，3］)列的4个元素(S′0.j，S′1.j，S′2.j，S′3.j)可以表示为多项式S′0.j+S′1.j·x+S′2.j·x2+S′3.j·x3，它经过列混淆变换后的输出记为(b′0.j，b′1.j，b′2.j，b′3.j)，表示为多项式b3.j·x3+b2.j·x2+b1.j·x+b0.j，由式(35)计算获得。符号{}内的数表示字节。


b3.j·x3+b2.j·x2+b1.j·x+b0.j
=((S′0.j+S′1.j·x+S′2.j·x2+S′3.j·x3)·c(x))mod(x4+1)
(35)

其中，c(x)={03}x3+{01}x2+{01}x+{02}。


(S′0.j+S′1.j·x+S′2.j·x2+S′3.j·x3)·c(x)
=(S′3.j·x3+S′2.j·x2+S′1.j·x+S′0.j)·({03}x3+{01}x2+{01}x+{02})
=(S′3.j·{03})x6+(S′3.j·{01}+S′2.j·{03})x5+
(S′3.j·{01}+S′2.j·{01}+S′1.j·{03})x4+
(S′3.j·{02}+S′2.j·{01}+S′1.j·{01}+S′0.j·{03})x3+
(S′2.j·{02}+S′1.j·{01}+S′0.j·{01})x2+
(S′1.j·{02}+S′0.j·{01})x+S′0.j·{02}
(36)

由于ximod(x4+1)=ximod4，所以有式(37)~式(39)成立。


((S′3.j·{03})x6)mod(x4+1)=(S′3.j·{03})x2(37)
((S′3.j·{01}+S′2.j·{03})x5)mod(x4+1)=(S′3.j·{01}+S′2.j·{03})x(38)
((S′3.j·{01}+S′2.j·{01}+S′1.j·{03})x4)mod(x4+1)
=(S′3.j·{01}+S′2.j·{01}+S′1.j·{03})(39)


所以


b3.j·x3+b2.j·x2+b1.j·x+b3.j
=((S′0.j+S′1.j·x+S′2.j·x2+S′3.j·x3)·c(x))mod(x4+1)
=(S′3.j·{02}+S′2.j·{01}+S′1.j·{01}+S′0.j·{03})x3+(S′3.j·{03}+
S′2.j·{02}+S′1.j·{01}+S′0.j·{01})x2+(S′3.j·{01}+S′2.j·{03}+
S′1.j·{02}+S′0.j·{01})x+
(S′3.j·{01}+S′2.j·{01}+S′1.j·{03}+S′0.j·{02})(310)


把式(310)写成矩阵形式，即式(311)。

02030101010203010101020303010103S0.0S0.1S0.2S0.3S1.0S1.1S1.2S1.3S2.0S2.1S2.2S2.3S3.0S3.1S3.2S3.3=S′0.0S′0.1S′0.2S′0.3S′1.0S′1.1S′1.2S′1.3S′2.0S′2.1S′2.2S′2.3S′3.0S′3.1S′3.2S′3.3
(311)

所以，系数矩阵C=02030101010203010101020303010103

上述矩阵乘法和加法都是定义在基于有限域GF(28)上的二元运算上，并不是通常意义上的矩阵乘法和加法，而是模m(x)=x8+x4+x3+x+1上的加法和乘法。其中，m(x)是AES算法设计者选的有限域GF(28)上的不可约多项式(也称为既约多项式)，是指不能写成两个次数较低的多项式之乘积的多项式。有限域GF(28)上加法计算规则等价于两个字节的异或。由式(311)可知，只需计算系数{01}、{02}和{03}这3个数的有限域GF(28)上的乘法，即(Ci.j·S′i.j)modm(x)的值，其中Ci.j表示系数矩阵C中的元素。计算规则如下： 

① 计算乘以{01}。

字节{01}表示成二进制数为00000001，对应的有限域GF(28)上的多项式就是1。对于任何S′i.j有式(312)成立。

({01}·S′i.j)modm(x)=S′i.j(312)

② 计算乘以{02}。

计算({02}·S′i.j)modm(x)需两步完成： 第一步需计算{02}·S′i.j，第二步需计算({02}·S′i.j)modm(x)。

步骤一： 计算{02}·S′i.j。

由于字节{02}表示成二进制数为00000010，对应的有限域GF(28)上的多项式就是x。{02}·S′i.j相当于字节S′i.j对应的多项式乘x，相当于S′i.j表示二进制数左移一位，即S′i.j对应的多项式的系数不变、次数加1。

步骤二： 计算({02}·S′i.j)modm(x)。

步骤一计算得到的结果，如果多项式次数小于8，即对应的二进制数最高位为0，相当于({02}·S′i.j)<m(x)，所以({02}·S′i.j)modm(x)={02}·S′i.j。

步骤一计算得到的结果，如果多项式次数等于8，即对应的二进制数最高位为1，就需要modm(x)。此时多项式一定小于2m(x)，所以modm(x)的余式就相当于{02}·S′i.j－m(x)的结果。已知有限域GF(28)上的减法也是进行异或运算。由于{02}·S′i.j只涉及8位二进制数，因此只需与m(x)的后8位二进制数00011011(十六进制数就是0x1b)进行异或运算即可。

综上，对于任何S′i.j，({02}·S′i.j)modm(x)相当于先把字节S′i.j表示的二进制数左移1位。移位后，若最高位a7=1，则将该二进制数的后8位与{1b}进行异或运算得到结果； 若最高位a7=0，取后8位就是结果。数学表述如下： 

令S′i.j表示的二进制数S′i.j=a7a6a5a4a3a2a1a0：

当a7=0时，{02}·S′i.j=a6a5a4a3a2a1a00；

当a7=1时，{02}·S′i.j=(a6a5a4a3a2a1a00)(00011011)。

③ 计算乘以{03}。

因为在有限域GF(28)上，{03}={01}{02}，所以有式(313)成立。

({03}·S′i.j)modm(x)=({02}·S′i.j{01}·S′i.j)modm(x)(313)

【例】计算下列矩阵经过列混淆后的值。

87F24D976E4C90EC46E74AC3A68CD895

解： 

第一步： 根据式(311)有如下等式成立。

0203010101020301010102030301010387F24D976E4C90EC46E74AC3A68CD895=S′0.0S′0.1S′0.2S′0.3S′1.0S′1.1S′1.2S′1.3S′2.0S′2.1S′2.2S′2.3S′3.0S′3.1S′3.2S′3.3

所以S′0.0={02}·{87}+{03}·{6E}+{01}·{46}+{01}·{A6}。

第二步： 计算{02}·{87}。

① 将{87}转化为二进制，{87}=(1000 0111)。

② 判断(1000 0111)最高位的情况。

③  因为a7=1，所以{02}·{87}=(0000 1110)(0001 1011)=(0001 0101)。

第三步： 计算{03}·{6E}。

① 将{6E} 转化为二进制，{6E}=(0110 1110)。

② 按如下规则计算： {03}·A=A({02}·A)。

③ 计算{02}·{6E}。

因为{6E}二进制数的最高位为0，所以{02}·{6E}=(1101 1100)。

④ 计算{03}·{6E}={6E}({02}·{6E})=(1011 0010)。

第四步： 继续计算如下。


{02}·{87}=(0001 0101)
{03}·{6E}=(1011 0010)
{01}·{46}=(0100 0110)
{01}·{A6}=(1010 0110)

(0100 0111)


所以S′0.0={02}·{87}+{03}·{6E}+{01}·{46}+{01}·{A6}={47}。

其余元素按上述计算，最后结果为

4740A34C37D4709F94E43A42EDA5A6BC

4) 轮密钥加变换

将列混淆变换后的结果与轮密钥进行异或运算，其结果作为后续变换的输入。其中，轮密钥是参与本轮运算的密钥。从图38可知，除初始密钥外，AES算法参与运算的每一轮的密钥都是由上一轮的密钥变换而来的。由图312所示的轮密钥加变换示意图可知，虽然轮密钥加变换非常简单，却能影响矩阵中每一位。



图312轮密钥加变换示意图


3. 密钥变换

密钥变换是以初始密钥的4×4矩阵为变换对象，以矩阵列为最小单位生成的，具体包括以下四个步骤： 密钥排列、置换、与轮常量异或、生成下一轮密钥的其他列。下文以AES128算法第二轮密码生成为例进行说明。密钥变换的目的是产生AES算法参与运算的每一轮密钥。因为AES128算法内部其实不只执行一轮加密，而是一共执行了11轮加密，所以AES算法会通过一个简单快速的混合操作，根据初始密钥依次生成后面10轮的密钥，每一轮的密钥都是依据上一轮生成的，所以每一轮的密钥都是不同的。因此密钥变换又称为密钥扩展。尽管很多人抱怨说这种方式太简单了，经实践和理论证明这其实已经足够安全了。

1) 密钥排列

① 按列将输入的128位密钥转换为4×4矩阵。

② 把初始密钥rk［0］最后一列的第一字节放到最后一字节的位置上，其余字节依次向上移动一位，经过密钥排列后的这一列称为排列列。示意图如图313所示。


2) 置换

把排列列经过一个S盒替换后，排列列就会被映射为一个崭新的列，称这个崭新的列为置换列。示意图如图314所示。



图313排列列生成示意图




图314置换列生成示意图




3) 与轮常量异或

把置换列和轮常量异或生成第二轮密码的最后一列。轮常量如表33所示，共四字节。轮常量的主要作用有： 一是增加密钥编排中的非线性； 二是消除AES算法中的对称性。这两种属性都是抵抗某些分组密码攻击所必要的。



表33轮常量





轮数轮常量轮数轮常量

第1轮01 00 00 00第6轮20 00 00 00
第2轮02 00 00 00第7轮40 00 00 00
第3轮04 00 00 00第8轮80 00 00 00
第4轮08 00 00 00第9轮1B 00 00 00
第5轮10 00 00 00第10轮36 00 00 00


4) 生成下一轮密钥的其他列

用第二轮密钥的最后一列和初始密钥的第一列异或得到第二轮密钥的第一列； 用第二轮密钥的第一列和初始密钥的第二列异或得到第二轮密钥的第二列； 用第二轮密钥的第二列和初始密钥第三列异或得到第二轮密钥的第三列。至此，第二轮密钥4×4矩阵的四列就全部生成完毕。其过程如图315所示。rk［1］表示第二轮密码。



图315生成下一轮密钥的其他列


后续轮密钥按上述过程生成，只是在与轮常量异或时轮常量有所不同而已。




辩证法中的对立统一规律


世界上任何事物的内部和事物之间都包含矛盾的两个方面，矛盾的双方既对立又统一，事物的运动发展在于自身的矛盾运动。密码学自诞生起就体现了矛盾的对立统一性，密码学作为一门学科包含密码编码学和密码分析学，也就是“攻”与“防”两个对立的方面，这对矛盾不断促进了密码学的发展。世上没有单一性质的、绝对的事物。这一规律也体现于密码学中。


3.2.4针对AES算法的攻击

目前，针对AES算法的攻击主要有功耗分析攻击、故障注入攻击、差分代数分析攻击、不可能差分攻击、零相关线性攻击、子空间路径攻击、混合差分攻击、交换攻击、折回镖攻击和中间相遇攻击等。目前而言，针对AES算法的所有已知攻击均不存在比穷尽密钥搜索更快的攻击。

3.3典型非对称密码算法RSA
3.3.1RSA算法的数学基础
1. 素数

素数又叫质数，是在大于1的自然数中只能被1和其自身整除的数。每个自然数都可以唯一地分解成有限个素数的乘积，素数因此构成了自然数体系的基石。2300多年前，古希腊数学家欧几里得在《几何原本》中证明了素数有无穷多个，并提出一些素数可写成“2p-1”(其中p也是素数)的形式。

【梅森素数】

由于这种特殊形式的素数具有独特数学性质，许多著名数学家以及无数数学爱好者对它情有独钟。其中，17世纪的法国数学家、法兰西科学院奠基人梅森在这方面有过重要贡献。为了纪念梅森，数学界就将“2p-1”型的素数称为“梅森素数”。梅森素数貌似简单，但当指数p值较大时，其素性检验的难度就会很大。正如梅森推测： “一个人，使用一般的验证方法，要检验一个15位或20位的数字是否为素数，即使终生的时间也是不够的。”享有“数学英雄”美誉的瑞士数学家及物理学家欧拉1772年在双目失明的情况下，以顽强毅力靠心算证明了231-1是第8个梅森素数； 该素数有10位，堪称当时世界上已知的最大素数。在“手算笔录年代”，人们历尽艰辛，共计才找到12个梅森素数。随着计算机时代的到来，大大加快了梅森素数的探究步伐。1996年初，美国数学家及程序设计师沃特曼编制了一个梅森素数计算程序，并把它放在网页上免费使用。这一计算程序就是著名的互联网梅森素数大搜索（Great Internet Mersenne Prime Search，GIMPS）项目，也是全球首个基于互联网的网格计算项目。目前，全球有近70万人参与该项目，动用了超过180万核中央处理器联网来寻找梅森素数(如图316所示)——这在数学史上前所未有，在科学史上也极为罕见。



图316GIMPS项目


用因式分解法可以证明，若2p-1是素数，则指数p也是素数； 反之，当p是素数时，2p-1却未必是素数。前几个较小的梅森数大都是素数，然而梅森数越大，梅森素数也就越难出现。目前仅发现五十几个梅森素数。2019年，一位名叫帕特里克·罗什的美国人利用GIMPS项目，成功发现第51个梅森素数282589933-1； 该素数有24862048位，是迄今为止人类发现的最大素数。如果用普通字号将它打印下来，其长度将超过100千米！是否存在无穷多个梅森素数是未解决的著名难题之一。

寻找梅森素数最新的意义是： 它促进了分布式计算技术的发展。从最新的17个梅森素数是在因特网项目中发现这一事实，可以想象到网络的威力。分布式计算技术使得用大量个人计算机去做本来要用超级计算机才能完成的项目成为可能，这是一个前景非常广阔的领域。它的探究还推动了快速傅里叶变换的应用。

梅森素数在实用领域也有用武之地，现在人们已将大素数用于现代密码设计领域。其原理是： 将一个很大的数分解成若干素数的乘积非常困难，但将几个素数相乘却相对容易得多。在这种密码设计中，需要使用较大的素数，素数越大，密码被破译的可能性就越小。




由于梅森素数的探究需要多种学科和技术的支持，也由于发现新的 “大素数” 所引起的国际反响，使得对于梅森素数的研究能力已在某种意义上标志着一个国家的科技水平，而不仅仅是代表数学的研究水平。我国数学家及语言学家周海中于 1992 年在《梅森素数的分布规律》一文中关于梅森素数分布的研究成果被国际上命名为“周氏猜测”，如图317所示。通过向学生介绍我国数学家的成就，激发学生的爱国热情和民族自豪感，以及学好该课程的信心和动力。




图317我国数学家及语言学家周海中和“周氏猜测”


2. 互质


互质又被称为互素，若N(N≥2)个整数的最大公因数是1，则称这N个整数互质。互质的主要性质有： 

(1) 任意两个质数构成互质关系，比如13和61。

(2) 一个数是质数，另一个数只要不是该数的倍数，两者就能构成互质关系，比如3和10。

(3) 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。

(4) 1和任一自然数都是互质关系，比如1和99。

(5) p是大于1的整数，则p和p-1构成互质关系，即相邻的两个自然数是互质数，比如57和56。

(6) p是大于1的奇数，则p和p-2构成互质关系，即相邻的两个奇数是互质数，比如17和19，17和15。

3. 大素数因子分解理论

已知两个大的质数，计算其乘积是很简单的。但反过来，已知两个大质数的乘积，将其分解为两个质数是非常困难的，即因其计算量非常大，目前还没有算法在较短时间内能有效求解该问题。表34给出了在现有计算机算力下，完成大整数因子分解需要的时间。但随着量子计算机的发展，这一分解时间将大幅缩短。




表34完成大数分解需要的时间





整数n的十进制位数因子分解的运算次数所需计算时间(每微秒一次)


501.4×10103.9小时
759.0×1012104天
1002.3×101574年
2001.2×10233.8×109年
3001.5×10294.0×1015年
5001.3×10394.2×1025年



4. 欧拉定理

如果数x和数n互质，那么x(n)=1modn。其中，(n)=(p－1)(q－1)是n的欧拉函数值，表示小于n的素数的个数，即在小于或等于n的正整数中与n互质的数的个数，其中，p和q都是素数。

5. gcd(a，b)最大公因数

gcd(a，b)表示两个正整数a，b的最大公因数(a>b且amodb不为0)。gcd(a，b)的计算方法主要有欧几里得算法。

6. 欧几里得算法

给定整数a，b，且b>0，重复使用带余除法，即用每次的余数为除数去除上一次的除数，直至余数为0。最后一个不为0的余数就是a和b的最大公因数gcd(a，b)。

【例】求gcd{224，34}。

解： 

gcd{224，34}余数20

=gcd{34，20}余数14

=gcd{20，14}余数6

=gcd{14，6}余数2

=gcd{6，2}余数0

=2

所以gcd{224，34}=2。

7. 同余关系

若两个自然数对于一个给定的模数有相同的余数，则称这两个数具有同余关系。例如7≡4mod3，即7和4被3除的余数相同，都为1，则7和4具有同余关系。

3.3.2RSA算法概述

RSA算法是1977年由罗纳德·李维斯特、阿迪·萨莫尔和伦纳德·阿德曼一起提出的。1987年7月首次在美国公布，当时他们三人都在麻省理工学院工作实习。RSA就是他们三人姓氏开头字母拼在一起组成的。2002年,RSA算法的三位发明人因此获得图灵奖。RSA算法的安全性是基于大数分解的难题，其公钥和私钥是一对大素数的函数，虽然迄今为止还没有从理论上证明破解RSA算法的难度等价于分解两个大素数之积，但RSA算法能抵抗到目前为止已知的所有密码攻击，已成为公钥密码的国际标准，一直是最广为使用的非对称密码算法。如表34所示，这种算法的密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是768位二进制。也就是说，长度超过768位的密钥，还无法破解(至少没人公开宣布)。1024位的RSA密钥基本安全，2048位的密钥极其安全。

只要有网络的地方，就有RSA算法。例如，网络服务器端生成公钥和私钥。在浏览器向服务器索取网页时，服务器将公钥存放在网页中发送给用户A。用户A在发送消息给服务器的时候用公钥给明文加密，再将密文发送给服务器。在A的发送过程中，如果密文被黑客B截获，B无法破解A发送的密文。因为经RSA算法公钥加密的密文必须由私钥解密，虽然B可以获得服务器分发的公钥，但是经公钥加密的密文不能由公钥解密。服务器收到A发送的密文后，用私钥将其解密，将处理结果用私钥加密后再发送给A。这时就可能存在风险，如果服务器返还给A的密文被B截获，虽然B无法解密A发出的密文，但是B有公钥，可以解密服务器发出的密文。通过将服务器发出的密文解密，B可以得到对自己有潜在价值的信息，这样就有可能对A产生不利影响。


为了避免服务器返回的密文被B截获并用公钥破解，A也可以主动利用RSA算法生成密钥对，将生成的公钥做好起止标记放在明文的某个位置，用服务器分发的公钥给这个新的明文加密后再发送给服务器； 服务器收到密文后用自己的私钥解密，按照起止标记提取出A分发的公钥，用此公钥给处理结果加密，将密文返回给A。虽然B可以截获此密文但是无法破解，因为此密文不是用服务器的私钥加密。当A收到服务器返回的密文后，用自己保存在网页中的临时私钥将密文解密得到明文，这样就保证了通信的安全性。




他们的名字无人知晓，他们的功绩永世长存。密码学背后默默付出的英雄们！

目前我们能了解到的密码学进展，都是军方、保密机构允许公开的。在密码学这个特殊的行业，有很多默默工作、不计个人名利的英雄们。他们并不是没有机会像RSA算法三位发明人一样获得图灵奖的殊荣，而是出于国家民族安全需要，暂不能将他们的研究成果公开。或许只能等他们的研究成果彻底过时，官方才会公布资料； 或许他们永远无法被人知晓。据相关资料记载，事实上，早在李维斯特、萨莫尔和阿德曼三人独立发明RSA概念的几年之前，RSA的理念实际上已被英国政府通信总部(Government Communications Headquarters，GCHQ)的克利福·柯克斯(Cliff Cocks)提出。因为英国GCHQ的工作是保密的，甚至在机密的加密技术领域内也绝非广为人知。因此，学术界最终认定RSA算法的发明人仍是李维斯特、萨莫尔和阿德曼，因此他们在2002年获得图灵奖。这并没有在任何程度上削弱李维斯特、萨莫尔和阿德曼三人成就的意思，只是希望后人们永远记住密码学背后默默奉献的英雄们！他们的名字可能无人知晓，但他们的功绩将永世长存。推荐电影《暗算》和书籍《红军破译科长曹祥仁》。

3.3.3RSA算法原理

RSA算法可分为密钥生成、加密、解密三部分。

1. 密钥生成

在RSA算法中，须生成两个密钥，一个是可以公开的密钥，一般称为“公钥”； 另一个是不能公开的密码，一般称为“私钥”。RSA算法密钥生成包括以下五步： 


(1) 选取两个互质的大素数p和q，且p和q均需保密，比如p和q选择100~200位十进制数或更大的素数。

(2) 按式(314)计算其欧拉函数： 


(n)=(p－1)(q－1)(314)
n=p×q(315)


式中，n表示一个十进制数，n转换为二进制的位数即为RSA算法密钥的位数，一般取1024位，重要场合取2048位。使用中称“多少位RSA算法”中的“位”就是指密钥的二进制位数。因此，p和q具体的长度是由n确定的。

(3) 选一个公开的整数e，满足1<e<(n)，且gcd{(n)，e}=1，实际中e一般取65537。

(4) 计算整数d，满足d×e≡1mod(n)。其中符号≡表示同余关系，所以有式(316)成立。

d=［k(n)+1］/e(316)

式中，k为整数。式(316)具体推导如下。

由同余关系可知，d×e≡1mod(n)可表示为(d×e)mod(n)=1mod(n)。由于(n)为两个大素数的欧拉函数，所以(d×e)mod(n)=1mod(n)=1，表示该式(d×e)除以(n)的余数为1，所以(d×e)=k(n)+1，即d=［k(n)+1］/e，且d和e互质。

(5) 确定{e，n}为公开密钥，{d，n}为秘密密钥。

2. 加密

(1) 将明文进行分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n。

(2) 分别对每个明文分组按式(317)进行如下加密运算： 

ci=meimodn(317)

式中，mi表示第i个分组的明文，mi<n(这里假设mi以十进制数表示)； ci表示mi加密后的密文。

3. 解密

将密文ci按式(318)进行如下计算，得到对应的分组明文mi。

mi=cdimodn(318)

将所有明文分组依次排序，即解密出对应的明文。

【例】在RSA公钥密码体制中，设p=7，q=13，e=5。当明文m=10时，求d和相应的密文。

1) 密钥生成

(1) 计算欧拉函数。


n=p×q=7×13=91
(n)=(p－1)(q－1)=6×12=72


(2) 计算d。

d=［k(91)+1］/e=(72k+1)/e=29，k为整数。

(3) 确定公钥和私钥。

确定{5，91}为公钥，{29，91}为私钥。

2) 加密

c=memodn=105mod91=82

3) 结果验证

m=cdmodn=8229mod91=?

其中，8229是一个非常大的数，已经超出计算机所允许的整数取值范围，那如何才能计算出来呢？这里要运用到3.2.1节学习过的模运算性质，通过快速指数法来计算： 


(amodn×bmodn)modn=(a×b)modn
abmodn=(amodn)bmodn


【快速指数法】

8229mod91

=(82×8228)mod91

=(82mod91×8228mod91)mod91

=(82×(822)14mod91)mod91

=(82×672414mod91)mod91

=(82×((6724mod91)14)mod91)mod91

=(82×(8114mod91)mod91

=(82×(812)7mod91)mod91

=(82×(65617mod91))mod91

=(82×(6561mod91)7mod91)mod91

=(82×97mod91)mod91

=(82×9)mod91

=10

注： 当a<n时，amodn=a，所以82mod91=82。

由于RSA算法的计算量较大，在实际应用中很少用于大块的数据加密，通常在混合密码系统中用于加密会话的密钥，或用于数字签名和身份认证等短消息加密。

3.3.4针对RSA算法的攻击
1. 共模攻击


在存在密钥统一生成的中央机构的情况下，为了节约资源等原因，中央机构往往会选择同一个整数n，并利用n给不同的用户产生各自的公钥私钥对： (e1，d1)，(e2，d2)，…，(ei，di)，则第i个用户的公钥和私钥分别为(ei，n)和(di，n)。此时，任意一个用户都可以使用自己的公钥私钥对计算出所有用户公用的(n)，进而计算出任意其他用户的私钥(di，n)，从而解密他们的密文。

共模攻击的另一种情况是对于一个外部的攻击者，在不知道任意一个公钥对应私钥的情况下的攻击方法。假如有一个系统内部的广播消息，使用两组或以上的公钥加密，分别发送给对应的系统用户。外部的攻击者在监听到两个密文(这两个密文加密的消息是相同的)的情况下，可以使用扩展欧几里得算法高效地恢复出加密的消息。假设两个密文分别被公钥(e1，n)和(e2，n)加密成如式(319)所示的形式： 


c1=me1modn
c2=me2modn

(319)

此时，假设e1和e2互素，则攻击者可以使用扩展欧几里得算法计算出s1e1+s2e2=1。然后通过式(320)所示过程恢复出明文m： 

cs11·cs22modn=ms1e1+s2e2modn=m(320)

2. 小指数攻击


小指数攻击存在两种形式，分别是小私钥指数d攻击和小公钥指数e攻击。

1) 小私钥指数d攻击

小私钥指数d攻击，即选择一个较小的d，虽然可以加快解密速度，但是这也使RSA加密参数的选择极其容易遭受穷举d攻击。即使当选择d的长度约为λ/2时(λ为p和q的长度)，依然存在某些攻击方法来恢复出d。

2) 小公钥指数e攻击

当公钥中的e值过小时，尤其是选择e=3时，RSA加密算法存在更多的攻击点。例如，当使用e来加密一个长度小于|n|/3的消息时，即根据式(316)计算密文c=memodn。由于m的长度小于|n|/3，因此c在数值上小于n，即在加密过程中没有进行任何模运算。此时消息m可以直接通过计算c的实数立方根得出。

小公钥指数e攻击需要限定加密消息长度小于|n|/3，利用中国剩余定理，该攻击可以将攻击的消息扩展到任意长度。由于共模攻击的存在，中央机构给三个用户分别选择了三组不同的大素数(p1，q1)、(p2，q2)和(p3，q3)，根据式(315)产生了对应的n1、n2和n3，但是却使用了同样的e=3。运用上述三个不同的公钥(n1，3)、(n2，3)和(n3，3)对消息m加密，可以得到三份密文：


c1=m3modn1
c2=m3modn2
c3=m3modn3


此时，如果攻击者得到这三份密文c1、c2和c3及对应的公钥(n1，3)、(n2，3)和(n3，3)，可以利用中国剩余定理解密消息m。具体过程如下： 

令n=n1×n2×n3，则可以得到一个密文c，即


c=c1modn1
c=c2modn2
c=c3modn3
c=m3modn
(321)

由于m<n，且m3<n，因此有c=m3，即明文m可通过计算密文c的实数立方根直接获得。因此抵抗小指数攻击最简单的办法就是e和d都取较大的值。

综上，因为RSA算法密钥的产生受素数产生技术的限制，所以也有它的局限性。

(1) 密钥的产生受素数产生技术的限制，因而难以做到一次一密，分组长度太大。

(2) 为保证安全性，n至少需要600bit。但这样做的代价是运算量很高，加解密速度比对称密码算法慢几个数量级。随着大整数素因数分解算法的改进和计算机计算能力的提高，对n的长度要求在不断增加，因此不利于实现数据格式的标准化。


3.4国产密码算法
3.4.1国产密码概述

国产密码算法简称国密算法，是由国家密码管理局认定的拥有自主知识产权的密码算法。2013年斯诺登事件曝光，美国国家安全局(National Security Agency，NSA)曾与加密技术巨头——RSA公司签订秘密交易，交易中NSA可以获取RSA加密算法中的后门，这一事件标志着加密算法的自主性缺失成为国家信息安全的威胁。我国自2002年以来就不断推动研发国密算法，并于2012年批准SM2、SM3、SM4等密码学算法作为行业标准。目前已经公布的国密算法包括SSF33、SM1、SM2、SM3、SM4、SM7、SM9以及祖冲之（ZUC）密码等算法，其中SM1、SM4、SM7、ZUC密码是对称密码算法； SM2、SM9是非对称密码算法； SM3是哈希算法。

3.4.2祖冲之密码算法

祖冲之密码算法，是一种基于线性返回移位寄存器设计的密码算法，于2012年3月成为密码行业标准，于2016年10月成为国家标准，2018年4月以补篇形式进入，由ISO及IEC联合制定国际标准ISO/IEC 18033—4，是中国第一个成为国际密码标准的密码算法，广泛应用于无线通信领域，我国4G入网检测已要求手机终端全部支持祖冲之密码算法。

祖冲之密码算法共有三层： 线性反馈移位寄存器、比特重组和非线性函数。线性反馈移位寄存器定义在素数域上，增加了线性复杂度，提高了算法安全性； 比特重组也使攻击变得困难； 非线性函数使用S盒、异或等运算，降低了能耗和硬件门电路数目。

祖冲之密码算法的软硬件实现是近年来信息安全领域的热点，高通公司研究人员在高通700MHzHexagonDSP上实现了祖冲之密码算法，其性能如表35所示。Lei Wang等给出了基于现场可编程门阵列(Field Programmable Gate Array，FPGA)的几种优化硬件实现，其性能如表36所示。可见祖冲之密码算法在软硬件实现上都有优异的性能。



表35祖冲之密码算法软件实现性能




长度/Byte1282565121024150020484096


速度/bit/轮0.39890.54600.66940.75470.78650.80600.344




表36祖冲之密码算法硬件实现性能





序号频率/MHz面积/m2吞吐量/Mbps吞吐量/Mbps


112631120166.5
210835624569.7
3222.4575711112.3



3.4.3国密算法与国际加密算法对比
1. SM1与AES算法

SM1算法是国家密码管理局审批的密码算法，其分组长度和密钥长度都是128bit，但该算法不公开，仅固化在加密芯片中。SM1算法安全性和软硬件实现性能与AES算法相当，表37给出SM1与AES算法的相关对比。



表37SM1与AES算法对比





项目SM1算法AES算法


计算结构
基于椭圆曲线
Rijndael结构
存储空间长度
128bit
128/192/256bit
加密解密速度
约几十兆bps
约50Mbps


2. SM4与DES算法

SM4算法是我国自主设计的分组对称密码算法，是无线局域网标准的分组数据算法，密钥长度和分组长度为128bit。SM4算法在计算过程中加入了非线性变换，安全性高于3DES算法。表38给出了SM4与DES算法的相关对比。



表38SM4与DES(3DES)算法对比





项目SM4算法DES(3DES)算法


计算轮数32轮16轮
分组长度128bit64bit
密钥长度128bit64bit
加密解密速度约几十兆bps约50Mbps
性能硬件、软件实现均快硬件实现较快，软件实现较慢
安全性较高较低(3DES较高)


3. SM2与RSA算法

SM2算法由国家密码管理局于2010年12月17日发布，全称为椭圆曲线算法。RSA算法的安全性基于素数分解问题，其复杂度是亚指数级的，SM2算法基于离散对数问题，目前数学上还找不到亚指数级的算法求解该问题，所以同等安全性要求下SM2算法需要的密钥长度更短。SM2与RSA算法对比如表39所示。



表39SM2与RSA算法对比





项目SM2算法RSA算法


计算结构基于椭圆曲线基于可逆模幂运算
复杂度指数级亚指数级
加密解密速度约几兆bps约0.1Mbps
性能硬件、软件实现均快硬件实现较快，软件实现较慢
相同安全性所需公钥位数较少(160位的SM2与1024位的RSA安全性相近)较多


国密算法相比于国际加密算法其安全性和执行速度具有一定的优势。国密算法与国际加密算法相比，每组算法执行占用内存大小相当，作为我国拥有自主知识产权的加密算法，能够在不依赖别国技术的情况下保障信息安全。


本章小结

本章首先从密码学的基本概念出发，介绍密码学的历史、密码系统、密码技术的分类等基本知识。随后，分别介绍了物联网实际应用中的典型对称密码算法AES算法和非对称密码算法RSA算法的基本原理。最后，在此基础上介绍了几种国产密码算法。

思考与练习

1. 红蓝军通过对称密码通信需要多少个密钥？

2. 简述密码系统的组成。哪些要素是必须保密的？哪些要素是可以公开的？

3. 试分析下例中的哪部分是密钥K，加密算法E，解密算法D。

密文： KCOCUQNFKGT

明文： IAMASOLDIER

4. 对称密码体制和非对称密码体制有什么区别？

5. Alice生成了一个公钥和一个私钥。不幸的是，她后来把私钥弄丢了。试回答如下问题： 

(1) 其他人能发送给她加密信息吗？

(2) 她能解密以前收到的消息吗？

(3) 她能对文档进行数字签名吗？

(4) 其他人能验证她以前签过名的文件吗？

6. 假设在下列算力条件下：

(1) 每台计算机每秒可尝试1020个密钥； 

(2) 共有10100台计算机； 

(3) 所有的计算机可运转1020年。

如果依然要保证无法通过暴力破解遍历整个密钥空间，则对称密码的密钥需要达到多少bit？请从下列选项中选出正确的答案。

A. 只要512bit就够了

B. 至少需要1024bit

C. 至少需要4096bit

D. 至少需要10000bit

E. 100000bit也不够


注： 这里假设的算力是远远超过实际情况的。相比之下，超级计算机“京”每秒可执行1016次浮点运算，宇宙中所有粒子的总数为1087个左右，宇宙的年龄为1011年左右。

7. AES算法中S盒的作用是什么？若S2的输入为110101，其输出是什么？

8. 说明RSA算法中密钥产生和加解密的过程。如何寻找大素数？

9. 柯克霍夫原则是()。

A. 密码系统的任何细节已为人悉知，该密码系统不可用

B. 密码系统的任何细节已为人悉知，该密码系统仍可用

C. 密码系统的任何细节已为人悉知，只要密钥未泄露，它也应该是安全的

D. 密码系统的任何细节已为人悉知，密钥泄露了也是安全的