信息加密技术基础.ppt
《信息加密技术基础.ppt》由会员分享,可在线阅读,更多相关《信息加密技术基础.ppt(107页珍藏版)》请在三一办公上搜索。
1、第二章信息加密技术基础,引 言,信息加密是网络安全体系中重要机制之一。信息加密的目的是为了保持信息的机密性,使用恰当的加密标准将在计算机环境中增加安全性。信息加密通过使用一种编码而使存储或传输的信息变为不可读的信息,解密是一个相反的过程。这些编码就是将明文变成密文的加密算法或数学方法。,引 言(续),加密编码在Shannon的信息论中有针对性的阐述,数论及基础代数是加密算法的理论基础。要将一段信息加密或解密,你会要用到密钥,它是一个很大的值。一般来说,密钥越大,加密就越健壮。一般来说加密体制分为对称密钥加密和公用密钥加密,对称密钥加密在密钥方面有一定的缺陷,但执行效率高;公用密钥加密加密执行效
2、率底,但保密性强,在报文和网络方面对小量信息加密非常有效.,2.1 信息加密理论基础,信息安全的核心技术之一是加密技术,它涉及信息论、基础数论和算法复杂性等多方面基础知识。随着计算机网络不断渗透到各个领域,加密技术的应用也随之扩大,应用加密基础理论知识,深入探索可靠可行的加密方法,应用于数字签名、身份鉴别等新技术中成为网络安全研究重要的一个方面。,加密的理论依据,密码学问题就是随机性的利用问题.差不多每台使用加密技术的计算机安全系统都需要随机数,供密钥、协议中的基础参量等使用或者用做辅助信息或者初始化向量。这些系统的安全也经常依赖于这些随机数的随机性及被保护程度。,简单的加密举例,中秋日月 编
3、码 密钥 密文编码 诗 月明明日 010101 10 111111 明日月明 101010 000000?明日明日 101101 000111 日明月明 110010 011000 通过这个例子我们看到一个简单的加密过程,原来的诗通过与密钥的模二运算实现了加密。,信息编码基础知识,第二次世界大战期间,美国为了提高信息储存和传递的效率,发明了多种新的编码方法,奠定了现代信息科学技术的基础。Shannon还于1949年发表了“保密系统的通信理论”一文,奠定了现代密码学基础从而对加密过程中信息编码有了明确的分析。在该文中他从信息论观点,对信息系统的保密性问题作了全面而深刻的阐述。,1.信 息 熵 基
4、 本 知 识,信息论中最重要的内容,是如何认识和使用信息熵来表现信息。这里用Shannon最喜欢用的猜谜方法来说明信息熵的基本概念。假如有:“我们大_都喜_使_计_机来管_数_。”不用很多努力,就可以猜出完整的句子:“我们大家都喜欢使用计算机来管理数据。”Shannon在信息论中指出,能猜出来的字符不运载信息,而不能猜出来的字符运载信息。,1.信 息 熵 基 本 知 识(续),空格所隐藏的字符属于多余度字符,不用那些字符也能运载该句子的全部信息,比如:“我_大_使_机来_数_。”就很难猜出完整的句子,在信息传递的时候,也很难做检错和抗错。因此,保留一定的多余度(或冗余度)是非常重要的。,2.信
5、息量和信息熵基本定义(1),信息熵(information entropy)是对信息状态“无序”与“不确定”的度量(从本质上讲,熵不是对信息的度量,但信息的增加而使产生的熵减小,熵可以用来度量信息的增益)。,2.信息量和信息熵基本定义(2),定义:给定一离散集合X=xi;i=1,2,n,令xi出现的概率是 且。事件xi包含的信息量 通常=2,此时相应的信息量单位是bit。Shannon定义信息的数学期望为信息熵,即信源的平均信息量。,2.信息量和信息熵基本定义(3),定义:将集合X中事件所包含的信息量统计平均,则平均值定义为集合X的熵.信息熵表征了信源整体的统计特征,集合X的熵H(x)表示X中
6、事件所包含的平均信息量,或总体的平均不确定性的量度。,2.信息量和信息熵基本定义(4),对某一特定的信源,其信息熵只有一个,因统计特性不同,其熵也不同。例如,两个信源,其概率空间分别为:,2.信息量和信息熵基本定义(5),则信息熵为:可见,,说明信源 比信源 的平均不确定性要大,即在事件发生之前,分析信源,由于事件 是等概率的,难以猜测哪一个事件会发生.,2.信息量和信息熵基本定义(6),而信源,虽然也存在不确定性,但大致可以知道,出现的可能性要大。正如两场比赛,其中一场,双方势均力敌;而另一场双方实力悬殊很大。当然,人们希望看第一场,因为胜负难卜,一旦赛完,人们获得信息量大。也可以这样理解,
7、信息熵 表征了变量 的随机性。因此,熵反映了变量的随机性,也是表征随机变量统计特性的一个特征参数。,3.信息熵的基本性质(1),对称性 当概率空间中 序任意互换时,熵函数的值不变,例如下面两个信源空间:,3.信息熵的基本性质(2),其信息熵.该性质说明,熵只与随机变量的总体结构有关,与信源总体的统计特性有关,同时也说明所定义的熵有其局限性,它不能描述事件本身的主观意义。,3.信息熵的基本性质(3),确定性 如果信源的输出只有一个状态是必然的,即 则信源的熵:此性质表明,信源的输出虽有不同形态,但其中一种是必然的,意味着其他状态不可能出现。那么,这个信源是一个确知信源,其熵为零。,3.信息熵的基
8、本性质(4),非负性 即。因为随机变量 的所有取值的概率分布为,当取对数的底大于时,,而,则得到的熵是正值,只有当随机变量是一确知量时,熵才等于零。这种非负性对于离散信源的熵来说,这一性质并不存在。,3.信息熵的基本性质(5),可加性 独立信源 和 的联合信源的熵等于它们各自的熵之和。如果有两个随机变量 和,它们彼此是统计独立的,即 的概率分布为,而 的分布概率为,则联合信源的熵:可加性是熵函数的一个重要特性,正因为有可加性,所以可以证明熵函数的形式是唯一的。,3.信息熵的基本性质(6),极值性 信源各个状态为零概率分布时,熵值最大,并且等于信源输出状态数,因为 当 时,(2.5),例 题,例
9、,信源有两种状态时,概率空间 其 与 关系如图所示,,当=1/2时熵有最大值;当信源输出是确定的,即,则,此时表明该信源不提供任何信息;反之,当信源输出为等概率发生时,即 时信源的熵达到最大值,等于1bit信息量。,4.信息熵在信息加密编码中的作用(1),通过熵和信息量的概念,可计算加密系统中各部分的熵。令明文熵为,密钥熵,密文熵。这里M、K和C分别是明文、密钥和密文空间,m、k、c分别是它们的字母集,l,r和v分别是明文、密钥、和密文的长度。则明文和密文之间的互信息以及密钥与密文之间的互信息分别是:,4.信息熵在信息加密编码中的作用(2),因为只要密文、密钥确定后,明文也就得到了,所以,故
10、定理:对任意加密系统 从该理论我们可以看出,密钥熵越大,密文中所包含的明文信息量就越小。一个加密系统中,若其密文与明文之间的互信息,则密码分析者无论截获多大的密文,均不能得到有关明文的任何信息。这种加密系统称为完善加密系统,或无条件加密系统。,4.信息熵在信息加密编码中的作用(3),在对密文攻击下,完善加密系统是安全的,但它不能保证在已知明文或选择性明文攻击下也是安全的。因此,完善保密系统存在的必要条件是 证明:若,则由前一个定理可得,所以 的必要条件是,数论基本术语,数论是研究整数性质的一个数学分支,同时也是加密技术的基础学科之一。首先介绍一些数论的基本知识.,1.整 数,定义:设。如果存在
11、 使得,那么就说b 可以被a 整除,记为,且称b是a的倍数,a 是b的因数(或称约数、除数、因子)。b不能被a整除可以记作dFa。由定义及乘法运算的性质,可推出整除关系具有以下性质(注:符号 本身包含了条件):(1);(2)如果 且,则;(3)设,那么 与 等价;(4)如果 且,则对所有的,有;(5)设,如果,那么;,2.素 数,定义:设整数。如果它除了显然因数 外没有其他的因数,则p就称为是素数,也叫不可约数。若,且a不是素数,则a称为合数。关于素数,有以下性质:(1)如果p是素数,且,则 或,即p至少整除a与b中的一个。(2)任何一个整数,均可以分解成素数幂之积:(3)若不计因数的顺序,这
12、个分解式是唯一的。其中,是两两互不相同的素数,是正整数。(4)素数有无穷多个。(5)设 表示不大于 的素数的数目,则。,3.同 余,设,如果,则称a和b模n同余,记为,整数n称为模数。由 于 等价于,所以 与 等价。因此,一般我们总假定。如果,我们称b是a对模n的最小非负剩余,有时也称b为a对模n的余数。,同余式的一些基本性质,(1)反身性:;(2)对称性:如果,那么;(3)传递性:如果,,那么;(4)如果,那么;。(5)如果,gcd,(两个不同时为0的整数a与b的最大公约数表示成gcd(a,b)那么,存在,当且仅当gcd。,一些关于同余的基本概念(1),同余类 可用其中任一元素a(经常取)代
13、替,记作。于是 从 中分别取一个数作为代表构成一个集合,称为模n的一个完全剩余系,记为,称为模n的非负最小完全剩余系。,一些关于同余的基本概念(2),在模n的完全剩余系中,去掉那些与n不互素的数,剩下的部分称为模n的简化剩余系;的简化剩余系记为,读为模n的非负最小简化剩余系。显然,中的元便是不超过n并与n互素的那些数,它们的个数等于欧拉函数 的值。(欧拉函数的定义为:小于自然数N并与N互质(除1以外无其它公因子)的自然数的个数用函数 表示,称为欧拉函数。欧拉函数的具体性质会在后面第6小节进行阐述),4.模 运 算,给定正整数n,对任意a,若存在q,使得 则称r是a关于模n的余数,记为。若 则称
14、整数a,b同余,记为 整数集中所有与数a同余的整数集合称为a的同余类,记为。,模 运 算 的 性 质,(1)当且仅当。(2)当且仅当。(3)如果,则。a模n的运算给出了a对模n的余数。注意:模运算的结果是从0到 的一个整数。模运算就像普通的运算一样,它是可交换,可结合,可分配的。而且,对每一个中间结果进行模m运算,其作用与先进行全部运算,然后再进行模m运算所得到结果是一样的。,5.最大公约数与最小公倍数,设,是两个整数,如果 且,那么就称b是 和 的公约数.一般的,设,是K个整数,如果 那么就称b是 的公约数。因为对于任意一个不等于零的整数,它的因数是有限的。所以,任意一对整数,其中一个不为零
15、时,它们的公约数的个数也必定是有限的;同理,当 中有一个不为零时,它们的公约数是有限的.这样,我们引入最大公约数的概念。定义:设,是两个整数,我们把 和 的公约数中最大的数称为 和 的最大公约数,记为(,)或 当 时,我们称 和 是互素的。显然,最 大 公 约 数 的 性 质,(1)(2)若|,j=2,k,则(3)任意的整数x,有(4)对任意的整数x,有(5)设,是不都为零的整数,则一定存在一对整数,,使得:,最 小 公 倍 数 的 概 念,设,是两个均不等于零的整数,如果 且,那么 1 就称为是 和 的公倍数,一般地,设 是k个均不等于零的整数。如果,则称 l是 的公倍数。公倍数的集合是无穷
16、集合,但根据自然数的理论,存在最小的正的公倍数。我们把 和 的正的公倍数中最小的数称为 和 的最小公倍数,记为 或,6.欧拉(Euler)函数,欧拉(Euler)函数 设n1,欧拉函数 表示在区间 中与n互素的整数的个数。欧拉函数 具有以下性质:(1)如果p是素数,则;(2)如果p是素数,。那么;(3)对于整数,根据算术基本定理,n可以分解成惟一的形如 的分解式,则(4)若 和 互素,则。,算法复杂性基础知识,所谓问题,是指一个要求给出解释的一般性提问,通常含有若干个未定参数或自由变量。它由两个要素组成,第一个要素是描述所有的参数,也就是对所有未定参数的一般性描述;第二个要素是解答必须满足的性
17、质。一个问题 可以看成是由无穷多个问题实例组成的一个类。,1.算 法 的 定 义,所谓算法是由明确指出操作的规则所组成的若干语句的集合,只要按照规则一步一步执行一定数目的语句,便可求出问题的答案。通常的计算机程序都可以看作是算法的表达形式,在问题的两要素中,对算法而言,第一个要素就是“输入”,第二个要素就是“输出”。如果把问题P的任意一个实例作为算法A的输入,A在有限步骤之内总能输出关于此实例的正确答案,我们就说算法A可解问题P。对于一个问题P,如果存在一个算法A可解问题P,我们称问题P是算法可解的。,2.算 法 复 杂 性,算法的复杂性表征了算法在实际执行时所需计算能力方面的信息,通常它由该
18、算法所要求的最大时间与存取空间来确定。由于算法所需的时间和空间往往取决于问题实例的规模n(n表示了该实例的输入数据长度),同时,算法在用于相同规模n的不同实例时。其时间和空间需求也可能会有很大差异,因此,实际中我们常常研究的是算法关于输入规模 的所有实例的时间与空间需求的平均值。,算 法 复 杂 性 的 构 成,通常情况下,一个算法的计算复杂性由两个变量度量:时间复杂性 和空间复杂性。它们定义如下:(1)时间复杂性:以某特定的基本步骤为单元,完成计算过程所需的总单元数称为算法的时间复杂性,或时间复杂度。n为输入的规模或尺寸。(2)空间复杂性:以某特定的基本存储空间为单元,完成计算过程所用的存储
19、单元数,称为算法的空间复杂性或空间复杂度。n是输入的规模或尺寸。,算法复杂性的基本符号(1),一个算法的计算复杂性用“O”符号表示其数量级。“O”的意思是:对于两个任意的实值函数f和g,若记号,则存在有一个值a,对充分大的n,有。计算复杂性的数量级就是这种类型的函数,即当n变大时增长得最快的函数,所有常数和较低阶形式的函数可以忽略不计。,算法复杂性的基本符号(2),另一个符号是“o”。它的定义是:当且仅当,这意味着在 时,比 可以忽略不计。时间复杂度 有时也用工作因子W表示,这时。如果一个算法的复杂性不依赖于n,那么它是常数级的用 表示之,而 表示复杂性随n线性增长,因而是线性型算法。复杂性随
20、n线性增长的其他一些算法也称为二次方或三次方等,所有这些算法都是多项式的,它们的时间复杂性是。有多项式时间复杂性的算法称为多项式时间算法或有效算法。,3.问 题 的 复 杂 性,问题的复杂性是问题固有的性质。问题的复杂性理论利用算法复杂性作为工具,将大量典型的问题按照求解的代价进行分类。问题的复杂性由在图灵机上解其最难实例所需的最小时间与空间决定,还可以理解为由解该问题的最有效的算法所需的时间与空间来度量。,N P 问 题,在确定型图灵机上可用多项式时间求解的问题,称为易处理的问题。易处理的问题的全体称为确定性多项式时间可解类,记为P类。在非确定性图灵机上可用多项式时间求解的问题,称为非确定性
21、多项式时间可解问题,记为NP问题。NP问题的全体称为非确定性多项式时间可解类,记为NP类。显然,因为在确定型图灵机上多项式时间可解的任何问题在非确定型图灵机上也是多项式时间可解的。,N P C 问 题,NP类中还有一类问题称为NP完全类,记为NPC。所有的NP问题都可以通过多项式时间转换为NPC中的问题。NPC是NP类中困难程度最大的一类问题,但NPC中的问题困难程度相当,都可以多项式时间转化为称为可满足性问题的NPC问题,此类NPC具有如下性质,若其中的任何一个问题属于P,则所有的NP问题都属于P,且。现在的密码算法的安全性都是基于NPC问题的,破译一个密码相当于求解一个NPC问题,如果,则
22、破译密码就是一件很容易的事情.,2.2 信息加密方式与标准,经典的信息加密理论主要用于通信保密,而现代信息加密技术的应用已深入到信息安全的各个环节和对象,信息的加密方式和标准也有了深入广泛的发展,特别是现代加密和信息隐藏技术的结合,实现信息隐蔽传输使人类对信息的加密技术有了新的认识和要求,下面介绍信息加密技术的基本概念、方式和标准。,信息加密基本概念(1),研究安全信息的加密技术和研究破解安全信息密码的密码分析技术的学科称为密码学。信息加密是通过使用一种编码而使某些可读的信息(明文)变为不可读的信息(密文)。这些编码就是将明文变成密文的加密算法(也称为密码)或数学方法。密码使用隐蔽语言、文字、
23、图象的特种符号,目标是接收数据作为输入,产生密文作为输出,以便数据的原始意义得以隐藏。在计算机通讯中,采用密码(密钥为参数)将信息隐蔽起来,再将隐蔽后的信息传输出去,使信息在传输过程中即使被窃取或载获,也不能了解信息的内容,从而保证信息传输的安全。,2.2.1 信息加密基本概念(2),通信两端将信息编码时,发送端使用简单的信息加密;接收端收到传来的信息后通过解密看到编码前的信息,整个过程中加密或解密是由密钥控制实现的。密钥是用户按照一种密码体制随机选取,它通常是一随机字符串,是控制明文变换(加密)和密文变换(解密)的唯一参数。密钥全体称为密钥空间。一般来说,密钥越大,加密就越健壮。,加密系统的
24、组成部分,如上所述,一个加密系统实际上是某种加密算法在密钥控制下实现的从明文到密文的映射,它至少包括下面四个组成部分:(1)加密的报文,也称明文;(2)加密后的报文,也称密文;(3)加密解密设备或算法;(4)加密解密的密钥;一般情况下,密钥由K表示,明文由m表示,加密算法由()表示,解密算法由()表示,;则,(m)=m,加密系统示意图,一个完整的加密系统如下图所示:,加密系统的安全规则(1),任何一个加密系统必须基本具备四个安全规则:(1)机密性(confidentiality):加密系统在信息的传送中提供一个或一系列密钥来把信息通过密码运算译成密文,使信息不会被非预期的人员所读取,只有发送者
25、和接收者应该知晓此信息的内容。,加密系统的安全规则(2),(2)完整性(integrity):数据在传送过程中不应被破坏,收到的信宿数据与信源数据是一致的。应该选取健壮的密码和加密密钥,以确保入侵者无法攻破密钥或找出一个相同的加密算法,阻止入侵者会改变数据后对其重新加密。有时,数据完整性可以通过适当的方法在信息还未被完全修改时检测到,如:密码散列函数是单向密码,它为明文产生惟一的“指纹”,当明文被拦截和读取,要修改它将改变散列,致使有意向的接收者很容易看出散列之间的差异。,加密系统的安全规则(3),(3)认证性(authentication):加密系统应该提供数字签名技术来使接收信息用户验证是
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息 加密 技术 基础
链接地址:https://www.31ppt.com/p-4951187.html