第十四章第十四章 通信安全通信安全14.1 概述概述通信安全的基础通信安全的基础 密码学密码学n密码编码学密码编码学n密码分析学密码分析学通信不安全因素通信不安全因素n被破译被破译n被攻击被攻击 被伪造和篡改被伪造和篡改认证认证 防止被攻击的手段防止被攻击的手段认证的目的：认证的目的：n验证信息发送者真伪验证信息发送者真伪n验证接收信息的完整性验证接收信息的完整性 是否被篡改了？是否被重复接收是否被篡改了？是否被重复接收了？是否被拖延了？了？是否被拖延了？认证技术：包括消息认证、身份验证和数字签字。认证技术：包括消息认证、身份验证和数字签字。恃涟姐慢痉骤盘泌贵赛臃红掳均泊仔枪训衣常缸灭晰平疆洱卯喝很税窖瞻第十四章通信安全第十四章通信安全1密码编码学内容：密码编码学内容：n将消息加密的方法将消息加密的方法n将已加密的消息解密的方法将已加密的消息解密的方法密码分析学内容：如何破译密文和伪造密文。密码分析学内容：如何破译密文和伪造密文。密码学的基本术语密码学的基本术语n明文明文 待加密的消息待加密的消息n密文密文 加密后的消息加密后的消息n密码密码 用于加密的数据变换集合用于加密的数据变换集合n密钥密钥 用于表示加密变换的参数用于表示加密变换的参数密码种类：密码种类：n单密钥密码单密钥密码n公共密钥密码：也称为双密钥密码公共密钥密码：也称为双密钥密码荷痘群腕献途腿毖铅泅炳笔叭址树殊衫抢霞帅考各岿孙前羌裕岛夸撼夹格第十四章通信安全第十四章通信安全214.2 单密钥加密通信系统单密钥加密通信系统例：例：n密钥密钥Z m序列序列n加密算法加密算法 模模2加法加法n解密算法解密算法 仍是模仍是模2加法加法 一般算法：一般算法：令令F为产生密文为产生密文Y 的可逆变换，即有的可逆变换，即有Y = F(X, Z) = FZ(X)在接收端，密文在接收端，密文Y 用逆变换用逆变换F-1恢复成原来的明文恢复成原来的明文X ，即，即X = F-1(Y, Z) = FZ-1(Y) = FZ-1FZ(X)密钥安全信道信源加密解密信道XYZX敌方发送端 信道 接收端豫是雁图疽逆犀报同尚侥羡妇咋蔽昔陈傲汉棒粱云呐煤什鲁毅囊亥秆梧呼第十四章通信安全第十四章通信安全314.3 分组密码和流密码分组密码和流密码分组密码分组密码n加密过程加密过程n原理原理p连续的分组用相同的密钥加密。连续的分组用相同的密钥加密。p若有一个特定的分组明文和以前的一个分组相同，则若有一个特定的分组明文和以前的一个分组相同，则加密后两者的密文也相同。加密后两者的密文也相同。p目标是使明文的任目标是使明文的任1比特都不会直接出现在密文中。比特都不会直接出现在密文中。串行-分组变换器密码加密逻辑分组-串行变换器密钥串行明文串行明文污噬粹刑寸钵屡稠艳匡敝澳盐车蚕寸挨弱挺饵傀倡墒掺峙双簧掖羌擒蓉扣第十四章通信安全第十四章通信安全4流密码流密码n原理：对明文的逐个比特进行不同的变换。原理：对明文的逐个比特进行不同的变换。 n例：二进制加性流密码例：二进制加性流密码p令令xn, yn和和zn分别表示在分别表示在n时刻明文比特、密文比特和密时刻明文比特、密文比特和密钥流比特，则有钥流比特，则有式中，式中，N是密钥流的长度。是密钥流的长度。因为在模因为在模2运算中加法和减法是一样的，所以上式也运算中加法和减法是一样的，所以上式也可以写为可以写为因此，同样的装置既可以用于加密，也可以用于解密。因此，同样的装置既可以用于加密，也可以用于解密。密钥流产生器明文 xn密文 yn密钥流 zn密钥(a)加密装置密钥流产生器密文 yn明文 xn密钥流 zn密钥(b)解密装置删踩纬酬们陇闽颓莱亨孝伦度皇乱倦撬镁枯寸减润诸题疟谷间汹椅毫虞见第十四章通信安全第十四章通信安全5p密钥流应当尽可能地近似于一个完全随机的序列。密钥流应当尽可能地近似于一个完全随机的序列。p若密钥流是一个若密钥流是一个m序列，则图中的密钥流产生器就是一序列，则图中的密钥流产生器就是一个个m序列产生器；密钥则是控制此序列产生器；密钥则是控制此m序列的生成多项式序列的生成多项式和同步信息等。和同步信息等。p二进制加性流密码没有错误传播；在密文中一个错误二进制加性流密码没有错误传播；在密文中一个错误比特解密后只影响输出中的相应比特。比特解密后只影响输出中的相应比特。（分组密码可能有错误传播，使明文分组中很少几个比（分组密码可能有错误传播，使明文分组中很少几个比特的改变在密文输出中产生很多比特的变化。分组密码特的改变在密文输出中产生很多比特的变化。分组密码的这种错误传播性质在认证中很有价值，因为它使敌方的这种错误传播性质在认证中很有价值，因为它使敌方的破译人员不可能修改加密后的数据，除非知道密钥。）的破译人员不可能修改加密后的数据，除非知道密钥。）p 流密码通常较适用于通过易出错的通信信道传输数据，流密码通常较适用于通过易出错的通信信道传输数据，用于要求高数据率的应用中，例如视频保密通信，或者用于要求高数据率的应用中，例如视频保密通信，或者用于要求传输延迟很小的场合。用于要求传输延迟很小的场合。策沥廊辫惭决孔攘腾蛹鉴麦沈迈块疫寝薪苦含堤眷锦负阴杉微虱氛涝汁窘第十四章通信安全第十四章通信安全6对通信安全的基本要求对通信安全的基本要求n假设：敌方破译人员知道所用加密法的全部机理，只是假设：敌方破译人员知道所用加密法的全部机理，只是不知道密钥。不知道密钥。 n密码分析性攻击的形式：密码分析性攻击的形式：p仅对密文的攻击仅对密文的攻击p对已知明文的攻击对已知明文的攻击p对选定的明文的攻击对选定的明文的攻击p对选定的密文的攻击对选定的密文的攻击 n实际中常发生的是仅对密文的攻击：实际中常发生的是仅对密文的攻击：p例：使用语言的统计结构知识（例如，英文字母例：使用语言的统计结构知识（例如，英文字母e的的出现概率是出现概率是13%，以及字母，以及字母q的后面总跟随着的后面总跟随着u）和关）和关于某些可能的字的知识（例如，一封信的开头中可能于某些可能的字的知识（例如，一封信的开头中可能有有“先生先生”或或“女士女士”两字）。两字）。 n仅对密文的攻击是一个密码系统受到的最轻的威胁。因仅对密文的攻击是一个密码系统受到的最轻的威胁。因此，任何系统若不能战胜这种攻击，则被认为是完全不此，任何系统若不能战胜这种攻击，则被认为是完全不安全的系统。安全的系统。 输兼谓郑介碉沁沛刹毕嫡宰邹错诲丁触弟俏闹折铸翼乓边娱打丢墟艇矾挖第十四章通信安全第十四章通信安全714.4用信息论研究密码的方法用信息论研究密码的方法香农模型的假定：香农模型的假定：n敌方破译人员具有无限的时间和无限的计算能力；敌方破译人员具有无限的时间和无限的计算能力；n敌方仅限于对密文攻击。敌方仅限于对密文攻击。香农的密码分析定义：给定密文以及各种明文和密钥的先验香农的密码分析定义：给定密文以及各种明文和密钥的先验概率，搜寻密钥的过程。当敌方破译人员获得密文的唯一解概率，搜寻密钥的过程。当敌方破译人员获得密文的唯一解时，就成功地解密了。时，就成功地解密了。香农对安全性的基本度量香农对安全性的基本度量 互信息量互信息量I(X; Y) n令令X = (X1, X2, , XN)表示一个表示一个N 比特的明文消息比特的明文消息; Y = (Y1, Y2, , YN)表示相应的表示相应的N 比特密文。比特密文。n假定：假定：p密钥密钥Z服从某种概率分布服从某种概率分布pH(X) X的不确定性的不确定性pH(X/Y) 给定给定Y后后X的不确定性的不确定性pI (X; Y) = H(X) H(X/Y) X和和Y之间的互信息量。之间的互信息量。犬鸵啮栋侍菩趋瘫地馅雅苑婴叙褪筷勇垮常艾逆摧歼聂罢再经系瓜晌辰蓝第十四章通信安全第十四章通信安全8 14.4.1 完善安全性完善安全性完善安全性定义完善安全性定义 假定：破译人员只能够看到密文假定：破译人员只能够看到密文Y，则一个保密系统的完，则一个保密系统的完善安全性定义为：明文善安全性定义为：明文X和密文和密文Y之间是统计独立的，即有之间是统计独立的，即有I(X; Y) = 0于是，由于是，由I (X; Y) = H(X) H(X/Y)，可以求出，可以求出H(X/Y) = H(X) 上式表明，敌方破译人员最多只能，按照所有可能消息上式表明，敌方破译人员最多只能，按照所有可能消息的概率分布，从给定的密文的概率分布，从给定的密文Y，去猜测明文消息，去猜测明文消息X。 酬筛毗超沁穿桓斩霹胁年梨瓢秘恳贝俭蒲惫饯蚂搬贬政迫债梅碳爵嗣男挺第十四章通信安全第十四章通信安全9香农基本界香农基本界给定密钥给定密钥Z后，有后，有H(X/Y) H(X, Z/Y) = H(Z/Y) + H(X/Y, Z)当且仅当当且仅当Y 和和 Z 共同唯一地决定共同唯一地决定X 时，时，H(X/Y, Z) = 0；当使用已知密钥当使用已知密钥 Z 解密时，这是一个很有价值的假定。解密时，这是一个很有价值的假定。 因此，我们可以将式因此，我们可以将式H(X/Y) H(X, Z/Y) = H(Z/Y) + H(X/Y, Z)简化如下：简化如下：H(X/Y) H(Z/Y) H(Z)将上式代入式将上式代入式H(X/Y) = H(X)得知：为使一个保密系统给出完善的安全性，必须满足条件得知：为使一个保密系统给出完善的安全性，必须满足条件H(Z) H(X) 它表明为了达到完善安全性，密钥它表明为了达到完善安全性，密钥Z的不确定性必须不的不确定性必须不小于被此密钥所隐蔽的明文小于被此密钥所隐蔽的明文X的不确定性。的不确定性。 婶锨巳坊请体五挑瓜丙酋通逗懂驱披阐伯匝辑高漆凝跑冯耽麻洛垛骨害速第十四章通信安全第十四章通信安全10一次一密密码一次一密密码n原理方框图：一种流密码，其密钥和密钥流相同，并且密原理方框图：一种流密码，其密钥和密钥流相同，并且密钥只使用一次。钥只使用一次。 n密文密文 yn = xn zn,n = 1, 2, 式中，式中，xn 消息比特序列；消息比特序列； zn 统计独立和均匀分布的密钥比特序列。统计独立和均匀分布的密钥比特序列。n一次一密密码是完善安全的，因为消息和密文之间的互信一次一密密码是完善安全的，因为消息和密文之间的互信息量为息量为0；所以它是完全不可解密的。；所以它是完全不可解密的。 消息xn密文yn密钥zn密文yn消息xn密钥zn(a) 加密(b) 解密鸿熟手咒孵枉饯瞥鸵蛛已眉美壮货影助凌煎众星炎罢楷单叔出午好祭氰粱第十四章通信安全第十四章通信安全11 14.4.2 唯一解距离唯一解距离对于一个用非完善密码加密的密文，可以预期，当截获的文对于一个用非完善密码加密的密文，可以预期，当截获的文件量随时间增大到某一点时，破译人员用无限的时间和无限件量随时间增大到某一点时，破译人员用无限的时间和无限的计算能力，将能够找到密钥并从而破译了密文。的计算能力，将能够找到密钥并从而破译了密文。 在香农的模型中，破译人员能破译此密文的临界点称为唯一在香农的模型中，破译人员能破译此密文的临界点称为唯一解距离。解距离。唯一解距离的定义：唯一解距离的定义： 使条件熵使条件熵H(Z/Y1, Y2, , YN)近似为近似为0的最小的最小N。对于一类特殊的对于一类特殊的“随机密文随机密文”，唯一解距离近似由下式给出：，唯一解距离近似由下式给出：式中，式中，H(Z) 密钥密钥Z的熵，的熵， Ly 密文字符集的大小，密文字符集的大小， r N比特密文中所含信息的冗余度百分比，即比特密文中所含信息的冗余度百分比，即式中，式中，H(X)为明文为明文X的熵。的熵。 柏峙入樱坡质琐壶振捕巩拨粪鸣累哎衷剖取牧盾舵站猜茨挎说斌孽辐鉴腮第十四章通信安全第十四章通信安全12 在大多数保密系统中，密文字符集的大小在大多数保密系统中，密文字符集的大小Ly和明文字符集和明文字符集的大小的大小Lx一样。在这种情况下，一样。在这种情况下，r就是明文本身的冗余度百分就是明文本身的冗余度百分比。比。求求H(Z) 令令 K = 密钥密钥Z中的数字数目，这些数字是从大小为中的数字数目，这些数字是从大小为Lz的字的字符集中选用的；则可以将密钥符集中选用的；则可以将密钥 Z 的熵表示如下：的熵表示如下：当且仅当密钥是完全随机的时，上式等号成立。当且仅当密钥是完全随机的时，上式等号成立。 令令Lz = Ly，并完全随机地选择密钥以使唯一解距离最大。，并完全随机地选择密钥以使唯一解距离最大。然后，将然后，将H(Z) = K log2 Lz代入代入得到：得到：N0 K / r 谨铆绢靳戒操拙呆犬眩够剧尼糟胸狈暗竣样昂彼傈渡硬辖及池抬棋冗攒电第十四章通信安全第十四章通信安全13N0 K / r 例：考察一个例：考察一个Lx = Ly = Lz保密系统，它用于对英文文本加密保密系统，它用于对英文文本加密 典型英文文本的典型英文文本的 r 大约等于大约等于75。因此，按照上式，一个。因此，按照上式，一个破译人员在仅截获约破译人员在仅截获约1.333K比特的密文数据后，就能破译此比特的密文数据后，就能破译此密码，其中密码，其中K是密钥长度。是密钥长度。值得注意，非完善密码仍然有实用价值。值得注意，非完善密码仍然有实用价值。 隧氰斋侧抵祖幽迁湘匝后渡目联祭救嫁涣循灌馆币洒烦涤颖腾渺石冠竖倦第十四章通信安全第十四章通信安全14 14.4.3 数据压缩在密码编码中的作用数据压缩在密码编码中的作用数据压缩能除去冗余度，因此增大了唯一解距离。数据压缩能除去冗余度，因此增大了唯一解距离。 14.4.4 扩散与混淆扩散与混淆扩散：将明文中一个比特的影响扩散到密文中很多比特，从扩散：将明文中一个比特的影响扩散到密文中很多比特，从而将明文的统计结构隐藏起来。而将明文的统计结构隐藏起来。 混淆：采用数据变换，使密文的统计特性与明文的统计特性混淆：采用数据变换，使密文的统计特性与明文的统计特性之间的关系更为复杂。之间的关系更为复杂。 乘积密码：由一些简单的密码分量相继加密构成；这些较简乘积密码：由一些简单的密码分量相继加密构成；这些较简单的密码分量分别能使最终的密码有适度的扩散和混淆。单的密码分量分别能使最终的密码有适度的扩散和混淆。 例：乘积密码用例：乘积密码用“替代密码替代密码”和和“置换密码置换密码”作为基本分作为基本分量。量。氛露哺罐酶痕眼匈捣珠鲁蹄断蒜榆凹欢渐蔓呆嫉怂今栅捷氯自健溢沧朴务第十四章通信安全第十四章通信安全15替代密码：明文的每个字符用一种固定的替代所代替；代替替代密码：明文的每个字符用一种固定的替代所代替；代替的字符仍为同一字符表中的字符；特定的替代规则由密钥决的字符仍为同一字符表中的字符；特定的替代规则由密钥决定。定。 若明文为若明文为X = (x1, x2, x3, x4, ) 式中，式中，x1, x2, x3, x4, 为相继的字符，则为相继的字符，则变换后的密文为变换后的密文为Y = (y1, y2, y3, y4, ) = f(x1), f(x2), f(x3), f(x4),式中，式中，f ( )是一个可逆函数。是一个可逆函数。 例：密文的字符表例：密文的字符表 从此表中可以看到，第一个字符从此表中可以看到，第一个字符U替代替代A，第二个字符，第二个字符H替代替代B，等等。，等等。 使用替代密码可以得到混淆。使用替代密码可以得到混淆。明文字符明文字符ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字符密文字符UHNACSVYDXEKQJRWGOZITPFMBL过桔婚当川路母揪妻竟蹲笺涌枫栽缄骂该睦驼媒减穿觅跨镑缎踢僳厅剖褐第十四章通信安全第十四章通信安全16置换密码：明文被分为具有固定周期置换密码：明文被分为具有固定周期 d 的组，对每组作同样的组，对每组作同样的交换。特定的交换规则是由密钥决定的。的交换。特定的交换规则是由密钥决定的。n若周期若周期d4，交换规则为，交换规则为则明文中的字符则明文中的字符 x 将从位置将从位置 1 移至密文中的位置移至密文中的位置 4。 一般而言，明文一般而言，明文X = (x1, x2, x3, x4, x5, x6, x7, x8, )将变换成密文将变换成密文Y = (x3, x4, x2, x1, x7, x8, x6, x5, )n虽然密文虽然密文Y 中单个字符的统计特性和明文中单个字符的统计特性和明文X 中的一样，但中的一样，但是高阶统计特性却改变了。是高阶统计特性却改变了。n使用置换密码可以得到扩散。使用置换密码可以得到扩散。明文字符明文字符x1 x2 x3 x4密文字符密文字符x3 x4 x2 x1吾厢薄系皂务黄庆奄及那塞丛缩辱爪辨瞪茧颇朱奥宛亢摈迭椽甭稠葡剪犬第十四章通信安全第十四章通信安全17将替代和置换作交织，并将交织过程重复多次，就能得到具将替代和置换作交织，并将交织过程重复多次，就能得到具有良好扩散和混淆性能的保密性极强的密码。有良好扩散和混淆性能的保密性极强的密码。例：例： 设明文消息为设明文消息为THE APPLES ARE GOOD使用交换字符表使用交换字符表作为替代密码，则此明文将变换为如下密文：作为替代密码，则此明文将变换为如下密文：IYC UWWKCZ UOC VRRA 下一步我们将交换规则下一步我们将交换规则用于置换密码，则从替代密码得到的密文将进一步变换成用于置换密码，则从替代密码得到的密文将进一步变换成UCI YCKWWC OZU ARVR这样，上面的密文和原来的明文相比，毫无共同之处。这样，上面的密文和原来的明文相比，毫无共同之处。明文字符明文字符ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字符密文字符UHNACSVYDXEKQJRWGOZITPFMBL明文字符明文字符x1 x2 x3 x4密文字符密文字符x3 x4 x2 x1砚杏喊盲冰镐栏富肚意伞狰穗鞠功钵否钮梆绑俩瞻钥疹羌仅镑捻熙姨旋玄第十四章通信安全第十四章通信安全1814.5 数据加密标准数据加密标准 美国政府标准算法美国政府标准算法DES DES采用扩散和混淆算法，是一种保密性很强的密码。采用扩散和混淆算法，是一种保密性很强的密码。它对它对64 b长的明文数据分组运算，所用的密钥长度为长的明文数据分组运算，所用的密钥长度为56 b。 DES算法中：算法中：n总变换总变换 = P -1FP(X)，其中其中 X 明文，明文，P 某种交换，某种交换，F 包括替代和置换；由某些函数包括替代和置换；由某些函数 f 的级连构成。的级连构成。迎恼瘫壕傀涸酬奥岩御摊被戒滑滓彩葫婚信瓷堡模墅忘蚁然丑绘撤浮迎拣第十四章通信安全第十四章通信安全19DES算法流程图算法流程图n第第1次初始交换后：次初始交换后：64 b的明文分为左的明文分为左半部半部L0和右半部和右半部R0，每半部长，每半部长32 b。 n完成完成16轮交换，其中第轮交换，其中第 i 轮交换：轮交换： Li = Ri1， i = 1，2，16Ri = Li-1 f(Ri-1, Zi)，i = 1，2，16式中，式中，Zi 在第在第i 轮中使用的密钥；轮中使用的密钥；此密钥的长度为此密钥的长度为48 b。 n第第16轮运算的结果，经过颠倒后，轮运算的结果，经过颠倒后，得到得到R16L16。 n再经过最后一次交换再经过最后一次交换P -1，就产生出就产生出64 b的密文。的密文。n为了解密，函数为了解密，函数f( , )不必须是可逆的，不必须是可逆的，因为因为(Li-1, Ri-1)能够从能够从(Li, Ri)直接恢复：直接恢复： Ri-1 = Li i = 1，2，16Li-1 = Ri f(Li, Zi) i = 1，2，16f(R0, Z1)R16L16最后一次交换64 b密文Z164 b 明文初始交换32 b L032 b R0f(R0, Z1)R1L1f(R0, Z1)R2L2R15L15Z2Z16枕寒母扑劳脏散饶捉合贞酒试酥藩碰剔达素论瞻亿字肠蕊闭翌援麦铭讫豢第十四章通信安全第十四章通信安全20计算计算f( , )的流程图的流程图n扩展：扩展：R(32b) R (48b) 方法：重复每个相继的方法：重复每个相继的4 比特字的两端比特。比特字的两端比特。若若 R = r1r2r3r4 r5r6r7r8 r29r30r31r32 则扩展后则扩展后 R r32r1r2r3r4r5 r4r5r6r7r8r9 r28r29r30r31r32r1nR 和和 Zi 模模2相加，再将相加相加，再将相加结果分成结果分成8个个6 b的字：的字： B1B2 B8 = R Zi 32 b的R扩 展48 b的R48 b的ZiS2S8S1交换 P32 b f(R, Zi)第1个4 b的字第2个4 b的字第8个4 b的字第1个6 b的字第2个6 b的字第8个6 b的字轧铸噪四臆崎枣捆萝绽猖滨望绢囱产佑她瑟殿掇谭寒稿氯镊冰锅枝果莉豪第十四章通信安全第十四章通信安全21n每个每个6 b的字的字 Bi 输入到一个替代方框输入到一个替代方框Si；后者用查表的方法；后者用查表的方法产生出一个产生出一个4 b的输出的输出Si(Bi)。 Si(Bi)是是6 b字字Bi的布尔函数。的布尔函数。n 8个输出个输出Si 输入到交换方框输入到交换方框P 。n交换所得就是所要求的交换所得就是所要求的32 b的函数的函数f(R, Zi) : f(R, Zi) PS1(B1)S2(B2)S8(B8)32 b的R扩 展48 b的R48 b的ZiS2S8S1交换 P32 b f(R, Zi)曝幽笔缆矛啡浑少洼锯隘扎昏白也兰棵肃猴恕爱流晤砂凛戈弥记锁郴鲤慕第十四章通信安全第十四章通信安全22密钥进程计算密钥进程计算 决定每个决定每个Zi所用的过程所用的过程n流程图流程图 n各各Zi使用密钥使用密钥Z0的的不同子集。不同子集。 n密钥密钥Z0在位置在位置8, 16, , 64上有上有8个监督个监督比特，用于在对应比特，用于在对应的的8 b字节中进行错字节中进行错误检测。误检测。n“交换选择交换选择1”丢掉丢掉Z0的监督比特。的监督比特。n然后存入两个然后存入两个28 b的的移存器中。移存器中。64 b密钥交换选择156 b密钥28 b C028 b D0左 移左 移C1D1左 移左 移交换选择2C2D2左 移左 移交换选择2C16D16交换选择2移存器Z1Z2Z16挑摈贷锦致蓑汀诽瘩荡周许焙捉颓钳涩蛤襄餐季循铀诉哇吨思建扯语症对第十四章通信安全第十四章通信安全23n作作16次迭代运算，每次迭代包括一次或两次循环左移，然次迭代运算，每次迭代包括一次或两次循环左移，然后进行后进行“交换选择交换选择2”。n输出就是第输出就是第1次至第次至第16次迭代用的不同的次迭代用的不同的48 b密钥分组密钥分组Z1, Z2, , Z16。64 b密钥交换选择156 b密钥28 b C028 b D0左 移左 移C1D1左 移左 移交换选择2C2D2左 移左 移交换选择2C16D16交换选择2移存器Z1Z2Z16斡官侠逝线暂羞肇强乾梗铝檄险讯幕痘玖抚仪珠危酷喝患管粒兼掺羞偏胖第十四章通信安全第十四章通信安全2414.6 公共密钥密码编码方法公共密钥密码编码方法14.6.1 基本原理基本原理公共密钥系统中，用两种算法去计算两个不可逆函数（变换）公共密钥系统中，用两种算法去计算两个不可逆函数（变换）。令这两种算法用。令这两种算法用Ez和和Dz表示：表示：Ez: fz(x) = y 公共密钥（公钥）公共密钥（公钥）Dz: fz-1(y) = x 秘密密钥（私钥）秘密密钥（私钥）式中，式中，x 在某个函数在某个函数fz的域中的一个输入消息，的域中的一个输入消息，y 在在fz取值范围内相应的密文。取值范围内相应的密文。基本要求：函数基本要求：函数fz必须是一个单向函数。必须是一个单向函数。公钥和私钥的两个基本性质：公钥和私钥的两个基本性质：n消息被这对密钥之一加密后，能够用另一个密钥解密。消息被这对密钥之一加密后，能够用另一个密钥解密。n知道公钥后，不可能计算出私钥。知道公钥后，不可能计算出私钥。将此系统的用户姓名、地址和公钥列于一本将此系统的用户姓名、地址和公钥列于一本“电话簿电话簿”中。中。当一个用户需要向另一个用户发送保密消息时，查此当一个用户需要向另一个用户发送保密消息时，查此“电话电话簿簿”，用对方的公钥对消息加密。加密的消息只能由持有对，用对方的公钥对消息加密。加密的消息只能由持有对应私钥的用户阅读。应私钥的用户阅读。 钝靡回疽卤短荷诈衣赫罪循舟豪撼茵勾议告粹凿泛茵密斟胁妖呛狭凄激焊第十四章通信安全第十四章通信安全25 14.6.2 Diffie-Hellman 公共密钥分配系统公共密钥分配系统基本原理：令离散指数函数为基本原理：令离散指数函数为 Y = X mod p1 X p 1式中，式中， 一个整数，并且是一个本原元。一个整数，并且是一个本原元。因此，因此，X是是Y的以的以 为底的模为底的模p离散对数：离散对数： X = log Y mod p 1 Y p 1使用使用“平方的乘积平方的乘积”法，很容易从法，很容易从X计算计算Y。例如，对于例如，对于X = 16，有，有Y = 16 = ( 2)222 另一方面，从另一方面，从Y计算计算X则难得多。则难得多。应用方法：假定所有用户都知道应用方法：假定所有用户都知道 和和p。n若有一用户若有一用户i，从一组整数，从一组整数1, 2, , p中，均匀地选择一个中，均匀地选择一个独立随机数独立随机数Xi，作为私钥；并将离散指数，作为私钥；并将离散指数 Yi = Xi mod p 和用户姓名及地址一起放在和用户姓名及地址一起放在“公共电话簿公共电话簿”中。其他用户中。其他用户也如此做。也如此做。伎攻票蝇怪苫套滑弟恳窟胺少醉匪眶流钟人抽厌趾窘瞥采裴社逸件利罚贞第十四章通信安全第十四章通信安全26n假设用户假设用户i 和和 j 希望进行保密通信。为此，用户希望进行保密通信。为此，用户i 从从“公共公共电话簿电话簿”中取出中取出Yj，并用私钥，并用私钥Xi计算计算用户用户j 用同样方法计算用同样方法计算Kij。因为。因为Kji = Kij所以，用户所以，用户i和和j可将可将Kji 看作是普通保密系统中的密钥。看作是普通保密系统中的密钥。n敌方若想得到敌方若想得到Kji，必须用从，必须用从“公共电话簿公共电话簿”中得到的中得到的Yi和和Yj，按照下列公式去计算，按照下列公式去计算Kji：上式因为包含离散对数故难于计算。上式因为包含离散对数故难于计算。 风殃社尼欺算体永半湘遭光簿岗鲍穷捅迟码瓶择担帛肇川张勾蚁沫叹捧伤第十四章通信安全第十四章通信安全2714.7 RSA算法算法14.7.1 RSA公共密钥密码系统公共密钥密码系统基本原理：基本原理：RSA算法是一种分组密码，其理论基础是，求出算法是一种分组密码，其理论基础是，求出一个随机的大素数不难，但是将两个这种数的乘积分解因子一个随机的大素数不难，但是将两个这种数的乘积分解因子目前认为是不可能的。目前认为是不可能的。算法：算法：n随机选择两个很大的素数随机选择两个很大的素数p和和q，p q；n将将p和和q相乘，得到乘积相乘，得到乘积pq = n n使用下式求出欧拉函数使用下式求出欧拉函数 (n): (n) = (p 1)(q 1)n从欧拉函数从欧拉函数(n)的定义可知，上式给出小于的定义可知，上式给出小于n的正整数的正整数i的的数目，且数目，且i和和n的最大公因子等于的最大公因子等于1，即，即i和和n互为素数。互为素数。例：设 p3，q5，则n15，(n) = (3-1)(5-1) = 8。它表示小于15且和15互素的正整数i共有8个；它们是：1，2，4，7，8，11，13，14。瘪钟驶叶竿效频肾扣柠冻怯钾纯彻息羔壮放疹搞惰快占捻征酷伙喝恭酚迭第十四章通信安全第十四章通信安全28n令令e是一个小于是一个小于(n)的正整数，它使的正整数，它使e和和(n)的最大公因子等于的最大公因子等于1。这样，求出一个小于这样，求出一个小于(n)的正整数的正整数d，它使，它使de 1 mod(n)nRSA的单向函数由计算下式中的离散指数定义：的单向函数由计算下式中的离散指数定义：fz(x) = xe = y mod nn将将n和和e值组成公共密钥值组成公共密钥 公布计算函数公布计算函数fz的算法的算法Ez（它很容易（它很容易找到）就相当于公布找到）就相当于公布n和和e的值。的值。n素数素数p和和q组成秘密密钥。组成秘密密钥。n知道素数知道素数p和和q后，就容易求出逆函数后，就容易求出逆函数fz-1 。 fz-1的定义是的定义是fz-1(y) = yd mod n使用式使用式 de 1 mod(n)，能求出解密指数，能求出解密指数d ，即，即 de (n)Q + 1式中，式中，Q是某个整数。是某个整数。 y = xe，利用欧拉的一个著名定理，即对于任何正整数利用欧拉的一个著名定理，即对于任何正整数x和和n，x n，有有 ，将其代入，将其代入de (n)Q + 1，得到，得到yd = x 它表明：知道素数它表明：知道素数p和和q后，就容易求出逆函数后，就容易求出逆函数fz-1。遂殷溉烃蒜翁鳖缎熟泻简梢蜡臻扼舌瞥匙咋博代光枕惺哄滥腆身防搂鸣鸯第十四章通信安全第十四章通信安全29RSA密码算法的安全性依赖于如下前提：求密码算法的安全性依赖于如下前提：求fz的逆函数的任何的逆函数的任何方法等效于求分解方法等效于求分解n = pq的方法。这样就产生了一个问题：用的方法。这样就产生了一个问题：用分解分解n的方法进行攻击可能吗？答案是不可能的。若素数的方法进行攻击可能吗？答案是不可能的。若素数p和和q分别由分别由100位以上十进制数字组成，目前尚无分解因子的算法。位以上十进制数字组成，目前尚无分解因子的算法。波羽巫曝湾睹渗秦鞠纳鹿轴殴磊渠劝瓷神喳酸额升袒犯腕听燎届吹幌幅租第十四章通信安全第十四章通信安全3014.7.2 RSA算法在数字签字中的应用算法在数字签字中的应用数字签字必须具有的性质：数字签字必须具有的性质：n一个电子消息的接收设备必须能够验证发送者的签字。一个电子消息的接收设备必须能够验证发送者的签字。n签字不可能伪造。签字不可能伪造。n已签字的电子消息的发送者不能否认它。已签字的电子消息的发送者不能否认它。用用RSA算法实现数字签字的方法：算法实现数字签字的方法：n一个拥有私钥一个拥有私钥d的用户可以对给定的消息分组的用户可以对给定的消息分组m签字为签字为s = md mod n若不知道私钥若不知道私钥d，则很难计算出，则很难计算出s。 故此签字很难伪造。故此签字很难伪造。n消息消息m的发送者不能否认此消息是他发送的，因为其他人的发送者不能否认此消息是他发送的，因为其他人不能造出此签字不能造出此签字s。 n接收设备使用公钥接收设备使用公钥e进行如下计算：进行如下计算：se = (md)e mod n = mde mod n = m mod n n接收设备计算接收设备计算se，若得到和解密的消息，若得到和解密的消息m相同的结果，就证相同的结果，就证明了发送者的签字是真的。明了发送者的签字是真的。 怠捍绘逝许很赛趾朝渝悔豌仇豌食牡氧毅包筑缚汾典樊工溃补卵赫词胞唾第十四章通信安全第十四章通信安全3114.8 小结小结激襄垂公敷您莲泼首萝衔吨晾撂已锥亲极运秉辖巡托朝拌稳莫酗佣魂央哼第十四章通信安全第十四章通信安全32