《[工学]第2章 信息加密技术基础》由会员分享，可在线阅读，更多相关《[工学]第2章 信息加密技术基础（96页珍藏版）》请在金锄头文库上搜索。
1、第二章 信息加密技术基础,引 言,信息加密是网络安全体系中重要机制之一。信息加密的目的是为了保持信息的机密性，使用恰当的加密标准将在计算机环境中增加安全性。信息加密通过使用一种编码而使存储或传输的信息变为不可读的信息，解密是一个相反的过程。这些编码就是将明文变成密文的加密算法或数学方法。,引 言 (续),加密编码在Shannon的信息论中有针对性的阐述，数论及基础代数是加密算法的理论基础。要将一段信息加密或解密，你会要用到密钥，它是一个很大的值。一般来说，密钥越大，加密就越健壮。一般来说加密体制分为对称密钥加密和公用密钥加密，对称密钥加密在密钥方面有一定的缺陷，但执行效率高；公用密钥加密加密执
2、行效率低，但保密性强，在报文和网络方面对小量信息加密非常有效.,2.1 信息加密理论基础,信息安全的核心技术之一是加密技术，它涉及信息论、基础数论和算法复杂性等多方面基础知识。随着计算机网络不断渗透到各个领域，加密技术的应用也随之扩大，应用加密基础理论知识，深入探索可靠可行的加密方法，应用于数字签名、身份鉴别等新技术中成为网络安全研究重要的一个方面。,加密的理论依据,密码学问题就是随机性的利用问题. 差不多每台使用加密技术的计算机安全系统都需要随机数，供密钥、协议中的基础参量等使用或者用做辅助信息或者初始化向量。这些系统的安全也经常依赖于这些随机数的随机性及被保护程度。,2.1.1 信息编码基
3、础知识,第二次世界大战期间，美国为了提高信息储存和传递的效率，发明了多种新的编码方法，奠定了现代信息科学技术的基础。Shannon还于1949年发表了“保密系统的通信理论”一文，奠定了现代密码学基础从而对加密过程中信息编码有了明确的分析。在该文中他从信息论观点，对信息系统的保密性问题作了全面而深刻的阐述。,1. 信 息 熵 基 本 知 识,信息论中最重要的内容，是如何认识和使用信息熵来表现信息。 这里用Shannon最喜欢用的猜谜方法来说明信息熵的基本概念。假如有：“我们大_都喜_使_计_机来管_数_。” 不用很多努力，就可以猜出完整的句子:“我们大家都喜欢使用计算机来管理数据。” Shann
4、on在信息论中指出，能猜出来的字符不运载信息，而不能猜出来的字符运载信息。,1. 信 息 熵 基 本 知 识(续),空格所隐藏的字符属于多余度字符，不用那些字符也能运载该句子的全部信息，比如：“我_大_使_机来_数_。”就很难猜出完整的句子，在信息传递的时候，也很难做检错和抗错。因此，保留一定的多余度(或冗余度)是非常重要的。,2. 信息量和信息熵基本定义(1),信息熵（information entropy）是对信息状态“无序”与“不确定”的度量（从本质上讲，熵不是对信息的度量，但信息的增加而使产生的熵减小，熵可以用来度量信息的增益）。,2. 信息量和信息熵基本定义(2),定义：给定一离散集
5、合X=xi; i=1,2,n，令xi出现的概率是 且 。事件xi包含的信息量 通常=2，此时相应的信息量单位是bit。Shannon定义信息的数学期望为信息熵，即信源的平均信息量。,2. 信息量和信息熵基本定义(3),定义：将集合X中事件所包含的信息量统计平均，则平均值定义为集合X的熵.信息熵表征了信源整体的统计特征，集合X的熵H（x）表示X中事件所包含的平均信息量，或总体的平均不确定性的量度。,2. 信息量和信息熵基本定义(4),对某一特定的信源，其信息熵只有一个，因统计特性不同，其熵也不同。例如，两个信源，其概率空间分别为：,2. 信息量和信息熵基本定义(5),则信息熵为： 可见， ,说明
6、信源 比信源 的平均不确定性要大，即在事件发生之前，分析信源 ，由于事件 是等概率的，难以猜测哪一个事件会发生.,2. 信息量和信息熵基本定义(6),而信源 ，虽然也存在不确定性，但大致可以知道, 出现的可能性要大。正如两场比赛，其中一场，双方势均力敌；而另一场双方实力悬殊很大。当然,人们希望看第一场，因为胜负难卜，一旦赛完，人们获得信息量大。也可以这样理解，信息熵 表征了变量 的随机性。因此，熵反映了变量的随机性，也是表征随机变量统计特性的一个特征参数。,2.1.2 数论基本术语,数论是研究整数性质的一个数学分支，同时也是加密技术的基础学科之一。首先介绍一些数论的基本知识.,1. 整 数,定
7、义：设 。如果存在 使得 ，那么就说b 可以被a 整除，记为 ，且称b是a的倍数,a 是b的因数(或称约数、除数、因子) 。 b不能被a整除可以记作dFa。由定义及乘法运算的性质，可推出整除关系具有以下性质（注：符号 本身包含了条件 ）： （1） ； （2）如果 且 ，则 ； （3）设 ,那么 与 等价; （4）如果 且 ,则对所有的 ,有 ; （5）设 ,如果 ,那么 ;,2. 素 数,定义:设整数 。如果它除了显然因数 外没有其他的因数，则p就称为是素数，也叫不可约数。若 ， 且a不是素数，则a称为合数。 关于素数，有以下性质： （1）如果p是素数，且 ，则 或 ，即p至少整除a与b中的一
8、个。 （2）任何一个整数 ，均可以分解成素数幂之积： （3）若不计因数的顺序，这个分解式是唯一的。其中 , 是两两互不相同的素数， 是正整数。 （4）素数有无穷多个。 （5）设 表示不大于 的素数的数目，则 。,3. 同 余,设 ，如果 ，则称a和b模n同余，记为 ，整数n称为模数。由 于 等价于 ，所以 与 等价。因此，一般我们总假定 。如果 ，我们称b是a对模n的最小非负剩余，有时也称b为a对模n的余数。,同余式的一些基本性质,（1）反身性: ； （2）对称性:如果 ，那么 ； （3）传递性:如果 ， ,那么 ； （4）如果 ， 那么 ； 。 （5）如果 ， ，gcd ，(两个不同时为0的
9、整数a与b的最大公约数表示成gcd(a,b)那么 ，存在 ,当且仅当gcd 。,一些关于同余的基本概念(1),同余类 可用其中任一元素a(经常取 )代替，记作 。于是 从 中分别取一个数作为代表构成一个集合，称为模n的一个完全剩余系， 记为 ，称为模n的非负最小完全剩余系。,一些关于同余的基本概念(2),在模n的完全剩余系中，去掉那些与n不互素的数，剩下的部分称为模n的简化剩余系； 的简化剩余系记为 ，读为模n的非负最小简化剩余系。显然, 中的元便是不超过n并与n互素的那些数，它们的个数等于欧拉函数 的值。（欧拉函数的定义为: 小于自然数N并与N互质(除1以外无其它公因子)的自然数的个数用函数
10、 表示,称为欧拉函数。欧拉函数的具体性质会在后面第6小节进行阐述）,4. 模 运 算,给定正整数n，对任意a，若存在q，使得 则称r是a关于模n的余数，记为 。 若 则称整数a，b同余，记为 整数集中所有与数a同余的整数集合称为a的同余类，记为 。,模 运 算 的 性 质,（1） 当且仅当 。 （2） 当且仅当 。 （3）如果 ， ，则 。 a模n的运算给出了a对模n的余数。注意：模运算的结果是从0到 的一个整数。模运算就像普通的运算一样，它是可交换，可结合，可分配的。而且，对每一个中间结果进行模m运算，其作用与先进行全部运算，然后再进行模m运算所得到结果是一样的。,5. 最大公约数与最小公倍
11、数,设 ， 是两个整数，如果 且 ，那么就称b是 和 的公约数.一般的，设 ，是K个整数，如果 那么就称b是 的公约数。因为对于任意一个不等于零的整数，它的因数是有限的。所以，任意一对整数 ，其中一个不为零时，它们的公约数的个数也必定是有限的；同理，当 中有一个不为零时，它们的公约数是有限的.这样,我们引入最大公约数的概念。 定义: 设 ， 是两个整数，我们把 和 的公约数中最大的数称为 和 的最大公约数，记为( , )或 当 时，我们称 和 是互素的。 显然,最 大 公 约 数 的 性 质,（1） （2）若 | ,j=2,k ，则 （3）任意的整数x, 有 （4）对任意的整数x,有 （5）设
12、 , 是不都为零的整数，则一定存在一对整数 , ，使得：,最 小 公 倍 数 的 概 念,设 ， 是两个均不等于零的整数，如果 且 ，那么 1 就称为是 和 的公倍数，一般地，设 是k个均不等于零的整数。 如果 ，则称 l是 的公倍数。公倍数的集合是无穷集合，但根据自然数的理论，存在最小的正的公倍数。我们把 和 的正的公倍数中最小的数称为 和 的最小公倍数，记为 或,6. 欧拉（Euler）函数,欧拉（Euler）函数 设n1,欧拉函数 表示在区间 中与n互素的整数的个数。 欧拉函数 具有以下性质： (1)如果p是素数，则 ； (2)如果p是素数， 。那么 ； (3)对于整数 , 根据算术基本
13、定理，n可以分解成惟一的形如 的分解式，则 (4)若 和 互素，则 。,2.1.3 算法复杂性基础知识,所谓问题，是指一个要求给出解释的一般性提问，通常含有若干个未定参数或自由变量。它由两个要素组成 ，第一个要素是描述所有的参数，也就是对所有未定参数的一般性描述;第二个要素是解答必须满足的性质。一个问题 可以看成是由无穷多个问题实例组成的一个类。,1. 算 法 的 定 义,所谓算法是由明确指出操作的规则所组成的若干语句的集合，只要按照规则一步一步执行一定数目的语句，便可求出问题的答案。通常的计算机程序都可以看作是算法的表达形式，在问题的两要素中，对算法而言，第一个要素就是“输入”，第二个要素就是“输出”。如果把问题P的任意一个实例作为算法A的输入，A在有限步骤之内总能输出关于此实例的正确答案，我们就说算法A可解问题P。对于一个问题P，如果存在一个算法A可解问题P，我们称问题P是算法可解的。,2. 算 法 复 杂 性,算法的复杂性表征了算法在实际执行时所需计算能力方面的信息 ， 通常它由该算法所要求的最大时间与存取空间来确定。 由于
