本发明是与用来计算相与具有一2n比特长度的一模数(N)有关的一第一操作数(A)以及一第二操作数(B)的一模数乘法的一结果有关的装置及方法，这些操作数以及该模数乃被开成为长度为该长度的一半的次操作数，并且被馈送至控制装置(14)，以控制用于依照一预先决定步骤顺序并藉相对应的输入操作数(12a，12b)与MultModDiv模数(12c)而执行一MultModDiv运算的MMD装置，进以在一输出端(12d)获得与该MMD模数有关的整数商数值(Q(i))以及剩余数值(R(i))。再者，结合装置(16)乃可以用来结合来自该步骤顺序的预先决定步骤的整数商数值以及剩余数值进以获得该结果。藉由将具有，举例而言，一2n比特长度，的操作数的一模数乘法分成数个具有一n比特长度，亦即，该长度的一半，的操作数的MMD运算，便可以藉由针对于较短的操作数所想出的一计算单元上的长操作数来有效率地执行密码算法，因此，提高长密码的安全性需求乃可以有效率地适用于既有的电路。
1.一种计算与一模数N有关的一第一操作数A以及一第二操作数B的一模数乘法的一结果的装置，该第一操作数、该第二操作数、以及该模数乃具有第一比特长度，该装置包括：一种用以提供来自该第一操作数A的一第一次操作数At以及一第二次操作数Ab、来自该第二操作数B的一第一次操作数Bt以及一第二次操作数Bb、以及自该模数N的一第一次模数Nt以及一第二次模数Nb的装置(10)，这些次操作数和次模数乃分别具有比该第一比特长度为短的一第二比特长度，其中用以提供的该装置被配置来将该第一操作数A分解为x该第一次操作数At与该第二次操作数Ab而使得A＝At2+Ab、将该第二操作数B分解为该第x一次操作数Bt以及该第二次操作数Bb而使得B＝Bt2+Bb、以及将该模数N分解为该第一次x模数Nt以及该第二次模数Nb而使得N＝Nt2+Nb；
MultModDiv装置(12)，用以执行一MultModDiv运算，而一MultModDiv运算乃被定义为自一项次中提出与一MultModDiv模数有关的一整数商数值Q以及一剩余数值R；
控制装置(14)，用以依照一预先决定步骤顺序而向该MultModDiv装置馈送输入操作数以及与MultModDiv模数有关的预先决定结合，而这些输入操作数以及MultModDiv模数乃是基于该第一操作数A的该第一次操作数At以及该第二次操作数Ab、基于该第二操作数B的该第一次操作数Bt以及该第二次操作数Bb、基于该模数N的该第一次模数Nt以及该第x二次模数Nb、基于整数商数值以及剩余数值，以及基于一因子2，其中，x等于该第二比特长度；以及结合装置(16)，用以结合来自该步骤顺序中的预先决定步骤的整数商数值以及剩余数值，进而获得有低阶比特(120a)与高阶比特(120b)的该结果，其中该低阶比特(120a)是代表剩余数值的第一总和的结果，且该高阶比特(120b)代表整数商数值以及剩余数值的第二总和，而该第一总和的剩余数值从预先决定步骤顺序的预先决定步骤计算，且该第二总和的剩余数值以及整数商数值从预先决定步骤顺序的预先决定步骤计算。
其中，该第一操作数A、该第二操作数B、以及该模数N乃具有一2n比特长度；
其中，该MultModDiv装置为具有比2n比特短的一长度的一运算单元；以及其中，该结合装置(16)为具有比2n比特短的一长度的一运算单元。
其中，该MultModDiv装置具有一n+ε比特长度，而ε乃比10短小；以及其中，该结合装置(16)乃为具有一n比特长度的一运算单元。
其中，该控制装置是依照下列的预先决定步骤顺序而被配置以馈送至该MultModDiv装置：n
第一馈送(51)作为输入操作数的Bt与2 以及作为一MultModDiv模数的Nt，以获得一(1) (1)第一整数商数值Q 以及一第一剩余数值R ，其中Bt为来自该第二操作数值的该第一次操作数，2n为该第一长度，而Nt为该第一次模数；
第二馈送(52)作为输入操作数的该第一整数商数值与Nb以及作为一MultModDiv模n (2) (2)数的2，以获得一第二整数商数值Q 以及一第二剩余数值R ，其中Nb为该第二次模数；
第三馈送(53)作为输入操作数的At与该第一剩余数值-第二整数商数值+Bb的总和(3) (3)以及作为一MultModDiv模数的Nt，以获得一第三整数商数值Q 以及一第三剩余数值R ，其中At为该第一操作数之该第一次操作数，而Bb为来自该第二操作数之该第二次操作数；
第四馈送(54)作为输入操作数的Ab与Bt以及作为一MultModDiv模数的Nt，以获得一(4) (4)第四整数商数值Q 以及一第四剩余数值R ，其中Ab为该第一操作数之该第二次操作数；
第五馈送(55)作为输入操作数的该第三整数商数值+该第四整数商数值的一总和与n (5)Nb以及作为一MultModDiv模数的2，以获得一第五整数商数值Q 以及一第五剩余数值(5)R ；
第六馈送(56)作为输入操作数的At与该第二剩余数值以及作为一MultModDiv模数n (6) (6)的2，以获得一第六整数商数值Q 以及一第六剩余数值R ；以及n
第七馈送(57)作为输入操作数的Ab与Bb以及作为一MultModDiv模数的2，以获得一(7) (7)第七整数商数值Q 以及一第七剩余数值R ；以及(3)
其中，该结合装置被配置，以形成该第三剩余数值R +该第四剩余数值-该第五整数商数值-该第六整数商数值+该第七整数商数值的该第二总和，以形成该第七剩余数值-该第六剩余数值-该第五剩余数值的该第一总和，以及结合该第一总和及该第二总和，n以使得该结果等于该第二总和乘以2 后与该第一总和的总和。
其中，该控制装置通过执行下列步骤来馈送MultModDiv单元：n
馈送作为输入操作数的Bt与2 以及作为MultModDiv模数的Nt，以获得第一整数商数(1) (1)值Q 以及第一剩余数值R ，其中Bt为来自该第二操作数之该第一次操作数，2n为该第一长度，而Nt为该第一次模数；
馈送作为输入操作数的Q 与Nb以及作为MultModDiv模数的2，以获得第二整数商数(2) (2)值Q 以及第二剩余数值R ，其中Nb为该第二次模数；
馈送作为输入操作数的R -Q +Bb的总和与At以及作为MultModDiv模数的Nt，以获(3) (3)得第三商数值Q 与第三剩余数值R ，其中At为该第一操作数的该第一次操作数，且Bb为来自该第二操作数的该第二次操作数；
馈送作为输入操作数的Ab与Bt以及作为MultModDiv模数的Nt，以获得第四整数商数(4) (4)值Q 以及第四剩余数值R ，其中Ab为该第一操作数的该第二次操作数；
馈送作为输入操作数的Nb与Q +Q 的总和以及作为MultModDiv模数的2，以获得第(5) (5)五整数商数值Q 以及第五剩余数值R ；
馈送作为输入操作数的At与R 以及作为MultModDiv模数的2，以获得第六整数商数(6) (6)值Q 以及第六剩余数值R ；以及
馈送作为输入操作数的Ab与Bb以及作为MultModDiv模数的2，以获得第七整数商数(7) (7)值Q 以及第七剩余数值R ；以及
其中，该结合装置(16)配置以形成R +R -Q -Q +Q 的该第二总和与形成(7) (6) (5)
R -R -R 的该第一总和，以及结合该第一总和及该第二总和，以使得该结果等于该第二n总和乘以2 后与该第一总和的总和，
其中，该MultModDiv装置(12)乃为了互相平行执行Bt及2 之馈送、Ab及Bt之馈送、以及Ab及Bb之馈送而被配置。
其中，该控制装置被配置，以便依照用于计算具有相同的第一以及第二操作数的该模数乘法的下列预先决定步骤顺序而馈送该MultModDiv装置(12)：n
馈送(71)作为输入操作数的At与2 以及作为一MultModDiv模数的Nt，以获得一第一(1) (1)整数商数值Q 以及一第一剩余数值R ，其中At为来自该第一操作数之该第一次操作数，
馈送(72)作为输入操作数的该第一整数商数值与Nb以及作为一MultModDiv模数的n (2) (2)
2，以获得一第二整数商数值Q 以及一第二剩余数值R ，其中Nb为该第二次模数；
馈送(73)作为输入操作数的At与该第一剩余数值-该第二整数商数值+2*Ab的一总(3)和以及作为一MultModDiv模数的该第一次模数Nt，以获得一第三整数商数值Q 以及一第(3)三剩余数值R ，其中Ab为来自该第一操作数之第二次操作数；
馈送(74)作为输入操作数的该第三整数商数值与该第二次模数作为一MultModDiv模n (4) (4)数的2，以获得一第四整数商数值Q 以及一第四剩余数值R ；
馈送(75)作为输入操作数的At与该第二剩余数值R 以及作为一MultModDiv模数的n (5) (5)
2，以获得一第五整数商数值Q 以及一第五剩余数值R ；以及馈送(76)作为一第一输入操作数及作为一第二输入操作数的Ab以及作为一n (6) (6)MultModDiv模数的2，以获得一第六整数商数值Q 以及一第六剩余数值R ；以及其中，该结合装置(16)被配置，以便计算出该第三剩余数值-该第四整数商数值-该第五整数商数值+该第六整数商数值的该第二总和以及该第六剩余数值-该第五剩余数值-该第四剩余数值的该第一总和，以及以获得来自该第一总和以及该第二总和的一结n果，以使得该结果等于该第二总和乘以2 后与该第一总和的总和。
其中，该MultModDiv装置(12)乃更包括一用于一初始MultModDiv运算(30b)的处理器，其被配置成以便根据两个加数的一总和来计算出与一模数相关的一整数商数值以及一剩余数值，一第一加数乃等于一第一输入操作数与一第二输入操作数的一乘积，而第二加n数则等于一第三输入操作数与一数2 的一乘积；以及其中，该控制装置被配置，以便于该预先决定的步骤顺序中的一步骤中控制该初始MultModDiv运算(30b)。
其中，该控制装置(14)被配置，以便依照下列的预先决定步骤顺序而馈送该MultModDiv装置(12)：馈送作为输入操作数的At与Bt以及作为一MultModDiv模数的Nt，以获得一第一整数(1) (1)商数值Q 以及一第一剩余数值R ，其中At为该第一操作数之该第一次操作数，Bt为该第二操作数之第一次操作数，而Nt为该第一次模数；
馈送(62)作为输入操作数的Nb，-该第一整数商数值，该第一剩余数值以及作为一(2)MultModDiv模数的Nt进入该初始MultModDiv运算(30b)，以获得一第二整数商数值Q 以(2)及一第二剩余数值R ，其中Nb为该第二次模数；
馈送(63)作为输入操作数的At与Bb以及作为一MultModDiv模数的Nt，以获得一第三(3) (3)整数商数值Q 以及一第三剩余数值R ，其中Ab为该第一操作数之该第二次操作数；
馈送(64)作为输入操作数的Ab与Bt以及作为一MultModDiv模数的Nt，以获得一第四(4) (4)整数商数值Q 以及一第四剩余数值R ；
馈送(65)作为输入操作数的Ab与Bb以及作为一MultModDiv模数的2，以获得一第五(5) (5)整数商数值Q 以及一第五剩余数值R ，其中2n为该第一长度，而Bb为该第二操作数之该第二次操作数；以及馈送(66)作为输入操作数的该第二整数商数值+该第三整数商数值+该第四整数商n (6)数值的一总和与Nb以及作为一MultModDiv模数的2，以获得一第六整数商数值Q 以及一(6)第六剩余数值R ；以及
其中，该结合装置被配置，以根据该第一总和及第二总和来计算该第二剩余数值+该第三剩余数值+该第四剩余数值+第五整数商数值-该第六整数商数值的该第二总和，以及该第五剩余数值-该第六剩余数值的该第一总和，进以获得该结果，以使得该结果等于n该第二总和乘以2 后与该第一总和的总和。
其中，该第一操作数乃等于该第二操作数以便计算出一模数平方运算Amod N，其中A为该第一操作数，而N为该模数；
其中，该控制装置(14)被配置，以便依照下列的预先决定步骤顺序而馈送该MultModDiv装置(12)：馈送(81)作为输入操作数的A以及作为一MultModDiv模数的Nt，以获得一第一整数(1) (1)商数值Q 以及一第一剩余数值R ，其中At为该第一操作数之该第一次操作数，而Nt为该第一次模数；
馈送(82)作为输入操作数的Nb，-该第一整数商数值，第一剩余数值以及作为一(2)MultModDiv模数的Nt进入该初始MultModDiv装置(30b)，以获得一第二整数商数值Q 以(2)及一第二剩余数值R ，其中Nb为该第二次模数；
馈送(83)作为输入操作数的2At与Ab以及作为一MultModDiv模数的Nt，以获得一第(3) (3)三整数商数值Q 以及一第三剩余数值R ，其中Ab为该第一操作数之该第二次操作数；
馈送(84)作为输入操作数的该第二整数商数值+该第三整数商数值的一总和与Nb以n (4) (4)及作为一MultModDiv模数的2，以获得一第四整数商数值Q 以及一第四剩余数值R ，其n中2 为该第一长度；以及
馈送(85)作为输入操作数的Ab以及作为一MultModDiv模数的2，以获得一第五整数(5) (5)商数值Q 以及一第五剩余数值R ；
其中，该结合装置(16)被配置，以计算出(86)该第二剩余数值+该第三剩余数值-该第四整数商数值+该第五整数商数值的该第二总和，以及该第五剩余整数值-该第四剩余数值的该第一总和，进以获得该模数平方运算的结果，以使得该结果等于该第二总和乘以n
其中，该控制装置被配置以便选择该预先决定步骤顺序，进而使得在多个步骤之后，仅有长度比2n比特短的数字会留下来。
其中，该控制装置(14)被配置以便使用经由下列步骤所获得的一预先决定步骤顺序：将一第一项次与一第二项次的一乘积(90a)展开以获得部分乘积，而该第一项次包括该第一操作数的一第一次操作数At以及一第二次操作数Ab，以及该第二项次包括该第二操作数的一第一次操作数Bt以及一第二次操作数Bb；以及以一步接着一步的方式，利用MultModDiv运算来处理这些部分乘积，以仅获得长度比nn比特短的数字与一因子2 的乘积、或是长度比2n比特短的数字。
其中，该控制装置被配置，以便对该MultModDiv装置(12)馈送该第一次模数Nt或是z仅作为MultModDiv模数的一数字2，其中，x乃等于该第二比特长度。
其中，该结合装置被配置，以确定(116)该第一总和是否会提供一进位；以及若是该第一总和确实提供一进位时，则藉由在一加法器(112)的一进位输入(122)处且等于″1″的一进位来计算出该第二总和。
14.一种用于计算与一模数N有关的一第一操作数A以及一第二操作数B的一模数乘法的一结果的方法，该第一操作数、该第二操作数、以及该模数乃具有一第一比特长度，该方法包括下列步骤：通过一提供装置(10)而自该第一操作数A中提供出一第一次操作数At以及一第二次操作数Ab，自该第二操作数B中提供出一第一次操作数Bt以及一第二次操作数Bb，以及自该模数N中提供出一第一次模数Nt以及一第二次模数Nb，这些次操作数与次模数分别具有比该第一比特长度短的一第二比特长度，其中该第一操作数A被分解为该第一次操作数Atx与该第二次操作数Ab而使得A＝At2+Ab、该第二操作数B被分解为该第一次操作数Bt以及x该第二次操作数Bb而使得B＝Bt2+Bb、以及该模数N被分解为该第一次模数Nt以及该第二x次模数Nb而使得N＝Nt2+Nb；
通过一MultModDiv装置(12)而执行一MultModDiv运算，而一MultModDiv运算乃被定义，以自一项次中提供与一MultModDiv模数有关的一整数商数值Q以及一剩余数值R；
通过一控制装置(14)依照一预先决定步骤顺序而把输入操作数以及与MultModDiv模数有关的预先决定结合馈送至该MultModDiv装置(12)，而这些输入操作数以及MultModDiv模数乃是基于该第一操作数A的该第一以及该第二次操作数、基于该第二操作数B的该第一以及该第二次操作数、基于该模数N的该第一以及该第二次模数、基于来自在x该预先决定步骤顺序中的步骤的整数商数值以及剩余数值以及基于一因子2 而得，其中，x等于该第二比特长度；以及通过一结合装置(16)而结合来自该步骤顺序的预先决定步骤的整数商数值以及剩余数值，进而获得有低阶比特(120a)与高阶比特(120b)的该结果，其中该低阶比特(120a)是代表剩余数值的第一总和的结果，且该高阶比特(120b)代表整数商数值以及剩余数值的第二总和，而该第一总和的剩余数值从预先决定步骤顺序的预先决定步骤计算，且该第二总和的剩余数值以及整数商数值从预先决定步骤顺序的预先决定步骤计算。
计算模数乘法之结果的装置及方法
技术领域
[0001] 本发明涉及计算算法，以及，特别地相关于密码应用所需的计算算法。 背景技术
[0002] 密码长度特别地会于公开密码密码学中，但亦会在其它的密码学领域之中，稳定地增加，这是因为，寄托于如此之密码算法上的安全性需求亦在增加，而该RSA方法作为一非对称密码概念的一代表的使用，也就是说，一公开码方法的使用，会于所使用的密码长度增加时，增加所谓暴力攻击的安全性，再者，由于暴力攻击为在一密码算法上的攻击，其中，一密码会推论自所有可能性的试验，因此，其立即地证明，随着该密码长度增加，理论上，为了试验所有可能性，一暴力攻击所需要的时间量亦会增加。
[0003] 应该要指出的是，在此上下文中，以前所使用的具有密码长度512比特的RSA应用充分地加以考虑，而由于″其它侧(other side)″所造成的技术以及数学上地进展，因此，用于典型RSA应用的密码长度接着被增加到1024比特，现今，有许多的人主张即使是此密码长度一不足够，因此，以RSA密码长度2048比特为目标。
[0004] 换言之，当考虑既存的密码协处理器，例如，于智能卡(SmartCards)上，时，其可以发现，当然，有需要亦允许具有，举例而言，2048比特的密码长度的RSA应用，于实际上仅为了，举例而言，1024比特的密码长度而加以发展的密码电路上运作，因此，用于既存智能卡应用的算术协处理器会以它们已经为了不适用于大多数当前的安全性需求，亦即，太短，之一特有比特长度而加以发展的特有事实为特征，而此会导致，举例而言，一2048比特RSA算法无法有效地在1024比特协处理器上受到掌控的事实，对RSA应用而言，中国剩余定理(Chinese RemainderTheorem，CRT)为已知，其中，具有一大密码长度的一模数幕乘(modularexponentiation)被破坏成为两个具有一半该密码长度的模数幕乘，据此，一半该长度的两个模数幕乘的结果相对应地结合在一起。
[0005] 近来，其已经试验出，该中国剩余定理特别地受到DFA(DFA＝differential fault analysis，差分错误分析)攻击的影响。
[0006] 因此，相关于许多方法的一个问题是，在密码计算中的一中心操作的所谓模式乘法的″加倍(doubling)″，所以，一模数幕乘可以被破坏成为许多个模数乘法，亦即，成为一第一操作数A以及一第二操作数B的一乘积在相关于一模数N的一剩余分类(residual class)中加以计算的一操作，而若是这些操作数A以及B的每一个具有一2n比特的长度时，则具有一n比特长度的计算单元会典型地加以使用，这些计算单元因为它们长的长度而被称之为长数计算单元(long-number calculatingunits)，正如相对于，举例而言，PC或工作站运算器所使用之，举例而言，8比特、16比特、32比特、或64比特架构。 [0007] 是以，有需要在一n比特计算单元上执行具有一比特长度2n的数A、B以及N的一模数乘法A*B mod N，然，此非常的耗时，因为这些数A，B，N仅可能小部分接着小部分的加以加载，而若是它们没有完全失败的话，则此即为为什幺习知的方法需要一大量的组织并且为错误倾向(error-prone)的原因。在习知技术中，至目前为止，有数种可以解决此问题的方法，而这些方法已藉由蒙哥马利乘法(Montgomerymultiplication)、正常乘法，亦即，具有Karatsuba-Ofman、及一接续缩减，例如，Barret缩减的关键词而为已知。 [0008] 而在一″CRt窗口″中的一蒙哥马利乘法的另一使用概念则已经于P.Pailler，″Low-cost double size modular exponentiation or how tostretch your cryptocoprocessor″中提出。
[0009] 所有如此的概念于计算时间以及资料组织方面相当的昂贵，并且，因此并不总是有效率。
发明内容
[0010] 本发明的一目的为提供一种用于计算可以有效地使用执行以及计算时间的一模式乘法的一结果的概念。
[0011] 此目的藉由权利要求1中所主张的装置、或是藉由权利要求10中所主张的方法而加以达成。
[0012] 本发明基于发现，相关于一模数、两个操作数、以及具有一，举例而言，2n比特长度的该模数，这些操作数的一模数乘法可以藉由一较短 长度，举例而言，该长度的一半，例如，n比特，的次操作数At，Ab，Bt及/或次模数Nt，Nb，而被转换成为MultModDiv运算的一预先决定的步骤顺序，这些MultModDiv运算(MMD运算)与一较短长度，举例而言，该长度的一半，之这些次操作数及/或次模数一起作用，而在MultModDiv运算中，除了提供一模数乘法的余数的该MultMod运算之外，该已知Div运算的结果亦被插入，再者，除了在一MMD运算中的该余数之外，该Div运算的结果，亦即，该模数的该整数商，加以计算，根据该预先决定步骤顺序，并藉由输入参数以及模数而执行如此的一MMD运算数次会引起源自该步骤顺序的预先决定步骤的整数商数值以及剩余数值，其所有皆具有较短的比特长度，举例而言，n比特，以及其亦藉由一n比特加法器，举例而言，而可以被加总，以及写入在分别地点的一结果存储位置。
[0013] 用于此的基础为，作为用于衍生一较佳预先决定步骤顺序的一条件方程式的一逼n n近(At*2+Ab)(Bt*2+Bb)，展开该式子会引起不同的乘积，而其一步一步地藉由一MMD运算而n
加以取代，接着，该模数缩减，亦即，其接着计算A*B mod N，藉由等式Nt*2 ＝-Nb而加以考虑。
[0014] 该指数″t″表示一操作数A，B及/或一模数N的上部位，反之，指数″b″(b＝nbottom)代表该分别数的底部位，因此，该操作数A，举例而言，产生为At*2+Ab，而相同的情形亦适用于模数N以及该第二操作数B，由于，正如已经提出的，这些部分乘积一步一步地n
藉由MMD运算而加以取代，因此，仅有具有一因子2 之较n比特为短的一长度的数、或是一n比特长度的数的乘积将会在复数个取代步骤之后留下来，该结合定向亦可以加以执行为n
一n比特加法器，以结合，一方面，乘上该因子2 的这些中间结果，以及，以结合，另一方面，n
未应用一因子2 的这些中间结果。
[0015] 藉由一2n比特长度的操作数及/或一模数所得出的该模数乘法的结果，当然，再n次地为一比特计数2n，其藉由将不具该因子2 的这些中间结果的总和写入该结果内存的该n
低阶比特而被结合入一结果内存，反之，已应用2 的这些中间结果的总和被写入该结果内存的该上部位，而其有可能为，可能存在的自该结果内存中的这些底部位至该结果内存中的上部位的一进位很快地受到考虑。
[0016] 本发明的一个优点是，本发明的概念允许用于具有相对而言较长长度的数，具有相对而言较短长度的计算单元的使用。
[0017] 本发明的另一优点是，本发明的概念为有效率的，本发明的概念在Advanced Crypto Engine of Infineon Technologies，Munich上的一执行与已经记载于本发明的序言中的Pailler的概念间的一比较显示出，举例而言，RSA，之执行时间的40％减少。 [0018] 本发明的一另一优点是，该Div信息，也就是该整数商，可以藉由软件、或是藉由硬件，以及藉由容易执行的方法，而获得自该MultMod运算，该MultMod运算典型地于每一个多目的密码运算器上加以执行，再者，在模数算术中，正如典型地在现代密码系统中被使用一样，该Div运算的结果，也就是相关于该模数的该整数商，因为其已经不需要，因此，至目前为止，已经被忽略，不过，依照本发明，现在，此信息不再简单地被忽略，而是加以计算以及使用，以于较短的计算单元上藉由较长的操作数执行计算。
[0019] 本发明的在一优点是，该Div运算经常可以在不需要实际上为硬接线的该计算单元中有所改变的情形下，仅藉由在一密码运算器的控制器中的改变而加以计算，而根据该观点，该MMD运算需要与该MultMod运算相同量的时间，但是却会于该Mod结果的上部上提供额外的信息，精确地说，依照本发明而使用的该Div结果。
附图说明
[0020] 本发明的较佳实施例将于之后，以所附图式做为参考，而进行更详尽地解释，其中：
[0021] 第1图：其显示依照本发明的一实施例的一装置的方块图；
[0022] 第2图：其显示操作数A的一代表，At，Ab为用于一半长度的次操作数； [0023] 第3图：其显示MMD运算的一示意代表；
[0024] 第4图：其显示初始MMD运算的一示意代表；
[0025] 第5图：其显示一预先决定的步骤顺序的一较佳实施例，其中，仅使用MMD运算； [0026] 第6图：其显示一预先决定的步骤顺序的一较佳实施例，其中，仅使用一初始MMD运算；
[0027] 第7图：其显示一预先决定的步骤顺序的一较佳实施例，其中，仅使用MMD运算； [0028] 第8图：其显示一预先决定的步骤顺序的一较佳实施例，其中，仅使用一初始MMD运算；
[0029] 第9图：其显示用于自这些操作数A、B以及该模数N的一因式分解(factorization)而取得第5图的该预先决定步骤顺序的一代表图；
[0030] 第10图：其显示用于自对这些操作数A、B以及该模数N的一因式分解(factorization)而取得第7图的该预先决定步骤顺序的一代表图；以及
[0031] 第11图：其显示一本发明的结合装置的一方块图。
具体实施方式
[0032] 第1图显示本发明用于计算一第一操作数A以及一第二操作数B的一模式乘法的一结果的一装置的方块图，其相关于一模式N，该第一以及第二操作数，以及具有一第一比特长度，举例而言，2n比特长度，的模数，这些操作数会被馈送进入用于提供次运算源的装置10之中，而藉由装置10所提供的次操作数为At，Ab，而它们产生自该第一操作数A，接着，该用于提供的装置10更进一步地提供产生自该第二操作数B的次操作数Bt，Bb，最后，该用于提供的装置10会提供产生自该模数N的次模数Nt，Nb，且这些变量At，Ab，Bt，Bb，Nt，以及Nb具有较原先数为短的长度。在本发明的一较佳实施例中，其中，最大成就加以达成，亦即，其中，该模数乘法可以藉由该最短的计算单元而加以执行，这些次操作数及/或次运算模数具有一长度n，也就是说，它们与该分别″原先操作数″的一半一样长。 [0033] 再者，根据本发明的装置包括MMD装置12，而其比特长度相等于最大次操作数及/或次模数的比特长度。若是所有的这些次操作数以及次模数具有相同的n比特长度时，则(i)MMD装置亦会具有一n比特的长度，该MMD运算加以定义为，一整数商数值Q 以及一剩余(i)
数值R 计算自两个经由输入端12a、12b而被馈送至该MMD装置的输入操作数，以及计算自经由一第三输入端12c而被提供的一MMD模式，以及加以定义为，该商数值以及剩余数值被输出于同时连接至控制装置14以及连接至结合装置16的一输出端12d处，该用于对该MMD装置馈送以输入运算以及相关的 MMD模数的预先结合的控制装置14，其会依照一预先决定的步骤顺序而一步一步地执行此馈送，这些输入操作数以及MMD模数会基于该第一操作数A的该第一次操作数At以及该第二次操作数Ab，基于该第二操作数B的该第一次操作数Bt以及该第二次操作数Bb，基于该模数N的该第一次模数Nt以及该第二次模数Nb，基于x
变量2 以及在该预先决定的步骤顺序中在前步骤的整数商数值以及剩余数值，其中，x，特别地，较2n为短，而在一较佳实施例中，相等于n，亦即，相等于该控制装置14可获得的这些数的最大长度。
[0034] 该结合装置16加以执行，以结合来自该预先决定的步骤顺序的预先决定步骤的整数商数值以及剩余数值，而获得结果E ＝A*B mod N，其再次地具有一长度2n比特。 [0035] 该用于提供的装置10的运算模式将于之后，以第2图做为参考，而进行更详尽地解释。第2图显示用于储存，举例而言，该第一操作数A的具有一2n比特长度的一第一站存器20。该用于提供的装置10会藉由将这些前x个比特复制进入一次操作数寄存器22之中，而产生该操作数A的该第一次操作数Ab，其中，在较佳实施例中，x相等于n，反之，该寄存器20的剩余比特，At，则被复制进入一第二次操作数寄存器24，因此，该第一以及第二次操作数可以藉由简单地分开该基本长数操作数的这些比特而加以获得，所以，源自该两个次操作数寄存器22以及24的数可以依照第2图所显示的方程式，亦即，藉由将该第一操作数写入一结果寄存器A，以及藉由将该第二操作数同样地也写入该结果寄存器，但向左移nn个比特，正如因子2 所代表的，而再次地产生该原先的操作数。
[0036] 第3图显示该MMD装置12的运算模式的一更详细代表图，相同地包括，特别是，用于执行一MMD运算的一MMD运算子30，而″MMD″代表″MultModDiv″，该MMD运算会自(i) (i) (i) (i) (i)三个输入数值A ，B ，以及N 而产生该整数商数值Q 以及一剩余数值R ，以作为一模数，该剩余数值照例藉由该mod运算而加以定义，反之，该商数值Q则是对应于A*B除以N的整数结果，因此，该MMD运算会将该乘积A*B转换成为由该整数商与该模数的乘积以及该剩余数值所形成的总和，在右上角的该指数(i)会符号化在该控制装置14所执行的该预先决定的步骤顺序中的一特殊步骤i，以利用一适当的方式控制该MMD装置12。 [0037] 在本发明的一较佳实施例中，较佳地是，该预先决定的顺序不仅是包括MMD算，而是除了该MMD运算之外，亦会执行至少一初始MMD运算，该初始MMD运算藉由在第4图标示n
为40的一方程式而加以定义，该运算会将一式子A*B+C*2 转换成为乘上模数的一整数商以及余数的一表述，C为任何所需的数，至于其数值n，该指数n会对应于上述的例子，其中，这些原先的操作数A、、以及N具有一n比特的长度，以及其中，这些次操作数及/次模数具有一n比特的长度，若是使用不同于对半这些操作数的一分割时，则n将必须由第4图中的该数值x所取代，x相等于该第一次操作数Ab，Bb及/或该次模数Nb的比特的数量，该整数余A会如在第4图的方程式42中所表示地加以定义，此外，该整数商Q则会如在第4图的方程式44中所表示地加以定义，因此，一初始MMD运算子30b会执行具有显示这些输入操(i) (i) (i) (i) (i)
作数A ，B ，N ．C 以及n的一式子的一所谓的输出MMD运算，进而产生该整数商Q(i)
以及该剩余数值R ，以作为输出数值。
[0038] 应该要指出的是，该初始MMD运算为一特殊定义的运算，若是该预先决定的步骤顺序在一MMD运算之外亦包括一初始MMD运算时，则其亦可以于第1图的该MMD装置12中执行，在此例子，第1图的该MMD装置12亦将被提供以该参数C以及该参数n，以作为该输入变量。
[0039] 请参阅第5图，接着叙述包括仅利用第1图的一MMD单元12以及第1图的具有一较短比特长度(较佳地为该比特长度的一半)的结合装置16，而计算A*B mod N的模数乘(i)法的结果的七个MultModDiv运算的一步骤顺序。在一第一步骤51中，一第一整数商Q 以(i) n
及一第一剩余数值R 利用这些输入操作数Bt以及2 再加上该MMD模数Nt而加以计算，在一第二步骤中，一第二整数商以及一第二剩余数值则是利用将该第一剩余数值以及该第一次模数Nb作为输入操作数而加以计算，而正如在第5图中所表示的一样，此程序接续着步(7) (7)
骤53，54，55，56，以及57，以于最终接收一第七整数商数值Q 以及一第七剩余数值R ，其利用该第一操作数A的该第一次操作数Ab与该第二操作数B的该第二次操作数Bb以及数n
2 作为该MMD模数，而获得自一MMD运算。
[0040] 第5图中，具有标题″输出″的一方程式58代表第1图的该结合装置16的该结(7) (6) (5)合运算，特别地是，该结合装置首先会形成剩余数值R -R -R 的一总和，以作为一第一(3) (4) (5) (6) (7)
总和，再者，第1图的这些结合装置16会计 算R +R -Q -Q +Q 的一总和，以作为一第n
二总和，而正如在第5图所表示的一样，该第二总和被乘上该因子2，并且，接续地被加上该第一总和，也正如第11图所表示的，此运算亦可以藉由一n比特计算单元，也就是说，一较点长度的一计算单元，而加以执行。
[0041] 其可由第5图获得证实，在第5图中所显示的该预先决定的步骤顺序中，仅需要具有输入操作数以及MMD模数的相对应结合的七个MMD运算，若是B已于事先为已知时，正如通常的例子一样，则该前面的两个MMD运算可以事先先加以计算，因此，会得出5个MMD运算的一线上效能(online performance)的结果，不过，应该要特别注意的是，该预先决定的(1) (2)步骤顺序的该第三步骤53，在此步骤中，该式子R -Q +Bb被使用作为该MMD运算的该第(3) (5)
二输入操作数，而因为此式子有可能变为负，因此，Q 以及Q (第5图的第五步骤55)亦可以变为负，在此例子中，其较佳地采用在负数值会于其中发生的那些例子的模数算术领域中，为普遍以及已知的适当预防，例如，举例而言，增加一模数，以将一负的结果带入正确的剩余分类(residual class)之中，也就是说，进入介于0以及构成该计算的基础的该模数之间的剩余分类之中。
[0042] 第6图显示一替代的预先决定顺序，其中，除了第3图的该MMD运算30a之外，第4图的该初始MMD运算30b亦加以使用。当在第6图中所显示的该预先决定的步骤顺序的(1) (1)
一第一步骤61中时，一第一商数值Q 以及一第一剩余数值R 藉由At，Bt，以及一MMD模数Nt而计算自一MMD运算，接着，一初始MMD运算(MultModDivInt)于步骤62中举行，精确地说，具有作为该第一输入操作数的该第一输入操作数(对应于第4图的A)，具有作为该第(1) (1)
二输入操作数的-Q (对应于第4图的B)，具有作为该第三输入操作数的R (对应于第4图的C)，以及具有作为该MMD模数的该第二次模数Nt(对应于第4图的N)。
[0043] 其可以由第6图中看出，不像第5图，仅需要六个MMD运算，其中，一个运算，精确地说，在该第二步骤62中的该第二运算，为一初始MMD运算，而要更进一步指出的是，由于(2)Q 可以变为负，其在此成为可能，因此，再次地，上述的用于负变量的方法可能必须加以使用。
[0044] 在第6图的一行67中，第1图的该结合装置16所执行的任务再次地加以表示，该(5) (6) (2) (3) (4) (5) (6)任务包括，形成R 以及-R 的该第一总和，形成R +R +R +Q -Q 的该第二总和以获得该第二总和，并且，以结合该第 一以及第二总和，若是需要考虑一进位(carry)时，则正如将于之后以第11图作参考而具有的更详尽解释一样。
[0045] 第7图其显示包括用于计算平方该操作数A的结果的步骤71，72，73，74，75，76的一预先决定步骤顺序。在此例子中，该第一操作数会对应于该第二操作数，亦即，该第一以及第二运算源为相同的，而从第7图可以看出，在第7图中所显示的该平方算法中，没有使用具有初始的MMD运算，以及全部六个MMD运算为足够，正如相对于若是该第一以及第二操作数并不相同时所需要的七个MMD运算一样，此外，其应该要指出的是，由于存在于该第三(3) (4)步骤中的差异，因此，该第三商数值Q 以及该第四商数值Q 两者会变为负的。 [0046] 第8图显示依照一替代实施例的一预先决定步骤顺序，其中，一初始MMD运算再次地于该预先决定步骤顺序的该第二步骤82中加以使用，而该第一以及第二输入操作数分(1) (1)
别为Nb以及-Q ，该第三输入操作数(对应于第4图中的C)为该第一剩余数值R ，以及该第一次模数Nt被用作为该MMD模数。若是一初始MMD运算加以使用时，则会产生五个MMD运算，正如相对于第7图在没有初始情况下的六个MMD运算，再次地，其应该要指出的是，该(2)
第二整数商数值Q 可能变为负的。
[0047] 各种预先决定步骤顺序的一示范性衍生将于之后藉由第9A图以及第9B图而加以讨论。
[0048] 特别地是，第9A图显示用于不具有初始的一乘法的在第5图中所示的该预先决定步骤顺序的一衍生，而第9B图，相对地，则是显示用于具有初始的一乘法，也就是说，一初始MMD运算于其中发生在该预先决定步骤顺序的一步骤中的一乘法，之在第6图中所示的该预先决定步骤顺序的一衍生。
[0049] 第10图显示用于不具初始的一平方的第7图的该预先决定步骤顺序的一衍生，也就是说，仅具有MMD运算，没有在该预先决定步骤顺序的任何步骤中执行任何初始MMD运算。
[0050] 第9A图、第9B图、以及第10图的每一个皆开始于建立相关的乘积进行计算，然而，现在，加以考虑在第2图中所表示的连结，亦即，该第一以及第二操作数A、B已经被该分别的第一以及第二次操作数所取代的事实，正如可以自第9A图的90a、第9B图的90b、以及第10图的100 看出的一样，特别地是，一第一项次At*Z+Ab以及一第二项次Bt*Z+Bb的一乘积加以建立，并且加以展开。
[0051] 接下来，请参阅在第9A图中的一示范性方式。展开产生在第9A图中的一行91，举例而言，在第9A图的该行91的该第一项次中，该乘积Bt*Z经历会一MMD运算，z对应于n该数2，正如在第9图、第9B图、以及第10图的右半边所表示一样，而由于该模数的该第一次模数Nt被使用作为用于此第一MMD运算的该MMD模数，因此，可以获得一第二行92，在其(1) (1)
中，出现了该第一整数商Q 以及该第一整数剩余R ，接着，在一行93中，使用提供于行93的右边的一关系，而该关系则在于陈述，乘上z的该第一次模数Nt乃会相等于该第二次模数Nbmod N的负值，此连结源自于下列的条件方程式：
[0052] N ＝Nt*Z+Nb.
[0053] 若是Nb自整个方程式被减去时，则会得到下列的方程式：
[0054] N-Nb＝Nt*Z.
[0055] 若是此方程式被缩减，在上述方程式中的左手侧的N被删除的话，因此会得到下列的方程式：
[0056] Nt*Z＝-Nb mod N.
[0057] 藉由使用用于展开于第9A图中该行92的该第一个刮号的上述条件方程式，其(1)中，会产生该因子Q *Nt*At*Z，而当考虑第9A图的行93的该第二项次时，此因子会变(1)
为-At*Q *Nb，正如可由第9A图的一行93看出的一样，接着，在第9A图的一行94中，此第二项次现在会经历一MMD运算(第5图的步骤52)，以获得一行94，在此之后，上述在Nt*Z以及-Nb之间的连结会再次地加以考虑，而此程序会重复数次，因此，在行91中所形成的这些部分乘积会利用MMD运算而一步一步地加以处理，所以，仅会留下一n比特长度以及一因n
子2 的数、或是一n比 特长度的数的乘积，正如可由第9A图的最后一行看出的一样，其对应于第5图的行58。
[0058] 在第9B图中所显示的该衍生例子对应于第6图的该预先决定步骤顺序，亦即，对应于具有初始的一般乘法，一MultModDivInt，其亦为一初始MMD运算，于一行95中加以执行，精确地说，藉由第9B图的该第一项次。该第一操作数(对应于第4图的A)为Nb，该第二(1) (1)操作数(对应于第4图中的B)为该数值-Q ，该第三操作数(对应于第4图的C)为R ，n
反之，该数Z对应于2，正如已经解释过的，该MMD初始运算的结果显示于第9B图的行96的第一项次之中。
[0059] 第10图显示用于平方，也就是说，用于表示于第7图中的该预先决定步骤顺序，之不具有初始的一相对应衍生，原则上，其再次地以相似于在第9A图以及第9B图中所示的该衍生的方式而加以执行。
[0060] 由上述的表述可以证实，任何预先决定的步骤顺序皆可以利用由于数学转换的多样可能性的总和乘法逼近(sum multiplication approach)(90a，90b，100)而加以形成，以解决在该″总和乘积逼近(sum-productapproach)″中所显示的运算，因此，将仅会留下具n有一n比特长度的商数值以及剩余数值，及/或适当乘上2 的商数值以及剩余数值。而除了一正常加法之外，唯一所需要的运算仅是一MMD运算、或可选择地，亦可以为一初始MD运算，然而，其亦仅需要一x(较佳地为n)比特长度。
[0061] 为了实际的理由，举例而言，为了能够掌控一进位、或一负数，其较佳地使得用于执行该MMD运算、该初始MMD运算、或该结合装置16藉由少数比特，例如，1或2个比特，所执行的该运算的该计算单元大于n个比特，然而，若是不考虑尺寸的话，则此并不构成问题，亦即，现在，2n比特的操作数可以在实际执行时需要更多少数比特的一n比特计算单元上，以一有效率且清楚的方式而加以计算，然而，相较于省略1024个比特及/或关于能够在既存装置上运作一安全算法的可能性，这些额外的比特为微不足道。
[0062] 在第1图中所显示的该结合装置16的一较佳实施例将以第11图做为参考而于之后进行更详尽的解释。该结合装置用以转换，在电路工程方面，第5图的该预先决定步骤顺序的行58，第6图的该预先决定步骤顺序的行67，第7图的该预先决定步骤顺序的行77，或是第8图的该预先决定步骤顺序的行86，此将于之后以第5图的行58作为参考而提出。 [0063] 结合装置16包括复数个用于这些剩余数值R(3)与R(4)，R(5)，R(6)，以及R(7)，以及用(5) (6) (7)于这些商数值Q ，Q ，以及Q 的n比特寄存器110，而其被用于结合运算，其它的剩余数值及/或商数值仅需要作为中间结果，亦即，从该预先决定步骤顺序的一个步骤至下一个、或是至该预先决定步骤顺序的一接续步骤，然而，在第11图中所显示的这些寄存器最终结合运算58所需要。
[0064] 再者，该结合装置包括标示为112的一n比特加法器(或是，正如已经解释过的，关于比n比特多出1至2个比特)，一流程控制114、进位确认装置116，以及一n比特乘法器118，以将获得的结果写入一2n比特存储位置120。
[0065] 起初，该流程控制114会控制该寄存器档案110以及该n比特加法器，以计算(7) (6) (5)R -R -R 的该第一总和，而为了这个计算，该个别加法器的最不重要比特(1sb)的该进位输入端112会加以初始化至一数值″0″，在此之后，该第一总和的最重要比特的进位会加以检查。
[0066] 若是发现该n比特加法器112的该msb(msb＝most significant bit，最重要比特)包括一″0″进位比特时，则没有改变会发生在该1sb个别加法器的该进位输入，此输入会继续被初始化至″0″。
[0067] 然而，若是发现该第一总和提供一进位时，则该第二总和R(3)+R(4)-Q(5)-Q(6)+Q(7)会加以计算，精确地说，藉由初始化至″1″的一进位，该第一总和会藉由该流程控制114所控制该n比特乘法器而被写入该2n比特存储位置120的低阶(low-order)比特120a之中，反之，在计算完该第二总和之后，其会藉由为了该最不重要个别加法器而相对应地初始化的一进位输入而被写入该2n比特存储位置120的高阶(high-order)比特120b之中，因n此，乘上该因子2 藉由在第11图所示的该实施例中的该n比特乘法器而加以执行，当然，此运俗亦可以藉由一暂存位移器(register shifter)、或类似者，正如在习知技术中已知者，而加以执行。
[0068] 根据本发明概念的上述解释可以清楚知道，所需要的复数个任何另外的衍生及/或复数个另外预先决定的步骤顺序亦可以自在第9图、第9B图、以及第10图中所建立的这些衍生而进行推论，藉由长度较这些输入变量A、B、N为短的一计算单元，仅利用MMD运算、或利用MMD运算的一模数乘法，以及一个或数个初始MMD运算。
[0069] 在第9图、第9B图、以及第10图中所显示的例子中，及/或在用于预先决定的步n骤顺序的各种实施例中，其较佳地仅使用该第一次模数Nt以及该数2，而不是该第二次模数Nb，以作为该MMD模数。对本领域普通技术人员而言，显然地，上述的衍生亦可以应用于n
除了2 之外的其它数Z，只要将该模式分解为次模数的因式分解依照该数Z而加以选择即可。
[0070] 参考符号列表
[0071] 10 means for providing 用于提供的装置
[0072] 12 MMD means MMD装置
[0073] 12a first input for the first input operand
[0074] 第一输入操作数的第一输入端
[0075] 12b second input for the second input operand
[0076] 第二输入操作数的第二输入端
[0077] 12c input for the MMD modulus MMD模数的输入端
[0078] 12d output of the MMD means MMD装置的输出端
[0079] 14 control means for feeding 用于馈送的控制装置
[0080] 16 combining means 结合装置
[0081] 20 2n-bits number 2n比特数
[0082] 22 sub-operand Ab with n bits具有n比特的次操作数Ab
[0083] 24 sub-operand At with n bits 具有n比特的次操作数At
[0084] 30a MMD operator MMD运算子
[0085] 30b initializing MMD operator初始MMD运算子
[0086] 40 conditional equation for the initializing MMD operation [0087] 初始MMD运算的条件方程式
[0088] 44a defining equation for the remainder 余数的定义方程式 [0089] 44b defining equation for the integer quotient整数商的定义方程式 [0090] 51 up to 57，steps 1 to 7 of a predetermined step sequence for [0091] a multiplication and initialization
[0092] 用于一乘法以及初始化的一预先决定步骤顺序的步骤1至7
[0093] 58 calculation specification for the combining means
[0094] 用于结合装置的计算说明
[0095] 61 up to 66，predetermined step sequence for a general
[0096] multiplication with initialization
[0097] 用于一具有初始化的一般乘法的预先决定步骤顺序
[0098] 67 calculation specification for the combining device
[0099] 用于结合装置的计算说明
[0100] 71 up to 76，predetermined step sequence for a squaring without [0101] initialization
[0102] 用于一不具有初始化的平方的预先决定步骤顺序
[0103] 77 combining specification结合说明
[0104] 81 up to 85，predetermined step sequence for a squaring with [0105] initialization
[0106] 用于一具有初始化的平方的预先决定步骤顺序
[0107] 86 combining specification结合说明
[0108] 90a，90b，90c sum/product approach总和/乘积逼近
[0109] 91 multiplied products 被乘的乘积
[0110] 92 term of an MMD operation一MMD运算的项次
[0111] 93 derivation term衍生项次
[0112] 94 another derivation term另一衍生项次
[0113] 95 another derivation term另一衍生项次
[0114] 96 another derivation term另一衍生项次
[0115] 100 sum/product approach for squaring
[0116] 用于平方的总和/乘积逼近
[0117] 110 n-bits register n比特寄存器
[0118] 112 n-bits adder n比特加法器
[0119] 114 flow control 流程控制
[0120] 116 carry verification means 进位确认装置
[0121] 118 n-bits multiplexer n比特乘法器
[0122] 120 2n-bits memory location 2n比特存储位置
[0123] 120a low-order bits 低阶比特
[0124] 120b high-order bits 高阶比特
