密码学的基本概念和信息理论基础.ppt
45页
密码学的基本概念和信息理 论基础 1什么是密码学• 密码学是研究密码系统或通信安全的一门学 科• 密码编码学是使得消息保密的学科，从事此 行的称为密码编码者• 密码分析学（密码破译学）是研究加密消息 的破译的学科，从事此行的称为密码分析者 ，精于此道的人被称为密码学家，现代的密 码学家通常是理论数学家2密码学的发展历史 • 第1阶段：1949年以前，科学密码学的前夜 • 第2阶段：从1949年到1975年 – 标志：1949年Shannon发表的《保密系统的信息理 论》一文，标志着密码学阶段的开始 • 第3阶段：1976年至今 – 标志：1976年Diffie和Hellman发表了《密码学新 方向》一文3保密通信的Shannon模型 4组成部分• X，明文（plain-text）： 作为加密输入的原始信息 • Y，密文（cipher-text）：对明文变换的结果 • E，加密（encrypt）：是一组含有参数的变换 • D，解密（decrypt）：加密的逆变换 • Z，密钥（key）：是参与加密解密变换的参数一个密码系统由算法以及所有可能的明文、密文 和密钥（分别称为明文空间、密文空间和密钥空间 ）组成。
5密码体制的分类 • 几种不同的分类标准 – 按操作方式进行分类 • 操作方式：是明文变换成密文的方法 • 替代操作、置换操作、复合操作 – 按照使用密钥的数量进行分类 • 对称密钥（单密钥），如DES密码体制 • 公开密钥（双密钥），如RSA密码体制• 普遍采用对称密钥和公钥密钥密码相结合的混合加密体制 ，即加解密采用对称密钥密码，密钥传送则采用公钥密码 – 按照对明文的处理方法进行分类 • 流密码 • 分组密码6Kerckhoffs假设 • 假定：密码分析者知道对方所使用的密码系统 – 包括明文的统计特性、加密体制（操作方式、处理 方法和加/解密算法 ）、密钥空间及其统计特性– 不知道密钥 • 成功的密码分析不权能够恢复出消息明文和密 钥，而且能够发现密码体制的弱点，从而控制 通信 • 在设计一个密码系统时，目标是在Kerckhoffs 假设的前 提下实现安全 7密码分析 • 密码分析 ：从密文推导出明文或密钥 • 密码分析：常用的方法有以下4类： – 惟密文攻击（cybertext only attack）； – 已知明文攻击（known plaintext attack）； – 选择明文攻击（chosen plaintext attack）； – 选择密文攻击（chosen ciphertext attack）。
8惟密文攻击 • 密码分析者知道一些消息的密文（加密算法相同） ，并且试图恢复尽可能多的消息明文，并进一步试 图推算出加密消息的密钥（以便通过密钥得出更多 的消息明文9已知明文攻击 • 密码分析者不仅知道一些消息的密文，也知道与 这些密文对应的明文，并试图推导出加密密钥或 算法（该算法可对采用同一密钥加密的所有新消 息进行解密） 10选择明文攻击 • 密码分析者不仅知道一些消息的密文以及与之对应 的明文，而且可以选择被加密的明文（这种选择可 能导致产生更多关于密钥的信息），并试图推导出 加密密钥或算法（该算法可对采用同一密钥加密的 所有新消息进行解密）11选择密文攻击 • 密码分析者能够选择不同的密文并能得到对应的明 文，密码分析的目的是推导出密钥主要用于公钥 算法，有时和选择明文攻击一起被称作选择文本攻 击 12密码系统 • 一个好的密码系统应满足： – 系统理论上安全，或计算上安全； – 系统的保密性是依赖于密钥的，而不是依赖于对 加密体制或算法的保密； – 加密和解密算法适用于密钥空间中的所有元素； – 系统既易于实现又便于使用 13密码学的基本功能• 保密性：基本功能，使非授权者无法知道消息的内容 。
• 鉴 别：消息的接收者应该能够确认消息的来源 • 完整性：消息的接收者应该能够验证消息在传输过程 中 没有被改变 • 不可否认性：发送方不能否认已发送的消息 14古典加密技术• 代替密码 • 置换密码15Vernam 密码• 明文：1 0 1 1 1 • 密钥：0 1 0 1 1 • 密文：1 1 1 0 016代替密码• 代替密码（substitution cipher）：明文中的每个字符被替换 成密文中的另一个字符 – 简单代替，即单字母密码，如Caesar(凯撒)密码； – 多码代替密码(同音代替密码)； – 多字母代替密码(字母成组加密，用Huffman编码作密码) ； – 多表代替密码，如Vigenère密码 17Caesar 密码•ADBECFDGEHFIGJ •HKILJMKNLOMPNQ •ORPSQTRGSHTIUJ •VDWEXFYGZH• f(x) = x + 3 mod 26 • 明文： GOOD • 密文： JRRG • f(x) = x + i mod 26 (i 為該字元的位置) • 密文： JSTG18Playfair密码• Playfair加密法，密钥为一个5乘5的矩阵， 将25个英文字母随意排列(其中I和J为同一位 置) • 加密规则：将明文字串分成两两字元组。
若明文字串长度为奇数，则在明 文后随意添加一个字符将每一字元组对应到密钥矩阵中 –如果构成一个矩形，则取对角线之字元为密文； –如果为一直线，则取上/下方（或左/右方）字元； –如果为一点，则可取八方之临近字元为密文 • 解密规则：加密规则的反向动作 19Playfair密码P I C N UX R O D Y •密钥： L T A F EQ V K Z GH B S M W明文：DEFFENCE ，分组后 (D, E) (F, F) (E, N) (C, E) 密文：YFDDFUUA 20作业• 论述Caesar(凯撒)密码、Playfair密码的加 密算法，并用程序实现Playfair加密算法 21置换密码• 置换密码（permutation cipher）：又称换位密码 （transposition cipher） ，并没有改变明文字母 ，只改变了这些字母的出现顺序 22代替密码的特点• 单字母代换密码 ：明文中字母的出现频度、重复字 母的模式和字母相互之间的结合模式等统计特性不 变，安全性差 • 多码代替密码 ：没有隐藏明文中不同字母的统计特 性 ，安全性有所提高。
• 多字母代替密码 ：字符块被成组加密 ，有利于抗击 统计分析 • 多表代替密码 ：有多个映射表，可隐藏单字母出现 的频率分布23Vigenère密码 – 构成 • 明文：每个字符惟一对应一个0~25间的数字• 密钥：一个字符串，其中每个字符同明文一样 对应一个数字，代表位移值，如a 表示位移 0 ，b 表示位移 1，c 表示位移 2，...... ）– 加密过程： • 将明文数字串依据密钥长度分段，并逐一与密 钥数字串相加（模26），得到密文数字串；• 最后，将密文数字串转换为字母串 24Vigenère密码的密码分析（1）• 第一步：确定密钥的长度，主要方法有： – Kasiski测试法；– 重合指数法 25Kasiski测试法• 基本原理：对于密钥长度为d的Vigenère密码，如果 利用给定的密钥表周期性地对明文字母进行加密， 则当明文中有两个相同的字母组在明文序列中间隔 的字母数为d的倍数时，这两个明文字母组对应的密 文字母组一定相同；反之，如果密文中出现两个相 同的字母组，则其对应的明文字母组不一定相同26重合指数法 • 对于长度为d的字母串，x=x1,x2,…,xn，“重合指数”指的 是x中两个随机元素相同的概率，记为：Ic(x)= 。
• 基本思想：对于长度分别为n的密文串y=y1y2…yn，将其 分为长度为n/d的d个子串Yi（i=1,2,…,d)，如果密钥长 度为d，则Ic(Yi)≈0.065(1≤i≤d) ，否则，因为采用不同的 密钥依位加密，子串Yi将更为随机对于一个完全随机 的密文串，Ic(y)≈26(1/26)2=0.038由于0.038与0.065的 差值足够大，所以在一般情况下，依据重合指数法能够 判断出正确的密钥长度 27Vigenère密码的密码分析（2）第二步：确定密钥通常采用重合互指数法 对于长度分别为n及n′的字母串x=x1x2…xn和 y=y1y2…yn，“重合互指数”指的是x的一个随机元 素与y的一个随机元素相同的概率，记为MIc(x,y) 其值仅依赖于(ki,kj) mod 26 Ki为第i个密钥字 在英文字母表中的序号，kj为第j个密钥字在英文 字母表中的序号通过采用重合互指数法，可以获得任何两个 子串Yi与Yj的相对移位 28Shannon的保密系统信息理论 • 1949年， Shannon发表了一篇题为《保密系统的信息 理论》的论文 • 用信息论的观点对信息保密问题进行了全面的阐述 ，使信息论成为密码学的一个重要理论基础。
• 宣告了科学的密码学时代的到来 • 从概率统计观点出发研究信息的传输和保密问题29通信系统模型 • 目的：在信道有干扰的情况下，使接收的信息无错 误或差错尽可能小30保密系统模型• 目的：使窃听者即使在完全准确地收到了接收信号 的情况下也无法恢复出原始消息31保密系统的数学模型• 信源是产生消息的源，在离散的情况下可以产生字 母或符号 • 当信源为无记忆时：（P为各元素的概率分布）LPp(m)=P(m1,m2,……,mL)=∏P(ml)L=1 • 密钥源是产生密钥序列的源，通常是离散的，为无 记忆均匀分布源，各密钥符号为均匀等概率 • 明文空间、密文空间、密钥空间 • 密文空间的统计特性由明文和密钥的统计特性决定 关于密文空间的条件概率分布，任何知道密文空 间和密钥空间的概率分布的人，都能确定密文空间 的概率分布和明文空间32• 在保密系统研究中，假定信道是无干扰的，对于合 法接收者，他知道解密变换和密钥，易于从密文得 到原来的消息m，即m=Dk(c)=Dk(Ek(m))• 在无干扰的条件下，假定密码分析者可以得到密文c ，而且一般假定密码分析者知道明文的统计特性、 加密体制、密钥空间及其统计特性，但不知道加密 截获的密文c所用的特定密钥。
密码的安全完全寓于 密钥安全性之中33密码体制的安全性（1）• 无条件安全或完善保密性（unconditionally secure） ： – 不论提供的密文有多少，密文中所包含的信息都 不足以惟一地确定其对应的明文； – 具有无限计算资源（诸如时间、空间、资金和设 备等）的密码分析者也无法破译某个密码系统34完善保密性 • 一个保密系统（P，C，K，E，D）称为完善的无条件的 保密系统，如果H(P)=H(P|C)，其中，P为明文集合，C 为密文集合，K为密钥集合，E为加密算法，D为解密算 法，则完善保密系统存在的必要条件是H(P)≤H(K)可 见，要构造一个完善保密系统，其密钥量的对数（密钥 空间为均匀分布的条件下）必须不小于明文集的熵 – 从熵的基本性质可推知，保密系统的密钥量越小，其 密文中含有的关于明文的信息量就越大 • 存在完善保密系统如：一次一密（one-time pad）方案；不实用35密码体制的安全性（2）• 实际上安全 – 计算上安全：算出和估计出破译它的计算量下限 ，利用已有的最好的方法破译该密码系统所需要 的努力超出了破译者的破译能力（诸如时间、空 间、资金等资源）。
– 可证明安全：从理论上证明破译它的计算量不低 于解已知难题的计算量36伪密钥和惟一解距离 • 当分析者截获到密文c时，他首先利用所有的密钥对其 进行解密，并得到明文m。
