密碼學(xué)數(shù)學(xué)知識(shí)

第五章 公鑰密碼*1公鑰密碼數(shù)論簡(jiǎn)介公鑰密碼體制的基本概念RSA算法橢圓曲線密碼體制12/15/20202數(shù)論簡(jiǎn)介*3模運(yùn)算12/15/20204

設(shè)n是一正整數(shù),a是整數(shù),若

a=qn+r,0≤r<n,則a

mod

n=r

若(a

mod

n)=(b

mod

n),稱為a,b模n同余，記為a≡b

mod

n

稱與a模n同余的數(shù)的全體為a的同余類，記為[a]，a稱為這個(gè)同余類的代表元素模運(yùn)算12/15/20205同余的性質(zhì)若n|(a-b)，則a≡b

mod

n(a

mod

n)≡(b

mod

n),則a≡b

mod

na≡b

mod

n，則b≡a

mod

na≡b

mod

n，b≡c

mod

n，則a≡c

mod

n求余運(yùn)算a

mod

n將a映射到集合{0,1,…,n-1},求余運(yùn)算稱為模運(yùn)算模運(yùn)算12/15/20206模運(yùn)算的性質(zhì)[(a

mod

n)+(b

mod

n)]

mod

n=(a+b)

mod

n[(a

mod

n)-(b

mod

n)]

modn=(a-b)

mod

n[(a

mod

n)×(b

mod

n)]

mod

n=(a×b)

mod

n模運(yùn)算12/15/20207例：Z8={0,1,2,3,4,5,6,7},模8加法和乘法＋01234567001234567112345670223456701334567012445670123556701234667012345770123456×01234567000000000101234567202460246303614725404040404505274163606420642707654321模運(yùn)算12/15/20208

若x+y=0

mod

n,y為x的加法逆元。每一元素都有加法逆元

若對(duì)x，有xy=1

mod

n，稱y為x的乘法逆元。在上例中，并非所有x都有乘法逆元定義Zn={0,1,..,n-1}為模n的同余類集合模運(yùn)算12/15/20209Zn上模運(yùn)算的性質(zhì)交換律（x+w)

mod

n=(w+x)

mod

n(x×w)

mod

n=(w×x)

mod

n結(jié)合律[(x+w)+y]

mod

n=[x+(w+y)]

mod

n[(x×w)

×y]

mod

n=[x×(w×y)]

mod

n分配律[w×(x+y)]

mod

n=[w×x+w×y)]

mod

n模運(yùn)算單位元(0+w)

mod

n=w

mod

n(1×w)

mod

n=w

mod

n

加法逆元：對(duì)w∈Zn,有z∈Zn，滿足

w+z=0

mod

n,z為w的加法逆元，記為

z=-w。加法的可約律(a+b)≡(a+c)mod

n,則b≡c

mod

n對(duì)乘法不一定成立，因?yàn)槌朔嬖灰欢ù嬖凇?2/15/202010模運(yùn)算

定理:設(shè)a∈Zn,gcd(a,n)=1,則a在Zn有逆元證明思路：用反證法證明a和Zn中任何兩個(gè)不同的數(shù)相乘結(jié)果都不相同從1得出a×Zn=Zn,因此存在x∈Zn,使

a×x=1

mod

n

設(shè)p為素?cái)?shù)，Zp中每一個(gè)非零元素都與p互素，因此有乘法逆元，有乘法可約律12/15/2020

(a×b)=(a×c)

mod

n,

b=c

mod

n11費(fèi)爾瑪定理和歐拉定理12/15/202012費(fèi)爾瑪定理若p是素?cái)?shù)，a是正整數(shù)且gcd(a,p)=1，則ap-1≡1

mod

p證明：gcd(a,p)=1,則a×Zp=Zp,a×(Zp-{0})=Zp-{0}{a

mod

p,2a

mod

p,…,(n-1)a

mod

p}

={0,1,…,p-1}(a

mod

p)

×(2a

mod

p)

×…×(n-1)a

mod

p=(p-1)!

mod

p(p-1)!

×ap-1=(p-1)!

mod

p(p-1)!與p互素，所以乘法可約律，ap-1=1

mod

p費(fèi)爾瑪定理和歐拉定理12/15/202013歐拉函數(shù)

設(shè)n為一正整數(shù)，小于n且與n互素的正整數(shù)的個(gè)數(shù)稱為n的歐拉函數(shù)，記為j(n)

定理：若n是兩個(gè)素?cái)?shù)p和q的乘積，則

j(n)＝

j(p)j(q)=(p-1)(q-1)歐拉定理若a和n互素,則aj(n)=1

mod

n素性檢驗(yàn)12/15/202014

引理：如果p為大于2的素?cái)?shù)，則方程x2≡1mod

p的解只有和x≡1和x≡-1證明:x2≡1

mod

p x2

-1

≡0

mod

p(x+1)(x-1)≡0

mod

p所以,p|(x+1)或p|(x-1)或p|(x+1)且p|(x-1) 存在k,j，x+1=kp,

x-1=jp2=(k-j)p,

這是不可能的。

引理的逆命題：若方程x2≡1

mod

p有唯一解

x不為+1或-1，p不是素?cái)?shù)素性檢驗(yàn)12/15/202015Miller-Rabin素性概率檢測(cè)法

n為待檢測(cè)數(shù)，a為小于n的整數(shù)，將n-1表示為二進(jìn)制形式bkbk-1…b0,d賦初值為1，算法核心如下for

i=k

downto

0

do{x

d;d

(d×d)

mod

n;if

d=1

and

(x≠1)and(x≠n-1)

then

return

Falseif

bi=1the

d

(d×a)

mod

n}if

d

≠1

then

return

False;return

True若返回False,n不是素?cái)?shù),若返回True,有可能是素?cái)?shù)素性檢測(cè)12/15/202016

For循環(huán)結(jié)束,有d≡an-1

mod

n.由費(fèi)爾瑪定理,若n為素?cái)?shù),d為1.所以d≠1，則d不是素?cái)?shù)

n-1≡-1

mod

n,所以x≠1和x≠n-1指x2≡1mod

n有非±1的根,n不是素?cái)?shù)

該算法對(duì)s個(gè)不同的a，重復(fù)調(diào)用，如果每次都返回true，則n是素?cái)?shù)的概率大于等于1-2-s歐幾里德算法12/15/202017求兩個(gè)正整數(shù)的最大公因子

兩個(gè)正整數(shù)互素，可以求一個(gè)數(shù)關(guān)于另一個(gè)數(shù)的乘法逆元

性質(zhì):對(duì)任意非負(fù)整數(shù)a和正整數(shù)b,有g(shù)cd(a,b)=gcd(b,a

mod

b)證明：a=kb+r≡r

mod

b a

mod

b=a-kb設(shè)d|a,d|b,所以d|kb.由d|a和d|kb，得d|(a

mod

b)故d是b和a

mod

b的公因子。a,b以及b,a

mod

b公因子集合相同，故最大公因子也相同Euclid(f,d)

f>d12/15/202018X

f;Y

d;If

Y=0

then

return

X=gcd(f,d)R=X

mod

YX=Y;Y=RGoto

2歐幾里德算法例:gcd(55,22)=gcd(22,11)=gcd(11,0)=11歐幾里德算法求乘法逆元

若gcd(a,b)=1,b在模a下有乘法逆元(設(shè)

b<a)。即存在x<a,bx≡1

mod

aExtended

Euclid(f,d)

(f>d)1.（X1

X2

X3)

(1,0,f);(Y1Y2

Y3)

(0,1,d);If

Y3=0,

then

return

X3=gcd(f,d);no

inverse;If

Y3=1,

then

return

X3=gcd(f,d);Y2=d-1

mod

f;Q=X3

div

Y3;(X1-QY1,X2-QY2,X3-QY3);(Y1Y2

Y3);(T1

T2

T3);(T1

T2

T3)(X1

X2

X3)(Y1Y2

Y3)12/15/20208.Goto

219中國(guó)剩余定理

如果已知某個(gè)數(shù)關(guān)于一些量量互素的數(shù)的同余類集，就可以重構(gòu)這個(gè)數(shù)定理(中國(guó)剩余定理)：設(shè)m1,m2,…,mk是兩兩互素的正整數(shù)，則一次同余方程組對(duì)模M有唯一解12/15/202020中國(guó)剩余定理12/15/202021

中國(guó)剩余定理可以將一個(gè)很大的數(shù)x表示為一組較小的數(shù)(a1,…ak)

例：x≡1

mod

2,x≡2

mod

3,x≡3

mod5

x≡5

mod

7,求x

解：M＝2×3×5×7＝210，M1=105,M2=70,M3=42,M4=30,(Mi=M/mi),可以求得e1=1,e2=1,e3=3,e4=4,所以

x=105×1×1＋70×1×2＋42×3×3＋30×4×5

mod

210＝173離散對(duì)數(shù)12/15/202022求模下的整數(shù)冪

根據(jù)歐拉定理，若gcd(a,