现代密码学第6章：公钥密码学

1公钥密码《现代密码学》第6章2本章主要内容1、数论简介2、公钥密码体制的基本概念3、RSA算法4、背包密码体制5、Rabin密码体制6、椭圆曲线密码体制习题3数论是密码学特别是公钥密码学的基本工具，本章首先介绍密码学中常用的一些数论知识，然后介绍公钥密码体制的基本概念和几种重要算法。1.数论简介4数论介绍数论概念:研究“离散数字集合”运算是“+”,“×”例:整数:5+9=14;5×3=5+5+5=15多项式:x2+1+x=x2+x+1;x×x2+1=x3+x5运算概念运算:模数运算模多项式运算进一步运算:指数运算,逆运算理解公钥算法的基础6整除对整数b!=0及a,如果存在整数m使得a=mb,称b整除a,也称b是a的因子记作b|a例1,2,3,4,6,8,12,24整除2471.因子设a，b(b≠0)是两个整数，如果存在另一整数m，使得a=mb，则称b整除a，记为b|a，且称b是a的因子。1.1素数和互素数8整数具有以下性质：①a|1，那么a=±1。②a|b且b|a，则a=±b。③对任一b(b≠0)，b|0。④b|g，b|h，则对任意整数m、n有b|(mg+nh)。1.1素数和互素数9这里只给出④的证明，其他3个性质的证明都很简单。性质④的证明：由b|g，b|h知，存在整数g1、h1，使得g=bg1,h=bh1所以mg+nh=mbg1+nbh1=b(mg1+nh1),因此b|(mg+nh)。1.1素数和互素数102.素数称整数p(p1)是素数，如果p的因子只有±1，±p。任一整数a(a1)都能惟一地分解为以下形式：其中p1p2…pt是素数，ai0(i=1,…,t)。例如91=7×11，11011=7×112×131212ttappp1.1素数和互素数11这一性质称为整数分解的惟一性，也可如下陈述：设P是所有素数集合，则任意整数a(a1)都能惟一地写成以下形式：其中ap≥0,等号右边的乘积项取所有的素数，然而大多指数项ap为0。相应地，任一正整数也可由非0指数列表表示。例如：11011可表示为{a7=1,a11=2,a13=1}。两数相乘等价于对应的指数相加，即由k=mn可得：对每一素数p,kp=mp+np。而由a|b可得：对每一素数p,ap≤bp。这是因为pk只能被pj(j≤k)整除。papPap1.1素数和互素数123.互素数称c是两个整数a、b的最大公因子，如果①c是a的因子也是b的因子，即c是a、b的公因子。②a和b的任一公因子，也是c的因子。表示为c=gcd(a,b)。1.1素数和互素数13由于要求最大公因子为正，所以gcd(a,b)=gcd(a,-b)=gcd(-a,b)=gcd(-a,-b)。一般gcd(a,b)=gcd(|a|,|b|)。由任一非0整数能整除0，可得gcd(a,0)=|a|。如果将a，b都表示为素数的乘积，则gcd(a,b)极易确定。例如：300=22×31×52；18=21×32gcd(18,300)=21×31×50=6一般由c=gcd(a,b)可得：对每一素数p，cp=min(ap,bp)。1.1素数和互素数14由于确定大数的素因子不很容易，所以这种方法不能直接用于求两个大数的最大公因子，如何求两个大数的最大公因子在下面介绍。如果gcd(a,b)=1，则称a和b互素。1.1素数和互素数15整数互素整数a,b互素是指它们没有除1之外的其它因子8与15互素8的因子1,2,4,815的因子1,3,5,151是唯一的公因子16素数与不可约多项式素数:只有因子1和自身1是一个平凡素数例2,3,5,7是素数,4,6,8,9,10不是素多项式或不可约多项式irreducible:不可写成其他因式的乘积x2+x=x×x+1是非不可约多项式;x3+x+1是不可约多项式17一些素数200以内的素数:235711131719232931374143475359616771737983899710110310710911312713113713914915115716316717317918119119319719918素数分解把整数n写成素数的成绩分解整数要比乘法困难整数n的素数分解是把它写素数的乘积eg.91=7×13;3600=24×32×5219设n是一正整数，a是整数，如果用n除a，得商为q，余数为r，则a=qn+r,0≤rn,其中x为小于或等于x的最大整数。用amodn表示余数r，则。如果(amodn)=(bmodn)，则称两整数a和b模n同余，记为a≡bmodn。称与a模n同余的数的全体为a的同余类，记为[a]，称a为这个同余类的表示元素。注意：如果a≡0(modn)，则n|a。aqnmodaanann1.2模运算20同余有以下性质：①若n|(a-b)，则a≡bmodn。②(amodn)≡(bmodn)，则a≡bmodn。③a≡bmodn,则b≡amodn。④a≡bmodn,b≡cmodn,则a≡cmodn。从以上性质易知，同余类中的每一元素都可作为这个同余类的表示元素。1.2模运算21求余数运算（简称求余运算）amodn将整数a映射到集合{0,1,…,n-1}，称求余运算在这个集合上的算术运算为模运算，模运算有以下性质：①[(amodn)+(bmodn)]modn=(a+b)modn。②[(amodn)-(bmodn)]modn=(a-b)modn。③[(amodn)×(bmodn)]modn=(a×b)modn。1.2模运算22性质①的证明：设（amodn）=ra，(bmodn)=rb，则存在整数j、k使得a=jn+ra，b=kn+rb。因此(a+b)modn=[(j+k)n+ra+rb]modn=(ra+rb)modn=[(amodn)+(bmodn)]modn（证毕）性质②、③的证明类似。1.2模运算23例：设Z8={0,1,…,7}，考虑Z8上的模加法和模乘法，结果如表4.1所示。从加法结果可见，对每一x，都有一y，使得x+y≡0mod8。如对2，有6，使得2+6≡0mod8，称y为x的负数，也称为加法逆元。对x，若有y，使得x×y≡1mod8，如3×3≡1mod8，则称y为x的倒数，也称为乘法逆元。本例可见并非每一x都有乘法逆元。1.2模运算24一般地，定义Zn为小于n的所有非负整数集合，即Zn={0,1,…,n-1}，称Zn为模n的同余类集合。其上的模运算有以下性质：①交换律(w+x)modn=(x+w)modn(w×x)modn=(x×w)modn②结合律[(w+x)+y]modn=[w+(x+y)]modn[(w×x)×y]modn=[w×(x×y)]modn1.2模运算25③分配律[w×(x+y)]modn=[w×x+w×y]modn④单位元(0+w)modn=wmodn(1×w)modn=wmodn⑤加法逆元对w∈Zn，存在z∈Zn，使得w+z≡0modn，记z=-w。1.2模运算26此外还有以下性质：如果(a+b)≡(a+c)modn，则b≡cmodn，称为加法的可约律。该性质可由(a+b)≡(a+c)modn的两边同加上a的加法逆元得到。1.2模运算27然而类似性质对乘法却不一定成立。例如6×3≡6×7≡2mod8，但37mod8。原因是6乘以0到7得到的8个数仅为Z8的一部分，见上例。即如果将对Z8作6的乘法6×Z8（即用6乘Z8中每一数）看作Z8到Z8的映射的话，Z8中至少有两个数映射到同一数，因此该映射为多到一的，所以对6来说，没有惟一的乘法逆元。但对5来说，5×5≡1mod8，因此5有乘法逆元5。仔细观察可见，与8互素的几个数1，3，5，7都有乘法逆元。这一结论可推广到任一Zn。1.2模运算28定理4.1设a∈Zn，gcd(a,n)=1，则a在Zn中有乘法逆元。证明：首先证明a与Zn中任意两个不相同的数b、c（不妨设cb）相乘，其结果必然不同。否则设a×b≡a×cmodn，则存在两个整数k1,k2，使得ab=k1n+r，ac=k2n+r，可得a(b-c)=(k1-k2)n，所以a是(k1-k2)n的一个因子。1.2模运算29又由gcd(a，n)=1，得a是k1-k2的一个因子，设k1-k2=k3a，所以a(b-c)=k3an，即b-c=k3n，与0cbn矛盾。所以|a×Zn|=|Zn|，又知a×ZnZn，所以a×Zn=Zn。因此对1∈Zn，存在x∈Zn，使得a×x≡1modn，即x是a的乘法逆元。记为x=a-1。（证毕）1.2模运算30设p为一素数，则Zp中每一非0元素都与p互素，因此有乘法逆元。类似于加法可约律，可有以下乘法可约律：如果(a×b)≡(a×c)modn且a有乘法逆元，那么对(a×b)≡(a×c)modn两边同乘以a-1，即得b≡cmodn1.2模运算31模算式除法取余运算同余(congruence)fora=bmodn如果a,b除以n,余数相同eg.100=34mod11b叫做a模n的剩余通常0=b=n-1eg.-12mod7=-5mod7=2mod7=9mod7可以进行整数运算32模运算举例-21-20-19-18-17-16–15-14-13-12-11-10-9-8-7-6-5-4-3-2-101234567891011121314151617181920212223242526272829303132333433模算术运算加法a+bmodn减法a-bmodn=a+(-b)modn34乘法\除法乘法a.bmodn重复加法除法a/bmodn乘以b的逆元:a/b=a.b-1modn如果n是素数,b-1modn存在s.tb.b-1=1modn例.2.3=1mod5hence4/2=4.3=2mod535模递归运算•模递归运算是“模除求余”•例.r=amodn计算a=d.n+r•33mod7=4.7+5;得数是5•通常,r取正数•例-18mod7=-3.7+3;答案是3•a+/-bmodn=[amodn+/-bmodn]modn36费尔玛(Fermat)定理和欧拉(Euler)定理在公钥密码体制中起着重要作用。1.3费尔玛定理和欧拉定理371.费尔玛定理定理4.2(Fermat)若p是素数，a是正整数且gcd(a,p)=1，则ap-1≡1modp。证明：由4.1.2的讨论知当gcd(a,p)=1时,a×Zp=Zp，其中a×Zp表示a与Zp中每一元素做模p乘法。又知a×0≡0modp，所以a×Zp-{0}=Zp-{0}，a×(Zp-{0})=Zp-{0}。即{amodp,2amodp,…,(p-1)amodp}={1,2,…,p-1}费尔玛定理38所以a×2a×…×(p-1)a≡[(amodp)×(2amodp)×…×((p-1)amodp)]modp≡(p-1)!modp另一方面a×2a×…×(p-1)a=(p-1)!ap-1因此(p-1)!ap-1≡(p-1)!modp由于(p-1)!与p互素，因此(p-1)!有乘法逆元，由乘法可约律得ap-1≡1modp。（证毕）费尔玛定理39Fermat定理也可写成如下形式：设p是素数，a是任一正整数，则ap≡amodp。费尔玛定理402.欧拉函数设n是一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为φ(n)。例如：φ(6)=2，φ(7)=6，φ(8)=4。若n是素数，则显然有φ(n)=n-1。欧拉定理41定理4.3若n是两个素数p和q的乘积，则φ(n)=φ(p)×φ(q)=(p-1)×(q-1)。证明：考虑Zn={0,1,…,pq-1}，其中不与n互素的数有3类，A={p,2p,…,(q-1)p}，B={q,2q,…,(p-1)q},C={0}，且A∩B=Φ，否则ip=jq，其中1≤i≤q-1，1≤j≤p-1,则p是jq的因子，因此是j的因子，设j=kp，k≥1。则ip=kpq，i=kq，