第第3 3章章信息论与数学基础信息论与数学基础 第第3章章信息信息论与数学基与数学基础3.1 信息论信息论3.2 复杂性理论复杂性理论3.3 数论数论3.4 因子分解因子分解3.5 素数生成元素数生成元3.6 有限域上的离散对数有限域上的离散对数返回目录返回目录第第3 3章章信息论与数学基础信息论与数学基础 3.1 信息信息论3.1.1 熵和不确定性熵和不确定性3.1.2 语言信息率语言信息率3.1.3 密码体制的安全性密码体制的安全性3.1.4 唯一解距离唯一解距离3.1.5 信息论的运用信息论的运用3.1.6 混乱和散布混乱和散布返回本章首页返回本章首页第第3 3章章信息论与数学基础信息论与数学基础 3.1.1 熵和不确定性和不确定性信信息息论论中中一一条条消消息息的的信信息息量量的的定定义义为为：对对消消息息的的所所有有可可能能含含义义进进行行编编码码时时所所需需要要的的最最少少的比特数。的比特数。一一条条消消息息M中中的的信信息息量量可可通通过过它它的的熵熵来来度度量量，表表示示为为H（M）。通通常常，一一条条消消息息或或随随机机变变量量的熵是：的熵是：返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 其中：其中：P()表示随机变量表示随机变量的的概率分布概率分布 B为为的分布空间。的分布空间。一条一条消息的熵也表示它的不确定性消息的熵也表示它的不确定性。即当消息被加密。即当消息被加密成密文时，为了获取明文，需要解密的明文的比特数。成密文时，为了获取明文，需要解密的明文的比特数。 如果如果H(M)=0，则表示该信息不含任何不确定性，该消，则表示该信息不含任何不确定性，该消息百分之百会发生。如果息百分之百会发生。如果H(M)很大，则表示该信息的很大，则表示该信息的不确定性很大。不确定性很大。从安全的角度来看，明文的熵值不大，则不确定性太从安全的角度来看，明文的熵值不大，则不确定性太小，这样攻击者有很大的概率猜中该信息。小，这样攻击者有很大的概率猜中该信息。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 3.1.2 语言信息率言信息率对一个给定的语言，其对一个给定的语言，其语言信息率语言信息率是：是： 其其中中，N是是消消息息的的长长度度，在在N相相当当大大时时，标标准准英英语语的的语语言言信信息息率率（r值值）在在1.0比比特特/字字母母与与1.5比特比特/字母之间字母之间 （香农的估计值是（香农的估计值是1.2bit）如如果果在在一一种种语语言言中中有有L个个字字母母，其其语语言言绝绝对对信信息率息率是：是： 返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 对英语而言，它有对英语而言，它有26个字母，其语言绝对信个字母，其语言绝对信息率是息率是log226=4.7比特比特/字母。英语的实际信字母。英语的实际信息率（息率（1.2）大大低于其绝对信息率并不惊奇。）大大低于其绝对信息率并不惊奇。英语是一种高多余度（英语是一种高多余度（4.7-1.2=3.5比特比特/字母）字母）的语言。的语言。一种语言的一种语言的多余度多余度称为称为D，定义为：，定义为：D=R-r返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 3.1.3 密密码体制的安全性体制的安全性 密码分析者利用自然语言的多余度来减少可能的明文密码分析者利用自然语言的多余度来减少可能的明文数目数目。语言的。语言的多余度越大，它就越容易被攻击多余度越大，它就越容易被攻击。攻击者通过分析关于明文攻击者通过分析关于明文p的统计信息，明文会从所有的统计信息，明文会从所有可能的明文集合中暴露出来。可能的明文集合中暴露出来。因此，许多因此，许多正在使用的密码装置在加密明文前，都要正在使用的密码装置在加密明文前，都要用一个压缩程序减少明文大小，其原因就在于此。压用一个压缩程序减少明文大小，其原因就在于此。压缩（明文）可降低消息的多余度。缩（明文）可降低消息的多余度。密密码码体体制制的的熵熵是是密密钥钥空空间间大大小小的的量量度度。密密钥钥的的数数目目K取取以以2为底的对数可估计其大小：为底的对数可估计其大小： 返回本节返回本节一个密码体系的熵越大，破译它的难度就越大。一个密码体系的熵越大，破译它的难度就越大。第第3 3章章信息论与数学基础信息论与数学基础 3.1.4 唯一解距离唯一解距离 唯一唯一解距离解距离是指，当进行强力攻击时，可能是指，当进行强力攻击时，可能解密出唯一有意义的明文所需要的最少密文量。解密出唯一有意义的明文所需要的最少密文量。一般而言，一般而言，唯一解距离越长，密码体制越好唯一解距离越长，密码体制越好。 对对绝大多数对称密码体制而言，唯一解距离绝大多数对称密码体制而言，唯一解距离被定义为密码体制的熵除以语言的多余度：被定义为密码体制的熵除以语言的多余度： UH（K）/D 返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 例如例如，对有，对有56比特密钥和用比特密钥和用ASCII字符表示的英字符表示的英文消息来说，文消息来说，DES（数据加密标准）的（数据加密标准）的唯一解距唯一解距离是：离是： 56/3.516大约大约16个个ASCII字符，或字符，或56比特。比特。唯一唯一解距离不是对密码分析需要多少密文的度量，解距离不是对密码分析需要多少密文的度量，而是对存在唯一合理的密码分析解所需要的密文而是对存在唯一合理的密码分析解所需要的密文数量的指标。数量的指标。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 唯一解距离与多余度成反比，当多余度接近唯一解距离与多余度成反比，当多余度接近于零时（唯一解距离接近无穷大，也就是解密于零时（唯一解距离接近无穷大，也就是解密出唯一有意义的明文所需要的最少密文接近无出唯一有意义的明文所需要的最少密文接近无穷大），即使一个普通的密码体制也可能是不穷大），即使一个普通的密码体制也可能是不可破译的。可破译的。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 3.1.5 信息信息论的运用的运用 很少有实际的算法密码分析上是绝对不可破很少有实际的算法密码分析上是绝对不可破译的。各式各样的特点起着破译已加密信息的译的。各式各样的特点起着破译已加密信息的突破作用。然而，类似于信息论方面的考虑有突破作用。然而，类似于信息论方面的考虑有时是有用的。时是有用的。例如，为了使一个确立的算法增加安全性，例如，为了使一个确立的算法增加安全性，建议一个密钥变化其间隔或周期，以加大唯一建议一个密钥变化其间隔或周期，以加大唯一解距离的值。解距离的值。 返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 3.1.6 混乱和散布混乱和散布（1）混乱）混乱用于掩盖明文和密文之间的关系用于掩盖明文和密文之间的关系。这可以。这可以挫败通过研究密文以获取多余度和统计模式。挫败通过研究密文以获取多余度和统计模式。通过通过代替代替可做到这点。一个简单的代替密码，可做到这点。一个简单的代替密码，如凯撒移位密码，其中每一个确定的明文字符如凯撒移位密码，其中每一个确定的明文字符被一个密文字符代替。现代的代换密码更复杂，被一个密文字符代替。现代的代换密码更复杂，一个长长的明文块被代替成一个不同的密文块，一个长长的明文块被代替成一个不同的密文块，并且代替的机制随明文中的每一比特发生变化。并且代替的机制随明文中的每一比特发生变化。返回本节返回本节13简单字符的加密、解密（凯撒移位）简单字符的加密、解密（凯撒移位）加密的思想是：加密的思想是： 将每个字母将每个字母C C加（或减）一序数加（或减）一序数k k，即用它后的第，即用它后的第k k个字母个字母代替，变换式公式：代替，变换式公式： c=c+kc=c+k 例如序数例如序数k k为为5 5，这时，这时 “A 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-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）散布）散布 通过通过将明文多余度分散到密文中使之分散开来将明文多余度分散到密文中使之分散开来。产生散布最简单的方法是通过产生散布最简单的方法是通过换位换位（也称为置换）（也称为置换）。一个简单的换位密码，如列换位体制，只简单。一个简单的换位密码，如列换位体制，只简单地重新排列明文字符。现代密码也做这种类型转地重新排列明文字符。现代密码也做这种类型转换，但它们也利用其他能将部分消息散布到整个换，但它们也利用其他能将部分消息散布到整个消息的散布类型。消息的散布类型。 返回本节第第3 3章章信息论与数学基础信息论与数学基础 3.2 复复杂性理性理论3.2.1 算法的复杂性算法的复杂性3.2.2 问题的复杂性问题的复杂性3.2.3 NP完全问题完全问题返回本章首页返回本章首页第第3 3章章信息论与数学基础信息论与数学基础 3.2.1 算法的复算法的复杂性性密码体制的强度由破译它所需的计算能力确密码体制的强度由破译它所需的计算能力确定的，所需计算能力越大，密码体制越安全。定的，所需计算能力越大，密码体制越安全。 一个算法的计算复杂性由两个变量来度量：一个算法的计算复杂性由两个变量来度量：（1）T（时间复杂性）。（时间复杂性）。（2）S（空间复杂性或所需存储空间）。（空间复杂性或所需存储空间）。 T和和S一般表示为一般表示为n的函数。的函数。 n是输入的尺寸。是输入的尺寸。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 通常通常，一个算法的计算复杂性的数量级用称之为，一个算法的计算复杂性的数量级用称之为“大大O”的符号来表示的符号来表示。计算复杂性计算复杂性的数量级是这种类型的函数：当的数量级是这种类型的函数：当n变大时，变大时，增长得最快的函数；增长得最快的函数；所有常数和较低阶形式的函数忽所有常数和较低阶形式的函数忽略不计略不计。例如，一个所给的算法的复杂性是。例如，一个所给的算法的复杂性是 4n2+7n+12 ，那么，其计算复杂性是那么，其计算复杂性是 n2 阶的，表示为阶的，表示为O(n2) 。第第3 3章章信息论与数学基础信息论与数学基础 表表3.1 不同算法族运行时间不同算法族运行时间与与n的关系的关系 复杂度复杂度 所需运算所需运算 所需时间（所需时间（106运算运算/秒）秒） 常数常数 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，则强力攻击的复杂性是，则强力攻击的复杂性是O(2n)。对于对于56bit密钥的复杂性是密钥的复杂性是256（2285年）。年）。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 3.2.2 问题的复的复杂性性 复杂性理论，按照解决问题时所需最少的时间及复杂性理论，按照解决问题时所需最少的时间及最小的空间，归纳成不同类别的复杂度问题。最小的空间，归纳成不同类别的复杂度问题。多项式时间多项式时间，在计算复杂度理论中，指的是一个，在计算复杂度理论中，指的是一个问题的计算时间问题的计算时间m(n)不大于问题大小不大于问题大小n的多项式的多项式倍数。（倍数。（O(n)问题。）问题。）-易处理问题易处理问题超多项式时间超多项式时间，表示任何多项式时间的输入数目，表示任何多项式时间的输入数目只要够大，超多项式时间所需的解题时间终究会只要够大，超多项式时间所需的解题时间终究会大大超过任何多项式时间的问题。大大超过任何多项式时间的问题。-难解问题难解问题指数时间指数时间（Exponential time）就是一例。）就是一例。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 3.2.2 问题的复的复杂性性 依照依照求解问题所需的时间，复杂理论也将各种问题求解问题所需的时间，复杂理论也将各种问题区分成下面几类：区分成下面几类：（1）P问题：代表那些能够在问题：代表那些能够在多项式时间多项式时间(与时间复杂度与时间复杂度有关有关)内内可解的问题。可解的问题。（2）NP问题：多项式时间内可问题：多项式时间内可验证（猜出）的验证（猜出）的问题问题。（找不到多项式时间算法解的问题）（找不到多项式时间算法解的问题） （3）NP完全问题：是完全问题：是NP问题中的一些特殊问题，问题中的一些特殊问题，NP中的所有问题都可以转换成中的所有问题都可以转换成NP-完全问题，只要完全问题，只要NP完全问题解决了，其他问题都可以解决完全问题解决了，其他问题都可以解决。是。是NP问题中问题中最困难的问题。最困难的问题。 返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 （4）PSPACE问题：它是较问题：它是较NP复杂度更高一级的问复杂度更高一级的问题，但题，但PSPACENP是否成立仍是没有被解决的问是否成立仍是没有被解决的问题。题。（5）EXPTIME问题：复杂度最高的称为问题：复杂度最高的称为EXPTIME，EXPTIME问题需要指数的时间才能解决。问题需要指数的时间才能解决。EXPTIME已被证明不等于已被证明不等于P。返回本节第第3 3章章信息论与数学基础信息论与数学基础 3.2.3 NP完全完全问题* *例举一些例举一些NP完全问题：完全问题：（1）整数分解问题）整数分解问题任何整数都可以分解成标准形式：任何整数都可以分解成标准形式： m= ，pi是素数是素数，ei N当当m较小时，这个问题不太困难，例如较小时，这个问题不太困难，例如623，1002252。但但当当m较大时，此问题就变得非常困难了。较大时，此问题就变得非常困难了。 返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 （2）背包问题）背包问题 背包背包问题是这样的一个问题：已知长度为问题是这样的一个问题：已知长度为k的圆形背包及长度分别为的圆形背包及长度分别为a1，a2，an的的n个圆形物品。假定这些物品的半径和背包半个圆形物品。假定这些物品的半径和背包半径相同，要求从径相同，要求从n个物品中选出若干个正好装个物品中选出若干个正好装满这个背包满这个背包。第第3 3章章信息论与数学基础信息论与数学基础 把背包问题抽象成数学模型，称为子集合问把背包问题抽象成数学模型，称为子集合问题：设有长度为题：设有长度为n的向量的向量 A=（ a1，a2，an ），任意给定一个正整），任意给定一个正整数数k，寻找有没有一些恰好等于，寻找有没有一些恰好等于k，即求方程：，即求方程：的解向量的解向量 x=(x1，x2，xn）其中）其中xi=0或或1。当当n比较小的时候，可以用穷举法求得解向量，比较小的时候，可以用穷举法求得解向量，但当但当n比较大时，穷举法就不可行了。比较大时，穷举法就不可行了。背包问题是背包问题是NP完全问题。完全问题。第第3 3章章信息论与数学基础信息论与数学基础 （3）离散对数问题）离散对数问题设设x，r，n是正整数，已知是正整数，已知x，r和和n，可以，可以很快地求得很快地求得反过来，如果已知反过来，如果已知y，和和n，求，求r使得：使得：成立，这便是离散对数问题。离散对数问题也成立，这便是离散对数问题。离散对数问题也是是NP完全问题。完全问题。 返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 3.3 数数论 3.3.1 模运算模运算 3.3.2 素数素数 3.3.3 最大公因子最大公因子 3.3.4 取模数求逆元取模数求逆元 3.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章章信息论与数学基础信息论与数学基础 3.3.1 模运算模运算模模运算是这样一个问题，举例来说，如果小运算是这样一个问题，举例来说，如果小刘说她刘说她10:00会回家，而她迟到了会回家，而她迟到了13个小时，个小时，那么她什么时候回家的呢？这就是模那么她什么时候回家的呢？这就是模12运算：运算：(1013)mod 1211另另一种写法是：一种写法是：101311(mod 12)返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 本质上，如果本质上，如果a=b+kn对某一些整数对某一些整数k成立，成立，那么那么ab(mod n)。如果。如果a和和b是正的，且是正的，且a小小于于n，那么可将，那么可将a看作看作b被被n整除后的余数。整除后的余数。 通常，通常，a和和b被被n整除时有相同的余数。有时，整除时有相同的余数。有时，b被叫做被叫做模模n的余数的余数。有时。有时a被叫做与被叫做与b模模n同余。同余。（“”表示同余表示同余）。）。 第第3 3章章信息论与数学基础信息论与数学基础 从从0n-1的整数组成的集合构成了的整数组成的集合构成了模模n的的“完完全剩余集全剩余集”。这意味着，对每一个整数。这意味着，对每一个整数a ，它，它的模的模n的余项是从的余项是从0n-1的某个整数。的某个整数。a模模n的运算给出了的运算给出了a的余数，这样的余数是从的余数，这样的余数是从0n-1的某个整数。这种运算称为的某个整数。这种运算称为模变换模变换。例。例如，如，5 mod 3=2。第第3 3章章信息论与数学基础信息论与数学基础 密码学密码学用了许多模用了许多模n运算，因为像计算离散运算，因为像计算离散对数和平方根这样的问题是困难的，而模运对数和平方根这样的问题是困难的，而模运算可将所有中间结果和最后结果限制在一个算可将所有中间结果和最后结果限制在一个范围内，所以用它进行计算比较容易。范围内，所以用它进行计算比较容易。计算数计算数a的乘方并对其取模：的乘方并对其取模：它它可分成一系列的乘法和除法（取模）。有可分成一系列的乘法和除法（取模）。有方法使它运算得更快。方法使它运算得更快。第第3 3章章信息论与数学基础信息论与数学基础 例如，如果要计算例如，如果要计算，不要，不要运用直接计算运用直接计算的方法进行的方法进行7次乘法和一个大数的模化简运算次乘法和一个大数的模化简运算,相反相反，应进行三次较小的乘法和三次较小的模化，应进行三次较小的乘法和三次较小的模化简简运算运算: 依此类推：依此类推：返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 3.3.2 素数素数素数素数：比：比1大，其因子只有大，其因子只有1和它本身，没有和它本身，没有其他可以整除它。其他可以整除它。2是一个素数，其他素数诸如是一个素数，其他素数诸如73，2 521，2 365 347 734 339，和，和2756 839-1等。等。素数是无限的素数是无限的，密码学常用大的素数（，密码学常用大的素数（512比比特，甚至更长）。特，甚至更长）。 任意整数任意整数a1，都可以唯一的因式分解为素数，都可以唯一的因式分解为素数的乘积。的乘积。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 3.3.3 最大公因子最大公因子两个数互素是指：当它们除了两个数互素是指：当它们除了1之外没有共同的因子之外没有共同的因子；换而言之，如果换而言之，如果a和和n的最大因子等于的最大因子等于1，那么写作：，那么写作： gcd(a，n)=1或写成或写成 (a，n)=1数数15和和28是互素的，是互素的，15和和27不是，而不是，而13和和500是。是。一个素数与它的倍数以外的任何其他数都是互素的。一个素数与它的倍数以外的任何其他数都是互素的。确定一个大数的素因子不是一件容易的事。确定一个大数的素因子不是一件容易的事。如果每个整数都表示成素数乘积的形式，就可以很容如果每个整数都表示成素数乘积的形式，就可以很容易的求出两个正整数的最大公约数。易的求出两个正整数的最大公约数。返回本节返回本节37辗转相除法辗转相除法( (欧几里德算法欧几里德算法) )求两个整数的最大公约数、最小公倍数。求两个整数的最大公约数、最小公倍数。分析：求最大公约数的算法如下：分析：求最大公约数的算法如下： 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 不是素数。不是素数。（5）设）设j = j+1。如果。如果j b且且z = p-1，设，设z = z 2 mod p ，然后回到步骤（，然后回到步骤（4）。）。（6）如果）如果j = b且且z = p-1, 那么那么 p 不是素数。不是素数。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 3.5.3 LEHMANN方法方法另一种更简单的测试是由另一种更简单的测试是由Lehmann独立研独立研究出的。下面是迭代数设置为究出的。下面是迭代数设置为100的这个算法：的这个算法：（1）选择一个待测的随机数。）选择一个待测的随机数。（2）确信不能被任何小素数整除。测试）确信不能被任何小素数整除。测试2，3，5，7和和11将显著地提高这个算法的速度。将显著地提高这个算法的速度。（3）选择）选择100个个1和和n - 1之间的随机数之间的随机数a1，a2，a100。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 （4）对所有的）对所有的ai= a1，a2，a100 ，计算计算ai (n-1)/2： 如果对所有的如果对所有的i, ai (n-1)/2 =1( mod n)，那，那n可可能是合数。能是合数。 如果对任一个如果对任一个i, ai (n-1)/21或或-1( mod n)，那，那么么n是合数。是合数。 如果对所有如果对所有i, ai (n-1)/2=1或或-1( mod n)，但并，但并非对所有非对所有i 均等于均等于1，那么，那么n 是素数。是素数。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 3.5.4 强素数素数许多关于许多关于RSA的文献都建议对于和应该用的文献都建议对于和应该用强素数。这些强素数是满足某些特性的素数。强素数。这些强素数是满足某些特性的素数。使得用某些特殊的因子分解的方式对它们的乘使得用某些特殊的因子分解的方式对它们的乘积进行分解是困难的。某些建议的性质如下：积进行分解是困难的。某些建议的性质如下：p-1和和q-1的最大公因子应该较小。的最大公因子应该较小。p-1和和q-1都应有大的素因子，分别记为都应有大的素因子，分别记为p和和q。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 p-1和和q-1都应有大的素因子，分别记为都应有大的素因子，分别记为p”和和q”。(p-1)/2和和(q-1)/2都应该是素数。都应该是素数。在此仍然推荐使用强素数，即使它们不会在此仍然推荐使用强素数，即使它们不会使因子分解更简单些。虽然它使得产生素数更使因子分解更简单些。虽然它使得产生素数更困难，但它是无害的。困难，但它是无害的。返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 3.6 有限域上的离散有限域上的离散对数数* *1. 离散对数基本定义离散对数基本定义给定一个质数给定一个质数p，和有限域，和有限域Zp上的一个本原上的一个本原元元a，对，对Zp上整数上整数b，寻找唯一的整数，寻找唯一的整数c，使得，使得acb(mod p)。模指数模指数运算运算ax mod n是频繁地用于密码体制是频繁地用于密码体制中的另一种单向函数，它的逆问题是找出一中的另一种单向函数，它的逆问题是找出一个数的离散对数，这是一个困难的问题。个数的离散对数，这是一个困难的问题。返回本章首页返回本章首页第第3 3章章信息论与数学基础信息论与数学基础 2. 举例举例例如求例如求x，使得，使得x满足满足3x mod 17 = 15 。虽然。虽然可以求出可以求出x = 6，但目前没有更简单的求，但目前没有更简单的求离散对离散对数的方法。数的方法。并不是所有的离散对数都有解。可以很容易并不是所有的离散对数都有解。可以很容易发现，下面的方程并没有解：发现，下面的方程并没有解： 3x mod 13 = 7 对对1024比特或更大的数求离散对数非常困难。比特或更大的数求离散对数非常困难。 第第3 3章章信息论与数学基础信息论与数学基础 3. 计算有限群中的离散对数计算有限群中的离散对数密码设计者对下面密码设计者对下面3个主要群上的离散对数个主要群上的离散对数是很感兴趣的：是很感兴趣的：素数域的乘法群素数域的乘法群GF（p）。）。 特征为特征为2的有限域的有限域GF（2n）上的乘法群。）上的乘法群。有限域有限域F上的椭圆曲线群上的椭圆曲线群EC（F）：）：返回本节返回本节第第3 3章章信息论与数学基础信息论与数学基础 思考思考题1一条消息的熵和一个密码体制的熵如何计算，它们与一条消息的熵和一个密码体制的熵如何计算，它们与安全性有什么关系？安全性有什么关系？2什么叫唯一解距离？简述它与多余度的关系。什么叫唯一解距离？简述它与多余度的关系。3简述简述“散布散布”与与“混乱混乱”在密码中的应用。在密码中的应用。4什么是计算复杂性、空间复杂性和问题复杂性？简述什么是计算复杂性、空间复杂性和问题复杂性？简述P问问题、题、NP问题和问题和NP-完全问题之间的关系。完全问题之间的关系。5简述中国剩余定理并说明它的一个实际应用。简述中国剩余定理并说明它的一个实际应用。第第3 3章章信息论与数学基础信息论与数学基础 6对整数对整数15和和18，有以下问题：，有以下问题：（1）它们是否互素？）它们是否互素？（2）试用）试用欧几里德算法欧几里德算法求它们的最大公因子。求它们的最大公因子。（3）是否有解，为什么？）是否有解，为什么？（4）如果有解，请给出两种计算方法。）如果有解，请给出两种计算方法。7验证验证437是一个是一个Blum数。数。8素数的个数是无限还是有限？找素数与求分解因子相比，素数的个数是无限还是有限？找素数与求分解因子相比，哪个难度更大？哪个难度更大？返回本章首页返回本章首页