密码学课件 公钥密码数学基础

密码学导论IntroductiontoCryptology主讲教师：李卫海、胡红钢第7章公钥密码数学基础公钥密码数学基础公开密钥密码的概念椭圆曲线代数素数相关问题本原元与指数函数有限域方程公钥密码数学基础公开密钥密码的概念椭圆曲线代数素数相关问题本原元与指数函数有限域方程对称密码体制的缺陷对称密码体制的问题加密能力与解密能力是捆绑在一起的能加密即能解密，能解密也能加密不能实现数字签名密钥更换、传递和交换需要可靠信道，密钥分发困难密钥管理困难如有N用户，则需要C=N(N-1)/2个密钥，N=1000时，C(1000,2)≈500000无法满足不相识的人之间通信的保密要求非对称密钥密码思想1976年，WhitfieldDiffie和MartinHellman提出设想：每个用户A有一加密密钥ke，不同于解密密钥kd将加密密钥ke公开，kd保密，ke的公开不影响kd的安全若B要向A发送明文m，用A的公开密钥ke加密得密文C=E(ke,m)只有A才拥有的解密密钥kd，可以对C进行解密得m=D(kd,C)实用方案的发展依赖于单向陷井函数计算是容易的产生一对密钥(公钥ke和私钥kd)在计算上是容易的不难计算C=E(ke,m)和m=D(kd,C)分析是不可行的知道ke,计算kd不可行不知道kd，即使知道ke,E,D及C，计算m不可行非对称密钥密码系统的优点加密能力与解密能力是分开的从密码算法和加密密钥来确定解密密钥在计算上是不可行的两个密钥的任何一个都可用来加密，另一个用来解密。如何使用，取决于需求密钥分发简单需要保存的密钥量大大减少，N个用户只需要N个密钥可满足不相识的人之间保密通信可以实现数字签名对称密码加/解密密钥相同，密钥为双方共享密钥必须保密

已知算法和密文不易推导出密钥非对称密钥密码加/解密密钥不同，双方各持一个其中一个密钥必须保密——私钥已知算法和公钥，不易推导出私钥公钥密码体制的基本应用保密：Alice要发消息给BobAlice用Bob的公钥对消息加密C=E(PUb,m)Bob收到消息后，用其私钥对消息解密M=D(PRb,C)只有Bob知道自身的私钥，其他接收者均不能解密消息公钥密码体制的基本应用认证：Alice在自己的消息上加认证信息示证方Alice用自己的私钥加密消息(签名)S=E(PRa,m)验证方Bob用示证方Alice的公钥解密消息(验证)m=D(PUa,S)若结果证实公钥与示证方的私钥相吻合，则可以确认消息来自示证方(认证)公钥密码体制的基本应用即保密又认证：把保密和认证过程结合起来C=E(PUb,D(PRa,m))m=E(PUa,D(PRb,C))公钥密码数学基础公开密钥密码的概念椭圆曲线代数素数相关问题本原元与指数函数有限域方程素数与互素素数：仅能被1和它自身整除的数不能写成其它数字乘积的形式素数是现代数论的核心内容a能够整除b，或b能够被a整除，记为a|b例如12|36公因子：能够同时整除a和b的数，称为a和b的公因子最大公约数：k=gcd(a,b)两个数a,b互素是指它们公因子仅有1素因子分解

费马定理Fermat'sTheorem

费马定理费马定理等价形式：若p是素数，则apmodp=a例：a=7,p=1972=49≡11(mod19)74=121≡7(mod19)78=49≡11(mod19)716=121≡7(mod19)ap-1=718=716×72≡7×11≡1(mod19)ap=719=718*7≡7(mod)19注意p-1并不一定是使得atmodp=1的最小t73≡11*7≡1mod19欧拉函数欧拉函数Φ(n)：比n小且与n互素的正整数的个数，即模n的缩剩余类集中元素之个数。若p是素数，则Φ(p)=p-1nΦ(n)nΦ(n)nΦ(n)111110211221124221032131223224214624854158252062168261276171627188418628129619182928104208308欧拉函数若p和q是素数，n=pq，则Φ(n)=Φ(p)Φ(q)=(p-1)(q-1)证明：不与n互素的数有p,2p,…,(q-1)p,q,2q,…,(p-1)qΦ(n)=pq-1-[(q-1)+(p-1)]=pq-(p+q)+1=(p-1)(q-1)事实上，只需p,q互素，即有Φ(n)=Φ(p)Φ(q)Φ(n)=pq-(p-Φ(p))q-(q-Φ(q))p+(p-Φ(p))(q-Φ(q))

=Φ(p)Φ(q)例：Φ(35)=Φ(5)Φ(7)=4×6=24欧拉函数素数p，pe的完全剩余类集中共有pe个数，p的倍数有pe-1个，则Φ(pe)=pe–pe-1=pe-1(p-1)一般说来，对任意n，Φ(n)由下式给出：其中pi是素数，P是n的素因子集合例：Φ(24)=Φ(23)Φ(3)=22(2-1)30(3-1)=8

欧拉定理Euler'sTheorem欧拉定理Euler'sTheorem：

对满足gcd(a,n)=1的任意a和n，有aΦ(n)modn=1证明：令{r1,…,rΦ(n)}是模n的缩剩余集则{arimodn}是{ri}的置换形集合因此，即得aΦ(n)modn

=1费马定理是当n为素数时的特例

欧拉定理欧拉定理的等价形式：aΦ(n)+1

modn=a推论：akΦ(n)+1

modn=a用欧拉定理求逆元：若axmodn=1,gcd(a,n)=1，则x≡aΦ(n)-1modn证明：axmodn=1=aΦ(n)modn两边同除a，即同乘a的逆，得x≡aΦ(n)-1modn欧拉定理等价形式的推广若n为素数或两个素数乘积时，对任意a，1≤a<n，有aΦ(n)+1

modn=a当a与n互素时，有欧拉定理保证当a与n不互素时，不妨令n=pq,a=bqr时，gcd(b,n)=1，b、r是正整数由费马定理，qp-1modp=1，即qΦ(n)modp=1即qΦ(n)-1=kp两边同乘q，有qΦ(n)+1-q=kpq，即qΦ(n)+1modn=q因gcd(b,n)=1，bΦ(n)+1modn=b所以aΦ(n)+1=(bqr)Φ(n)+1=bqr≡a(modn)在GF(2n)中求逆除了0，长度为n每一个多项式都与p(x)互素，因此，Φ(p(x))=2n-1a-1≡aΦ(p(x))-1≡a2n-2modp(x)例：GF(23)，a=100，p(x)=1011

Φ(p(x))=23-1=7 a-1≡aΦ(p(x))-1≡1007-1=

(100)6≡111(mod1011)素性测试寻找大素数是密码学中的一个常见操作传统方法是逐个尝试除法寻找因子用小于等于该数平方根的所有素数去除只适合找小素数或者用基于素数性质的统计素性测试所有的素数都满足相应性质存在一些合数（称为伪素数）也满足相应性质或者使用慢一些的确定性素性测试，如AKS

M.Agrawal,N.Kayal,andN.Saxena,PRIMESisinP,AnnalsofMathematics,Volume160,Issue2,Pages781-793,2004.(https:///2004/160-2/p12)

素性测试：WITNESS测试素数的性质1：若n是素数，a是正整数，a<n，则a2modn=1当且仅当amodn=1或a=-1=n-1modnWITNESS测试算法输入：待测试整数n输出：合数，或可能是素数1.任选随机整数a，1<a<n–12.ifa2modn=1thenreturn(“composite");3.elsereturn("maybeprime")素性测试：MillerRabin测试素数的性质2：对奇数n≥3，(n-1)可表示为n-1=2kq，k>0，q是奇数若n是素数，则序列(aq,a2q,…,a2k-1q)modn中或者第一个元素为1，或者某个元素为n-1；否则n是合数。证明：考察序列aq,a2q,…,a2k-1q,a2kq若n是素数，则由费马定理可知，an-1modn=a2kqmodn=1。即序列最后一项一定是1序列的后一项是前一项的平方，则第一个1或者是第一项，或者其前面一项为-1条件成立，并不意味着n一定是素数模合数时，1的开平方未必是1或-1。例如，模12时，5*5≡1

mod

12素性测试：MillerRabin测试MillerRabin测试算法输入：待测试整数n输出：合数，或可能是素数1.计算奇数q和整数k，使得(n-1)=2kq2.任选随机整数a，1<a<n-13.ifaqmodn=1thenreturn("maybeprime");4.forj=0tok-1do5.if(a2jqmodn=n-1)thenreturn("maybeprime")6.return("composite")素性测试：MillerRabin测试若Miller-Rabin算法返回“合数”，则该数确定不是素数否则可能是素数，可能是伪素数对于伪素数，检测结果为“不确定”的概率小于1/4若随机选择a，重复测试t次都返回不确定，则n为素数的概率1-4-t例，t=10，则此概率>0.999999取足够大的t，若检测结果均不确定，则可以相信n是素数素性测试：MillerRabin测试例，n=29(n-1)=28=22(7)=2kq取a=10,计算107mod29=17,既不为1也不为28。计算(107)2mod29=28,测试算法返回不确定取a=2,27mod29=12,214mod29=28,返回不确定对1到28之间的所有整数a进行测试，都会返回不确定。判定n为素数例，n=13x17=221n-1=220=22(55)=2kq取a=5,555mod221=112,既不为1也不为220。(555)2mod221=168,返回合数如果a=21,2155mod221=200,(2155)2mod221=220,返回不确定，表明221可能是素数事实上，1到220这220个整数中，a有6个整数会返回不确定：1,21,47,174,200和220素数的分布数论给出：大约每ln(n)个数里会出现一个素数第n个素数pn位于n·ln(n)<pn<n[ln(n)+ln(ln(n))],n≥6偶数和5的倍数无需测试，实际确定一个素数只需测试0.4ln(n)个数字。例：若寻找大小约2200的素数，需要测试0.4ln(2200)≈55次这仅是平均统计结果。素数有时会离得很近，有时会离得很远1,000,000,000,061和1,000,000,000,063都是素数1001!+2,1001!+3,…,1001!+1000,1001!+1001是1000个连续的合数公钥密码数学基础公开密钥密码的概念椭圆曲线代数素数相关问题本原元与指数函数有限域方程本原元根据欧拉定理，aΦ(n)modn=1，则至少有一个整数m满足：ammodn=1,即m=Φ(n)一般地，Φ(n)是一个数模n的可能的最高指数如果数g满足gimodn（0<i<n）各不相同，遍历除0之外所有元素，则称g为n的本原元（PrimitiveElement、本原根、素根、原根、生成元）若a是n的本原元，则a,a2,…,aΦ(n)是模n各不相同的，且均与n互素例：模19的所有本原元aa2a3a4a5a6a7a8a9a10a11a12a13a14a15a16a17a18111111111111111111248161371491817151136125101398515726181610111441217131416791711651416791711651561117971641561117971641617745119161617745119161711171117111711171117111871811121871811121871811121957616114171957616114171105126311151718914713168421117111711171117111711171121118781121118781121118781131712414111016186271558931146817107341851311291216151151612921113518437101786141169115471761169115471761174111667591174111667591181181181181181181181181181对于素数p，非本原元的元素的周期都是p-1的因子，因为aΦ(n)modn=1本原元本原元的寻找本原元：对模素数p，对于任意素数p，其本原元必定存在当g为本原元且a与p-1互素时，gamodp也是本原元模p的本原元素个数为欧拉函数Φ(p-1)例：p=11,Φ(p-1)=Φ(10)=4,即有4个本原元若已知g=2为模p的本原元，且1,3,7,9与p-1互素则21=2，23=8，27=7，29=6mod11均为模11之本原元素找到一个本原元素后很容易找到所有本原元素本原元的判定：对素数p，整数b为模p的本原元，当且仅当对所有能整除p-1的素数q，有b(p-1)/q≠1modp用本原元表示的有限域定义有限域GF(2n)的另一种等价形式设有限域GF(2n)的模素多项式为f(x)阶为q=2n的有限域中，生成元g的幂：g0,g1,…,gq-2构成有限域的所有非零元素有限域GF(2n)中前n+1个元素为0,g0,g1,…,gn-1gn=f(g)-(f(g)-gn)=f(g)-gn（生成元g满足f(g)=0）gn+1到gq-2需要计算gq-1=1乘法运算简化为指数相加gk=gkmod(q-1)指数表示多项式表示00g0(=g7)1g1gg2g2g3g+1g4g2+gg5g2+g+1g6g2+1模x3+x+1的域GF(23)的元素例：模x3+x+1的域GF(23)的生成元及运算+01gg2g3g4g5g6001gg2g+1g2+gg2+g+1g2+1110g+1g2+1gg2+g+1g2+gg2ggg+10g2+g1g2g2+1g2+g+1g2g2g2+1g2+g0g2+g+1gg+1x2g3g+1g1g2+g+10g2+1g2g2+gg4g2+gg2+g+1g2gg2+101g+1g5g2+g+1g2+gg2+1g+1g210gg6g2+1g2g2+g+11g2+gg+1g0

01gg2g3g4g5g6000000000101gg2g+1g2+gg2+g+1g2+1g0gg2g+1g2+gg2+g+1g2+11g20g2g+1g2+gg2+g+1g2+11gg30g+1g2+gg2+g+1g2+11gg2g40g2+gg2+g+1g2+11gg2g+1g50g2+g+1g2+11gg2g+1g2+gg60g2+11gg2g+1g2+gg2+g+1指数函数及其性质定义：令G为有限乘法群，g∈G，则对于所有整数x，E(x,g)=gx∈G，为指数函数通常，令G={1,…,p-1},p为素数，则E(x,g)=gxmodp为指数函数特性1：周期性（Periodicity）G是有限群，序列{g0,g1,g2,…}必为周期序列存在最小正整数T，使得E(T,g)=gT=1=g0，称T为g在G中的序(order)，或g元素的阶。对于所有g，T必定整除Φ(p)aa2a3a4a5a6a7a8a9a10a11a12a13a14a15a16a17a18a的阶1111111111111111111248161371491817151136125101183985157261816101114412171311841679171165141679171165195611179716415611179716419617745119161617745119161971117111711171117111711138718111218718111218718111216指数函数及其性质特性2：本原元问题若找到一个本原元，容易找到其它本原元。问题是如何找到第一个本原元。特性3：交换性指数函数满足交换性，因为： E(x,E(y,g))=E(x,gy)=(gy)x=gyx

E(y,E(x,g))=E(y,gx)=(gx)y=gxy

∴E(x,E(y,g))=E(y,E(x,g))特性4：乘法性(MultiplicativeProperty)乘法同态E(x,g1)E(x,g2)=g1xg2x=(g1g2)x=E(x,g1g2)指数函数及其性质特性5：非对称性(AsymmetricProperty)∵E(x,-g)=(-g)x=(-1)xgx=(-1)xE(x,g)∴若x为偶，则满足偶对称；若x为奇，则满足奇对称特性6：乘法逆元素(MultiplicativeInverse)若T为g之序，则对于所有x，0≤x<T,E(x,g-1)=E(T-x,g)因为：E(x,g-1)=g-x=1•g-x=gT•g-x=gT-x=E(T-x,g)这是一种求乘法逆元素的方法，g-1=gT-1(这里x=1)特性7：可逆性若T为g∈G之序，x­-1为x在模T时的乘法逆元素（不一定存在），

即xx-1=1modT=kT+1

则E(x,E(x-1,g))=E(x-1,E(x,g))=gxx-1modp =gkT+1=(gT)k∙g=1k∙g=gmodp指数函数及其性质特性8：快速指数运算法

gx设x为n比特(xn-1,xn-2,…,x1,x0)2gx=g^[(…(xn-1×2)+xn-2)×2…+x1)×2+x0]=(…(gxn-1)2×gxn-2)2×gxn-3…)2×gx0共需n-1次平方及w(x)-1次乘法。w(x)是x中1的个数，平均而言w(x)=n/2。因此平均需要1.5n-2次乘法(平方算一次乘)b=bkbk-1…b1b0f=abmodnc=b离散对数离散对数问题DLP(DiscreteLogarithmsProblem)指数运算的逆运算：求解ax=bmodp，记为x=logabmodp-1或x=loga,p(b)若a是本原根，则离散对数一定存在，否则未必log34mod12(x满足3x=4mod13)无解log23mod12=4指数运算是简单的，而离散对数是困难的离散对数运算与大数分解同等困难离散对数的计算考虑方程y=gxmodp若给定整数g,x和p，可以直接用快速指数算法求出y但是若给定p,g及y,求x，则为DLP问题最快方法的难度为L(p)=exp{(ln

p)1/3(ln(ln

p))2/3}例：GF(19)里的离散对数a123456789101112131415161718log2amod1801132161463817121557114109log3amod1807114486321112151713510169log10amod1801751624121510163131171489log13amod1801117414101215167631513829log14amod1801378102631451215111171649log15amod1805111081612154136471712149IndexCalculus求离散对数求解ax=b(modp)，p是大素数，a是本原元任选m个“小”素数做基底S={p1,p2,…,pm}构建同余方程组并求解：随机选取m个随机整数kj(0<kj<p,1≤j≤m)，计算解上述m个线性方程，求得logapi(modp-1)随机选取整数r，计算例，在GF(269)中求x=log2108解：选取S={2,3,7,11}构建同余方程求解上述三个方程，得随机取r=188，得公钥密码数学基础公开密钥密码的概念椭圆曲线代数素数相关问题本原元与指数函数有限域方程一元一次方程axmodn=b假如a·xmodn=b在[0,n-1]中有一个解，则n|(ax-b)

令g=gcd(a,n)，则当且仅当g|b时，方程有解等式(a/g)xmod(n/g)=1有唯一的解x0，x0∈[1,(n/g)-1]，因为a/g和n/g互素则(a/g)xmod(n/g)=(b/g)在[0,(n/g)-1]中的一个解是

x1≡(b/g)x0mod(n/g)

等式两边（包括模数）同乘g，可知x1是原方程的一个解任意的x=x1+t(n/g)，t=0,1,…,g-1都满足上式，因此它们都是axmodn=b在[0,n-1]中的解，共有g个解例，6xmod10=4解：g=gcd(6,10)=2，2|4，有两个解先求x0：(a/g)xmod(n/g)=1

3xmod5=1,x0=2再求x1=x0(b/g)=2*4/2=4x=[x1+t(n/g)]，t=0,1,…,g-1

=[4+5t]，t=0,1

=4或9一元一次方程axmodn=b令n=d1d2…dk，di

两两互素，则f(x)modn=0当且仅当f(x)moddi=0

(1≤i≤k)解决f(x)modn=0的问题等价于从一组独立解x1,…,xk

(f(xi)moddi=0)为f(x)moddi=0构造一个公共解x，x

=ximoddi，f(xi)moddi=0，i=1,…,k例：6xmod10=4解：10=2*5联立方程组为

6xmod2=4mod2=0（恒成立）

6xmod5=4即xmod5=4x=4或9例：3xmod10=4解：10=2*5联立方程组为

3xmod2=0

3xmod

5=4即xmod2=0且xmod5=3x=8一元一次方程axmodn=b考虑求解的最后一步：从xmoddi=xi

(1≤i≤k)构造一个公共解这实际上给出了整数的另一种表示方式，整数的CRT表示Zn中元素与k元组一一对应：A

(a1,a2,…,ak),ai≡A(moddi),1≤i≤kZn中元素上的运算等价于对应的k元组上的运算整数分解为CRT表示是容易的。问题在于，如何由CRT表示重构出整数？孙子定理孙子定理（孙子算经，3－5世纪）今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。

xmod3=2 xmod5=3 xmod7=2 n=3

5

7=105 (5*7)((5*7)-1mod3)=35*35-1mod3=35*2=70 (3*7)((3*7)-1mod5)=21*21-1mod5=21*1=21 (3*5)((3*5)-1mod7)=15*15-1mod7=15*1=15 x=2*70+3*21+2*15mod105=23三人同行七十稀

五树梅花二一枝

七子团圆正月半

除零百五便可知中国剩余定理CRT中国余数定理(ChineseRemainderTheorem)令d1,…,dt两两互素，n=d1d2…dt，则xmoddi=xi，i=1,…,t在[0,n-1]中有一个公共解x=CRT(n,d1,d2,...,dt,x1,x2,...,xt)证明：对每一个i，i=1,…,t,有gcd(di,n/di)=1，存在yi满足

(n/di)yimoddi=1(n/di)yimoddj=0,j≠i(因为dj是(n/di)的一个因数)令x=[∑i(n/di)yixi]modn.

则xmoddi=(n/di)yiximoddi=xiCRT定理的证明向量表示：m1m2m3Aa1a2a3整数的CRTM=m1m2…mkA=(a1,a2,...,ak)例：3xmod10=4 10=2

5，d1=2，d2=5 3xmod2=0，解为x1=0 3xmod5=4，解为x2=3

应用CRT找下列方程组的公共解：

xmod2=0 xmod5=3

5*(5-1mod2)=5*1=5 2*(2-1mod5)=2*3=6 x=CRT(10,2,5,0,3)=5*0+6*3mod10=8二次剩余问题定义：对正整数a，若存在x满足x2modn=a，则称a为模n的二次剩余或平方剩余(QuadraticResidues,R2)；否则a是模n的非二次剩余(QuadraticNon-residues,NR2)用QRn表示所有模n的二次剩余的集合，用QNRn表示所有模n的非二次剩余的集合例：模7的QR7={1,2,4}，QNR7={3,5,6}12mod7=62mod7=142mod7=32mod7=222mod7=52mod7=4当a是模n的二次剩余时，二次方程x2=amodn有解，解称为a模n的一个平方根平方根与二次剩余的个数定理：对于素数p，p>2，0<a<p，若a∈R2，则x2modp=a有两个解，否则无解证明：若a∈R2,至少有一个解x1,满足x12modp=a同时p-x1也是一个解：(p-x1)2modp=x12modp=ap-x1≠x1（p为奇数），所以这两个解是可以区分的定理：对于素数p，p>2,有(p-1)/2个模p的二次剩余，(p-1)/2个模p的非二次剩余证明：对每个a∈R2，它的两个平方根x1或p-x1中有且仅有一个落在[1,(p-1)/2]中(p-1)/2个剩余12,22,…,((p-1)/2)2modp是不同的R2中的数不存在其它二次剩余二次剩余判定定理：对素数p>2,0<a<p,若a∈R2,则a(p-1)/2modp=1；否则a(p-1)/2modp=p-1证明：根据费马定理，ap-1modp=1,有(ap-1–1)modp=0∵p是奇数，因此有(a(p-1)/2+1)(a(p-1)/2-1)modp=0即p|a(p-1)/2+1或p|a(p-1)/2–1，但不同时成立，否则p|2∴a(p-1)/2modp=±1若a∈R2，则其平方根x满足a(p-1)/2modp=xp-1modp=1共(p-1)/2个平方剩余，都是a(p-1)/2modp=1的解。而不会有更多的解，因为(p-1)/2次方程最多有(p-1)/2个解。(p-1)/2个非平方剩余只能是a(p-1)/2modp=p-1的解一元二次方程x2modp=a，a∈R2，p是素数尚无有效的确定性算法求解模素数的平方根问题若素数p≡3(mod4)，则存在确定性解法a(p-1)/2modp=1a(p+1)/2modp=ax1=a(p+1)/4modpx2=p-x1在生成随机素数时，保证生成的是模4余3的素数只需最低2个比特固定为11一元二次方程x2modpq=a，a∈R2，p、q是素数考虑n=pq，p和q是素数x2modn=a

x2modp=amodp，x2modq=amodqa∈R2，则两式必有解 x2modp=amodp有两个解，x1和p-x1 x2modq=amodq有两个解，x2和q-x2当p、q≡3(mod4)时，易解 x1=a(p+1)/4modp，并导出p-x1 x2=a(q+1)/4modq，并导出q-x2应用CRT，可以求出x2modn=a的四个解， z1=CRT(n,p,q,x1,x2),z2=CRT(n,p,q,x1,q-x2), z3=CRT(n,p,q,p-x1,x2),z4=CRT(n,p,q,p-x1,q-x2)gcd(z1＋z2,n)=qgcd(z1＋z3,n)=pgcd(z1＋z4,n)=ngcd(z2＋z3,n)=ngcd(z2＋z4,n)=pgcd(z3＋z4,n)=q例：x2mod21=4 21=3

7 x2mod3=1，解为x1=1，2 x2mod7=4，解为x2=2，5 z1=CRT(n,p,q,x1,x2)=CRT(21,3,7,1,2)=7*(7-1mod3)*1+3*(3-1mod7)*2

=7*1*1+3*5*2≡16mod

21 z2=CRT(21,3,7,1,5)=7*1*1+3*5*5≡19mod21 z3=CRT(21,3,7,2,2)=7*1*2+3*5*2≡2mod21 z4=CRT(21,3,7,2,5)=7*1*2+3*5*5≡5mod21公钥密码数学基础公开密钥密码的概念椭圆曲线代数素数相关问题本原元与指数函数有限域方程椭圆曲线密码ECC大多数公开密钥密码系统如RSA,都使用具有非常大数目的整数或多项式，计算量大，密钥和报文存储量也大计算能力的提高使得密钥长度一直在增加椭圆曲线密码系统，可以达到同样安全程度，但位数要少得多椭圆曲线算术椭圆曲线并非椭圆，它指的是由Weierstrass方程所确定的平面曲线：

y2+axy+by=x3+cx2+dx+e满足上述方程的数偶(x,y)称为椭圆曲线E上的点同时定义无穷远点(pointatinfinity)O，作为零点(zeropoint)椭圆曲线算数实数域有限域实数域上的椭圆曲线一般简化形式y2=x3+ax+bx3+ax+b=0没有重根的条件4a3+27b2≠0例子： y2=x3-4x=x(x-2)(x+2)椭圆曲线上的加法椭圆曲线上的点集及其上的加法操作构成一个群点集：椭圆曲线上的所有点和无穷远点加法规则：若椭圆曲线上的三个点处于一条直线上，则它们的和为O逆元：一条垂直线与曲线相交于P=(x,y)和P'=(x,-y)，

也相交于无穷点O，有P+P'+O=O。即P'=-P对于椭圆曲线上的任一点P，有P+O=PO是加法的单位元(additiveidentity)，O=-O椭圆曲线上的加法加法：连接PQ做直线得交点R' P+Q+R'=O P+Q=-R’=R例：y2=x3-xy2=x3+x+1PQ直线：y-yP=(x-xP)+y0

=(yQ-yP)/(xQ-xP)与曲线相交：

(

x+y0)2=x3+ax+bR点坐标： xR=

2-xP-xQ yR=-(

xR+y0)椭圆曲线上的数乘二倍：过点P(x,y)的切线P+P+R'=OP+P=2P=-R’数乘，多次累加：kP=P+…+P过P切线：y-yp=s(x-xp)+y0 s=dy/dx=(3xp2+a)/(2yp)与曲线相交：

(sx+y0)2=x3+ax+bR点坐标： xR=s2-2xP yR=-(sxR+y0)有限域上的椭圆曲线将椭圆曲线定义于有限域GFP上：y2=x3+ax+bmodpp是一