第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)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