密码学的数学基础

1密码学的数学基础——从“孙子定理谈起”翟起滨中国科学院研究生院DCS中心[e-mail]2第2章数学基础数论中的许多概念是设计公帀密钥密码算法的基础，本章对其他各章引用到的这些概念做了一些概述。前四节内容主要介绍了一些比较浅但是在其他各章经常用到的初等数论方面的知识。第五节、第六节和第七节内容对群，环，域特别是有限域做了一个概述，主要介绍了一些重要的概念和定理。这两节比较偏重于数学，熟悉这些内容的读者可以跳过这两节。数论中的概念和算法是十分抽象的，没有例子的说明很难掌握，因此，本章提供了许多例子，并用“例如：”标明。2.1数的整除性初等数论研究的基本对象是整数集合},3,2,1,0{K±±±=Z和自然数集合(即正整数集合)},4,3,2,1{K=N在集合N中可以进行加法和乘法运算，即两个自然数之和或乘积仍然是自然数，在集合Z中除了加法和乘法之外还可以做减法运算，并且这些运算满足一些规律(即：加法和乘法的结合律和交换律，加法和乘法的分配律)，但是一般不能作除法，也就是说，设a和b是整数，0≠b，则ba/不一定是整数。即不一定存在整数c，使得bca=。由此产生出数论中的第一个基本概念：数的整除性。2.1.1除数(因子)和整除的概念：定义：设Z为有全体整数而构成的集合，若0b≠且Zmba∈,,使得mba=此时称b整除a。记为ab|,还称b为a的除数(因子)。如果不存在整数m使得mba=则称b不整除a。例如：24的正因子是：1、2、3、4、6、8、12和24。对于数的整除有以下规则成立：31.如果1|a则1±=a。2.如果ba|且ab|，则ba±=。3.任何0≠b能整除0。4.如果gb|而且hb|，则对任意整数m和n有)(|nhmgb+。为明白昀后一个规则，证明如下：如果gb|，则g是b的倍数，可以表示成：1gbg×=，1g为某一整数。如果hb|，则h是b的倍数，可以表示成：1hbh×=，1h为某一整数。故有：)(1111nhmgbnbhmbgnhmg+×=+=+所以b能整除nhmg+。2.1.2素数(质数)的概念:定义：整数1p被称为素数是指p的因子仅有pp−−,,1,1。素数在数论和本章将要讨论的技术中起着至关重要的作用。例如：表2.1给出了在2000以内的所有素数。表2.12000以内的所有素数23571113171923293137414347535961677173798389971011031071091131271311371391491511571631671731791811911931971992112232272292332392412512572632692712772812832933073113133173313373473493533593673733793833893974014094194214314334394434494574614634674794874914995035095215235415475575635695715775875935996016076136176196316416436476536596616736776836917017097197277337397437517577617697737877978098118218238278298398538578598638778818838879079119199299379419479539679719779839919971009101310191021103110331039104910511061106310691087109110931097110311091117112311291151115311631171118111871193120112131217122312291231123712491259127712791283128912911297130113031307131913211327136113671373138141399140914231427142914331439144714511453145914711481148314871489149314991511152315311543154915531559156715711579158315971601160716091613161916211627163716571663166716691693169716991709172117231733174117471753175917771783178717891801181118231831184718611867187118731877187918891901190719131931193319491951197319791987199319971999任意大于1的整数a都能被因式分解为如下的唯一形式：ttPPPaαααK2121=其中tPPPK21都是素数而且每一个()K,3,2,10=iiα。这其实就是数论的一大基石：算术基本定理。该定理的证明比较复杂，由于本书不是一本数学理论的专著，所以我们没有给出具体的证明过程，感兴趣的读者可以参考初等数论方面的书籍。例如：13791×=；13117110112××=任一个给定的正整数可以通过简单列出后面公式中非零分量来说明。例如：整数12可以表示为{}1,232==aa；整数18可以表示为{}2,132==aa；两个数的乘法等同于对应指数分量的加法：pppnmkmnK+=→=对所有的p例如：2161812=×=k；3122=+=k；3213=+=k；3332216×=对于ba|，它们的素数因子的关系如何？如果任何以kp形式表示的整数仅能被对应素数分量小于或者等于它的另一整数jp整除，其中kj≤，因此有：ppbaba≤→|对所有的p例如：12=a；36=b；12|36；32122×=；223236×=222ba==；3321ba=≤=52.1.3互为素数定义：符号),gcd(ba表示a和b的昀大公因子。正整数c是a和b的昀大公因子，如果满足下列条件：1.c是a和b因子；2.任何a和b的因子也是c的因子。此外，还有如下的等价定义：]||,max[),gcd(bkakkba且=因为通常要求昀大公因子为正，而),gcd(),gcd(),gcd(),gcd(babababa−−=−=−=，一般)|||,|gcd(),gcd(baba=。此外，由于0均能被所有非零整数整除，因此有aa=)0,gcd(。如果将两个正整数分别表示为素数的乘积，很容易确定它们的昀大公因子。),min(),gcd(pppbakbak=→=对所有的p确定一个大数的素因子是不容易做到的，因此之前给出的关系并不能得出一个计算昀大公因子的方法，有关计算昀大公因子的方法将在下一节介绍。如果它们之间没有共同的素数因子，整数a和b互素。即它们仅有一个公因子1。换句话说，如果1),gcd(=ba，则认为a和b互素。2.2带余除法和欧几里德算法在上一节里，我们介绍了一些基本的概念，在这一节里，我们将给出一个十分重要的算法——欧几里德算法。欧几里德算法是数论中的一项基本技术，它通过一个简单的过程来确定两个正整数的昀大公因子。扩展的欧几里德算法不仅可以确定两个正整数的昀大公因子，如果这两个数互素，还可以确定它们各自的乘法逆元（乘法逆元将在后面的章节里介绍）。为了引出欧几里德算法，先来看几个定理：定理1：（带余除法）设0,,∈bZba则存在唯一决定的整数q和r，使得：brrqba≤+=0,证明：定义实数}{][aaa+=，][a前者为a的整数部分，}{a为a的小数部分。6先证明满足条件的q和r是存在的。为此令=baq，qbar−=，则q和r都是整数，并且由于=−=baqbabr，而10≤ba，从而10≤br，即br≤0。再证明q和r是唯一确定的。如果又有整数q′和r′使得rbqa′+′′=，br′≤0，则brr′−，并且)(qqbrr−′=′−。这表明rr′−是正整数b的倍数，并且rr′−的绝对值又小于b。只有可能rr′=，于是qq′=，证毕。利用定理1可以证明如下引理：引理1：考察集合{}ZyxbyaxS∈+=,|1.若Snm∈,，则Snm∈±。2.若ZcSn∈∈,，则Scn∈。3.设d为集合S中的昀小正整数，则S恰好是d的所有倍数构成的集合。4.),gcd(bad=。由于这些结论的证明过程比较繁琐，这里就不给出了，有兴趣的读者可以自行推导。引理1表明，集合S恰好是由),gcd(ba的所有倍数构成的，利引理1可以得到昀大公因子的一些有用的性质：引理2：1.设m为正整数，则),gcd(),gcd(bammbma×=。2.若dba=),gcd(，则da和db是互素的整数。3.a和b的每个公因子都是),gcd(ba的因子。4.若1),gcd(),gcd(==mbma，则1),gcd(=mab。5.若a，b是不全为0的整数，则对每个整数x有),gcd(),gcd(axbaba+=。6.若abc|，1),gcd(=bc，则ac|。7利用引理2，我们可以得到求出昀大公因子的如下算法：欧几里德算法：假定0fd。限制算法仅仅考虑正整数是可以接受的，因为),gcd(),gcd(baba=。EUCLID(d,f)1.fYdX←←;2.),gcd(0fdXreturnYif==3.YXRmod=4.YX←5.RY←6.goto2例如：要找出)1006,1970gcd(904100611970+×=)904,1006gcd(16290411006+×=)162,904gcd(941625904+×=)94,162gcd(68941162+×=)68,94gcd(2668194+×=)26,68gcd(1626268+×=)16,26gcd(1016126+×=)10,16gcd(610116+×=)6,10gcd(46110+×=)4,6gcd(2226+×=)2,4gcd(0222+×=)0,2gcd(所以2)1066,1970gcd(=。82.3模运算由上一节的定理1我们知道，任意给定一个正整数n和任意一个整数a，如果用a除以n，得到商q和余数r将满足如下关系：naqnrrqna/;0=≤+=这里x表示小于或者等于x的昀大整数。图2.1说明了给定a和正整数n，总能找到q和r满足之前的关系。数轴上的点代表整数；a必将为余数线上某一点（图中显示a为正数的情况，a为负数也是类似的情况）。由0为起点，经过n，n2，直到qn，以致aqn≤并且anq+)1(由qn到a的距离是r，这样就得到了唯一的值q和r，剩余值r通常称为余数。图2.1naqnrrqna/;0=≤+=的关系如果)mod()mod(nbna=，则称整数a和b模n同余，可以书写为nbamod≡。例如：23mod473≡；10mod921−≡注意：如果namod0≡则an|。模运算符就有如下性质：1.如果)(|ban−则nbamod≡。2.)mod()mod(nbna=等价于nbamod≡。3.nbamod≡等价于nabmod≡。4.如果nbamod≡而且ncbmod≡，则有ncamod≡。92.3.1模运算操作根据定义（图2.2），模n运算将所有整数映射到整数集合上。这会带来一个疑问：能在这个集合内进行算术运算吗？结果是可以进行算术运算，这就是所谓的模运算。模运算有如下性质：1.()()[]()nbannbnamodmodmodmod+=+。2.()()[]()nbannbnamodmodmodmod−=−。3.()()[]()nbannbnamodmodmodmod×=×。下面证明第一条性质。定义arna=)mod(，brnb=)mod(则可得jjnraa,+=为某一整数；kknrbb,+=为某一整数。有：nknrjnrnbabamod)(mod)(+++=+nnjkrrbamod))((+++=nrrbamod)(+=nnbnamod)]mod()mo