信息安全与密码

专题八、信息安全与密码数论在信息安全与密码学中有重要的应用.在历史上早就将密码作为军事斗争和政治斗,一、通讯安全中的基本概念1．明文、密文、密钥密形式再发送.我们把原信息称为明文,明文的秘密形式称为密文.将明文变为密文的过程称为加密.通过已知密码将密文译为明文的过程称为解密.密码中的关键信息称为密钥.密钥在.一套组成基本密码的通讯方法或程序的规则。称为通2）密码的外部形式和内部构成可以有着千差万别，但总括起来只有两种基本形式（1）位移式。即只（2置换式。即用其他字母代替明文中的字母而顺序保持不变。有时也可以同时使用这两种密码系统来构成一套密码系统。20世纪40二、传统的密码系统下面我们介绍在历史上曾经用过的密码系统.位移式密码位移式即只重新排列或调整明文中的字母顺序，而不改变字母本身的密码系统。例1.明文goodmorning→密文mgoorondgin明文中第1,5）个字母为密文中第2（3，4）个字母，依此类推。置换密码所谓置换密码,就是将明文中的每一个字母或数字换为另一个字母或数字,明文经代换后即构成密文.代换规则(即密钥)可以是系统的,也可以是随机的.例如,在公元前高卢战争期间,罗马大将恺撒就使用了一种系统置换的密码,置换的密钥(规律)为:按英文26,,替.A←D,B←E,C←F,……，X←A，Y←B，Z←C。例2:明文：good morning,则在上述密码下，密文为pruqlqj。如果不知密码则窃收到密文也不知所云。根据数论中的同余理论，我们可以解释恺撒密码。将26个字母按顺序依次编号为：A=01，B=02，C=03，……，Y=25。Z=26。设p表示明文中的字母编号，s表示密文中的字母编号，则恺撒密码就可以用同余式表示：s≡p+3（mod26）同余式中的数字3即密钥，它是解密的关键。只要知道了此密钥，则只要通过解同余式p≡s-3≡s+23（mod26）就容易由密文s得出明文p(单个字母)。置换密码的一般形式可以用同余式s≡p+k（mod26）表示。有时为了迷惑企图破译的一方，通常将密文分为五个字母一组的形式。如例2可改写为irrgpruqlqj。这种置换密码或它的变种在第二次世界大战之前使用了很长一段时期,但是它有严重缺点.它的加密原理是把26故名置换密码体制),明文中所有出现的字母a，在密文中均换成字母（计算机）就可以破译这种置换密码。破译置换密码的关键在于确定数字k的值()。破译）穷举法。即对k的可能值逐一进行尝试（关于模nk的值有n种2面语言中，各个字母使用的频率不同，例如e13.04％,其次是t,a,o,I,n,h,r,而字母ｖ,ｋ,ｊ,ｘ,ｑ,ｚ,使之对应于e,去尝试求解，把密文中出现最少的字母分别用ｖ,ｋ,ｊ,ｘ,ｑ,ｚ去进行尝试性求解，再考虑英文词组出现的频率并联系上下文，运用统计分析方法破译置换密码，已不是十分困难的事情。仿射变换密码仿射变换密码是比置换密码更复杂的一种密码，它将明文p变为密文s的变换由同余式s≡apb（mod26） （1）确定。其中（a，26）=1。因为小于26并且与26互素的正整数有12个，按模26同余，b26种可供选择，所以由12×26=312换密码要复杂，从而破译它也就更困难。在仿射密码中，密码的收发双方均使用同一把密钥。发送者用这把密钥加密，接受者也用它解密。26=2×132626互素的正整数有26(112

1)=12个。13序列加密密码第二次世界大战以后,密码体制发生了巨大的变化.由于电子通讯和计算机的发展,信息,它把26个英文字母和63232个五位数。字字ABCDEFGHIJK母编码1100010011011101001010000101100101100101011001101011110字母LMNOPQRSTUV编码0100100111001100001101101111010101010100000011110001111字母WXYZ—/@▼？，编码11001101111010110001001000100000010110110000011111还有一种传统的密码编译法，称为序列加密密码体制。即密文=明文+约定数。例如，我们设明文用0、1得到密文。例3.googoo”被编成一个长为20的二元序列（明文，设约定数（密钥）15的序列0001001101011112的加法得到密文的过程如下：明文0 1 0 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0+)约定数0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0密文0 1 0 0 1 0 1 1 1 0 0 1 1 0 0 1 0 0 0 0就成为+约定数，按模2的加法（即1+1=0，1+0=0+1=1，0+0=0）得到。这个约定数即密钥。用同余式表示即为：密文(数(数)+(mod2)（由于模2加密又可解密，即明文(数)≡密文(数)+约定数。(mod2)这个约定数（周期数列）应是伪随机数列。它可以按某种规则随机改变，使得破译更加困难。在二战期间，德国人用这种方法编译密码，数学家图灵利用数学原理，发明了一种破屡重创敌人。三、现代密码系统，RSA密码体制对编码体制的思考如何设计编码（即加密）接受者处（可能远隔千里，关键在于这种隐藏着的规则应埋的足够深，以防被敌人发现。所有现代密码体制都要使用计算机，一般都假定敌人拥有强大的计算机来分析你的信（或专门设计的计算机；后者（钥匙）通常是一个秘密选定的数。加密程序将依赖这把选定的钥匙要保密。标准DES（DataEncryptionStandard）就是这种体制，它的钥匙是一个数，其二进制表示有565601DES256虽然没有人对DES体制是如何工作的加以保密，从理论上讲，任何人只要试遍了所有可能的钥匙，就能找到哪把钥匙在起作用，但数256如此之大，以至于想试遍所有的钥匙实际上虽然目前广泛使用着DES，但该体制存在明显的缺陷：在使用前，发送者和使用者必须商定好他们要使用的密钥，因为不愿通过任何通讯渠道传送密钥（安全因素，所以他们必须见面并选定钥匙（或雇用一个可靠的信使来传送密钥往往需要把保密信息发送到世界各地的未曾见过面的人。密码体制的新方向1975年,美国的两位密码专家迪菲和M.赫尔曼(M.E.Hellman)在一篇重要的NewDirectionsCrytograph（密码术的新方向）（好象一把锁要用一把钥匙把它锁上，用另一把钥匙才能把它打开。的标准程序（或专用计算机，然后他再选定两把钥匙，一把是他的解密钥匙，他应严格保RSA省理工学院R.(R.Rivest),A.(A.Shamir)和阿德勒曼(L.Adleman)现以他们姓氏的首字字母命名为RSA体制.钥体制提出后，人们怀着极大兴趣纷纷提出各种具体实现方案,接着也有许多人试图攻破这些方案，虽然有许多方案被攻破了，但是RSA.RSARSA体制所用的原理是数论中同余式的欧拉定理和大数分解非常困难这一事实。如何判定一个正整数是否为素数，以及如何将一个正整数分解成素数乘积,是数论中古老的数学问题。第一个问题要比第二个问题问题容易。根据目前的算法和计算机的能力,判100302008分钟但是对大100200(10-6秒),2003.8×109年，即用每秒1038亿年，即使把计算机的速度提高万倍，工作40万年也是难以想象的。有时，即使已知n2101-1(是31)是两个不同素数的乘积，而且已知其中一个比较小的素因子至少有11我们已经知道191的最小素因子为p=5219451是585但至今还不,200n,n没有比较小的素因子，要分解nRSA公开密钥体制就是建立在这个事实基础上的。(是数论中的重要定理，它是RSA(学)理论基础。我们仅给出这两个定理的结论，其证明在一般数论著作中都可查到。定理（欧拉定理）设m是大于1（）=1，则a(m)1 （mod其中(m)为欧拉函数。定理2（费马小定理）对任意正整数a和任意素数p，有apa （mod（2）RSA体制的数学原理取两个不同的素数100，则(n)=(p-1)(q-1)，这里(n)n就不能算出(n)再取两个正整数d，满足ed≡1 （mod(n)）即ed-1=m(nm是正整数，也即e和d均与(n互素（也包含了q-1）=（d，p-1）=（d，q-1）=1）则有如下定理：3对每个整数aeda （mod证明：因为n=pq,p,q均为素故（a，n）只可能为1,p,q,n,下面分类讨1)若(a,n)=1,由欧拉定理知a(n)1 (mod因此aeda1m(n)a(a(n))ma1=a (modn)2)若(a,n)=p或p|a,q|a,则由(a,q)=1(或费马小定理)得a(q)aq11(modq),故a(n)a(q1)(p1)(aq1)p11 (modq)从而另一方面，因p|a,显然有

aeda1m(n)a(a(n))ma1=a (modq)aeda (modp)所以由n=pq，(p,q)=1及同余式性质即得aeda （mod3若(a,n)=n显然有aed0a mod。证毕。RSA利用上述性质设计的公开密钥体制，其工作原理如下。假设某公司在各地的分公司Ｘ1,Ｘ2,…，互相进行保密通讯。整个公司都选取公共的正n=pq，其中pq100位的不同素数。公司将n公开，但是n的分解n=pq中的p和ｑi选取两个正整数i和d，满足1（mod(n)，Ｘieidi保密，eiXiXi的解密密钥，各分公司间把要传送的信息表达成0到n-1（例如6可以表示为11。如果要向分公司Xi发送的明文信息为a（0≤a≤n-1）,则根据Xi公开的的加密密钥ei将明文a加密为密文的加密方法为：把a变成ae关于模n的最小非负剩余（[ae]，i iｎ这个加密运算记为Ei，即iE(a)=[ae]≡aeiiｎ i

(modn)iiｎXi收到发给他的加密信息b=[ae]b解密（还原）成明文的解密方法为：把bbdn[bd]，Xiiｎi i ｎ这个解密运算记为Di，即ｎDi(b)=[bdi]≡bdiｎ

(modn)3a(0≤a≤n-1),先用加密运算Ei再用解密运算Di之后必然恢a:DiEi(a)=aI.

DE(a)=D([ae])≡aedii iｎ ii DiEi=I

≡a (modn)所有的分公司Xi都把自己的加密密钥ei公开，这些加密密钥可以像公共电话本一样收集成册供各分公司查阅，任何人都可以查阅，就像打电话查对方的电话号码一样方便。现在我们设分公司X1要向分公司X2发送信息ａX1先在公开的密码本上查到X2的加密密钥为e2,则知道X2的加密运算E2X1就把要发送给X2明文)a(0≤a≤n-1)加密成密文E2(a)(=[ae2]n),然后把E2(a)发至X2,X2收到E2(a)后用自己的解密密钥D2作用其上，D2(E2(a))=a,便看到明文a。这样的RSAE2(a),使用的保密体制，也不知道发给何人,每人都有不同的解密密钥且严格保密。退一步讲，即X2pq，也就无法知道(n)(p-1)(q-1),所以即2 2 2 2 2使敌人知道X使用E(即e),也算不出d来(ed=1+m(n2 2 2 2 2例为了使对RSA公开密钥体制有更清楚的认识，我们给出几个具体的例子，其中的素数p和q取成较小的素数。1取素数p=5，q=11，n=pq=55，(n)=(p-1)(q-1)=40，某分公司Y取为e=3，(3,4)=(3,10)=1,将模n=55和加密密钥e=3Y的解密密钥d应满足ed=1+m(n3d=1+m·40,所以d=40m1m13 3m=2，d=27，Yd=27应严格保密，模n=55p=5，q=11对总公司外保X要向Y（代码先查阅Yn=55，e=3，做加密运算E(23)=ae23312(mod55)将密文b=12发出。Y收到密文后，做解密运算D(12)=1227(123)917289239(233)312323 (mod55)于是Y就得到明文b=23，这与X向Y.例2取两个较小的素数p=29，q=53，则模n=29×53=1537.取m=1，得1+m(n)=1+28×52=1457=31×47将加密密钥取为e=4d需满足同余式ed=47≡1（mod(n)4(n)）=1，故有唯一解d=31。设明文信息a是Noway需要把信息a转换为一个常数M，为此，令A=01 B=02 C=03 D=04 E=05 D=06 …… Y=25 Z=26,=27 .=28 ?=29 0=30 1=31 2=32 …… 9=39 !=40并且用00表示字母之间的空位.这样，信息a就被变成明文数M：M=141500230125由于模n=153，因此限制明文数小于153，故可将M分成四段（每段三位数为141， 500， 230， 125.然后分段进行加密运算E。第一段141被加密为密文14147≡658(=E(141))（mod1537）同样可得其它三段的密文。全部四段的密文分别为:0658 1408 1250 1252现在我们看通讯的另一端，接收者收到密文后，根据只有他自己知道的解密密钥d=31，可以把密文解密成明文：65831≡141(=D(658))（mod1537）同样可得其它三段的明文(同上).这样就得到了明文。RSA体制中进行加密运算Ei和解密运算Dinn=pq，可以先用较小的模pqnn的剩余。为此，要先求出整数NpNq，满足：Np≡1（mod，Np≡（mod，Nq≡（modNq≡（mod）i EE(a)≡ae(modn),pq分别算出aei i ii [aep和[aeq,()可知Eii E(a)=[ae]

≡[ae

N +[ae]

(modn)i iｎ

i p

i q q这样就比较简单地得到密文Ei(a)。做解密运算Di时可类似进行。举例如下。1 2 例3取则n=55,=4*10=40.设X 要把信息a=3发往X ,查到X 1 2 公开加密密钥为e2=7,（7，40）=1,为计算密文E2(a)=E2(3)≡37(mod55),先求N5和N11，满足：N5≡1(mod5), N5≡0(mod11), 可取N5N11≡0(mod5), N11≡1(mod11), 可取N11=-10.由欧拉定理，34≡1(mod5),310≡1(mod11)，所以[37]

≡37≡(34)2162 (mod5)5 3 3 3[37]

≡310

1110

2 (mod11)于是密文E(3)为

11 33

27 5 5E2(3)=[37]55≡211(2)(10)≡42(mod55)X1把加密的密文E2(3)=42 发至X2, X2 用自己的解密密钥d2 =23(d 1

11120

1191723 (mod40))进行解密运算

(42)≡4223 (mod55),可2 e2 7 7 7 2先求出4223≡23≡3(mod5), 4223≡(2)23≡3(mod11)所以4223≡3(mod即D 从而将密文E (3)=42解（恢复成原来的明文a=3。2 2整个解密过程为D (E (a=3))=D (42)=3。2 2 2RSA学科的发展。（4）RSA公开密钥体制的“签名”功能RSA公开密钥体制于1977年提出后，许多人开发出这种体制的新功能就是其中的一种。从上述密码传递过程中可以看出，当X 译出明文a时，他并不知道是谁2发给他的，因为X 的加密密钥e 甚至n以及密码体制都可公开，任何人都可以制造一个2 2假消息然后用X 的加密密钥e 编成密文E (b)=[be2 2 2

]n发给X2。这就好象有人知道他的地址写匿名信，或者知道他的电话号码打电话乱说一通。所以X应当有办法让X 知道1 2消息只能来自X1而RSA公开密钥体制却可以做到这一点。RSA公开密钥体制“签名”功能的基本思想非常简单。因为每个Xi的加密运算Ei和解密运算DiDiEi=I，而且还满足EiDi=I。因为对任何信息a，0≤a≤n-1，都有：i i i ED(a)≡E(ad)≡([ad] )e≡adi i i i i i i