|
第11章 数据通信的容错和加密 容错和加密是一种提高数字通信系统可靠性的技术。本章简要介绍在信息的传输、存储和交换过程中广泛应用的奇偶校验码、循环码等差错控制码以及常用的数据加密技术。 11.1 数据通信的容错数据通信中的噪音是不可避免的，为了克服因此而造成的误差，数据通信中的容错是必不可少的。下面将着重介绍差错控制码的概念、模型以及奇偶校验码和循环冗余校验码。 11.1.1 引言1． 差错控制码的概念香农（Shannon）于1984年在“通信的数学理论”一文中提出了关于在噪声信道中传输信息的重要理论，即香农第二定理。该定理指出：只要对信息进行适当的编码（提供足够的冗余），就可以在不牺牲信息传输率的前提下把噪声信道引起的差错减少到任意希望的程度。香农的这一定理奠定了差错控制码的理论基础，后经海明（Hamming）等人的进一步发展，差错控制码形成了一套完整的理论体系。差错控制码抑制（控制）噪声的影响（差错）的实质是通过增加额外的信息（冗余信息）来揭露（检测）和／或屏蔽（纠正）差错。 图11-1示出一个数字通信系统的模型。源信息可能是消息、符号、数据或图表等信息。编码器把源信息转换成可传输的符号序列。这个序列中的每一个符号称为一个码符，表示一条信息的一个码符序列称为一个国字或码向量，表示所有源信息的码字的集合就称为一个码。源信息被转换成码字的过程称为编码，码字被转换成它所表达的信息的过程称为译码。以最有效的方式（即平均用最短的码符序列）来表达信息的码称为源码。源码中含冗余最少，通常认为是无冗余码。相反，非源码的码称为冗余码或差错控制码（因为冗余能够提供差错控制能力）。具有检测差错能力的码称为检错码，具有纠正差错能力的码称为纠错码。 file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4B96.tmp.jpg 图11-1 差错控制码的应用 尽管差错控制码是为数字通信系统设计的，但是，它的应用远不仅限于此。事实上，只要把图11-1中的传输部件理解为存储部件或变换部件，立即可以看到差错控制码的更加广泛的应用领域． 2． 差错模型在码字的传输过程中，有许多原因（如环境的干扰、部件的失效等）都可能导致差错的发生。差错的表现形式（差错模型）由系统及系统的应用环境决定。本节将涉及以下几种最常见的差错模型并讨论控制这些差错的编码和译码技术。 （1） 独立差错模型 如果一个失效（或环境的一次干扰）只会使码字中的一个码符发生差错，或者说，一个码字的各个码符的差错的发生是相互独立的，则称失效的这种差错表现形式为独立差错。 （2） 突发（burst）差错模型 如果一个失效可能使一个码字的任意一段相邻的码符同时发生差错，则失效的这种差错表现形式被称为突发差错。 （3） b邻接差错 如果一个码字被分成若干个长度为b的字段，一个失效可能使一个字段中的任意多个码发生差错，则失效的这种差错表现形式就称为长度为b的b邻接差错。b邻接差错是突发差错的一个特例。 3． 译码原则在图11-1所示的模型中，在正常情况下译码器的功能是把码S0的码向量转换成它所表达的信息，该功能只须执行S0的编码过程的逆过程就能实现。当差错发生时，即当传输部件输出的序列（向量）Yfile:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4BA6.tmp.pngS0时，编码过程的逆过程不能给出Y对应的源信息。若S0是检错码，若发现了Yfile:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4BA7.tmp.pngS0。则检测到了差错。若S0是纠错码，则译码器必须首先从S0中选择一个码向量V，把Y纠正成V，然后把V译成它所表达的信息。问题是，如何选择V才最合理（真正达到纠错的目的）？通常有以下三种策略。 （1） 条件极大似然译码 当收到一个非码向量Y时，在S0中选择码向量V的最理想的原则是使 file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4BB8.tmp.png file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4BB9.tmp.png S0 （11-1） 式中file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4BBA.tmp.png是在Y出现的条件下出现X的概率。满足式（11-1）的纠错原则称为条件极大似然译码原则。 （2） 极大似然译码 在式（11-1）中，file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4BBB.tmp.png不仅同Vi与Y的差异和差错模型有关，而且同Vi对应的源信息的出现概率有关。精确地统计出所有源信息的出现概率往往是一件困难甚至不可能的工作。为此，可以对式（11-1）作修改，使选择的码向量V满足在应该收到V的条件下可能收到Y的概率最大，即 file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4BBC.tmp.png file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4BCD.tmp.pngS0 （11-2） 这一修改了的纠错原则称为极大似然译码原则。当所有源信息的出现概率相等时，上述两种纠错原则是等效的。 （3） 最近距离译码原则 当码向量的所有码符出差错的概率都相等时，极大似然译码原则简化为下述最近距离译码原则。 当收到向量Y时，最近距离译码原则选择的码向量Vfile:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4BCE.tmp.pngS0。满足 d(Y，V)=min d(Y，Vi) file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4BCF.tmp.pngS0 （11-3） 式中d（Y，V）是向量Y与V间的距离，它反映Y与V之间的差异。距离的概念将在以后的各种差错模型下得到具体化。 4． 差错控制的策略在图11-1所示的传输系统中，发信者和受信者之间仅有一条单向传输线路。为了实现纠错，唯一的办法是传送纠错码。这种差错控制策略通常称为前向纠错。 如果在发信者和受信者之间增加一条反向传输线路，则只须把源信息编成检错码就可以 实现纠错，因为当译码器检测到差错时，可以通过反向传输线路要求重发以消除差错。这种差错控制策略通常称为自动重发请求（ARQ）。 ARQ策略的优点是用检错码代替纠错码，因而可望比前向纠错策略用更少的正向传输线和更简单的编码器和译码器。ARQ策略的缺点是对传输部件的永久性故障引起的差错的控制能力不如前向纠错策略，而且，ARQ策略使系统纠错的开销时间集中于差错发生时（重发）。因此，ARQ系统的实时响应性不如前向纠错系统。 目前，大多数编码系统中都采用了前向纠错策略，例如，存储系统、远程通信系统等。ARQ策略在电话、电报和某些卫星通信系统中得到了广泛的应用。事实上，容错技术中的重试、向后恢复等技术也采用了ARQ策略。 11.1.2 循环冗余校验码––––CRC码（Cyclic Redundancy Check）循还冗余校验码是目前通信传送系统和磁介质存储器中广泛采用的一种编码形式。下面将对其进行详细的介绍。 CRC码一般指在k位信息码之后再拼接r位校验码。其编码格式如图11-3所示。整个编码长度为n位，其中k位信息位，另外附加r=(n一k)位校验位，这种编码又称（n，k）码。应用CRC码的关键是如何从k位信息位得到r位校验位，以及如何从k＋r位信息码判断是否出错。 file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4BD0.tmp.jpg图11-3 CRC编码 （1） CRC码的编码方法：对于一个给定的（n，k）循环码，可以证明存在一个最高次幂为（n－k）的多项式q（x），g（x）为循环码的生成多项式，根据g（x）可以生成k位信息的校验码。 （2） CRC码的校验原理：假设被传送的k位二进制信息用表达式C（x）表示，则C（x）=Ck－1Ck－2…C1C0，Ci取值0或1。 将C（x）左移n－k位（即左移r位），则可表示成C（x）·2r。这样C（x）的左边就会空出r位，这r位便是校验码的位置。 用C（x）·2r除以g（x）生成多项式，所得到的余数即为所求的校验位。 假设余数表达式为r（x），商的表达式为q（x），C（x）·2r除以g（x）后得： file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4BD1.tmp.png 将上式两边同乘以g（x）得： file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4BD2.tmp.png 将上式右边的余数r（x）移到余式左边得： file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4BE2.tmp.png 上式左边的C(x)· 2r＋ r(x)即为所求的n位CRC码，r(x)就是校验位。从上式可以看出，等式右边是g(x)的倍式，那么等式左边也应该是g(x)的倍式。把等式左边生成的n位CRC码传送到接收方，接收方收到这n位编码后，同样除以g(x)，如果传送正确，余数应为0，如果余数不为0则传送出错。 为什么要将前面式子右边的r(x)移到等式的左边仍然为加r(x)呢？这是因为CRC码编码所用到的特殊运算，即每一位二进制位在进行四则运算时都采用模2运算，运算时不考虑进位和借位。 l 模2加减：模2加减运算就是按位加，逻辑上可以用异或门实现。模2加与模2减相同。0±0=0，0±1=1，1±0=1，1±1=0。 l 模2乘：模2乘时用模2加求部分积之和。 file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4BE3.tmp.png例： l 模2除：模2除是按模2减求部分余数。每上一位商，部分余数都要减一位。上商规则是只要余数最高位为1，则商为1，否则为0。当部分余数的位数小于除数时，该余数为最后余数。 file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4BE4.tmp.png例： 在求CRC码过程中始终要遵循按位模2运算规则，因此r(x)移到等式左边后仍为位加。 （3） 举例：有一个（7，4）码，求C(x)＝1100的CRC码，生成多项式g(x)＝1011。 解： C(x)=1100 C(x)左移n－k=3位，即C(x)·23=1100·23=1100000 g(x)=1011 C(x)23除以g(x)，余数位010 形成CRC码位1100010 （4） CRC码的纠错 前面已经讲过，将收到的CRC码除以约定的生成多项式g(x)，如果余数为0，则码字无错。如果某一位出错，则余数不为0，不同位出错余数也不同。表11-1列出了上例的出错模式。更换不同的测试码字，只要生成多项式不变，余数与出错位的对应关系就不变。 表11-1 （7，4）循环校验码出错模式（生成多项式g(x)＝1011） | A1 A2 A3 A4 A5 A6 A7 | 余数 | | | | | | | 1 0 0 0 1 1 | 001 | | 1 0 0 0 0 0 | 010 | | 1 0 0 1 1 0 | 100 | | 1 0 1 0 1 0 | 011 | | 1 1 0 0 1 0 | 110 | | 0 0 0 0 1 0 | 111 | | 1 0 0 0 1 0 | 101 | |
（5） 关于生成多项式 并不是任何一个最高次幂为（n－k）的多项式g(x)都可以作为生成多项式。从检错和纠错的要求出发，生成多项式要满足以下要求： l 任何一位发生错误都使余数不为0； l 不同位数发生错误余数不同； l 余数继续作模2除，应使余数循环。 使用者可以从有关资料上直接查到对应不同码制的生成多项式。表11-2给出了部分生成多项式。 表11-2 部分生成多项式 | K | g(x)多项式 | | | | | | | 3 | g(x)= x4＋x3+x+1 或g(x)= x4＋x3+x2+1 | | | 11 | g(x)= x4＋x+1 | | | 26 | g(x)= x5＋x2+1 | | | 1024 | g(x)= x16＋x15+x2+1 | |
11.2 数据加密技术随着数据通信技术应用的不断深入，数据加密技术显得日益重要。本节将介绍几种常用的数据加密算法并将给出其Basic实现程序。 11.2.1 概述[size=10.5000pt]1． 密码技术历史回顾密码技术有着悠久的历史，现代英语中的cryptograph（密码学）一词源于古希腊的kryptos（隐藏）和graphein（写）这两个单词。密码学伴随着人类社会的发展不断完善。 四千多年前至公元14世纪，是古典密码技术的孕育、兴起和发展时期。这个时期以手工作为加密手段。 14世纪到20世纪中叶，是古典密码学发展的鼎盛时期。16世纪前后，广泛地采用了密表和密本作为密码的基本体制，著名的维吉尼亚密码就是其中一例。该密码采用的是一种多字母表––––单字母表––––单元代替法。它依据“维吉尼亚字母方阵”进行加密。若设明文为Vigenere Cipher（维吉尼亚密码）则密钥为CSL，加密时将密钥写在明文下面，再依维吉尼亚密表得出密文，即： 明文——Visenere Cipher 密钥——CSLCSLCS LCSLCS 密文——XARGGPTW NKHSGJ 在维吉尼亚密码于16世纪正式命名之前，1379年拉文迪提出了一套专用“密钥”系统；文艺复兴时期，享有“西方密码之父”美誉的意大利人艾伯蒂对加密和破译做出了很大贡献。他不仅发明了密码史上的第一个字母频率表，还发明了实现多表替代的密码盘。利用这种密码盘可以变换出多个字母表，开辟了密码技术新的重要途径，使得同一个明文单词能以完全不同的伪装形式出现。在此基础上，1553年，意大利的白拉索提出使用密钥来控制加密字母表的选择和变换，从而把多表替代向前推进了一步。 这一时期的另一个特点是，有关密码术的著述和专著相继出现。上文提及艾伯蒂发明的字母频率表是现存的最早的一部关于密码分析的著述。此外，还有许多有关密码术的著作。 1499年德国的约翰尼斯写下了他的《密写》。虽然此书直到1606年才正式出版，但他仍不失为密码史上第一个撰写密码技术专著的作者。 1516年约翰尼斯的另一部有关密码的专著——《复写术》面世，书中涉及的众多加密字母表，其中含有可以将明文情报转换为一篇“恭维”文章的玛丽亚密码。 1586年，法国人维热约热出版了《论密码》。他在书中不仅罗列了众多的密码、多字母密表、密钥，还论述了他的密钥体系。 1927年，移居美国的俄国人弗里德曼和史密斯这对“密码技术史上最有名的夫妻搭档”写出了《密码破译原理》一书。弗里德曼是第一次世界大战期间杰出的密码破译专家，英文单词Cryptanalysis（密码破译）就是他创造的。 1931年，美国人亚德利出版其《美国密室》。该书被译成多种外文，一时间久销不衰。 这一时期的加密手段发展到机械手段，除上文提及的艾伯策发明的那种简单的密码盘外，20世纪30年代前后出现了更为复杂而精巧的转轮密码机，譬如日本制造的“紫色”密码机PURPLE，德国制造的“恩尼格码”密码机ENIGMA，瑞典人哈格林研制的Hagdin密码机（即美国的M209密码机）。密码机是一种把明文情报转换为密文的机械设备。例如美国M209密码机可以产生101405850个加密字母而不出现一次重复。 第二次世界大战期间，传统的密码技术得到了前所未有的发展和利用，加密手段也发展到电子阶段——密文通过无线电发报机发送，例如 1942年美国制造的“北极”发报机，前苏联组建的“露西”谍报网等。 20世纪50年代之后到现在，是传统密码学新的高水平发展时期和现代密码学的产生与研讨时期。特别是电子计算机技术的出现，促使密码学这一古老的学科焕发出空前的青春与活力，并从军事、外交等敏感部门的应用扩大到金融、商业、科技、经济等民用领域。 这一时期最具有代表性的两大成就如下。 1971年美国学者塔奇曼（Tuchman）和迈耶（Meyer）依据信息论科学创始人香农（Shannon）提出的“多重加密有效性理论”创立的，后于1977年由美国国家标准局采纳颁布的联邦数据加密标准——DES。 1980年，DES被美国国家标准协会正式采用作为美国商业加密算法。 DES的一个显著特点是公开算法的所有细节，而让秘密完全寓于密钥之中。它的面世，把传统密码学的研究推进到一个崭新的阶段，是“密码史上应用最广，影响最大的传统密码算法”。它具有较高的保密强度，而且易于用大规模集成电路予以实现，所以被誉为是密码史上的一个里程碑。 第二个重大成就，是1976年由美国著名的密码学家狄菲（Diffie）和赫尔曼（Hellman）创立的公开密码体制的新思想。这是密码史上划时代的革命性的新概念。它标志着现代密码学的诞生，引起了数学界、计算机科学界和密码界众多学者的广泛关注和深入探索，从而开创了密码学理论研究的新纪元。 相对于传统密码体制而言，公开密钥密码体制的独特之处在于：它的加密算法和加密密钥均可通过任何非安全通道（如普通电话线等）公布于众，仅将解密密钥保持秘密，特别是它易于解决密码通信系统发送方和接收方的认证，便于实现“数字签名”，确认双方的身份，为密码技术在商业、金融等民用领域的普遍应用创造了条件，展示了令人神往的广阔前景。 自1978年以来，陆续出现了许多实现这种新思想的实验性方案。例如：美国学者迈克尔（Merkle）、赫尔曼（Hellman）提出的基于背包问题的公开密钥密码体制；累夫斯特（Rivest）、沙米尔（Shamir）和艾德勒曼（Adleman）提出的基于数论中剩余函数的密钥单向特性的公开密钥密码体制（即RSA体制）；荷兰学者沙尔玛（Salomaa）提出的基于语言理论的公开密钥密码体制；波兰学者提出的建立在幂等元素性质之上的公开密钥密码体制；我国学者提出了基于有限自动机理论的公开密钥密码体制，基于布尔代数的公开密钥密码体制等。 [size=10.5000pt]2． 密码学的应用意义密码学的诞生及其发展，是人类文化水平不断进步的一个具体标志。历史上，人们在开始使用文字通信不久，就出现了用秘密方式伪装语言来迷惑对方的现象；自从有了战争，秘密通信方式及其破译手段日趋完善，其重要意义得到了充分体现。 从古代战争史到近代战争史，都不乏因使用密码而获得胜利的成功战例。第一次世界大战期间，美国人对德国外长齐默尔曼秘密电报的破译，促使在战争之初不愿参战的美国一改初衷，于1917年对德军宣战，扭转了战事的局面。在第二次世界大战期间，美国于1940年借助密码技术，以1200架飞机打败了是自己三倍兵力的德军，赢得了具有决定意义的不列颠之战的巨大胜利。被称为人类历史上最关键战役之一的中途岛战役所取得的辉煌战果归功于美军成功地破译了日本海军JN25密本加密电报，使得美军适时地调集兵力击毁了日军曾用以偷袭珍珠港的四艘主力航空母舰，给予日本海军致命的打击而陷入完全瘫痪。 随着计算机技术的问世及其日新月异的迅猛发展和广泛应用（特别是计算机网络应用的逐步增加），计算机已深入到人类社会生活的各个领域，对人类社会的进步产生了前所未有的积极影响，人们开始步入到信息时代。信息的价值越来越为人们所重视，当代人已经认识到“信息就是时间，信息就是财富，信息就是生命”。另一方面，由于计算机系统本身存在的脆弱性，又使得计算机系统中的信息资源和社会机密成为不法分子窥视、作案的一个主要目标，“计算机犯罪”正作为一种社会问题开始出现。如果计算机系统中的机密信息被泄露乃至被窃取，则将对国家安全造成直接或间接的威胁。因此，对信息资源的安全保护不仅成为军事、外交、**上的迫切需要，而且还成为当今社会中商业、金融、经济、科技等各个行业和部门广泛关注的共同问题。 对数据加密是有效地控制信息安全的一个重要方面。传统密码学的应用可以保护在非安全通道上的传输信息；现代密码学的应用则可保护在通信网络中的传输信息以及存储在计算机系统中的信息，实现信息的保密性和真实性。 密码学已经走出了“黑屋”研究，它的广泛应用不仅对国家安全，而且对人类生活的各个方面将产生越来越重要的影响。 3． 密码学的基本概念和有关术语把真实信息转化成为秘密形式信息的技术，有密写和编码两种类型。转化前的信息称为明文，转化后产生的信息称为密文。密写是指隐去明文信息本身固有的书面可见形式，使这些信息变得不可见，让局外人看不出来，发现不了，无可阅读，例如用微粒书写信息。如果说密写是一种外观上“无形”的表达形式，它并不改变明文信息本来的含意，那么编码则是对明文信息进行特殊变换处理的“有形”表现过程。实现该过程的方式有如下两种： l 密本方式（代码方式）——以明文信息中的单词或者音节作为其变换的基本单位； l 密表方式（密码方式）——以组成明文信息的字符（字母）为变换单位。 在密表方式中，可以把组成明文信息的字符变形不变位，或者变位不变形。前者即为替代密码，后者就是置换密码。不论是哪种类型的密码，它们所隐蔽的是明文信息的真实含意，即便局外人能够窃取到明文信息经变换后的某些“有形”表达形式——密文，却无法识别、无从理解它们。 密码学（又称保密学）既针对信息通信的保密，又针对存储数据（包括程序）的加密。它研究信息的变换与逆变换，实现明文信息真实含意的隐蔽和重现，防止局外人对信息的窃取、盗用。通信双方中的信息发送者把明文转换成密文的过程称之为加密；而信息接收者，把接收到的密文再现为明文的过程就是解密。这就是密码学所包括的两大分支： l 密码编码学——研究加密算法的设计，用于明文编码，隐蔽明文信息的真实含意； l 密码分析学——研究如何把密文还原成明文，即密码的破译。加密、解密都是在密钥的控制下进行的。把控制加密过程的密钥称为加密密钥；把控制解密过程的密钥称为解密密钥。它们分别是确定加密算法与解密算法变换过程的基本参数。 11.2.2 基本的加密技术如前所述，密码编码学和密码分析学是密码学的两大组成部分。 密码系统包括以下四个方面： l 明文空间——信息本来的原始空间； l 密文空间——明文经“改头换面”后得到的令他人（局外人）难以理解、辨认的信息空间； l 密钥空间——控制算法的实现，由信息通信双方所掌握的专门信息空间； l 算法——“计算某些量值或对某个反复出现的数学问题求解的公式、法则或程序。它规定了明文和密文之间的变换方式。 密钥和算法是密码体制中两个最基本的要素。在某种意义上，可将算法视为常量，它可以是公开的；将密钥视为变量，它是秘密的。 加密和解密通常是对一特定的密码体制而言的。在一般情况下密码体制指定一些（常常是多个）密码。每个密钥k确定一种加密函数ek和解密函数dk，用ek从明文P中获得密文C： ek(P)＝C， 反之则： dk(C)＝P。 因此，dk(ek(P))＝P。 一个良好的密码体制应具备的基本条件是：在不知道dk的情况下要将密文恢复成明文是十分困难的。众所周知，把密文还原成明文的过程即为密码的解密（破译）。良好的密码体制应经受得住各种类型的破译攻击。数据加密标准DES的设计者C．H．Meger认为，所谓攻击是指“在一组给定的假定之下进行的，它们包括为达到诸如恢复明文或密钥之类的预定目标而可能获得信息的假定”。它们大体上可分为主动型攻击（active attack）和被动型攻击（Passive attack）。例如消息穷尽攻击、分析攻击、块频率分析及确定性攻击等。 信息论的奠基人C．E．Shanon指出，一个良好的密码体制的设计必须考虑到： l 对密码破译攻击的工作因素——破译密文极为困难。算法的复杂程度使得破译者在破译过程中付出的工作量和资源代价极大； l 密钥的长度——为了在各种环境下都能够易于密码体制的使用，在有效地防破译的前提下，密钥长度应很小； l 加密、解密的操作流程简便易行； l 错码率及错码的扩散程度低； l 加密后源信息的长度不受影响。 可以认为，1975年以前的密码体制是经典密码体制（或称传统密码体制），而块密码（亦称分组密码）则是经典密码中一种特别有用的密码类型。它把明文信息分割成块结构，逐块予以加密和解密；块的长度由算法设计者预先确定。密文输出块的每个信息同时受明文输入块的每个信息与密钥中每个信息的综合影响，即密文中的各个信息都是明文和密钥中每个信息的尽可能复杂的数学函数，它将复杂到破译者要想从中求出其密钥的工作量极大，大到破译者在计算上望而止步、不可能实现的地步。 如果按照生成密文所采用的不同方法分类，那么此密码最基本的类型有： l 置换（移位）密码； l 替代密码； l 乘积密码。 本节简述这三种密码的若干基本算法，并着重于这些算法的计算机实现技术，分别给出每一种算法的计算机高级程序设计语言的“同解”源程序，略去算法的理论推导、计算复杂度方面的分析以及这些算法的逆过程——解密算法。 [size=10.5000pt]1． 置换密码置换密码又称移位密码或互换密码。它是依照某种算法使明文中的各个信息“变位不变形”，即不改变明文中的每个信息本身的形式，仅改变它在明文中的位置，再将如此重新排列后所得到的信息作为密文。实现置换密码的方法有很多，例如栏栅法、矩阵法等。为了叙述方便，下文中的明文（记为P－text）均以COMPUTER／CENTER／CHENG／SHENG／LI为例。 l 栏栅法 这种加密方法是先把明文书写成两行，再按列顺序得出密文。 对已设明文COMPUTER／CENTER／CHENG／SHENG／LI作变换，按图11-4的箭头所指方向，重新排列得密文（C－text）C／OCMHPEUETGE／RS／HCEENTGT／ELRI。 file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4BF5.tmp.jpg 图11-4 栏栅变换之一 在此基础上再稍加变换，例如将明文排成三行，再按列序正、反相间生成密文。即对明文P－text按图11-5方式进行变换得密文C－Text CEGON／MTSPEHURET／NECGRH／／ELCNI。 file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4BF6.tmp.jpg 图11-5 栏栅变换之二 显而易见明文所排列成的行数即为这种加密方法的密钥。 美国南北战争时期曾使用过这种加密方式，它是把图11-4中的变换方向作为明文的输入方向，而把其中明文的行方向作为密文的输出方向。例如图11-6所示的加密方式是将P－text按图11-6实线所示箭头方向输入，而虚线方向上的信息即为密文C－text：CMUE／ETRCEGSEGLOPTRCNE／HN／HN／I。 file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4BF7.tmp.jpg 图11-6 栏栅变换之三 l 矩阵法 矩阵法有非钥式法和钥式法两种类型。 设矩阵A的行数为K1，列数为K2。最简单的非钥式矩阵加密方法是把P－text从给定方向按行序输入到A中。而将A中各列上的信息作为C－text输出。若K1＝5，K2＝6，则按此方法得到的 C－text为：C E T E E O R E N N M／RGGPC／／／U E C S L T U H HI，如图11-7所示。 file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4C07.tmp.jpg 图11-7 非钥式矩阵变换 钥式矩阵加密法是非钥式矩阵加密法的改进。它仍按非钥式矩阵加密法P－text输入方向输入明文。所不同的是C－text的输出方向是由给定的密钥K控制（密钥K一般取若干行英文字母。以这些字母的字典顺序优先级输出密文）。 设密钥K＝WUHANC，则K中各字母的字典顺序优先级为653142；得到的C－text是：PC／／／TNHHIM／RGGUECSLORENNCETEE，如图11-8所示。 file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4C08.tmp.jpg 图11-8 钥式矩阵变换 为了增加破译的难度，还可以设置双重的密钥。其中的一个密钥为文字密钥K1＄，另一个为数字密钥K2＄。 K1＄的作用是使 P－Text穿插一些冗余信息，K2＄的作用是控制C－text的输出顺序。下面给出这种加密方法的计算机实现步骤及其源程序。 置密钥K1＄＝DFIL W于 P－text中 C O M P U T E R的前面，并将这个“加长”所得的新的P－text各字符从左至右按每五个字符长度分块，顺序排列成一个K1×K2的（7×5）矩阵B，再取密钥K2＄＝31542，即可设置一个变换： file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4C09.tmp.png 作列移位，形成一个新的K1’×K2’（7×5）的矩阵 B’；最后将 B’按顺时针方向旋转90度，得到一个K2’×K1’（5×7）的矩阵B”，依次取B”各行中的字符作为密文C－ text：IMRTHS／DCTE／GNWUCRNEILP／EEHLFOENC／G 实现上述三种矩阵算法的BASIC程序如下： 10 REM PROGRAM CB3201 20 INPUT ″PLEASE A KEYWORD：K1＄＝″；K1＄ 30 INPUT ″PLEASE INPUT A KEY NUMBER IN DATA LINE：K2＄＝″；K2＄ 40 INPUT ″PLEASE INPUT A P－TEXT： P＄＝″； P＄ 50 PRINT ″A P－TEXT IS：″：PRINT″″；P＄ 60 K1＝LEN（K1＄）：P＝LEN（P＄） 70 D＝INT（P／K1） 80 D1＝D＋1 90 DIM A ＄（D1，D1），C＄（D1，D1） 100 DIM B＄（D1，D1），C1＄（D1，D1） 110 A＄（1，1）＝K1＄ 120 FOR I＝2 TO D1 130 R ＄＝MID＄（P＄，K1*（I－2）＋1，K1） 140 A ＄（I，1）=R＄ 150 NEXT I 160 PRINT 170 FOR I=1 TO D1：PRINT A＄（I，1）：NEXT I 180 FOR I=1 TO D1 190 FOR J=1 TO K1 200 B＄（I，J）=MID＄（A＄（I，l），J，1） 210 NEXT J，I 220 FOR I=1 TO LEN（K2＄） 230 R（I）=VAL（MID＄（K2＄，I，l）） 240 NEXT I 250 FOR I=1 TO D1 260 FOR J=1 TO K1 270 C＄（I，J）=B＄（I，R（J）） 280 NEXT J，1 290 PRINT 300 FOR I=1 TO D1：FOR J=1 TO D1 310 PRINT C＄（I，J）； 320 NEXT J；PRINT；NEXT I 330 PRINT 340 FOR I=1 TO D1 50 FOR J=1 TO D1 360 C1＄（J，I）=C＄（I，J） 370 NEXT J，I 380 FOR I=1 TO D1：FOR J=1 TO D1 390 PRINT C1＄（I，J）； 400 NEXT J；PRINT；NEXT I 410 PRINT ″THE C－TEXT IS：″；PRINT″″； 420 FOR I＝1 TO D1 430 FOR J＝1 TO D1 440 PRINT C1＄（I，J）； 450 NEXT J，I 460 END ]RUN PLEASE A KEYWORD：K1＄=DFILW PLEASE INPUT KEY NUMBER IN DATAI LINE：K2＄=31542 PLEASE INPUT A P－TEXT：P＄=COMPUTER／CENTER／CHENG／SHENG／LI A p－TEXT IS： COMPUTER／CENTER／CHENG／SHENG／LI DFILW COMPU TER／C ENTER ／CHEN G／SHE NG／LI IDWLF MCUPO RIC／E TEREN H／NEC SGEH／ ／NILG IMRTHS／ DCTE／GN WUCRNEI LP／EEHL FOENC／G THE C－TEXT IS： IMRTHS／DCTE／GNWUCRNEILP／EEHLFOENC／G [size=10.5000pt]2． 替代密码 替代密码（又称换字密码）是根据某种算法，用其他字符去取代明文字符，明文与密文中各对应字符的相对位置保持不变，使明文中的各个字符“变形不变位”从而得到密文。 可以把替代密码分为四种类型： l 简单替代密码——明文中每一个字符均被与之对应的另一个字符取代，例如Caesar密码； l 多名替代密码——明文中每个字符用多个不同的字符取代。 l 多表替代密码——明文与密文字符集之间存在着多种替代关系，每一种替代关系又是——对应的，这种替代关系称为“表”——将明文变换为密文的映射表，例如下文的 Vigenere表。属于这类密码的有 Vigenere密码、Beaufort密码、Sestri密码以及 Delastelle密码等； l 区组替代密码——把明文分成若干个区组单位，每个区组单位包含有明文的若干个字符；然后一次加密明文的一个区组（即一次加密多个明文字符）作为密文的对应区组。例如Playfair密码、Hill密码。 这里以Caesar密码和Vigenere密码为例，简要地介绍替代密码中简单替代和多表替代加密方法的基本原理和实现技术。 (1) Caesar密码 公元前五十年古罗马大将朱利叶斯·凯撒（Julins Caesar）在高卢战争中首先使用过这种密码，故称为Caesar密码。 单表替代密码即用单个“明密字母表”实现信息的加密和解密，而Caesar密码是一种最简单的单表替代密码。该字母表中的明文字母顺序按字母的正常字典优先次序排列；密文字母表则由明文字母表左移三个字典顺序字母而得到。这里左移位字典顺序的“字母个数”即为移位密钥K，即K=3。加密时，仅需将密文字母表中的字母去替代所对应的明文字母表中的字母即可。 例如： 明文字母表——A B C D E F G H i J K L M…… 密文字母表——D E F G H I J K M N O P Q…… 设明文信息为：COMPUTER 则： 明文——COMPUTER 明文字母顺序：3 15 13 16 21 20 5 18 密钥 K＝3 6 18 16 19 24 23 8 21 密文——FRPSXWHU (2) Vlgenere密码 Vigenere密码是一种多表替代密码。该密码是由十六世纪德国密码学家布莱斯特·维吉尼亚（Blaise de Visenere）发明的。它的基本原理是： 1 ) 按下列方式构造一个Vigenere字母方阵，如图11-9所示。 第一行为明文字母（小写英文字母）；第一列为密钥字母（大写英文字母）；虚线内侧的各行字母是分别将第一行字母逐次按字典顺序循环移位0，1，2，……，25之后得到的。所得到的二十六行字母表即为这种密码的“多表”。 file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4C1A.tmp.jpg 图11-9 Vigenere方阵 上述Vigenere方阵可用以下BASIC程序予以实现： 10 REM PROGRAM CB32021 20 DIM A1（100），A2（10） 30 READ B1＄，B2＄ 40 DATA ″ABCDEFGHIJKLMNOPQRSTUVWXYZ″ 50 DATA ″abcdefghljklmnopqrstuvwxyz″ 60 PRINT TAB（5）；″″＋B2＄ 70 T＝LEN（B1＄） 80 FOR I＝1 TO T 90 PRINT TAB（6）；″－″； 100 NEXT I 110 PRINT 120 FOR I＝1 TO T 130 C1＄＝MID＄（B1＄，I，l） 140 IFI＝1 THEN PRINT TAB（3）；C1＄＋″！″＋B1＄：GOTO 190 150 K＝I－1 160 C＄＝MID＄（B1＄，I，T）＋LEFT＄（B1＄，K） 170 C2＄＝C1＄＋″! ″＋C＄ 180 PRINT TAB（3）；C2＄ 190 NEXT I 200 END 2 ) 加密时，取Vigenere方阵中第一行与第一列所对应的明文字母与密钥字母的交点字母作为密文字母。例如：该方阵中p、P的交点处所在的字母为E，则明文字母所对应的密文字母即为E，即用“E”替代“P”。用下例来说明这种加密方法。 设明文P－text为computercenterchengshengl！，密钥为DFILW。密钥规定了加货时取用的密钥字母表中的那些字母表。对于本例所设定的密钥，表明要用到D表、F表、I表、L表和W表，再将密钥字母重复写在明文的下方： 明文——c o m p u t e r c e n t e r c h e n g s h e n g l ！ 密钥——D F I L W D F I L W D F I L W D F I L W D F I L W D 最后按上述方式找出各对明文字母与密钥字母的“交叉字母”，对于本例，第一对字母c、D的交叉字母为F；第二对字母o、F的交叉字母为S……最末一对字母i、D的交叉字母为L。 则得该明文所对应的密文是：F T U A Q W J Z N A Q Y M C Y K J V R O K J V R H L。 以下是实现Vigenere密码的BASIC程序： 10 REM PROGRAM CB3202 20 DIM B（100），C（100），K（100） 30 READ A＄ 40 DATA ″COMPUTERCENTERCHENGSHENGL！″ 50 PRINT ″A P－TEXT IS：″ 60 PRINT A＄ 70 T＝LEN（A＄） 80 FOR I＝1 TO T 90 B（l）＝ASC（MID＄（A＄，I，1）） 100 NEXT I 110 PRINT ″YOUR KEYWORD IS：″ 120 INPUT K＄ 130 T1＝LEN（K＄） 140 FOR I＝1 TO T1 150 K（I）＝ASC（MID＄（K＄，I，1）） 160 NEXT I 170 J＝0 180 FOR I＝1 TO T 190 GOSUB 320 200 IF B（I）＞90－K THEN 220 210 C（I）＝B（I）＋K 220 GOTO 240 230 C（I）＝（B（I）＋K－90）＋64 240 NEXT I 250 PRINT 260 FOR I＝1 TO T 270 E＄一E＄＋CHR＄（C（I）） 280 NEXT I 290 PRINT ″VIGENERE TABLE CIPHERTEXT IS：″ 300 PRINT E＄ 310 END 320 J＝J＋1 330 IF J＞T1 THEN 360 340 K=K（J）－65 350 RETURN 360 J＝1 370 K=K（J）－65 380 RETURN ]RUN A P－TEXT IS： COMPUTERCENTERCHENGSHENGLI YOUR KEYWORD IS？DFILW VIGENERE TABLE CIPHERTEXT IS： FTUAQWJZNAQYMCYKJVROKJVRHL 11.3 DES和RSA体制加密的基本工作原理前面介绍了基本的加密技术，下面将介绍两个广泛应用的加密体制——DES和RSA体制加密的工作原理。 11.3.1 DES 体制加密的基本工作原理1977年7月，美国国家标准局公布的联邦数据加密标准——DES被举世公认为近代密码学最重大的成果之一。DES是重复使用移位变换和替代变换的强块密码（强分组密码），从本质上看，它属于一种抗破译能力更强的乘积密码体制。它把明文按64位（本节中的“位”即bit）分块输入，在64位（其中包含8位的校验位）密钥的控制下，将明文转换为等块长的64位密文输出，其密钥空间为256 ≈1017。 B．Bosworth曾用一个例子详细地介绍了DES加密算法DEA的11个步骤，并罗列了DES的算法框图和有关数据，对深入理解DES的基本原理很有帮助。DES加密算法的基本工作原理可用简图11-10扼要地描述如下。 file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4C1B.tmp.jpg 图11－10 DES加密算法的DEA流程示意图 图11-10中各框的含意是： 1 密钥64位； 2 子密钥生成48位； 3 输入明文64位； 4 初始移位（IP变换）； 5 乘积变换（密码运算）64位； 6 指示乘积变换由16次选代构成； 7 逆初始移位（IP逆变换）； 8 输出密文64位。 DES的加密过程为： 子密钥的生成——初始移位——乘积变换——逆初始变换。这四大步骤的基本内容如下。 （1） 子密钥的生成 依“子密钥生成算法”对输入的64位密钥进行16次选择，得到16个不同的子密钥，每个于密钥长48位。这些子密钥的作用是控制复杂的乘积变换。 （2） 初始移位 对输入的64位明文按“初始排列IP表”进行移位变换（即IP变换），改变该64位明文的排列顺序，生成两个长度分别32位的数据块L0和R0。这一步与密钥无关。 （3） 乘积变换 即密码运算，由“加密函数”及“模2加”运算经16次迭代完成（每次从16个子密钥中取用一个子密钥）。在这一过程中，先是依“扩展运算”将32位的L0和R0分别扩展成48位的L16和R16；再经过8次替换（亦称8个S盒）又变成为32位的L16和R16；最后将L16和R16互换位置。 （4） 逆初始移位 对经过乘积变换最终得到的L16和R16按“逆初始移位IP-1表”进行逆变换，从而得到64位的密文输出。这一步也与密钥无关。 关于“加密函数”、“扩展运算”及 IP表、IP-1表的详细介绍可参阅有关参考文献。 尽管在对DES加密过程的叙述中略去了许多细节，但读者仍可体会到它的复杂程度。DES体制足以使破译者在现有的实际情况下不可能用解析法对之求解。迄今为止，仍具有良好的抗计算机破译能力。据有关专家预测，若在通用计算机上以6μs试验一个密钥的速度来进行对密钥的穷举攻击，大约需要6800年。 另一方面，DES也受到几方面的批评，主要有： 其一，没有公布DES的设计原理； 其二，56位的密钥长度太短； 其三，乘积变换的选代次数太少。 在1988年5月召开的第五届国际计算机安全会议上，澳大利亚国防研究院的专家提出了DES的一种扩展方案，将其密钥长度由56位加长到112位。这样，若用穷举法搜索密钥，则密钥空间将为2112 ≈1033，这对于进一步增加DES的安全强度是很有意义的。 虽然DES的问世在美国国内引起很大争论，但它在商界、金融界乃至军界获得的广泛应用，表明它已取得了巨大的成功。 11.3.2 RSA公开密钥密码体制大数分解（将一个大合数分解成其素因子的乘积）与素性检测（判定一个给定的正整数是否为素数）是著名的数论难题之一。Gauss在其《Disquisitione Arithmeticae》一书中称之为“算术中最重要最有用的问题之一”。这一论题在理论上和应用上有着重大的意义。古往今来，曾吸引了不少中外学者以浓厚的兴趣对它进行了艰辛的探讨和不懈的研究，然而由于它本身所固有的难度以及拥有的指数阶计算复杂度，一直阻碍着人们的深入探索。 尽管如此，这个古老的难题在近30年来却又成为热门论题而重新兴起，变得空前的活跃。论其原因，其一是理论计算机科学技术的出现和迅猛发展。作为一个现代化的计算工具，计算机使很多复杂的算法得以执行。其二是本世纪以来，数学家们对这一感兴趣的论题创造出了许多涉及大数的巧妙方法，并将之应用于密码学中，导致了被誉为现代密码学第二个里程碑的代表——RSA公开密钥密码体制（简称RSA体制，下同）的出现，同时该体制受到商业、金融等行业的迅速采用。 RSA体制基于一个简单的事实之上：将两个大素数相乘比将它们的乘积分解为素因子要容易得多。这个结论使得“大数分解与素性检测”课题研究的每一个进展对于各国使用RSA密码的各个部门以及信息安全传送人员均具有直接的现实意义。 1990年6月，美国Bell实验室的Lenstra和DEC公司的Manasse宣称：他们在上百名研究人员的协助下，动用包括Cary巨型机、Sun3工作站在内的1000台计算机联网，连续运行六个星期，将具有155位十进制的第9个Fermat数F9分解成为下述位数分别为7位、49位和99位的素数因子而获得成功，此成果被誉为是“1990年世界十大科技成果之一”。 F9＝2，424，833 × 7，455，602，825，647，884，208，337，395，736，200， 454，918，783，366，342，657 × 741，640，062，627，530，801，524， 787，141，901，937，474，059，940，781，097，519，023，905，821， 316，144，415，759，504，705，008，092，818，711，693，940，737 [size=10.5000pt]1． RSA公开密钥体制的基本原理（1） 公开密钥体制 公开密钥密码（亦称非对称密码体制，简写为PKE，下同）的基本思想是Diffle和Hellman在斯坦福、Merkle在加利福尼亚大学于1976年独立提出的。到那时为止的一切密码，其加密密钥与解密密钥实际上是一致的。 在PKE中，加密密钥与解密密钥互异、分离。加密密钥可以通过非保密信道（如电子邮件或者电话等）向他人公开，使任何得到该加密密钥的用户可以据此将明文信息加密成密文信息予以发送；而按特定要求选择的解密密钥则保持秘密。虽然从理论上讲，解密密钥可由加密密钥计算得出，但该密码体制建立的思想使得这种计算在实际上成为不可行的。这也就是说，在实践中，解密密钥不可能由加密密钥（或加密信息、加密技术以及破译技术）轻易地产生、猜想出来；如果解密密钥须得破译者集中世界上所有最快的计算机运行数年才能算出，那么该密码事实上就是安全的。PKE安全性依赖于一种特殊的数学函数——单向陷门函数而获得。单向函数是这样一种数学函数：从一个方向求值是容易的，但由其逆向计算却很困难。例如，对于y＝f（x），任意给定自变量x能够很容易地计算出函数y的值；而由任意给定的y值，即便是依照已知的函数关系仍很难求出x的值。PKE取用单向陷门函数的独特性质，使得计算加密函数对于任何人都是简单易行的，然而在没有一定的条件下仅仅依据已知的加密函数去求解解密函数，在计算上是不可能的。这种“条件”或者说“专门知识”归于陷门（trapdoor），PKE使得不具备该条件的破译者在解密过程中将不可避免地遇到特定的计算上的难题。 公开密钥算法的核心是运用一种产生复杂的、伪随机数据序列的模运算。许多算法（例如Pohlig－Hellman算法）都用到了把素数作为模数r来产生加密序列的算法，RSA算法则是另一种类似的算法，它适于进行公开密钥加密。 PKE信息流程可参见图11-11。图中：EB——公开的加密算法；M——明文信息；DB———秘密的解密算法；C——密文信息。 file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps4C2C.tmp.jpg 图11-11 PKE信息流程示意图 （2） RSA算法 在已提出的多种公开密钥密码方案中，有一种加密、解密计算速度较快以及信息在传递时保密性能较为成熟的方案，即1978年由Rivest、Shamir和Adleman在麻省理工学院研制出的RSA公开密钥密码体制。 该体制的理论基础建立在与“大数分解和素性检测”这一已知的著名数论难题有关的论断之上，即：将两个大素数相乘在计算上是容易实现的，但将该乘积分解为两个大素数因子的计算量相当巨大，大到甚至在实际计算上不可能实现。 RAS算法运用了数论中的 Euler定理，即：若a、r是互素的两个正整数，贝aZ≡1（modr），其中Z为与r互素且不大于r的正整数的个数（即Euler函数）。该算法取用一个合数（该合数为两个大素数的乘积）而不是取用一个大素数作为其模数r，使之具备幂剩余函数的单向陷门特性功能。 RSA公开密钥密码体制的实施步骤为：设计密钥、设计密文、恢复明文。其要点如下。 先仔细选取两个互异的大素数p、q，令r=p×q，z=(p－l)×(q－1)；接着寻找两个正整数d和e，使之分别满足： gcd(d，z)=1，e×d≡1（mod z） 这里的（r、e）是公开的加密密钥，而（p、q、d）则为秘密的解密密钥。为把要求发送的明文信息M数字化、分块，则 对M的加密过程是：C≡Me（mod r）； 对C的解密过程是： M≡cd（mod r）。 其中C为密文信息。 （3） RSA算法的具体运用举例 假设用户A需要将明文信息“HI”通过RSA算法传递给用户B。 第一步，设计密钥（e、r），（d、p、q） a） 令p=5，q=11，取e=3； b） 计算r r=p×q=5×11=55； c） 求Z Z=(p－1)×(q－1)=(5－1)×(11－1)=40； d） 计算d 由e×d≡1（mod z），即：3×d≡1（mod z），可得d=27； 故加密密钥为(e，r)=(3，55)，解密密钥为：(d，P，q)=(27，5，11)。 第二步，设计密文 先将明文信息数字化，并按每块2个数字分组： 假定明文编码方式为：空格＝00；A＝01；B＝02；……；Z＝26，则数字化分组后的明文信息为：08；09。 而后用加密密钥（3，55）将数字化明文分组信息加密成密文。 由C≡Me(mod r)得： C1≡Me1(mod r)=(08)3(mod 55)=512(mod 55)=17； C2≡Me2(mod r)=(09)3(mod 55)=729(mod 55)=14； 故得相应的密文信息C为：17，14。 第三步，恢复明文 用户B收到密文，若需将其解密，只须计算M≡cd（mod r），即： M1≡cd1（mod r）＝（17）27（mod 55）＝08； M2≡cd2（mod r）＝（14）27（mod 55）＝09， 用户B得到的源文信息为08，09；将之转化为源文即得“HI”。 上例仅仅只是用来说明RSA算法的基本运用，它所具有的安全强度实在太弱，即便取P＝17，q＝11，e＝7，对明文信息“123”加密的结果也是毫无意义的。其中一个重要原因就是所选取的三个素数值太小，使得不经过因子分解这一途径就可破译。 读者要较为深入地讨论这一问题可以参考有关素性检测及其实现技术的相关书籍。
| 
发表于 2015-3-14 15:50:14
收藏
分享
支持
反对