基于蒙哥马利模乘的Tate对算法及其硬件结构

摘要

本发明属于嵌入式系统的密码算法实现技术领域，尤其涉及一种基于三进制有限域蒙哥马利模乘的Tate对算法和实现该算法的硬件结构,包括：将两个输入的椭圆曲线上的点P和R的X坐标和Y坐标分别由所定义的GF(3^m)域上转换到蒙哥马利域；按照由GF(3^m)上的乘法、加/减法和立方运算作为基本运算的MDL算法流程在蒙哥马利域上分别进行运算；再把计算结果从蒙哥马利域上转换回GF(3^6m)域上，再计算结果的3^3m-1次模幂。硬件结构包括：顶层处理器、控制器、三进制累加器、三进制乘法器、寄存器堆、SRAM；控制器控制三进制累加器和三进制乘法器的输入以及SRAM和寄存器堆的读写操作，从而控制整个电路的数据传输。

主权项

一种基于Montgomery模乘的Tate对算法，其特征在于，包括：步骤1、将作为输入的定义在GF(3^m)上的椭圆曲线E_±:Y²=X³‑X±1上的点P和R的X坐标和Y坐标分别由所定义的GF(3^m)域上转换到Montgomery域，具体地，把被转换的数据与x^2m进行Montgomery模乘；GF(3^m)是阶为3^m的伽罗华有限域的表示形式，有限域的特征值为3，m为GF(3^m)的度，x^2m表示GF(3)域上的2m次项系数为1其它项系数为0的2m次多项式；步骤2、按照由GF(3^m)上的乘法、GF(3^m)上的加/减法和GF(3^m)上的立方运算作为基本运算的MDL算法流程在Montgomery域上完成MDL算法，其中的乘法、加/减法和立方运算全部在Montgomery域上进行；步骤3、在MDL算法结束后，根据需要，再把计算结果从Montgomery域上转换回GF(3^6m)域上，具体地，把被转换的数据与GF(3)中的元素1进行Montgomery模乘；GF(3^6m)是阶为3^6m的伽罗华有限域的表示形式，有限域的特征值为3，6m为GF(3^m)的度；步骤4、按照由GF(3^m)上的乘法、加/减法和求逆运算构成的算法计算GF(3^6m)上的模幂：其中t是步骤3所述转换回GF(3^6m)域上的MDL算法的结果，τ是Tate对的计算结果。