椭圆曲线、双线性对与群签名

第9章密码学新技术主讲人：叶世贝、倪凯敏、高闯2020/5/2719.1椭圆曲线★椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似。在数学上，椭圆曲线的曲线方程是以下形式的三次方程：y2=x3+ax+b因为＝(a/3)3+(b/2)2=(4a3+27b2)/108是方程x3+ax+b＝0的判别式，当4a3+27b2＝0时方程有重根，设为x0，则点Q0＝(x0,0)是椭圆曲线的重根即x3+ax+b＝(x-x0)3，重根使一阶导数3x2＋a在该Q0点为0令F(x,y)=y2－x3－ax－b，则F/x|Q0=F/y|Q0=0所以dy/dx=－(F/x)/(F/y)＝(3x2＋a)/2y在Q0点无定义，即曲线y2≡x3+ax+b在Q0点的切线无定义，因此点Q0的倍点运算无定义所以要求判别式=4a3+27b202020/5/2729.1椭圆曲线★实数域上的椭圆曲线对于固定的a和b，满足形如方程y2=x3+ax+b的所有点（x，y）集合，外加一个无穷远点O，其中，a、b是实数,x和y在实数域上取值。★有限域GF(p)上的椭圆曲线对于固定的a和b，满足形如方程y2≡x3+ax+b(modp)(a,b,x,yGF(p),4a3+27b2(modp)≠0)的所有点（x，y）集合，外加一个零点或无穷远点O，其中，a、b、x和y均在有限域GF(p)上取值，即在{0,1,2,…p-1}上取值。P是素数。2020/5/2739.1椭圆曲线2020/5/274★一般来说，Ep(a,b)由以下方式产生：①对每一个x(0xp且x为整数），计算x3+ax+b(modp)。②在①中求得的值在模p下是否有平方根，如果没有，则曲线上没有与这一x相对应的点；如果有，则求出两个平方根y和-ymodp(y=0时只有一个平方根)。★有限域GF(2^m)上的椭圆曲线对于固定的a和b，满足形如方程y2≡x3+ax+b(modp)的所有点（x，y）集合，外加一个零点或无穷远点O，其中，a、b、x，yGF(2^m)GF(2^m)上的点是m位比特串。9.1.1椭圆曲线的加法运算法则2020/5/275★Ep(a,b)上的加法定义如下：设P，QEp(a,b)，则①P+O=P；②若P=(x,y)，那么(x,y)+(x,-y)=O，即(x,-y)是P的加法逆元，记为-P。•显然任一点P和其逆元-P都是Ep(a,b)中的点，•如P=(1,11)和-P=(1,-11)=(1,12)E23(1,4)③设P=(x1,y1)，Q=(x2,y2)，P≠-Q，则P+Q=(x3,y3)由以下确定：•x3≡λ2－x1－x2(modp)•y3≡λ(x1－x3)－y1(modp)•其中λ＝•切线，倍乘9.1.1椭圆曲线的加法运算法则2020/5/276★两相异点相加：P,Q为椭圆曲线上相异两点，有P+Q=R，点R是经过P、Q两点的直线与曲线相交点的唯一负点（逆元）。★倍乘运算：P的倍点2P是经过点P的切线与椭圆曲线相交点的负点（逆元）。若存在最小正整数n使nP=0成立，则点P的阶(周期)为n。★倍乘运算仍定义为重复加法，如4P=P+P+P+P★Ep(a,b)是一个Abel群对一般的Ep(a,b)，其上的加法运算是封闭的，满足交换律、结合律，其上的加法逆元运算也是封闭的，有单位元O，所以Ep(a,b)是一个Abel群。9.1.2椭圆曲线的应用2020/5/277★椭圆曲线群中的离散对数问题是指已知群中的P和Q，求解方程：kP=Q中k值的问题。由k和P易求Q，但由P、Q求k则是困难的，这就是椭圆曲线上的离散对数问题，可应用于公钥密码体制。★例：对基于GF(23)的椭圆群y2＝x3+9x+17(mod23)，求Q=(4，5)对于P=(16，5)的离散对数。P＝(16，5)，2P=(20，20)，3P＝(14，14),4P=(19，20)，5P＝(13，10)，6P＝(7，3)，7P＝(8，7)，8P＝(12，17)，9P＝(4，5)因此k关于Q的离散对数是9，点P称为基点。明文到椭圆曲线上的嵌入2020/5/278★使用椭圆曲线构造密码体制前，需将明文嵌入到椭圆曲线上，作为椭圆曲线上的点。设明文消息为m，令k为一个大整数，满足(m+1)kp，如下计算一系列x：x＝{mk+j,j=0,1,2,…k-1}，直到是x3+ax+b(modp)是平方剩余，即得到椭圆曲线上的点(x,)。因为在0到p的整数中，有一半是模p的平方剩余，一半是模p的非平方剩余。所以k次找到x，使得x3+ax+b(modp)是平方根的概率不小于1－1/2k。反之，从椭圆曲线上点(x,y)得到明文消息m，只须求m＝x/k椭圆曲线上的密码★利用椭圆曲线实现ElGamal密码体制首先选取一条椭圆曲线，并得Ep(a,b)，将明文消息m通过编码嵌入到曲线上点Pm，再对点Pm做加密变换。取Ep(a,b)的一个生成元G，G的阶为素数n，Ep(a,b)、G和n作为公开参数。用户A在[1,n-1]上选随机整数kA作为私钥，并以PA=kAG作为公钥任一用户B若想向A发送消息Pm，可在[1,n-1]选取一随机正整数k，产生以下点对作为密文：Cm={kG，Pm+kPA}A解密时，以密文点对中的第二个点减去用自己的秘密钥与第一个点倍乘，即(Pm+kPA)－kAkG=Pm+k(kAG)－kAkG=Pm攻击者若想由Cm得到Pm，就必须知道k。而要得到k，只有通过椭圆曲线上的两个已知点G和kG，这意味着必须求椭圆曲线上的离散对数，因此不可行。2020/5/279椭圆曲线上的密码★利用椭圆曲线实现Diffie-Hellman密钥交换第1步：选取一个基域GF(p)和两个参数a、b，则得椭圆曲线上的点及无穷远点构成Abel群Ep(a,b)。第2步:取Ep(a,b)的一个生成元G＝(x1,y1)，G的阶是素数n。Ep(a,b),G,n作为公开参数。第3步:用户A和B之间的密钥交换如下进行：•①A随机选整数kAn，保密kA，计算PA=kAG产生Ep(a,b)上的一点发给B•②B类似地选取秘密的kB并计算PB发给A•③A、B分别由K=kAPB和K=kBPA产生出双方共享的秘密钥事实上K=kAPB=kA(kBG)=kB(kAG)=kBPA•攻击者若想获取K，则必须由PA和G求出kA，或由PB和G求出kB，即需要求椭圆曲线上的离散对数，因此是不可行的。•如果将这一密钥用作传统密码中的会话密钥，可简单地取点坐标中的一个，如取x坐标，或取x坐标的某一简单函数。2020/5/2710椭圆曲线密码体制的优点★与基于有限域上离散对数问题的公钥体制相比，椭圆曲线密码体制有如下优点:(1)安全性高攻击有限域上的离散对数问题可以用指数积分法对椭圆曲线上的离散对数问题并不有效。目前攻击椭圆曲线上的离散对数问题的方法只有适合攻击任何循环群上离散对数问题的大步小步法，其运算复杂度高。(2)密钥量小在实现相同安全性能条件下，椭圆曲线密码体制所需的密钥量远比基于有限域上的离散对数问题的公钥体制的密钥量小。2020/5/2711椭圆曲线密码体制的优点(3)灵活性好有限域GF(P)一定的情况下，其上的循环群是确定的GF(P)上的椭圆曲线可以通过改变曲线参数，得到不同的曲线，形成不同的循环群。可在和RSA/DSA体制同样安全性能的前提下大大缩短密钥长度(目前160比特足以保证安全性)，因而在密码领域有着广阔的应用前景下表给出了椭圆曲线密码体制和RSA/DSA体制所需的密钥的长度2020/5/27129.2双线性对Menezes、Okamota和Vanstones在1983年，在有限域上定义了一种特殊的椭圆曲线,即超奇异曲线，并指出了这些椭圆曲线上利用椭圆曲线离散对数问题构建密码体制较标准的离散对数问题可使用较小的有限域的优势不存在了。但Joux首先利用椭圆曲线中的Weil配对构造了一个一轮三方密钥交换协议，随后Boneh和Franklin用Weil配对构造了一个基于身份的加密体制。从此以Weil配对技术为基础的各种密码学算法层出不穷，成为近年来的一个研究热点。2020/5/27139.2.1双线性映射在超奇异曲线中，存在一个有效算法，将曲线（在有限域上）上的两点映射到基域中的一个元素。超奇异曲线中,典型的代表是Weil对和Tate对。这两个超奇异椭圆曲线对改造可以用来构造双线性对。双线性对的基本概念如下。设𝑮𝟏，𝑮𝟐分别是同为q阶的加群和乘群,并且假设𝑷为𝑮𝟏的生成元。假设在群𝑮𝟏，𝑮𝟐，中，离散对数问题是难解的。可以定义双线性映射对为𝒆：𝑮𝟏×𝑮𝟏→𝑮𝟐，并且满足以下特性：（1）双线性。对所有的𝑷，𝑸∈𝑮𝟏和𝒂，𝒃∈𝒁𝒒∗，𝒆𝒂𝑷,𝒃𝑸=e𝒂𝒃𝑷,𝑸=e𝑷,𝒂𝒃𝑸=e𝑷,𝑸𝒂𝒃（2）非退化性。存在一个P∈𝑮𝟏，满足𝒆𝑷,𝑷≠𝟏。（3）可计算性。对P，Q∈𝑮𝟏，存在一个有效的算法计算e𝑷,𝑸。2020/5/27149.2.2双线性对在密码学中的应用在数字化的信息社会里，数字签名代替了传统的手写签名和印签，是手写签名的电子模拟。在使用数字签名的过程中，仍然会遇到需要将签名权委托给其他人的情况。比如，某公司的经理由于业务需要到外地出差。在他出差期间，很可能有人给他发来电子邮件，其中有些邮件需要及时回复。然而，他出差的地方很偏僻，没有覆盖互联网，因此，该经理不得不委托他的秘书代表他处理这些电子邮件，包括代表他在回复这些电子邮件时在回信上生成数字签名。那么如何以安全、可行、有效的方法实现数字签名权利的委托？2020/5/27159.2.2双线性对在密码学中的应用1996年，Mambo、Usuda和Okamoto首先提出代理签名的概念。所谓代理签名是指在一个代理签名方案中，代理签名人代表原始签名人生成的有效的签名。由初始化过程，数字签名权力的委托过程，代理签名的生成过程和代理签名的验证过程四部分组成。1982年，Chaum首次提出了盲签名的概念。所谓盲签名，就是先将要隐藏的文件放进信封里，当文件在一个信封中时，任何人都不能读它。对文件签名就是通过在信封中放一张复写纸，当签名者在信封上签名时，他的签名便会透过复写纸签到文件上。盲签名是一种特殊的数字签名，它与通常的数字签名的不同之处在于，签名者并不知道他所要签发文件的具体内容。正是这一点，使得盲签名这种技术可广泛应用于许多领域，如电子投票系统和电子现金系统等。2020/5/2716基于双线性对的代理签名方案在基于双线性对的代理签名方案中，用户的私钥是自己选定，而不是系统颁发的，因此不同于基于身份的签名方案。（1）系统参数的建立。①生成两个阶都为素数q的群𝑮𝟏，𝑮𝟐，𝑒是一个双线性映射，任意选取一个生成元𝑷∈𝑮𝟏。②系统选取𝒔∈𝒁𝒒∗𝑹作为系统的主密钥，算出𝑷𝒑𝒖𝒃=𝒔𝑷作为系统的公钥。③选取Hash函数h：𝟎,𝟏𝒏→𝑮𝟏，该Hash函数把用户的身份ID映射到𝑮𝟏中的一个元素。另外一个Hash函数为𝒉𝟏：𝟎,𝟏𝒏→𝒁𝒒，该𝑯ash函数决定明文空间是𝟎,𝟏𝒏。2020/5/2717基于双线性对的代理签名方案公开的系统参数为𝑮𝟏,𝑮𝟐,𝒆,𝒏,𝒒,𝑷′,𝑷𝒑𝒖𝒃,𝒉,𝒉𝟏。（2）用户公私钥对的生成。设用户A任意选取一个随机数𝒔𝑨∈𝒁𝒒∗，计算𝑷𝑨=𝒔𝑨𝑷作为自己的公钥，那么A的公私钥对就是（𝒔𝑨，𝑷𝑨）；同理，用户B的公私钥对为（𝒔𝑩，𝑷𝑩）。（3）委托过程。①设原始签名A写给B的代理签名授权委托书为𝒎𝒘，计算𝑽=𝒔𝑨𝒉𝒎𝒘，将𝑽,𝒎𝒘发送给B；②B接收到𝑽,𝒎𝒘，验证𝒆𝑽,𝑷=𝒆𝒉𝒎𝒘,𝑷𝑨是否成立。若不成立，则拒绝接受A的委托；否则，接受委托，并计算代理签名