《密码学基础理论.》由会员分享,可在线阅读,更多相关《密码学基础理论.(63页珍藏版)》请在金锄头文库上搜索。
1、第6章 密 码 就广义而讲,保密措施也可以分为两 类:一类称为信道保密,它指专人传递或 者专线传递以及采用扩谱与流星余迹传送 等信道掩蔽和保护的一系列措施。另一类 称为消息(信号)保密,它主要针对传送的信 号加以掩蔽和保护,本章只讨论后者。 6.1 6.1 密码学的基本概念密码学的基本概念 6.2 6.2 保密学的理论基础保密学的理论基础 6.3 6.3 序列序列 ( ( 流流 ) ) 密码密码 6.4 6.4 分组分组 ( ( 块块 ) ) 密码密码 *6.5 *6.5 公开密钥密码公开密钥密码 *6.6 *6.6 认认 证证 系系 统统 6.7 6.7 模拟消息加密体制模拟消息加密体制 6
2、.8 6.8 GSMGSM的鉴权与加的鉴权与加 密密 6.1 密码学的基本概念 通信加密,从消息与信号的类型划分 ,可分为数字加密与模拟加密两大类。 数字加密还可以按照所采用的密钥类 型划分为单钥制与双钥制两类。 所谓单钥制是指通信的双方发送端和 接收端采用的是同一种密钥,又称为对称 式密钥。所谓双钥是指通信的双方所采用 的是不同的两种密钥,称为不对称式密钥 。 模拟加密,它是指对模拟信号的加密 ,在60 年代以前是话音加密的主导体制。 它主要是依据对模拟信号的置乱来实现的 。 密表加密是以字母和数字为单元进行 加密处理的,又称为单表密码。它的加密 算法很简单,一般用一个简单的线性方程 来表示
3、: C am+b,modq 这里C为密文,m为明文,而a、b、q 则是由密钥规则所决定的数。 为了去掉循环多表密码体制的缺点, 可采用一种叫滚动密钥的密码体制,它是 一种非循环体制。比如通信双方约定以某 一本书为密钥,具体加密方法是以该书的 某页、某行、某句开始为密钥,对明文序 列逐个字母加密,求得密文字母序列发送 出去,接收端可按照同样的规则逐个字母 解密恢复成原来的明文序列,这种密码体 制破译比较困难。 6.2 保密学的理论基础 40年代末,C.E.Shannon在发表信息 理论奠基性论文“通信中的数学理论”的同 时,发表了“保密系统的信息理论”,他引 用信息论的观点对信息的保密问题作了系
4、 统和深入的描述和分析。 一、 保密系统的数学 模型和基本定理 保密系统是以研究通信系统的安全性 为目的的专用通信系统。其实质是为了提 高通信系统中信息传输和存储的安全和保 密。 作为授权合法用户A的公钥,它可以 在任何公开的密码簿上查找到,供对方用 户B或任一第3者用户解密用,以验证是否 是授权的合法用户A发送来的信息。 在认证时,授权的合法用户A为了 保证自己所传送的信息安全,首先采用 仅用户A掌握的私钥DkA进行加密,构成 密文送至对方,这时用户B或者任一第三 方均可以采用查找到的用户A的公钥EkA 进行解密,若能解出明文,则证明这明 文系合法用户A所发送,而并非非法用户 伪造,若不能解
5、出明文,则证明该信息 系非法用户伪造的,而并非A所发送,从 而达到防伪造的目的。 在进行保密通信时,授权的合法用户 A为了防止传送的信息被窃听,首先采用加 密变换Tk进行加密,构成密文之后送至对 方。 一般保密问题,实质上要解决保密通 信系统在安全保密指标下的优化问题,它 可通过信源和信宿之间的匹配来实现。 定理6-2-1:不考虑信道干扰时,具有 加密、解密变换为Tk1和Tk2,且Tk1Tk2=1的 保密通信系统,当系统满足明文M和密文C 统计独立时,即HM | C=HM,可 以构成一个理想的保密系统。 二、 惟一解距离 和明文信源冗余度 前面叙述了保密学基本概念和 基本定理,下面将探讨如何度
6、量和 实现理论上的保密。 40年代末,密码学奠基人之一 仙农引入了一个非常重要的惟一解 距离(ud)的概念。它是从密码分析 学角度来考虑的一个重要物理量。 仙农曾用下列直观图形从物理概念上 形象地说明惟一解距离的概念,从前面分 析得知密码C的随机性(即保密性能)是取决 于密钥K与信源明文M的性质,即C=TK(M) 。它可以形象地用图6-2-3图形中两条曲线 的走向及其交点来说明。 图6-2-3 惟一解距离示意图 为了实现理想保密,即N0, 存在以下两种可能性。 (1) 完全保密体制 (2) 理想保密体制 (1) 实现保密的过程实质上是使密文随 机化的过程,它不仅可以通过传统的增大 密钥的方法来
7、实现,也还可以等效地从减 少信源明文的冗余度的方式实现。 (2) 实现无交点,即ud=N0不大现 实,达不到,但它确实给我们明确地指出 ,采用增大密钥量、减少明文冗余度,或 者同时采用以上两种手段,至少可以实现 将惟一解距离ud=N0推得更远些。 所谓随机密码,它应满足以下3个条件 。 (1) 长度为N的可能明文总数为T=2NR 。 (2) 长度为N的可能明文2NR,可以划分 为两类,一类是高概率组,是有意义的, 它含有:S=2Nr个。 (3) 使用了2H(K)个等概率出现的密钥。 三、 实际保密系 统 前面,我们研究了理论保密性 能和实现理论保密的两种体制:完全 保密和理想保密。但是这两类理
8、论保 密体制实现都极其困难。 下面,我们将从推远交点增大 惟一解距离改善理论保密性能和提高 密码的工作特性的改善实际保密性两 个方面进一步探讨。 减少信源冗余度,总的说来可以 分为两类:一种是直接法,即采用信 源编码的方法直接消除信源的冗余。 另一类是间接法,即采用扩散与混淆 的方法将信源冗余度在更大的范围上 扩散开或者加以扰乱混淆,以实现间 接减少信源冗余度的目的。 工作特性W(N)是一个由系统所提 供的“实际保密性能”的度量。两种不 同的密码体制可以有相同的惟一解距 离,但工作特性不一样。 一个好的实际保密系统,其W(n) 曲线虚线部分要保持足够高,以防止 窃听者找出其解,或者要迅速使它取
9、 足够大的值,以致当窃听者分析出其 解时,已经失去时效。 四、 现代密码中的计 算复杂性理论基础 一个密码系统的安全性可以通过破译 该系统的最好算法的计算复杂度来度量。 复杂度理论是指处理算法难度的分类。而 算法难度则是指执行一个算法所需消耗资 源的一个测度,这里资源是指下列4种类型 :基本操作的数目;所耗费的时间; 需要的存储空间;需要的硬件数量。 6.3 序列(流)密码 序列密码系统是单钥体制中的两个最 主要加密体制之一。它与分组(块)加密比较 具有如下优点。序列加密最大优点是适 合于实时加密,所以对实时的数字话音特 别适合。序列密码有较成熟的理论作指 导,它的设计、分析较分组密码容易。
10、序列密码系统的加密和解密较分组密码易 于实现。由于有以上3个优点,序列加密被 广泛地用于实时业务传输的加密中。 一、 序列密码的基本 概念 前面,我们讨论了“一次一密”的完全 保密的密码体制,同时也指出,纯随机的 无限长的随机序列密码,产生、同步、管 理、分配都极其困难,因此是不实用的。 序列a=a1a2an)若满足下列递推关系 : ai+n=f(ai,ai+1ai+n-1),i1 二、 m序列的非线性组合 序列 既能保留m序列的良好随机统计特性和 产生同步方便的优点,又要设法提高其线性 复杂度的方法,无疑在序列密码中应首先要 考虑的方法。前馈序列就能同时满足上述特 性的一种重要方法。它是通过
11、一个或几个m 序列加上一个非线性前馈网络来产生既具有 周期长、随机特性好又具有线性复杂性高的 伪随机序列。这类前馈序列又可分为基于单 个m序列的前馈序列和基于若干个m序列的 前馈组合序列两大类型。 三、 非线性移位寄存序列: M序列 上面我们讨论了线性移位寄存序列以 及在它基础上的非线性组合序列,下面将 简要讨论非线性移位寄存器序列。就反馈 函数的代数标准型而论,不同的n级非线性 反馈移位寄存器有22n个,其中只有2n个是 线性反馈移位寄存器。二者之间的巨大差 别告诉我们,使用非线性反馈移位寄存器 来构造密钥序列将会给设计者提供充分的 选择余地,从而大大增加破译难度。 6.4 分组(块)密码
12、一、 分组加密的基本 概念 一个好的分组加密算法应满足: (1) 分组的明文字长n要足够大,以防 止明文穷举攻击法奏效; (2) 密钥量要足够大(即置换子集中的 元素足够多)以防止密钥穷举攻击法奏效; (3) 由密钥确定置换的算法足够复杂( 即明文与密文之间的联线规律),使破译者 除了用穷举法以外,无其他捷径可循。 常用的代换有下述几种。 (1) 左循环移位代换 (2) 右循环移位代换 (3) 模2加1代换 (4) 线性变换 (5) 坐标变换 (6) 仿射变换 二、 数据加密标准 (DES) 数据加密标准(DES)是由IBM研制, 并由美国国家安全局(NSA)认证是安全的。 它已于1976年作
13、为联邦标准被采用,1977 年美国国家标准局正式批准。 DES可以构成分组(块)加密和序列(流) 加密形式。各用户之间惟一的差别是密钥 不同。当DES被用作分组加密时,密钥长 为64位,当然56位代表密钥序列,而其余 的8位作校验位,而每一校验位都对一个8 位序列形成奇校验。 在这种分组加密模式中,同样的明文 总是形成严格相同的密文。DES是靠由模 块组成的复杂系统完成其工作的。 DES是一类对二元数据进行加密的算 法,数据分组长度为64bit(8byte),密文分 组也是64bit,密钥长度为64bit,其中含 8bit奇偶校验位,有效密钥长度为56bit。 (1) 初始置换IP。将64bi
14、t明文按一定 规律进行置换,得到一个乱序的64bit明文 组再将它分成左、右两组各32bit以Ri与Li 表示送至乘积变换。 (2) 初始逆置换IP-1。它是将经乘积变 换的16次迭代后所给出的64bit密文组,按 照逆置换表进行逆置换后按表中行读出得 到输出的64bit密文组。 (3) 乘积变换。乘积变换是DES算法的核心 部分,它将经初始变换后明文分为左、右两个 32bit分组,进行迭代运算,在每次迭代过程中左 、右两组不断地彼此交换位置,而每次迭代仅对 右边分组的32bit进行一系列加密变换,如图6-4-5 所示,然后左、右两分组彼此交换位置,下一轮 仍对右边分组,即原来左边分组的32b
15、it与右边经 加密变换后的32bit逐位模2加后的32bit数据再进 行加密变换,一直进行下去共进行16次迭代,而 每一轮迭代时,右边都要进行选择扩展运算E、 加密模2加运算、选择压缩远算S、置换运算P和 左右混合运算。 (4) 选择扩展运算E。它将右边每组 32bitRi-1扩展成每组48bit的输出,其扩展 规律是按照将右边32bit数据进行模4运算, 模4运算中周期为0和1的数据重复一次,周 期为2和3的数据不重复,这样32位中就有 一半16位要重复,加上原来的32位即 16+32=48,即可构成48位。 (5) 加密运算。将上面选择扩展运 算E输出的48bit明文数据与子密钥产生 器输
16、出的48bit子密钥逐位模2相加进行 加密,输出48bit密文组。 (6) 选择压缩运算S。它将来自加 密运算的48bit密文数据自左至右分成8 组,每组6bit然后并行送入8个S盒,而 每个S盒为一非线性代换网络,它有4 个输出,如图6-4-7所示。 图6-4-7 选择压缩运算S框图 (7) 置换运算P。它是将S1至S8盒输出 的32bit数据进行坐标变换。 (8) 其他部分。置换P输出的32bit数据 要与左边32bit即Ri-1逐位模2相加,所得结 果作为下一轮迭代用的右边数据段,并将 右边Ri-1并行到左边寄存器,作为下一轮迭 代用的左边数据段。 (9) 子密钥产生器。这部分虽不属乘积 变换,但是它是乘积变换的控制部分。 第二种形式数据序列(流)加密配置是 输出反馈(OFB),它与CFB的差别是现在 的密钥流不依赖于数据如图6-4-9所示。要 注意,被反馈的输出码组,是密钥流而不 是密文被反馈来生成新的密钥流。不管 DES如何配置,其运算都依赖于56位密钥 。 图6-4-9密钥流反馈模式的DE