IT博客汇
  • 首页
  • 精华
  • 技术
  • 设计
  • 资讯
  • 扯淡
  • 权利声明
  • 登录 注册

    关于椭圆曲线的验证计算

    春秋十二月发表于 2024-11-10 13:45:00
    love 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)
    (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] 代数学基础与有限域                             林东岱


    春秋十二月 2024-11-10 21:45 发表评论


沪ICP备19023445号-2号
友情链接