(好资料)2[1].2_单表代替密码

第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 第二节单表代替密码第二节单表代替密码 1 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 代替密码代替密码是通过对明文字母表的置换，将明文 加密为密文的密码。 代替密码分为单表代替和多表代替 是通过对明文字母表的置换，将明文 加密为密文的密码。 代替密码分为单表代替和多表代替 2 代替密码代替密码 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 3 假设所采用语言的字母表含有假设所采用语言的字母表含有q个字母个字母, 即即 Zq=0, 1, , q-1 集合集合Zq上置换的全体记为上置换的全体记为SYM(Zq), 则则SYM(Zq) 是是 Zq上的对称群 。上的对称群 。 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 定义定义2.1 设设k = ( 1, 2, n, ) 是一列置换，是一列置换， x = (x1,x2,xn,)是一列明文，其中是一列明文，其中i SYM(Zq), xi Zq。变换。变换Ek将将n-明文组明文组 x = (x1,x2,xn)加密成加密成n- 密文组密文组 y = (y1,y2,yn), 即即 Ek( 1(x1), 2(x2), , n(xn) = (y1,y2,yn) = y 4 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 称上述加密方式为称上述加密方式为代替加密代替加密(substitution)。当 。当 1= 2= n时时, 称称Ek为为单表代替加密单表代替加密。否则。否则, 称 其为 称 其为多表代替加密多表代替加密。称 。称 i为为代替加密密表代替加密密表。 5 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 6 由于由于SYM(Zq)的阶等于的阶等于q!, 故单表代替密码共有故单表代替密码共有q! 个个(其中含恒等代替加密其中含恒等代替加密EI)不同的代替加密密表。 下面介绍几种简单的单表代替密码。 不同的代替加密密表。 下面介绍几种简单的单表代替密码。 单表代替单表代替 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 以下将以下将q个字母的字母表与个字母的字母表与Z模模q中数作一一对应中数作一一对应, 用 每个字母对应的数字代替该字母。例如 用 每个字母对应的数字代替该字母。例如, 将英文字母表作 如下对应 将英文字母表作 如下对应: 7 移位代替密码移位代替密码 abcdefghijklm 012345678910 11 12 nopqrstuvwxyz 13 14 15 16 17 18 19 20 21 22 23 24 25 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 加密变换为：加密变换为： Ek(m) = m + + k c (mod q) 0 m, cq 解密变换为：解密变换为： Dk= = Eq k(c) m (mod q) 移位代替密码的密钥空间移位代替密码的密钥空间K = = k | 0 k q元素的个 数为 元素的个 数为q, 其中其中k = 0是恒等变换。是恒等变换。 8 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 例例2.3 凯撒密码凯撒密码(Caesar Cipher)是对英文字母表进 行移位代替的密码 是对英文字母表进 行移位代替的密码, 即即q = 26。例如。例如, 选择密钥选择密钥k = 3, 则有 下述代替表 则有 下述代替表: 9 明文明文abcdefghijklm 密文密文DEFGHIJKLMNOP 明文明文nopqrstuvwxyz 密文密文QR STUVWXYZABC 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 若明文若明文 m = casear cipher is a shift substitution 则密文为则密文为 C = = E3(m) = = FDVHDU FLSKHU LV D VKLIW VXEVWLWXWLRQ 10 明文明文abcdefghijklm 密文密文DEFGHIJKLMNOP 明文明文nopqrstuvwxyz 密文密文QR STUVWXYZABC 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 解密时解密时, 只要用密钥只要用密钥k = 23的加密密表对密文的加密密表对密文c进行 加密运算就可恢复出原明文。 进行 加密运算就可恢复出原明文。 11 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 12 这这种密码是将明文字母表中字母位置下标种密码是将明文字母表中字母位置下标与与 密钥密钥 k 进行模进行模 q 加加法运算的结果作为密文字母位法运算的结果作为密文字母位置置 下标下标, 相应的字母即为密文字母相应的字母即为密文字母, 因此又称其为因此又称其为加加 法代替密码法代替密码。 为了加密与解密方便为了加密与解密方便, 可可将英文字母表的所将英文字母表的所有有 移位作为行列出移位作为行列出,该表称作该表称作维吉尼亚密表维吉尼亚密表。见书见书 P17 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 乘法代替密码的加密变换为：乘法代替密码的加密变换为： Ek(m) = = mk c (mod q), 0 c q. 这种密码又叫这种密码又叫采样密码采样密码, 这是因为其密文字母表是将明 文字母表按下标每隔 这是因为其密文字母表是将明 文字母表按下标每隔k位取出一个字母排列而成位取出一个字母排列而成 (字母表 首尾相接 字母表 首尾相接)。 13 乘法代替密码乘法代替密码 当当gcd(k, q) = 1时时, 明文字母与密文字母才是一一对应 的。 明文字母与密文字母才是一一对应 的。 当当gcd(k, q) = 1时时, 明文字母与密文字母才是一一对应 的。 明文字母与密文字母才是一一对应 的。 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 定理定理2.1 在乘法代替密码中在乘法代替密码中, 当且仅当当且仅当 gcd(k,q) = 1, Ek才是一一映射。才是一一映射。 14 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 15 证明证明: 对于任意的对于任意的 j, k, i Zq, jk ik (mod q) (j - i)k 0 (mod q)。 若若 gcd(k, q) = 1, 则必有则必有 j = i, 因而是一一映射。因而是一一映射。 若若 gcd(k, q) = d1, 则则 j = = i + + q/d 也可使也可使 (j i)k 0 (modq), 因而对因而对j i, j和和i将被映射成同一字母将被映射成同一字母, Ek不再不再 是一一的。是一一的。 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 16 由定理由定理 2.1 可知可知, 乘法代替密码实际可用密钥乘法代替密码实际可用密钥 个数为个数为 (q) 1。 若若 1 i r i i qp = = , 其中其中 pi为素数为素数, 则则 1 1 ( )(1) r i i qq p = = 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 17 对于对于 q = 26, 与与 q 互素且小于互素且小于 q 的正整数个数的正整数个数 为为 (26) = 12, 除去除去 k =1 的恒等变换的恒等变换, 还有还有 11 种选种选 择择, 即即 k = 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 和和 25。 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 18 若若q为素数为素数, 则有则有q 2个可用密钥。否则就只有 个可用密钥。否则就只有 (q) 1个可用密钥。这里个可用密钥。这里(q)是欧拉函数是欧拉函数, 它表示小 于 它表示小 于q且与且与q互素的正整数的个数。互素的正整数的个数。 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 例例2.2 英文字母表英文字母表q = 26, 选选k = 9, 则有乘法代替密 码的明文密文字母对应表 则有乘法代替密 码的明文密文字母对应表: 19 明文明文abcdefghijklm 密文密文AJSBKTCLUDMVE 明文明文nopqrstuvwxyz 密文密文NW FOXGPYHQZIR 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 若明文若明文 m = multiplicative cipher 则有密文则有密文 c = EYVPUFVUSAPUHK SUFLKX 20 明文明文abcdefghijklm 密文密文AJSBKTCLUDMVE 明文明文nopqrstuvwxyz 密文密文NW FOXGPYHQZIR 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 21 设设gcd (k, q) = 1, 则以则以k为加密密钥的乘法代 替密码的解密变换是以 为加密密钥的乘法代 替密码的解密变换是以k modq的逆的逆k 1为加密密钥的 乘法代替密码 为加密密钥的 乘法代替密码, 即即 Dk(c)= = k 1c m (mod q) 0 c q 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 例如例例如例2.4中乘法代替密码的解密变换为中乘法代替密码的解密变换为 D3(c)= = 3c m (mod 26) 故解密密表为故解密密表为 22 明文明文abcdefghijklm 密文密文ADGJMPSVYBEHK 明文明文nopqrstuvwxyz 密文密文NQ T WZCFILORUX 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 问题： 在 问题： 在(k, q) = 1时，如何求时，如何求k模模q的逆？的逆？ ?初等数论中欧几里德扩展算法初等数论中欧几里德扩展算法 ?辗转相除法辗转相除法 23 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 因为因为gcd(k1,q) = = 1, 所以存在所以存在k1 1 Zq,使得使得 k1 k1 1 1 (mod q), 故仿射代替密码的解密变换为故仿射代替密码的解密变换为 Dk(c) = = (c k0) k1 1(mod q) 24 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 例例2.5 k1= = 5, k0= = 3 的仿射代替密码的代替表为的仿射代替密码的代替表为: 25 明文明文abcdefghijklm 密文密文DINSXCHM R WBGL 明文明文nopqrstuvwxyz 密文密文QV AFKPUZEJOTY 若明文若明文m为为affine cipher, 则密文则密文c为为 DCCRQX NRAMXK 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 可以通过下述方法对例可以通过下述方法对例2.1 的加法代替密码进行改 造 的加法代替密码进行改 造, 得到一种密钥可灵活变化的密码。 选一个英文短语 得到一种密钥可灵活变化的密码。 选一个英文短语, 称其为称其为密钥字密钥字(key word)或或密钥 短语 密钥 短语(key phrase)，如，如HAPPY NEWYEAR, 按顺序去 掉重复字母得 按顺序去 掉重复字母得HAPYNEWR。 26 密钥短语密码密钥短语密码 第二章第二章第二章第二章 古典密码学古典密码学古典密码学古典密码学 将它依次写在明文字母表之下将它依次写在明文字母表之下, 而后再将明文字 母表中未在短语中出现过的字母依次写在此短语之 后 而后再将明文字 母表中未在短语中出现过的字母依次写在此短语之 后, 就可构造出一个代替表就可构造出一个代替表, 如下所示如下所示: 27 明文明文abcdefghijklm 密文密文HAPYNEWRBCDFG 明文明文nopqr