[发明专利]用于蒙哥马利模乘中的不均等分块的数据处理方法及装置

摘要

本公开提供用于蒙哥马利模乘中的不均等分块的数据处理方法及装置。方法包括：对aM和bM、以及N和k添加位，并将其分组为不均等的分块；将分块的乘积结果表示为网格；在网格上划分多个竖列，从第一竖列起，从低位到高位按竖列顺序地计算大块ai×bj和Ni×kj并进行对齐累加，需要累加到x+1竖列上的部分数值在计算x+2竖列时才计算出来。当计算到第x+1竖列及以后的竖列时，提前计算这部分数值，并在计算下一竖列时抛弃这些数值；在所有竖列计算完成后，得到低2n+2m+1位的数据，作为(aM×bM+k×N)的结果；进行移位处理得到pM＝(aM×bM+k×N)×R‑1；将pM作为输入数据aM或bM，循环执行上述过程，直到计算完一系列蒙哥马利模乘运算；输出最后一个pM值。

主权项

1.一种用于蒙哥马利模乘中的不均等分块的数据处理方法，包括以下步骤：接收输入数据，包括aM＝a×R mod N、bM＝b×R mod N、以及模数N，其中a和b为蒙哥马利模乘的输入，并且aM和bM为转换到蒙哥马利域中的输入；如果aM和bM的位宽为n，则添加m个位以将其作为位宽为n+m的输入数据，使得aM＝[a_n+m‑1,a_n+m‑2,…,a₀]和bM＝[b_n+m‑1,b_n+m‑2,…,b₀]被分组为x个不均等的分块，即aM＝[a_x‑1,a_x‑2,…,a₀]和bM＝[b_x‑1,b_x‑2,…,b₀]中的每个a_i和每个b_j的位宽不全相同，其中，R＝2^n+2m且2^n+2m＞N，n为N的位宽，m为大于或等于1的正整数，x是小于n+m且大于或等于2的正整数，i和j均取[x‑1,x‑2,…,0]，其中，每个a_i和b_j中有多个位，表示为a_i[g_i]和b_j[h_j]，g_i取0至(a_i的位宽‑1)之间的整数，并且h_j取0至(b_i的位宽‑1)之间的整数；设pM＝(aM×bM+k×N)×R^‑1，按照aM和bM的分块方式相应地将N和k分组为x个不均等的分块，即N＝[N_x‑1,N_x‑2,…,N₀]和k＝[k_x‑1,k_x‑2,…,k₀]中的每个N_i和每个k_i的位宽不全相同，其中，k是使得(aM×bM+k×N)的低n+2m位都为0的最小整数，并且k为mc×aM×bM的结果的低n+2m位，以及mc是使得mc×N的低n+2m位全为1的整数，其中，每个N_i和k_j中有多个位，表示为N_i[y_i]和k_j[z_j],y_i取0至(N_i的位宽‑1)之间的整数，并且z_j取0至(k_i的位宽‑1)之间的整数；将aM＝[a_n+m‑1,a_n+m‑2,…,a₀]与bM＝[b_n+m‑1,b_n+m‑2,…,b₀]乘积的结果表示为第一网格的形式，并且所述第一网格的每一大块表示a_i×b_j，每一大块中有多个小格，每一小格表示a_i中的每一位与b_j中的每一位的乘积结果，即a_i[g_i]×b_j[h_j]，将N＝[N_x‑1,N_x‑2,…,N₀]和k＝[k_x‑1,k_x‑2,…,k₀]乘积的结果表示为第二网格的形式，并且所述第二网格的每一大块表示N_i×k_j，每一大块中有多个小格，每一小格表示N_i中的每一位与k_j中的每一位的乘积结果，即N_i[y_i]×k_j[z_j]，所述第一网格和所述第二网格中在竖直方向上的每一小竖列上的每一小格具有相同的位权，将所述第一网格与所述第二网格从低位到高位对齐，以便将a_i×b_j的乘积结果与N_i×k_j的乘积结果进行对齐累加得到a_i×b_j与N_i×k_j之和；将所述第一网格和所述第二网格从低位到高位进行划分，使最低点处为第一竖列，第二竖列与第一竖列之间的位宽，第三竖列与第二竖列之间的位宽，直到第x‑1竖列与第x‑2竖列之间的位宽依次与输入数据aM或bM从低位到高位的位宽相对应，即a₀至a_x‑2的位宽，而第x竖列与第一竖列之间的位宽为n+2m，并且第x+1竖列以及之后的竖列之间的位宽与输入数据aM或bM从低位到高位的位宽相对应，即a₀至a_x‑1的位宽，使得模乘结果的输出与输入保持相同的分块方式以便于数据管理，其中，小竖列与所有竖列相平行；从第一竖列起，从低位到高位按竖列顺序地计算块a_i×b_j和N_i×k_j并进行对齐累加，当计算到第x竖列时，将对齐累加的结果的低n+2m位作为数据的低n+2m位，并且所述低n+2m位均为0；当计算到第x+1竖列时，由于需要累加到x+1竖列上的部分数值在计算x+2竖列时才计算出，所以通过在计算第x+1竖列的一个大块时，记录与第x+1竖列上的、不包含在第x+1竖列的所有大块中的小格的列数相对应的a_i[g]和N_i[g]，并且在计算第x+1竖列的另一大块时，记录与第x+1竖列上的、不包含在第x+1竖列的所有大块中的小格的行数相对应的b_j[h]和k_j[h]，来提前计算所述部分数值，即a_i[g]×b_j[h]以及N_i[g]×k_j[h]，其中，g是g_i或y_i中的与第x+1竖列上的、不包含在第x+1竖列的所有大块中的小格的列数相关的值，以及h是h_i或z_i中的与第x+1竖列上的、不包含在第x+1竖列的所有大块中的小格的行数相关的值；将所述a_i[g]×b_j[h]以及N_i[g]×k_j[h]的结果与第x+1竖列的大块进行对齐累加，以得到低第n+2m+1至第(n+2m+a₀的位宽)的数据；计算第x+1竖列以后的竖列，采用与计算第x+1竖列相同的方法，即提前计算需要累加到所计算的竖列上的、但要在该竖列之后的竖列才计算出的部分数值，在所有竖列计算完成后，得到低第n+2m+1至第2n+2m+1的数据，作为(aM×bM+k×N)的结果，并进行移位处理得到pM＝(aM×bM+k×N)×R^‑1；确定pM是否是一系列蒙哥马利模乘运算后的最后得到的一个pM；如果不是，则将pM作为输入数据aM或bM，循环执行上述步骤，直到计算完一系列蒙哥马利模乘运算，得到最后一个pM；当得到的pM是一系列蒙哥马利模乘运算的最后一个pM时，输出最后一个pM值作为蒙哥马利域中的蒙哥马利模乘的结果。