密码学的理论基础

引言密码学简介•密码学是一门古老而年轻的科学，在当今的信息时代，大量敏感信息如法庭记录、私人文档、软件源代码、银行交易、保险单据等常常通过公共通信设施或计算机网络来进行交换。•为了保证这些信息的私密性、完整性、真实性，必须使用技术手段对其进行处理。–私密性:对信息处理后，保证让他人不能读懂。–真实性:对信息处理后，保证他人不能篡改信息（改了之后会被接收者发觉）。–完整性:对信息处理后，保证他人不能从原始信息中删除或插入其它信息（删除或插入后会被接收者发觉）。密码学常识–密码学（cryptology）作为数学的一个分支，是密码编码学和密码分析学的统称。使消息保密的技术和科学叫做密码编码学（cryptography)破译密文的科学和技术就是密码分析学（cryptanalysis）–明文：是作为加密输入的原始信息，即消息的原始形式，通常用m或p表示。所有可能明文的有限集称为明文空间，通常用M或P来表示。.–密文：是明文经加密变换后的结果，即消息被加密处理后的形式，通常用c表示。所有可能密文的有限集称为密文空间，通常用C来表示。–密钥：是参与密码变换的参数，通常用k表示。一切可能的密钥构成的有限集称为密钥空间，通常用K表示。–加密算法：是将明文变换为密文的变换函数，相应的变换过程称为加密，即编码的过程（通常用E表示，即c=Ek(p)）。–解密算法：是将密文恢复为明文的变换函数，相应的变换过程称为解密，即解码的过程（通常用D表示，即p=Dk(c)）。第一章密码学的发展历史密码学的发展历程大致经历了三个阶段：古代加密方法、古典密码和近代密码•古代加密方法（手工阶段）源于应用的无穷需求总是推动技术发明和进步的直接动力。存于石刻或史书中的记载表明，许多古代文明，包括埃及人、希伯来人、亚述人都在实践中逐步发明了密码系统。从某种意义上说，战争是科学技术进步的催化剂。人类自从有了战争，就面临着通信安全的需求，密码技术源远流长。–古代加密方法大约起源于公元前440年出现在古希腊战争中的隐写术。当时为了安全传送军事情报，奴隶主剃光奴隶的头发，将情报写在–奴隶的光头上，待头发长长后将奴隶送到另一个部落，再次剃光头发，原有的信息复现出来，从而实现这两个部落之间的秘密通信。–密码学用于通信的另一个记录是斯巴达人于公元前400年应用Scytale加密工具在军官间传递秘密信息。Scytale实际上是一个锥形指挥棒，周围环绕一张羊皮纸，将要保密的信息写在羊皮纸上。解下羊皮纸，上面的消息杂乱无章、无法理解，但将它绕在另一个同等尺寸的棒子上后，就能看到原始的消息。–我国古代也早有以藏头诗、藏尾诗、漏格诗及绘画等形式，将要表达的真正意思或“密语”隐藏在诗文或画卷中特定位置的记载，一般人只注意诗或画的表面意境，而不会去注意或很难发现隐藏其中的“话外之音”。–传输密文的发明地是古希腊，一个叫AeneasTacticus的希腊人,他使用了一个称为Polybius的校验表，这个表中包含许多后来在加密系统中非常常见的成分，如代替与换位。Polybius校验表由一个5×5的网格组成（如表1-1所示），网格中包含26个英文字母，其中I和J在同一格中。每一个字母被转换成两个数字，第一个是字母所在的行数，第二个是字母所在的列数。如字母A就对应着11，字母B就对应着12，以此类推。使用这种密码可以将明文“message”置换为密文“32154343112215”。在古代，这种棋盘密码被广泛使用。–表1-1Polybius校验表123451ABCDE2FGHI/JK3LMNOP4QRSTU5VWXYZ•古典密码（机械阶段）–古典密码的加密方法一般是文字置换，使用手工或机械变换的方式实现。古典密码系统已经初步体现出近代密码系统的雏形，它比古代加密方法复杂，其变化较小。古典密码的代表密码体制主要有：单表代替密码、多表代替密码及转轮密码。Caesar密码就是一种典型的单表加密体制；多表代替密码有Vigenere密码、Hill密码；著名的Enigma密码就是第二次世界大战中使用的转轮密码。–在第一次世界大战期间，敌对双方都使用加密系统（CipherSystem），主要用于战术通信，一些复杂的加密系统被用于高级通信中，直到战争结束。而密码本系统（CodeSystem）主要用于高级命令和外交通信中。–到了20世纪20年代，随着机械和机电技术的成熟，以及电报和无线电需求的出现，引起了密码设备方面的一场革命——发明了转轮密码机（简称转轮机，Rotor），转轮机的出现是密码学发展的重要标志之一。美国人EdwardHebern认识到：通过硬件卷绕实现从转轮机的一边到另一边的单字母代替，然后将多个这样的转轮机连接起来，就可以实现几乎任何复杂度的多个字母代替。转轮机由一个键盘和一系列转轮组成，每个转轮是26个字母的任意组合。转轮被齿轮连接起来，这样就能实现当一个齿轮转动当一个转轮转动时，可以将一个字母转换成另一个字母。照此传递下去，当最后一个转轮处理完毕时，就可以得到加密后的字母。为了使转轮密码更安全，人们还把几种转轮和移动齿轮结合起来，所有转轮以不同的速度转动，并且通过调整转轮上字母的位置和速度为破译设置更大的障碍。–典型的密码机HagelinC-48型（即M-209)是哈格林对C-36改进后的产品,共由6个共轴转轮组成，每个转轮外边缘分别有17,19,21,23,25,26个齿，它们互为素数，从而使它的密码周期达到了26×25×23×21×19×17=101405850(数量级达到了亿)。•近代密码（计算机阶段）–密码形成一门新的学科是在20世纪70年代，这是受计算机科学蓬勃发展刺激和推动的结果。快速电子计算机和现代数学方法一方面为加密技术提供了新的概念和工具，另一方面也给破译者提供了有力武器。计算机和电子学时代的到来给密码设计者带来了前所未有的自由，他们可以轻易地摆脱原先用铅笔和纸进行手工设计时易犯的错误，也不用再面对用电子机械方式实现的密码机的高额费用。总之，利用电子计算机可以设计出更为复杂的密码系统。•关于二战的密码小插曲:–计算机和电子学时代的到来使得美国在1942年制造出了世界上第一台计算机.二战期间,日本采用的最高级别的加密手段是采用M-209转轮机械加密改进型—紫密,在手工计算的情况下不可能在有限的时间破解,美国利用计算机轻松地破译了日本的紫密密码,使日本在中途岛海战中一败涂地,日本海军的主力损失殆尽.1943年,在获悉山本五十六将于4月18日乘中型轰炸机，由6架战斗机护航，到中途岛视察时,罗斯福总统亲自做出决定截击山本,山本乘坐的飞机在去往中途岛的路上被美军击毁,山本坠机身亡,日本海军从此一蹶不振.密码学的发展直接影响了二战的战局!•密码学的理论基础–密码学的理论基础之一是1949年ClaudeShannon发表的“保密系统的通信理论”（TheCommunicationTheoryofSecrecySystems），这篇文章发表了30年后才显示出它的价值。1976年W.Diffie和M.Hellman发表了“密码学的新方向”（NewDirectionsinCryptography）一文，提出了适应网络上保密通信的公钥密码思想，开辟了公开密钥密码学的新领域，掀起了公钥密码研究的序幕。受他们的思想启迪，各种公钥密码体制被提出，特别是1978年RSA公钥密码体制的出现，成为公钥密码的杰出代表，并成为事实标准，在密码学史上是一个里程碑。–1976美国国家标准局（NBS，即现在的国家标准与技术研究所NIST）正式公布实施了美国的数据加密标准（DataEncryptionStandard，DES），公开它的加密算法，并被批准用于政府等非机密单位及商业上的保密通信。第二章密码体制的分类及应用•密码体制•密码体制就是完成加密和解密功能的密码方案。近代密码学中所出现的密码体制可分为两大类：对称加密体制和非对称加密体制。•对称密码体制（SymmetricEncryption）–对称密码体制也称为秘密密钥密码体制、单密钥密码体制或常规密码体制，对称密码体制的基本特征是加密密钥与解密密钥相同。对称密码体制的基本元素包括原始的明文、加密算法、密钥、密文及攻击者。–发送方的明文消息P=[P1，P2，…，PM]，P的M个元素是某个语言集中的字母，如26个英文字母，现在最常见的是二进制字母表{0,1}中元素组成的二进制串。加密之前先生成一个形如K=[K1，K2，…，KJ]的密钥作为密码变换的输入参数之一。该密钥或者由消息发送方生成，然后通过安全的渠道送到接收方；或者由可信的第三方生成，然后通过安全渠道分发给发送方和接收方。–发送方通过加密算法根据输入的消息P和密钥K生成密文C=[C1，C2，…，CN]，C=EK(P)–接收方通过解密算法根据输入的密文C和密钥K恢复明文P=[P1，P2，…，PM]，即P=EK(C)–目前普遍使用的对称加密算法主要有DES、3DES、RC4、RC5和AES（Rijndeal算法）等，AES是目前最新的加密标准，DES将被渐渐淘汰。–安全性AES3DESDESDES算法介绍DES是DataEncryptionStandard（数据加密标准）的缩写。它是由IBM公司研制的一种加密算法，二十年来，它一直活跃在国际保密通信的舞台上，扮演了十分重要的角色。DES是一个分组加密算法，它以64位为分组对数据加密。同时DES也是一个对称算法：加密和解密用的是同一个算法。它的密钥长度是56位（因为每个第8位都用作奇偶校验），密钥可以是任意的56位的数。DES由于密钥长度短，因此不够安全，而且它不易于硬件实现，未来会被渐渐替代（AES），但其设计方法是没有过时的。明文（64bits）IP置换（64bits）L0(32bits)R0(32bits)L1=R0R1=L0f(R0,k1)fki+16轮同样运算…L16+R16=L15f(R15,ki)+IP-1置换（64bits）DES算法结构IP置换表58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157(1)58表示：结果中位于第1个位置的值，等于原文中第58个位置的值(2)图中的一格代表1bit，共有64bit，即8字节DES：IP置换DES：f的结构(即黑盒变换)R（32bit）EE(R)（48bit）K（48bit）B1B2B3B4B5B6B7B8S1S2S3S4S5S6S7S8C1C2C3C4C5C6C7C8P+（48bit）（32bit）•非对称密码体（AsymmetricEncryption）–非对称密码体制也叫公开密钥密码体制、双密钥密码体制。其原理是加密密钥与解密密钥不同，形成一个密钥对，用其中一个密钥加密的结果，可以用另一个密钥来解密。–目前普遍使用的对称加密算法主要有RSA、Elgamal（离散对数）、ECC（椭圆曲线）等。RSA算法介绍:设p、q为两个大素数，n=pq令φ(n)=(p-1)(q-1)寻找一对e,d，使ed≡1modφ(n)加密：E(X)=xemodn,x∈Zn解密：E(y)=ydmodn,X∈Zn(其中x为原文,y为密文)其原理是初等数论的费马小定理:a的（p-1）次方≡1（modp）Hash函数Hash简单点讲就是把任意一段数据经过某种算法生成一段唯一的固定长度的数据。也叫做摘要。为了确保数据A免受意外或者故意（恶意）的修改，往往用这段数据A产生一个hash数据一起发送出去，Hash一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射，pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。目前常用的Hash函数有MD5（128bit）和SHA-1（