| 主权项 |
1.一种用以作为两个二进位数A及B相乘之方法,各者具达n位元,其乘法系属模数N,其中A和B可被分割成m个各具k位元的区块,令以mk≧n+2,而该方法至少包含下列步骤:预先决定并储存数値s=-1/N0 mod R,其中N0为N中最少显着k位元,而R=2k;将一用以存放Zi値的结果储存装置値初始化为零値;及依i从0行至m-1的序列値,执算出下列步骤:(a)按Zi+AiB来计算Xi并储存之,其中Ai为A的第i个k位元区块,而A0为A的低序位元;(b)按sxi,0 mod R计算yi并储存之,其中xi,0为Xi中的最少显着k位元;及(c)按(Xi+yiN)/R来计算Zi+1并储存之,其中Zm为乘积AB2-mk mod N。2.如申请专利范围第1项所述之方法,其中该步骤(b)及(c)的乘法运算系利用交替周期里、相同的乘法器电路来执算。3.一种用以计算AB mod N的方法,其中至少包含下列步骤:利用如申请专利范围第1项所述之方法来产生AB2-mkmod N;及从先前步骤里,再利用如申请专利范围第1项所述之方法,将AB2-mk mod N乘上22mk mod N,在此原先引入的因数2-mk,并同目前的乘法运算步骤所引入之额外因数2-mk,可抵销之而产生AB mod N的结果。4.一种用以两个各具达n位元之二进位数A及B相乘的电路,其中该乘积为模数N,此为一具有n位元的奇数,且其中A及B可被分割成m个各具k位元的区块,令以mk≧n+2,而该电路至少包含:一累加暂存器,具n+1位元,以握存中间性数値Zi,此i表示一序列复数个电路运算周期其中一者,而各周期含有依第一相阶及依第二相阶;一临时性暂存器,具k位元,以于该第一相阶过程中握存其中间性结果;一常数储存暂存器,含有s=-1/N0 mod R的二进位表示方式,其中N0为N中最少显着k位元,而其中R=2k;一第一二进位乘法器,以将一n+1位元数値乘上一k位元数値;一供应装置,可供应一系列A的k位元宽度之区块Ai,作为对该第一乘法器于电路的第一运算相阶过程内之输入,该序列系以A的低序位元开始而达B的n位元,以产生AiB数値,且在与该第一相阶相互交替的第二运算相阶的过程中,在该电路的第二运算相阶过程内会将数値N及临时性储存暂存器的内容yi供应给该乘法器,此暂存器中握留有乘积sxi,0 mod R,其中xi,0为该累加暂存器内的低序k位元;一第一加法器,在该第一运算相阶过程内,接收该AiB的高序n+1位元数値,并且将该値加到存放在该累加暂存器内的目前数値,其各个位元向右位移k个位元,而该第一加法器在该第一运算相阶过程内的输出会被馈返到该累加暂存器,并于第二运算相阶过程内,用以将存放在该累加暂存器内的目前数値,加到该第一乘法器的输出yiN,该第一乘法器的输出会被馈返到该累加暂存器;一第二加法器,在该第一运算相阶过程内,将来自于该累加暂存器的低序k位元,加到该第一乘法器在该第一运算相阶过程中所产生的低序k位元,而此第二加法器的输出会被储存在该临时性储存暂存器内;及一第二乘法器,用以将来自于该第二加法器的输出,乘上该常数储存暂存器的内容,而来自于此第二乘法器输出的低序k位元会被供应给该临时性暂存器。5.如申请专利范围第4项所述之电路,其中该累加暂存器会具有至少mk个位元。6.如申请专利范围第4项所述之电路,其中A及B可具达n+1个位元。图式简单说明:第1图为说明本揭乘积模数N方法及系统所采用的电路之区块图;第2图为除特别绘示出该等资料串流路径以外,等同于该第1图之区块图,在此这些路径于计算作业之第一或X-相阶过程里系属作用中;第3图为除更特别绘示出该等资料串流路径以外,类似于该第1及2图之区块图,在此这些路径于计算作业之第二或Z-相阶过程里系属作用中;第4图为如第1图电路之经分割具体实施例里,在一处理单元序列中其最右端处理单元之区块图;第4A图为类似于第4图之区块图,但此者绘示出一替代性乘法器-转-加法器连线;第5图为说明衆多等同处理单元其中一者之区块图,彼等可加以组态成为一处理单元序列,而能够执行与第1图所示电路相同的运算;第5A图系一类似于第5图之区块图,但此亦绘示一替代性乘法器-转-加法器连线;第6图为说明可加速地被用来作为一用以执算与如第1图电路之相同计算作业的处理单元序列中,最后或最左端处理器单元之处理单元形式的区块图;第7图说明如何连接如第4.5及6图所述之处理器单元,俾以产生与第1图电路相同结果之区块图;第8图为说明处理器单元跨于时间上之逻辑连线区块图,而特别参考量暂存器储存以及X和Z相阶运算;第9图为说明按管线方式应用处理器单元之区块图;第10图为说明经组态设定于管线模式应用之典型处理器单元区块图;第11图为类似于第10图之区块图,但此更特别地说明一待应用于最右端或最低序位置之处理器单元;第12图为类似于第8图之区块图,但此更特别地说明利用管线方式,藉由从关键路径中消除掉加法器俾以加速处理时间;第13A及13B图系说明一经改良最右端处理器之区块图,其中既已移除关键路径上一加法器以改善效能;第14图为类似于第13A及13B图之区块图,但更特别说明应用于一改良式管线运算之典型处理器单元;第15图系一区块图,以说明对于经改良管线组态里最左端处理器单元之较佳设计;第16图说明一管线运算作业中的处理器单元利用性;第17图系一区块图,以说明一用于计算某数値之负模数倒数的电路;第18图系一流程图,说明一种用以利用可实作模数乘法之电路的方法,而可藉此实作方式以进一步实作指数计算函数;第19图系一类似于第18图之流程图,但展现一种替代性演算法以实作一模数指数函数;第20图系一电路区块图,可用以实作如第18或19图所示之各演算法其中一者;第21图系一公钥加密及解密处理方法之区块图,而特别在于本项采用指数运算,且尤其是说明在此出现用以改良效率的信号变数;第22图系一整体区块观视图,说明一种根据本发明所建构之加密引擎具体实施例;第23图系一区块图,说明一种纳入相符于模数N乘积系统之检查总和机制;第24图系一区块图,说明利用模数(R-1)加法以产生中间性检查总和数値之常用电路;第25图系一区块图,说明可用以执行运用在最终检查总和比较运算里检查总和运算的电路,且该者可提供错误指示;以及第26图系一区块图,说明可利用模数(R-1)加法器组对来产生待加比较之检查总和变数的电路。 |
