计算机系统安全课件第3章信息论与数学基础.ppt

《计算机系统安全课件第3章信息论与数学基础.ppt》由会员分享，可在线阅读，更多相关《计算机系统安全课件第3章信息论与数学基础.ppt（78页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第3 3章章信息论与数学基础信息论与数学基础 3.1 3.1 信息论信息论3.2 3.2 复杂性理论复杂性理论3.3 3.3 数论数论3.4 3.4 因子分解因子分解3.5 3.5 素数生成元素数生成元3.6 3.6 有限域上的离散对数有限域上的离散对数返回目录返回目录第第3 3章章信息论与数学基础信息论与数学基础 3.1.1 3.1.1 熵和不确定性熵和不确定性3.1.2 3.1.2 语言信息率语言信息率3.1.3 3.1.3 密码体制的安全性密码体制的安全性3.1.4 3.1.4 唯一解距离唯一解距离3.1.5 3.1.5 信息论的运用信息论的运用3.1.6 3.1.6 混乱和散布混乱和

2、散布返回本章首页返回本章首页第第3 3章章信息论与数学基础信息论与数学基础 信信息息论论中中一一条条消消息息的的信信息息量量的的定定义义为为：对对消消息息的的所所有有可可能能含含义义进进行行编编码码时时所所需需要要的的最最少少的比特数。的比特数。一一条条消消息息MM中中的的信信息息量量可可通通过过它它的的熵熵来来度度量量，表表示示为为H H（MM）。通通常常，一一条条消消息息或或随随机机变变量量 的熵是：的熵是：返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 其中：其中：P()P()表示随机变量表示随机变量 的概率分布的概率分布 B B为为 的分布空间。的分布空间。一条一条消息

3、的熵也表示它的不确定性消息的熵也表示它的不确定性。即当消息被加密。即当消息被加密成密文时，为了获取明文，需要解密的明文的比特数。成密文时，为了获取明文，需要解密的明文的比特数。如果如果H(M)=0H(M)=0，则表示该信息不含任何不确定性，该消，则表示该信息不含任何不确定性，该消息百分之百会发生。如果息百分之百会发生。如果H(M)H(M)很大，则表示该信息的很大，则表示该信息的不确定性很大。不确定性很大。从安全的角度来看，明文的熵值不大，则不确定性太从安全的角度来看，明文的熵值不大，则不确定性太小，这样攻击者有很大的概率猜中该信息。小，这样攻击者有很大的概率猜中该信息。返回本节返回本节第第3

4、3章章信息论与数学基础信息论与数学基础 对一个给定的语言，其对一个给定的语言，其语言信息率语言信息率是：是：其其中中，N N是是消消息息的的长长度度，在在N N相相当当大大时时，标标准准英英语语的的语语言言信信息息率率（r r值值）在在1.01.0比比特特/字字母母与与1.51.5比特比特/字母之间字母之间 （香农的估计值是（香农的估计值是1.2bit1.2bit）如如果果在在一一种种语语言言中中有有L L个个字字母母，其其语语言言绝绝对对信信息率息率是：是：返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 对英语而言，它有对英语而言，它有2626个字母，其语言绝对信个字母，其语

5、言绝对信息率是息率是loglog2 226=4.726=4.7比特比特/字母。英语的实际信字母。英语的实际信息率（息率（1.21.2）大大低于其绝对信息率并不惊奇。）大大低于其绝对信息率并不惊奇。英语是一种高多余度（英语是一种高多余度（4.7-1.2=3.54.7-1.2=3.5比特比特/字母）字母）的语言。的语言。一种语言的一种语言的多余度多余度称为称为D D，定义为：，定义为：D=R-r 返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 密码分析者利用自然语言的多余度来减少可能的明文密码分析者利用自然语言的多余度来减少可能的明文数目数目。语言的。语言的多余度越大，它就越容易被

6、攻击多余度越大，它就越容易被攻击。攻击者通过分析关于明文攻击者通过分析关于明文p p的统计信息，明文会从所有的统计信息，明文会从所有可能的明文集合中暴露出来。可能的明文集合中暴露出来。因此，许多正在使用的密码装置在加密明文前，都要因此，许多正在使用的密码装置在加密明文前，都要用一个压缩程序减少明文大小，其原因就在于此。压用一个压缩程序减少明文大小，其原因就在于此。压缩（明文）可降低消息的多余度。缩（明文）可降低消息的多余度。密密码码体体制制的的熵熵是是密密钥钥空空间间大大小小的的量量度度。密密钥钥的的数数目目K K取取以以2 2为底的对数可估计其大小：为底的对数可估计其大小：返回本节返回本节一

7、个密码体系的熵越大，破译它的难度就越大。一个密码体系的熵越大，破译它的难度就越大。第第3 3章章信息论与数学基础信息论与数学基础 唯一解距离唯一解距离是指，当进行强力攻击时，可能解是指，当进行强力攻击时，可能解密出唯一有意义的明文所需要的最少密文量。密出唯一有意义的明文所需要的最少密文量。一般而言，一般而言，唯一解距离越长，密码体制越好唯一解距离越长，密码体制越好。对绝大多数对称密码体制而言，唯一解距离被对绝大多数对称密码体制而言，唯一解距离被定义为密码体制的熵除以语言的多余度：定义为密码体制的熵除以语言的多余度：U UH H（K K）/D/D 返回本节返回本节第第3 3章章信息论与数学基础信

8、息论与数学基础 例如，对有例如，对有5656比特密钥和用比特密钥和用ASCIIASCII字符表示的英文字符表示的英文消息来说，消息来说，DESDES（数据加密标准）的唯一解距离（数据加密标准）的唯一解距离是：是：56/3.556/3.51616大约大约1616个个ASCIIASCII字符，或字符，或5656比特。比特。唯一解距离不是对密码分析需要多少密文的度量，唯一解距离不是对密码分析需要多少密文的度量，而是对存在唯一合理的密码分析解所需要的密文而是对存在唯一合理的密码分析解所需要的密文数量的指标。数量的指标。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 唯一解距离与多余度成

9、反比，当多余度接近于唯一解距离与多余度成反比，当多余度接近于零时（唯一解距离接近无穷大，也就是解密出零时（唯一解距离接近无穷大，也就是解密出唯一有意义的明文所需要的最少密文接近无穷唯一有意义的明文所需要的最少密文接近无穷大），即使一个普通的密码体制也可能是不可大），即使一个普通的密码体制也可能是不可破译的。破译的。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 很少有实际的算法密码分析上是绝对不可破译很少有实际的算法密码分析上是绝对不可破译的。各式各样的特点起着破译已加密信息的突的。各式各样的特点起着破译已加密信息的突破作用。然而，类似于信息论方面的考虑有时破作用。然而，类似于

10、信息论方面的考虑有时是有用的。是有用的。例如，为了使一个确立的算法增加安全性，建例如，为了使一个确立的算法增加安全性，建议一个密钥变化其间隔或周期，以加大唯一解议一个密钥变化其间隔或周期，以加大唯一解距离的值。距离的值。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础（1 1）混乱）混乱 用于掩盖明文和密文之间的关系用于掩盖明文和密文之间的关系。这可以挫败。这可以挫败通过研究密文以获取多余度和统计模式。通过通过研究密文以获取多余度和统计模式。通过代替代替可做到这点。一个简单的代替密码，如凯可做到这点。一个简单的代替密码，如凯撒移位密码，其中每一个确定的明文字符被一撒移位密码，其中

11、每一个确定的明文字符被一个密文字符代替。现代的代换密码更复杂，一个密文字符代替。现代的代换密码更复杂，一个长长的明文块被代替成一个不同的密文块，个长长的明文块被代替成一个不同的密文块，并且代替的机制随明文中的每一比特发生变化。并且代替的机制随明文中的每一比特发生变化。返回本节返回本节13简单字符的加密、解密（凯撒移位）简单字符的加密、解密（凯撒移位）加密的思想是：加密的思想是：将每个字母将每个字母C C加（或减）一序数加（或减）一序数k k，即用它后的第，即用它后的第k k个字母个字母代替，变换式公式：代替，变换式公式：c=c+kc=c+k 例如序数例如序数k k为为5 5，这时，这时 “A

12、A”“F F”，“a a”“f f”，“B B”“G G”当加序数后的字母超过当加序数后的字母超过“Z”Z”或或“z”z”则则 c=c+k-26c=c+k-26 例如：例如：You are good You are good Dtz fwj ltti Dtz fwj ltti 解密为加密的逆过程解密为加密的逆过程 将每个字母将每个字母C C减（或加）减（或加）一序数一序数k k，即，即 c=c-k,c=c-k,例如序数例如序数k k为为5 5，这时，这时 “Z Z”“U U”，“z z”“u u”，“Y Y”“T T”当加序数后的字母小于当加序数后的字母小于“A”A”或或“a”a”则则 c=c

13、-k+26c=c-k+2614void main()char c;while(c=getchar()!=n)if(c=a&c=A&cZ&cz)c=c-26;printf(%c,c);加密程序：加密程序：15void main()char c;while(c=getchar()!=n)if(c=a&c=A&c=Z)c=c-4;if(cA|c=a-4)c=c+26;printf(%c,c);解密程序：解密程序：第第3 3章章信息论与数学基础信息论与数学基础 （2 2）散布）散布 通过将明文多余度分散到密文中使之分散开来通过将明文多余度分散到密文中使之分散开来。产生散布最简单的方法是通过产生散布最简

14、单的方法是通过换位换位（也称为置换）（也称为置换）。一个简单的换位密码，如列换位体制，只简单。一个简单的换位密码，如列换位体制，只简单地重新排列明文字符。现代密码也做这种类型转地重新排列明文字符。现代密码也做这种类型转换，但它们也利用其他能将部分消息散布到整个换，但它们也利用其他能将部分消息散布到整个消息的散布类型。消息的散布类型。返回本节第第3 3章章信息论与数学基础信息论与数学基础 3.2.1 3.2.1 算法的复杂性算法的复杂性3.2.2 3.2.2 问题的复杂性问题的复杂性3.2.3 NP3.2.3 NP完全问题完全问题返回本章首页返回本章首页第第3 3章章信息论与数学基础信息论与数学

15、基础 密码体制的强度由破译它所需的计算能力确密码体制的强度由破译它所需的计算能力确定的，所需计算能力越大，密码体制越安全。定的，所需计算能力越大，密码体制越安全。一个算法的计算复杂性由两个变量来度量：一个算法的计算复杂性由两个变量来度量：（1 1）T T（时间复杂性）。（时间复杂性）。（2 2）S S（空间复杂性或所需存储空间）。（空间复杂性或所需存储空间）。T T和和S S一般表示为一般表示为n n的函数。的函数。n n是输入的尺寸。是输入的尺寸。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 通常，一个算法的计算复杂性的数量级用称之为通常，一个算法的计算复杂性的数量级用称之

16、为“大大O O”的符号来表示。的符号来表示。计算复杂性的数量级是这种类型的函数：当计算复杂性的数量级是这种类型的函数：当n n变大时，变大时，增长得最快的函数；增长得最快的函数；所有常数和较低阶形式的函数忽所有常数和较低阶形式的函数忽略不计略不计。例如，一个所给的算法的复杂性是。例如，一个所给的算法的复杂性是 4n2+7n+12 ，那么，其计算复杂性是那么，其计算复杂性是 n2 阶的，表示为阶的，表示为O(n2)。第第3 3章章信息论与数学基础信息论与数学基础 表表3.1 3.1 不同算法族运行时间不同算法族运行时间与与n的关系的关系 复杂度复杂度 所需运算所需运算 所需时间（所需时间（106

17、运算运算/秒）秒）常数常数 O(1)11微秒微秒 线性线性 O(n)106 1秒秒 二次方二次方 O(n2)1012 11.6天天 三次方三次方 O(n3)1018 32 000年年 指数指数 O(2 n)10 301 303 宇宙年龄的宇宙年龄的10 301 006倍倍 返回本节第第3 3章章信息论与数学基础信息论与数学基础 密码强力攻击的时间复杂性是与可能的密钥总数成比密码强力攻击的时间复杂性是与可能的密钥总数成比例的，它是密钥长度的指数函数。例的，它是密钥长度的指数函数。如果密钥长度为如果密钥长度为n n，则强力攻击的复杂性是，则强力攻击的复杂性是O(2O(2n)。对于对于56bit56

18、bit密钥的复杂性是密钥的复杂性是2 25656（22852285年）。年）。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 复杂性理论，按照解决问题时所需最少的时间及复杂性理论，按照解决问题时所需最少的时间及最小的空间，归纳成不同类别的复杂度问题。最小的空间，归纳成不同类别的复杂度问题。多项式时间多项式时间，在计算复杂度理论中，指的是一个，在计算复杂度理论中，指的是一个问题的计算时间问题的计算时间m(n)m(n)不大于问题大小不大于问题大小n n的多项式倍的多项式倍数。（数。（O(n)O(n)问题。）问题。）-易处理问题易处理问题超多项式时间超多项式时间，表示任何多项式时间的

19、输入数目，表示任何多项式时间的输入数目只要够大，超多项式时间所需的解题时间终究会只要够大，超多项式时间所需的解题时间终究会大大超过任何多项式时间的问题。大大超过任何多项式时间的问题。-难解问题难解问题指数时间指数时间（Exponential timeExponential time）就是一例。）就是一例。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 依照求解问题所需的时间，复杂理论也将各种问题区依照求解问题所需的时间，复杂理论也将各种问题区分成下面几类：分成下面几类：（1 1）P P问题：代表那些能够在多项式时间问题：代表那些能够在多项式时间(与时间复杂度与时间复杂度有关有关

20、)内可解的问题。内可解的问题。（2 2）NPNP问题：多项式时间内可验证（猜出）的问题。问题：多项式时间内可验证（猜出）的问题。（找不到多项式时间算法解的问题）（找不到多项式时间算法解的问题）（3 3）NPNP完全问题：是完全问题：是NPNP问题中的一些特殊问题，问题中的一些特殊问题，NPNP中中的所有问题都可以转换成的所有问题都可以转换成NP-NP-完全问题，只要完全问题，只要NPNP完全完全问题解决了，其他问题都可以解决。是问题解决了，其他问题都可以解决。是NPNP问题中最困问题中最困难的问题。难的问题。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 （4 4）PSPACE

21、问题：它是较问题：它是较NP复杂度更高一级的问题，复杂度更高一级的问题，但但PSPACENP是否成立仍是没有被解决的问题。是否成立仍是没有被解决的问题。（5）EXPTIME问题：复杂度最高的称为问题：复杂度最高的称为EXPTIME，EXPTIME问题需要指数的时间才能解决。问题需要指数的时间才能解决。EXPTIME已被证明不等于已被证明不等于P。返回本节第第3 3章章信息论与数学基础信息论与数学基础 例举一些例举一些NPNP完全问题：完全问题：（1 1）整数分解问题）整数分解问题任何整数都可以分解成标准形式：任何整数都可以分解成标准形式：m=m=，pi是素数，是素数，ei N N当当mm较小时

22、，这个问题不太困难，例如较小时，这个问题不太困难，例如6 62323，10010022522252。但当但当mm较大时，此问题就变得非常困难了。较大时，此问题就变得非常困难了。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 （2 2）背包问题）背包问题 背包问题是这样的一个问题：已知长度为背包问题是这样的一个问题：已知长度为k k的的圆形背包及长度分别为圆形背包及长度分别为a1 1，a2 2，an n的的n n个个圆形物品。假定这些物品的半径和背包半径圆形物品。假定这些物品的半径和背包半径相同，要求从相同，要求从n n个物品中选出若干个正好装满个物品中选出若干个正好装满这个背包

23、。这个背包。第第3 3章章信息论与数学基础信息论与数学基础 把背包问题抽象成数学模型，称为子集合问题：把背包问题抽象成数学模型，称为子集合问题：设有长度为设有长度为n n的向量的向量 A=A=（a1 1，a2 2，an n），任意给定一个正整），任意给定一个正整数数k k，寻找有没有一些恰好等于，寻找有没有一些恰好等于k k，即求方程：，即求方程：的解向量的解向量 x=(=(x1 1，x2 2，xn n）其中）其中xi=0=0或或1 1。当当n n比较小的时候，可以用穷举法求得解向量，比较小的时候，可以用穷举法求得解向量，但当但当n n比较大时，穷举法就不可行了。比较大时，穷举法就不可行了。背

24、包问题是背包问题是NPNP完全问题。完全问题。第第3 3章章信息论与数学基础信息论与数学基础 （3 3）离散对数问题）离散对数问题 设设x，r，n n是正整数，已知是正整数，已知x x，r r和和n n，可以很快，可以很快地求得地求得 反过来，如果已知反过来，如果已知y，和和n，求，求r使得：使得：成立，这便是离散对数问题。离散对数问题也成立，这便是离散对数问题。离散对数问题也是是NPNP完全问题。完全问题。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 3.3.1 模运算模运算 3.3.2 素数素数 3.3.3 最大公因子最大公因子 3.3.4 取模数求逆元取模数求逆元 3.

25、3.5 费马小定理费马小定理 3.3.6 欧拉函数欧拉函数 3.3.7 中国剩余定理中国剩余定理 3.3.8 二次剩余二次剩余3.3.9 勒让德符号勒让德符号 3.3.10 雅可比符号雅可比符号 3.3.11 Blum整数整数3.3.12 生成元生成元3.3.13 有限域有限域3.3.14 GF上的计算上的计算返回本章首页返回本章首页第第3 3章章信息论与数学基础信息论与数学基础 模运算是这样一个问题，举例来说，如果小刘模运算是这样一个问题，举例来说，如果小刘说她说她10:0010:00会回家，而她迟到了会回家，而她迟到了1313个小时，那个小时，那么她什么时候回家的呢？这就是模么她什么时候回

26、家的呢？这就是模1212运算：运算：(10(1013)mod 1213)mod 121111另一种写法是：另一种写法是：10101311(mod 12)1311(mod 12)返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 本质上，如果本质上，如果a=b+kna=b+kn对某一些整数对某一些整数k k成立，那成立，那么么ab(mod n)ab(mod n)。如果。如果a a和和b b是正的，且是正的，且a a小于小于n n，那么可将那么可将a a看作看作b b被被n n整除后的余数。整除后的余数。通常，通常，a a和和b b被被n n整除时有相同的余数。有时，整除时有相同的余数

27、。有时，b b被叫做被叫做模模n n的余数的余数。有时。有时a a被叫做与被叫做与b b模模n n同余。同余。（“”表示同余表示同余）。）。第第3 3章章信息论与数学基础信息论与数学基础 从从0n-10n-1的整数组成的集合构成了的整数组成的集合构成了模模n n的的“完完全剩余集全剩余集”。这意味着，对每一个整数。这意味着，对每一个整数a a，它，它的模的模n n的余项是从的余项是从0n-10n-1的某个整数。的某个整数。a a模模n n的运算给出了的运算给出了a a的余数，这样的余数是从的余数，这样的余数是从0n-10n-1的某个整数。这种运算称为的某个整数。这种运算称为模变换模变换。例。例

28、如，如，5 mod 3=25 mod 3=2。第第3 3章章信息论与数学基础信息论与数学基础 密码学用了许多模密码学用了许多模n n运算，因为像计算离散运算，因为像计算离散对数和平方根这样的问题是困难的，而模运对数和平方根这样的问题是困难的，而模运算可将所有中间结果和最后结果限制在一个算可将所有中间结果和最后结果限制在一个范围内，所以用它进行计算比较容易。范围内，所以用它进行计算比较容易。计算数计算数a a的乘方并对其取模：的乘方并对其取模：它可分成一系列的乘法和除法（取模）。有它可分成一系列的乘法和除法（取模）。有方法使它运算得更快。方法使它运算得更快。第第3 3章章信息论与数学基础信息论与

29、数学基础 例如，如果要计算例如，如果要计算 ，不要运用直接计算的方，不要运用直接计算的方法进行法进行7 7次乘法和一个大数的模化简运算次乘法和一个大数的模化简运算,相反，应进行三次较小的乘法和三次较小的模化相反，应进行三次较小的乘法和三次较小的模化简运算简运算:依此类推：依此类推：返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 素数素数：比：比1 1大，其因子只有大，其因子只有1 1和它本身，没有和它本身，没有其他可以整除它。其他可以整除它。2 2是一个素数，其他素数诸如是一个素数，其他素数诸如7373，2 5212 521，2 2 365 347 734 339365 347

30、 734 339，和，和2756 839-12756 839-1等。等。素数是无限的素数是无限的，密码学常用大的素数（，密码学常用大的素数（512512比比特，甚至更长）。特，甚至更长）。任意整数任意整数a1a1，都可以唯一的因式分解为素数，都可以唯一的因式分解为素数的乘积。的乘积。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 两个数互素是指：当它们除了两个数互素是指：当它们除了1 1之外没有共同的因子之外没有共同的因子；换而言之，如果换而言之，如果a和和n的最大因子等于的最大因子等于1 1，那么写作：，那么写作：gcd(a，n)=1)=1或写成或写成 (a，n)=1)=1数

31、数1515和和2828是互素的，是互素的，1515和和2727不是，而不是，而1313和和500500是。是。一个素数与它的倍数以外的任何其他数都是互素的。一个素数与它的倍数以外的任何其他数都是互素的。确定一个大数的素因子不是一件容易的事。确定一个大数的素因子不是一件容易的事。如果每个整数都表示成素数乘积的形式，就可以很容如果每个整数都表示成素数乘积的形式，就可以很容易的求出两个正整数的最大公约数。易的求出两个正整数的最大公约数。返回本节返回本节37辗转相除法辗转相除法(欧几里德算法欧几里德算法)求两个整数的最大公约数、最小公倍数。求两个整数的最大公约数、最小公倍数。分析：求最大公约数的算法如

32、下：分析：求最大公约数的算法如下：1）对于已知两数）对于已知两数m，n，使得使得mn。2）m除以除以n得余数得余数r。3）若若r=0，则则n为为求求得得的的最最大大公公约约数数，算法结束；否则执行算法结束；否则执行4）。）。4）mn，nr，再重复执行，再重复执行2）。）。（最最小小公公倍倍数数=两两个个整整数数之之积积/最最大大公公约数）。约数）。算法的算法的N-S流程图如右图，实现流程图如右图，实现的程序代码如下：的程序代码如下：38void main()int n,m,nm,r,t;scanf(%d%d,&m,&n);nm=n*m;if(m 0且且z=1，那么，那么 p 不是素数。不是素数

33、。（5）设）设j=j+1。如果。如果j b且且z=p-1，设，设z=z 2 mod p，然后回到步骤（，然后回到步骤（4）。）。（6）如果）如果j=b且且z=p-1,那么那么 p 不是素数。不是素数。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 另一种更简单的测试是由另一种更简单的测试是由Lehmann独立研究独立研究出的。下面是迭代数设置为出的。下面是迭代数设置为100的这个算法：的这个算法：（1）选择一个待测的随机数。）选择一个待测的随机数。（2）确信不能被任何小素数整除。测试）确信不能被任何小素数整除。测试2，3，5，7和和11将显著地提高这个算法的速度。将显著地提高这

34、个算法的速度。（3）选择）选择100个个1和和n-1之间的随机数之间的随机数a1，a2，a100。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 （4 4）对所有的）对所有的ai=a1，a2，a100，计算计算ai (n-1)/2(n-1)/2：如果对所有的如果对所有的i,ai (n-1)/2(n-1)/2=1(mod n)，那，那n可可能是合数。能是合数。如果对任一个如果对任一个i,ai (n-1)/2(n-1)/211或或-1(mod n)，那，那么么n是合数。是合数。如果对所有如果对所有i,ai (n-1)/2(n-1)/2=1=1或或-1(mod n)，但并，但并非对所

35、有非对所有i 均等于均等于1 1，那么，那么n 是素数。是素数。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 许多关于许多关于RSARSA的文献都建议对于和应该用强素的文献都建议对于和应该用强素数。这些强素数是满足某些特性的素数。使得数。这些强素数是满足某些特性的素数。使得用某些特殊的因子分解的方式对它们的乘积进用某些特殊的因子分解的方式对它们的乘积进行分解是困难的。某些建议的性质如下：行分解是困难的。某些建议的性质如下：p-1和和q-1的最大公因子应该较小。的最大公因子应该较小。p-1和和q-1都应有大的素因子，分别记为都应有大的素因子，分别记为p和和q。返回本节返回本节第

36、第3 3章章信息论与数学基础信息论与数学基础 p p-1-1和和q q-1-1都应有大的素因子，分别记为都应有大的素因子，分别记为p p”和和q q”。(p-1)/2(p-1)/2和和(q-1)/2(q-1)/2都应该是素数。都应该是素数。在此仍然推荐使用强素数，即使它们不会使在此仍然推荐使用强素数，即使它们不会使因子分解更简单些。虽然它使得产生素数更困因子分解更简单些。虽然它使得产生素数更困难，但它是无害的。难，但它是无害的。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 1.1.离散对数基本定义离散对数基本定义给定一个质数给定一个质数p，和有限域，和有限域Zp上的一个本原元

37、上的一个本原元a，对，对Zp上整数上整数b，寻找唯一的整数，寻找唯一的整数c，使得，使得acb(mod p)。模指数模指数运算运算ax mod n是频繁地用于密码体制中是频繁地用于密码体制中的另一种单向函数，它的逆问题是找出一个的另一种单向函数，它的逆问题是找出一个数的离散对数，这是一个困难的问题。数的离散对数，这是一个困难的问题。返回本章首页返回本章首页第第3 3章章信息论与数学基础信息论与数学基础 2.2.举例举例 例如求例如求x，使得，使得x满足满足3x mod 17=15。虽然可。虽然可以求出以求出x=6，但目前没有更简单的求，但目前没有更简单的求离散对数离散对数的方法。的方法。并不是

38、所有的离散对数都有解。可以很容易并不是所有的离散对数都有解。可以很容易发现，下面的方程并没有解：发现，下面的方程并没有解：3x mod 13=7 对对10241024比特或更大的数求离散对数非常困难。比特或更大的数求离散对数非常困难。第第3 3章章信息论与数学基础信息论与数学基础 3.3.计算有限群中的离散对数计算有限群中的离散对数 密码设计者对下面密码设计者对下面3 3个主要群上的离散对数是个主要群上的离散对数是很感兴趣的：很感兴趣的：素数域的乘法群素数域的乘法群GFGF（p p）。）。特征为特征为2 2的有限域的有限域GFGF（2 2n）上的乘法群。）上的乘法群。有限域有限域F F上的椭圆

39、曲线群上的椭圆曲线群ECEC（F F）：）：返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 1 1一条消息的熵和一个密码体制的熵如何计算，它们与一条消息的熵和一个密码体制的熵如何计算，它们与 安安全性有什么关系？全性有什么关系？2 2什么叫唯一解距离？简述它与多余度的关系。什么叫唯一解距离？简述它与多余度的关系。3 3简述简述“散布散布”与与“混乱混乱”在密码中的应用。在密码中的应用。4 4什么是计算复杂性、空间复杂性和问题复杂性？简述什么是计算复杂性、空间复杂性和问题复杂性？简述P P问问题、题、NPNP问题和问题和NP-NP-完全问题之间的关系。完全问题之间的关系。5 5简

40、述中国剩余定理并说明它的一个实际应用。简述中国剩余定理并说明它的一个实际应用。第第3 3章章信息论与数学基础信息论与数学基础 6 6对整数对整数1515和和1818，有以下问题：，有以下问题：（1 1）它们是否互素？）它们是否互素？（2 2）试用）试用欧几里德算法欧几里德算法求它们的最大公因子。求它们的最大公因子。（3 3）是否有解，为什么？）是否有解，为什么？（4 4）如果有解，请给出两种计算方法。）如果有解，请给出两种计算方法。7 7验证验证437437是一个是一个BlumBlum数。数。8 8素数的个数是无限还是有限？找素数与求分解因子相比，素数的个数是无限还是有限？找素数与求分解因子相比，哪个难度更大？哪个难度更大？返回本章首页返回本章首页