随笔-156  评论-223  文章-30  trackbacks-0
符号含义 
    E            表示满足椭圆曲线Weierstrass方程上的点群
    K            代数闭域,用来限制Weierstrass方程的系数与E中的点
    E(K)        定义在K上的点群E
    E/K         定义在K上的椭圆曲线E
    End(E)    E上的自同态环


域扩张分析 
  

End(E)模与Z代数 
  

极点首项系数 
  
  

除子映射及同构
  
  

同种映射同态性的解释 
  
  
  

Hasse定理之引理证明的补充  
  

挠曲线及其个数   
  

有限域上的椭圆曲线  
  一种确定型群阶计算法 
    
 
  奇素域上的算法应用 
    
   

 GF域上的群阶计算  
   
   

Schoof算法正确性根本   
    一种计算椭圆曲线群的阶的确定型多项式时间算法,确定型是因为算法内部没有随机选择/概率抛币操作,多项式时间是因为域k的乘法与求逆总次数是O((logq)^6)
qk的大小,乘法与求逆相对加减运算显著耗时)。具体原理及流程详见参考文献[1]中5.2节。这里给出笔者的一些思考
​     1. Hasse定理(Frobenius自同态方程式)在扭点群上的限制亦成立,这决定了tl的一个同余方程成立,且在模l的最小非负剩余系下解是唯一的
​     2. 孙子定理保证了某取值范围内的一个tLL为各素因子l的乘积)的唯一解,即由tL各个素因子l的同余方程构成的同余方程组的解是唯一的
​     3. L必须大于t取值上限的2倍。这是为了算法求得的解满足上述2(否则在更小的L内得到的解不唯一,因Lt上限或下限间的某数可以与tL同余)
​     4. 素因子l的选择排除2与椭圆曲线特征p。这是因为算法构造所依赖的一个引理之前提条件:为奇素数保证l次除子多项式属于k[X],即引理论断有意义;
       不等于p保证检测一个多项式f是否零多项式的充要条件成立,即可以用l次除子多项式去整除f来判断。另l为素数保证了与其它除子多项式(及其幂次)互素
     另外发现了算法的一处瑕疵,即第4步预计算除子多项式与Frobenius自同态的复合少了两个值,这导致第5步可能崩溃,当依赖的后续两个复合多项式没被计算时。
  这个纠正可通过修改第4步扩大2个值,或第5步通过除子多项式的递推公式按需计算

扭点的阶计算正确性根本  
    

在密码学中的应用  
    选取原则  
        1. 排除超奇异椭圆曲线。这是为避免MOV等约化攻击,约化攻击时间复杂度是亚指数
        2. 有限域的选择要使E(Fq)的群阶足够大。这是为了缓解ShanksPollard ρ攻击
        3. E(Fq)存在阶为大素数的子群。这是为了抵抗Pohlig-Hellman攻击
      对于第1点,就排除了char(K)=2或3且j(E)=0对应的如下标准形式曲线
           Y23Y=X34X+α6(α3≠0) 与  Y2=X34X+α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] 代数与数论                                        李超   周悦
posted on 2024-11-10 21:45 春秋十二月 阅读(160) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理