数论第九章 数论的应用

数论第九章 数论的应用 第九章 数论de应用 在一个很长de时期里，数论被认为是很难有应用价值de。但是，二十世纪中后期，数论de应用，特别是在密码学等学科中de应用，改变了人们de看法，数论de研究也增加了新de内容。在这一章中我们要介绍数论de几个应用。 第一节 计算星期几 要知道几十天以后de某一天是星期几，这是不难de，因为只要计算一下被7除de余数就可以了。但是，如果要知道几十年以后de某一天是星期几，那就比较困难了，因为在这段时间里有闰年，而且，每个月所含de天数也不一样。在这一节，我们要给出一个公式，可以方便地解决这个问题。 按现行de公历历法，每年有365天，若这一年是闰年，则有366天，二月有二十九天。闰年是这样确定de:公元年份数不被100整除但被4整除，或者年份数被400整除。 如果某一年是闰年，这一年de二月比正常年份de二月多一天，这样，从这一年de三月一日开始，星期数都受到这闰月de影响，同时，这一年de一月和二月里de星期数却不受影响。这样，就使得同一年里de计算有些不方便。所以，为了计算方便，我们把三月一日作为计算星期数de基点。 1600年以来，全世界大部分地区使用现行de公历历法。因此，我们考虑一个从1600年起使用de计算星期几de公式。 以下，我们使用记号: N = 100c ， y表示年份，其中0 , y , 99; m表示月份，m = 1表示三月，m = 2表示四月，？ ？，m = 12表示二月; 178 (m)表示第N年m月1日de星期数。 dN 假设d(1)是已知de，我们首先计算d(1)，即第N年3月1日1600N de星期数。我们知道:如果没有闰月，一年有365天，因为 365 , 1 (mod 7)， 所以，每过一个正常年，星期数就增加1;每过一个闰年，星期数就增加2。 以r表示从1600年到N年de闰年数，我们得到 d(1) , d(1) ， N – 1600 ， r (mod 7)。 (1) 1600N 由闰年de确定方法，我们有 100c，y,1600100c，y,1600100c，y,1600r,,， [][][]4100400 yy100c，y ,25c，[],400,c,[]，16，[],44100400 yy100c，y (2) ,[]，24c,[]，[],388。4100400 设c = 4q ， s，0 , s , 3，那么，由于0 , y , 99，100s ， y < 400，所以 y100s，y,0，= 0， [][]100400 因此，由式(2)得到 y400q，100s，y r,[]，24c，[],3884400 y ,[]，24c，q,3884 yc , (3) ,[]，24c，[],38844 d(1),d(1)，N,1600，rN1600 yc ,d(1)，100c，y,1600，[]，24c，[],388160044 179 yc (4) (1)2[][](mod7)。,d,c，y，，160044 为了确定d(1)de数值，我们把一个已知de数据代人式(4)，例1600 如，我们知道1998年3月1日是星期日，即d(1) , 0 (mod 7)，代1998 人式(4)，得到 9819, d(1) , 2,19 ， 98 ，, d(1) ， 4 (mod 7)， 0 ，[][]1600160044 所以d(1) , 3，即1600年de3月1日是星期三。将这个数值代人式1600 (4)，得到 ycd(1) , 3 , 2c ， y ，(mod 7)。 (5) ，[][]N44 现在，我们已经能够计算N年de3月1日是星期几。剩下de问题是如何计算这一年dem月k日是星期几。 我们先计算d(m)，即N年m月1日de星期数。容易知道: N 3 月是31天，所以 d(2) , d(1) ， 3 (mod 7)， NN 4 月是30天，所以 d(3) , d(1) ， 5 (mod 7)， NN 5 月是31天，所以 d(4) , d(1) ， 8 (mod 7)， NN 6 月是30天，所以 d(5) , d(1) ， 10 (mod 7)， NN 7 月是31天，所以 d(6) , d(1) ， 13 (mod 7)， NN 8 月是31天，所以 d(7) , d(1) ， 16 (mod 7)， NN 9 月是30天，所以 d(8) , d(1) ， 18 (mod 7)， NN 10月是31天，所以 d(9) , d(1) ， 21 (mod 7)， NN 11月是30天，所以d(10) , d(1) ， 23 (mod 7)， NN 12月是31天，所以d(11) , d(1) ， 26 (mod 7)， NN 1 月是31天，所以d(12) , d(1) ， 29 (mod 7)。 NN 现在，计算N年m月k日de星期数已经是很容易de事了。但是，我们希望找一个更简单de公式。从上面de数字可以看出，从3月1日到2月1日de11个月中，星期数“增加”了29天，平均每月“增加”2.6天，因此，我们来找一个形如[2.6m , a]de公式，其中m是月份，a是某个适当de数。经过验证，发现函数f(m) = [2.6m , 0.2] , 2满足这些条件: f(1) = 0，f(2) = 3，f(3) = 5，f(4) = 8，？，f(12) = 29。 180 利用这个函数，我们得到N年m月1日de星期数是 (m) , d(1) ， [2.6m , 0.2] , 2 (mod 7)。 dNN 因此，N年m月k日de星期数W(N, m, k)是 W(N, m, k) = d(m) + k , 1 , d(1) ， [2.6m , 0.2] ， k – 3 (mod 7)， NN 由式(5)，得到 ycW(N, m, k) , k , 2c ， y ，， [2.6m , 0.2] (mod 7)。 (6) ，[][]44 利用上式我们就能较容易地计算出任意给定deN年m月k日de星期数de星期数W(N, m, k)了。 例1 问:1976年8月6日是星期几, 解 将N = 1976，c = 19，y = 76，m = 6，k = 6代入式(6)，得到 7619W(1976, 6, 6) , 6 – 38 ， 76 ，， [2.6,6 – 0.2] , 5 (mod 7)， ，[][]44 即1976年8月6日是星期五。 例2 问:1978年2月24日是星期几, 解 将N = 1977，c = 19，y = 77，m = 12，k = 24代入式(6)，得到 7719W(1977,12,24) , 24 – 38 ， 77 ，， [2.6,12 – 0.2] , 5 (mod 7)， ，[][]44 即1978年2月24日是星期五。 注意，由例2我们看到，一月和二月分别是作为上一年de十一月和十二月。 习 题 一 1. 问:1948年2月14日是星期几, 2. 问:1999年10月1日是星期几, 第二节 循环比赛 有N个球队要进行循环赛。我们希望知道:最少需要按排几轮比 181 赛，才能完成循环赛, 我们先来做一些分析。首先，由于是进行循环赛，每个队要和另外de队都比赛过，所以至少要进行N , 1轮比赛。其次，用r表示在每一轮比赛中所进行de比赛场数，则 N,，当N是偶数;,2 r,,N,1,，当N是奇数。2, 如果N是奇数，那么，在每一轮比赛中总有一个队不参加比赛。这时，我们把一个“假想de”球队A加到这N个球队中，就有了N ， 1个球队。现在，在每一轮比赛中对这N ， 1个球队进行按排，并且 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 :凡是被按排和A队比赛de球队，就是没有比赛de球队。这样，N是奇数de情形就可以化为N是偶数de情形，因此，下面我们总假定N 是偶数。 为了叙述方便，我们用1, 2, ？, N表示这N个球队，用x(1 , x , iiN)表示在第i轮比赛中与x队进行比赛de球队。 下面，我们给出一个按排比赛de方法，它说明，用N , 1轮比赛就可以完成循环赛。 按排方法:在第i(1 , i , N , 1)轮比赛中，对于每个球队x我们这样确定与它比赛de球队x: i (?) 当x = N时，取 i,，当i是偶数;,2N, (1) ,i1i，N,,，当i是奇数。2, 显然N , N。 i (?) 当x , N且 i,，当i是偶数;,2x, (2) ,i，N,1,，当i是奇数2, 时，取x满足 i x ， x , i (mod N , 1)，1 , x , N , 1。 (3) i i 182 下面，我们要证明，这样de按排满足要求。 首先，我们指出，在每一轮比赛中，不同球队de比赛对手是不同 , x,(1 , i , N , 1)。 de，即，若x , x,，则xii 我们分三种情况进行讨论。 ) 若x与x,都不等于N，则1 , x, x, , N , 1，于是 (? x , x,0 (mod N , 1)， ,, 由式(3)得到 x ， x , x, + x,，0x , x, , x, , x (mod N , 1)， (4) ,,iiii 因此，x , x,。 ii (?) 若x = N，x, = N，则x = N，x, = N，显然x , x,。 iiiiii (?) 若x = N，但x,不满足式(2)，则x,由式(3)定义，此时，如果i x, = x = N，那么，由式(3)和式(1)，当i是偶数，我们有 iii ii,,i，x,x, ， x, , x, +(mod N , 1); (5) i22 当i是奇数，我们有 i，N,1i，N,1,,i，x,x, ， x, = x, ，(mod N , 1)。 (6) i22 但是，由于对x, de假定，式(5)或式(6)都不能成立。 其次，我们指出，每一个队x在每一轮比赛中de对手不是它自己，即对于1 , i , N , 1，必定x , x。当x = N时，由式(1)可知N , N。当ii1 , x , N , 1，且式(2)满足时，若x = x，则式(3)给出 i 2x , x + x , i (mod N , 1)， i 由此推出x不满足式(2)，这个矛盾说明x , x。 i 最后，我们指出，对于每一个确定de队x，它在每一轮比赛中de对手是不同de，即 x,x，i , i，(1 , i, i , N , 1)。 (7) 1212ii12 (?) 先看球队N。如果 N,N(1 , i, i , N , 1)。 12ii12 由式(1)可知， i ,2N,2N, i (mod N , 1)， 12ii12 因此i = i。 12 (?) 再看球队x，x < N。如果 183 (1 , i, i , N , 1)， x,x,N，则N,N12iiii1212 因此，由上面在(?)中de讨论，可知i = i。如果, N，那么，x,x12ii12由式(3)得到 i ,, i (mod N , 1)， x，x,x，x12ii12 因此i = i。 12 以上讨论说明，用上面de按排方法可以在N , 1轮比赛中完成N个球队de循环赛。 下面，我们举了两个例子说明具体de按排方法。表格中，第k行第m列上de数字就是第k轮中与球队m进行比赛de球队所对应de 数字。如果在这个位置上没有数字，就表示球队m在第k轮比赛中没有赛事。 例1 五个球队进行循环赛de比赛程序: 1 2 3 4 5 1 5 4 2 1 2 5 4 3 2 3 2 1 5 3 4 3 1 5 4 5 4 3 2 1 例2 八个球队进行循环赛de比赛程序: 1 2 3 4 5 6 7 8 1 7 6 5 8 3 2 1 4 2 8 7 6 5 4 3 2 1 3 2 1 7 6 8 4 3 5 4 3 8 1 7 6 5 4 2 5 4 3 2 1 7 8 5 6 6 5 4 8 2 1 7 6 3 7 6 5 4 3 2 1 8 7 184 习 题 二 1. 编一个有十个球队进行循环赛de程序表。 2. 编一个有九个球队进行循环赛de程序表。 第三节 仿射加密方法 在很长de一个历史时期内，数论被认为是一门没有应用价值de“纯”理论学科。事实并非如此。本章以下几节将要介绍数论在信息保密技术中de几个应用。 现实社会中，充满了各种各样de信息，例如，军事情报，商业秘密，金融消息，计算机文件，私人通信等等。在很多情况下，人们希望在秘密de情况下保存或传送信息，这就导致了对信息加密de研究。 对于那些一目了然de信息，我们称为“明文”。当我们要把某个信息传送给某些人(称之为“合法接收人”)时，是先把明文进行“加密”处理，这种经过加密处理de明文，我们称为“密文”。密文不是随便甚麽人都可以看懂de。只有合法接收人，他们掌握了一定de方法，才能把它“翻译”成加密处理之前de明文。总de来说，关于信息加密de研究主要是两个方面:第一，研究把明文翻译成密文de方法，这个方法要尽可能de简单易行;第二，研究这种加密方法de保密性(安全性)，即，除合法接收人外，其他人从密文了解到明文内容(全部或部分)de可能性。 把明文翻译成密文de过程，称为加密过程，或加密;所用de方法(或公式)，称为加密方法(或加密公式)。把密文翻译成明文de过程，称为解密过程，或解密;所用de方法(或公式)，称为解密方法(或解密公式)。 为了能将数论用于明文de加密，首先需要建立明文与正整数de对应关系。一个文件总是由文字和其他符号(标点符号，数字，特殊记号，等等)组成de。如果用汉语拼音 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 写汉字，那么，文件就可以用26个拉丁字母和一些符号来表达。假设所使用de字母和符号共有N个，如果把这些符号和N个正整数0，1，2，？，N , 1建立一一对应de关系，那么，文字、符号、句子和文件就都和正整数建立了一一 185 对应de关系。例如，假设使26个拉丁字母a，b，c，？，y，z与数字00，01，02，？，24，25建立了下表所示de一一对应关系: 表 1 a b c d e f g h i j k l m 00 01 02 03 04 05 06 07 08 09 10 11 12 n o p q r s t u v w x y z 13 14 15 16 17 18 19 20 21 22 23 24 25 那么，与“woyaolai”(我要来)对应de数字就是2214240014110008。 在实际应用中，一个文件所对应de整数是一个很大de数字，所以，人们往往要对大de正整数进行处理，使它们可以与较小de正整数列对应，从而容易进行加密运算。我们知道，对于给定de正整数k，任何正整数P都可以唯一地表示成 nn , 1k ， pk ， ？ ， pk + p，0 , p , k , 1，0 , i , n。 P = pnn , 110i 这样，任何整数P就与整数列{p, p, ？, p}建立了一一对应de关系，nn , 10 对大整数Pde加密就转化为对不超过kde整数p(0 , i , n)de加密。 i 以下几节中，我们总用P表示明文，用E(P)或E表示与P相应de密文。 在这一节，我们主要介绍历史较长久de一类加密方法，即仿射加密方法。用,表示需要加密de所有明文Pde集合，并且假定集合,de上界是A。用仿射加密方法对明文P加密de过程是这样de: (?) 取大正整数M > A，以及正整数a，b，a,，使得 (a, M) = 1，aa, , 1 (mod M)。 (1) (注意:因此，明文P满足0 , P < M。) (?) 加密:对于明文P，计算 E , aP ， b (mod M)，0 , E < M。 (2) E就是与P对应de密文。 (?) 解密:对于密文E，计算 P , a,(E , b) (mod M)，0 , P < M， (3) 00 P就是与E对应de明文P。 0 现在，我们说明式(3)中确定deP就是明文P。事实上，由式(3)，0 式(2)和式(1)，我们得到 186 , a,(E , b) , a,((aP ， b) , b) , aa,P , P (mod M)， P0 由于0 , P < M，0 , P < M，所以，由上式得到P = P。 00 例1 设符号a，b，？，y，z分别与整数0，1，？，24，25对应， 使用仿射加密方法，取M = 26，a = 1，b = 3，a, = 1，对明文P中de每一个符号用这一方法加密: E , P ， 3 (mod 26)。 这就是所谓de“恺撒密码”。在古罗马时代，恺撒大帝在传送军事命令时，把每个英文字母用它后面de第三个字母代替，即按表2de替换方式: 表 2 P a b c d e f g h i j k l m E d e f g h i j k l m n o p P n o p q r s t u v w x y z E q r s t u v w x y z a b c 例如，使用例1中de加密方法，明文“jiudianzhong”(九点钟)被加密成“mlxgldqckrqj”。 以下，为了叙述方便，我们用“,”表示数字与符号de对应关系，例如，“a 00”，“d 03”，等等。又用“”表示明文和密, , , 文de对应关系，例如，“s a”“men phq”，等等。 ,, 例2 已知明文所使用de符号只是26个英文字母a，b，？，y，z，它们分别与整数00，01，？，24，25对应，又知道使用公式 E , P ， b (mod 26)，0 , E < 26 (4) 对每个符号加密。已经知道明文字母e与密文字母u对应，试求出解密方法。 解 将已知dee , u以及e , 04，u , 20代入式(4)，得到 20 , 4 ， b (mod 26)， 所以b , 16 (mod 26)，再由式(4)得到 P , E , 16 , E ， 10 (mod 26)，0 , P < 26， 这就是解密方法，也可以用下表说明: 表 3 187 E a b c d e f g h i j k l m P k l m n o p q r s t u v w E n o p q r s t u v w x y z P x y z a b c d e f g h i j 一般地，对于由式(2)定义de仿射加密方法，只要知道两对(不同 ，E与P，E，就可以求出解密方法。de)相对应de明文和密文P1122 事实上，由式(2)及已知de对应关系，得到 E , aP ， b (mod M)， 11 E , aP ， b (mod M)， (4) 22 所以 E , E , a(P , P) (mod M)。 2121 以 x , a (mod M)，0 , a < M，1 , i , r ii 表示同余方程 x(P , P) , E , E (mod M) 2121 de全部解，并且记 b , E – aP (mod M)，0 , b < M， i1i1i 则a与b(1 , i , r)就可能是式(2)中所使用dea和b。 ii 当(P , P, M) = 1时，这样dea与b只有一组，当(P , P, M) > 121ii21时，为了确定出正确dea与b，首先，利用(a，M) = 1删去某些a与ib，其次，用它们验证式(4)是否成立，并用它们试译部分密文，就i 可以确定正确dea与b。将确定dea，b代入式(3)，就得到解密公式。 在现实生活中，无论使用什么语言符号传送信息，各个符号de出现频率总是有差别de。例如，有统计数字表明，在报刊文章中，英语de26个字母中，出现频率较高de，依次是e，t，a，o等;较低de，依次是z，q，j，x等。这样，在对密文中de每个字母de出现频率进行统计之后，可以对于明文字母和密文字母之间de对应关系作出猜测，然后试行解密。 例3 已知明文由26个英文字母a，b，？，y，z(分别与00，01，？，24，25对应)及符号“～”和“,”(分别与26和27对应)组成，用这28个符号写成de正常英文中，出现频率最高de依次是～，e与t。在对一组密文做了统计分析之后，发现密文中出现频率最高de三个符188 号依次是b，?与i，试求解密公式。 解 设解密公式为 ,E ， b, (mod 28)，0 , P < 28， P , a 则由已知de符号与数字de对应关系，比较出现频率de高低，可以假 !”与“e”分别对应着“b”与“?”，于是 定“ 26 , a,,1 ， b, (mod 28)， 4 , a,,27 ， b, (mod 28)， 将两式相减，得到 26a,, ,22 (mod 28)。 这个同余方程有两个解:a, , 11 (mod 28)，a, , 25 (mod 28)，相应de，12 b, , 15 (mod 28)，b, , 1 (mod 28)。 12 这样，得到了两个可能de解密方法: (?) P , 11E ， 15 (mod 28)，0 , P < 28， (?) P , 25E ， 1 (mod 28)，0 , P < 28。 再通过比较出现频率，又可假定i与t对应(它们对应de数字分别是8与19)，将这两个数字分别代入(?)与(?)进行验证，可知解密方法(?)是正确de。 习 题 三 1. 利用例1中de加密方法，将“ICOMETODAY”加密。 2. 已知字母a，b，？，y，z，它们分别与整数00，01，？，24，25对应，又已知明文h与p分别与密文e与g对应，试求出密解公式: P , a,E ， b, (mod 26)， 并破译下面de密文:“IRQXREFRXLGXEPQVEP”。 第四节 RSA加密方法 对信息进行加密de目de，当然是希望这个信息de内容不被某一部分人(以后，我们称他们为“敌方”)了解;同时，这个信息de内容应该能够被另一部分人(以后，我们称他们为“友方”)很容易地了 189 解。上一节所介绍de仿射加密方法具有计算方便de优点，其中，参数a和b是两个关键de数据。我们已经看到，利用统计de方法，能够很容易地确定这两个数据，此外，为了提高保密性，即增加敌方从密文得到密文de困难程度，需要经常更换a和bde数值，于是，就要随时把这些数值及时通知友方，这就增加了敌方获取 a和bde数值de可能性。因此，仿射加密方法de保密性(安全性)是不好de。在这一节，我们介绍一种加密方法，在很大程度上克服了上述缺点。 从实用de观点来看，保密是有时间性de。如果加密后de文件在一个足够长de时间内不被敌方了解，就可以认为这个加密是安全de。当我们谈论“把某一份文件加密，使它不被敌方了解”de时候，其实是包含着一个时间界限de。就是说，这里指de是，在某一个时期内，加密后de文件不被敌方了解。例如，一个发动某次战役de具体时间，在战役开始之前是绝对要保密de，但是，战役结束之后，就不存在保密de必要了。 用P和E分别表示明文和密文，从数学de观点来看文件加密de问题，加密方法和解密方法其实就是两个满足下述条件de函数f(P)和g(E): (?) 对于某个整数集合中de数 P，有确定de函数值E = f(P)与之对应，同时，计算f(P)是容易de: (?) 对于某个整数集合中de数E，有确定de函数值P = g(E)与之对应，同时，计算g(E)是困难de; (?) 如果掌握了关于函数g(E)de某种条件(信息)，计算g(E)是容易de。 在这一节，我们要介绍满足上述三个条件de一个加密方法，它以下面de命题为基础。 命题 已知两个素数，计算它们dede乘积是容易de;但是，已知两个大素数de乘积，求这两个素数却是非常困难de。 从这一个命题出发，R. L. Rivest与A. Shamir，L. M. Adleman提出了下面de加密方法。 RSA加密方法 ? 参数de选取 随机地选取大素数p，q，计算 ,(n) = (p , 1)(q , 1)， n = pq， 190 ,(n)) = 1，并计算d，使得 再随机地取正整数e，(e, ed , 1 (mod ,(n))。 (1) 公开n，e，供加密使用(称它们为RSA加密钥);将p，q，,(n)和d保密(称它们为保密钥)。 加密 ? 设明文是P，0 , P < n，则与之相应de密文是 eE , P (mod n)， 0 , E < n。 (2) ? 解密 已知密文E时，明文P由下式确定: dP , E (mod n)， 0 , P < n。 (3) 我们将以上 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 deRSA加密方法简记为RSA(n, e)。 下面de定理给出了解密方法de依据。 定理1 设n = pp？p是k个不同de素数之积，e与d是正整数，12k (e, ,(n)) = 1，并且式(1)成立，则对于任意dea,N，有 eda , a (mod n)。 证明 对于任意dep(1 , i , k)， 若(a, p) = 1，则由Euler定理ii 可知 p,1i, 1 (mod p)。 ai 由式(1)，ed = r,(n) ， 1 = r (p , 1) ？ (p , 1) ， 1，其中r是非负整数，1k 所以， eda , a (mod p)，i = 1, 2, ？, k。 (4) i 当(a, p) > 1时，这个同余式当然也成立。由于p, p, ？, p是互不相同i12kde素数，由式(4)及同余式de性质即可证得定理。证毕。 一般来说，从密文求明文，有许多可能de方法，例如: (?) 将n分解因数，求出p和q， 使得n = pq，然后计算,(n) = (p , 1)(q , 1)，利用辗转相除法求出d，使得式(1)成立。再利用式(3)从密文E计算明文P。容易看出，用这种方法从密文求出明文de难度，就是将大整数分解因数de难度。 (?) 如果能用某种方法(不是先将n分解因数)求出,(n)，则也可以从密文E求出明文P。因为，利用辗转相除法，由e可以求出d使得式(1)成立，于是，由式(3)可以从密文E计算明文P。但是，如果,(n) = (p , 1)(q , 1)是已知de，那么，有pq = n以及 191 ,(n) ， 1 = n , ,(n) ， 1。 p ， q = pq , 由此，可以利用一元二次方程de求解公式求出p和q。这说明，这种方法de难度不会低于将大整数分解因数de难度。 除此之外，还有一些别de方法。对于这些方法de分析，有兴趣de读者可以查阅关于密码学de文献。总de来说，RSA加密方法被认为有较好de安全性。 RSA加密方法de特点，在于加密方法是公开de，而且加密时所使用de参数也是公开de。这是它与仿射加密方法de重要区别。 通常，称具有这种特点de加密方法为公钥加密方法。公钥加密方法使得信息de加密传送更为方便。例如，每个单位或个人可以像公布电话号码一样公布自己deRSA加密钥。于是，凡是要向它或他发送加密信息de单位或个人都可以使用这些参数发送加密信息。此外，RSA加密方法还有更广泛de用途。下面介绍de数字签名de方法就是一个例子。 数字签名 在社会生活中，在处理具体事件时，常需要当事人进行签证(签名)，以保证他做出de许诺或送出de信息de可靠性与合法性。例如，在签署文件时，由当事人签名，盖章，签署日期以及重要de特殊记号，常是不可少de环节。这样de签证，应该满足一定de要求。 假设A签证一个文件给B，那么， (?) B应该能够确定这是否Ade签证; (?) 任何其他人，无法伪造Ade签证，即A有其独特de签证方式; ) 有一个仲裁签证是否由A发出de方法，例如，当A否认这(? 个签证时，这样de方法可以鉴定签证de真伪。 下面我们说明，RSA加密方法可以用来进行签证，不需要当事人到场，只需传送必要de信息。 假设要签证de信息是M(例如，它是签证人de姓名，签证日期，特定de标志，等等)，并且，已经根据信息M所使用de符号将它与一个正整数对应。为方便计，我们就同时用M表示签证以及它所对应de正整数。 设A要将签证信息M传送给B。又设向 A和B传送信息时使用deRSA加密方法分别是RSA(n, e)和RSA(n, e)，设A和Bde保密钥AABB 分别是d，p，q，和d，p，q。 AAABBB 192 。 在第一节中我们已经谈到，不妨假定M < nA A要将签证信息M传送给B时，首先计算 dAE ,(mod n)，0 , E < n。 (5) M1A1A 同样地，不妨假定E < n。再计算 1B eBE ,(mod n)，0 , E < n。 (6) EBB 1 然后，A将E传送给B。n和e是公开de，而d却只有A知道，所BBA 以，其他人是无法依照上述 步骤 新产品开发流程的步骤课题研究的五个步骤成本核算步骤微型课题研究步骤数控铣床操作步骤 进行伪造de。 B收到信息E后，计算 dBM ,(mod n)，0 , M < n， (7) E1B1B eAM ,(mod n)，0 , M < n， (8) M0A0A 1 并且进行验证是否M = M。事实上，由定理1以及式(5)，式(6)，式(7)0 和式(8)，应该有 eddBBBM ,(mod n)， M = E， E,E,E1B1111eeedAAAAM ,(mod n)，M = M。 M,E,M,M0A011 对B来说，上述验证过程是容易de，因为他知道d 。 B 显然，任何第三者都可以按照式(7)和式(8)鉴定收到de信息是否Ade签证。这样，此处所提供de数字签名方法是满足上面de三个要求de。 做为本节de结尾，我们指出，RSA加密方法de基础是命题“将大整数分解成素因数乘积在计算上是困难de”。此处所谓“计算上困难”与素因数de大小以及人们de计算能力是有关de。如果限定素因数de大小，那么，当人们de计算能力达到一定水平de时候，这个命题就不成立了，那时，RSA加密方法也就不再是安全de了。 习 题 四 1. 设一RSAde公开加密钥为n = 943，e = 9，试将明文P = 100加密成密文E。 2. 设RSA(n, e) = RSA(33, 3)，RSA(n, e) = RSA(35, 5)，AdeAABB 签证信息为M = 3，试说明A向B发送签证Mde传送和认证过程。 193 第五节 孙子定理de应用 本节要介绍孙子定理在信息加密中de两个应用。 一、文件集合de加密 假设A是由n个文件F, F, ？, F组成de集合，它们分别属于n12n 个单位(例如，n个个人，公司，工厂，等等)。又设按某种方法使这 n个文件与n个整数对应。为简便计，我们仍用F, F, ？, F表示每个12n文件所对应de整数。 下面叙述一种对集合Ade加密方法，满足这样de要求:每个单位 可以很方便地查阅集合A中属于自己de文件，却很难查阅集合A中不 属于自己de文件。 设正整数m, m, ？, m满足条件 12n m > F(1 , i , n)，(m, m) = 1(i , j，1 , i，j , n)， iiij 记 MM = mm？m，M =(1 , i , n)。 (1) 12nimi 又设M,(1 , i , n)由下面de同余式确定: i MM, , 1 (mod m)，1 , M, , m。 (2) i iii MM, (mod M)，0 , ,M-1。 e,ei iii 将集合A按下面de方式进行加密: n E = E(A) ,eF(mod M)，1 , E , M。 (3) ,iii,1 若要从密文E求出F，可利用同余式 in F , E ,eF (mod m)，0 , F < m。 (4) iiii,iii,1 在上面所用de加密方法中，数据m，M以及M,(1 , i , n)都iii是保密de。显然， (?) 只有掌握m，才能利用式(4)由E得到F; ii (?) 在掌握mde情况下，可以求出F，也可以对它进行修改。ii 194 例如，修改成F,，并且，在修改之后，还可以重新对由F, ？, F, F,, i1i ,1iF, ？, F组成de新集合A,进行加密; i + 1n (?) 无论求出F或者对F进行修改，都对其他文件F(j , i)iij没有影响。 例1 设某数据库含四段文字:F = 7，F = 9，F = 12，F = 15，1234取 m = 11，m = 13，m = 17，m = 19， 1234 则 M = 11,13,17,19 = 46189， M = 13,17,19 = 4199，M = 11,17,19 = 3553， 12 M = 11,13,19 = 2717，M = 11,13,17 = 2431， 34 M, = 7，M, = 10，M, = 11，M, = 18, 1234 e=4199,7, e=3553,10, e=2717,11, e=2431,18。 1234 对集合{7, 9, 12, 15}加密，得到 n E = E(A) , eF,ii,1i = 4199,7,7 + 3553,10,9 +2717,11,12 + 2431,18,15 , 16298 (mod 46189)， 即E = 16298。 若要求出F，则由 2 F , 16298 , 9 (mod 13) 2 得到F = 9。若要将F改变成10，并且将新de数据库加密，则使用22 上面de方法，对{7, 10, 12, 15}加密，得到 E, , 4199,7,7 + 3553,10,10 + 2717,11,12 + 2431,18,15 , 5639 (mod 46189) 即E, = 5639。 二、秘密共享 假定有一个文件M与r个人有关。为了共同de利益，他们约定，只有当他们中de至少s(s , r)个人同意时，才可以把M公开。这样，就需要一种满足下述条件de加密方法: (?) r个人各掌握一个与这个加密方法有关de数据; (?) 利用s个不同de数据可以很容易地求出M; 195 (?) 如果知道de数据少于s个，那么求出M是很难de。 现在，我们来提出一个满足这些条件de加密方法。 , m, ？, m，使得 选取素数p > M，又选取两两互素de正整数m12r m < m < ？ < m，pmm？m， |,12r 12r mm？m , pmm？m。 (5) rr , 1r , s + 212s 又随机地选取正整数t，使得 mmm？12st ,,1。 (6) p 我们这样来计算第i(i = 1, 2, ？, r)个人所要掌握de数据: E , M + tp (mod m)，0?E M以及式(6)，有 M + tp < (t ， 1)p , mm？m ,， (8) mm？m12siii12l因此，必是x = M ， tp，即M = x , tp。 00 条件(?):如果仅仅知道，l , s , 1，则确定M是很E,E,？,Eiii12l 困难de。 事实上，由孙子定理，方程组 x ,E(modm)，1 , k , l (9) iikk 对模mm？m有唯一解x，0 , x < mm？m。因为m,m,？,m00iiiiiiiii12l12l12l是两两互素de，由Ede定义，显然 i x , M ， tp (mod mm？m)。 (10) 0iii12l 即 mm？mM ， tp , x = ,， (11) 0iii12l 其中,是整数。要确定Mde值，必须确定,de数值。我们要说明，确定196 ,de数值是困难de。事实上，由式(11)，得到 Mtpx，,00 , , ,。 (12) mm？miii12l 另一方面，由式(5)式(6)和l , s , 1，以及 0 , x << mm？m mm？m0rr , 1r , s + 2iii12l 得到 Mtpx，,Mtp，0, 1。 ,mm？mmm？miiirr,1r,s，212l 由式(8)我们见到，M ， tpde取值范围是从1到mm？m，因此，利12s Mtpx，,0用式(5)可知，de取值范围是从1到p , 1，于是，由式(12)，mm？miii12l ,de取值范围是从0到p , 1，当p很大de时候，确定,de数值显然是困难de， 例2 设由三方共同管理de一份文件是M = 5。取p = 7，m = 11，1m = 12，m = 17，则11,12 > 7,17。 23 11取t = 14 <，分配给三方de数据分别是 mm,1,,11,12,112p7 E , 5 + 14,7 , 4 (mod 11)，E = 4; 11 E , 5 + 14,7 , 7 (mod 12)，E = 7; 22 = 1。 E , 5 + 14,7 , 1 (mod 17)，E33 由E，E与E中de任意两个都可以确定出M。例如，假设已知123 E = 4和E = 7，则利用孙子定理，得到方程组 12 x , 4 (mod 11)，x , 7 (mod 12) de解x , 103 (mod 11,13)，于是 0 M = x , tp = 103 , 14,7 = 5。 0 习 题 五 1. 设某数据库由四个文件组成:F = 4，F = 6，F = 10，F = 13。1234试设计一个对该数据库加密de方法，但要能取出个别deF(1 , i , 4)，i 197 同时不影响其他文件de保密。 2. 利用本节中de秘密共享 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，设计一个由三方共管文件M = 3de方法，要求:只要有两方提供他们所掌握de数据，就可以求出文件M，但是，仅由任何一方de数据，不能求出文件M。(提示:取p = = 8，m = 9，m = 11) 5，m123 第六节 背包型加密方法 假设a, a, ？, a是正整数，对于给定de整数b，方程 12n x ， ？ ， ax = b (1) ax ， a1122nn 是否有0,1解，即解(x, x, ？, x)，x = 0或1(1 , i , n),这就是“背12ni 包问题”。一般地，求解背包问题是计算上困难de。但是，对于某些特殊dea, a, ？, a，背包问题是容易解决de。例如，若a, a, ？, a12n12n满足条件 a >a ， a ， ？ ， a，2 , i , n ， (2) i12i , 1 则解方程(1)可以按以下步骤进行: (?) 比较b与a，若a > b，则x = 0;否则，x = 1; nnnn (?) 若x, x, ？, x已经确定，则由方程 nn , 1k + 1 ax ， ax ， ？ ， ax = b , (ax ， ？ ， ax) 1122kknnk + 1k + 1及步骤(?)确定x。 k (?) 重复步骤(?)与(?)，直到求出所有dex(1 , i , n):或者，i 断定方程(1)没有0,1解。 定义1 若a, a, ？, a都是正整数，则称向量(a, a, ？, a)是背12n12n包向量。称满足条件(2)de背包向量为超增背包向量，或超增向量。 如上所述，一般地，求解背包问题是计算上困难de。但是，对于某些特殊de背包向量(例如，超增背包向量)，求解背包问题并不困难。求解一般de背包问题与特殊de背包问题在计算困难程度上de差别，是设计背包型加密方法de基础。1978年，R. C. Merkel与M. E. Hellman提出了一个加密方法，是以求解背包问题de计算困难性为基础de，这个方法，称为MH加密方法。 MH加密方法de设计 198 ? 参数de选取 , a, ？, 随机地选取正整数M，k，(M, k) = 1，以及超增背包向量(a12 a)，使得 n a ， a ， ？ ， a < M; (3) 12n 计算 b , ka (mod M)，1 , b < M，1 , i , n (4) iii ,1以及正整数k，使得 ,1kk , 1 (mod M )。 (5) ,1将背包向量(b, b, ？, b)公开, 称为加密钥。正整数M，k，k则保密。 12n ? 明文de加密 设明文de二进制表示是P = (pp？p)，则与P对应de密文是 12n2 E = bp ， bp ， ？ ， bp。 (6) 1122nn ? 解密 (?) 计算 ,1E , kE (mod M)，0 , E < M。 (7) 00 (?) 由 E = ap ， ap ， ？ ， ap (8) 01122nn求出p, p, ？, p。 12n 注1:一般地，用MH(b, b, ？, b)表示上面所定义de加密方法。 12n 注2:我们来说明由式(8)所确定de(pp？p)就是明文P。事实上，12n2由式(6)和式(5)，有 ,1 ,1 kE = k(bp ， bp ， ？ ， bp) 1122nn ,1 , kk(ap ， ap ， ？ ， ap) 1122nn , ap ， ap ， ？ ， ap (mod M)。 1122nn由式(3)，得到 0 , ap ， ap ， ？ ， ap , a ， a ， ？ ， a < M。 1122nn12n所以，由上式和式(7)，可知E = ap ， ap ， ？ ， ap。因此，由式(8)01122nn得到dep, p, ？, p就是明文Pde二进制表示de位数码。 12n 例1 利用超增背包向量(2, 3, 6, 12, 24, 48)设计一个背包型加密 方法，将明文P = 47加密。 ,1解 取M = 99，k = 5，k = 20，计算 b , 5,2 = 10 (mod 99)， 1 199 = 10。同样de，计算 取b1 b , 5,3 = 15 (mod 99)，取b = 15， 22 b , 5,6 = 30 (mod 99)，取b = 30， 33 b , 5,12 = 60 (mod 99)，取b = 60， 44 b , 5,24 , 21 (mod 99)，取b = 21， 55 b , 5,48 , 42 (mod 99)，取b = 42。 66 对外公开de加密向量是(10, 15, 30, 60, 21, 42)。 由于P = 47 = (101111)，所以与P对应de密文是 2 E = 10,1 + 15,0 + 30,1 + 60,1 + 21,1 + 42,1 = 163。 若要从密文163得到明文P，计算 ,1kE = 20,163 = 3260 , 92 (mod 99)， 解方程 92 = 2p ， 3p ， 6p ， 12p ， 24p ， 48p， 123456 其中p = 0或1，i = 1, 2, 3, 4, 5, 6，得到p = 1，p = 0，p = 1，p = 1，i1234p = 1，p = 1，即明文是P = (101111) = 47。 562 在加密一个文件时，自然希望有很好de保密性。于是，出现了这样一个问题:把加密过de密文再加密一次是否能会提高保密性, 事实并非总是如此。为了说明这一点，我们来看一下用MH方法两次施行加密de情况。 迭代MH加密方法de设计 ? 参数de选取 随机地选取超增向量(a, a, ？, a)，正整数M，k，(M, k) = 1，12n1111使得a ， a ， ？ ， a < M，计算 12n1 c , ka (mod M)，1 , c < M，1 , i , n; i1i1i1 再随机地选取正整数M，k，(M, k) = 1，使得c ， c ， ？ ， c < M，222212n2计算 b , kc (mod M)，1 , b < M，1 , i , n。 i2i2i2 将(b, b, ？, b)公开，作为加密钥。 12n,1,1将(a, a, ？, a)，k，k，M，M以及由下式确定dek与k12n121212保密: ,1k k , 1 (mod M )， i = 1, 2。 iii ? 加密 仍使用式(6)。 ? 解密 由密文E，首先计算 200 ,1, , kE (mod M)，0 , E, < M; E02202 再计算 ,1E , kE, (mod M)，0 , E < M， 010201 再由式(8)求出明文P。 粗看起来，迭代MH加密方法应该具有更好de保密性。其实不然。下面就是一个例子。 例2 给定超增背包向量(5, 10, 20)，以及M = 47，k = 17，M 112= 89，k = 3，由 2 c , 17a (mod 47)，1 , i , 3，0 , c , 46 iii 得到(c, c, c) = (38, 29, 11)，再由 123 b , 3c (mod 89)，1 , i , 3，0 , b , 88 iii 得到(b, b, b) = (25, 87, 33)，这就是要公开de加密钥。这显然是一个123 超增背包向量，因此，用它所得到de密文很容易被解密。 习 题 六 1. 设明文Pde二进制表示是P = (pppppppp)，与P对应123456782de密文是E是E = ap ， ap ， ？ ， ap，如果这里de超增背包向量(a, 1122881a, a, a, a, a, a, a) = (5, 17, 43, 71, 144, 293, 626, 1280)，并且已知密2345678 文E = 1999，求明文P。 2. 给定超增背包向量(2, 3, 7, 13, 29, 59)，试设计一个背包型加密方法，将明文P = 51加密。(提示:取M = 118，k = 77)。 201