主权项 |
一种应用于数字签名验证的提高椭圆曲线标量乘法计算效率的方法,其特征在于,所述方法包括如下步骤:步骤A、将椭圆曲线坐标从仿射坐标系转化到射影坐标系;步骤B、将常规二进制整数k、l表示为非联合形式二进制整数NAF(k)、NAF(l),包括如下具体步骤:步骤B1、常规二进制整数k、l均具有n比特位;其中,i、n均为非负整数,且0≤i≤n;步骤B2、对常规二进制整数k、l进行奇偶性判断:当常规二进制整数k、l为奇数时,k<sub>i</sub>=2‑(kmod4)、l<sub>i</sub>=2‑(lmod4)、k=k‑k<sub>i</sub>、l=l‑l<sub>i</sub>;当常规二进制整数k、l为偶数时,k<sub>i</sub>=0、l<sub>i</sub>=0;存储k<sub>i</sub>、l<sub>i</sub>;其中,k<sub>i</sub>、l<sub>i</sub>分别为常规二进制整数k、l的第i比特位;步骤B3、根据步骤B2中常规二进制整数k、l奇偶性判断结果,取k=k/2、l=l/2、i=i+1;步骤B4、判断k≥1是否成立:当k≥1时,返回步骤B2;当k<1时,常规二进制整数k、l为非联合形式二进制整数NAF(k)=(k<sub>n‑1</sub>,k<sub>n‑2</sub>,…,k<sub>1</sub>,k<sub>0</sub>)、NAF(l)=(l<sub>n‑1</sub>,l<sub>n‑2</sub>,…,l<sub>1</sub>,l<sub>0</sub>),输出NAF(k)、NAF(l);步骤C、采用滑动窗口法计算射影坐标下椭圆曲线标量乘法kP,包括如下具体步骤:步骤C1、计算并存储P<sub>j</sub>=jP,设置R=∞、d=n‑1;其中,d为非负整数,且0≤d≤n;P为椭圆曲线上的一个点,<img file="FDA0000506530790000011.GIF" wi="671" he="158" />滑动窗口w的大小为使得窗口内的部分非联合形式二进制整数是比特位最大的奇数;步骤C2、判断k<sub>d</sub>=0是否成立:当k<sub>d</sub>=0时,设置t=1、u=0;当k<sub>d</sub>≠0时,寻找满足t≤w的最大t,且u=(k<sub>d</sub>,k<sub>d‑1</sub>,…,k<sub>d‑t+1</sub>)为奇数;其中,k<sub>d</sub>为常规二进制整数k的第d比特位;t为整数,(k<sub>d</sub>,k<sub>d‑1</sub>,…,k<sub>d‑t+1</sub>)为部分NAF(k);步骤C3、根据步骤C2中的判断结果,依次设置R=2<sup>t</sup>R、R=R+P<sub>u</sub>、d=d‑t;其中,P<sub>u</sub>=uP;步骤C4、判断是否d≥0:当d≥0时,返回步骤C2;当d<0时,R即为kP,输出R;步骤D、采用滑动窗口法,在射影坐标下同步计算应用于数字签名验证的标量乘法之和kP+lQ;其中,Q为椭圆曲线上的另一个点。 |