矩阵模运算与古典密码——Hill2加密解密.pptx

第四讲矩阵模运算与古典密码—— Hill2 加密解密 2主要内容 信息加密与古典密码 矩阵运算与Hill2 加密解密 Hill2 密码破译 MATLAB 实现 3 为什么要加密 保密通讯无论在军事、政治、经济还是日常生活中都起着非常重要的作用。 为了将信息传递给己方的接受者，同时又要防止他人（特别是敌人）知道信息的内容，必须将要传递的信息（明文）加密，变成密文后发送出去，这样，即使敌方得到密文也看不懂，而己方的接受者收到密文后却可以按照预先定好的方法加以解密。信息加密 密码分类 古典密码：以字符为基本加密单元 现代密码：以信息块为基本加密单元 4加密信息传递过程明文（信息）加密器密文密文明文（信息）解密器普通信道发送敌方截获破译发送方接收方 矩阵运算与Hill2 密码5 6Hill2 密码的加密过程 Hill2 密码中所用的数学手段是 矩阵运算 加密过程：① 将 26 个字母 与 0 到 25 之间的整数建立一一对应关系，称为字母的 表值，然后根据明文字母的表值，将明文信息用数字表示ABCDEFGHIJKLM12345678910111213NOPQRSTUVWXYZ1415161718192021222324250设通讯双方所给出的 26 个字母的表值如下：注：这里假定明文中只使用 26 个大写字母 7Hill2 密码的加密过程② 选择一个 二阶可逆整数方阵 A，称为Hill2密码的 加密矩阵，它是加密体制的 “密钥”，是加密的关键，仅通讯双方掌握③ 将明文字母分组。 Hill2 使用的是二阶矩阵，所以将明文字母每 2 个一组（可以推广至Hilln密码）。查出每个字母的表值，这样，每组字母构成一个二维列向量 ? 若最后仅剩一个字母，则补充一个没有实际意义的哑字母（哑元），这样使得每组都有 2 个字母④ 令 ? = A? ，由 ? 的两个分量反查字母表值表，得到相应的两个字母，即为密文字母 8Hill2 加密举例例： 设明文为“HDSDSXX”（华东师大数学系），试给出这段明文的 Hill2 密文。其中加密矩阵为 将明文字母分组： HD SD SX XX最后的一个字母 X 为哑字母，无实际意义。解:ABCDEFGHIJKLM12345678910111213NOPQRSTUVWXYZ1415161718192021222324250查表得每组字母的表值，得到 4 个二维列向量： 9将上述 4 个二维向量左乘密钥矩阵 A 得：作模 26 运算，将所有的数都化为 0 到 25 之间的整数：Hill2 加密举例 10反查字母表值得每个向量对应的字母组为：HDSDSXXPLALOTTTHill2 加密Hill2 加密举例ABCDEFGHIJKLM12345678910111213NOPQRSTUVWXYZ1415161718192021222324250PL AL OT TT 11问题：怎样解密？明文字母查表值分组一组向量加密矩阵左乘一组新的向量反查表值密文Hill2 加密过程模运算 Hill2 密码解密12 13先查出密文字母 “ PL AL OT TT ” 所对应的向量：在模运算下解方程组： A? = ? 解密：加密的逆过程，将加密过程逆转回去即可Hill2 解密过程上面的向量是由 经过模 26 运算得来的，现在的问题是怎样逆转回去？例：怎么得到密文 “ PLALOTTT ” 的原文 14模 m 可逆记定义 1：设 A 为定义在集合 Zm 上的 n 阶方阵，若存在一个定义在 Zm 上的方阵 B，使得 则称 A 模 m 可逆， B 为 A 的 模 m 逆矩阵，记为定义 2：设 a ? Zm ，若存在 b ? Zm 使得 ab=1 (mod m) ，则称 b 为 a 的 模 m 倒数 或乘法逆，记作 b = a-1 (mod m) 。注: a , b 都是 Zm 中的数 15命题：定义在集合 Zm 上的 n 阶方阵 A 模 m 可逆的充要条件是：m 和 det(A) 无公共素数因子，即 m 与 det(A) 互素。Hill2 密码的加密矩阵必须满足上述条件。m=26m 的素数因子只有 2 和 13 定义在 Z26上的方阵 A 模 26 可逆的充要条件是：模 m 可逆det(A) 不能被 2 和 13 整除 问题：是否 Zm 中所有的数都存在模 m 倒数？a 存在唯一的模 m 倒数a 与 m 无公共素数因子 16 Z26 中具有模 26 倒数的整数及其模 26 倒数表a1357911151719212325a-11921153197231151725模 26 可逆 思考：如何用 Ma