王晓静

(同济大学电子与信息工程学院，上海 201804)

0 引言

近年来，双线性对越来越广泛地被运用在密码学和各种加密方案中。由于它的独特性质，可以用来构造许多的加密方案和协议。例如群签名、短签名［1］、三方密钥协商［2］、可搜索加密等都要用到双线性对。

双线性对最早被应用在攻击椭圆曲线有理点群上的离散对数问题。攻击方法就是将椭圆曲线中的离散对数问题归约到有限域乘法群中的离散对数问题［3］。使用这种方法可以使得某些椭圆曲线有理点群中的离散对数问题变得容易。

双线性对的输入变量的系数可以灵活变化，它的双线性这一特点可以用来构造许多应用和协议方案。最常见的双线性对包括Weil［4］对和Tate对，以及Tate对的变种 Eta［5］对、Ate［6］对等。本文以研究 Tate 对为主，一般而言，计算Tate对的主要算法是Miller算法［7］。

在二元扩域GF(2m)中，双线性对选用超奇异曲线［7］Eb:y2+y=x3+x+b，b∈F2。对于曲线 y2+y=x3+x+1而言，目前m的推荐参数是283、353、367、457。本文Tate对计算都是在二元扩域GF(2457)中实现的。

模乘运算在硬件中实现很占资源，很多平台(如智能卡)无法实现高位的模乘运算。Jean-Claude Bajard等人在文献［8］中，介绍了一种小特征值的Montgomery模乘计算方法。本文结合文献［8］中介绍的改进的Montgomery算法和中国剩余定理，使得在只支持250 bits以内模乘运算的硬件平台上实现457 bits的二元扩域中Tate对最终模幂运算。

1 双线性对和Miller算法介绍

1.1 Tate对的基础知识

双线性对是一种如下形式的映射:

е:G1× G2→GT

其中G1和G2是加法群，GT是乘法群。

双线性对的基本性质:

(1)双线性:对任意的 P∈G1，Q∈G2，n∈Z，有 e( nP，Q)=e( P，nQ)=e(P，Q)n。

(2)非退化性:一定存在某个P∈G1和Q∈G2，使得e( P，Q)≠1，其中1代表乘法群中的单位元。……