智能卡模乘器VLSI结构的计算机实现方法

摘要

VLSI用的蒙格玛丽(Montgomery)模乘算法及智能卡模乘器VLSI实现结构，适用于智能卡加/解密技术领域。其特征在于：它是一种适合于VLSI实现的高并性度算法，它把原始的Montgomery模乘算法的3次大数乘分解为2s²+s次小数乘，s是r进制数的位数；所述的智能卡模乘器的VLSI结构是一种用32位乘法器来实现1024位模乘运算且数据通道采用三级并行流水结构的高基模乘器。第一级为两个32乘法器并行执行。第二级为一个64的加法器累加两个64位的积并产生一个进位，第三级为一个求总的累加和的76位加法器。与现有结构相比，它有效地降低了芯片面积和模乘的时钟数，从而可在智能卡中实现RSA算法的数字签名与认证。

主权项

1、VLSI用的蒙格玛丽模乘方法，其特征在于：它是一种实现VLSI的高并行度方法，其实质在于把原始的三次大数乘法运算分解为2s2+s次小整数乘，所述方法依次含有以下步骤：首先设定A，B分别为s位r进制整数；A＝(as-1as-2…a1a0)，B＝(bs-1bs-2…b1b0)；模N也为s位r进制整数，N＝(ns-1ns-2…n1n0)，且R＝rs，则有N＜R，n0 n0′mod r＝-1，并使A＜N，B＜N，以下描述中用a[s-1]a[s-2].…a[1]a[0]来表示as-1as-2…a1a0；b[s-1]b[s-2].…b[1]b[0]来表示bs-1bs-2…b1b0；n[s-1]n[s-2].…n[1]n[0]来表示ns-1ns-2…n1n0；//求n0的模逆，可表示为：n′[0]：＝-n[0]-1mod r //求n0的模逆；有(A)用s2+2s次乘法，计算乘积结果的低位s个字，可用中间结果m[i]表示：A.1 for i＝0 to s-1；A.2 for j＝0 to i-1；A.2.1 S：＝S+a[j]b[i-j]+m[j]n[i-j]；表达式S：＝S+a[j]b[i-j]+m[j]n[i-j]在智能卡模乘器VLSI实现结构分以下4个步骤来描述：步骤1：a[j]b[i-j]对应的结构实现；a[j]b[i-j]表示a[j]与b[i-j]两数相乘，用第一个32位乘法器mul32来实现，乘法器mul32有两个输入a，b；分别用a[j]来替换a；用b[i-j]来替换b，也即a＝a[j]，b＝b[i-j]此时乘法器的输出结果就是a[j]b[i-j]，该结果存放在第一个64位寄存器reg64；步骤2：m[j]n[i-j]对应的结构实现；m[j]n[i-j]表示m[j]与n[i-j]两数相乘，用第二个32位乘法器mul32来实现该乘法器mul32也有两个输入m，n；分别用m[j]来替换m，用n[i-j]来替换n，也即m＝m[j]，n＝n[i-j]此时乘法器的输出结果就是m[j]n[i-j]，该结果存放在第二个64位寄存器reg64；步骤3：表达式a[j]b[i-j]+m[j]n[i-j]结构实现；把步骤1，步骤2的两个64位的寄存器的输出分别作为加法器adder64的两个输入，得到的结果就是a[j]b[i-j]+m[j]n[i-j]，并存入一个65位的寄存器reg65；步骤4：S：＝S+a[j]b[i-j]+m[j]n[i-j]结构实现；把步骤3的寄存器reg65的结果以及寄存器reg76的结果S作为加法器adder76的输入，得到的结果就为S：＝S+a[j]b[i-j]+m[j]n[i-j]，并把该结果存入到76位的加法器reg76，作为下一次循环迭代累加时用的S值；A.3 S：＝S+a[i]b[0]；把表达式S：＝S+a[j]b[i-j]+m[j]n[i-j]中的m[j]，n[i-j]的置初值0，并输入到第2个32位的乘法器mul32，再按上述A.2.1的步骤1～4，计算出所述的S+a[i]b[0]；A.4 m[i]：＝Sn′[0]mod r；一个乘法器mul32的两个输入a，b分别用S，n′[0]来替换，另一个乘法器mul32的两个输入m，n分别用0，0来替换，重复A.2.1的步骤1～4，就可得到Sn′[0]的结果，mod r操作，就是取S的低32位数字；A.5 S：＝S+m[i]n[0]；S：＝S+m[i]n[0]是A.2.1中S：＝S+a[j]b[i-j]+m[j]n[i-j]的表达式实现步骤1～4步骤的一个特例，只是对实现a[j]b[i-j]的乘法器mul32的两个输入a，b赋初值0即可；A.6 S：＝S/r //右移一个r进制位；寄存器reg76右移一个r进制位，即可实现；(B)用s2-s次乘法计算乘积结果的高位s个字，用存储变量m表示；B.1 for i＝s to 2s-1；B.2 for j＝i-s+1，to s-1；B.2.1 S：＝S+a[j]b[i-j]+m[j]n[i-j]；同A.2.1的结构实现步骤1～4完全相同；B.3 m[i-s]：＝S mod r； mod r操作，就是取S的低32位数字；B.4 S：＝S/r //右移一个r进制位；寄存器reg76右移一个r进制位，即可实现；(C)用s次加法把蒙格玛丽模乘积由[0，2N)调整到[0，N)；C.1 r进制位t0：＝S mod r //t0是一个r进制位； mod r操作，就是取S的低32位数字；C.2 进位Cy＝1；C.3 for j＝0 to s-1；C.3.1 (Cy，b[j])：＝m[j]+not(n[j])+Cy；一个乘法器mul32的两个输入a，b分别用m[j]，1来替换，另一个乘法器mul32的两个输入m，n分别用not(n[j])，1来替换，重复A.2.1的步骤1～4，就可得到(Cy，b[j])的结果；//Cy为进位位，随进位而变；t0：＝t0+not[0]+Cy；一个乘法器mul32的两个输入a，b分别用t0，1来替换，另一个乘法器mul32的两个输入m，n分别用not[0]，1来替换，重复A.2.1的步骤1～4，就可得到t0的结果；C.4 若t0＝0；则 返回(b[s-1]b[s-2]…b[1]b[0])；否则 返回(m[s-1]m[s-2]…m[1]m[0])；上述的VLSI用的蒙格玛丽模乘方法在VLSI实现时，要被模幂Memod N所调用，为叙述方便，把“VLSI用的蒙格玛丽模乘方法”简称为MonPro，模幂Memod N实现步骤如下：在模幂Memod N实现步骤中，调用MonPro关系如下；其中R＝rs＝2ks；function MonExp(M，e，N，R) /*N是奇数*/步骤1：M：＝M·R mod N；步骤2：x：＝1·R mod N；步骤3：for i＝u-1 downto 0；步骤4：x：＝MonPro(x，x)；步骤5：if(ei＝1)then x：＝MonPro(M，x)；步骤6：x：＝MonPro(x，1)；步骤7：return x；在上述由步骤3，步骤4，步骤5和步骤6组成的循环体中，共2次调用了MonPro；第一次调用执行MonPro(x，x)；第二次调用要由ei的值来确定执行何种运算；在ei＝1时，执行MonPro(M，x)运算，在ei≠1时，执行MonPro(x，1)，这个特点使每次循环执行2次MonPro调用。