一种计算椭圆曲线群的阶的确定型多项式时间算法,确定型是因为算法内部没有随机选择/概率抛币操作,多项式时间是因为域
k的乘法与求逆总次数是O((logq)^6)
(
q为
k的大小,乘法与求逆相对加减运算显著耗时)。具体原理及流程详见参考文献[1]中5.2节。这里给出笔者的一些思考
1. Hasse定理(Frobenius自同态方程式)在扭点群上的限制亦成立,这决定了t模l的一个同余方程成立,且在模l的最小非负剩余系下解是唯一的
2. 孙子定理保证了某取值范围内的一个t模L(L为各素因子l的乘积)的唯一解,即由t模L各个素因子l的同余方程构成的同余方程组的解是唯一的
3. L必须大于t取值上限的2倍。这是为了算法求得的解满足上述2(否则在更小的L内得到的解不唯一,因L与t上限或下限间的某数可以与t模L同余)
4. 素因子l的选择排除2与椭圆曲线特征p。这是因为算法构造所依赖的一个引理之前提条件:为奇素数保证l次除子多项式属于k[X],即引理论断有意义;
不等于p保证检测一个多项式f是否零多项式的充要条件成立,即可以用l次除子多项式去整除f来判断。另l为素数保证了与其它除子多项式(及其幂次)互素
另外发现了算法的一处瑕疵,即第4步预计算除子多项式与Frobenius自同态的复合少了两个值,这导致第5步可能崩溃,当依赖的后续两个复合多项式没被计算时。
这个纠正可通过修改第4步扩大2个值,或第5步通过除子多项式的递推公式按需计算
扭点的阶计算正确性根本
在密码学中的应用
选取原则
1. 排除超奇异椭圆曲线。这是为避免MOV等约化攻击,约化攻击时间复杂度是亚指数
2. 有限域的选择要使E(Fq)的群阶足够大。这是为了缓解Shanks及Pollard ρ攻击
3. E(Fq)存在阶为大素数的子群。这是为了抵抗Pohlig-Hellman攻击
对于第1点,就排除了char(K)=2或3且j(E)=0对应的如下标准形式曲线
Y2+α3Y=X3+α4X+α6(α3≠0) 与 Y2=X3+α4X+α6
一种典型方案
椭圆曲线及有限域的选择使得|E(Fq)|=cm,且char(Fq) ∤ q+1-cm。其中m是一个大素数(通常不低于256位二进制长度,提供中长期安全性),c小于m。
m阶子群的生成元可通过以下方法确定:随机选择E上的一个有理点P,如果Q=cP为零元(即无穷远点),则重复选择,直到其不等于零元。
一旦找到了生成元,那么子群就可以构造出来了。下面分析正确性
参考文献
[1] 椭圆曲线及其在密码学中的应用—导引 Andreas Enge
[2] 算法数论 裴定一、祝跃飞
[3] The Arithmetic of Elliptic Curves Joseph H. Silverman
[4] 标识密码学 程朝辉
[5] 代数学基础与有限域 林东岱
[6] 抽象代数I 赵春来 徐明曜
[7] 代数与数论 李超 周悦