《密码学》05-4 椭圆曲线公钥密码体制

密码学第五章公钥密码5.4

椭圆曲线公钥密码体制ECC应用背景1有限域上的椭圆曲线2椭圆曲线公钥密码体制35.4

椭圆曲线公钥密码体制公钥密码体制都建立在数学难题之上，现在被广泛认可和使用的三类数学难题是：1、大整数因子分解问题；2、有限域乘法群上的离散对数问题；3、椭圆曲线上的离散对数问题。目前，前两个问题都有了亚指数时间算法。一、ECC应用背景

1985年，Koblitz

和Miller独立地提出了椭圆曲线公钥密码体制(ECC)，安全性基于椭圆曲线群上的离散对数问题的难解性，该问题目前最好的解法是指数级时间的算法。一、ECC应用背景

一般认为，RSA和D-H密钥交换协议需用1024比特以上的模数才安全，但对ECC，只要160比特的模数就可达到同样级别的安全性。一、ECC应用背景破解所需时间(MIPS年)RSA密钥大小ECC密钥大小RSA/ECC密钥大小之比10410810121020512768102420481061321602105：16：17：110：1ECC与RSA性能比较ECC的高强度安全性带来了许多优点：可使用较短的密钥；数字签名和证书小；运算速度快等。ECC标准：ANSIX9.62、IEEEP1363等。椭圆曲线指的是由Weierstrass方程所确定的曲线。先从来探讨椭圆曲线的图像。二、有限域上的椭圆曲线

实数域

R上的椭圆曲线xy二、有限域上的椭圆曲线

定义1

有限域

F上的椭圆曲线是由满足F上的方程的所有点和无穷远点O

构成的集合有时也记作E

。1、有限域上椭圆曲线的定义二、有限域上的椭圆曲线例：F23上的一个椭圆曲线为y2=x3+x

，(0,0),(1,5),(1,18),(9,5),(9,18),(11,10),(11,13),(13,5),(13,18),(15,3),(15,20),(16,8),(16,15),(17,10),(17,13),(18,10),(18,13),(19,1),(19,22),(20,4),(20,19),(21,6),(21,17),无穷远点Ο.则该方程在F23上的解(即该椭圆曲线上的点)为二、有限域上的椭圆曲线xy2、椭圆曲线上的加法运算设P,Q是E上的任意两点,P+Q=RR=P+QR’连接P,Q交E于R’,则称R’关于x轴的对称点R为P与Q的和,记为PQ二、有限域上的椭圆曲线R=P+Q=P+P=2P2、椭圆曲线上的加法运算此时称之为倍乘运算xyP(Q)R’R=2P当P与Q重合时二、有限域上的椭圆曲线2、椭圆曲线上的加法运算当P与Q关于x轴对称时,P+Q

=OxyQP定义P与Q的和为O

,即并称O

为无穷远点二、有限域上的椭圆曲线可以证明，有限域上的椭圆曲线在我们定义的加法运算下构成群。显然有

P+O=O+P=P

若P=(x,y)，则–P=(x,–y)且P+(–P)=O既然构成群，就必然有零元和负元，这里的零元就为无穷远点O，P的负元就是它关于x轴的对称点，记为–P。二、有限域上的椭圆曲线已知E(F)上两点P=(x1,y1),Q=(x2,y2),求P+Q。3、加法运算的代数表示xyR=P+QR’P(x1,y1)Q(x2,y2)解：设P+Q=R=(x3,y3),解得二、有限域上的椭圆曲线当P≠Q时，当P=Q时，xyRR’P(x1,y1)Q(x2,y2)xyRR’P(x1,y1)二、有限域上的椭圆曲线k(k>2)个相同的点P相加为xy此时称之为点乘运算P2P

3P二、有限域上的椭圆曲线定义2

设称

n

为点

P的阶，记为

n=ord(P)。

由阶为

n

的点

P

在上述加法定义下生成的循环群

<P>

是椭圆曲线群

(E(F),+)

的一个

n

阶子群。

二、有限域上的椭圆曲线

定义3

设E是有限域F上的椭圆曲线，G是E的一个循环子群，点P是G的一个生成元，即G={

kP:k1}，在已知P，

Q的条件下，求解整数n，使得nP=Q的问题，称为椭圆曲线E上的离散对数问题。1、安全性基础三、椭圆曲线公钥密码体制2、椭圆曲线公钥密码算法1）参数选取

选取有限域F上的椭圆曲线

在[1，n-1]内随机选取整数

d，计算

Q=dP用户公钥：点Q用户私钥：整数d和其上一个阶为素数

n

的点

P

=(xP，yP

)。三、椭圆曲线公钥密码体制2）加脱密算法加密：用户A给用户B发送信息

m，m

F（1）在[1，n-1]内随机选取整数

k，计算

kP=(x1，y1

)（2）计算kQ=(x2，y2)，若x2=0,则回到(1)（3）计算c=mx2密文为(x1，y1，c)三、椭圆曲线公钥密码体制脱密：（1）用自己的私钥

d计算(x2，y2

)=d(x