计算机网络安全与管理：第五讲 理论基础

计算机网络安全与管理

第五讲理论基础本讲内容信息论基础抽象代数可计算性与计算复杂性数论基础Shannon的保密系统信息理论1949年，Shannon发表了一篇题为《保密系统的信息理论》的论文。用信息论的观点对信息保密问题进行了全面的阐述。宣告了科学的密码学时代的到来。通信系统模型目的：在信道有干扰的情况下，使接收的信息无错误或差错尽可能小。保密系统模型目的：使窃听者即使在完全准确地收到了接收信号的情况下也无法恢复出原始消息。密码体制的安全性（1）无条件安全或完善保密性（unconditionallysecure）：不论提供的密文有多少，密文中所包含的信息都不足以惟一地确定其对应的明文；具有无限计算资源（诸如时间、空间、资金和设备等）的密码分析者也无法破译某个密码系统。完善保密性一个保密系统（P，C，K，E，D）称为完善的无条件的保密系统，如果H(P)=H(P|C),其中，P为明文集合，C为密文集合，K为密钥集合，E为加密算法,D为解密算法,则完善保密系统存在的必要条件是H(P)≤H(K)。可见，要构造一个完善保密系统，其密钥量的对数（密钥空间为均匀分布的条件下）必须不小于明文集的熵。从熵的基本性质可推知，保密系统的密钥量越小，其密文中含有的关于明文的信息量就越大。存在完善保密系统如：一次一密（one-timepad）方案；不实用。密码体制的安全性（2）实际上安全计算上是安全：算出和估计出破译它的计算量下限，利用已有的最好的方法破译该密码系统所需要的努力超出了破译者的破译能力（诸如时间、空间、资金等资源）。可证明安全：从理论上证明破译它的计算量不低于解已知难题的计算量。伪密钥和惟一解距离当分析者截获到密文c时，他首先利用所有的密钥对其进行解密，并得到明文m′＝Dk(c)，k∈K。接下来，对于所有有意义的消息m′，他记录下与之对应的密钥。这些密钥构成的集合通常含有多个元素，并且至少含有一个元素，即正确的密钥。人们把那些可能在这个集合中出现但并不正确的密钥称为伪密钥（spuriouskey）。一个保密系统的惟一解距离定义为使得伪密钥的期望数等于零的n的值，记为n0，即在给定的足够的计算时间下分析者能惟一地计算出密钥所需要的密文的平均量。用于衡量在惟密文攻击下破译一个密码系统时，密码分析者必须处理的密文量的理论下界。Simmons认证系统的信息理论内容：将信息论用于研究认证系统的理论安全性和实际安全性问题，指出认证系统的性能极限以及设计认证码所必须遵循的原则。目的：一个是推导欺骗者欺骗成功的概率的下界；另一个是构造欺骗者欺骗成功的概率尽可能小的认证码。认证码基本要素有3个：信源集合；消息集合；编码规则集合，其中每一个编码规则由一个秘密密钥来控制。

认证系统模型一种是无仲裁者的认证系统模型。在这种模型中，只有3种参加者，即消息的发送者、接收者和入侵者。消息的发送者和接收者之间相互信任，他们拥有同样的秘密信息。另一种是有仲裁者的认证系统模型。在这种模型中，有4种参加者，即消息的发送者、接收者、入侵者和仲裁者，信息的发送者和接收者之间相互不信任，但他们都信任仲裁者，仲裁者拥有所有的秘密信息并且不进行欺骗。无仲裁者的认证系统模型无仲裁者的认证系统数学描述一个无分裂的、没有保密功能的、无仲裁者的认证系统，可由满足下列条件的四重组（S，A，K，ε）来描述：①S是所有可能的信源状态构成的一个有限集，称为信源集；②A是所有可能的认证标签构成的一个有限集；③K是所有可能的密钥构成的一个有限集，称为密钥空间；④对每一个k∈K,有一个认证规则：ek∈ε：S->A。消息集M定义为M=S×A。群一个元素的集合对于定义的运算封闭遵从结合律：(a.b).c=a.(b.c)

由单位元e：e.a=a.e=a

有逆元：a-1: a.a-1=e如果还遵从交换律：a.b=b.a

则我们称该群为阿贝尔群（交换群）abeliangroup循环群定义幂运算为群上运算的重复叠加例：a3=a.a.a且有单位元e=a0我们说一个群是循环的就是指对该群中的任意元素均可表示为某一固定元素的幂ieb=

ak

对某个a

与与任意一个b在群中。其中a称为该群的生成元环集合上定义了两种操作（乘和加）对于加法运算是一个阿贝尔群对于乘法运算有是封闭的满足结合律具有对加运算符合分配率：a(b+c)=ab+ac若对乘法具有可交换性则称为交换环若对乘法运算有单位元但无零因子，则称为整环域域作为定义了两中运算的集合具有对于加法是阿贝尔群对于乘法是阿贝尔群（忽略0）是一个环模运算定义“amodn”表示用n去除a得到的余数用“a=bmodn”表示a与b模n具有相同的余数对于一个数a通常可以表示为a=qn+r称r为余数（余数通常取最小的正数）模运算的性质模运算我们在整数群上定义模运算

Zn={0,1,…,n-1}构成了一个加法交换群具有乘法单位元具有下面的性质：if(a+b)=(a+c)modn thenb=cmodnbutif(a.b)=(a.c)modn thenb=cmodn当且仅当a与n互质例如：出现这种情况的原因是当有公因数时不会产生完整的余数集合最大公约数gcd该问题是数论中的一个普便问题GCD(a,b)表示能同时整除a与b的数中最大的一个当除1外不存在其它公因式时称作互质EuclideanAlgorithm该算法是一个很有效的计算最大公约数的算法利用到了GCD(a,b)=GCD(b,amodb)

EUCLID(a,b)1.A=a;B=b2.ifB=0returnA=gcd(a,b)3.R=AmodB4.A=B5.B=R6.goto2

例1970=1x1066+904 gcd(1066,904)1066=1x904+162 gcd(904,162)904=5x162+94 gcd(162,94)162=1x94+68 gcd(94,68)94=1x68+26 gcd(68,26)68=2x26+16 gcd(26,16)26=1x16+10 gcd(16,10)16=1x10+6 gcd(10,6)10=1x6+4 gcd(6,4)6=1x4+2 gcd(4,2)4=2x2+0 gcd(2,0)练习：gcd（2152，764）迦罗华域（有限域）

GaloisFields有限域理论在密码学中具有重要作用元素数为某一个素数的n次方这样的域被称为有限域（迦罗华域）记为GF(pn)经常用到的有：GF(p)GF(2n)GaloisFieldsGF(p)GF(p)是{0,1,…,p-1}的集合，其上定义了模p的算术运算构成了一个有限域因为乘法运算有逆元其上可以进行加减乘除运算GF(7)Example012345600000000101234562024613530362514404152635053164260654321FindingInversesEXTENDEDEUCLID(m,b)1. (A1,A2,A3)=(1,0,m); (B1,B2,B3)=(0,1,b)2.ifB3=0 returnA3=gcd(m,b);noinverse3.ifB3=1 returnB3=gcd(m,b);B2=b–1modm4.Q=A3divB35.(T1,T2,T3)=(A1–QB1,A2–QB2,A3–QB3)6.(A1,A2,A3)=(B1,B2,B3)7.(B1,B2,B3)=(T1,T2,T3)8.goto2练习：550在1769上的逆密码技术和算法复杂性计算复杂性：研究密码分析对于计算量的需求和密码分析的困难程度，从而得出这些密码技术和算法在现有可行的条件下是否具有足够的安全性：算法复杂性；问题复杂性。密码协议、方案和体制的安全性证明：零知识证明理论。问题（problem）即需要回答的一般性提问:它通常含有若干个参数。对于一个问题进行描述应该包括两方面的内容：必须对问题的所有给定参数给出一般性描述；必须描述该问题的答案（或解）应该满足的性质。当问题的所有参数都有了确定的取值时，我们称得到了该问题的一个实例（instance）。算法（algorithm）即求解某个问题的一系列具体步骤（通常被理解为求解所需的通用计算程序）。算法总是针对具体问题而言的，求解一个问题的算法通常不止一个。当某个算法能够回答一个问题的任何实例时，我们称该算法能够回答这个问题。当一个问题至少有一个能够回答该问题的算法时，我们称该问题可解（resolvable），否则称该问题不可解（unresolvable）。算法复杂性即度量该算法所需的计算能力，包括：时间复杂性T（timecomplexity）；空间复杂性S（spacecomplexity）；随机位数目；信道带宽；数据总量；……算法复杂性计算复杂性的表示符号为“O”（称为“大O”），表示计算复杂性的数量级好处：使算法复杂性度量与处理器的运行速度和指令运行时间无关；明确地揭示了输入的数据长度对算法复杂性的影响。算法复杂性算法的分类及其运行时间运算次数宇宙年龄的类别复杂性时间多项式常数11微妙线性1秒二次11.6天三次32,000年指数问题复杂性研究问题的内在复杂性，即在图灵机上解决最难的问题实例所需的最小时间和空间条件。图灵机图灵机是一种具有无限读写存储带的有限状态机，可以被当作一个实际可用的计算模型。确定性图灵机。非确定性图灵机：能够进行猜测。求解一个问题分两个阶段：猜测阶段和验证阶段。问题分类易处理的（tractable）：确定性图灵机上能够在多项式时间内得到处理的问题。称易处理问题的全体为“多项式时间可解类”，记为P。非确定性图灵机上能够在多项式时间内得到处理的问题被称为“非确定性多项式时间可解问题”，简称NP问题。NP问题的全体被称为“非确定性多项式时间可解类”，记为NP。NP问题意义：能够通过非确定性的多项式时间算法对许多对称密钥算法和所有公钥算法进行攻击。NP完全问题：指NP中的任何一个问题都可以通过多项式时间转化为该问题。NP完全问题的全体被记为NPC。NP完全问题是NP问题中最难的问题。零知识证明证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。零知识“洞穴”零知识“洞穴”（1）V站在A处；（2）P走进洞穴，到达C处或D处；（3）当P消失在洞穴中时，V走到B处；（4）V呼叫P，要求P：（a）从左通道出来；或者（b）从右通道出来；（5）P答应V的呼叫，并在有必要的情况下用咒语打开C与D之间的秘密之门；（6）重复步骤（1）~（5）次。基本的零知识协议过程假设P知道一部分信息，并且该信息是一个难题的解法：（1）P用自己的信息和一个随机数将这个难题转变为与之同构的新难题，然后用自己的信息和这个随机数这个新难题；（2）P利用位承诺方案提交对于这个新难题的解法；（3）P向V透漏这个新难题，V无法通过新难题得到关于原难题或其解法的任何信息；（4）V要求P：（a）证明新、旧难题同构；或者（b）公布P在（2）中提交解法并证明该解法的确为新难题的解法；（5）P答应V的要求；（6）重复步骤（1）~（5）次。交互与非交互交互零知识证明：证明者和验证者之间必须进行交互。由Goldwasser等人在20世纪80年代初提出GMR模型；

FFS模型。

非交互零知识证明：用一个短随机串代替交互过程并实现了零知识证明。20世纪80年代末，Blum等人进一步提出成员（或定理）的非交互零知识证明系统；知识（或身份）的非交互零知识证明系统。交互图灵机交互图灵机指的是一个具有一条只读输入带、一条工作带、一条随机带、一条只读通信带和一条只写通信带的图灵机。其中，随机带上包含一条无限长的随机比特序列，并且只能从左向右读入。“一个交互图灵机投一个硬币”指该图灵机从自己的随机带上读取1bit。交互协议即满足以下两个条件的有序图灵机（A