方案避免了出现由部分成员可决定的系统秘密，所以对于内部成员同样具有较强的抗攻击能力 第6章 公钥密码体制 (2) 具有较强的防伪造性伪造者B′在不知道各个签名者Bi的私钥ki及随机数ui的情况下，伪造签名信息(m，s′，R)(其中s′≠s)满足广播多重签名公式(6-7)：或伪造签名信息(m,( ))(其中 )满足有序多重签名公式(6-3)：时，都是求解多重的椭圆曲线离散对数问题即使对于签名收集者Bc，方案也具有较强的防伪造性，因为签名者Bi的私钥和随机参数ui对Bc是保密的，要伪造签名，面对的是求解椭圆曲线离散对数问题 第6章 公钥密码体制 (3) 具有牢固的抗抵赖性两种多重签名子方案中，签名验证者对各个签名者公钥进行遍历，完成验证后，签名者Bi不能否认对消息进行了签名，因为完成签名协议过程的前提是掌握Bi的私钥及相应随机数ui (4) 算法简洁、高效方案充分发挥了ECC密钥短、安全性高的优势，密钥长度仅需160 bit就可以提供与1024 bit的RSA或DSA同样的安全度因此，该方案特别适用于计算能力和集成电路空间受限(如智能卡smart card)、带宽受限(如无线通信和某些计算机网络)、要求高效率实现的情况。
第6章 公钥密码体制 需要特别指出的是，方案中签名者Bi每次签名时必须更换随机产生的秘密参数ui例如，在有序多重签名方案中，如不更换随机数且签名的顺序保持不变，那么攻击者根据变化了的si与m′的值，依据式(6-4)，在经过2(i－1)次协议过程后，就可以联立2(i－1) 个关系式，从而求解出前面i－1个签名者的私钥与相应的随机数同理，在广播多重签名中，可由式(6-5)、(6-6)得到如不更换随机数，那么协议过程次数越多私钥就越不安全，当协议次数大于2n时，就完全有可能攻破私钥，伪造签名 第6章 公钥密码体制 4) 方案的软件实现效率与安全性 椭圆曲线密码软件实现时的函数包括：模一般素整数运算函数集，其中有加、减、乘、除、求逆；大素数域GF(q)中运算函数集，这其中也有加、减、乘、除、求逆；椭圆曲线基本运算函数集，其中有点加、倍点、固定点标量乘(scalar multiplication，即求固定点p的k倍)、随机点标量乘；辅助函数，如安全散列函数选择SHA_1或RIPEMD_160 第6章 公钥密码体制 模一般素整数运算与大素数域GF(q)中运算是ECC软件实现中调用最频繁的函数，这些函数采用汇编语言编写，其它的函数与算法用标准C语言编写。
表6-1列出了运用相关文献提出的椭圆曲线软件实现方法，在PⅢ800 MHz 128 M内存的运行环境下方案的执行效率 第6章 公钥密码体制 方案中，椭圆曲线选取192 bit二元域上的Koblitz曲线，安全素数(公开基点P的阶)是160 bit的素数利用目前对一般椭圆曲线离散对数问题进行攻击的最好方法Pollardρ算法，对于一台每分钟能执行1百万条指令的机器(每秒钟能执行4×104次椭圆曲线加法运算，在一年内可执行(4×104)(60×60×24×365)≈240次椭圆曲线点加运算)，要完成(πn/2)1/2≈280步攻击运算，至少需要9.6×1011年到2004年时，可得到的计算能力已为108 MIPS(一个MIPS为一台每分钟能执行1百万条指令的机器工作一年)，到2014年，可得到的计算能力为1010~1011 MIPS，即使此时要实现对此ECDLP的攻击也分别至少需要9.6×103年和9.6年(不考虑并行Pollardρ攻击方法)因此可以得出结论：对算法进行强力攻击在计算上是不可实现的，同时方案也以较少的存储空间和较小的通信带宽与系统开销实现了较高的安全性 第6章 公钥密码体制 多重数字签名是网络中常用的一种通信协议，但由于是通过多次签名与认证的策略实现联合签名以加强协议的安全性，因此多重签名方案存在着协议过程复杂、签名认证运算开销大等不足之处。
上文中提出的基于椭圆曲线密码的网络通信中的多重数字签名方案体现了低通信消耗(low communication costs)与低系统开销的设计原则 第6章 公钥密码体制 6.3 超椭圆曲线密码超椭圆曲线密码 Neal Koblitz和Victor Miller在20世纪80年代中期提出了椭圆曲线密码体制(ECC)，经过20多年的研究，ECC理论已经比较成熟，并且已经广泛应用于实际当中作为椭圆曲线的一个推广，Neal Koblitz在1989年提出了超椭圆曲线密码体制(HCC)，它的安全性基于有限域上超椭圆曲线的Jacobian上的离散对数问题的难解性 第6章 公钥密码体制 6.3.1 超椭圆曲线超椭圆曲线 定义 定义6-3 设F是域， 是其代数闭域，则F上亏格为g(g≥1)的超椭圆曲线C是指具有方程形式:C：v2+h(u)v=f(u) (6-8)的曲线这里h(u)∈F［u］是次数不大于g的多项式，f(u)∈F［u］是一个次数为2g+1的首一多项式，而且不存在 满足下列方程组:如果g=1，则称C为椭圆曲线 第6章 公钥密码体制 定义定义6-4 设K是F上的一个扩域，那么C上的一个K-点P是符号∞(称为C上的无穷远点)或是方程C：v2+h(u)v=f(u)的一个解(x，y)∈K×K。
C上的所有K-点记为C(K) 定义定义6-5 设P=(x，y)是一条椭圆曲线C：v2+h(u)v=f(u)上的一个有限K-点，那么它的相反点记为 如果P=∞，我们取 如果P是一个有限点且满足 ，则称P是一个特殊点，否则称P是一个普通点 第6章 公钥密码体制 引理引理6-1 设C是由方程C：v2+h(u)v=f(u)定义的域F上的超椭圆曲线，则满足： (1) 如果h(u)=0，那么Char(F)≠2 (2) 如果Char(F)≠2，那么作变换u→u及v→v－h(u)/2，从而将C的形式变为v2=f(u) (其中deguf=2g+1) 第6章 公钥密码体制 6.3.2 除子与除子与Jacobian群群 定义 定义6-6 一个除子d是C上若干点的一种形式和:其中只有有限个整数mP非零整数 称为d的度数，记为degdd在P点的阶是mP，表示为ordP(d)=mP设D表示C上所有除子的集合，那么D在如下加法规定之下是一个加群：设D0={d∈D|degd=0}，那么D0是D的一个子群 第6章 公钥密码体制 定义定义6-7 设C是域F上的一条超椭圆曲线，域 上C的坐标环是定义为 的商环。
中的元素称为C上的多项式函数 对每一个多项式函数 ，可以通过重复地将G(u，v)中的v2替换成f(u)－h(u)v来降低v的幂次，最终得到G(u，v)的一种唯一形式，可设为 第6章 公钥密码体制 定义定义6-8 设 是一个非零的多项式函数，P∈C，那么G在P点的阶记为ordP(G)，定义如下： (1) 如果P=(x，y)是一个有限点，那么可设G(u，v)=(u－r)r(a0(u)－b0(u)v)，这里r是可同时整除a(u)和b(u)的(u－x)的最高次幂如果(a0(x)－b0(x)y)≠0，则设s=0；否则，设s是使(u－x) s整除范数的最高次幂如果P是一个普通点，则定义ordP(G)=r+s；如果P是一个特殊点，则定义ordP(G)=2r+s 第6章 公钥密码体制 (2) 如果P=∞，则定义ordP(G)=－max{2degu(a)，2g+1+2degu(b)}对于一个非零的有理函数 及C上的一个点P的阶定义为ordP(R)=ordP(G)－ordP(H) 第6章 公钥密码体制 定义定义6-9 设 是一个有理函数，则R的除子定义为 例如，如果P是一个普通点，则有 ; 如果P是一个特殊点，则有div(u－x)=2P－2∞。
显然， 如果R=G/H，则div(R)=div(G)－div(H) 第6章 公钥密码体制 定义定义6-10 设J(更准确地说为 也可以用F的任何一个扩域代替)表示商域D0/P，J称为曲线C上的Jacobian群 设d1，d2∈D0，如果d1－d2∈P，那么记d1～d2，并称d1与d2等价 J中的每一个元素是D0中元素的一个等价类，它可以表示成d+P，或简单地记为 ，这里d∈D0是一个除子，并称为 的一个代表元很显然，该代表元不唯一J中元又称为除子类 第6章 公钥密码体制 6.3.3 超椭圆曲线超椭圆曲线Jacobian群中的运算群中的运算 定理 定理6-2 设d=∑miPi－∞∑mi是一个半约化除子，这里Pi=(xi，yi)∈C，设 ，那么存在唯一的一对多项式(a(u)，b(u))满足d=gcd(div(a(u))，div(b(u)－v))为了简便，通常将其写成div(a,b)因此，J中的每一个元素可唯一地表示成 其中，多项式a(u)、b(u)满足degub＜degua＜g及a(u)|(b2(u)+b(u)h(u)－f(u))，因此J(Fq)是一个有限Abelian群，且其阶＃J(Fq)≤q2g。
第6章 公钥密码体制 设D*表示所有约化除子div(a，b)组成的集合，a，b∈F(u)，且满足degub＜degua＜g及a|(b2+bh－f)，则集合J(F)与集合D*之间存在一个一一映射在如下的讨论中，我们可以将J(F)看成是D*，将 看成是div(a，b)，群J(F)的零元则是div(1，0) 第6章 公钥密码体制 此处定义一种运算，称为J(F)中的加法，用标记，这也被称为超椭圆曲线Jacobian上的除子加 设d1=div(a1，b1)，d2=div(a2，b2)∈D*，规定d1⊕d2=d(a，b)是由下列算法唯一确定的约化除子： (1) 利用广义Euclidean算法找出多项式d，s1，s2，s3∈F(u)，满足: d=gcd(a1，a2，b1+b2+h)，d=s1a1+s2a2+s3(b1+b2+h) (2) 置 第6章 公钥密码体制 (3) 置 (4) 如果degua＞g，则作变换a′←a，b′←b，并返回(3) (5) 输出div(a，b)即为d 第6章 公钥密码体制 有限域上超椭圆曲线的Jacobian是一个有限交换群，超椭圆曲线的Jacobian上的基本运算包括除子加、倍除子和除子标量乘。
Jacobian上实用的群运算算法最早是由Cantor提出的，当时只是限定在非特征2的域上之后，Neal Koblitz于1988年提出超椭圆曲线密码体制时将Cantor算法推广到了任意的域上Cantor-Koblitz群运算法则实际上等价于高斯的二元二次型归约算法Andreas Enge将归约算法进行了推广，在除子运算中运用了扩展的Euclidean算法，对几种除子运算的计算量作了理论上的分析，得到了一次除子加用到有限域GF(qn)中运算的平均值，其数据如表6-2所示(超椭圆曲线为C：v2+h(u)v=f(u)) 第6章 公钥密码体制 第6章 公钥密码体制 我们以F.G.Zhang［19］借助Frobenius自同态提出的一种快速除子标量乘算法为例，计算分析快速除子标量乘的运算量Zhang的方法可推广为一类计算超椭圆曲线除子标量乘的方法，实现步骤如下： (1) 输入一个除子D及一个正整数m; (2) 计算曲线Jacobian上的Frobenius自同态的特征多项式P(T); (3) 对于1≤i≤qg－1，预计算iD; 第6章 公钥密码体制 (4) 将m转换成符号q-进制： ，其中－qg+1≤i≤qg－1; (5) 令B:=〈1，0〉; (6) 对于i自l－1 递减到0，计算: B：B+rD 若ri不为零 (7) 输出B为mD。
下面我们以几条选定的GF(qn)上的超椭圆曲线为例，比较二元法与Zhang提出的方法计算qnP的运算量，如表6-3所示表中，a、m和s分别表示一次除子加、倍加和赋值运算) 第6章 公钥密码体制 第6章 公钥密码体制 6.3.4 超椭圆曲线密码体制超椭圆曲线密码体制(HCC) 设C是Fq上亏格为g的超椭圆曲线，J(Fq)是它的Jacobian， ，n是160 bit的大素数(h=1，或是较小的余因子)，q约为160 bitp∈J(Fq)是具有大素数阶n的一个约化除子，在g=2时， 设 ， Q=kP=［aq，bq］ ≠0，则Q可以作为公钥公布，k作为密钥保存，加密时将信息嵌入密钥当中 第6章 公钥密码体制 同时我们需要一个单射，将P对应于一个整数设ψ表示该对应关系，则ψ是一个从J(Fq) 到有限整数集 的单射，将其记为(P) x或(P) q很显然，这样的赋值映射是不唯一的在实际密码应用中，可以根据给定的超椭圆曲线规定一个适当的映射的值域范围下面是例子： (1) 设β＝(c0，c1，…，c2g－1)是集合{a0，…， ag－1，b0，…， bg－1}上的一个置换映射，那么是一个单的赋值映射。
第6章 公钥密码体制 (2) 先对每个ai与bi取模q，转换为不大于q－1的非负的整数，令上式表示将所有ai与bi取模q后的非负数联接而得到的整数 第6章 公钥密码体制 超椭圆曲线密码体制的安全性是建立在超椭圆曲线离散对数问题(HCDLP)的难解性之上的，目前对低亏格(g≤4)的HCC的攻击是指数时间的，对亏格小于4的一般超椭圆曲线没有发现亚指数时间攻击在与RSA或传统的离散对数密码系统相同的安全强度下，它可以使用更短的操作数长度实际中，操作数长度在50~80之间(依赖于亏格的取值)所建立的密码体制就足以抗击目前已知的攻击若取亏格为3，则所基于的有限域的大小可以是60 bit，由此所建立的密码体制的安全性与180 bit的ECC等同，远远大于1024 bit的RSA如果使用的是64 bit处理器的计算机，则超椭圆曲线的运算就可以用单个计算机的字去处理，从而避免了多精度整数运算，使得存储和运算更简单［1］ 第6章 公钥密码体制 6.3.5 基于超椭圆曲线密码体制的密码协议基于超椭圆曲线密码体制的密码协议 分工的社会化、经济的全球化促使经济业务更为复杂多变，单一的经营实体经常难以处理专业性强、职能特征突出的交易与事务，这就不可避免地出现了委托、信托、行寄的经营形式。
而在经营实体规模不断扩大的趋势下，所有权与经营权的分离也出现了管理经营的授权委托，比较典型的就是合伙制与股份公司制的受托经营在这些运作模式下，处理电子商务重大事务的真正决定权仍在所有者，由其对重大合同、契约等授权签字，而又需要由运作者执行签字这就内含一种代理行使签名权的机制，即代理签名同样，在B2B模式下的电子交易系统中，代理数字签名也成为代理营销方案保证交易真实性、完整性、有效性与可靠性的关键技术 第6章 公钥密码体制 1. 代理数字签名方案及其分类代理数字签名方案及其分类 代理数字签名可以分为单个代理签名与多重代理数字签名 1) 单个代理签名 设A，B是某个数字签名体制(M，S，K，SIG，VER)的两个用户，他们的私钥和公钥分别是(xA，yA)与(xB，yB)，若有以下5个条件成立，那么，就称A将他的数字签名权力委托给了B，称A为原始签名人，B为A的代理签名人，f为委托密钥，fAB为代理签名密钥 (1) A利用他的密钥xA计算出一个数f，并将f秘密地交给B； 第6章 公钥密码体制 (2) 任何人(包括B)在试图求出xA时，f不会对其有任何帮助； (3) B利用xB和f生成一个新的签名密钥fAB； (4) 存在一个公开的验证算法VERAB，满足对于任何s∈S和m∈M，都有VER(yA，s，m)=True，等价于s=SIG(fAB, m)； (5) 任何人在试图求出xA，xB，f或fAB时，任何数字签名SIG(fAB，m)都不会对其产生帮助。
第6章 公钥密码体制 2) 多重代理数字签名 若Ai(1≤i≤n)是某个数字签名体制(M，S，K，SIG，VER)的n个用户，Ai的秘钥与公钥对为(xi，yi)假若对于任意的Ai(1≤i≤n)都将他的签名权力委托给了B(设B得到的代理签名秘钥为fi)，B对某个特定的消息m∈M联合生成了一个多重签名s=SIG(f1，f2，…，fn，m)，使得验证这个多重签名的有效性时，必须使用所有Ai的公钥，那么称S为一个由B代表Ai (1≤i≤n)生成的多重代理签名［2］ 第6章 公钥密码体制 2. 基于基于HCC的单一代理数字签名方案的单一代理数字签名方案 方案包括系统初始化、委托过程、签名产生与签名验证过程，同时方案的协议方为原始签名者、代理签名者与签名验证者 第6章 公钥密码体制 1) 初始化过程 设C是Fq上亏格为g的超椭圆曲线，J(Fq)是它的Jacobian，#J(Fq)=hl，l是190 bit的大素数(h=1，或是较小的余因子)，q约为190/g bitP， P1∈J(Fq)是具有大素数阶的约化除子，它们的阶分别为L0、 L1(满足min(L0，L1)≥190 bit)。
n为一个大素数(满足n>max(L0，L1))H0、 H1、 H2为安全的散列函数，H0，H1，H2{0，1} *→Znka， kb∈ 分别为用户A和银行的私钥，Kb=kbP，Ka=kaP作为两者的公钥，密钥对 (Ka，ka)、 (Kb，kb)作为协议中的主密钥ψ表示是一个从J(Fq)到有限整数集 ={0，1，…，q2g+1－1}的单射函数，将其记为(P)x或(P)q公开n，P、 P1和H0、 H1、 H2以及公钥Kb=kbP，Ka=kaP设kA，kB∈(1，2，…，n－1)分别为A和B的私钥， KA=kAp，KB=kBp为A和B的公钥，共享的安全散列函数为H1和H2 第6章 公钥密码体制 2) 委托过程 (1) A随机选取u∈(1，2，…， n－1)，计算:R=up≠0，h=H1((R) x)f=hkA+u(mod n) (6-9)并将(R，f)秘密地发送给B (2) B计算h=H1((R) x)，然后验证:fp=hKA+R是否成立，若成立则计算f′=f+kB(mod n)(6-10) 第6章 公钥密码体制 3) 代理签名过程 对于某个消息m，B随机选取v∈(1，2，…， n－1)，计算得到T=vp≠0，再计算m′=H2(m)s=(T) xf′－m′v(mod n)(6-11)并将(m，s，R，T)发送给签名验证者。
第6章 公钥密码体制 4) 代理签名验证过程 验证者接收到(m，s，R，T)后，计算h=H1((R) x)，m′=H2(m)验证(T) x(hKA+R+KB)=sp+m′T (6-12)是否成立如果等式成立，则认为B代理A的签名有效；否则认定为无效签名 第6章 公钥密码体制 签名验证中，由式(6-11)可得式(6-12)右边=等式左边这就验证了上述单一代理数字签名方案的正确性 第6章 公钥密码体制 3. 基于基于HCC的多重代理数字签名方案的多重代理数字签名方案 1) 初始化过程 系统初始化和参数设定与单一代理数字签名的方案相同，假设ki，kB分别为Ai(i=1，2，…，n) 和B的私钥， Ki=kip，KB=kBp为Ai和B的公钥，共享的安全散列函数为H1和H2 第6章 公钥密码体制 2) 委托过程 (1) Ai随机选取ui∈(1，2，…， n－1)，计算Ri=uip≠0，hi=H1((Ri) x)fi=hiki+ui(mod n)(6-13)并将(Ri，fi)秘密地发送给B 第6章 公钥密码体制 (2) B在收到(Ri，fi)(i=1，2，…，n)后，计算hi=H1((Ri)x)，然后验证fip=hiKi+Ri是否成立。
若成立则认为(Ri，fi)是一个有效的子代理密钥; 否则B要求Ai重复(1)或终止协议过程 第6章 公钥密码体制 3) 代理签名过程 B在收到所有(Ri，fi)后，计算出 (6-14)对于某个消息m，B随机选取v∈(i=1，2，…， n－1)，计算T=vp≠0，m′=H2(m)s=f′－(m′+(T) x)v(mod n)(6-15)(s，T，R1，R2，…， Rn)为B代表Ai(i=1，2，…，n)生成的多重代理签名 第6章 公钥密码体制 4) 代理签名验证过程 验证者收到(s，T，R1，R2，…， Rn)和消息m后，计算hi=H1((Ri) x)，m′=H2(m)验证(6-16)是否成立如果等式成立，则认为B代理Ai生成的多重代理签名有效；否则认定为无效签名 第6章 公钥密码体制 签名验证中，由式(6-15)可得式(6-16)右边＝等式左边这就验证了上述多重代理数字签名方案的正确性 第6章 公钥密码体制 4. 代理数字签名方案分析代理数字签名方案分析 (1) 代理签名方案可具有区分与身份证实性根据式(6-10)，在单一代理签名中有f′=f+kB(mod n)根据式(6-14)，在多重代理签名中有 第6章 公钥密码体制 所以代理签名密钥的产生依赖于原始签名人的普通签名密钥，但不同于原始签名者的普通签名密钥，因此与原始签名密钥是可区分的，而且在存在多个代理签名者的情况下，每个代理签名者的子代理密钥(Ri，fi)也是不相同的。
所以，原始签名者可以将不同的代理者区分开，有效地实现对代理者的监督，防止代理签名权力的滥用在出现问题时，第三方也可以将原始签名者与代理签名者、不同的代理者区分开来 第6章 公钥密码体制 (2) 具有较强的防伪造性除了原始签名人A以外，任何人(包括代理签名者)在不知道私钥kA的情况下，都不能伪造原始签名人的普通签名信息同理，代理签名者的签名秘钥对于攻击者(包括原始签名者)也是安全的如果原始签名者委托了多人代理签名，则根据式(6-10) 、(6-14)，由于代理签名秘钥f′中引入了代理签名者的私钥kB，各个代理签名者之间也不能伪造签名信息，因为要伪造签名必须攻击相应代理签名者的私钥及随机数v，这就使得面对的都是求解HCDLP问题对于内部攻击，假定有m(m
由于代理签名密钥与普通签名密钥具有较强的防伪造性与身份证实性，因此签名验证者对各个原始签名者的公钥进行遍历，完成验证或(T) x(hKA+R+KB)=sp+m′T后，原始签名者Ai不能否认将代理签名权委托给了B，代理签名者B也不能否认对消息进行了签名，因为完成委托与代理签名协议过程的前提是掌握相应的私钥及协议中产生的随机数 第6章 公钥密码体制 (4) 代理签名权撤销灵活当原始签名人想撤消代理签名者Bi的代理签名权时，他可以通过媒体公开宣布原有委托信息(Ri，fi)不再有效，注销代理签名密钥f′但是这种广播方式必须要有签名机制，以防止攻击者发布伪造的撤销消息进行中间入侵攻击(intruder-in-middle attack) 第6章 公钥密码体制 (5) 算法简洁、高效方案充分发挥了HCC密钥短、安全性高的优势当超椭圆曲线亏格为3时，方案所基于的有限域仅需60 bit就可以提供与180 bit的ECC相同的安全强度 需要特别指出的是，签名者B每次签名时必须更换随机产生的秘密参数v，否则攻击者根据si与m′值的变化，从单一代理签名式(6-9)、 (6-10) 、(6-11)可得s=(T) x(hkA+u+kB)－m′v(mod n)经过四次协议过程就可以联立四个关系式，解出原始签名者与代理签名者的私钥与相应的随机数。
第6章 公钥密码体制 同理，在多重代理签名中，依据式(6-13)~(6-15)可得 如不更换随机数，那么协议过程越多私钥就越不安全，当协议次数大于2(n+1)时，就完全能够攻破私钥，破坏整个签名系统 第6章 公钥密码体制 6.4 基于身份的公钥密码体制基于身份的公钥密码体制6.4.1 基于身份的密码体制简介基于身份的密码体制简介 基于身份的密码体制最早于1984年由Shamir提出［8］，针对公钥基础设施利用向用户分发证书实现密钥管理而造成的使用上的不便，Shamir提出了用任意字符串作为密钥的思想，即IBE(Identity Based Encryption)，其主要思路是利用用户的身份信息(ID、邮箱等)生成公钥，从而信息的发送方无须访问任何证书机构或可信第三方就能得到接收方的公钥 第6章 公钥密码体制 Shamir通过邮件加密来阐述IBE的工作过程，当用户Alice要向Bob发送邮件时，假设Bob的邮箱为//，，无须从任何证书管理机构获得Bob的公钥证书Bob收到密文时，与称为私钥生成器(PKG，Private Key Generator)的第三方联系，通过认证后，得到自己的私钥，从而可以解密信息。
这样做可以大大简化邮件系统中的密钥管理，从而使公钥密码的应用变得极为方便 第6章 公钥密码体制 IBE的思想提出后，人们用各种数学工具设计了许多实现方案，但这些方法都有一定的局限性，因此，长期以来，设计实用的IBE方案被视为一个公开的难题2001年，Boneh和Franklin利用代数曲线上的双线性对实现了第一个既实用又安全的IBE方案［9］他们还利用随机预言机模型(ROM，Random Oracle Model)证明，该方案能抵抗不可区分的自适应选择密文攻击此后，大量基于双线性对技术的加密和签名机制被提出，基于身份的密码学研究成为学者们关注的热点目前，基于身份的方案包括基于身份的加密体制、可鉴别身份的加密和签密体制、签名体制、密钥协商体制、鉴别体制、门限密码体制和层次密码体制等 第6章 公钥密码体制 一个基于身份的密码体制由四个随机算法构成 初始化(Setup)：给定安全参数k，输出系统参数params和主密钥，系统参数包括消息空间M、密文空间C系统参数是公开的，而主密钥只有“私钥生成器”PKG知道 密钥提取(Extract)：输入系统参数params，主密钥和任意的ID∈{0，1}*，输出私钥d，其中ID为用户公钥，d为相应的私钥，提取算法由给定的公钥生成私钥d。
加密(Encrypt)：输入系统参数params、ID，以及m∈M，输出密文c∈C 解密(Decrypt)：输入系统参数params、ID，私钥d以及c∈C，输出m∈M 第6章 公钥密码体制 这些算法必须满足一致性条件，即当d为由提取算法产生的相对于ID的私钥时，对任意m∈M，有Decrypt(params，ID，c，d)=m其中，c=Encrypt(params，ID，m) 基于身份的密码体制建立在椭圆曲线密码学(ECC，Elliptic Curve Cryptography)的基础之上，ECC体制的安全基础是有限域中椭圆曲线上的点群中的离散对数问题(ECDLP，Elliptic Curve Discrete Logarithm Problem)目前的研究结果表明，解决椭圆曲线离散问题比有限域上的离散对数问题更加困难对椭圆曲线密码体制的研究与应用极大地促进了基于身份密码体制的研究 第6章 公钥密码体制 以下我们详细介绍Boneh和Franklin提出的IBE体制(BF方案)6.4.2 BF方案及其安全性方案及其安全性 1. 安全模型安全模型 在公钥密码体制中，由于加密密钥公开，因此认为攻击者拥有所有用户的公钥，并且可以任意选择明文进行加密，此外攻击者还有机会获得密文，而且可能利用各种途径来获得解密。
因此，足够安全的公钥密码体制应该能够抵抗选择密文攻击 第6章 公钥密码体制 公钥密码体制按照攻击者所掌握的条件及攻击目标的不同，可以分为 单向性(OW)安全：由密文不能恢复相应的明文； 不可区分性(IND)安全：对已知给定的两个明文，加密者随机选择其中一个进行加密，攻击者无法从密文中获知是对哪个明文的加密； 非延展性(NM)安全：攻击者无法构造与已给密文相关的新密文 以上安全性概念是依次加强的，NM比IND安全，IND比OW安全 第6章 公钥密码体制 此外，公钥密码体制还可按照可能的攻击模型分为 选择明文(CPA)攻击：攻击者可以先适应性选择明文，获得相应的密文； 非适应性选择密文(CCA1)攻击：攻击者除了可以适应性选择明文攻击外，在给定目标密文前，还可以任意选择密文并获得相应的解密； 适应性选择密文(CCA2)攻击：攻击者的唯一限制就是不能直接获得与目标密文相对应的明文，即攻击者可以在给定目标密文后，任意选择密文并获得相应的解密 同时考虑攻击目标和攻击模型，可以获得不同的安全性，其中最重要的是IND-CCA2和NM-CCA2安全，而二者被证明是等价的，所以通常意义上的选择密文攻击安全性是指IND-CCA2安全。
第6章 公钥密码体制 1) IND-ID-CCA IND-CCA是一种被普遍接受的公钥密码安全性标准，在一般情况下，对于攻击者所掌握的条件可以定义为得到了某个公钥ID相对应的私钥，而在IBE中，选择密文攻击安全性的定义必须有所加强这是因为攻击者在攻击时，可以任意选择系统中任何一个用户的ID因此应该定义为允许攻击者任意选择公钥IDi，并得到与之相应的私钥这个条件被称为私钥提取询问(Private Key Extraction Query)，而加入了私钥提取询问条件的IND-CCA记作IND-ID-CCA 第6章 公钥密码体制 在定义IND-ID-CCA安全的IBE系统时，Boneh和Franklin设计了如下攻击游戏： 初始化：挑战者选择安全参数k，运行IBE中的初始化算法，将系统参数送给敌手，而将主密钥保密 阶段1：敌手发出m个询问q1，q2，…，qm其中，qi可以是以下二者之一： (1) 提取询问〈IDi〉，此时挑战者的响应是运行IBE中的密钥提取算法，产生相应于公钥IDi的私钥di并将其送给敌手 第6章 公钥密码体制 (2) 解密询问〈IDi，ci〉，此时挑战者的响应是运行密钥提取算法，产生私钥di，然后运行解密算法，利用di对密文解密，将明文送给敌手。
敌手可以根据q1，q2，…，qi－1的结果自适应地选择qi为何种询问 挑战：阶段1结束后，挑战者输出两个明文m0，m1∈M，以及要挑战的公钥ID，唯一的限制条件是ID不出现在阶段1的任何询问中挑战者随机选择1比特b∈{0，1}，设置C=Encrypt(params，ID，Mb)，将C作为挑战发送给敌手 第6章 公钥密码体制 阶段2：敌手发出更多的询问qm+1，…，qn其中，qi为以下二者之一： (1) 提取询问〈IDi〉，其中IDi≠ID，挑战者的响应如阶段1 (2) 解密询问〈IDi，ci〉≠〈ID，c〉，挑战者的响应如阶段1 猜测：敌手输出一个猜测b′∈{0，1}，如果b′=b，则获胜 第6章 公钥密码体制 进行以上攻击的敌手A被称为一个IND-ID-CCA攻击者，其优势定义为 如果不存在敌手A，能以不可忽略的优势在上述攻击游戏中获胜，则说一个IBE系统在IND-ID-CCA下是语义安全的不可忽略的优势”理解为存在某个多项式f，使得 ，其中k为系统的安全参数 第6章 公钥密码体制 2) OWE 为了证明IBE系统的安全性，需要采用一个弱化的安全概念，称为单向加密(OWE，One-Way Encryption)。
OWE是针对标准公钥体制而定义的，其含义为：假设敌手A掌握了一个随机的公钥Kpub和密文c，c是利用Kpub对随机明文m加密的结果，攻击者的目标是恢复相应的明文，其优势定义为Pr［A(Kpub，c)=m］ 如果不存在多项式时间攻击者，能够以不可忽略的优势攻破该体制，则称一个公钥体制是单向加密体制 第6章 公钥密码体制 在IBE中，Boneh和Franklin对该定义进行了强化，即如果不存在多项式时间的敌手，能以不可忽略的优势在以下的攻击中获胜，则称一个IBE体制是基于身份的单向加密体制(ID-OWE)攻击包括四个步骤： 初始化：挑战者选择安全参数k，运行IBE中的初始化算法，将系统参数给敌手，而将主密钥保密 第6章 公钥密码体制 阶段1：敌手发出私钥提取询问ID1，…，IDr，挑战者运行密钥提取算法，输出每个公钥IDi对应的私钥di，并将其传给敌手； 挑战：阶段1结束后，挑战者输出公钥ID≠ID1，…，IDrID为其要挑战的公钥，随机选择m∈M，并用ID对m加密，将密文c送给敌手 阶段2：敌手发出更多的询问IDr+1，…，IDn，要求IDi≠ID，挑战者的响应如阶段1。
猜测：最后敌手输出消息m′∈M，如果m′=m，则获胜 第6章 公钥密码体制 2. 数学工具数学工具 1) 双线性映射 定义定义6-11 令G1和G2为两个阶为素数q的循环群，P为G1的生成元，如果映射e：G1×G1→G2满足如下性质，则称e为双线性映射： (1) 可计算性：给定P，Q∈G1，存在一个多项式时间算法计算e(P，Q)∈G2； (2) 双线性性：对任意P，Q∈G1，a，b∈Zp，有e(aP，bQ)=e(P，Q) ab； (3) 非退化性：存在P∈G1，使得e(P，P)≠1 第6章 公钥密码体制 此时，称G1为双线性群，如果其中的群运算以及双线性映射都是可以有效计算的注意，映射e是对称的，因为e(Pa，Pb)=e(P，P) ab=e(Pb，Pa) 第6章 公钥密码体制 在加法群G1上，有如下一些数学难题： (1) 离散对数问题(DLP)：对P，Q∈G1，找到一个整数n∈ ，使Q=nP成立； (2) Difie-Hellman判定问题(DDHP，Decisional Diffie-Hellman Problem)：对于a，b，c∈ ，给定P，aP，bP，cP∈G1，判定c=ab mod p是否成立； (3) Difie-Hellman计算问题(CDHP，Computational Diffie-Hellman Problem)：对a，b∈ ，给定P，aP，bP∈G1，计算abP。
第6章 公钥密码体制 2) Weil对及其性质 令p为素数，满足p=2 mod 3，且存在素数q，使得p=6q－1，令E/Fp为由Fp上方程y2=x3+1确定的椭圆曲线，这种曲线满足如下性质： (1) 由于x3+1是Fp上的置换多项式，因而E/Fp中包含p+1个点，令O表示无穷远点，P∈E/Fp为 阶群Gq中的生成元； (2) 对任意y0∈Fp，存在唯一的点(x0，y0)∈E/Fp从而若(x，y)随机地取遍E/Fp上的非零点，则y随机地取遍Fp上的所有点； 第6章 公钥密码体制 (3) 若ζ∈ ，ζ≠1，为x3－1=0 mod p的根，则映射φ(x，y)=(ζx，y)为曲线E上的自同构，注意到P=(x，y)∈E/Fp,从而有 ，但φ(P) E/Fp，因此P∈E/Fp与φ(P)线性无关； (4) 由于点P与φ(P)线性无关，它们可以生成一个与Zq×Zq同构的群，将该群记作E［q］ 令μq为 中由所有 阶点构成的子群，曲线 上的Weil对定义为映射e：E［q］×E［q］→μq定义修正后的Weil对为 (6-17) 第6章 公钥密码体制 修正后的Weil对满足以下性质： (1) 双线性性：对任意P，Q∈Gq，a，b∈Z，有 ； (2) 非退化性： 是q阶元素，事实上，它是μq的生成元； (3) 可计算性：给定P，Q∈Gq，存在一种有效的算法计算 。
第6章 公钥密码体制 3) Weil Diffie-Hellman (WDH)假设 在双线性群中，BDHP问题是指已知P，aP，bP，cP∈G1，计算W=e(P，P) abc在现有条件下，不存在多项式算法解决BDHP问题 Jouxt和Nguyen指出［12］，在群Gq中，CDHP问题是困难的，而DDH(Decisional Diffie-Hellman)问题容易解决因为给定P，aP，bP，cP∈Gq，易知 第6章 公钥密码体制 从而修正后的Weil对提供了一种简单的方法来验证Diffie-Hellman向量，所以，不能利用DDH问题在群Gq上构建公钥密码体制，而必须依赖于以下的CDH假设的变体，即WDH (Weil Diffie-Hellman)假设 WDH假设：令p=2 mod 3为一个k比特素数，且存在素数q，使得p=6q－1，E/Fp为Fp上由y2=x3+1确定的椭圆曲线，P∈E/Fp为曲线上的q阶元，双线性映射 如式 (6-17)中所定义，则WDH问题描述为，对任意的a，b，c∈ ，给定〈P，aP，bP，cP〉，计算 WDH假设是指当p为随机的k比特素数时，不存在多项式时间算法求解WDH问题。
第6章 公钥密码体制 3. BasicIdent方案方案 在描述基于Weil对的IBE方案之前，为了使该方案更易于理解，Boheh和Franklin给出了一种简化的IBE体制，称为 BasicIdent，并指出这种体制在选择密文攻击下是不安全的 BasicIdent方案的构建环境：令p=2 mod 3为一个k比特素数，且存在素数q，使得p=6q－1，E为由Fp上方程y2=x3+1确定的椭圆曲线，BF方案利用一个算法MapToPoint将任意串ID∈{0，1}*映射到曲线上的q阶点QID，令G为Hash函数G：{0，1}*→Fp 第6章 公钥密码体制 MapToPoint算法描述如下： (1) 计算y0=G(ID)及 (2) 设Q=(x0，y0)∈E/Fp，令QID=6Q，则QID即为曲线上的q阶点 BasicIdent方案包括如下四大步骤 第6章 公钥密码体制 初始化： Step1：选择一个k 比特大素数，且存在素数q>3，使得p=6q－1，E为由Fp上方程y2=x3+1确定的椭圆曲线，在E/Fp上随机选取q阶点P； Step2：随机选择 ，令Ppub=sP； Step3：选择Hash函数H： →{0，1} n，G：{0，1}*→Fp，在安全性分析中，将H与G视为随机预言机(Random Oracle)。
第6章 公钥密码体制 系统的消息空间为M={0，1} n，密文空间为C=E/Fp×{0，1}n，系统参数为params=〈p，n，P，Ppub，G，H〉，主密钥为 提取：对给定的串ID∈{0,1}*，算法通过如下方法生成私钥d Step1：利用MapToPoint将ID映射为E/Fp上的q阶元QID； Step2：计算私钥dID=sQID，其中s为主密钥 加密：对消息m∈M加密时，进行如下步骤 Step1：利用MapToPoint将ID映射为E/Fp上的q阶元QID； Step2：随机选择r∈Zq； Step3：计算密文其中， 第6章 公钥密码体制 解密：解密：令c=(U，V)∈C为利用公钥ID加密后的密文，如果U不是E/Fp上的q阶点，则丢弃此密文，否则，利用私钥dID进行如下计算来解密： 第6章 公钥密码体制 以下定理表明，在WDH假设成立的前提下，BasicIdent方案具有单向性 定理 定理6-3 令H与G为随机预言机，假设存在一个ID-OWE敌手A，能以优势ε攻破BasicIdent，并且假设A最多进行了qE>0次私钥提取询问及qH>0次Hash询问，那么存在算法B，能以至少 的优势计算WDH，其中e≈2.71，为自然对数的底，而B的运行时间是O(time(A))。
证明详见参考文献［5］ 第6章 公钥密码体制 4. 具有选择密文攻击安全性的具有选择密文攻击安全性的IBE 利用Fujisaki-Okamoto在参考文献［13］中提供的方法，可以将BasicIdent方案转化为在随机预言模型下具有选择密文攻击安全性的IBE 设E为一个公钥加密方案，用Epk(m; r)表示在公钥pk下利用随机比特r对m加密的结果，Fujisaki-Okamoto定义了混合方案Ehy如下：其中，σ为随机生成的串; H1，G1为Hash函数Fujisaki-Okamoto证明了如果E为单向加密方案，则Ehy是在随机预言模型下选择密文攻击安全(IND-CCA)的方案 第6章 公钥密码体制 如果将上述变换施加于BasicIdent，则可以得到一个IND-ID-CCA的IBE体制，称之为FullIdent 设n为要加密的消息长度，FullIdent方案描述如下所述 初始化：与BasicIdent基本相同，区别是还需要选择Hash函数H1：{0，1}n×{0，1} n→Fq，以及G1：{0，1} n→{0，1} n 第6章 公钥密码体制 提取：与BasicIdent相同。
加密：用公钥ID对消息m∈M加密时，进行如下步骤 Step1：运行算法MapToPoint，将ID转化为E/Fp中的q阶点QID； Step2：随机选择σ∈{0，1} n； Step3：令r=H1(σ，m)； Step4：计算密文为其中， 第6章 公钥密码体制 解密：设c=〈U，V，W〉为用公钥ID加密后的密文，如果U不是E/Fp中的q阶点，则丢弃该密文，否则，利用私钥dID进行如下的解密过程 Step1：计算 ； Step2：计算m=W⊕G1(σ)； Step3：令r=H1(σ，m)，验证是否有U=rP，若未通过验证，则丢弃该密文； Step4：输出m作为解密结果 第6章 公钥密码体制 以下定理表明了当WDH假设成立时，FullIdent是一个选择密文攻击安全的IBE体制，即IND-ID-CCA 定理定理6-4 设A为一个IND-ID-CCA攻击者，其运行时间为t，A能以优势ε成功攻破FullIdent假设A最多进行了qE次提取私钥询问、 qD次解密询问以及分别qH、 、 次对于Hash函数H、G1、H1的询问，则存在一个运行时间为t1的算法，可以以优势ε1解决WDH问题，其中 第6章 公钥密码体制 其中，函数FOadv定义为证明详见参考文献［5］。