1、12024/3/192024/3/1912024/3/192024/3/1912024/3/192024/3/191 15.4.1 椭圆曲线密码体制简介5.4 椭圆曲线密码体制（略）椭圆曲线密码体制（略）在1985年，由Neal Koblitz和Victor Miller分别独立的提出了可以在低要求的计算环境里做到高强度加密的公钥算法，即椭圆曲线密码体制（ECC）。从1998年起，一些国际标准化组织开始了对椭圆曲线密码的标准化工作。椭圆曲线密码算法在与RSA算法相同安全性的情况下，其密钥短较短，160比特长的密钥相当于RSA算法密钥长1024比特的安全性，因而有利于容量受限的存储设备如智能卡等
2、在安全领域的使用。加拿大的Certicom公司是一家ECC密码技术公司，Certicom已经对上百家企业应用ECC密码技术进行授权，包括知名企业Cisco、摩托罗拉等。22024/3/192024/3/1922024/3/192024/3/192在我国，国家密码管理局2010年12月提出了SM2椭圆曲线公钥密码算法，同时，还要求升级并重新修改已有的RSA算法的电子认证系统和应用系统等。中国国家密码管理局发布了SM2椭圆曲线公钥密码算法标准。为满足电子认证服务系统等应用需求，该标准推荐了一条256位的随机椭圆曲线。NIST在标准FIPS 186-2中，推荐了美国政府使用的15个不同安全级别的椭圆
3、曲线。其包括5条二进制域上的随机椭圆曲线、5条二进制域上的Koblitz曲线和5条素域上的随机椭圆曲线。FIPS 186-3中，对于椭圆曲线的参数选择有进一步的介绍.32024/3/192024/3/1932024/3/192024/3/193ECCECC和和和和RSARSA安全性能比较安全性能比较安全性能比较安全性能比较42024/3/192024/3/1942024/3/192024/3/1942024/3/192024/3/194 45.4.2 椭圆曲线（选讲）椭圆曲线是指由Weierstrass方程：y y2 2+a+a1 1xy+axy+a3 3y=xy=x3 3+a+a2 2x x
4、2 2+a+a4 4x+ax+a6 6 所确定的曲所确定的曲所确定的曲所确定的曲线线线线。在公钥密码学中，主要用到两种椭圆曲线：（1）素域Fp(p3)上的椭圆曲线，可以表示为：y y2 2=x=x3 3+ax+b(modp)+ax+b(modp)其中a,b为整数，其判别式4a3+27b20 （2）域F(2n)(n1)上的椭圆曲线，可以表示为：y y2 2+xy=x+xy=x3 3+ax+ax2 2+b+b1.椭圆曲线的定义椭圆曲线的定义52024/3/192024/3/1952024/3/192024/3/1952024/3/192024/3/195 5图图5-1 y2x3+x+6所表示的曲线
5、所表示的曲线 本章的介绍以第一种椭圆曲线为主，本章的介绍以第一种椭圆曲线为主，如图5-1是y2x3+x+6所表示的曲线，该图可以用matlab实现。显然该曲线关于x轴对称。62024/3/192024/3/1962024/3/192024/3/1962024/3/192024/3/196 62椭圆曲线的加法椭圆曲线的加法 在在在在椭椭椭椭圆圆圆圆曲曲曲曲线线线线所所所所在在在在的的的的平平平平面面面面上上上上，定定定定义义义义一一一一个个个个称称称称为为为为无无无无穷穷穷穷远远远远点点点点的的的的元元元元素素素素，记记记记为为为为O O，把它定义为加法的单位元。把它定义为加法的单位元。把它定义
6、为加法的单位元。把它定义为加法的单位元。也即椭圆曲线上的点也即椭圆曲线上的点也即椭圆曲线上的点也即椭圆曲线上的点P P和它相加：和它相加：和它相加：和它相加：P+O=PP+O=P。椭圆曲线的加法定义如下：如如如如果果果果椭椭椭椭圆圆圆圆曲曲曲曲线线线线上上上上的的的的3 3个个个个点点点点位位位位于于于于同同同同一一一一直直直直线线线线上上上上，则者三个点的和为则者三个点的和为则者三个点的和为则者三个点的和为OO。设P1，P2为两个关于x轴对称的椭圆曲线上的点即P1=(x,y),P2=(x,-y)，则它们互为加法逆元。由由由由上上上上面面面面的的的的加加加加法法法法定定定定义义义义，P P1
7、1P P2 2的的的的连连连连线线线线的的的的延延延延长长长长线线线线为为为为无无无无穷穷穷穷远远远远，故故故故P P1 1，P P2 2，OO三三三三点共线，由加法定义容易得：点共线，由加法定义容易得：点共线，由加法定义容易得：点共线，由加法定义容易得：P P1 1+P+P2 2+O=O+O=O，P P1 1=-P=-P2 2。72024/3/192024/3/1972024/3/192024/3/1972024/3/192024/3/197 7 设P和Q是椭圆曲线上x坐标不同的两个点，R=P+QR=P+Q定义为：画一条通定义为：画一条通定义为：画一条通定义为：画一条通过过过过P,QP,Q的
8、直线与椭圆曲线交于的直线与椭圆曲线交于的直线与椭圆曲线交于的直线与椭圆曲线交于P1P1,由加法的定义：P+Q+R1=OP+Q+R1=O。则P+Q=-R1=R，如图5-2。图图5-2 R=P+Q示意图示意图82024/3/192024/3/1982024/3/192024/3/1982024/3/192024/3/198 8 点点P的倍点定义为：的倍点定义为：过P点做椭圆曲线的切线，设与椭圆曲线交于R1,则P+P+R1=OP+P+R1=O,故2P=-R1=R2P=-R1=R。如图5-3。图图5-3 R=2P示意图示意图92024/3/192024/3/1992024/3/192024/3/199
9、2024/3/192024/3/199 9 对于上述加法，可以通过以下方式理解：对于上述加法，可以通过以下方式理解：对于上述加法，可以通过以下方式理解：对于上述加法，可以通过以下方式理解：设设设设椭椭椭椭圆圆圆圆曲曲曲曲线线线线的的的的方方方方程程程程为为为为y y2 2xx3 3+ax+b+ax+b，椭椭椭椭圆圆圆圆曲曲曲曲线线线线上上上上有有有有点点点点P(xP(x1 1,y y1 1),),Q(xQ(x2 2,y y2 2)，见图见图见图见图5-25-2。则则则则过过过过QQ和和和和R R点点点点的的的的直直直直线线线线的的的的斜斜斜斜率率率率为为为为k=(yk=(y2 2-y-y1 1
10、)/(x)/(x2 2-x-x1 1)，该该该该直直直直线线线线可可可可以以以以表表表表示示示示为为为为y=kx+cy=kx+c。通通通通过过过过把把把把直直直直线线线线方方方方程程程程代代代代人人人人椭椭椭椭圆圆圆圆曲曲曲曲线线线线方方方方程程程程，可可可可以以以以求求求求得得得得第第第第三三三三个个个个交交交交点点点点的的的的坐坐坐坐标标标标，取取取取第三个点关于第三个点关于第三个点关于第三个点关于x x轴的对称点即为所求。轴的对称点即为所求。轴的对称点即为所求。轴的对称点即为所求。图图5-2 R=P+Q示意图示意图102024/3/192024/3/19102024/3/192024/3
11、/19102024/3/192024/3/191010 对对对对于于于于倍倍倍倍点点点点运运运运算算算算，则则则则通通通通过过过过P(xP(x1 1,y y1 1)点点点点做做做做椭椭椭椭圆圆圆圆曲曲曲曲线线线线的的的的切切切切线线线线(见见见见图图图图5-35-3)，则则则则该该该该切切切切线线线线的斜率可以如下求得的斜率可以如下求得的斜率可以如下求得的斜率可以如下求得:对对对对y y2 2xx3 3+ax+b+ax+b两两两两边边边边求求求求导导导导数得：数得：数得：数得：2yy=3x 2yy=3x2 2+a,k=y=(3x+a,k=y=(3x2 2+a)/2y +a)/2y 通通通通过过
12、过过P P点点点点的的的的椭椭椭椭圆圆圆圆曲曲曲曲线线线线的的的的切切切切线线线线就就就就可可可可以以以以表表表表示示示示为为为为y=kx+c,y=kx+c,通通通通过过过过把把把把直直直直线线线线方方方方程程程程代代代代入入入入椭椭椭椭圆圆圆圆曲曲曲曲线线线线方方方方程程程程，可可可可以以以以求求求求得得得得直直直直线线线线与与与与椭椭椭椭圆圆圆圆曲曲曲曲线线线线的的的的另另另另一一一一个个个个交交交交点点点点的的的的坐坐坐坐标标标标，取取取取该该该该点点点点关关关关于于于于x x轴轴轴轴的的的的对对对对称点即称点即称点即称点即为为为为所求所求所求所求。图图5-3 R=2P示意图示意图112
13、024/3/192024/3/19112024/3/192024/3/19112024/3/192024/3/191111 通通通通过过过过以以以以上上上上推推推推导导导导，可可可可以以以以得得得得出出出出椭椭椭椭圆圆圆圆曲曲曲曲线线线线y y2 2=x=x3 3+ax+b+ax+b上上上上的的的的点点点点的的的的加加加加法法法法运运运运算算算算规规规规则则则则，这个规则可以定义为：这个规则可以定义为：这个规则可以定义为：这个规则可以定义为：122024/3/192024/3/19122024/3/192024/3/19122024/3/192024/3/1912125.4.3 有限域上的椭圆
14、曲线 有限域有限域有限域有限域GF(p)GF(p)上的上的上的上的椭圆椭圆椭圆椭圆曲曲曲曲线线线线是由方程：是由方程：是由方程：是由方程：y y2 2xx3 3+ax+b(mod p)+ax+b(mod p)(a,ba,bGF(p),4aGF(p),4a3 3+27b+27b2 2(mod p)0(mod p)0)定定定定义义义义的曲的曲的曲的曲线线线线，简单简单简单简单表示表示表示表示为为为为E Ep p(a,b)(a,b)。132024/3/192024/3/19132024/3/192024/3/19132024/3/192024/3/191313 例例5-5：y2x3+x+6(mod
15、11)是是有有限限域域GF(11)上上的的椭椭圆圆曲曲线线，可可以以表表示示为为E11(1,6)。下面看看下面看看y2x3+x+6(mod 11)上的离散的点。上的离散的点。由平方剩余的定义，容易知道，由平方剩余的定义，容易知道，1，3，4，5，9是模是模11的平方剩余。的平方剩余。求求该该曲曲线线上上离离散散的的点点可可以以通通过过令令x=0,1,10,求求得得y26,8,5,3,8,4,8,4,9,7,4(mod 11).故故该该椭椭圆圆曲曲线线上上的的有有(2,4)(2,7)(3,5)(3,6)(5,2)(5,9)(7,2)(7,9)(8,3)(8,8)(10,2)(10,9)。1420
16、24/3/192024/3/19142024/3/192024/3/1914 -求解方法举例如下：求解方法举例如下：当当x=0,y26 mod11，6不是模不是模11的平方剩余，无解；的平方剩余，无解；当当x=1,y28 mod11，8不是模不是模11的平方剩余，无解；的平方剩余，无解；当当x=2,y28+2+65 mod11,5是模是模11的平方剩余，的平方剩余，y4 mod 11 其他的点可以按这个方式求出。其他的点可以按这个方式求出。由前面的分析可知，该椭圆曲线上一共有由前面的分析可知，该椭圆曲线上一共有12个点。个点。这这12个点的分布如图个点的分布如图5-4所示，图所示，图5-4中左
17、下标起点是中左下标起点是(0,0)点。点。对于对于同一条椭圆曲线，同一条椭圆曲线，y2x3+ax+b，p取不同的值，点的分布也不同。取不同的值，点的分布也不同。图图5-4 y2x3+x+6(mod 11)所表示的曲线所表示的曲线152024/3/192024/3/19152024/3/192024/3/19152024/3/192024/3/191515 通过比较通过比较通过比较通过比较y y2 2xx3 3+x+6+x+6在平面的曲线（见图在平面的曲线（见图在平面的曲线（见图在平面的曲线（见图5-15-1所示）和所示）和所示）和所示）和y y2 2xx3 3+x+6(mod 11)+x+6(
18、mod 11)在平面上的点（如图在平面上的点（如图在平面上的点（如图在平面上的点（如图5-45-4所示）所示）所示）所示），直观感觉没有太多的联系。，直观感觉没有太多的联系。，直观感觉没有太多的联系。，直观感觉没有太多的联系。图图5-1 y2x3+x+6所表示的曲线所表示的曲线图图5-4 y2x3+x+6(mod 11)所表示的曲线所表示的曲线162024/3/192024/3/19162024/3/192024/3/19162024/3/192024/3/191616 对于同一条椭圆曲线，在不同的有限域上（即对于同一条椭圆曲线，在不同的有限域上（即对于同一条椭圆曲线，在不同的有限域上（即对于
19、同一条椭圆曲线，在不同的有限域上（即p p取不同的值），点的个数是取不同的值），点的个数是取不同的值），点的个数是取不同的值），点的个数是有差别的，有差别的，有差别的，有差别的，当当当当p p很大时，虽然离散点的个数是确定的，离散点的分布情况看上去很大时，虽然离散点的个数是确定的，离散点的分布情况看上去很大时，虽然离散点的个数是确定的，离散点的分布情况看上去很大时，虽然离散点的个数是确定的，离散点的分布情况看上去也没有什么规律。也没有什么规律。也没有什么规律。也没有什么规律。172024/3/192024/3/19172024/3/192024/3/19172024/3/192024/3/19
20、1717 以以以以y y2 2xx3 3+x+6(mod 11)+x+6(mod 11)为例子，选取为例子，选取为例子，选取为例子，选取P=(2,7)P=(2,7)，计算，计算，计算，计算2P2P。首先计算：首先计算：首先计算：首先计算：k=(32k=(322 2+1)(27)+1)(27)-1-1 mod 118 mod 118 于是于是于是于是，x x3 3=8=82 2-2-2 mod 115,y-2-2 mod 115,y3 3=8(2-5)-7 mod 112=8(2-5)-7 mod 112 因此因此因此因此，2P=(5,2)2P=(5,2)。再计算：再计算：再计算：再计算：3P=
21、2P+P=(5,2)+(2,7)3P=2P+P=(5,2)+(2,7)，先计算先计算先计算先计算k=(7-2)(2-5)k=(7-2)(2-5)-1-1 mod 112 mod 112。于是于是于是于是，x x3 3=2=22 2-5-2 mod 118,y-5-2 mod 118,y3 3=2(5-8)-2 mod 113=2(5-8)-2 mod 113 因此，因此，因此，因此，3P=(8,3)3P=(8,3)。计算完毕后，可以通过把计算完毕后，可以通过把计算完毕后，可以通过把计算完毕后，可以通过把2P=(5,2),3P=(8,3)2P=(5,2),3P=(8,3)代入到代入到代入到代入到
22、y y2 2xx3 3+x+6(mod 11)+x+6(mod 11)中验中验中验中验证等式成立否，证等式成立否，证等式成立否，证等式成立否，如果不成立，则要检查计算过程的错误。如果不成立，则要检查计算过程的错误。如果不成立，则要检查计算过程的错误。如果不成立，则要检查计算过程的错误。182024/3/192024/3/19182024/3/192024/3/1918椭圆曲线密码体制椭圆曲线密码体制-原理原理 -椭圆曲线离散对数问题椭圆曲线离散对数问题 已知椭圆曲线已知椭圆曲线E和点和点P，随机生成一个整数，随机生成一个整数d，容易计算，容易计算:Q=d*P，但给定但给定Q和和P,计算计算d就
23、相对困难。就相对困难。（1 1）ECCECC密密密密码码码码体制的建立体制的建立体制的建立体制的建立 选取选取:一个基域一个基域GF(p);定义在该基域上的椭圆曲线定义在该基域上的椭圆曲线Ep(a,b);E上的一个拥有素数阶上的一个拥有素数阶n的点的点P。其中有限域其中有限域GF(p)，椭圆曲线参数，椭圆曲线参数a,b，点，点P和阶和阶n都是公开信息。都是公开信息。192024/3/192024/3/19192024/3/192024/3/1919（2 2）密）密）密）密钥钥钥钥的生成的生成的生成的生成n在区间在区间1,n-1中随机选取一个整数中随机选取一个整数dn计算计算:Q=d*Pn实体的
24、实体的 -公开密钥公开密钥:点点Q -实体的私钥实体的私钥:整数整数d n待发送消息（待发送消息（AB）：）：M-查找查找B的公开密钥：的公开密钥：Q-将消息将消息M表示成一个域元素表示成一个域元素:m-在区间在区间1,n-1中随机选取一个整数中随机选取一个整数k（3 3）加密）加密）加密）加密过过过过程程程程202024/3/192024/3/19202024/3/192024/3/1920-计算点计算点:(x1,y1)=kP-计算点计算点:(x2,y2)=kQ，如果，如果x2=0，则返回第，则返回第步步-计算计算:c=mx2-传送加密数据传送加密数据(x1,y1,c)给给B n 当实体当实
25、体B解密从解密从A收到的密文收到的密文(x1,y1,c)时，执行步骤：时，执行步骤：-使用私钥使用私钥d，计算点，计算点:(x2,y2)=d(x1,y1)-计算计算 ，恢复出消息，恢复出消息m（4 4）解密）解密）解密）解密过过过过程程程程212024/3/192024/3/19212024/3/192024/3/1921212024/3/192024/3/19212024/3/192024/3/19212024/3/192024/3/1921215.4.4 椭圆曲线上的ElGamal密码体制（选讲）（1）先先由由系系统统选选取取一一条条椭椭圆圆曲曲线线，该该椭椭圆圆曲曲线线上上的的点点形形成
26、成了了循循环环群群E，GE是椭圆曲线上的一个点是椭圆曲线上的一个点，N是点是点G在循环群在循环群E的阶，即的阶，即NG=O。（2）用用户户选选择择一一个个整整数数a，0aN，计计算算=aG,a保保密密，但但将将公公开开。即即a,G是是私钥，私钥，a,是公钥，是公钥，所选择的椭圆曲线也是公开的。所选择的椭圆曲线也是公开的。（3）假假定定把把明明文文消消息息m嵌嵌入入到到群群E的的点点Pm上上。当当消消息息发发送送者者欲欲向向A发发送送m，可可求得一对数偶求得一对数偶(C1,C2)，其中，其中C1=kG,C2=Pm+k,k是随机产生的整数。是随机产生的整数。222024/3/192024/3/19
27、222024/3/192024/3/1922 （4）A收收到到(C1,C2)后后，计计算算C2-aC1得得到到消消息息Pm，因因为为C2-aC1=(Pm+k)a(kG)=Pm。可可以以看看到到，如如同同ElGamal密密码码体体制制一一样样，它它也也是是一一个个不不确确定定性性算算法法，对对于于一一个个消消息息m，加加密密过过程程中中k的的选选取取不不一一样样，则则加加密密所所得得的的密密文文也也不不同同。另另外外，该该密码体制也有密文密码体制也有密文“信息扩展信息扩展”问题。问题。232024/3/192024/3/19232024/3/192024/3/1923232024/3/19202
28、4/3/19232024/3/192024/3/19232024/3/192024/3/1923235.4.5 算法举例例例5-12：设设p=11，E是由是由y2x3+x+6(mod 11)所确定的有限域所确定的有限域Z11上的椭圆曲线。上的椭圆曲线。解：解：先要确定先要确定E中的点，以减少计算过程。对每个中的点，以减少计算过程。对每个xZ11，首先计算，首先计算z=x3+x+6 mod 11，然后再求同余方程，然后再求同余方程y2z mod 11的解来实现。的解来实现。由由5.2.7的计算，可以得知，的计算，可以得知，E中有中有13个点。选取个点。选取r=(2,7)，计算，计算2r。首先计算
29、：。首先计算：k=(32 k=(322 2+1)(27)+1)(27)-1-1 mod 118 mod 118 于是于是，x3=82-2-2 mod 115,y3=8(2-5)-7 mod 112 因此因此，2r=(5,2)。242024/3/192024/3/19242024/3/192024/3/1924242024/3/192024/3/19242024/3/192024/3/19242024/3/192024/3/192424 再计算再计算3r=2r+r=(5,2)+(2,7)，首先计算首先计算k=(7-2)(2-5)-1 mod 112。于是于是，x3=22-5-2 mod 118,
30、y3=2(5-8)-2 mod 113 因此，因此，3r=(8,3)。类似地，类似地，还可以计算出还可以计算出nr，n1，计算结果如下：，计算结果如下：r=(2,7)2r=(5,2)3r=(8,3)4r=(10,2)5r=(3,6)6r=(7,9)7r=(7,2)8r=(3,5)9r=(10,9)10r=(8,8)11r=(5,9)12r=(2,4)13r=因此，因此，r=(2,7)是是E的生成元，的生成元，E是一个循环群。是一个循环群。252024/3/192024/3/19252024/3/192024/3/19252024/3/192024/3/192525 由由上上面面的的讨讨论论，可
31、可以以确确定定E中中的的所所有有点点，但但这这只只是是在在例例题题中中，实实际际应应用用中中，由由于于给给定定的的椭椭圆圆曲曲线线上上的的点点数数太太多多，无无法法完完全全列列举举E中中所所有有的的点点，也也没没有有必必要要列举列举E中所有的点。中所有的点。要要确确定定z是是否否是是一一个个模模p的的平平方方剩剩余余，可可以以利利用用Euler准准则则来来实实现现，即即如如果果p是一个奇素数，则是一个奇素数，则z是模是模p平方剩余当且仅当平方剩余当且仅当z(p-1)/21 mod p。当当p3 mod 4时时，如如果果x是是一一个个模模p的的平平方方剩剩余余，则则z(p+1)/41 mod p
32、就就是是z的两个模的两个模p的平方根，这是因为：的平方根，这是因为：(z z(p+1)/4(p+1)/4)2 2zz(p+1)/2(p+1)/2 mod pzz mod pzz(p-1)/2(p-1)/2z mod pz mod p 完成上面运算后，下面看例题。完成上面运算后，下面看例题。262024/3/192024/3/19262024/3/192024/3/1926262024/3/192024/3/19262024/3/192024/3/19262024/3/192024/3/192626例例5-13：假设选取：假设选取r=(2,7)，B的私钥是的私钥是7，有，有=7r=(7,2).加
33、密运算是：加密运算是：e(m,k)=(k(2,7),m+k(7,2)0k12,m是要加密的消息是要加密的消息 解密运算是：解密运算是：d(c1,c2)=c2-7c1 假设假设A要加密明文要加密明文m=(10,9)(这是这是E上的一个点上的一个点)，如果随机选择，如果随机选择k=3,A计算计算c1=3r=3(2,7)=(8,3),c2=m+3=(10,9)+3(7,2)=(10,9)+(3,5)=9r+8r=17r=4r=(10,2)A发送（发送（(8,3),(10,2)）给）给B.B收到密文后，解密计算如下：收到密文后，解密计算如下：m=(10,2)-7(8,3)=(10,2)-21r=(10
34、,2)-8r=(10,2)+5r=4r+5r=9r=(10,9)，于是恢复了明文。，于是恢复了明文。272024/3/192024/3/19272024/3/192024/3/19272024/3/192024/3/1927275.5 RSA、ElGamal及椭圆曲线密码比较 RSA密密码码体体制制是是基基于于大大数数分分解解难难题题的的，出出现现的的时时间间是是20世世纪纪70年年代代，到到现现在在已已经经30多年了。多年了。经经过过比比较较长长时时间间的的使使用用和和学学者者们们的的研研究究，从从算算法法和和计计算算角角度度看看是是安安全全的的，只只是是随随着着人人类类计计算算能能力力的的
35、提提高高，RSA算算法法中中选选取取的的参参数数(p,q)越越来来越越大大，现现在在普普遍遍认认为为，n=pq的的取取值值为为2048比比特特是是安安全全的的，这这相相当当于于600位位的的十十进进制制整整数数。这这也也导导致致了了加解密的运算量和存储空间的增加，影响了其在便携产品如手机加解密的运算量和存储空间的增加，影响了其在便携产品如手机/PDA等中的使用。等中的使用。国际上一些标准化组织国际上一些标准化组织ISO,ITU及及SWIFT等均己接受等均己接受RSA体制作为标准。体制作为标准。在在Internet中所采用的中所采用的PGP中也将中也将RSA作为传送会话密钥和数字签字的标准算法。
36、由作为传送会话密钥和数字签字的标准算法。由于于RSA是简单且，比较成熟的一种公钥密码体制，许多公司及研究团体都对它进是简单且，比较成熟的一种公钥密码体制，许多公司及研究团体都对它进行了实现。行了实现。282024/3/192024/3/19282024/3/192024/3/1928ECCECC和和和和RSARSA安全性能比较安全性能比较安全性能比较安全性能比较292024/3/192024/3/19292024/3/192024/3/19292024/3/192024/3/192929 ElGamal密密码码体体制制是是基基于于离离散散对对数数难难题题的的，很很多多密密码码算算法法如如著著名
37、名的的密密钥钥交交换换算算法法DH(Diffie-Hellman)密密钥钥交交换换算算法法，以以及及后后面面学学到到的的美美国国的的数数字字签签名名标标准准（DSA）就就是是基基于于离离散散对对数数问问题题的的。ElGamal密密码码体体制制在在加加密密的的时时候候要要完完成成两两次次模幂运算，密文的长度是消息长度的两倍，在一定程度上影响了其广泛使用。模幂运算，密文的长度是消息长度的两倍，在一定程度上影响了其广泛使用。椭椭圆圆曲曲线线密密码码是是ElGamal密密码码体体制制在在椭椭圆圆曲曲线线上上的的应应用用，优优点点是是在在同同等等安安全全程程度度下下，其其密密钥钥比比RSA和和ElGam
38、al要要短短得得多多。由由现现有有的的资资料料可可知知，ECC的的密密钥钥长长度度为为160比比特特时时的的安安全全强强度度与与RSA的的密密钥钥长长度度为为1024比比特特时时相相当当，这这对对于于存存储储和和通通信信带带宽宽受受限限时时的的应应用用是是一一个个很很重重要要的的优优点点，比比如如PDA，IC卡卡，无无线线设设备备等等，而而且且160比比特特的的ECC的的运运算算速速度度比比1024比比特特的的模模运运算算快快。基基于于椭椭圆圆曲曲线线离离散散对对数数的的加密算法和签名算法被很多标准采用。加密算法和签名算法被很多标准采用。302024/3/192024/3/19302024/3
39、/192024/3/19302024/3/192024/3/1930305.6 其他非对称密码体制简介（略）除除了了前前面面介介绍绍的的基基于于大大数数分分解解难难题题的的RSA密密码码算算法法，基基于于离离散散对对数数难难题题的的ELGamal密密码码算算法法，基基于于椭椭圆圆曲曲线线离离散散对对数数难难题题的的椭椭圆圆曲曲线线密密码码算算法法外外，在在密密码码学学的的发发展展历历史史上上，还还有有一一些些其其他他的的非非对对称称密密码码算算法法，对对于于非非对对称称密密码码体体制制的的发发展展产生了重大影响。产生了重大影响。-背包公钥密码体制背包公钥密码体制312024/3/192024/
40、3/19312024/3/192024/3/1931 背背包包算算法法，公公钥钥密密码码体体制制的的第第一一个个算算法法是是有有Mercle和和Hellman开开发发的的背背包包算算法法，其其安安全全性性基基于于背背包包难难题题，这这是是一一个个NP完完全全问问题题。尽尽管管这这个个算算法法后后来来发发现现是是不不安安全全的的，但但由由于于它它证证明明了了如如何何讲讲NP完完全全问问题题用用于于公公钥钥密密码码学学，在在公公钥钥密密码码学学的的发发展史上有过重大的影响。展史上有过重大的影响。322024/3/192024/3/19322024/3/192024/3/1932332024/3/1
41、92024/3/19332024/3/192024/3/1933-Rabin公钥密码体制公钥密码体制342024/3/192024/3/19342024/3/192024/3/1934352024/3/192024/3/19352024/3/192024/3/1935362024/3/192024/3/19362024/3/192024/3/1936372024/3/192024/3/19372024/3/192024/3/1937-NTRU公钥密码体制公钥密码体制 NTRU(Number Theory Research Unit)公钥密码体制是由布朗大学公钥密码体制是由布朗大学 3 位数学家
42、位数学家Jeffrey Hoffstein，J.Pipher 和和 J.H.Silverman 于于 1996 年提出后，经过几年的迅速发年提出后，经过几年的迅速发展与完善，该算法在密码学领域中受到了高度的重视，并在实际应用中取得了良好展与完善，该算法在密码学领域中受到了高度的重视，并在实际应用中取得了良好的效果。的效果。NTRU 公钥算法的安全性不是基于传统的困难问题，而是公钥算法的安全性不是基于传统的困难问题，而是基于格基归约基于格基归约的困难的困难性性,建立在多项式环的基础之上的建立在多项式环的基础之上的，从现有技术来看，在量子计算机中本算法仍是安，从现有技术来看，在量子计算机中本算法仍
43、是安全的。全的。因此，从理论上来说为公钥密码体制开辟了一个新的领域。因此，从理论上来说为公钥密码体制开辟了一个新的领域。在以后的两年中，在以后的两年中，Don Coppersmith，Johan Hastad,Andrew Odlyzko,和和 Adi Shamir 等一些密码学界的资深专家对算法进行了深入的安全性分析，均没有发现等一些密码学界的资深专家对算法进行了深入的安全性分析，均没有发现 NTRU 算法存在有大的安全问题。在算法存在有大的安全问题。在 1998 年，年，Jeffrey Hoffstein、Jill Pipher 和和Joseph Silverman 正正 式式 发发 表表
44、 了了 论论 文文“NTRU:A New High Speed Public Key Crypto-system”。382024/3/192024/3/19382024/3/192024/3/1938 1999 年年,A.May 和和 P.Nguyen 于对该体制提出了一些攻击方法，在于对该体制提出了一些攻击方法，在 2000 年，年，Jeffrey Hoffstein 和和 Joseph Silverman 在对原有在对原有 NTRU 算法进行了改进，在不降低算法进行了改进，在不降低算法安全强度的情况下，进一步提高了算法的运算速度。算法安全强度的情况下，进一步提高了算法的运算速度。到目前为止
45、，有很多讨论到目前为止，有很多讨论 NTRU 算法安全性。但还没有哪一种分析方法能破译算法安全性。但还没有哪一种分析方法能破译该密码体制。该密码体制。在改进算法的同时，人们又开始研究在改进算法的同时，人们又开始研究 NTRU 签名算法，由于签名算法，由于 NTRU 的独特特性，的独特特性，其不能象其不能象 RSA 之类的公钥算法直接用于构造签名算法，因此借助于之类的公钥算法直接用于构造签名算法，因此借助于 NTRU 格的困格的困难性，提出了多种难性，提出了多种 NTRU 签名算法，如：签名算法，如：NSS，R-NSS和和 NTRU Sign等。等。自自 2000 年开始，美国年开始，美国 IE
46、EE 标准化组织起草专门针对标准化组织起草专门针对 NTRU 的标准的标准 P1363.1。在实际应用方面，在实际应用方面，NTRU 公司已对公司已对 NTRU 算法进行软硬件实现，并已作出产品，销算法进行软硬件实现，并已作出产品，销售量很好。售量很好。392024/3/192024/3/19392024/3/192024/3/1939 当前，当前，NTRU 公司还看好的三个项目公司还看好的三个项目“手机手机/PDA”、“无线无线 LAN”和和“IC 卡卡”其中，其中，IC 卡方面的应用被放在了首位。卡方面的应用被放在了首位。目前，在目前，在 IC 卡加密方面，主流方式是通用密钥方式卡加密方面
47、，主流方式是通用密钥方式“DES”，但是这种方式，但是这种方式“密钥长度较短，而且一旦通用密钥被盗则风险相当大密钥长度较短，而且一旦通用密钥被盗则风险相当大”，因此因此 NTRU 认为市场上存认为市场上存在着向该公司开发的公开密钥加密方式过渡的需求。在着向该公司开发的公开密钥加密方式过渡的需求。注注1 1：NTRUNTRU的的安安全全性性基基于于多多项项式式、不不同同模模混混合合运运算算的的相相互互作作用用和和从从一一个个非非常常大大的的维维数数格格中中寻寻找找最最短短向向量量的的困困难难性性。对对现现有有的的RSA、DSA等等公公钥钥密密码码体体制制而而言言，由由于于涉涉及及到到大大数数的的
48、模模指指运运算算，此此运运算算所所需需存存储储空空间间大大、速速度度慢慢。NTRU只只使使用用了了简单的模乘法和模求逆运算简单的模乘法和模求逆运算,因而它具有密钥产生容易因而它具有密钥产生容易,加、解密速度快等特点。加、解密速度快等特点。402024/3/192024/3/19402024/3/192024/3/19402024/3/192024/3/194040 -基基基基于于于于有有有有限限限限自自自自动动动动机机机机的的的的公公公公钥钥钥钥密密密密码码码码算算算算法法法法，这这是是由由中中国国密密码码学学家家陶陶仁仁冀冀提提出出的的，该该算算法法基基于于有有限限自自动动机机理理论论。如如
49、同同分分解解两两个个大大素素数数的的乘乘积积很很困困难难一一样样，要要分分解解两两个个有有限限自动机的合成也很困难。自动机的合成也很困难。-McElieceMcEliece算算法法，该算法由McEliece在在1978年年提提出出，是是一一种种基基于于代代数数编编码码理理论论的的公公开开密密钥钥密密码码系系统统。其其思思想想是是构构造造一一个个Goppa码码并并将将其其伪伪装装成成普普通通的的线线性性码码。不不过过该该算算法法的的公公开开密密钥钥太太庞庞大大，加加密密后后的的密密文文长长度度为为明明文文的的两两倍倍，在在一一定定程程度度上上影影响响了它的广泛了它的广泛应应用，故而研究的人也比用
50、，故而研究的人也比较较少。少。注注2 2：就就目目前前来来说说，NTRU 的的安安全全性性和和目目前前最最有有影影响响的的RSA算算法法、椭椭圆圆曲曲线线密密码码体体制制(ECC)等等算算法法是是一一样样安安全全的的，且且具具有有与与RSA同同等等程程度度的的安安全全性性，能能抵抵抗抗量量子子运运算攻击。算攻击。412024/3/192024/3/19412024/3/192024/3/19412024/3/192024/3/194141-多变量公钥密码体制（多变量公钥密码体制（Multivariate Public Key Cryptosystem，MPKC）被认为被认为是这样一种有希望的选
个人主页
