密碼學(xué)的數(shù)學(xué)基礎(chǔ)課件

密碼學(xué)的數(shù)學(xué)基礎(chǔ)初等數(shù)論素?cái)?shù)的產(chǎn)生有限域內(nèi)的離散對(duì)數(shù)單向哈希函數(shù)

初等數(shù)論1.模運(yùn)算2.素?cái)?shù)3.最大公因數(shù)4.乘法逆元素5.Fermat小定理及歐拉函數(shù)6.中國(guó)剩余定理7.二次剩余8.Legendre（勒讓得）符號(hào)9.Jacobi（雅各比）符號(hào)10.生成元11.有限域中的計(jì)算1模運(yùn)算同余：如果a=b+kn，k為整數(shù)，則a

b（modn）amodn：a模n操作，表示a除以n的余數(shù)，為0到n－1之間的整數(shù)。例如：(7＋9)mod12=16mod12=4模運(yùn)算（+、－、

）滿足交換律、結(jié)合律和分配律。按模計(jì)算原理：對(duì)中間結(jié)果作模運(yùn)算與做完了全部運(yùn)算后再做模運(yùn)算結(jié)果相同。按模指數(shù)運(yùn)算：ammodn將指數(shù)運(yùn)算作為一系列乘法運(yùn)算，每次做一次模運(yùn)算。例：a8modn=((a2modn)2modn)2modn當(dāng)m不是2的乘方時(shí)，將m表示成2的乘方和的形式。例如：25=(11001)2，即25=24+23+20

a25modn=(a16

a8

a)modn=((((a2)2)2)2

((a2)2)2

a)modn=((((a2

a)2)2)2

a)modn適當(dāng)存儲(chǔ)中間結(jié)果，則只需6次乘法：(((((((a2modn)

a)modn)2modn)2modn)2modn)

a)modn定理：若a

bmodm，c

dmodm，則1.

a

c

b

dmodm2.

ac

bdmodm證：a=km+b；c=hm+d定理：若ac

bcmodm，且gcd（c,m）=1，則a

bmodm證明：因?yàn)閍c

bcmodm所以ac=km+bc所以c（a-b）=km又因?yàn)間cd（c,m）=1所以c|k所以k=h·c所以a-b=hm所以a

bmodm定理：若ac

bcmodm，d=gcd（c,m），則：a

bmodm/d因?yàn)閍c

bcmodm所以ac=km+bc所以c（a-b）=km又因?yàn)閐=gcd（c,m）所以c=c1·d，m=c2·d，gcd（c1,c2）=1所以c1·d（a-b）=k·c1·d所以c1（a-b）=k·c2又因?yàn)間cd（c1,c2）=1所以c1|k所以k=h·c1所以a-b=k·h·c2所以a

bmodc2

所以

a

bmod（m/d）

2素?cái)?shù)素?cái)?shù)（質(zhì)數(shù)）：大于1的整數(shù)，只能被1和本身整除。有無窮多個(gè)素?cái)?shù)。如：2，73，2521，2365347734339，2756839-1整數(shù)的表示法1987的10進(jìn)制表示：1·103＋9·102＋8·10＋7定理：設(shè)m是大于1的正整數(shù)，則每個(gè)正整數(shù)n可唯一的表示為：

n=Ckmk＋Ck-1mk-1＋…＋C1m＋C0m為基（radix）設(shè)n0=n，則n1=

n0/m

C0=n0modm所以Ci=nimodmni＋1=

ni/m

例：n=389；m=5n0=389 ；C0=389modm=4n1=389/5=77 ；C1=n1mod5=2n2=77/5=15 ；C2=n2mod5=0n3=15/5=3 ；C3=n3mod5=3所以389=3×53＋2×5＋4=（3024）5

3最大公因數(shù)公因數(shù)：兩個(gè)整數(shù)a，b的公因數(shù)定義為能同時(shí)整除a，b的所有整數(shù)。

3為6的因子，記為3|6，3除盡6任意的a|b，a|c，稱a為b，c的公因子

最大公因數(shù)：a與b的公因數(shù)中能被所有a，b的公因數(shù)整除的正整數(shù)，記為gcd(a，b)?；ニ兀ɑベ|(zhì)）：兩個(gè)整數(shù)稱為互素的，如果它們除了1以外沒有其他的公因數(shù)，即gcd(a,b)=1。定理：若a=b·q+r，則gcd（a,b）=

gcd（b,r）

證明：d=（a,b），d’=（b,r）d|a–bq

d|r，d為b,r的公因數(shù)；d|d’

d’=h·dd’|b·q+r

d’|a，d’為a,b的公因數(shù)；d’|d

d=k·d所以k·h=1k=h=

1；

最大公因數(shù)的求法：輾轉(zhuǎn)相除法例如：求gcd(15,36)36=15

2+615=6

2+36=3

2+0因此，gcd(15,36)=3原理：若a

b(modc)，則gcd(a,c)=gcd(b,c)這里，gcd(15,36)=gcd(15,6)=gcd(6,3)=3求最大公因數(shù)的Euclid算法4乘法逆元素求x，滿足(a·x)modn=1,即xa-1(modn)當(dāng)a與n互素時(shí),方程xa-1(modn)有唯一解；當(dāng)a與n不互素時(shí),此方程無解。如果n為素?cái)?shù)，則從1到n-1的任意整數(shù)都與n互素，即在1到n-1之間都恰好有一個(gè)關(guān)于模n的乘法逆元。求乘法逆元：擴(kuò)展的Euclid算法例：求5關(guān)于模14的乘法逆元輾轉(zhuǎn)相除：14=52+4

5=4+1逆推：1=5-4=5-（14-52）=53-14因此，5關(guān)于模14的乘法逆元為3。5Fermat小定理及歐拉函數(shù)Fermat小定理：如果m為素?cái)?shù)，a不能被m整除，則am-1

1(modm)模n的簡(jiǎn)化剩余集：模n的完全剩余集的一個(gè)子集，其中每個(gè)元素與n互素。歐拉函數(shù)：記為(n)，為模n的簡(jiǎn)化剩余集中元素的個(gè)數(shù)。如果n是素?cái)?shù)，則(n)=n-1設(shè)n=p1r1p2r2…pmrm,其中p1,p2,…,pm是n的素?cái)?shù)因子,則(n)=n(1-1/p1)(1-1/p2)…(1-1/pm)歐拉擴(kuò)展的Fermat小定理：如果gcd(a,n)=1，則a(n)modn=1。6中國(guó)剩余定理定理：如果n的素?cái)?shù)因子分解式為p1

p2

…

pt，則一組方程(xmodpi）=ai，其中i=1,2,…,t，有唯一解x，其中x小于n（其中某些pi可能相等）。例：今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？xmod3=2xmod5=3xmod7=2定理：令d1，d2，…,dt為兩兩互素，并令n=d1d2…dt，則

xmoddi

xi(i=1,…,t)在[0，n-1]范圍內(nèi)有公共解x：x=

modn其中：mi=n/di，yi=mi-1moddi解法：令a1=2，a2=3，a3=2，p1=3，p2=5，p3=7，n=p1

p2

p3=105，M1=n/p1=35,M2=n/p2=21,M3=n/p3=15求解35·

x1mod3=1,得x1=2求解21·

x2mod5=1,得x2=1求解15·

x3mod3=1,得x3=1則x=(M1

·x1

·a1+M2

·x2

·a2+M3

·x3

·a3)modn=(35

2

2+21

1

3+15

1

2)mod105=233mod105=23孫子定理的應(yīng)用：3xmod10=1解：10=2

5，3x1mod2=1and3x2mod5=1x1=3

(2)-1mod2=1,m1=5,m1-1=5

(2)-1mod2=1x2=3

(5)-1mod5=2,m2=2,m2-1=2

(5)-1mod5=3所以

x=（1×5×1＋2×2×3）mod10=77二次剩余定義：設(shè)p為素?cái)?shù)，a>0且a<p，如果存在某個(gè)x，滿足x2

a(modp)，則稱a為模p的二次剩余；否則稱a為模p的非二次剩余。8Legendre（勒讓得）符號(hào)記為L(zhǎng)(a,p)，其中a為任意整數(shù)，p為大于2的素?cái)?shù)。定義：L(a,p)=0，如果a能被p整除；L(a,p)=1，如果a是模p的二次剩余；L(a,p)=-1，如果a是模p的非二次剩余；計(jì)算：L(a,p)=a(p-1)/2modp計(jì)算法則（略）9Jacobi（雅各比）符號(hào)記為J(a,n)，是Legendre符號(hào)的擴(kuò)展，其中a為任意整數(shù)，而n為任意奇數(shù)。定義：J(a,n)只對(duì)n為奇數(shù)時(shí)有意義J(0,n)=0如果n為素?cái)?shù)，且n|a，則J(a,n)=0如果n為素?cái)?shù)，且a是模n的二次剩余，則J(a,n)=1如果n為素?cái)?shù)，且a是模n的非二次剩余，則J(a,n)=-1如果n是合數(shù)，則J(a,n)=J(a,p1)×J(a,p2)×…×J(a,pm)，其中將n因數(shù)分解為p1×p2×…×pmJacobi符號(hào)的計(jì)算（略）Blum整數(shù)：若p和q為兩個(gè)素?cái)?shù)，且都與3模4同余，則n=pq稱為Blum整數(shù)。若n為Blum整數(shù)，則每個(gè)模n的二次剩余恰好有4個(gè)平方根，其中一個(gè)也是一個(gè)二次剩余，稱為原平方根。例如，139的模437的原平方根為24，另三個(gè)平方根為185，252和413。10生成元定義：如果p為素?cái)?shù)，g<p，如果對(duì)每個(gè)b從1到p-1，存在a，使ga

b(modp)，則g為模p的生成元。例：p=11，2為模11的生成元生成元的測(cè)試

素?cái)?shù)q,q|p-1,s.tg(p-1)/qmodp=1,則g不為p的生成元

11有限域中的計(jì)算有限域：元素個(gè)數(shù)有限的域，也叫伽羅瓦（Galois）域。在有限域中，非0數(shù)的加、減、乘、除都有定義。加法單位元是0，乘法單位元是1，每個(gè)非0元素都有一個(gè)唯一的乘法逆元。有限域中運(yùn)算滿足交換律、結(jié)合律和分配律。有限域中元素個(gè)數(shù)為素?cái)?shù)或素?cái)?shù)的乘方：設(shè)p為素?cái)?shù)，則有限域可記為GF(p)或GF(pn)。不可約多項(xiàng)式：一個(gè)多項(xiàng)式如果除了1和本身外，不能分解成其他多項(xiàng)式的乘積形式，則成為不可約多項(xiàng)式。本原多項(xiàng)式：一個(gè)有限域內(nèi)的生成元多項(xiàng)式，其系數(shù)是互素的。在GF(qn)中，所有運(yùn)算都是模p(x)的運(yùn)算，其中p(x)是n階不可約多項(xiàng)式。GF（pn）表示形式如：a=an-1xn-1+…+a1x+a0,其中ai是modp的整數(shù)。也表示：an-1an-2…a1a0一般研究GF（2n），如GF（25）：a(x)=x4+x3+1表示11001。若p（x）不能為次數(shù)小于n的多項(xiàng)式之積，則p（x）稱既約多項(xiàng)式。

二元多項(xiàng)式系數(shù)的運(yùn)算：（U+V）mod2=UV=0or1U－V=UVU·V=UV例：GF（25）：a(x)=x4+x2+1,b(x)=x3+x2a＋b=10101+01100=11001例：a=101，p（x）=x3+x+1，GF（23），求（a

a）modp（x）a

a=10001，p（x）=x3+x+1=1011如果p（x）為GF（2n）的既約多項(xiàng)式，則

（p（x））=2n－1。

例：a=100，p=1011，GF（23），求a-1

練習(xí)：a=011，p（x）=1011，GF（23），求a-1

素?cái)?shù)的產(chǎn)生因數(shù)分解：對(duì)一個(gè)數(shù)進(jìn)行因數(shù)分解，是指找出這個(gè)數(shù)的素?cái)?shù)因子。素?cái)?shù)的產(chǎn)生:1.Solovay-Strassen方法2.Lehmann法3.Rabin-Miller法4.實(shí)際應(yīng)用5.強(qiáng)素?cái)?shù)1Solovay-Strassen方法用Jacobi符號(hào)來測(cè)試p是否為素?cái)?shù)：（1）選擇一個(gè)隨機(jī)數(shù)a，a<p；（2）如果gcd(a,p)1，則p是合數(shù)，停止檢測(cè)；（3）計(jì)算i=a(p-1)/2modp；（4）計(jì)算Jacobi符號(hào)J(a,p)；（5）如果iJ(a,p)，則p不是素?cái)?shù)；（6）如果i=J(a,p)，則p不是素?cái)?shù)的概率小于50%。對(duì)t個(gè)不同的隨機(jī)數(shù)a，重復(fù)進(jìn)行這個(gè)測(cè)試。能通過所有t個(gè)測(cè)試的奇數(shù)是合數(shù)的概率小于1/2t。2Lehmann法測(cè)試p是否為素?cái)?shù)：（1）選擇一個(gè)小于p的隨機(jī)數(shù)a；（2）計(jì)算a(p-1)/2modp；（3）如果a(p-1)/2modp1或－1(modp)，則p不是素?cái)?shù)；（4）如果a(p-1)/2modp＝1或－1(modp)，則p不是素?cái)?shù)的概率小于50%。3Rabin-Miller法選擇一個(gè)隨機(jī)數(shù)p，進(jìn)行測(cè)試。計(jì)算b，其中b是能整除p-1的2的次方數(shù)（即2b是指整除p-1的最大的2的冪），然后計(jì)算m，使得p=1+2b*m。（1）選擇一個(gè)隨機(jī)數(shù)a，使a小于p；（2）令i=0，Z=ammodp；（3）如果Z=1，或Z=p-1，則p可能是素?cái)?shù)，通過了檢測(cè)；（4）如果i>0，且Z=1，則p不是素?cái)?shù)；（5）令i=i+1，如果i<b且Z