数论在密码学中的应用

ComputerKnowledgeandTechnology：617(20106)1，2（1.，712000；2.，714000）：。，，。，，DES、RSA，EIGamal，，。，，。：；RSA；ElGamal；：TP311：A：1009-3044(2010)17-4614-05ApplicationoftheNumberTheoryinCryptographyGUOHai-min1,BAIYong-xiang2(1.SuburbanSchoolsofDali,Dali715100,China;2.DepartmentofElectricalEngineeringWeinanTechnology,Weinan714000,China)Abstract:Thisthesisfocusonbasicknowledgeofnumbertheoryanditsapplicationsincryptography.introducethebackground,currentsituationofthecryptography,andresearchpurposeandsignificanceofcryptography.Expoundedclassicalcryptography,moderncryptogra-phy,focusingontheDES,RSA,EIGamal,ellipticcurvecryptography(ECC)Finally,oncryptographytheoryandalgorithmsareputfor-ward.Thisresearchworkisofgreatsignificancetothefutureresearchwork.Keywords:cryptography;RSA;EIGamal;EllipticCurvecryptography：“，”。，，，[1]。，、（CRT）、，、、、。11.11)：ab，b≠0，q，a=bq，abba，b—a，：(1)b|a，a≠0，|b|≤|a|；(2)b|a，a|b，a≠0，a=bb=a；(3)c|b，b|a,c|a；（c≠0）(4)b|a，cb|ca（c≠0）；(5)c|a，c|b,c|ma+nb，m，n∈Z（c≠0）。2)：a，b(b≠0)q，r，a=qb+r，（0≤r＜b）。qrba。3)：a，b[a，b]，a，b(a，b)，：(1)m，(am，bm)=m(a，b)[am，bm]=m[a，b]；(2)a，b，(a，b)[a，b]=ab；(3)a，b，c，(ab，bd，ac)[a，b，c]=abc；(4)ka，b，(k/a，k/b)=k/[a，b]；(5)ca，b，(a/c，b/c)=(a，b)/c；(6)(a，b)=1，(ab，c)=(a，c)(b，c)；(7)a1,a2,…an,n，(a1,a2,…an)=((a1,a2,…ak),(ak+1,ak+2,…an))。4)[5]:(1)：n≥2，n=p1a1,p2a2,…,pmamn，准（n）nn，。：2010-03-27：（1968-），，，，；（1970-），，，，，。ISSN1009-3044ComputerKnowledgeandTechnologyVol.6,No.17,June2010,pp.4614-4618E-mail:[e-mail]：617(20106)(2)：n！，p。1.2，，，。RSAp,q。，。，：，IEEEP1363；Miller-Rabin。1.2.11)π(x)x，2)n(n-1)≡-1(modn)，。。3)FermatFermat。p，，。，p，a，ap-1≡1(modp)，Fermat，。Miller-Rabin，，GKA，，，。Agrawal-Kayal-Saxena，，，。1.3，，，（Modulararithmetic）。。。，，。1.3.1a，b，m，a，bm：a≡b(modm)abm，abm。26≡14(mod12)：m1a，b，m|(a-b)，abm，a≡b(modm)，abm。，：(1)a≡0(modm)，m|a；(2)a≡b(modm)abm，。1.3.2(1)a≡a(modm)；(2)a≡b(modm)b≡a(modm)；(3)a≡b(modm)，b≡c(modm)，a≡c(modm)(4)a≡b(modm)，c≡d(modm)，①a±c≡b±d(modm)，②ac≡bd(modm)；(5)ac≡bc(modm)c!=0a≡b(modm/(c，m))(c，m)c，m；(c，m)=1a≡b(modm)；(6)a≡b(modm)，an≡bn(modm)(7)a≡b(modm)，n|m，a≡b(modn)(8)a≡b(modmi）i=1,2...na≡b(mod[m1,m2,...mn])[m1,m2,...mn]m1,m2,...mn(9)a，m∈N,(a，m)=1，a(φ(m))≡1(modm)(:φ(m)m，φ(m)=m-1,m；φ(m=q1r1×q2r2×...×qiri)=m(1-1/q1)(1-1/q2)...(1-1/qi))：：p，ap≡a(modp)a(p-1)≡1(modp)（p|a）(10)m1，m2，m3，......，mn，m=m1m2m3m4m5...mn（mi）。J（1，n)，：4615ComputerKnowledgeandTechnology：617(20106){xj≡1(modmj){xj≡0(modmi)ijx1najxj，xx≡aj（modmj）,j=1,2,3,.....,n：a，a1022.1，。，，，。，。：（）、（）（）。、。2070，：1949Shanon“TheCommunicationTheoryofSecrecySystem”1976DiffieHellman“NewDi-rectionofTheCryptography”。Shanon，；“”，。，，。1976，，。[4]：1)（IntegerFactorizationProblem）。。RSA，Rivest、Shamir、Adlman1978，RSA，。2)（DiscreteLogarithmProblem）。DLP，ELGamalDSA。3)（EllipticCurveDiscreteLogarithmProblem）。。Diffie-Hellman、。1985，NealKoblitzIBMVictorMiller（EllipticCurvesCryptogra-phy,ECC），GoldwasserKillian，Lenstra，，，，。，，，，、、、。：；。，，、，。，RSA，，，ECC“”。，，，，，。2.2，。，。，，，。n，n(n-1)/2，，。，，，。()。DES(DataEncryptionStandard)TripleDES(DES)、IDEA、FEALN、RC5。DES，(EFT)。DES56bit，TripleDES56bit3，112bit。RC2RC4RSA，。，C2RC4。，，。。，，。，。，，，。。2.3DES，。1971TuchmanMeyerShannon，1977。DESLucifer，。，。4616ComputerKnowledgeandTechnology：617(20106)DES，64。6464，16：64，32，，，；。。16。，，64。DES，。2.4，x，y，n，k（），y≡xk(modn)。，（，，O(lognk)，k）。，O(logn)2，。，，AB。，A、BqFqg；Aa∈{1，2，…，q-1}（aA），ga(modq)B；Bb∈{1，2，…，q-1}（bB），gb(modq)A；A(gb)a(modq)，B(ga)b(modq)，(gb)a(modq)=(ga)b(modq)=gab(modq)，，ABgab(modq)，，。，g，q，ga(modq)，gb(modq)。，，ab，gab(modq)。，，Fq，ab。，，（，，），（，）。，，，。[6]。ABq=2739·（7149-1）/6+1g=7。Aa，7a(modq)，B（：a）；B7a=127402180119973946824269244334322849749382042586931621654557735290322914679095998681860978813046595166455458144280588076766033781；Bb，7b(modq)，A（：b）；A7b=18016228528745312444782834836799895015967046695346697313025121734059953772058475958176910625380692101651848662362137934026803049。AB7ab(modq)，，ab。，7ab(modq)。2.5RSARSA。1978，（MIT）Rivest,ShamirAdleman《》()，RSA。RSA“”，。RSA,。：1：(a,n)=1,a＝(modn),φ(n)nn。2：(m1,m2)=1，φ(m1·m2)=φ(m1)·φ(m2)。3：p，φ(p)=p-1。RSA:1)p,q,n=p·q；2)φ(n)=(p-1)(q-1)；3)e，ed：d·e＝1modφ(n)＝k4)/：nm，：C=Me(modn)：M=Cd(modnRSA：D(d,E(M，e))=M(modn)E(e,D(d,M))=M(modn)e,d,,d“”,d,e“”,。RSA。，RSA，cemn。RSA。，d，。，RSA4617ComputerKnowledgeandTechnology：617(20106)。RSA。，RSA2.6，，。，，。01，。：，。，。、，：，，，RSA、Ra—bin；，，。，ElGamal。，（SignatureAlgorithm）（VerificationAlgorithm）。MSig（M）＝S，SVer（S）＝{，}＝{0，1}。，；，。，MSKM′，M′S。19918，NISTDSA，1994121。[3]：：p512～l024bit；q160bit，（p-1）。g＝h(p-1)/qmodq，1h＜p-1g＞1。y＝gamodp：0a＜q，。：0k＜q，。r＝(gk(modp))modq，s＝(k-1(H(m)ar))modq（r，s）m，H（a）Hash（）。：w＝s-1modqu1＝(H(m)aw)modqu2＝(rw)modqv＝((gu1ayu2)modp)modqv＝r，m。H(a)SHAMD5。DSA，RSA，。3，、。，[2]，，、、。，，，，。，，，。：[1].[M].:,2002:30-90.[2],.[M].:,2002:120-200.[3]BuchmannJA.IntroductiontoCryptography[M].NewYork:Springer-Verlag,2001:223-229.[4],.[M].:,2002:220-300.[5].—[M].:,1998:10-90.[6]BruceSchneier().[M].,,,,.:,2000:300-400.4618