密码学课件：密码学基础补充知识.pdf

群的定义定义（群）设三元组（G,1）中G为集合，为 集合G上的二元运算，1为G中的一个元。若（G,1）满足：G1（乘法结合率）G2（单位元）G3（逆元）G4（交换）ab 2)=(aOb)2 a5b5c e G1 8=aDL=a a g G对awG,有akG,使得ah=aAl aDb=bD a5b e G满足G1条件的称为半群理的例子篱Z+0),Z为整数，+为整数加法，0为整数零二鬻十,0)为交换群2.(Z2“，Zn为0.nT整数,n为模n整数加法，0为整数零$2 5S2 S2 z$C,.11 11 y 11 11鬻，n，。)为群W,X,1),Z为整数，X为整数乘法，1为整数l,(Z,x,l)不是群K二八二大益二G)(Z*n，,l),Z*n为l.nT整数，电为模n整数乘法，0为整数零 叫般不成群，但当n是素数时成群颖普K寸寸oi-CMc oc oc o寸oi-CM(NCMc o寸oT-CMc o寸oooi-CMc o寸g oi-CMc o寸寸门7 一OTN5的逆运算已知X WZ5,且35乂=2,求X的值？x=2-3=-1?亿5，%1)Z*=1,233软01234011234224133314244321软的逆运算已知X G Z*5,且3区求X的值？X二 1,5循环群由一个元素a生成的群是由元a的所有乘累组a。成的，用表示，a叫做生成元am.an=a m+n5 a0=e5 a-n=(a1)n蒙个群如果是由其中一个元素生成的就叫做循环群。藜如a的所有乘幕都互不相等，则循环群是无穷群。例如a的乘塞中有相等的，如果n是使an=e成立的最小正整数,氮循环群只含有n个元oO a1 an-1d,d,.,d攀a的阶数是nZt上的离散对数问题设P为素数，在亿*p,5,l）中，可以定义 r Jram=a 区 a （8）a（m个a,m是整数）Jr r r对已知的a,b g Z*。,求整数x,使Jrax=b的问题称为Z之上的离散对数问题。迄今为止，离散对数问题尚无快速算法，要想X唯一，对a也有要求0 12 3 4 5 6 7234567023456701346701245670i35670I24670123457012456(a)Addition modulo 8(b)Multiplication modulo 8(c)Addiliw and mulliplicauve inverses modulo 85.1指数及其基本性质定义设ml是整数，Q是与m互素的正整数.则使得=1(mod 7几)成立的最小正整数e叫做a对模rn的指数记作ordm().若Q对模m的指数是夕(m),则a叫做模m的原根.例1设整数m=7,这时例7)=6.我们有a-3-2-1123ordm（Q）362136因此，-2,3是模7的原根.但2,-3不是模7的原根.例2设整数m=10=2.5,这时夕(10)=4.我们有a-3-113。小4214因此，3,3是模10的原根.例3设整数m=15=35,这时以15)=8.我们有a-7-4-2-11247ordm（Q）42421424因此，没有模15的原根.例4设整数m=9=32,这时例9)=6.我们有a-4-2-1124ordm（Q）632163因此，-4,2是模9的原根.定理5设m 1是整数.如果模m存在一个原根孔则模m有3（m）个不同的原根.证设g是模m9,g2,.，gdm）构成模的一个原根.根据定理2,以m）个整数 m的一个简化剩余系.又根据定理4的推论，我们有9d是模的原根当且仅当“（】）=1.因为这样的d共有 个，所以模m有3（m）个不同的原根.定理7模m的原根存在的充分必要条件是m=2,4,p%2 p%其 中p是奇素数.定义设m是大于1的整数，g是模7H的一个原根.设Q是一个 与m互素的整数.则存在唯一的整数厂使得gr=a(mod rn),1 r x2S5a3xx3：/V-Z-4zzC k1/Oi/O oSxZ$Q22aQ;:/T2SC$M2aQz三斐斐斐7X xZy44Z，人,入,，zzvv,xv*4z,HM入标,二q 1二公,1./人,.,公.公.403须 必瑞过着 享个味 共这意 立方道 建因信 方是的。双这样送 信 这传 通船常式，问通方)刖：S，S 之难道理 现困 出较的以 制比全使 体个一女信 码一 s 雷是一门 钟W-要互 公一需由 在钥程要士口。钥穆遭的 一骸出 日援提 就心 点相1m 凭现ell 什霞阿 显诒e?一道Di的 i女点 鳗而一 密无这 钥以现 公可实雄Protocol 8.1:The Dif f ie-He I Im an Key Exchange ProtocolCOMMON INPUTOUTPUT(pz g):p is a large prime,g is a generatorF*element in P.F*An element in P shared between Alice andBob.1.Alice picks a U lf p-1);computes gaig a(mod p)sends ga to Bob;2.Bob picks b tU lf p-1);computes ga_g b(mod p);sends gb to Alice;Alice computes 卜 一九(modp);Bob computes 卜-%(modp).p=43,g=3 这时他们公开(p,g)=(43,3)为了协商一个密钥，Alic e选择一个秘密指 数8,把3八8=25(mod43)发送给Bob。Bob随机选取他的秘密指数37,把3八37=20(mod43)发送给Alic e,他们协商的密 钥就是9=20A8=25A37(mod43)要注意这个协议不支持对协商密钥的认证功能。处于Alic e和Bob通信中间的主动攻击者能够 操纵这个协议的消息以达到成功的攻击，称为中间人攻击。公钥加密体制环的定义定义 交换环or是指带有两个叫做加法和乘法运算的集合，满足:对所有a,66R有a+6=o+a;(ii)对所有 a,b,cR 有 a+(6+c)=(a+6)+c;(iii)存在0丘1?使对所有0 6火有0+a=a；(iv)对任意 aCR,存在 aGR 使 a+a=O;(v)对所有 a,bgR 本 ab=ba；(vi)对所有 a,b,cGR 有 a(6c)=(ab)c；(vii)存在1 GR,叫做单位元O,满足对每个aGK有la=a;(viii)对所有 a,b,cCR 有 a(b+c)=ab+ac.f艮域令如果一个环F满足乘法为群，贝UF称为域yitvvvwitv攀简单的说，在域中可以自由进行加减乘除四则运算;令元素个数有限的域称为有限域，又称为伽 罗瓦域（GF（P,n）有限域F的元素个数必须是素数或素数的整数幕（伽罗瓦）若P是素数，九是正整数，则存在恰有个元素的域.|伽罗瓦(E Galois,18111832)。系数是域F的元素，这样的多项式集合是一个环,称为多项式环对域上的多项式进行多项式运算时，除法运算 是可能的。即使系数集合是一个域，多项式除法也不一定 是整除。一般来说，除法会产生一个商式和一 个余太f(x)=q(x)g(x)+r(x)1 a)Addition000 001 010 011 100 101 IIO 111x 0 1 2 3 4 5 6 700000000012345670246317S0彳657412043762510514276)067I _|532 二40752 164与 3_00111225336447557663774(b)Multiplication(c)Additive and multiplicativeinvents熟多项式算法.鎏所有阶数小于等于1,系数在Zp上的多项式，共有an个 鬻P是素数Consider the set S of all polynomials of degr ee n 1 or less over the field Zp.Thus,each polynomial has the for m一 1/(x)=册_1+*_27+(X+劭=/，=0wher e each a；takes on a value in the set 0,1,.,p 1.Ther e ar e a total of pn differ ent polynomials in S.For p=3 and n=2,the 32=9 polynomials in the set are0X2x1X+12x+12x+22x+2For p=2 and n=3,the 23=8 the polynomials in the set are0 x+1X2+X1X2X2+X+1XX2+1裁算规则蠹1.先按照一般多项式运算规则，在做下面处 理 2.系数模P噩3.如果乘积阶大于“1,则用一个阶为n的既 约多项式求模，取余数做结果汽运Ar ithmetic follows the or dinar y r ules of polynomial ar ithmetic using the basic r ules of algebr a,with the following two r efinements.1.2.3.Ar ithmetic on the coefficients is per for med modulo p.That is,we use the r ules of ar ithmetic for the finite field Zp.If multiplication r esults in a polynomial of degr ee gr eater than n 1,then the polynomial is r educed modulo some ir r educible polynomial m(x)of degr ee n.That isz we divide by m(x)and keep the r emainder.For a polynomial f(x)f the r emainder is expr essed as r(x)=4x)mod m(x).The Advanced Encryption Standard(AES)uses arithmetic in the f inite f ield GF(28),with the irreducible polynomial m(x)=x8+x4x3+x+1.Consider the two polynomials/x)=x6+x4+x2+x+l and g(x)=x7+x+1.Thenfx)+g(x)=x6+x4x2+x+l+x7+x+1q x)x g(x)=x13+x11+x9+x8+x，+x7+x5+x3+x2+x+x6+x4+x2+x+l=X13+X11+x9+x8+x6+x5+x44-x3+1Theref ore,以x)x g(x)mod m(x)=x7+x6+1.妻项灰计算AdditionWe have seen that addition of polynomials is per fo r med by adding cor r esponding coefficients,and,in the case of polynomials over Z2 additio n is just the XOR oper ation.So,addition of two polynomials in GF(2n)cor r esponds to a bitwise XOR oper ation.Consider the two polynomials in GF(28)fr om our ear lier example:fx=x6+x4+x2+x+1 and g(x)=x7+x+1.(x6 4-x44-x2+x+1)+(x7+x+1)=x7+x6+x6+x4+x2(polyno mial notation)(01010111)(10000011)5783=(11010100)(binar y notation)=D4(hexadecimal notation)121MultiplicationTher e is no simple XOR oper ation that will accomplish multiplication in GF(2n)However,a r easo nably str aightfor war d,easily implemented technique is available.We will discuss the technique with r efer ence to GF(28)using m(x)=x8+x4+x3+x+1,which is the finite field used in AES.The technique r eadily gener alizes to GF(2n).xs mod/f i(x)=?(x)xs=(x4+k+1)Vow,consider a polynomial in GF(28),which has the for m f(x)=b-/x7+bgx5+bx4+J3X3+b2X2+b1x+bo.If we multiply by x,we haveEquation 4-9x X/(x)=(f t7xs+bp：+b/+by4+/2-v3+h()x)modIf/?7=0,then the r esult is a polynomial of degr ee less than 8,which is alr eady in r educed for m,and no fur ther computation is necessar y.If by=1,then r eduction modulo m(x)is achieved using Equation(4.8):x xx)=(b&(7+bsxe+Z)4X5+djx4+b2x3+bix2+box)+(x4+x3+x+1)It follows that multiplication by x(i.e.z 00000010)can be implemented as a 1-bit left shift followed by a conditional bitwise XOR with(00011011),which r epr esents(x4+x3+x+1).To summar ize,Equation 4-10V x f(x)=（b6b5仇也也2仇友P）ifb7=0(bob5b4b3b2E跖0)(0001 1 01 1)if by=1Multiplication by a higher power of x can be achieved by r epeated application of Equation(4.10).By adding inter mediate r esults,multiplication by any constant in GF(28)can be achieved.In an earlier example,we showed that f or=x6+x4+x2+x+lz g(x)=x7+x+1,and m(x)=x8+x4+x3+x+l/f(x)x g(x)mod m(x)=x7+x6+1.Redoing this in binary arithmetic,we need to compute(01010111)x(10000011).First,we determine the results of multiplication by powers of x:(01010111)x(00000001)=(10101110)(01010111)x(00000100)=(01011100)(00011011)=(01000111)(01010111)x(00001000)=(10001110)(01010111)x(00010000)=(00011100)(00011011)=(00000111)(01010111)x(00100000)=(00001110)(01010111)x(01000000)=(00011100)(01010111)x(10000000)=(00111000)So,(01010111)x(10000011)=(01010111)x(00000001)x(00000010)x(10000000)=(01010111)(10101110)(00111000)=(11000001)which is eq uivalent to x7+x6+1.f如果阶为q的有限域中一个元素g的前q/次 I哥可以生成所有非零元素，则g称为生成元爰在用多项式f(x)定义的有限域中，如果元素b I满足f(b)=O,则b称为多项式的根I定义有限域的不可约多项式的根就是就是I该域的生成元Let us consider the f inite f ield GF(23),def ined over the irreducible polynomial x3+x+1,discussed previously.Thus,the generator g must satisf y fx=g3+g+1=0.Keep in mind,as discussed previously,that we need not f ind a numerical solution to this eq uality.Rather,we deal with polynomial arithmetic in which arithmetic on the coef f icients is perf ormed modulo 2.Theref ore,the solution to the preceding eq uality is g3=gi=g+we now show that g in f act generates all of the polynomials of degree less than 3.We have the f ollowing:g4=g(g3)=g(g+1)=g?+ggs=g&)=g(g2+g)=g3+g2=g2+g+1g6=g(gs)=g(g2+g+l)=g3+g2+g=g2+g+g+l=g2+lg7=g(货)=g(g2+l)=g3+g=g+g+i=i=We see that the powers of g generate all the nonzero polynomials in GF(23).Also,it should be clear that gk=gk mod 7 for any integer k.Table 4.8 shows the power representation,as well as the polynomial and binary representations.Table 4.8.Generator for GF(23)using x3+x+1PowerRepresentationPolynomial RepresentationBinary RepresentationDecimal(Hex)Representation000000g0(=g7)10011g1g0102g2g21004g3g+i0113ff4g2+g1106gsg2+g+11117 Ig6g2+11015This power representation makes multiplication easy.To multiply in the power notation,add exponents modulo 7.For example,g4 x g6=g(10 mod 7)=g3=g+1.The same result is achieved using polynomial arithmetic,as f ollows:we have g4=g2+g and g6=g2+1.Then,(g2+g)x(g2+l)=g4+g3+g2+l.Next,we need to determine(g4+g3+g2+1)mod(g3+g+1)by division:g+1屋+/+、符+/+g2+gg4+陵+gS屋+g+1g+1We get a result of g+1,which agrees with the result obtained using the power representation.是两个整数，其中bwO,则存在两个唯一的整数q和r使得：a=bq+r 0r|b|立B=0,称b整除a,记作b|ad|b则d是a,b的公因子，a,b的最大公因子记作(a,b)iwia,b,c是任意三个不全为零的整数,且a=bq+c,其q中是整数,(a,b)=(b,c)只有1和自身是因子的整数称为素数。除了 1和自身外，还有其他因子的数称为合 数1既不是素数也不是合数舞E整数分为三类：1、素数、合数71定理3设生b,c是三个不全为零的整数.如果a=%+C,其中q 是整数，则(Q4=(b,c)证设 d=(q,&),d!=(6,c),则 da,db.由$1.1 定理 3,dc=a+(因而，d是b,c的公因数.从而，ddf.同理，d是a,b的公因数，d!1都可以表示成素数的乘 积，且在不考虑乘积顺序的情况下，该表达式是唯一的.即n=pPs,pi .ps,其中p,是素数，并且若n=qq。qi 其中%是素数，贝IJ s=t,Qi=Pi,1 i s.A iril 涂咨金宗o I乙十 y v 定义1给定一个正整数两个整数Q：b叫做模7同余,如果ma-b.记作q a 丰 b(mod m).=b(mod m).否则，叫做模m不同余.记作时.例1我们有29三1(mod 7),因为7|29 一 1.同样，27 三 6(mod 7),23 三-5(mod 7).同余的概念常常出现于日常生活中.例如，时针是模12或24小 分针和秒针是模60.ZSaaSxStSQSQS定理1设Q,b是整数，则a=b(mod m)、：9.的充要条件是存在一个整数k使得a=b+km.版是等价关系，即一整数 Q,Q 三 Q(mod m);z=6(mod m),贝ij b 三 q(mod m);a=b(mod m),b=c(mod m),贝lj a=c(mod m).定理4设qi,。2,b2是整数.右Qi三瓦(mod m),a2=&2(mod m),则(i)Qi+02 三仇+I)2(mod m);(ii)Q1Q2=&i&2(mod m).定理 5 若土三 y(mod m),ai=(mod m),0 i f c,则 ao+Qrn=bo+by+bkyk(mod m).例6 2003年5月9日是星期五，问第22003天是星期几?2.2剩余类及完全剩余系因为同余是一种等价关系，所以我们可以借助于同余将全体整数 分类，进而得到整数的一些新性质.这些性质已在信息安全中得到普 遍应用.定理1设m是一个正整数.对任意整数Q,令Ka=c c Z,a=c(mod rn).则i)任一整数必包含在一个中，0 S 丁 W m-1;ii)Ka=Kb的充分必要条件是a=b(mod m).(1)iii)Ka与Kb的交集为空集的充分必要条件是q r b(mod m).定义1定理1中的Ka叫做模m的剩余类.一个剩余类中的任 一数叫做该类的剩余或代表元.若To,F.，Gl是m个整数，并且其中任何两个数都不在同一个剩余类里，则0,.，叫做模 m的一个完全剩余系.例1设正整数m=10.对任意整数Q：集合Ka c c Z,a=c(mod zn)就是模m=10的剩余类.0,1,2,3,4,5,6：7,8,9为模10的一个完全剩余系.10,11,22,33,44,55,66,77,88,99 也为模 10 的一个完全剩余 系.定理2设m是一个正整数.则m个整数成为模m的一个完全剩 余系的充分必要条件是它们模m两两不同余.例2设m是一个正整数,则i）0,1,m-1是模m的一个完全剩余系，叫做模m的最小 非负完全剩余系；ii）1,m-1,m是模m的一个完全剩余系，叫做模m的最 小正完全剩余系；iii一（血-1）,-1,0是模m的一个完全剩余系，叫做模m的最大非正完全剩余系；iv）-m,-（/n-1）,一1是模m的一个完全剩余系，叫做模m 的最大负完全剩余系；v）当m分别为偶数时,m/2,（771 2）/2,，1,0,1,，（7R 2）/2,或（ZM 2）/2,1,0）1,j（771 2）/2,77l/2,是模m的一个完全剩余系；当m分别为奇数时，（771 1）/2,1,0,（771 1）/2是模m的一个完全剩余系，上述两个完全剩余系统称为模的一个 绝对值最小完全剩余系.定理3设m是正整数，Q是满足（Q,m）=1的整数，b是任意 整数.若1遍历模m的一个完全剩余系，则Q，+b也遍历模m的一 个完全剩余系.定义1设m是一个正整数.则m个整数0,1,.，m-1中与 m互素的整数的个数，记作以，n）,通常叫做欧拉（Euler）函数.例 1 设 m=10.则 10 个整数 0,1,2,3,4,5,6,7,8,9 中与 10 互素的整数为1,3,7,9,所以以素）=4.定义2 一个模m的剩余类叫做简化剩余类，如果该类中存在一个 与m互素的剩余.注：这个定义与剩余的选取无关.事实上，我们有定理1设门，/2是同一模m剩余类的两个剩余，则与m互素 的充分必要条件是r2与m互素.定义3设m是一个正整数.在模m的所有不同简化剩余类中，从每个类任取一个数组成的整数的集合，叫做模m的一个简化剩余 系定理3设771是一个正整数，Q是满足（Q,m）=1的整数.如果X 遍历模rn的一个简化剩余系，则ax也遍历模m的一个简化剩余系.应用2 Q a Ar 1 蔚 是：(mod m).1 计算 12996227(mod 37909).解设 m=37909,b=12996.令 q=1.将 227 写成二进制,227=1+2+25+26+27.运用模重复平方法，我们依次计算如下：1).n0=1.计算ciQ=a-b=12996,=b2=11421(mod 37909).2).ni=1.计算qi=qo 八三 13581,b2=bl=32281(mod 37909).3).n2=。.计算a2=i=13581b3=b1=20369(mod 37909).4).n3=0.计算。3=。2 三 13581,名三町三 20065(mod 37909).5).n4=0.计算a4=3=13581,打三层三 10645(mod 37909).6).ng=1.计算=Q4 打三 22728,%三隔三 6024(mod 37909).7).几6=1.计算Q6=Q5%三 24073,g 三标三 9663(mod 37909).8).nr=1.计算a7=a6 b7=7775(mod 37909).最后，计算出12996227=7775(mod 37909).欧拉函数。(n)I：欧拉函数。(n)是一个定义在整数集合上的函数，I#n)的值等于序列0,1,n-1中与n互素的数的个数=1，(2 h善=2，果P是素数/(p)=?xnSnxyzkySHzBi,n 互素时，0(mn)=0(m)(n)s2 KQS2 S2 cS2 z.,/:.二、.;二:二二；二、.”寡拉定理:欧拉定理x Z1二大二不。合_不.二.二鬻隹论:;.?.-可以利用上述定理，求某些数的逆:S2 SQS2 H2 SQz.i?v-*-*Leonard Adleman鬻1 9 78年sSA密码体制Key SetupTo set up a user s key mater ial,user Alice per for ms the following steps:1.2.5.choose two r andom pr ime number s p and q such that p=|q|;(*this can be done by applying a Monte-Car lo pr ime number finding algor ithm,e.g.,Alq 4.7*)computeA/=pq;computeA/)=(p-1)(q-1);choose a r andom integer e(/V)=1,and compute the integer d such thated=1(mod 0(Ar);(*since gcd(e/(/V)=1,this congr uence does have a solution for d which can be found by applying the Extended Euclid Algor ithm(Alq 4.2).*)publicize(N,e)as her public key,safely destr oy p,q and(/V),and keep d as her pr ivate key.辞SA密码体制_EncryptionTo send a conf idential message m N to Alice,the sender Bob creates the ciphertext c as f ollows(*viewed by Bob,the plaintext message space is the set of all positive numbers lessN,although in fact the space is.Z.*)DecryptionTo d ecrypt the ci phertext c,Al ice comp utesm cr(mod JV).MSA例子 4 p设 p=2 3,q=47,e=3明文m=32 0,s鬃Z1 RSA公钥体制加密m并解密聚 A设p=2 3,q=47,e=3明文m=32 0,建立RSA公钥体制加密m并解密=pq=2 3x 47=1081,#n)=(p-l)(q-l)=2 2 x46=1 01 2e?0(n)户(3,1 012)=1,以求得d=675,满足ed=1(mod/(n)是公钥是n,e=1 081,3；私钥是n,d=1 081,675对于m=32 0,加密得到密文c三32 03三72 8(modl081)即密文是c=72 8解密：解密得到明文m三72 8675(modl081):m 三 728675 三 15675=1515=2 1(mod2 3)m 三 728675 三 23675 三 2331=38(mod47)解方程得m三32 0(mod 1081)