《网络信息安全》课程 第二讲数据加密算法 主讲:段云所副教授 北京大学计算机系
网络信息安全 课程 第二讲 数据加密算法 主讲 段云所 副教授 北京大学计算机系 北京大学计算机系
数据加密 密码:是一组含有参数的变换。 明文( plaintext):作为加密输入的原始信息。 加密算法:变换函数 密文( ciphertext:明文变换结果 密钥(key):参与变换的参数
数据加密 密码 是一组含有参数的变换 明文 plaintext) 作为加密输入的原始信息 加密算法 变换函数 密文 ciphertext):明文变换结果 密钥 key):参与变换的参数
加密模型 钥 密钥 密文 明文 明文 加密算法 解密算法
加密模型 明文 明文 密文 加密算法 解密算法 密钥 密钥
密码体制 通常一个完整密码体制要包括如下五个要素M,CK,E,D (1)M是可能明文的有限集,称为明文空间 (2)C是可能密文的有限集,称为密文空间 (3)K是一切可能密钥构成的有限集,称为密钥空间 (4)对于密钥空间的任一密钥,有一个加密算法和相应的解密算法,使得 ek:M>C和dC→M分别为加密解密函数,满足d((x)=x,这里x∈M。 个密码体制要是实际可用的,必须满足如下特性: (1)每一个加密函数e和每一个解密函数d都能有效地计算。 (2)破译者取得密文后,将不能在有效的时间内破解出密钥k或明文x。 (3)一个密码系统是安全的必要条件穷举密钥搜索将是不可行的,即密钥 空间非常大
密码体制 通常一个完整密码体制要包括如下五个要素M,C,K,E,D 1 M是可能明文的有限集 称为明文空间 2 C是可能密文的有限集 称为密文空间 3 K是一切可能密钥构成的有限集 称为密钥空间 4 对于密钥空间的任一密钥 有一个加密算法和相应的解密算法 使得 ek:M->C 和 dk:C->M分别为加密解密函数 满足dk(ek(x))=x, 这里 x M 一个密码体制要是实际可用的 必须满足如下特性 1 每一个加密函数ek和每一个解密函数dk都能有效地计算 2 破译者取得密文后 将不能在有效的时间内破解出密钥k或明文x 3 一个密码系统是安全的必要条件穷举密钥搜索将是不可行的 即密钥 空 间非常大
密码算法分类: 按发展进程分:密码的发展经历了古典密码、对称密钥 密码、公开密钥密码的发展阶段。古典密码是基于字符 替换的密码,现在已很少使用了,但是它代表了密码的 起源。现在仍在使用的则是对位进行变换的密码算法。 这些算法按密钥管理的方式可以分为两大类,即对称算 法与公开密钥算法。对称算法的加密密钥和解密密钥相 同,这些算法也叫作秘密密钥算法或单密钥算法。 按加密模式分:对称算法又可分为序列密码和分组密码两 大类。序列密码每次加密一位或一字节的明文,也可以称 为流密码。序列密码是手工和机械密码时代的主流。分组 密码将明文分成固定长度的组,用同一密钥和算法对每 块加密,输出也是固定长度的密文
密码算法分类 按发展进程分 密码的发展经历了古典密码 对称密钥 密码 公开密钥密码的发展阶段 古典密码是基于字符 替换的密码 现在已很少使用了 但是它代表了密码的 起源 现在仍在使用的则是对位进行变换的密码算法 这些算法按密钥管理的方式可以分为两大类 即对称算 法与公开密钥算法 对称算法的加密密钥和解密密钥相 同 这些算法也叫作秘密密钥算法或单密钥算法 按加密模式分 对称算法又可分为序列密码 和分组密码 两 大类 序列密码每次加密一位或一字节的明文 也可以称 为流密码 序列密码是手工和机械密码时代的主流 分组 密码将明文分成固定长度的组 用同一密钥和算法对每一 块加密 输出也是固定长度的密文
算法分类 ·经典密码 代替密码:简单代替多名或同音代替多表代替多字母或多码代替 换位密码 对称加密算法 DES AES 非对称(公钥)算法 RSA、背包密码、 McEliece密码、 Rabin、椭圆曲线、 EIGamald H
算法分类 • 经典密码 代替密码 : 简单代替 多名或同音代替 简单代替 多名或同音代替 多名或同音代替 多表代替 多字母或多码代替 多字母或多码代替 换位密码 : •对称加密算法 DES AES •非对称 公钥 算法 RSA 背包密码 McEliece密码 Rabin 椭圆曲线 EIGamal D_H
简单代替密码或单字母密码 简单代替密码就是将明文字母表M中的每个字母用密文字母表C中的相应字母来代替。这一类密 码包括移位密码、替换密码、仿射密码、乘数密码、多项式代替密码、密钥短语密码等。 (1)移位密码是最简单的一类代替密码,将字母表的字母右移k个位置,并对字母表长度作模运算 ,形式为: (1)e(m=(k+m)=c mod q 解密变换为 (2)dK (c)(m-kF-m mod q 其中q为字母表M的长度,“m既代表字母表M中的位置,也代表其在M中的位置。“c既代表字母表 C中的位置,也代表其在C中的位置。凯撒( Caesar)密码是对英文26个字母进行移位代替的密码 ,其φ=26。这种密码称为凯撒密码,是因为凯撒使用过κ=3的这种密码。使用凯撒密码,将明文 M= Peking university加密为 C=Uipnsl zsnaiwxnyd (2)在替换密码中,可对明文字母表进行q个字符的所有可能置换得到密文字母表。移位密码是 替换密码算法一个特例。 (3)乘数密码也是一种替换密码,它将每个字母乘以一个密钥κ,即 ()ek(m)=km mod 其中,k和q为互素的,这样字母表中的字母会产生一个复杂的剩余集合,若k和q不互素,则会有 些明文字母被加密成相同的密文字母,而且不是所有的字母都会出现在密文字母表中 (4)替换密码的另一个特例就是仿射密码,加密的形式为: (4)em)=(km+k2)= c mod q其中,k和g是互素的 简单代替密码由于使用从明文到密文的单一映射,所以明文字母的单字母出现频率分布与密文中 相同,可以很容易地通过使用字母频率分析法进行只有密文的攻击
简单代替密码或单字母密码 简单代替密码就是将明文字母表 M中的每个字母用密文字母表 C中的相应字母来代替 这一类密 码包括移位密码 替换密码 仿射密码 乘数密码 多项式代替密码 密钥短语密码等 1 移位密码是最简单的一类代替密码 将字母表的字母右移 k个位置 并对字母表长度作模运算 形式为 1 e k(m)=(k+m) =c mod q 解密变换为 2 d k(c)=(m-k)=m mod q 其中 q为字母表 M的长度 “ m ”既代表字母表 M中的位置 也代表其在 M中的位置 “ c ”既代表字母表 C中的位置 也代表其在 C中的位置 凯撒 Caesar 密码是对英文26个字母进行移位代替的密码 其 q=26 这种密码称为凯撒密码 是因为凯撒使用过 k=3的这种密码 使用凯撒密码 将明文 M= Peking University加密为 C=Ujpnsl Zsnajwxnyd 2 在替换密码中 可对明文字母表进行 q个字符的所有可能置换得到密文字母表 移位密码是 替换密码算法一个特例 3 乘数密码也是一种替换密码 它将每个字母乘以一个密钥 k 即 3 e k(m)=km mod q 其中 k 和 q为互素的 这样字母表中的字母会产生一个复杂的剩余集合 若 k和 q不互素 则会有一 些明文字母被加密成相同的密文字母 而且不是所有的字母都会出现在密文字母表中 4 替换密码的另一个特例就是仿射密码 加密的形式为 4 e k(m)=(k1m+k 2) =c mod q 其中 k1和 q是互素的 简单代替密码由于使用从明文到密文的单一 映 射 所以明文字母的单字母出现频率 分 布与密文中 相同 可以很容易地通过使用字母频率 分 析法进行 只有密文的攻击
算法历史 (1)希腊密码(二维字母编码查表):公元前2世纪 bg 例: Peking University 35152524332245332451154243244454
算法历史 (1)希腊密码 二维字母编码查表 :公元前2世纪 v w x y z q r s t U l m n o p f g h ij k a b c d e 例 Peking University 35 15 25 24 33 22 45 33 24 51 15 42 43 24 44 54
算法历史 (2)凯撒密码:将宇母循环前移k位。 例k-5时对应关系如下: abcdefghijklmnopgrstuvwxyz fg hijkImnopgrstuvwxyzabcde 明文: Peking University 密文: Ujpnsl Zsnajwxnyd
算法历史 (2)凯撒密码 将字母循环前移k位 例 k-5时 对应关系如下 a b c d e f g h i j k l m n o p q r s t u v w x y z f g h i j k l m n o p q r s t u v w x y z a b c d e 明文 Peking University 密文 Ujpnsl Zsnajwxnyd
若将字母编号a-对应为1-26 恺撒变换:c=m+kmod26 更一般 仿射变换:c=km+k2mod26 k1=1为凯撒变换
若将字母编号a-z对应为1-26 则 恺撒变换 c=m+kmod26 更一般 仿射变换 c=k1m+k2 mod 26 k1=1为凯撒变换
