第12讲 古典密码的加密与破译 之数学原理.

Slides:



Advertisements
Similar presentations
1 、谁能说说什么是因数? 在整数范围内( 0 除外),如果甲数 能被乙数整除,我们就说甲数是乙数的 倍数,乙数是甲数的因数。 如: 12÷4=3 4 就是 12 的因数 2 、回顾一下,我们认识的自然数可以分 成几类? 3 、其实自然数还有一种新的分类方法, 你知道吗?这就是我们今天这节课的学.
Advertisements

因数与倍数 2 、 5 的倍数的特征
3 的倍数特征 抢三十
质数和合数 2 的因数( ) 6 的因数( ) 10 的因数 ( ) 12 的因数 ( ) 14 的因数 ( ) 11 的因数 ( ) 4 的因数( ) 9 的因数( ) 8 的因数( ) 7 的因数( ) 1 、 2 、 3 、 4 、 6 、 12 1 、 11 1 、 2 、 5 、 10.
3 的倍数的特征 的倍数有 : 。 5 的倍数有 : 。 既是 2 的倍数又是 5 的倍数有 : 。 12 , 18 , 20 , 48 , 60 , 72 , , 25 , 60 ,
因数与倍数 2 、 5 的倍数的特征 绿色圃中小学教育网 扶余市蔡家沟镇中心小学 雷可心.
2 和 5 的倍数的特征 运动热身 怎样找一个数的倍数? 从小到大写出 2 的倍数( 10 个): 写出 5 的倍数( 6 个) 2 , 4 , 6 , 8 , 10 , 12 , 14 , 16 , 18 , 20 5 , 10 , 15 , 20 , 25 , 30.
2.8 函数的微分 1 微分的定义 2 微分的几何意义 3 微分公式与微分运算法则 4 微分在近似计算中的应用.
2.6 隐函数微分法 第二章 第二章 二、高阶导数 一、隐式定义的函数 三、可微函数的有理幂. 一、隐函数的导数 若由方程 可确定 y 是 x 的函数, 由 表示的函数, 称为显函数. 例如, 可确定显函数 可确定 y 是 x 的函数, 但此隐函数不能显化. 函数为隐函数. 则称此 隐函数求导方法.
2.5 函数的微分 一、问题的提出 二、微分的定义 三、可微的条件 四、微分的几何意义 五、微分的求法 六、小结.
第二章 导数与微分. 二、 微分的几何意义 三、微分在近似计算中的应用 一、 微分的定义 2.3 微 分.
2 、 5 的倍数的特征 玉田百姓. 1 、在 2 、 3 、 5 、 8 、 10 、 12 、 25 、 40 这几个数中, 40 的因数有几个? 5 的倍数有几个? 复习: 2 、在 6 、 10 、 12 、 15 、 18 、 20 这几个数中,哪些数 是 2 的倍数?哪些数是 5 的倍数?
冀教版四年级数学上册 本节课我们主要来学习 2 、 3 、 5 的倍数特征,同学们要注意观察 和总结规律,掌握 2 、 3 、 5 的倍 数分别有什么特点,并且能够按 要求找出符合条件的数。
2 , 5 的倍数的特征. 我们可以先写出几个 5 的 倍数来看看。 对,先研究小范围的数, 再进行推广验证。
练一练: 在数轴上画出表示下列各数的点, 并指出这些点相互间的关系: -6 , 6 , -3 , 3 , -1.5, 1.5.
2 、 5 的倍数特征 集合 2 的倍数(要求) 在百数表上依次将 2 的倍数找出 并用红色的彩笔涂上颜色。
圆的一般方程 (x-a)2 +(y-b)2=r2 x2+y2+Dx+Ey+F=0 Ax2+Bxy+Cy2+Dx+Ey+ F=0.
第五章 二次型. 第五章 二次型 知识点1---二次型及其矩阵表示 二次型的基本概念 1. 线性变换与合同矩阵 2.
第三章 函数逼近 — 最佳平方逼近.
10.2 立方根.
小学生游戏.
例题 教学目的: 微积分基本公式 教学重点: 牛顿----莱布尼兹公式 教学难点: 变上限积分的性质与应用.
第5章 定积分及其应用 基本要求 5.1 定积分的概念与性质 5.2 微积分基本公式 5.3 定积分的换元积分法与分部积分法
第二章 导数与微分 第二节 函数的微分法 一、导数的四则运算 二、复合函数的微分法.
2-7、函数的微分 教学要求 教学要点.
C++中的声音处理 在传统Turbo C环境中,如果想用C语言控制电脑发声,可以用Sound函数。在VC6.6环境中如果想控制电脑发声则采用Beep函数。原型为: Beep(频率,持续时间) , 单位毫秒 暂停程序执行使用Sleep函数 Sleep(持续时间), 单位毫秒 引用这两个函数时,必须包含头文件
在PHP和MYSQL中实现完美的中文显示
网络与系统安全实验 一 传统加密技术 古典密码技术.
§3.7 热力学基本方程及麦克斯韦关系式 热力学状态函数 H, A, G 组合辅助函数 U, H → 能量计算
第二章 矩阵(matrix) 第8次课.
元素替换法 ——行列式按行(列)展开(推论)
!!! 请记住:矩阵是否等价只须看矩阵的秩是否相同。
计算机数学基础 主讲老师: 邓辉文.
§2 求导法则 2.1 求导数的四则运算法则 下面分三部分加以证明, 并同时给出相应的推论和例题 .
绿色圃中小学教育网 比例 比例的意义 绿色圃中小学教育网
实验六 古典密码与破译.
第一章 函数与极限.
第二章 经典密码学 加密通信的模型 Oscar x x y Alice 加密机 解密机 Bob k 安全信道 密钥源.
计算机安全与保密 古典密码 张 旻 杭 州 电 子 科 技 大 学.
数列.
线性代数 第二章 矩阵 §1 矩阵的定义 定义:m×n个数排成的数表 3) 零矩阵: 4) n阶方阵:An=[aij]n×n
概 率 统 计 主讲教师 叶宏 山东大学数学院.
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
复习.
1.2 有理数 第1课时 有理数 伏家营中学 付宝华.
第16讲 相似矩阵与方阵的对角化 主要内容: 1.相似矩阵 2. 方阵的对角化.
§8.3 不变因子 一、行列式因子 二、不变因子.
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
3.1.2 空间向量的数量积运算 1.了解空间向量夹角的概念及表示方法. 2.掌握空间向量数量积的计算方法及应用.
1.设A和B是集合,证明:A=B当且仅当A∩B=A∪B
第一节 不定积分的概念与性质 一、原函数与不定积分的概念 二、不定积分的几何意义 三、基本积分表 四、不定积分的性质 五、小结 思考题.
第三章 函数的微分学 第二节 导数的四则运算法则 一、导数的四则运算 二、偏导数的求法.
4) 若A可逆,则 也可逆, 证明: 所以.
第4课时 绝对值.
学习任务三 偏导数 结合一元函数的导数学习二元函数的偏导数是非常有用的. 要求了解二元函数的偏导数的定义, 掌握二元函数偏导数的计算.
2、5的倍数的特征 马郎小学 陈伟.
2.2矩阵的代数运算.
分数再认识三 真假带分数的练习课.
第15讲 特征值与特征向量的性质 主要内容:特征值与特征向量的性质.
第二节 函数的极限 一、函数极限的定义 二、函数极限的性质 三、小结 思考题.
§2 方阵的特征值与特征向量.
定义5 把矩阵 A 的行换成同序数的列得到的矩阵,
第四节 向量的乘积 一、两向量的数量积 二、两向量的向量积.
第三章 从概率分布函数的抽样 (Sampling from Probability Distribution Functions)
找 因 数.
第三节 数量积 向量积 混合积 一、向量的数量积 二、向量的向量积 三、向量的混合积 四、小结 思考题.
第十七讲 密码执行(1).
§4.5 最大公因式的矩阵求法( Ⅱ ).
一元一次方程的解法(-).
§2 自由代数 定义19.7:设X是集合,G是一个T-代数,为X到G的函数,若对每个T-代数A和X到A的函数,都存在唯一的G到A的同态映射,使得=,则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变, 变 变, 也变 对给定的 和A,是唯一的.
Presentation transcript:

第12讲 古典密码的加密与破译 之数学原理

教学目标 1、了解古典密码的历史和发展 2、了解凯撒密码的数学原理 3、掌握模运算,理解模逆的概念 4、掌握Hill密码的数学原理,理解公钥、模逆矩阵的概念,会用Hill密码进行加密和破译 5、了解现代密码的数学原理,了解公开密钥的概念和作用。 2017/9/12 广东科学技术职业学院

密码和解密模型 问题 1.甲方收到与之秘密通信往来的乙方的一个密文信息,密 文内容为: WKVACPEAOCIXGWIZUROQWABALOHDKCEAFCLWW CVLEMIMCC 按照甲方与乙方的约定,他们之间的密文通信采用Hill2密 码,密钥为二阶矩阵 且汉语拼音(或英文字母)的 26个字母与0 ~25之间的整数建立一一对应关系,称之为 字母的表值,具体表值见下表,问这段密文的原文是什么? A B C D E F G H I J K L M 1 2 3 4 5 6 7 8 9 10 11 12 13 N O P Q R S T U V W X Y Z 14 15 16 17 18 19 20 21 22 23 24 25 表1 2017/9/12 广东科学技术职业学院

MOFAXJEABAUCRSXJLUYHQATCZHWBCSCP 经分析这段密文是用Hill2密码编译的,且其中的字母U 问题 2.甲方截获了一段密文 MOFAXJEABAUCRSXJLUYHQATCZHWBCSCP 经分析这段密文是用Hill2密码编译的,且其中的字母U CRS依次代表字母TACO,问能否破译这段密文的内容? 2017/9/12 广东科学技术职业学院

问题背景和实验目的 保密通讯无论在军事、政治、经济还是日常生活中都起着非常重要的作用。 为了将信息传递给己方的接受者,同时又要防止他人(特别是敌人)知道信息的内容,必须将要传递的信息(明文)加密,变成密文后发送出去,这样,即使敌方得到密文也看不懂,而己方的接受者收到密文后却可以按照预先定好的方法加以解密。

问题背景和实验目的 密码可分为古典密码和现代密码 古典密码:以字符为基本加密单元; 现代密码:以信息块为基本加密单元。 本实验主要介绍古典密码的加密与破译原理,同时介绍如何用 Matlab 编程来实现加密、解密和破译过程。

加密信息传递过程 加密器 发送方 明文(信息) 密文 普通信道 发送 敌方截获 破译 解密器 明文(信息) 密文 接收方

密码的起源 密码学的历史大致可以推早到两千年前, 相传名将凯撒为了防止敌方截获情报, 用密码传送情报。 凯撒的做法很简单,就是对二十几个罗马字母建立一张对应表 这种密码我们往往称之为代替密码或置换密码

这样,如果不知道密码本,即使截获一段信息也看不懂 比如收到一个的消息是 EBKTBP,那么在敌人看来是毫无意义的字,通过密码本解破出来就是 CAESAR 一词,即凯撒的名字。 近年来一些谍报题材的电视剧中,比如用菜价(一组数字)传递信息,这些数字对应某本书的页码和字的次序。 金庸先生在他的《连城诀》中就使用了这种密码。

密码的发展与应用 对于这种密码的破译,只要多截获一些情报,统计一下字母的频率,就可以解破出这种密码。 柯蓝道尔在他的“福尔摩斯探案集”中“跳舞的小人”的故事里已经介绍了这种小技巧。

在第二次世界大战中,日本军方的密码设计就很成问题。美军破获了日本很多密码。 在中途岛海战前,美军截获的日军密电经常出现 AF 这样一个地名,应该是太平洋的某个岛屿,但是美军无从知道是哪个。 于是美军就逐个发表自己控制的每个岛屿上的假新闻。当美军发出“中途岛供水系统坏了”这条假新闻后,从截获的日军情报中又看到 AF 供水出来问题的电文,美军就断定中途岛就是 AF。 事实证明判断正确,美军在那里成功地伏击了日本主力舰队。

总的来说,日本在二战中情报经常被美国人破译,以致他们的海军名将山本五十六也因此丧命。我们常说落后就要挨打,其实不会使用数学也是要挨打的。 已故的美国情报专家雅德利二战曾在重庆帮助国民党破解日本的密码。雅德利在回国后写了本书《中国黑室》,从书中的历史可以了解到,日本和重庆间谍约定的密码本就是美国著名作家赛珍珠获得1938年诺贝尔奖的《大地》一书。密码所在的页数就是一个非常简单的公式:发报日期的月数加上天数再加上10.比如3月11号发报,密码就在3+11+10=24页。 总的来说,日本在二战中情报经常被美国人破译,以致他们的海军名将山本五十六也因此丧命。我们常说落后就要挨打,其实不会使用数学也是要挨打的。 2017/9/12 广东科学技术职业学院

好的密码必须做到不能根据已知的明文和密文的对应推断出新的密文的内容。从数学的角度上讲,加密过程可以看作是一个函数的运算F,解密的过程是反函数的运算。明码是自变量,密码是函数值。好的(加密)函数不应该通过几个自变量和函数值就能得到函数。 2017/9/12 广东科学技术职业学院

在很长时间里,人们试图找到一些好的编码方法使得解密者无法从密码中统计出明码的统计信息,但是基本上靠经验。 有经验的编码者会把常用的词对应成多个密码,使得破译者很难统计出任何规律。 比如如果将汉语中的“是”一词对应于唯一一个编码 0543,那么破译者就会发现 0543 出现的特别多。 但如果将它对应成十个密码 0543,3737,2947 等等,每次随机的挑一个使用,每个密码出现的次数就不会太多,而且破译者也无从知道这些密码其实对应一个字。

事实上在二战中,很多顶尖的科学家包括提出信息论的香农都在为美军情报部门工作, 而信息论实际上就是情报学的直接产物。 香农提出信息论后, 为密码学的发展带来了新气象。 根据信息论,密码的最高境界是使得敌人在截获密码后,对我方的所知没有任何增加,用信息论的专业术语讲,就是信息量没有增加。

一般来讲,当密码之间分布均匀并且统计独立时,提供的信息最少。均匀分布使得敌人无从统计,而统计独立能保证敌人即使看到一段密码和明码后,不能破译另一段密码。 这也是电视剧《暗算》 里传统的破译员老陈破译的一份密报后, 但无法推广的原因,而数学家黄依依预见到了这个结果,因为她知道敌人新的密码系统编出的密文是统计独立的。 有了信息论后,密码的设计就有了理论基础,现在通用的公开密钥的方法,包括电视剧《暗算》里的“光复一号”密码,应该就是基于这个理论。

公开密钥体制的提出就是为了从根本上解决上述问题 。其基本思想是:把密钥划分为公开密钥和秘密密钥两部分 ,两者互为逆变换,但几乎不可能从公开密钥推出秘密密钥 .每个使用者均有自己的公开及秘密密钥。 虽然只要能解密的密文,从理论上讲都是可破译的,但如果破译所需要的工作量过大,要求花费的时间过长,以致超过了保密期限,则该密码系统应当被认为是安全可靠的。 就是靠这样的数学原理,保证了二战后的密码几乎无法被破解。冷战时期美苏双方都投入了前所未有的精力去获得对方的情报,但是没有发生过大的因为密码被破而泄密的事件。 2017/9/12 广东科学技术职业学院

Hill密码的数学原理 希尔(Hill)密码 前面提到过代替密码的一个致命弱点 是明文字符和密文字符有相同的使用频率,破译者可从统计出来的字符频率中找到规律,进而找出破译的突破口。要克服这一缺陷,提高保密程度就必须改变字符间的一一对应。 1929年,希尔利用线性代数中的矩阵运算,打破了字符间的对应关系,设计了一种被称为希尔密码的代数密码。 2017/9/12 广东科学技术职业学院

Hill密码加密算法的思想是将l各明文字母通过线性变换转换为l个密文字母,解密只要做一次逆变换就可以了,密钥就是变换矩阵本身,即一般取n=26。 其中 或写成 其中 解密 2017/9/12 广东科学技术职业学院

模运算 设n是正整数,a是整数,如果用n去除a,得商为q,余数为r,则可以表示为: a=qn+r,0≤r<n, 用a mod n表示余数r,则r≡a mod n. 例如:令a=17, n=5,则17=3×5 +2, r =2≡17mod5 在MATLAB软件中,求余(模)运算命令式mod和rem,当x和y异号时,mod(x,y) 求余数,结果与 y 同号,rem(x,y) 求余数,则与 x 同号,当x,y同号时,两者结果是一样的

模运算典型实例 时钟模12的运算

同余 设n是正整数,a, b是整数,如果a mod n≡b mod n,则称整数a和b模n同余,记为a≡b mod n。 显然,a≡b mod n,则n|(a-b). 例如:a=17, b=-8, n=5, 因为17=3×5 +2, -8 =-2×5 +2, 则17 mod 5≡-8 mod 5,通常记为:17≡-8 mod 5.

同余式实例 Q: 下面哪个是真的? 3  3 (mod 17) 3  -3 (mod 17) 172  177 (mod 5)

同余式实例 A: 3  3 (mod 17) True. (3-3 = 0, divisible by all) 3  -3 (mod 17) False. (3-(-3)) = 6 不能整除 17. 172  177 (mod 5) True. 172-177 = -5 能整除 5 -13  13 (mod 26) True: -13-13 = -26 能整除by 26.

同余的基本性质 ① [(a mod n)+(b mod n)]mod n=(a+b)mod n

同余的基本性质 例 1 mod 8=3; 15 mod 8=7 ① [(11mod 8)+(15 mod 8)]mod 8=(3+7)mod 8 =2 =(11+15) mod 8=26 mod 8=2 ② [(11 mod 8)×(15 mod 8)]mod 8 =(3×7)mod 8 =21 mod 8=5 (11×15)mod 8=165 mod 8=5

同余性质 1. 若ab(mod m), cd(mod m), 则: ① ax+cy  bx+dy(mod m), 其中x和y为任给整数. ② ac  bd(mod m). ③ an  bn(mod m), 其中 n>0. 上面的性质容易证明,以②为例: 设a=b+q1m,c=d+q2m ac=( b+q1m)( d+q2m)=bd+(bq2+dq1+q1q2)m, 等式两边同时模m可证。

同余性质 2. 设m是一个正整数, ① ad≡bd(mod m), 如果(d, m)=1, 则a≡b(mod m) ② a≡b(mod m), k>0, 则ak≡bk(mod mk) ③ a≡b(mod m), 如果d是m的因子,则a≡ b(mod d) 下面对①③进行证明。

同余性质 ① 证明:若ad≡bd(mod m), 则m|(ad-bd), 即m|d(a-b). 因(d, m)=1,故m|(a-b), 即a=b(mod m) ③ 证明:d是m的因子,故存在m’, 使得m=dm’. 因为a≡b(mod m), 存在k, 使得a=b+mk= b+ dm’k. 等式两边模d, 可得a≡b(mod d).

同余的一个应用--最大公因数 设a, b是整数,则a, b的所有公因数中最大的一个公因数叫做最大公因数,通常记为gcd(a,b)。 思考:用何种算法求最大公约数? 如果两个整数的绝对值都比较小,求它们的最大公因数是比较容易的。如果两个数都比较大,可以用欧几里德算法,也称辗转相除法。

一个关于同余的性质 对任何非负整数a和非负整数b,设a≥b, a=bq+r, 0≤r<|b|, 则gcd(a, b )=gcd(b, r). 证明:设gcd(a, b)=d, 则d|a, d|b, 则d|a-bq即d|r. 同理,设gcd(b, r)=k, 则k|b, k|r, 则k|bq+r, 即k|a. 所以,结论成立。 例如,96=28×3+12,故gcd(96,28)=gcd(28,12)=4. 又如,88=11×8+0,故gcd(88,11)=gcd(11,0)=11.

辗转相除法 设 a, b>0, 且都为整数,进行下列计算: a=bq1+r1, 0<rl<b b=r1q2+r2, 0<r2<r1 r1=r2q3+r3, 0<r3<r2 ……. rn-2=rn-1qn+rn, 0<rn<rn-1 rn-1=rnqn+1+0 则a,b的最大公因数为rn. 因为gcd(a,b)= gcd(b,r1)= gcd(r1,r2)=… =gcd(rn-1, rn)=gcd(rn,0)= rn.

辗转相除法 举例 例 求gcd(184, 136)。 184=1×136+48, gcd(184,136)= gcd(136,48)

辗转相除的伪代码 欧几里得算法 function gcd(a, b) a>b while b ≠ 0 t := b ; b := a mod b ; a := t; return a ; 思考: 如何用程序实现辗转相除法?

逆元(倒数) a 模m,在什么情况下一定存在乘法逆元呢? 对于正整数m,记集合 设m是正整数,a是整数,如果存在 , 使得a×b ≡1(modm)成立,则a叫模m的可逆元,b叫a模m的模逆元(模倒数), b通常记为a-1。 例如,设m为11,则8模11的逆元为7,因为8×7≡1(mod11),即8-1(mod 11)=7 例如: 2-1 mod 5 =3 2-1mod 26=? a 模m,在什么情况下一定存在乘法逆元呢?

乘法逆实例 当a和m互素的情况下,即(a,m)=1,则a的模m的逆元总是存在的。 60-1 mod 89=? 用何种算法求乘法逆元?

由定理,0—26中除13以外的奇数均可取作这里的a,下表为计算求得的逆元素 定理:若 ,则a必是关于模m可逆的。 由定理,0—26中除13以外的奇数均可取作这里的a,下表为计算求得的逆元素 1 3 5 7 9 11 15 17 19 21 23 25 1 9 21 15 3 19 7 23 11 5 17 25 作业:完成实验1-3题 2017/9/12 广东科学技术职业学院

我们回过头来,Hill密码加密算法的思想是将l各明文字母通过线性变换转换为l个密文字母,解密只要做一次逆变换就可以了,密钥就是变换矩阵本身,即一般取n=26。 其中 或写成 其中 解密 2017/9/12 广东科学技术职业学院

在具体实施时 ,我们很快会发现一些困难: (1) 为了使数字与字符间可以互换,必须使用取自0—25之间的整数 在具体实施时 ,我们很快会发现一些困难: (1) 为了使数字与字符间可以互换,必须使用取自0—25之间的整数 (2)由线性代数知识 ,其中 为A的伴随矩阵。由于使用了除法,在求A的逆矩阵时可能会出现分数。不解决这些困难,上述想法仍然无法实现。解决的办法是引进同余运算,并用乘法来代替除法,(如同线性代数中用逆矩阵代替矩阵除法一样)。 2017/9/12 广东科学技术职业学院

当l=2时,就得到Hill2密码。其具体过程为: 步骤1:根据明文字母的表值,将明文信息用数字表示,设明文信息只需要26个字母A~Z(也可以多于26个),通信双方给出的字母表值见表1. 步骤2:选择一个二阶可逆整矩阵K,称为密码Hill2的加密矩阵,它是这个密码体制的密钥(是加密的关键,仅通信双方知道)。 步骤3:将明文字母依次两两分组,如最后一组只有一个字母,则补充一个没有实际意义的哑字母,使每一组都由两个明字母组成。查出每个明字母的表值,构成一个2维列向量a。 步骤4:计算b=Ka,由b的两个分量反查字母表值得到的两个字母就是密文。 解密过程就是上述过程的逆过程。 2017/9/12 广东科学技术职业学院

例 使用Hill2密码加密明文good bye。取 例 补充哑字母e,将明文分成:go,od,by,ee;对应的向量为 经计算得: 因此密文为:qknyexmc 2017/9/12 广东科学技术职业学院

Hill2 加密过程 分组 明文字母 一组向量 查表值 加密矩阵 左乘 模运算 密文 一组新的向量 反查表值 问题:怎样解密?

Hill2 解密过程 解密:加密的逆过程,将加密过程逆转回去即可。 例2:怎么得到密文 “qknyexmc ” 的明文? 上面的向量是由 经过模 26 运算得来的,现在的问题是怎样逆转回去? 在模运算下解方程组: A = 

模逆矩阵 对于正整数m,记集合 定义:对于一个元素属于集合Zm的n阶方阵A,如果存在 一个元素属于Zm的n阶方阵B ,使得 称A为模m可逆,B为A的模m逆矩阵,记为 定理:若 ,则矩阵A必是关于模m 可逆的。 2017/9/12 广东科学技术职业学院

Hill2 解密过程 ? 在模运算下解方程组: A =  问题:如何计算 ?

模 m 逆矩阵的计算 A*为 A 的伴随矩阵 设 B=k A*为 A 的 模 26 逆,其中 k 为待定系数 本计算方法可推广到求矩阵 A 的 模 m 逆矩阵

Hill2 解密过程 设加密矩阵 练习: 的模逆矩阵?例2该如何解密?(实验)

Hill2 加密过程总结 ① 通讯双方确定加密矩阵 ( 密钥) 和字母的表值对应表 ② 将明文字母分组,通过查表列出每组字母对应的向量 若明文只含奇数个字母,则补充一个哑元 ③ 令  = A mod(m) ,由  的分量反查字母表值表, 得到相应的密文字母

Hill2 解密过程总结 ① 将密文字母分组,通过查表列出每组字母对应的向量 ② 求出加密矩阵 A 的 模 m 逆矩阵 B ③ 令  = B mod(m) ,由  的分量反查字母表值表, 得到相应的明文字母

Hill2 解密举例 甲方收到乙方(己方)的一个密文信息,内容为: WKVACPEAOCIXGWIZUROQWABALOHDKCEAFCLWWCVLEMIMCC 按照甲方与乙方的约定,他们之间采用 Hill2密码,密钥 为 ,字母表值见下表,问这段密文的原文 是什么? A B C D E F G H I J K L M 1 2 3 4 5 6 7 8 9 10 11 12 13 N O P Q R S T U V W X Y Z 14 15 16 17 18 19 20 21 22 23 24 25

Hill2 解密举例 ① 将密文字母分组,通过查表列出每组字母对应的向量 ② 求出加密矩阵 A 的 模 26 逆矩阵 ③ 用 B 左乘每组密文字母组成的向量,然后再反查字母表值表,得到相应的明文字母

Hill2 解密举例 序号 分组 密文 表值 明文 1 W K 23 11 7 21 G U 2 V A 22 4 9 D I 3 C P 16 14 N E 5 13 M O 15 6 X 24 19 8 S H 序号 分组 密文 表值 明文 7 G W 23 9 25 I Y 8 Z U R 21 18 6 F 10 O Q 15 17 11 A 1 5 E 12 B 2 J

Hill2 解密举例 序号 分组 密文 表值 明文 13 L O 12 15 2 5 B E 14 H D 8 4 10 N J K C 11 3 9 1 I A 16 M 17 F 6 18 W 23 25 Y 序号 分组 密文 表值 明文 19 W C 23 3 21 1 U A 20 V L 22 12 14 4 N D E M 5 13 I 9

WKVACPEAOCIXGWIZUROQWABALOHDKCEAFCLWWCVLEMIMCC Hill2 解密举例 WKVACPEAOCIXGWIZUROQWABALOHDKCEAFCLWWCVLEMIMCC 密文 GU DIAN MI MA SHI YI ZI FU WEI JI BEN JIA MI DAN YUAN DE MI MA A 原文 即:“古典密码是以字符为基本加密单元的密码”

Hill2 密码破译举例 MOFAXJEABAUCRSXJLUYHQATCZHWBCSCP 我方截获一段密文 经分析该密文是用 Hill2密码 加密,且密文 ( U, C ) 和 ( R, S ) 分别对应明文 ( T, A ) 和 ( C, O ),问能否破译这段密文? 破译这段密文的关键是找到“密钥”和字母对应的表值 猜测密文是由26个字母组成,即 m=26, 经破译部门通过大量的统计分析和语言分析确定表值 A B C D E F G H I J K L M 1 2 3 4 5 6 7 8 9 10 11 12 13 N O P Q R S T U V W X Y Z 14 15 16 17 18 19 20 21 22 23 24 25

P C Hill2 密码破译举例 密文 ( U, C ) 和 ( R, S ) 分别对应明文 ( T, A ) 和 ( C, O ) 查 字 母 表 值 P C

Hill2 密码破译举例 P、C 模26可逆 可唯一确定加密矩阵 A

Hill2 密码破译举例 得到加密矩阵的 模26逆矩阵 后,根据前面的解密方法即可得密文的原文 HE WI LL VI SI TA CO LL EG E T HI SA FT ER NO ON 相应的 Matlab 程序见附录 4

RSA公开密钥系统简介 公开密钥的原理其实很简单,我们以给上面的单词 Caesar 加解密来说明它的原理。 我们先把它变成一组数,比如它的 Ascii 代码 X=099097101115097114(每三位代表一个字母)做明码。 现在我们来设计一个密码系统,对这个明码加密。

1.找两个很大的素数(质数)P 和 Q,越大越好,比如 100 位长的, 然后计算它们的乘积 N=P×Q,M=(P-1)×(Q-1)。 2,找一个和 M 互素的整数 E,也就是说 M 和 E 除了 1 以外没有公约数。 3,找一个整数 D,使得 E×D 除以 M 余 1,即 E×D mod M = 1。

现在世界上先进的最常用的密码系统就设计好了,其中 E 是公钥谁都可以用来加密,D 是私钥用于解密,一定要自己保存好。乘积 N 是公开的,即使敌人知道了也没关系。 现在,我们用下面的公式对 X 加密,得到密码 Y。

好了,现在没有密钥 D,神仙也无法从 Y 中恢复 X。

这个过程大致可慨括如下: 2017/9/12 广东科学技术职业学院

公开密钥的好处有: 1.简单 2.可靠。公开密钥方法保证产生的密文是统计独立而分布均匀的。也就是说,不论给出多少份明文和对应的密文,也无法根据已知的明文和密文的对应来破译下一份密文。更重要的是 N,E 可以公开给任何人加密用,但是只有掌握密钥 D 的人才可以解密, 即使加密者自己也是无法解密的。这样,即使加密者被抓住叛变了,整套密码系统仍然是安全的。(而凯撒大帝的加密方法有一个知道密码本的人泄密,整个密码系统就公开了。) 3.灵活,可以产生很多的公开密钥E和私钥D 的组合给不同的加密者。

最后让我们看看破解这种密码的难度。首先,要声明,世界上没有永远破不了的密码,关键是它能有多长时间的有效期。 要破公开密钥的加密方式,至今的研究结果表明最好的办法还是对大字N 进行因数分解,即通过 N 反过来找到 P 和 Q,这样密码就被破了。 而找 P 和 Q 目前只有用计算机把所有的数字试一遍这种笨办法。 这实际上是在拼计算机的速度, 这也就是为什么 P 和 Q 都需要非常大。 一种加密方法只有保证 50 年计算机破不了也就可以满意了。

前几年破解的 RSA-158 密码是这样因数分解的 39505874583265144526419767800614481996020776460304936454139376051579355626529450683609727842468219535093544305870490251995655335710209799226484977949442955603 = 3388495837466721394368393204672181522815830368604993048084925840555281177 × 11658823406671259903148376558383270818131012258146392600439520994131344334162924536139