求解迹1椭圆曲线上的离散对数

胡建军,王 伟,李恒杰

(兰州文理学院 数字媒体学院, 甘肃 兰州 730010)

Smart[1]提出一种有效的在迹1椭圆曲线上求解离散对数的方法,Monnerat[2]较为详细地描述了迹1椭圆曲线上求解离散对数的实施方法,Bradley[3]介绍了迹1椭圆曲线上求解离散对数的具体实践. 20多年来,学者们针对迹1椭圆曲线的理论研究较多[4-6],这些研究成果对于信息安全和密码学的应用起到了积极的作用,然而学者们对迹1椭圆曲线的攻击实践研究关注度不够,对于理解和应用迹1的椭圆曲线的研究也是不够的[7-9].

在迹1椭圆曲线上求解离散对数的实质是利用扩域上点的扭曲特征,通过约减和形式对数理论解决离散对数问题[10-12].为了较好地理解迹1椭圆曲线的理论成果及了解算法攻击的实施过程和效果,论文给出求解离散对数的实践方法,利用Hensel提升理论,将素数域Fp的点提升到p上,再通过约减和形式对数的方法求解离散对数问题,分析了该方法的计算效率,最后通过实例验证了该方法的正确性和有效性.

1 椭圆曲线的性质及Nigel Smart攻击

1.1 椭圆曲线的性质

(1)

(2)

(3)

x3=μ2-x1-x2,(x1,y1)+(x2,y2)=(x3,μ(x1-x3)-y1),

(4)

性质1椭圆曲线的迹与阶满足N=p+1-t,其中t为椭圆曲线的迹.

迹为1的椭圆曲线称为反常曲线(anomalous).反常曲线的阶等于点的个数,即N=p.

定义域K的最小素数子域的阶称为域K的特征,记为char(K).

因为有理数域和实数域不存在最小素数子域,因此有理数域和实数域的特征为0.

性质3设p是p-adic下的有理数域,则char(p)=0.

1.2 Nigel Smart攻击

设E(p)是的扩域,p),Q∈E(p),P和Q是和的纵坐标的Hensel提升,Q-mP=R∈E1(p).

Nigel Smart攻击过程基于如下事实

特别地,有

定义

则

有

pQ-pmP=pR∈E2(p).

(5)

定义两个映射

(6)

ψp:E1(p)→pp,P

(7)

用ψ映射对式(5)两边的每一项取p-adic椭圆曲线对数,得

ψp(pQ)-mψp(pP)=ψp(pR)≡0(modp2),

(8)

(9)

由式(6)的定义,得

(10)

其中:x(P)和y(P)分别表示点P的横坐标和纵坐标.

由式(7),(10),得

(11)

利用式(9),(11)可以快速求解迹1椭圆曲线的离散对数.

1.3 点的Hensel坐标提升

令f(x,y)=y2-x3-ax-b,则f(x,y)≡0(modp).由于椭圆曲线p上的元素的坐标值都落在[0,p2)之内,因此用O(p3)做点的坐标的边界,选择点和p上横坐标x的值相同.由Hensel提升理论可知,点的纵坐标y的p-adic扩张为y=c0+c1p+c2p2+….由于

故

故

2 算法分析与设计

提升椭圆曲线点的目的是利用椭圆曲线的扭曲点求解离散对数问题.由点坐标边界O(p3)可知,可以将一个坐标表示成一个3元组(h1,h2,h3).p-adic数的幂的范围为[-3,2].

根据p-adic数的除法运算法则,分母最左边的第一个数不能为零,因为零没有乘法逆元,因此,当分母最左边的第一个数为零时,需要移位解决,这样一来,坐标计算中的一些相关变量也要随之移位处理.为了能够处理相关变量,式(3),(4)中的斜率公式只能用分数表示.

在pP或pQ的运算中,由于p是奇数,因此最终一步只能是做加法运算才能使点投射到无穷远点.在这种情形下,只有考虑加法斜率中分母最左边的第一个数为零的情形.当加法斜率中分母最左边的第一个数不为零时,坐标中与斜率无关的变量不受影响,因此其他变量不做移位处理;当加法斜率中分母最左边的第一个数为零时, 坐标中与斜率无关的变量都受影响,因此,其他变量要根据零的个数做从左向右移位的处理,零的个数为移位的次数,处理的方式是每个与分母无关的变量乘以分母;最后做加法运算(减法转换成负数做加法运算).点运算根据两个是否相同,给出式(12),(13)两种表达式.

倍点坐标计算公式

(12)

点加坐标计算公式

(13)

其中:μd(1)表示分母的第一个值,μn=y2-y1,μd=x2-x1.

根据最后一次计算到无穷远点的加法运算可知,x的坐标表达式形式为c-2p-2+c-1p+c0+O(p),y的坐标表达式形式为c-3p-3+c-2p-2+c-1p+O(p0).

两个p-adic数的3元组,相乘需要2次加法,相除需要6次加法,如果将p-adic数的加法记为一次基本运算,则上述算法做一次点运算共需24次加法运算.根据“平方乘”算法,进行pP或pQ点运算的次数为log2p,从而整个算法进行p-adic数运算的时间复杂度为O(24log2p+6),两个点需要的存储空间为12p.如果p按照160位长度计算,计算两个点需要240个字节的存储空间.

3 实例验证与分析

O,(0,2),(0,17),(1,5),(1,14),(5,1),(5,18),(6,6),(6,13),(8,7),(8,12),(9,1),(9,18),(10,8),(10,11),(11,4),(11,15),(14,8),(14,11).

P=(5+O(193),1+13·19+10·192+O(193)),

Q=(8+O(193),7+14·19+3·192+O(193)).

19P的计算过程如下

2P=(9+18·19+3·192+O(193),18+16·19+18·192+O(193)),

4P=(8+1·19+10·192+O(193),12+16·19+11·192+O(193)),

8P=(14+5·19+12·192+O(193),11+2·19+3·192+O(193)),

9P=(1+12·19+O(193),14+6·192+O(193)),

18P=(5+7·19+10·192+O(193),18+5·19+16·192+O(193)),

19P=(9·19-2+12·19-1+O(190),8·19-3+5·19-2+O(19-1)),

同理计算出19Q点的坐标

上述过程结果与文献[3]有较大差异,主要是第2个及以后的数均不相同,但最终结果是相同的.文献[3]没有给出计算过程及结果,因此很难与其做对比.

P=(293+O(1 0193),914+308·1 019+857·1 0192+O(1 0193)),

Q=(794+O(1 0193),329+561·1 019+465·1 0192+O(1 0193)).

1 019P的计算过程如下

3P=(885+847·1 019+794·1 0192+O(1 0193),113+714·1 019+435·1 0192+O(1 0193)),

6P=(483+668·1 019+953·1 0192+O(1 0193),97+700·1 019+694·1 0192+O(1 0193)),

7P=(763+808·1 019+701·1 0192+O(1 0193),442+454·1 019+917·1 0192+O(1 0193)),

14P=(248+611·1 019+319·1 0192+O(1 0193),862+959·1 019+619·1 0192+O(1 0193)),

15P=(353+538·1 019+99·1 0192+O(1 0193),741+48·1 019+76·1 0192+O(1 0193)),

30P=(582+332·1 019+79·1 0192+O(1 0193),208+723·1 019+209·1 0192+O(1 0193)),

31P=(349+76·1 019+180·1 0192+O(1 0193),526+940·1 019+880·1 0192+O(1 0193)),

62P=(451+226·1 019+490·1 0192+O(1 0193),763+328·1 019+617·1 0192+O(1 0193)),

63P=(87+315·1 019+351·1 0192+O(1 0193),396+731·1 019+759·1 0192+O(1 0193)),

126P=(16+325·1 019+162·1 0192+O(1 0193),851+618·1 019+575·1 0192+O(1 0193))

127P=(564+707·1 019+349·1 0192+O(1 0193),339+147·1 019+370·1 0192+O(1 0193)),

254P=(334+597·1 019+257·1 0192+O(1 0193),207+785·1 019+585·1 0192+O(1 0193)),

508P=(747+42·1 019+399·1 0192+O(1 0193),416+490·1 019+969·1 0192+O(1 0193)),

509P=(430+834·1 019+175·1 0192+O(1 0193),162+462·1 019+440·1 0192+O(1 0193)),

1 018P=(293+645·1 019+542·1 0192+O(1 0193),105+402·1 019+651·1 0192+O(1 0193)),

1 019P=(867·1 019-2+309·1 019-1+O(1 0190),950·1 019-3+557·1 019-2+O(1 019-1)),

同理计算出1 019Q点的坐标

1 019Q=(210·1 019-2+952·1 019-1+O(1 0190),300·1 019-3+872·1 019-2+O(1 019-1)),

305·1 019+632·1 0192+O(1 0193),

上述过程结果与文献[2]有较大差异, 主要是第2个及以后的数均不相同,但最终结果是相同的.实例1的域空间大小比实例2小,但是无论两个实例的域空间大小如何,计算结果都是正确的,这说明算法是正确和有效的.

4 结束语

文中给出了Nigel Smart思想的攻击过程,其中实例部分通过C++编程实现.文章解决了如何通过实践去理解和应用研究成果,同时该方法对于椭圆曲线的安全性的研究具有一定的参考价值.