1、信息安全導(dǎo)論第五講密碼學(xué)技術(shù)中的數(shù)學(xué)基礎(chǔ)信息安全研究室Dr. Zuxi Wang2022/8/311密碼學(xué)是研究密碼系統(tǒng)或通信安全的一門學(xué)科，分為密碼編碼學(xué)和密碼分析學(xué)。密碼編碼學(xué)是使得消息保密的學(xué)科，從事此行的稱為密碼編碼者。密碼分析學(xué)（密碼破譯學(xué)）是研究加密消息的破譯的學(xué)科，從事此行的稱為密碼分析者。精于此道的人被稱為密碼學(xué)家，現(xiàn)代的密碼學(xué)家通常是理論數(shù)學(xué)家。2022/8/312密碼學(xué)是一門交叉學(xué)科，它很大程度上是應(yīng)用數(shù)學(xué)學(xué)科。密碼學(xué)中涉及數(shù)論、代數(shù)、概率論、組合數(shù)學(xué)、計(jì)算復(fù)雜理論等多種數(shù)學(xué)知識(shí)。還涉及信息論學(xué)科知識(shí)。密碼學(xué)所涉及的知識(shí)十分廣闊，這里僅介紹部分?jǐn)?shù)學(xué)基本知識(shí)。2022/8/3

2、13數(shù)論基礎(chǔ)素?cái)?shù)同余、模運(yùn)算中國剩余定理Euclean算法Fermat定理、Euler定理素性檢驗(yàn)因子分解離散對(duì)數(shù)2022/8/314整除、素?cái)?shù)記整數(shù)集合Z=,-3,-2,-1,0,1,2,3,整除設(shè)a,bZ，a0，如果存在mZ，使得b=ma，則稱a整除b，以a|b表示，a是b的一個(gè)因子或約數(shù)。如果沒有任何m，使得b=ma，則稱a不能整除b,記ab，此時(shí)有a=mb+r且0r1被稱為素?cái)?shù)是指p的因子僅有1，-1，p，-p。否則，稱為合數(shù)。2022/8/315整除基本性質(zhì)a|a; b0，b | 0;If a|b,b|c,then a|c;if a|1, then a=1;if a|b, and b

3、|a,then a=b;if b|g and b|h, then b|(mg+nh),for any integers m and n注意: if a=0 mod n, then n|a2022/8/316互素與最大公約數(shù)最大公約數(shù)（最大公因子）：若a,b,cZ，如果ca，cb，稱c是a和b的公約數(shù)。正整數(shù)d稱為a和b的最大公約數(shù)(記d=gcd(a,b)或(a,b) ，如果它滿足:d是a和b的公約數(shù)。對(duì)a和b的任何一個(gè)公約數(shù)c有cd。等價(jià)的定義形式是： gcd(a,b)=maxk: ka，kb若gcd(a,b)=1，稱a與b是互素的。2022/8/317最小公倍數(shù)最小公倍數(shù)a,b的倍數(shù)中最小者

4、稱為a,b的最小公倍數(shù)，記為：lcm(a,b)a,b不全為0，有ab=gcd(a,b)lcm(a,b).注意：對(duì)有限個(gè)整數(shù)a1,a2,an,也可定義最大公約數(shù)gcd(a1,a2,an)和最小公倍數(shù)lcm(a1,a2,an).2022/8/318帶余除法帶余除法：aZ, m0，可找出兩個(gè)唯一確定的整數(shù)q和r使a=qm+r, 0rP2P3Pt是素?cái)?shù)，其中i0整數(shù)。2022/8/3110目前沒有可用于整數(shù)分解的有效算法。對(duì)于整數(shù)a,b(a,b2)，a,b的素?cái)?shù)分解式分別為： ， ，其中ei，fi0,ti1，則有：2022/8/3111帶余除法中，aZ，m0，a=qm+r， 0r1）分成一些兩兩不交的

5、等價(jià)類（剩余類）。2、整數(shù)模m同余類共有m個(gè)，他們分別為mk+0,mk+1, mk+2,mk+(m-1); kz，每一個(gè)算一類，每一類都可以選一個(gè)代表元，一般選這一類中的最小的非負(fù)整數(shù)。于是稱0,1,2,m-1為標(biāo)準(zhǔn)完全剩余系。其中與m互素的剩余類構(gòu)成模m的簡約剩余系。Z模12的標(biāo)準(zhǔn)完全剩余系為：0,1,2,3,4,5,6,7,8,9,10,112022/8/3113Modulo 7 Example. -21 -20 -19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10

6、 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 . 2022/8/31143、模運(yùn)算：對(duì)于某個(gè)固定模m的同余式可以象普通的等式那樣相加相減和相乘：a(mod m)b(mod m)=(ab)(mod m)a(mod m)*b(mod m)=a*b(mod m)例：由同余式演算證明5601是56的倍數(shù)，2231是47的倍數(shù)。 解： 注意53=12513(mod56) 于是有561691(mod56) 對(duì)同余式的兩邊同時(shí)升到10次冪， 即有56(560-1)。 其次, 注意26=64-30(mod47)

7、,于是223=(26)325=(26 26)26 25 900*(-30)*(32) mod(47) (7)* (-30)*(32) (mod47) 1(mod47) 于是有 47(223-1)2022/8/3115Modulo 8 Example2022/8/31164、定理：(消去律)對(duì)于abac(mod m)來說，若最大公因子gcd (a,m)1（即a與m是互素），則bc(mod m)加法消去律： a+ba+c(mod m)，有bc(mod m).5、一次同余方程axb(mod m)，這個(gè)方程有沒有解，相當(dāng)于問有沒有那樣一個(gè)整數(shù)x，使得對(duì)于某個(gè)整數(shù)y來說，有ax+my=b 定理：記最大公

8、因子(a,m)=d，則同余方程axb(mod m)有解的充分必要條件是db。當(dāng)這個(gè)條件滿足時(shí)，恰有d個(gè)模m同余類中的整數(shù)是上述方程的解。 證明：略。（從ax+my=b入手）2022/8/31176、整數(shù)環(huán)z模正整數(shù)m得到的剩余類集合可以記為zm(或z/(m), zm=0,1,m-1 在3、中已說明zm對(duì)剩余類的加法，乘法是封閉的，可列出它們的加乘表。我們稱zm為剩余類環(huán)（或同余類環(huán)）7、在整數(shù)環(huán)z中是沒有零因子的，即兩個(gè)非零整數(shù)的乘積一定不等于0，但是剩余環(huán)則不然。 例z12中：3*4=12=0 說明，zm中的元素可分為兩類，一類是零因子，即若zm,0，存在zm且0，有*=0，則稱，都為zm中

9、的零因子。另一類是可逆元，即若zm，存在zm，使*=1，此時(shí),互為各自的逆元，記-1=；-1=2022/8/3118定理：剩余類環(huán)zm中元素=a為zm的可逆元最大公約數(shù)(a,m)=1要證明這個(gè)定理，只需證明下列引理：引理：任意兩個(gè)整數(shù)a和b都有一個(gè)最大公約數(shù)，這樣一個(gè)最大公約數(shù)d可以表示成a,b二數(shù)關(guān)于整系數(shù)的線性組合，即有s,tz，使dsatb。證明：不妨設(shè)b0，用輾轉(zhuǎn)相除法，先用b去除a，得 a=q1b+r1,0r1b;(1)如果r1=0，停止，否則再用r1去除b，得 b=q2r1+r2,0r2r1;(2)如果r2=0，停止，否則再用r2去除r1，得 r1=q3r2+r3;0r3r2;(3

10、)等等，這樣一直進(jìn)行下去，可得一系列關(guān)系式： rk-3=qk-1rk-2+rk-1,0rk-1rk-2; (k-1) rk-2=qkrk-1+rk,0rk r2 r3 r4 rk0是嚴(yán)格遞降的一串非負(fù)整數(shù)，故最后總會(huì)出現(xiàn)余數(shù)為0的情形：rk-1=qk+1rk(k+1)所以，進(jìn)行有限步必停止，此時(shí)d=rk=(a,b)成立，這是因?yàn)?). 可知rk為a和b的公約數(shù)，只要按倒序分析自然有此結(jié)論。2). a和b的任何一個(gè)公約數(shù)c都是rk的約數(shù)，只要按正序分析，自然可知。為證定理的后一部分，將式(1)做移項(xiàng)有 r1=s1a+t1b（其中s1=1,t1= -q1）再將式(2)右端通過移項(xiàng)變?yōu)閞2=s2a+

11、t2b這樣一直下去，最后得d=rk=s*a+t*b,s,tz.2022/8/3120例子：求(180，252)，并將他表示為180和252這兩個(gè)數(shù)的一個(gè)帶整系數(shù)的線性組合。解：252=1*180+72(1)180=2*72+36 (2)72=2*36(3) 得(180,252)=36，同時(shí)有72=252-1*180 (1) 由(2)得36=180-2*72 (2)將(1)代入(2 )，即得 36=180-2*(250-180) =3*180-2*2522022/8/3121中國剩余定理例子：（孫子算經(jīng)）今有物不知其數(shù)：三三數(shù)之余二；五五數(shù)之余三；七七數(shù)之余二。問物幾何？答曰：二十三。232*7

12、0+3*21+2*15(mod 105)（口訣：三人同行七十稀，五樹梅花廿一枝， 七子團(tuán)圓月正半，除百零五便得知。）問，70，21，15如何得到的？原問題為：求解同余方程組2022/8/3122注意：若x0為上述同余方程組的解，則x0=x0+105*k(kz) 也為上述同余方程組的解。有意義的是，解題口訣提示我們先解下面三個(gè)特殊的同余方程組(1) (2) (3)的特殊解=?=?=?以方程（1）為對(duì)象，相當(dāng)于解一個(gè)這樣的同余方程 35y1(mod 3)，為什么呢？原因是，從（1）的模數(shù)及條件知，x應(yīng)是35的倍數(shù)，于是可以假設(shè)x35y，有2022/8/312335y1(mod 3)相當(dāng)于2y1(m

13、od 3) 解出y=2（mod3）于是x35*2(mod(3*35) 70(mod105)類似地得到（2）、（3）方程的模105的解21、15。于是有得2022/8/3124中國剩余定理：設(shè)自然數(shù)m1,m2,mr兩兩互素，并記M=m1m2mr，則同余方程組在模M同余的意義下有唯一解。2022/8/3125證明：考慮方程組，(1=i=r)由于諸mi(1=i1時(shí)，它的值(n)等于比n小而與n互素的正整數(shù)的個(gè)數(shù)。 以n24為例，比24小而與24 互素的正整數(shù)為：1,5,7,11,13,17,19,23。因此，我們有(24)8。若p為素?cái)?shù)，則(p)p-1。若p，q都為素?cái)?shù)且pq，此時(shí)有(pq)(p)(

14、q)= (p-1)(q-1)證明：考慮zpq剩余類的集合是0，1，2，（pq-1）,集合中與pq不互素的元素子集為p,2p,(p-1)q和子集q,2q,(p-1)q以及0，于是若設(shè)npq，有(n)=pq-(q-1)+(p-1)+1 =(p-1)(q-1)=(p)(q).例：(21)=(3*7)=(3)(7)=2*6=12.2022/8/3132若m1,m2互素，則(m1m2)(m1) (m2).設(shè)n= p1e1p2e2prer，其中p1,p2,pr為互異素?cái)?shù)，則(n)= p1e1-1p2e2-1prer-1(p1-1)(p2-1)(pr-1) =n(1-1/p1) (1-1/p2) (1-1/

15、p3) (1-1/pr)Euler公式證明：考慮1/n,2/n,n/n，然后化簡成既約分?jǐn)?shù)，分母為d的一類分?jǐn)?shù)有(d)個(gè)，于是歐拉定理（Euler）： 若整數(shù)a與整數(shù)n互素，則a(n)1(mod n)。證明：設(shè)小于n而和n互素的(n)個(gè)正整數(shù)為 r1,r2,r3,r(n)(1)2022/8/3133他們是模n兩兩互不同余的。對(duì)每一個(gè)定數(shù)i來說，由于a和ri都與n互素，所以(ari,n)=1，所以ari同余于（1）中的某個(gè)ri即ariri(mod n)，1i(n)并且當(dāng)ij時(shí)有ari /arj(mod n).于是, 為 的置換.所以有由(ri,n)=1, 所以 Remarks：1*. np時(shí)，(

16、a,p)=1,有ap-11(mod p)為Fermat定理！ 而對(duì)任意的a，有apa(mod p)（Fermat）2*.易見a(n)+1a(mod n)3*.若n=pq，p與q為相異素?cái)?shù)，取0mn，若(m,n)=1，有m(n)+1m(mod n)，也即m(p-1)(q-1)+1m(mod n).2022/8/31344*.對(duì)于3中，若(m,n)p或q，也同樣有m(n)+1m(mod n)5*.由 (m(n)k1k(mod n) 知 mk(n)1(modn)， 進(jìn)一步mk(n)+1m(mod n)mk(p-1)(q-1)+1m(mod n)2022/8/3135素性檢驗(yàn)、因子分解在許多加密算法中

17、，需要隨機(jī)選擇一個(gè)或多個(gè)非常大素?cái)?shù)，因此必須確定一個(gè)給定的大數(shù)是否是素?cái)?shù)。素性檢驗(yàn)(測試)目前還沒有簡單有效的方法解決該問題。Miller和Rabin提出一種算法，其利用了Fermat定理。該算法產(chǎn)生的數(shù)不一定數(shù)素?cái)?shù)，但令人驚訝的是，其產(chǎn)生的數(shù)幾乎可以肯定是素?cái)?shù)。2022/8/3136素性檢驗(yàn)、因子分解RSA算法安全性以對(duì)大整數(shù)進(jìn)行素?cái)?shù)分解的困難性為基礎(chǔ)，即無法在多項(xiàng)式時(shí)間內(nèi)對(duì)于一個(gè)足夠大的整數(shù)進(jìn)行分解。一旦這個(gè)難題被破解，則RSA算法的安全性便不復(fù)存在。一些具代表性的因子分解算法包括：二次篩法p-1因子分解方法是更為有效的橢圓曲線方法的基礎(chǔ)數(shù)域篩法等2022/8/3137強(qiáng)素?cái)?shù)許多密碼算法關(guān)

18、心強(qiáng)素?cái)?shù)。設(shè)nZ，p和q是素?cái)?shù)，并且n=pq。當(dāng)p，q滿足以下特性時(shí)，稱之為強(qiáng)素?cái)?shù)。 Gcd(p-1,q-1)比較??； p-1和q-1都有大的素因子（分別記為p*和q*）； p*-1和q*-1都有大的素因子； p+1和q+1都有大的素因子； (p-1)/2和(q-1)/2都是素?cái)?shù)。如果素?cái)?shù)p具有特性,則它們一定具有特性和.此時(shí)，即使采用某些特殊的因子分解方法，對(duì)整數(shù)n進(jìn)行因子分解也非常困難。2022/8/3138為了增加密碼算法的安全性，建議使用長度大并且具有隨機(jī)性結(jié)構(gòu)的強(qiáng)素?cái)?shù)，其中，素?cái)?shù)的長度比其結(jié)構(gòu)特點(diǎn)更為重要。但是，從因子算法對(duì)整數(shù)進(jìn)行分解的概率的角度考慮，強(qiáng)素?cái)?shù)與其他素?cái)?shù)相比并沒有明確

19、的優(yōu)勢。2022/8/3139代數(shù)基礎(chǔ)群、環(huán)、域、布爾代數(shù)概述群、環(huán)、域基本概念有限域 GF(pn)多項(xiàng)式算術(shù)布爾代數(shù)與布爾函數(shù)2022/8/3140概 述有限群、有限域、布爾函數(shù)等在密碼技術(shù)和應(yīng)用中越來越重要。cryptographyAES, Elliptic Curve, IDEA, Public Key將從抽象代數(shù)的群、環(huán)、域的基本概念開始介紹。2022/8/3141群（Group）代數(shù)系統(tǒng)：一個(gè)集合以及定義在其上的一組運(yùn)算一起構(gòu)成一個(gè)代數(shù)系統(tǒng)。群（group）是一個(gè)代數(shù)系統(tǒng) ，它僅有一個(gè)二元運(yùn)算*（由于是代數(shù)系統(tǒng)，所以運(yùn)算封閉性滿足），并滿足:結(jié)合律:(a*b)*c = a*(b*c)

20、 具有單位元e:e*a = a*e = a 每一元a 有逆元a-1:a*a-1 = e如果滿足交換律: a*b = b*a 則形成一個(gè)交換群(commutative group),也叫阿貝爾群(abelian group).Remark:在不引起歧義下，經(jīng)常將運(yùn)算符號(hào)省略。 a*b=ab2022/8/3142 例1 和 不是群。 、和 都是群。例2 設(shè)有Z4=0,1,2,3，模4的加法運(yùn)算 定義為則構(gòu)成一個(gè)群。0 1 2 301230 1 2 31 2 3 02 3 0 13 0 1 2Examples:2022/8/3143Examples:是一個(gè)交換群，也叫加群。+是關(guān)于模m加法；，是關(guān)于

21、模m的乘法。當(dāng)m是素?cái)?shù)時(shí)，它構(gòu)成一個(gè)乘法交換群；但當(dāng)m不是素?cái)?shù)時(shí)，它不構(gòu)成群。2022/8/3144循環(huán)群（Cyclic Group）群元素的冪example: a3 = a*a*aak = a*a*a (k個(gè)a相乘，k正整數(shù))規(guī)定: e=a0，a-k=a-1*a-1*a-1=(a-1)-k(k個(gè)a-1相乘，k正整數(shù))對(duì)任意整數(shù)m,n,am*an=am+n,(am)n=amn,a-n=(a-1)n=(an)-1.群中任何元都是某個(gè)元g的冪，稱群為循環(huán)群，g稱為其一個(gè)生成元(generator)。i.e. 對(duì)群中任一元b,存在k,使 b = gk.以g為生成元的循環(huán)群記為G=.稱為由g生成的循環(huán)

22、群.2022/8/3145對(duì)任意負(fù)整數(shù) ,按照群中逆元的表示方法例3 群是循環(huán)群，1是生成元，10=0，對(duì)任意正整數(shù)n，n=1+1+1，按照群中元素的冪的表示方法n=1n. 例4 例2中的群是循環(huán)群，1是其生成元， 3也是其生成元。 因?yàn)?0=0，11=1，12=141=res4(2)=2, 13=1241=2 41=res4(3)=3 又30=0，31=3，32=343=res4(6)=2,33=32 43=243=res4(5)=12022/8/3146 例5 設(shè)G= a,b,c,e ，* 是G上的二元運(yùn)算， *e a b ceabca e c bb c e ac b a ee a b c

23、 a*a=b * b=c * c=e * e=e , a * b=b * a=c, b * c=c * b=a， a * c=c * a=b是一阿貝爾群，但它不是循環(huán)群，一般稱這個(gè)群為Klein四元群。2022/8/3147群的階和元素的周期設(shè)是一個(gè)群，如果G是有限集，則稱是有限群，G中元素的個(gè)數(shù)稱為群的階；若G是無限集，則稱是無限群。設(shè)是一個(gè)群，a G，若存在正整數(shù) r ，使得 ar =e，則稱元素 a 具有有限周期。使ar=e成立的最小的正整數(shù) r 稱為 a 的周期。如果對(duì)于任何正整數(shù)r，均有 ar e，則稱 a 的周期為無限。2022/8/3148群的階和元素的周期Examples在群

24、中，單位元1的周期為1, -1的周期為2. （-1）2=（-1）4=（-1）6= =1群中， 14 = 13 41=3 41 = res4(4)=0； 21 = 2 ，22=2 42 = res4(4)= 0；34 = 33 43 = 1 43 = res4(4) = 0。 生成元1和3的周期均為4，循環(huán)群的階也為4。循環(huán)群的生成元1和1，其周期均為無限，群是一個(gè)無限階的循環(huán)群。2022/8/3149群的部分性質(zhì)消去律：設(shè)是一個(gè)群，則對(duì)任意的a,b G，（1）存在唯一的元素xG，使a*x=b；（2）存在唯一的元素yG，使y*a=b。設(shè)是一個(gè)群，則對(duì)任意的a,b,cG（1）若a*b=a*c, 則

25、 b=c；（2）若b*a=c*a，則 b=c。2022/8/3150群的部分性質(zhì)求逆:設(shè)是一個(gè)群，則對(duì)任意的a,b,a1,a2,ak G(a*b)-1=b-1*a-1;(a1*a2*ak)-1=ak-1*a2-1*a1-1.關(guān)于元素的周期:群中的元素 a 若具有有限周期r，則當(dāng)且僅當(dāng)k 是r的整數(shù)倍時(shí)，ak = e.群中任一元素與它的逆元具有相同的周期。在有限群中，每個(gè)元素均具有有限周期，且周期不超過群的階。結(jié)論對(duì)無限群不成立。如群 . 2022/8/3151群的部分性質(zhì)設(shè)是一由元素 g 生成的循環(huán)群，則若 g 的周期為 n ，則是一個(gè)階為 n 的有限循環(huán)群；若 g 的周期為無限，則是一個(gè)無限

26、階的循環(huán)群。2022/8/3152群的部分性質(zhì)Examples群中單位元0的周期是1；1和3的周期均為4；2的周期為2，群的階4.設(shè)是一個(gè)群，且對(duì)于任意的a,bG，有(a * b)2=a2 * b2 , 則 是阿貝爾群。設(shè)Z6 =0,1,2,3,4,5, 6 是模6的加法，定義為： a 6b = res6(a+b)，是一個(gè)群。給出其單位元；各元素的逆元；各元素的周期。2022/8/3153設(shè)是一個(gè)群，若是的子代數(shù)，單位元e H，且對(duì)于任意的a H，有a-1 H，則稱是的子群。的非空子集H關(guān)于G的運(yùn)算*構(gòu)成子群，必須滿足：封閉性：H關(guān)于 * 封閉，a,bH，有a*b H;單位元：G的單位元eH;

27、可逆性：任意aH，有a-1H.Example:對(duì)于任意的整數(shù)m，若令I(lǐng)m= mi: i I. 則均構(gòu)成的子群。子群（Subgroup）2022/8/3154若是的子群，則也是群。設(shè)是一個(gè)群，H是G的非空子集，若也是群，則稱是的子群。（子群等價(jià)定義）設(shè)是群，H是G的非空子集，若(1)對(duì)于任意的a,bH，有a*bH；(2)對(duì)任意的aH，有a-1H，則是的子群。子群（Subgroup）2022/8/3155設(shè)是群，H是G的非空子集，若對(duì)于任意的a,bH，有a*b -1H，則是的子群。設(shè)是一有限群，若是的子代數(shù)，則是的子群。即：若對(duì)于任意的a,bH，有a*bH，則是的子群（H有限且關(guān)于運(yùn)算封閉就構(gòu)成子

28、群）。設(shè)是一個(gè)群，若是的有限子代數(shù)，則是的子群。子群（Subgroup）2022/8/3156子群（Subgroup）Examples設(shè)是一個(gè)群，a是G中任一元素，令H是a的所有整數(shù)次冪的集合，則H對(duì)于G的運(yùn)算構(gòu)成的子群。顯然是由元素a生成的一個(gè)循環(huán)群。設(shè)是一個(gè)群，定義G的子集H=h:對(duì)任意x G,h*x=x*h，H對(duì)于運(yùn)算*構(gòu)成的子群。2022/8/3157陪集（coset）、正規(guī)子群（normal subgroup）H是G的子群，a屬于G，aH=ah|h屬于H稱為G的一個(gè)關(guān)于H的左陪集（a所在的陪集）。同樣Ha構(gòu)成一個(gè)右陪集。對(duì)a，aH不一定等于Ha。如果對(duì)所以的a，都有aHHa，則稱H為

29、G的一個(gè)正規(guī)子群。稱aH或Ha為陪集。2022/8/3158拉格朗日(Lagrange)定理陪集定理：G的關(guān)于H的所有不用的左（右）陪集構(gòu)成G的一個(gè)分劃。Lagrange定理：群G必為其子群H及其全部不相同的陪集的直和。推論：有限群的階必為其子群的階的整數(shù)倍。素?cái)?shù)階群只有平庸子群（群自身與單位元）2022/8/3159群的同態(tài)與同構(gòu)h:G1G2群間的一個(gè)映射，如果h保持群的運(yùn)算，即：a,b of G，有h(ab)=h(a)h(b)，則稱h為群G1,G2間的一個(gè)同態(tài)映射，簡稱同態(tài)(homomorphism)。若同態(tài)h同時(shí)是一個(gè)雙射，那么稱h為一個(gè)同構(gòu)映射，簡稱同構(gòu)(isomorphism) 。這

30、是稱兩群G1,G2是同構(gòu)的。從代數(shù)結(jié)構(gòu)的角度看，同構(gòu)的群具有相同的代數(shù)結(jié)構(gòu)，被視為同一群。2022/8/3160商群（Quotient group）群G的正規(guī)子群H與其全部不相同的陪集在陪集乘法意義下構(gòu)成一個(gè)群，稱為G關(guān)于H的商群，記為G/H。f: GG群間的一個(gè)同態(tài)映射，kerfg:f(g)=e,e為G的單位元，即kerf為G的單位元e在G中的原象集合。稱kerf為同態(tài)映射f的核。同態(tài)基本定理：設(shè)G為G關(guān)于同態(tài)映射f的象，則有：1.kerf是G的正規(guī)子群；2.G與商群G/kerf同構(gòu)。2022/8/3161變換群（Transform group）集合A上的若干雙射（一一映射）對(duì)于映射的復(fù)合運(yùn)

31、算構(gòu)成一個(gè)群，稱其為A上的一個(gè)變換群。一個(gè)集合A的所有一一變換作成一個(gè)變換群。任何一個(gè)群都與一個(gè)變換群同構(gòu)。2022/8/3162置換群（permutation group）有限集A到直身的一個(gè)雙射稱為A上的一個(gè)置換。A=n，稱A上的置換為n階置換。An，A上所有的n階置換在置換乘積（映射復(fù)合操作）下構(gòu)成一個(gè)群，稱為n階對(duì)稱群(Symmetric group)，記為Sn。Sn的任一子群，都稱為一個(gè)置換群。所有n階偶置換（可分解為偶數(shù)個(gè)對(duì)換的乘積的置換）構(gòu)成Sn的一個(gè)子群，叫交錯(cuò)群(Alternative group)，記為An。2022/8/3163置換群（permutation group）

32、對(duì)稱群Sn的階為n!，交錯(cuò)群An的階為n!/2。凱萊(Caylay)定理：每一個(gè)有限群均同構(gòu)于由群元素集合上的一個(gè)置換群（ Sn的一個(gè)子群） (gG，gf(g),f(g)為G上一個(gè)置換，f(g)： gi g gi ,全體f(g)構(gòu)成G上的置換群)2022/8/3164群的生成元系G是一個(gè)群，S是G的一個(gè)非空子集S生成的子群H:G的包含S的最小子群,記H(S)。S生成的子群H由S中元素及逆元的任意乘積構(gòu)成。如果G=(S)，那么稱S為群G的一個(gè)生成元系(Generator system or generator set)。當(dāng)S1，Sa，那么S生成G的一個(gè)循環(huán)子群，(S).群的生成元系通常不唯一。2

33、022/8/3165對(duì)稱群的生成系對(duì)稱群Sn的每個(gè)元都可以寫成(12),(13),(1n)這n-1個(gè)對(duì)換（2-循環(huán)置換）中的若干個(gè)的乘積。S=(12),(13),(1n)是Sn的一個(gè)生成元系。Remark：Sn還有其他生成元系。2022/8/3166環(huán)（Ring）帶兩個(gè)運(yùn)算（稱加法和乘法）的集合滿足:關(guān)于加法+構(gòu)成一個(gè)abelian群，其單位元為0稱為零元；關(guān)于乘法 滿足:乘法封閉律；滿足結(jié)合律； a(bc)=(ab)c對(duì)加法的分配律: a(b+c) = ab + ac則稱為一個(gè)環(huán)（Ring）如果乘法是交換的，則稱環(huán)為交換環(huán)( commutative ring)環(huán)中關(guān)于乘法如果有單位元，稱之為

34、環(huán)的單位元。2022/8/3167子環(huán)、理想、剩余類環(huán)的子代數(shù)即為其子環(huán)。R的子集關(guān)于R的運(yùn)算仍然是環(huán)，稱為R的子環(huán)。R的子環(huán)I，如果同時(shí)關(guān)于乘法還滿足：對(duì)R中任意元r，I中任意元a，有ar,ra均仍屬于I.則稱I為一個(gè)理想。R的理想I，關(guān)于加法構(gòu)成的剩余類集合上關(guān)于模I的加法和乘法構(gòu)成環(huán)，叫R的模I的剩余類環(huán)。記為R/I.2022/8/3168環(huán)的同態(tài)與同構(gòu)環(huán)的同態(tài)與同構(gòu)映射定義類似群的同態(tài)與同構(gòu)。兩個(gè)環(huán)之間的映射如果保持分別保持環(huán)的運(yùn)算，就稱為環(huán)的同態(tài)如果同態(tài)是一一映射，就稱為同構(gòu)。類似地有同態(tài)基本定理。2022/8/3169零因子、整環(huán)若ab=0,但a,b都不是R中的零元, 那么a(b)

35、均稱為左(右)零因子.否則，稱為非零因子.無零因子環(huán): 如果R中的a, b有ab=o,那么必有a=0 or b=0.整環(huán)（domain）：交換的有單位元的無零因子環(huán)，稱為一個(gè)整環(huán)。2022/8/3170Example:整數(shù)集關(guān)于普通的加法和乘法構(gòu)成一個(gè)環(huán)且是一個(gè)整環(huán).是一個(gè)交換環(huán)，稱為模m的剩余類環(huán)。當(dāng)m是合數(shù)時(shí)，剩余類環(huán)Zm中有零因子，Zm中的a，若(a,m)=1,則a有逆元；當(dāng)m是素?cái)?shù)時(shí)，剩余類環(huán)Zm是整環(huán)。2022/8/3171除環(huán)、域一個(gè)環(huán)關(guān)于其乘法不一定有單位元，另外其任一元也不一定有乘法逆元。如果一個(gè)環(huán)有單位元，并且任一非零元均有逆元，則稱其為一個(gè)除環(huán)。所以是除環(huán)，它至少有一非零元

36、，且是加群；是群。一個(gè)除環(huán)，如果其關(guān)于乘法是交換的，則稱其為一個(gè)域（Field）。2022/8/3172有限域（Galois Fields）有限域也叫Galois 域，在密碼學(xué)中有重要作用。三個(gè)結(jié)論：每個(gè)有限域的階必為素?cái)?shù)的冪。對(duì)任意的素?cái)?shù)p和正整數(shù)n，存在pn階域。同階的有限域必同構(gòu)。于是：在同構(gòu)意義下，pn階的有限域有且只有一個(gè)，記為GF(pn).特別地，經(jīng)常用到有限域:GF(p) 稱為素域GF(2n)2022/8/3173Galois Fields GF(p)GF(p) 是 0,1, , p-1上關(guān)于模p加法、乘法構(gòu)成的有限域。P為素?cái)?shù)時(shí)，其中任意非零數(shù)都有逆元.2022/8/3174E

37、xample GF(7)2022/8/3175GF(p)中乘法逆元算法通過擴(kuò)展Euclidean算法得到:EXTENDED EUCLID(m, b)1. (A1, A2, A3)=(1, 0, m); (B1, B2, B3)=(0, 1, b)2. if B3 = 0return A3 = gcd(m, b); （b mod m 沒有逆）3. if B3 = 1 return B3 = gcd(m, b); B2 = b1 mod m4. Q = A3 div B3（A3除以B3的商）5. (T1, T2, T3)=(A1 Q B1, A2 Q B2, A3 Q B3)6. (A1, A2,

38、 A3)=(B1, B2, B3)7. (B1, B2, B3)=(T1, T2, T3)8. goto 2GF(pn)中乘法求逆類似（換成關(guān)于多項(xiàng)式的除法）2022/8/3176Inverse of 550 in GF(1759)2022/8/3177域上的多項(xiàng)式域F上的多項(xiàng)式為形如：的表達(dá)式，其中nN,aiF,i=1,2,n.若an0,稱n為該多項(xiàng)式的次數(shù),記n=deg(f(x),并稱an為首項(xiàng)系數(shù),首項(xiàng)系數(shù)為1的多項(xiàng)式稱為首1多項(xiàng)式.2022/8/3178多項(xiàng)式整環(huán)記Fx為域上所有多項(xiàng)式f(x)構(gòu)成的集合，則Fx關(guān)于通常的多項(xiàng)式加法+和乘法 形成一個(gè)整環(huán)，叫域F上的（一元）多項(xiàng)式環(huán)。0為

39、其零元，1為其單位元。在Fx上類似于整數(shù)環(huán)，關(guān)于多項(xiàng)式有商式、余式、整除、互素、最高公因式、最低公倍式等概念。2022/8/3179多項(xiàng)式帶余除法帶余除法：a(x),b(x)Fx,且b(x)0,則存在唯一的q(x),r(x)Fx,使a(x)=q(x)b(x)+r(x),式中deg(r(x)deg(b(x).q(x)稱為商式,r(x)稱為余式也用a(x) mod p(x) 表示a(x)除以p(x)的余式.稱為a(x)模p(x)，p(x)稱為模多項(xiàng)式。2022/8/3180不可約多項(xiàng)式若存在q(x),b(x)，deg(q(x)1, deg(b(x)1，使a(x)=q(x)b(x)，則稱a(x)為可

40、約多項(xiàng)式，否則稱為不可約(既約)多項(xiàng)式。2022/8/3181多項(xiàng)式運(yùn)算僅考慮一元多項(xiàng)式可把多項(xiàng)式運(yùn)算分為三種：使用代數(shù)基本規(guī)則的普通多項(xiàng)式運(yùn)算；系數(shù)運(yùn)算是模p運(yùn)算的多項(xiàng)式運(yùn)算，即系數(shù)在Zp中；系數(shù)在Zp中，且多項(xiàng)式被定義為模一個(gè)多項(xiàng)式m(x)的多項(xiàng)式運(yùn)算。2022/8/3182普通多項(xiàng)式運(yùn)算加法、減法為(相同次項(xiàng))對(duì)應(yīng)系數(shù)的加減法乘法為逐項(xiàng)相乘。eglet f(x) = x3 + x2 + 2 and g(x) = x2 x + 1f(x) + g(x) = x3 + 2x2 x + 3f(x) g(x) = x3 + x + 1f(x) x g(x) = x5 + 3x2 2x + 220

41、22/8/3183系數(shù) 在Zp中的多項(xiàng)式運(yùn)算在普通多項(xiàng)式運(yùn)算中，所有系數(shù)都取modp運(yùn)算。特別是 mod 2 的多項(xiàng)式運(yùn)算ie all coefficients are 0 or 1eg. let f(x) = x3 + x2 and g(x) = x2 + x + 1f(x) + g(x) = x3 + x + 1f(x) x g(x) = x5 + x22022/8/3184模多項(xiàng)式運(yùn)算基于多項(xiàng)式帶余除法:f(x) = q(x) g(x) + r(x)r(x) 稱為余式(remainder)記r(x) = f(x) mod g(x)定義模g(x)的多項(xiàng)式加法、乘法。如果沒有余式，說g(x)

42、 整除 f(x)如果g(x)僅有它自己和1為其因式，說g(x)不可約(或既約)多項(xiàng)式(或素多項(xiàng)式)所有多項(xiàng)式在模不可約多項(xiàng)式加法乘法下構(gòu)成一個(gè)域。2022/8/3185模p(x)的剩余類環(huán)Fx中一個(gè)多項(xiàng)式p(x)，(p(x)為由p(x)生成的Fx的子環(huán)，它是一個(gè)理想(主理想).Fx/(p(x)形成一個(gè)模p(x)的剩余類環(huán)。它等同于所有n-1次多項(xiàng)式集合上關(guān)于模p(x)加法乘法運(yùn)算構(gòu)成的環(huán)。當(dāng)p(x)為不可約多項(xiàng)式時(shí)，其形成一個(gè)域。2022/8/3186最大公因式尋找多項(xiàng)式的最大公因式c(x) = GCD(a(x), b(x) 如果 c(x) 是同時(shí)整除 a(x), b(x) 的次數(shù)最高的多項(xiàng)式

43、。（等價(jià)定義）通過擴(kuò)充Euclidean算法來尋找:EUCLIDa(x), b(x)1. A(x) a(x); B(x) b(x)2. if B(x) = 0 return A(x) = gcda(x), b(x)3. R(x) = A(x) mod B(x)4. A(x) B(x)5. B(x) R(x)6. goto 22022/8/3187模多項(xiàng)式運(yùn)算、GF(2n)有限域的元素個(gè)數(shù)必為pn，p為素?cái)?shù)，n為正整數(shù)。p個(gè)元素上以模p運(yùn)算產(chǎn)生一個(gè)域,Zp。但具有pn個(gè)元素的集合上模pn運(yùn)算卻不一定能產(chǎn)生域。如何定義合適運(yùn)算，使之pn個(gè)元成域？Zpn關(guān)于模pn運(yùn)算是不行的。2022/8/3188

44、模多項(xiàng)式運(yùn)算、GF(2n)S為域Zp上次數(shù)小于等于n-1的所有多項(xiàng)式組成。S中共有pn個(gè)不同的多項(xiàng)式。定義合適運(yùn)算，每個(gè)這樣的S都是一個(gè)有限域。運(yùn)算定義為：運(yùn)算遵循基本代數(shù)規(guī)則中的普通多項(xiàng)式運(yùn)算規(guī)則系數(shù)運(yùn)算以p為模，即遵循有限域Zp上的運(yùn)算規(guī)則。多項(xiàng)式運(yùn)算遵循模某個(gè)n次既約多項(xiàng)式m(x)的運(yùn)算。S即為一個(gè)pn階有限域，在同構(gòu)意義下，即為GF(pn).實(shí)際上，S=Zpx/(m(x).2022/8/3189模多項(xiàng)式運(yùn)算、GF(2n)P=2時(shí)，即為 GF(2n). 求其中的逆元通過擴(kuò)展的Euclidean求逆算法（與前面的GF(p)中求逆類似，將那里的整數(shù)換成Zp上的多項(xiàng)式）2022/8/3190E

45、xample GF(23)2022/8/3191計(jì)算上的考慮GF(2n)中的多項(xiàng)式系數(shù)都是0 or 1,所以任一多項(xiàng)式都可以由它的n個(gè)二進(jìn)制系數(shù)唯一表示。所以GF(2n)中的每個(gè)多項(xiàng)式都可以表示成一個(gè)n位的二進(jìn)制整數(shù)。兩個(gè)多項(xiàng)式加法等同于按位異或(XOR)運(yùn)算。乘法通過左移一位后按位異或來實(shí)現(xiàn)重復(fù)取模運(yùn)算來簡約高次的多項(xiàng)式 (also shift & XOR)2022/8/3192布爾代數(shù)代數(shù)系統(tǒng)(B;,)(這里和分別稱并和交運(yùn)算、稱為求補(bǔ)運(yùn)算)如果滿足如下性質(zhì)，稱為一個(gè)布爾代數(shù)：對(duì)于B中的任意元素x,y,z，有：(1) 交換律: x yy x，x yy x(2) 結(jié)臺(tái)律: x (y z)(x

46、 y) z x (y z)(x y) z(3) 等冪律: x xx，x xx(4) 吸收律: x (x y)x，、x (x y)x2022/8/3193(5) 分配律: x (y z)(x y) (x z) x (y z)(x y) (x z)(6) 同一律: x 0 x,x 1x(7) 零一律: x 11，x 0o(8) 互補(bǔ)律: x (x)=1，x (x)o(9) 對(duì)合律: (x)x(10) 德摩根定律: (x y)(x) (y) (x y)(x) (y)以上這10條性質(zhì)并不都是獨(dú)立的。事實(shí)上，所有其它的性質(zhì)都可由其中的四條：交換律、分配律、同一律和互補(bǔ)律推導(dǎo)出來。2022/8/3194如

47、：集合M的冪集2M關(guān)于集合的并集、交集、補(bǔ)集運(yùn)算形成一個(gè)布爾代數(shù)。有限布爾代數(shù)的基域的基數(shù)是2的冪。2022/8/3195布爾函數(shù)布爾表達(dá)式布爾代數(shù)B上由x1,x2,xn產(chǎn)生的布爾表達(dá)式歸納地定義為B的元素以及符號(hào)x1,x2,xn都是布爾表達(dá)式；布爾表達(dá)式的并、交、補(bǔ)運(yùn)算還是布爾表達(dá)式。布爾函數(shù)如果x1,x2,xn被解釋為只能在B中取值的變量，則一個(gè)由x1,x2,xn產(chǎn)生的布爾表達(dá)式實(shí)際上就是一個(gè)從Bn到B的函數(shù)。2022/8/3196由x1,x2,xn產(chǎn)生的布爾表達(dá)式有時(shí)也稱為B上的一個(gè)n元布爾函數(shù)。Bn到B的函數(shù)不一定是布爾函數(shù)，B2時(shí)，肯定有不是布爾函數(shù)的函數(shù)存在。B=2時(shí)，Bn到B的函

48、數(shù)都是布爾函數(shù)。多重布爾函數(shù)：(f1,f2,fm): Bn Bn.Bn到Bm的函數(shù)。其中fi是Bn到B的布爾函數(shù)。2022/8/3197GF(2)上布爾函數(shù)GF(2)只有兩個(gè)：0，1。關(guān)于這兩個(gè)量之間的邏輯運(yùn)算， GF(2)成為布爾代數(shù)。這時(shí)，GF(2) n到GF(2)的一個(gè)映射就稱為一個(gè)n元布爾函數(shù)(因?yàn)镚F(2) 的基數(shù)為2)。對(duì)于GF(2)中的元素，有x yxyx yx+y+xyx=x+1這里的+,分別表示GF(2)中的加(異或)、乘(與)運(yùn)算。2022/8/3198作為邏輯運(yùn)算的函數(shù)，布爾函數(shù)是研究數(shù)字邏輯電路的重要數(shù)學(xué)工具，也是研究以此為基礎(chǔ)的一切科學(xué)技術(shù)的重要工具，從而也是研究密碼

49、學(xué)和密碼技術(shù)的重要工具。無論在流密碼還是在分組密碼中，無論在私鑰還是在公鑰密碼中，布爾函數(shù)都有重要的應(yīng)用。2022/8/3199布爾函數(shù)的表示為了方便布爾函數(shù)的理論和應(yīng)用，人們在不同的情況下對(duì)布爾函數(shù)采用了不同的表示方法，主要有：真值表表示法小項(xiàng)表示法多項(xiàng)式表示法walsh譜表示法矩陣表示法等2022/8/31100布爾函數(shù)的研究問題布爾函數(shù)的表示布爾函數(shù)的研究方法布爾函數(shù)的設(shè)計(jì)實(shí)現(xiàn)布爾函數(shù)的性質(zhì)滿足一定性質(zhì)的布爾函數(shù)的特征刻劃、存在性、構(gòu)造與計(jì)數(shù)布爾函數(shù)不同性質(zhì)之間等價(jià)、相斥、相容、制約等關(guān)系密碼學(xué)中，布爾函數(shù)的一條性質(zhì)反映一種安全性能指標(biāo)，當(dāng)不同性能指標(biāo)相互制約時(shí)，如何折衷以提高綜合性能；

50、隨著技術(shù)的發(fā)展和新的攻擊方法的出現(xiàn)，新的性質(zhì)的提出和研究 等等2022/8/31101本原根（本原元）由Euler定理有: a(n)=1 mod n, GCD(a,n)=1考慮更一般的表示形式 am=1 mod n, GCD(a,n)=1則至少有 m= (n)使之成立，但可能有更小的m存在一旦冪次到m, a的冪便出現(xiàn)周期循環(huán)如果最小的m= (n)，則a稱為n的一個(gè)本原根(primitive root)如果n=p為素?cái)?shù)，則a的連續(xù)的冪生成模p的剩余類群。2022/8/31102使 am=1 mod n 成立的最小正冪m (這里(a,n)=1)為下列之一a mod n的階a 所屬的模n的指數(shù)a 所

51、產(chǎn)生的周期長。Zp中的a，如果a的階數(shù)(n)，在a就是n的一個(gè)本原根。如果a是n的本原根，則其冪a, a2, a(n)是(模n)各不相同的，且均與n互素。2022/8/31103特別的，對(duì)素?cái)?shù)p，若a是p的本原根，則a, a2, ap-1是(模p)各不相同的。a是Zp的生成元。如：素?cái)?shù)19的本原根為2,3,10,13,14,15.并不是所有的整數(shù)都有本原根。事實(shí)上，只有形為 2,4,pb,2pb的整數(shù)才有本原根，這里p任何奇素?cái)?shù)，b正整數(shù)。2022/8/31104離散對(duì)數(shù)或指標(biāo)求一個(gè)數(shù)模p的離散對(duì)數(shù)(discrete logarithm) 是求冪的逆問題即求x 使之滿足ax = b mod p

52、 記x=loga b mod p or x=inda,p(b)以底a(模p)的b的指標(biāo)。如果a是一個(gè)本原根，則x總存在,否則不一定。x = log3 4 mod 13 (x 使 3x = 4 mod 13)不存在而x = log2 3 mod 13 = 4（通過列出所以冪便知）2022/8/31105離散對(duì)數(shù)問題模指數(shù)運(yùn)算被認(rèn)為是一個(gè)單向函數(shù)，即：對(duì)于給定的整數(shù)n,a和x，容易通過“平方-乘”方法計(jì)算出ax mod n；但是，對(duì)于給定的整數(shù)n,a和b，由方程ax=b mod n求解整數(shù)x確是一個(gè)難題。有限域Zp上的離散對(duì)數(shù)問題是：對(duì)于給定的素?cái)?shù)p，有限域Zp上的一個(gè)本原元a，Zp中的非零元b，

53、求解滿足ax=b mod p的整數(shù)x(0 xp-2)，x=logab(mod p)(通常記為x=logab)。2022/8/31106離散對(duì)數(shù)計(jì)算目前還沒有能夠計(jì)算離散對(duì)數(shù)問題的多項(xiàng)式時(shí)間算法。對(duì)于已知的攻擊方法，素?cái)?shù)的選取應(yīng)該滿足至少兩個(gè)條件：長度大于150位p-1至少有一個(gè)大的素?cái)?shù)因子窮搜索方法可以對(duì)離散對(duì)數(shù)進(jìn)行求解，但對(duì)于足夠大的素?cái)?shù)p并不可行，其所需計(jì)算時(shí)間和存儲(chǔ)空間均為O(p).2022/8/31107離散對(duì)數(shù)計(jì)算有3個(gè)群的離散對(duì)數(shù)是密碼設(shè)計(jì)人員最為關(guān)心的。這三個(gè)群分別是：素域GF(p)的乘法群特征為2的有限域GF(2n)上的乘法群有限域F上的橢圓曲線群EC(F)2022/8/311

54、08離散對(duì)數(shù)計(jì)算GF(p)上計(jì)算離散對(duì)數(shù)問題的算法有很多種。平凡算法：通過預(yù)計(jì)算所有可能的ax值并按有序?qū)?x,ax)的第二個(gè)坐標(biāo)排序。表明可以在O(1)時(shí)間內(nèi)解決離散對(duì)數(shù)問題，所需預(yù)計(jì)算時(shí)間和存儲(chǔ)空間均為O(p)。非平凡算法有多種：Pohlig-Hellman算法線性篩選法(Linear Sieve)數(shù)域篩選法(Number Field Sieve-NFS)2022/8/31109離散對(duì)數(shù)計(jì)算Shakes算法指數(shù)算法 等等算法等內(nèi)容可以參考有關(guān)文獻(xiàn)。2022/8/31110計(jì)算復(fù)雜性理論 （1）理論安全性（無條件安全性）:如果具有無限計(jì)算資源的密碼分析者也無法破譯該密碼體制，這就是理論安全性

55、（無條件安全性），也稱絕對(duì)不可破譯，即是說密碼分析者無論截獲多少密文以及無論用什么方法進(jìn)行攻擊都不可能破譯。（2）可證明安全性：如果從理論上證明破譯該系統(tǒng)的代價(jià)（困難性）不低于求解某個(gè)已知的數(shù)學(xué)難題，這就是可證明安全性。（3）計(jì)算安全性：如果用用已知的最好算法和利用現(xiàn)有的（或密碼系統(tǒng)生命期內(nèi)）最大計(jì)算資源仍然不可能在合理的時(shí)間內(nèi)完成破譯該系統(tǒng)所要求的計(jì)算（量），這就是計(jì)算安全性。即密碼分析者根據(jù)可以利用的資源進(jìn)行破譯所用的時(shí)間非常長，或者說破譯的時(shí)間長到原來的明文失去保密價(jià)值。可證明安全性和計(jì)算安全性統(tǒng)稱為實(shí)際安全性。 2022/8/31111 計(jì)算機(jī)復(fù)雜性理論是密碼安全性理論的基礎(chǔ)，它為分析不同密碼技術(shù)和算法的“復(fù)雜性”提供了一種方法，它對(duì)不同的密碼算法和技術(shù)進(jìn)行比較，從而給出問題求解困難性的數(shù)量指標(biāo)，并確定它們的安全性。 什么是計(jì)算機(jī)復(fù)雜性理論？（1）算法復(fù)雜性：密碼分析所需的計(jì)算量則是密碼體制安全性的生命指標(biāo)。如果用n 表示問題