02 古典密码.ppt

概念 如何计算a对模m的逆？ 求逆算法 算法描述 C语言实现 完全剩余系 简化剩余系 同余式解 同余式解 模运算 古典密码 基于字符的密码 ? 替换密码（substitution cipher)：就是明文中的每一个字符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。 ? 置换密码(permutation cipher)，又称换位密码（transposition cipher)：明文的字母保持相同，但顺序被打乱了。 置换密码 置换密码－换位法 将明文按行顺序写入二维矩阵中，再按给定列顺序读出来构成密文。 明文：cryptography and network security 置换密码－换位法 密钥:n o w a r 顺序:2 3 5 1 4 明文:c r y p t o g r a p h y a n d n e t w o r k s e c u r i t y 密文：panwetcohnrurgyekrtpdocyyratsi 替换密码 替换密码 ? 替换密码（substitution cipher)：就是明文中的每一个字符被替换成密文中的另一个字符。 1、单表替换密码 移位密码、乘法密码、仿射密码、密钥短语密码 2、多表替换密码 维吉利亚密码 3、多字母替换密码 Hill 替换密码－移位密码 注1：26个英文字母与模26余数集合{0,….,25}建立一一对应 替换密码－移位密码 替换密码－移位密码分析 替换密码－乘法密码 替换密码－乘法密码 ABCDEFGHIJKLMNOPQRSTUVWXYZ AJSBKTCLUDMVENWFOXGPYHQZIR 替换密码－乘法密码分析 对于乘数密码，当且仅当k与２６互素时，加 密变换才是一一映射的，因此k的选择有１１ 种： k=3,5,7,9,11,15,17,19,21,23,25 可能尝试的密钥只有11个 替换密码－仿射密码 替换密码－仿射密码 单表替换密码的破译 1、明文与密文中的字母存在一一对应关系 2、语言的统计特性（字母的频数、使用频率） 对抗频率分析的办法 ? 多表替换密码 ? 多字母替换密码 多表替换密码 多表替换密码： 是以一系列（两个以上）替换 表依此对明文消息的字母进行替换的方法。 维吉尼亚（Vigenere)密码 明文:tradition cipher 密钥:fast 明文: trad itio ncip her 密钥: fast fast fast fas 密文: yrsw ntah scai mej Hill密码 基本思想：将n个明文字母通过线性变换将它们转换为n个密文字母，解密时只需做一次逆变换，密钥就是变换矩阵 Hill密码 一次一密方案 明文、密钥和密文均用二元数字序列表示，当明文M=(m1,m2,…,mn)，密钥K=(k1,k2,…,kn),密文C=(c1,…,cn)，加密方式为：ci=mi+ki mod 2 计算机安全与必威体育官网网址 张 旻 杭 州 电 子 科 技 大 学 古典密码 密码学基本概念 密码学基本概念 基本术语 原始可理解的消息或数据称为明文,用某种方法伪装消息以隐藏它的内容的过程称为加密,加密后的消息称为密文,密文转变为明文的过程称为解密. 用于加密和解密的数据函数称为密码算法 密码学基本概念 密码学基本概念 密码学基本概念 密码学基本概念 密码学基本概念 密码学基本概念 数论基础 初等数论是一门研究整数及其性质的学科 基本概念（1) 1、整除 2、倍数 3、因数（约数） 整除的性质 概念、定理（2) 素数 除了 外，没有其它的约数 概念（3) 公因子，最大公因子 公倍数，最小公倍数 概念推广 最大公约数、最小公倍数的概念可以推广到多个数的情形 欧几里德算法 欧几里德算法 欧几里德算法 欧几里德算法 欧几里德算法描述 迭代算法 输入:任意两个正整数a,b,ab 输出:a,b的最大公因数 扩展欧几里德算法 扩展欧几里德算法 扩展欧几里德算法 扩展欧几里德算法 迭代过程举例 扩展欧几里德算法 同余 同余式基本定理