前 言

密码学的历史分成三个阶段 ： l       1949年前，凭简单技巧来设计和分析密码； l       1949年C. E. Shannon发表文章 “Communication Theory of Secret System”Bell System Technical Journal v.28 n.4 1949 p.656-71为私钥密码系统建立理论了基础。密码学 形成一门科学。

l       1976年W. Diffie & M. E. Hellman发表文章“New Directions in Cryptography”IEEE Transactions on Information Theory, v. IT-22 n. 6 Nov. 1976 p.644-654 导致密码学的一场革命， 开创了公钥密码学新纪元 1. 密码学的基本概念 1.1 密码编码学与密码分析学

密码编码学 寻求保证信息安全性的方法及保证信息认证性的方法 密码分析学 研究经过加密的信息的破译及伪造信息 采用密码技术隐藏或保护需要保密的信息。 明文 (plaintext) —— 被隐藏的信息 密文 (ciphertext)—— 隐藏后的信息 加密算法 (encrypt algorithm)——对明文加密时采用的一组规则 解密算法 (decrypt algorithm)——对密文解密是采用的一组规则

密钥 (key)——加、解密通常在一组密钥控制下进行，分别称为 加密密钥和解密密钥。 1.2密码系统 根据密钥特点分成 ： 1 对称密码系统（单钥或私钥密码系统private key cryptography）——加密密钥与解密密钥相同或彼此容易确定。 2 非对称密码系统（双钥或公钥密码系统public keycryptography） ——加密密钥与解密密钥不同，从一个难于推出另一个。

根据加密方式分成： 流加密(stream cipher)——将明文信息逐位加密 分组加密(block cipher)——将明文分成块逐块进行加密 公钥密码属于分组密码（只有概率加密属于流加密） 1.3 攻击(attack)类型 密码系统所遭受的攻击分成主动和被动两种类型:

被动攻击： 在信息传输和处理系统中，除了发送者和接受 者外还有窃听者。他们使用搭线、电磁、声音 等方式窃取机密信息，经过分析推断出明文。 主动攻击： 非法入侵者采取删除、修改、插入、重放、伪 造等手段向系统注入假消息，从而达到损人利 己的目的.

破译密码是指从密文迅速确定明文或从明文—密文对迅速 确定密钥Kerckhoff假设是指“假定密码分析者知道加密者 使用的密码系统”。设计密码系统的目标是在Kerckhoff假 设之下是安全的. 对密码系统最普通的攻击等级大体区分如下 : l 仅有密文——对手只掌握一个密文行 l 已知明文——对手掌握一个明文x和它对应的密文y

l  有选择的明文——对手有机会使用加密机，他可以 选择一个明文x并构造相应的密文。 l  有选择的密文——对手有机会使用解密机，他可以 选择密文解出相应的明文。 以上各类攻击的强度逐次加强。

2. 密码学的计算复杂性理论 通过分析算法和问题的复杂性可对密码算法和技 术进行比较，确定它们的安全性。 2.1. 问题和算法 问题的描述：1) 给定所有未定参数的一般性描述。 2) 陈述“答案”或“解”必须满足的性质。

算法：求解某个问题的一系列具体步骤，可能一个问题 有多种算法 理解为求解该问题的计算机程序）。 可解与不可解： 如果一个算法能解决该问题的所有实例，则称该算 法能解答该问题。 如果针对一个问题至少存在一个算法可以解答该 问题， 则称该问题是可解的。否则称为该问题是不可解的。

2.2 算法的复杂性 一个算法的复杂性是由该算法所需要的最大运算时间和存储空间来度量的。它们分别是规模为n（输入数据的长度）的所有实例的时间和空间需求的平均值的函数 和 。 一个算法的复杂性通常用符号“O”表示量级。好处在于它与处理系统无关（如：处理机速度、数据类型及表示）。 表示存在常数 c和 ，对所有 ，

算法按复杂性分类 多项式时间算法——时间复杂性为 ，t为常数。 指数时间算法——时间复杂性为 ，t为常数， 是多项式。 当 大于常数小于线性函数时，称为超多项式时 间算法.

2.3. 问题复杂性 使用算法复杂性理论为工具，将大量典型的问题按求解代价进行分类。从密码学意义上，我们最关心NP和NP完全问题的理论。 确定的图灵机 有无限读写能力的有限自动机，每一步操作的结 果唯一确定. 非确定的图灵机 有无限读写能力的有限自动机，每一步操作的 结果有多种选择. 易解问题与难解问题 在确定图灵机上用多项式时间可解的问题，称为全体易解问题,集合记为P。否则，称为难解问题。

NP问题 在非确定的图灵机上用多项式时间可解的问题，称为非确定型多项式时间可解问题（NP问题）。其含义是，若机器猜测一个解，非确定的图灵机就可以在多项式时间内验证它的正确性。 全体非确定型多项式时间可解类记作NP。 显然 。 尚未证明。 几个NP问题的例子 1）背包问题（子集和问题）

由n个正整数组成的集合A = ，现有整 数S，确定是否有子集 使得 。 显然，给定一个子集验证其和是否等于S是容易的。 试验所有子集的时间复杂性为 . 2）SAT问题 判定一个n元布尔函数 ，是否存在 一组赋值 使得 。

Cook 证明： NP中的每个问题都可用多项式时间转化成为可满足问题。 若可满足问题是易解的，则NP中每个问题都是易解的。 一个NP问题称为“NP完全的”，是指NP中每个问题都可以用 多项式时间转化为该问题。NP完全问题的全体记作NPC。

NPC具有如下性质 若其中任何一个问题属于P，则所有NP问题都 属于P且P=NP.

3.2. 保密系统与认证系统的理论基础 3.2.1 保密系统的理论基础 3.2.1.1 保密系统的数学模型 1949年Claude Shannon发表的“保密系统的信息理 论”中使用信息论观点，对信息保密问题作了全面阐述。 以概率统计为手段研究信息传输和保密问题。

3.2.1.2 保密系统的安全性 衡量方法： 无条件安全 如果具有无限计算资源的密码分析者也无法破 译的系统成为无条件安全。 计算安全性 利用已有的最好方法来破译该系统所需的能力 超过密码分析者的能力（从时间、空间、资金 等资源上）。 使用信息论熵的概念可以证明： l       保密系统的密钥量越小，密文中含有明文的信息量越大。从密码设计者来讲，应该使密钥量足够大。 l       每发送一个信息都使用新的密钥，并在安全信道上传送密钥（一次一密）。

3.2.2认证系统的理论基础 防止消息被篡改、删除、重放、伪造的有效方法是使发送出的消息具有被验证的能力。使接受者或第三者能够识别和确认消息的真伪。实现这种功能的系统称为认证系统。 认证理论和认证技术是现代密码学的重要研究领域。安全的认证系统应满足： l      真正的接受者能够验证和证实消息的合法性和真实性。 l       发送者发送消息后不能否认。 l       其他人不能伪造合法消息。 l       通信双方发生争执时可由仲裁者为第三方解决问题。

G.J.Simmon发表的文章“Authentication Theory / Coding Theory”LNCS196 (1985) p.411-432 ( Advances in Cryptology-CRPTO’84) 首次提出认证系统的理论。 认证理论研究对象是： l        推导欺骗者成功概率的上界 l        构造使欺骗者成功概率最小的认证码 认证系统模型： l 无仲裁者的认证系统模型：该模型涉及三方，即 消息发送者、消息接受者、敌手。发送者与接受 者互相信任并拥有同样的秘密信息，共同抵御敌手。

l       有仲裁者的认证系统模型：该模型涉及四方， 即消息发送者、消息接受者、敌手、仲裁者。发 送者与接受者互相不信任，但他们都信任仲裁者。 仲裁者拥有全部秘密信息， 决对不参与欺骗。 认证系统的数学模型 无仲裁者的认证模型 无仲裁者的认证模型为四元组 ( S, A, K, R ) 其中 S 信源集 A 认证标签集 K 密钥空间 R 认证规则集 消息集M=S*A，对每个k有认证规则 发送者和接受者执行如下协议：

l共同选择一个随机密钥k 发送者要发送s，计算 ，将 发送给接受者 接受者收到 后计算 。如果 ，则s是真消息，否则拒绝。 两种类型攻击 模仿攻击 敌手在信道中插入一个消息 ，希望接受者把 它作为真消息接收。 代替攻击 敌手在信道中观察到一个消息 后，将 改 为 ，其中 ，希望接受者把它作为真消 息接收。 令 是敌手采用模仿攻击时欺骗接受者成功的最大概率 是敌手采用代替攻击时欺骗接受者成功的最大概率 是敌手欺骗接受者成功的最大概率。