以相似的效率处理任意密钥位长加密操作的方法和设备转让专利
申请号 : CN03824410.1
文献号 : CN100592676C
文献日 : 2010-02-24
发明人 : 哈非兹·扎阿比
申请人 : 睦塞德技术公司
摘要 :
一种具有诸如以流水线形式排列的多级的计算设备或系统，该计算设备或系统具有沿着级安置的计时轨或导体。在大量的即几百个级并行地排列成子阵列的情况下，计时导体沿着子阵列迂回延伸。在单个级中排列成，在级中进行的两个计算中的最短计算出现在返回路径中。可以将阵列分成分开的部件用于独立处理。
权利要求 :
1、一种处理加密过程中的数据的方法，所述方法包括以下步骤：a)提供用于加密的第一流水线处理器，包括以串行阵列的形式排 列的n个单独处理部件，其中第一处理部件在领先于作为最终处理部 件的第n处理部件的第二处理部件之前；
b)提供加密密钥给第一流水线处理器；
c)将指示加密密钥长度的数据提供给第一流水线处理器；
d)将数据提供给第一处理部件以便加密处理；
e)至少根据指示加密密钥长度的数据来确定第N个处理部件为 最末处理部件，其中N小于或等于n；
f)将指示处理部件是最末处理部件的信号提供给最末处理部件；
g)从第一处理部件以逐步正向串行的形式来传送用于进一步加 密处理的数据，仅仅到最末处理部件为止；以及其中，同一流水线处理器内的至少两个处理部件能够被确定为最 末处理部件。
2、根据权利要求1所述的处理数据的方法，其中最末处理部件不 同于最终处理部件。
3、根据权利要求1所述的处理数据的方法，其中加密密钥被填补 到整数倍的预定位数，以及其中预定位数等于多个处理部件中的单个 处理部件在一个处理周期期间处理的位数的整数倍。
4、根据权利要求3所述的处理数据的方法，其中只有能够被确定 为最末处理部件的那些处理部件才装备有用于接收所述信号的电路。
5、根据权利要求4所述的处理数据的方法，其中少于总数目的处 理部件能够被确定为最末处理部件。
6、根据权利要求1所述的处理数据的方法，包括以下步骤：
h)将指示加密密钥长度的数据和要处理的数据提供给第一处理 部件；
i)利用第一处理部件内部的电路处理指示加密密钥长度的数据； 以及j)将经过处理的指示加密密钥长度的数据传送给至少下一个处 理部件，以便利用所述至少下一个处理部件的内部电路进行附加处理。
7、根据权利要求6所述的处理数据的方法，其中处理指示加密密 钥长度的数据的步骤是递减操作和递增操作之一。
8、根据权利要求7所述的处理数据的方法，包括以下步骤：
k)当利用至少下一个处理部件的内部电路来处理指示加密密钥 长度的数据的步骤返回指示该处理部件是最末处理部件的预定值时， 在处理之后，仅仅沿前面的处理部件的方向上的返回处理路径来传送 数据。
9、根据权利要求1所述的处理数据的方法，包括以下步骤：
提供第二流水线处理器，所述第二流水线处理器包括以串行阵列 的形式排列的多个单独处理部件，其中第一处理部件在领先于最终处 理部件的第二处理部件之前；
其中，组合使用第一流水线处理器和第二流水线处理器来进行加 密处理。
10、根据权利要求9所述的处理数据的方法，其中第一流水线处 理器和第二流水线处理器在第一模式下是独立的流水线处理器，以及 在第二模式下是单一的组合流水线处理器。
11、一种处理加密过程中的数据的设备，所述设备包括：
以串行阵列的形式排列的n个单独处理部件，其中第一处理部件 在领先于作为最终处理部件的第n处理部件的第二处理部件之前；
端口，至少与串行阵列的处理部件电通信，以便提供数据给串行 阵列进行加密处理；以及逻辑电路，该逻辑电路与所述端口以及串行阵列的至少两个处理 部件电通信，用于在使用中处理指示加密密钥长度的数据以便在所述 至少两个处理部件之中确定串行阵列的最末处理部件，以及根据指示 加密密钥长度的数据而将信号提供给作为串行阵列的被确定最末处理 部件的至少两个处理部件之一，其中所述至少两个处理部件的数目小 于或等于n，其中，从第一处理部件以逐步正向串行的形式来传送用于进一步 加密处理的数据，仅仅到最末处理部件为止。
12、根据权利要求11所述的处理数据的设备，其中多个单独处理 部件排列成两个或多个流水线处理阵列，其中阵列用于独立地接收要 处理的数据，或者用于当最末处理部件状态是由超出单个流水线处理 阵列的最末处理部件以外的处理部件引起时，被连接到单个更大阵列 中。
13、根据权利要求11所述的处理数据的设备，其中少于总数目的 处理部件能够被确定为最末处理部件。
14、根据权利要求13所述的处理数据的设备，其中能够被确定为 最末处理部件的处理部件进一步包括用于接收所述信号的电路。
15、根据权利要求14所述的处理数据的设备，其中逻辑电路是用 于通过可寻址数据路径将信号提供给确定的处理部件的门逻辑开关电 路。
16、根据权利要求14所述的处理数据的设备，其中逻辑电路包括：第二处理器，用于执行用来根据指示密钥长度的数据来确定最末 处理部件的程序代码以及提供所述信号给确定的处理部件；以及在第二处理器与串行阵列的至少两个处理部件之间延伸的通信路 径，所述通信路径用于将所述信号从第二处理器引导至确定的处理部 件。
17、一种处理加密过程中的数据的设备，所述设备包括：
以串行阵列的形式排列的多个单独加密处理部件，其中第一加密 处理部件在领先于作为最终加密处理部件的第n加密处理部件的第二 加密处理部件之前；以及第一加密处理部件与第n加密处理部件之间的每个单独加密处理 部件内部的逻辑电路，用于在使用中处理指示加密密钥长度的数据， 以及在加密处理部件的内部提供指示最末加密处理部件状态的信号， 该信号根据指示加密密钥长度的数据来提供，其中，从第一加密处理部件以逐步正向串行的形式来传送用于进 一步加密处理的数据，仅仅到最末加密处理部件为止。
18、根据权利要求17所述的处理数据的设备，其中多个单独加密 处理部件排列成两个或多个流水线处理阵列，其中阵列用于独立地接 收要加密处理的数据，或者用于当最末加密处理部件状态是由超出单 个流水线处理阵列的最末加密处理部件以外的加密处理部件引起时， 被连接到单个更大阵列中。
说明书 :
本申请是2002年8月26日提交的美国申请No.10/228,151的继 续，并要求其优先权。以上申请的整个教导在此通过参考而被引入。
技术领域
本发明一般涉及并行处理器，并尤其涉及一种能够利用相同处理 器、以相似的效率来处理任意密钥位长加密操作的并行处理器。
背景技术
例如通过诸如万维网(WWW)的因特网的广泛分布式信息网络 在各方之间交换电子存储的文件正变得较为常见。因特网的常见问题 是缺少安全通信信道。因而，为了使医院、政府、银行、股票经纪人 和信用卡公司利用因特网，必须确保保密性和安全性。解决上述问题 的一种方法是在发送之前使用数据加密。在现有技术系统中，主计算 机系统装备有加密单元，例如与用于至少存储私有加密密钥的至少一 个存储电路进行电通信的加密处理器。当信息要从主计算机系统、通 过因特网发送给接收器、并且具有机密性质时，信息首先被传递到加 密处理器，以便利用存储的私有密钥对信息加密。典型地，每当执行 加密操作时，都使用相同的私有密钥。作为替换，从与加密处理器进 行电通信的至少一个存储电路中存储的一组有限的加密密钥中选择加 密密钥。
当然，由加密处理器执行的数据加密操作是算术算法，其中输入 数据值，例如散列型式的电子文件，是唯一变量值。因此，有可能对 加密处理器进行优化，以便利用最少量的处理器资源来执行期望的加 密功能。另外，在现有技术加密单元中，优化的加密处理器典型地与 主计算机系统的微处理器分开，因为加密单元这样被最佳地优化。
现今，对于通过加密/解密的因特网上保密性和强鉴定有几种标 准。典型地，根据意图允许在各方之间在公开信道上进行数据传送， 同时维持消息内容的保密性的算法，来执行加密/解密。这是通过由发 送器利用加密密钥对数据加密，并由接收器利用解密密钥对数据解密 来实现的。在对称密钥密码术中，加密密钥和解密密钥相同。
加密算法典型地被分类为公开密钥(public-key)和秘密密钥 (secret-key)算法。在秘密密钥算法中密钥是秘密的，而在公开密钥 算法中，使密钥之一广为公众所知。分组密码是当今使用的秘密密钥 密码系统的代表。通常，对于分组密码，使用对称密钥。分组密码取 一块数据，典型地为32-128位，作为输入数据，并产生相同的位数作 为输出数据。利用具有典型地在56-128位范围内的长度的密钥，来执 行加密和解密操作。加密算法被设计成在不知道密钥的情况下很难对 消息解密。
除分组密码(block cipher)以外，因特网安全协议也依赖于基于 公开密钥的算法。诸如Pogue和Rivest的美国专利No.5,144,667中描 述的Rivest、Shamir、Adelman(RSA)加密系统的公开密钥加密系统 使用两个密钥，其中一个是秘密一私有的，而另一个是公开可得的。 一旦某人公开了公开密钥，任何人都可以向那个人发送利用那个公开 密钥加密的秘密消息；然而，只能利用私有密钥来实现消息的解密。 这种公开密钥加密的优点是，事先不将私有密钥分发给会话的所有方。 相反，当使用对称加密时，多个秘密密钥被产生，想要接收消息的每 一方一个秘密密钥，并且每个秘密密钥被秘密地传送。试图以安全的 形式分发秘密密钥导致了与只利用秘密密钥加密发送消息所面临的问 题类似的问题；这典型地被称为密钥分发问题。
密钥交换是公开密钥技术的另一个应用。在密钥交换协议中，双 方能够约定秘密密钥，即使第三方截取了他们的会话。美国专利 No.4,200,770中描述的Diffie-Hellman指数密钥交换方法是这种协议 的例子。
大多数的公开密钥算法，诸如RSA和Diffie-Hellman密钥交换， 是基于模取幂，模取幂是αx模p的计算。该表达式表示，“使α乘以它 自己x倍，使答案除以p，并取余数”。由于以下原因，该计算执行起 来计算量非常大。为了执行该操作，需要许多重复的乘法操作和除法 操作。诸如“Modular Multiplication Without Trial Division”， Mathematics of Computation，Vol.44，No.170，April，1985中描述的 Montgomery方法的技术能够减少除法操作数，但是没有克服该总体计 算开销。另外，对于当前的数据加密系统，使用的数非常大(典型地 为1024位或更多)，因此普通中央处理器(CPU)中存在的乘法和除 法指令不能直接使用。而是，使用特定算法来将大的乘法操作和除法 操作分解成小得足以在CPU上执行的操作。这些算法通常具有与所涉 及的机器字的数量的平方成比例的运行时间。例如，Pentium处理器 能够在10个时钟周期内执行32×32位乘法。2048位的数可以表示为 64个32位的字。2048×2048位的乘需要64×64个单独的乘法操作， 这在Pentium处理器上花费40960个时钟。如果直接执行，则对2048 位指数取幂需要直到4096次乘法操作，这需要大约167百万个时钟周 期。如果Pentium处理器以166MHz运行，则全部操作大概需要一秒。 当然，除法操作进一步增加了整个计算时间。显然，诸如Pentium的 普通CPU不能期望以任何高的速率来执行密钥产生和交换。
包括以串行阵列形式排列的多个独立处理部件尤其是大量处理部 件的流水线处理器在现有技术中是周知的，并且尤其适于执行数据加 密算法。两种类型的流水线处理器是周知的：一端进且另一端出类型 的处理器，其中存在单一处理方向；以及同一端进和出类型的双向处 理器，其中存在正向处理方向和返回处理方向。考虑双向流水线处理 器的特定例子，第一数据块从存储缓冲器被读入串行阵列的第一处理 部件，第一处理部件执行第一阶段处理，然后将第一数据块传递给第 二处理部件。第二处理部件执行第二阶段处理，同时第一处理部件并 行地从存储缓冲器读出第二数据块，并对第二数据块执行相同的第一 处理阶段。依次地，每个数据块以逐步的形式沿串行阵列的正向处理 方向从一个处理部件传播到下一个处理部件。在每一步都有处理阶段， 该处理阶段对所提供的每一个数据块执行相同的数学运算。同时，关 于返回处理方向，在每一个处理部件中计算的结果被提供给串行阵列 的前一个处理部件，这些结果总计包括了加密处理器返回的经过处理 的数据。这种使用大量处理部件的流水线数据处理方法是执行前述的 大计算量的数据加密算法的非常有效方法。当然，用于执行大计算量 处理操作的流水线处理器的应用并不严格限于已经举例详细讨论的数 据加密算法。
现有技术加密处理器的缺点是，处理器限于固定的密钥大小或者 作为替换地限于固定的性能。因而，或者处理器只处理例如128位的 密钥，或者处理器需要用与处理40位加密操作所花时间相等的时间， 来处理128位加密操作。典型地，这两种设计要求考虑到处理器的最 佳性能。
提供一种能够利用相同处理器以相似的效率来处理任意密钥位长 加密操作的并行处理器将是有利的。
当然，由加密处理器执行的数据加密操作是算术算法，其中输入 数据值，例如散列型式的电子文件，是唯一变量值。因此，有可能对 加密处理器进行优化，以便利用最少量的处理器资源来执行期望的加 密功能。另外，在现有技术加密单元中，优化的加密处理器典型地与 主计算机系统的微处理器分开，因为加密单元这样被最佳地优化。
现今，对于通过加密/解密的因特网上保密性和强鉴定有几种标 准。典型地，根据意图允许在各方之间在公开信道上进行数据传送， 同时维持消息内容的保密性的算法，来执行加密/解密。这是通过由发 送器利用加密密钥对数据加密，并由接收器利用解密密钥对数据解密 来实现的。在对称密钥密码术中，加密密钥和解密密钥相同。
加密算法典型地被分类为公开密钥(public-key)和秘密密钥 (secret-key)算法。在秘密密钥算法中密钥是秘密的，而在公开密钥 算法中，使密钥之一广为公众所知。分组密码是当今使用的秘密密钥 密码系统的代表。通常，对于分组密码，使用对称密钥。分组密码取 一块数据，典型地为32-128位，作为输入数据，并产生相同的位数作 为输出数据。利用具有典型地在56-128位范围内的长度的密钥，来执 行加密和解密操作。加密算法被设计成在不知道密钥的情况下很难对 消息解密。
除分组密码(block cipher)以外，因特网安全协议也依赖于基于 公开密钥的算法。诸如Pogue和Rivest的美国专利No.5,144,667中描 述的Rivest、Shamir、Adelman(RSA)加密系统的公开密钥加密系统 使用两个密钥，其中一个是秘密一私有的，而另一个是公开可得的。 一旦某人公开了公开密钥，任何人都可以向那个人发送利用那个公开 密钥加密的秘密消息；然而，只能利用私有密钥来实现消息的解密。 这种公开密钥加密的优点是，事先不将私有密钥分发给会话的所有方。 相反，当使用对称加密时，多个秘密密钥被产生，想要接收消息的每 一方一个秘密密钥，并且每个秘密密钥被秘密地传送。试图以安全的 形式分发秘密密钥导致了与只利用秘密密钥加密发送消息所面临的问 题类似的问题；这典型地被称为密钥分发问题。
密钥交换是公开密钥技术的另一个应用。在密钥交换协议中，双 方能够约定秘密密钥，即使第三方截取了他们的会话。美国专利 No.4,200,770中描述的Diffie-Hellman指数密钥交换方法是这种协议 的例子。
大多数的公开密钥算法，诸如RSA和Diffie-Hellman密钥交换， 是基于模取幂，模取幂是αx模p的计算。该表达式表示，“使α乘以它 自己x倍，使答案除以p，并取余数”。由于以下原因，该计算执行起 来计算量非常大。为了执行该操作，需要许多重复的乘法操作和除法 操作。诸如“Modular Multiplication Without Trial Division”， Mathematics of Computation，Vol.44，No.170，April，1985中描述的 Montgomery方法的技术能够减少除法操作数，但是没有克服该总体计 算开销。另外，对于当前的数据加密系统，使用的数非常大(典型地 为1024位或更多)，因此普通中央处理器(CPU)中存在的乘法和除 法指令不能直接使用。而是，使用特定算法来将大的乘法操作和除法 操作分解成小得足以在CPU上执行的操作。这些算法通常具有与所涉 及的机器字的数量的平方成比例的运行时间。例如，Pentium处理器 能够在10个时钟周期内执行32×32位乘法。2048位的数可以表示为 64个32位的字。2048×2048位的乘需要64×64个单独的乘法操作， 这在Pentium处理器上花费40960个时钟。如果直接执行，则对2048 位指数取幂需要直到4096次乘法操作，这需要大约167百万个时钟周 期。如果Pentium处理器以166MHz运行，则全部操作大概需要一秒。 当然，除法操作进一步增加了整个计算时间。显然，诸如Pentium的 普通CPU不能期望以任何高的速率来执行密钥产生和交换。
包括以串行阵列形式排列的多个独立处理部件尤其是大量处理部 件的流水线处理器在现有技术中是周知的，并且尤其适于执行数据加 密算法。两种类型的流水线处理器是周知的：一端进且另一端出类型 的处理器，其中存在单一处理方向；以及同一端进和出类型的双向处 理器，其中存在正向处理方向和返回处理方向。考虑双向流水线处理 器的特定例子，第一数据块从存储缓冲器被读入串行阵列的第一处理 部件，第一处理部件执行第一阶段处理，然后将第一数据块传递给第 二处理部件。第二处理部件执行第二阶段处理，同时第一处理部件并 行地从存储缓冲器读出第二数据块，并对第二数据块执行相同的第一 处理阶段。依次地，每个数据块以逐步的形式沿串行阵列的正向处理 方向从一个处理部件传播到下一个处理部件。在每一步都有处理阶段， 该处理阶段对所提供的每一个数据块执行相同的数学运算。同时，关 于返回处理方向，在每一个处理部件中计算的结果被提供给串行阵列 的前一个处理部件，这些结果总计包括了加密处理器返回的经过处理 的数据。这种使用大量处理部件的流水线数据处理方法是执行前述的 大计算量的数据加密算法的非常有效方法。当然，用于执行大计算量 处理操作的流水线处理器的应用并不严格限于已经举例详细讨论的数 据加密算法。
现有技术加密处理器的缺点是，处理器限于固定的密钥大小或者 作为替换地限于固定的性能。因而，或者处理器只处理例如128位的 密钥，或者处理器需要用与处理40位加密操作所花时间相等的时间， 来处理128位加密操作。典型地，这两种设计要求考虑到处理器的最 佳性能。
提供一种能够利用相同处理器以相似的效率来处理任意密钥位长 加密操作的并行处理器将是有利的。
发明内容
根据本发明，提供一种处理数据的方法，该方法包括以下步骤：
a)提供包括以串行阵列的形式排列的n个单独处理部件的流水 线处理器，以致第一处理部件在领先于第n处理部件的第二处理部件 之前；
b)提供m位加密密钥给流水线处理器；
c)将指示加密密钥长度的数据提供给流水线处理器；
d)将数据提供给第一处理部件以便处理；
e)至少根据指示加密密钥长度的数据来确定最末处理部件；
f)将指示处理部件是最末处理部件的信号提供给最末处理部件；
g)从第一处理部件以逐步正向串行的形式来传送用于进一步处 理的数据，仅仅到最末处理部件为止；以及其中，同一流水线处理器 内的至少两个处理部件可以被确定为最末处理部件。
根据本发明，提供一种处理数据的设备，备包括：
以串行阵列的形式排列的多个单独处理部件，其中第一处理部件 在领先于第n处理部件的第二处理部件之前；
端口，至少与串行阵列的处理部件电通信以便提供数据给串行阵 列进行处理；以及
逻辑电路，该逻辑电路与所述端口以及串行阵列的至少两个处理 部件电通信，用于在使用中处理指示加密密钥长度的数据以便确定串 行阵列的最末处理部件，以及根据指示加密密钥长度的数据将信号提 供给作为串行阵列的被确定处理部件的至少两个处理部件之一。
根据本发明，提供一种处理数据的设备，包括：
以串行阵列的形式排列的多个单独处理部件，其中第一处理部件 在领先于第n处理部件的第二处理部件之前；以及
每个单独处理部件内部的逻辑电路，用于在使用中处理指示加密 密钥长度的数据，以及将指示最末处理部件状态(last processing element status)的信号提供给处理部件的内部，该信号根据指示加密 密钥长度的数据来提供。
a)提供包括以串行阵列的形式排列的n个单独处理部件的流水 线处理器，以致第一处理部件在领先于第n处理部件的第二处理部件 之前；
b)提供m位加密密钥给流水线处理器；
c)将指示加密密钥长度的数据提供给流水线处理器；
d)将数据提供给第一处理部件以便处理；
e)至少根据指示加密密钥长度的数据来确定最末处理部件；
f)将指示处理部件是最末处理部件的信号提供给最末处理部件；
g)从第一处理部件以逐步正向串行的形式来传送用于进一步处 理的数据，仅仅到最末处理部件为止；以及其中，同一流水线处理器 内的至少两个处理部件可以被确定为最末处理部件。
根据本发明，提供一种处理数据的设备，备包括：
以串行阵列的形式排列的多个单独处理部件，其中第一处理部件 在领先于第n处理部件的第二处理部件之前；
端口，至少与串行阵列的处理部件电通信以便提供数据给串行阵 列进行处理；以及
逻辑电路，该逻辑电路与所述端口以及串行阵列的至少两个处理 部件电通信，用于在使用中处理指示加密密钥长度的数据以便确定串 行阵列的最末处理部件，以及根据指示加密密钥长度的数据将信号提 供给作为串行阵列的被确定处理部件的至少两个处理部件之一。
根据本发明，提供一种处理数据的设备，包括：
以串行阵列的形式排列的多个单独处理部件，其中第一处理部件 在领先于第n处理部件的第二处理部件之前；以及
每个单独处理部件内部的逻辑电路，用于在使用中处理指示加密 密钥长度的数据，以及将指示最末处理部件状态(last processing element status)的信号提供给处理部件的内部，该信号根据指示加密 密钥长度的数据来提供。
附图说明
由以下连同附图的优选实施例的说明，本发明将更容易理解，其 中：
图1显示了根据先有技术的流水线处理器的实施例的简化框图；
图2显示了根据先有技术的流水线处理器的另一个实施例的简化 框图；
图3a显示了根据本发明第一实施例的具有分布式递减电路的流 水线处理器的简化框图；
图3b显示了与分布式递减电路通信的图3a的流水线处理器的串 行处理器阵列的简化框图；
图4a显示了根据本发明第二实施例的具有电路的流水线处理器 的简化框图；
图4b显示了与该电路通信的图4a的流水线处理器的串行处理器 阵列的简化框图；
图5a显示了根据本发明第三实施例的流水线处理器的简化框图；
图5b显示了其中每个处理部件都具有内部递减电路的图4a的流 水线处理器的串行处理器阵列的简化框图；
图6显示了根据本发明的流水线处理器的第四优选实施例的简化 框图；
图7显示了根据本发明的流水线处理器的第五优选实施例的简化 框图；
图8是供用于执行加密功能的流水线阵列处理器之用的资源高效 处理部件设计的框图；
图9是用于模乘的脉动阵列(systolic array)的框图；
图10是其输入路径被显示的单个单元的框图；
图11是DP RAM Z单元的框图；
图12是Exp RAM单元的框图；
图13是Prec RAM单元的框图；
图14是供用于执行加密功能的流水线阵列处理器之用的速度高 效处理部件设计的框图；
图15是用于模乘的脉动阵列的框图；
图16是其输入路径被显示的单一单元的框图；以及
图17是DP RAM Z单元的框图。
图1显示了根据先有技术的流水线处理器的实施例的简化框图；
图2显示了根据先有技术的流水线处理器的另一个实施例的简化 框图；
图3a显示了根据本发明第一实施例的具有分布式递减电路的流 水线处理器的简化框图；
图3b显示了与分布式递减电路通信的图3a的流水线处理器的串 行处理器阵列的简化框图；
图4a显示了根据本发明第二实施例的具有电路的流水线处理器 的简化框图；
图4b显示了与该电路通信的图4a的流水线处理器的串行处理器 阵列的简化框图；
图5a显示了根据本发明第三实施例的流水线处理器的简化框图；
图5b显示了其中每个处理部件都具有内部递减电路的图4a的流 水线处理器的串行处理器阵列的简化框图；
图6显示了根据本发明的流水线处理器的第四优选实施例的简化 框图；
图7显示了根据本发明的流水线处理器的第五优选实施例的简化 框图；
图8是供用于执行加密功能的流水线阵列处理器之用的资源高效 处理部件设计的框图；
图9是用于模乘的脉动阵列(systolic array)的框图；
图10是其输入路径被显示的单个单元的框图；
图11是DP RAM Z单元的框图；
图12是Exp RAM单元的框图；
图13是Prec RAM单元的框图；
图14是供用于执行加密功能的流水线阵列处理器之用的速度高 效处理部件设计的框图；
图15是用于模乘的脉动阵列的框图；
图16是其输入路径被显示的单一单元的框图；以及
图17是DP RAM Z单元的框图。
具体实施方式
本发明涉及供加密操作之用的并行处理器的实施过程，该实施过 程使得并行处理器在没有大大牺牲效率的情况下支持可变长度加密密 钥。
参考图1，图1显示了根据现有技术的流水线处理器1的简化框 图。处理器1包括多个处理部件，例如支持256位加密的串行阵列2。 输入/输出端口3与阵列2的第一处理部件(未显示)通信，用于从例 如也在操作中与端口3通信的客户站(client station)(未显示)接收 要被处理器1处理的数据。
为了执行加密操作，将预定长度的加密密钥提供给处理器1，并 且执行加密操作。作为替换，如果加密密钥少于预定长度，则填补加 密密钥以使加密密钥变成预定长度，然后执行操作。在任何一种情况 下，操作都花费近似相同的预定量时间。不幸的是，当密钥长度变得 更长时，用于处理以前的更短密钥的现有技术处理器1的效率降低了。 例如，被设计成可供256位密钥使用的处理器将以用于处理仅仅40 位密钥的大约六分之一“高效”时间，来处理被填补到256位的40 位密钥。这是很差的资源分配。为了更好地分配资源，一些处理器包 括多个处理器阵列，每个处理器阵列用于处理不同长度的加密密钥， 如图2所示。因而，处理器将包括40位加密处理器阵列2a，128位加 密处理器阵列2b和256位加密处理器阵列2c。输入/输出端口3分别 与每个阵列2a、2b、2c的第一处理部件通信，用于从例如也在操作中 与端口3通信的客户站(未显示)接收要被处理器4处理的数据。这 种高效实施的资源使用的效率低，因而是不合需要的。
现在参考图3a，图3a显示了根据本发明第一实施例用于以相似 的效率来处理任意密钥位长加密操作的流水线处理器5的简化框图。 流水线处理器5包括至少一个阵列，并且在图3a中显示了多个处理器 部件(处理器部件未显示)阵列6a、6b、6c，例如阵列6a和6b的每 一个都支持256位加密，而阵列6c支持512位加密。输入/输出端口3 分别与每个阵列6a、6b、6c的第一处理部件通信，用于从也在操作中 与端口3通信的客户站(未显示)接收要被流水线处理器5处理的数 据。另外，逻辑电路7与输入/输出端口3以及与末位信号导体 (conductor)9进行电通信，该导体9以曲折的形式沿着每个阵列6a、 6b、6c内的每个部件延伸。逻辑电路7用于接收指示加密密钥长度的 数据、以及取决于所述数据而通过导体9向每个阵列6a、6b、6c内的 每个部件提供信号。
现在参考图3b，图3b显示了包括处理器部件81、82、83、…、及 8n的串行阵列6a(为简明起见省略了阵列6b和6c)的简化框图。每 个处理器部件8分别通过连接11与末位信号导体9进行电通信。作为 特例，每个处理器部件是8位处理器部件，以致于串行阵列6a包括 32个单独的处理器部件以便支持256位加密。因而，处理器资源的最 有效分配需要5个单独的处理器部件来执行40位加密操作，8个单独 处理器部件来执行64位加密操作，以及16个单独处理器部件来执行 128位加密操作等等。任选地，可以使用不同于8位处理器部件的处 理器部件。
说明性地考虑特定例子，例如需要至少5个单独的8位处理器部 件来完成的40位加密操作。在使用中，客户站(未显示)通过端口3 提供要加密的数据，例如作为总计包括完整数据文件的单个数据块的 流。在第一处理周期开始时，阵列6a中的第一处理器部件81从端口3 的缓冲存储器(未显示)接收第一数据块，并对第一数据块执行预定 的第一阶段处理。在该例子中，第一阶段处理对应于利用加密密钥的 8位段的加密操作。当然，第一处理器部件81与端口3的缓冲存储器 (未显示)，以及与逻辑电路7是时间同步的，以致数据块的流被同步 地选通到第一处理器部件81。在第二处理周期开始时，第一处理器部 件81通过端口3接收第二数据块。近似同时地，第一处理器部件81 以第一数据块的形式将输出沿正向处理路径提供给第二处理器部件 82。另外，第一处理器部件81把在其中计算的第一结果沿返回处理路 径提供给端口3的缓冲存储器。这种处理数据的流水线方法继续，直 到最终结果沿返回处理路径被提供给端口3的缓冲存储器为止。
有利地，数据块的流被同步地选通到第一处理器部件81，如前面 所述的。在每个处理周期开始时，逻辑电路7使指示加密密钥长度的 数据递减预定量。在该例子中，加密密钥长度是40，需要5个处理器 部件来完成加密操作，因而指示加密密钥长度的数据代表5值。于是， 在第一处理周期开始时，逻辑电路7使值5递减1，以指示剩下4个 处理周期。在第二至第五处理周期开始时，该值进一步被递减，此时 逻辑电路7返回零值。如果指示加密数据已结束的零值产生了，则逻 辑电路7通过末位信号导体9向每个处理器部件发送末位信号。刚好 沿正向处理路径收到末位信号的处理器部件，在该情况下为第五处理 器部件，立刻“知道”它是最末处理器部件、并使数据转向，以致数 据不沿正向处理路径传播通过所述处理器部件。在最末处理器部件之 前的每一个处理器部件在末位信号被发送时，既沿正向处理路径又沿 返回处理路径接收数据，这表示不是最末部件状态。
当然，如果在特殊处理周期期间逻辑电路7的值达到非零值，则 处理正常地继续。例如，在第二处理周期期间，第一处理器部件81对 第二数据块执行相同的第一处理操作，并且第二处理器部件82对第一 数据块执行第二处理操作。在第二处理周期末尾，第一数据块沿着第 二处理器部件82与第三处理器部件83之间的正向处理路径传播。同 时，第二数据块沿着第一处理器部件81与第二处理器部件82之间的正 向处理路径传播。另外，第二处理器部件82把在其中计算的结果沿着 返回处理路径提供给第一处理器部件81。当然，同时沿着相邻处理器 部件之间的正向处理路径及返回处理路径选通数据块典型地涉及同步 定时。
利用所示的双向流水线设计，高效地计算结果而与密钥长度无关， 并且避免了附加的处理周期。用于支持不同长度密钥的处理器在设备 中的使用同时支持多个高效加密过程一每个过程都具有最大的密钥大 小。也就是说，在普通加密处理系统中，容易将统计学用于选择处理 器大小，以便在统计学上为给定的资源使用提供最佳的性能。
作为替换，末位信号导体9只与处理器部件8的子集进行电连接。 例如，在串行阵列6a中，末位信号导体9任选地连接到每第四个处理 器部件。因此利用8位处理器部件，处理器5将加密数据处理为一系 列的32位段。对于支持通过32位段处理的直到256位加密的处理器， 支持8种可能的长度。有利的是，用于将末位信号从逻辑电路7引导 至处理器部件的数据路进的数量从32减少到仅仅8个单独的数据路 径，大大方便了处理器5的制造的容易。不幸的是，对于不能被32 位除的加密密钥长度，例如在处理之前被填补到至少64位的40位加 密密钥，处理资源以较低效率被分配。因而，数据在第八个处理器部 件而不是在如上所讨论的第五个处理器部件被转向。
现在参考图4a和图4b，图4a和4b显示了根据本发明第二实施 例用于以相似的效率来处理任意密钥位长加密操作的流水线处理器 20的简化框图。在此，与先前参考图3a和图3b描述的部件相同的部 件具有相同的附图标记，并且为简洁起见省略了对它们的论述。例如 包括一系列门(gate)的开关网络21另外与输入/输出端口3电通信， 以及与一系列硬连线的(hardwired)可寻址数据路径22电通信。开 关网络21用于接收指示加密密钥长度的数据，以及用于通过一系列硬 连线的可寻址数据路径22将信号提供给确定的处理部件。在使用中， 指示加密密钥长度的数据被提供给开关网络21，以致该一系列门确定 指示最末处理部件状态的信号要发送给哪个处理器部件8。开关网络 21通过硬连线的可寻址数据路径22的选定数据路径将所述信号发送 给确定的处理部件。例如，该信号用于将确定的处理部件的位设置为 指示最末处理部件状态的值。有利地，当确定的处理部件完成数据加 密处理时，该处理部件立即使数据转向，使得数据被端口3的缓冲存 储器(未显示)读出。当然，任选地在开关网络21与处理部件的预定 子集，例如每第四个处理部件之间提供数据路径。有利的是，数据路 径的总数以及开关网络的复杂性减小了。不幸的是，对于不能被32 位除的加密密钥长度，例如在处理之前被填补到至少64位的40位加 密密钥，处理资源以较低效率被分配。
现在参考图5a和图5b，图5a和5b显示了根据本发明第三实施 例用于以相似的效率来处理任意密钥位长加密操作的流水线处理器 12的简化框图。在此，与先前参考图3a和图3b描述的部件相同的部 件具有相同的附图标记，并且为简洁起见省略了对它们的论述。根据 本发明第三实施例，每个单独处理部件14都包括专用逻辑电路15。 在使用中，指示加密密钥长度的数据连同要加密的数据一起被提供给 第一处理器部件141。第一处理器部件141对第一数据块执行预定的第 一阶段处理，并且另外使指示加密密钥长度的数据递减预定量。递减 的指示加密密钥长度的数据连同第一数据块一起被提供给第二处理器 部件142。第二处理器部件142的逻辑电路接收该递减的指示加密密钥 长度的数据，并使所述数据递减附加的预定量。如果第二处理器部件 142的逻辑电路计算零值，则第二处理器部件142的逻辑电路在第二处 理器部件142内部产生指示最末处理器部件状态的信号。近似与第二 处理器部件142完成预定的第二阶段处理同时地，第二处理器部件142 使数据转向，并且经过处理的数据被读出串行阵列13a，并被读入端 口3的缓冲存储器(未显示)。
参考图6，图6显示了根据本发明第四优选实施例的流水线处理 器16的简化框图。流水线处理器16包括多个处理器部件(未显示的 处理器部件)阵列6a、6b和6c，例如阵列6a和6b的每一个都支持 256为加密操作，而阵列6c支持512位加密操作。虚线17a和17b分 别表示用于在阵列6a的最末处理部件与阵列6b的最末处理部件之间 提供电通信的任选电耦合，以及用于在阵列6b的第一处理部件与阵列 6c的第一处理部件之间提供电通信的任选电耦合。与每个阵列6a、6b、 6c的第一处理部件通信的输入/输出端口3用于接收由也在操作中与 输入/输出端口3通信的客户站(未显示)提供的数据，该数据要被阵 列6a、6b和6c中的一个专门阵列处理。在此，提供了三个处理器， 每个处理器具有支持的最大加密密钥大小，但是其中三个处理器可任 选地被连接以形成一个1024位处理器。当然，也有可能装备任意长度 的处理器，但是这常常招致大量的寻址开销，而这是不合乎需要的。 当然，当希望最大限度的灵活性时，按照该实施例来把许多例如用于 处理64位密钥的较小处理阵列连在一起。
因为指示密钥长度的数据连同待处理的数据及加密密钥一起被提 供给处理器，因此处理器能够分配足够的处理单元给任务，并由此高 效地分配资源。所示的处理器16具有逻辑电路7，如先前参考图3a 和图3b所讨论的情况一样。因而，在该实施例中，逻辑电路计算被处 理器16处理的位数，将计数与指示加密密钥长度的数据进行比较，以 及取决于指示加密数据结束的比较，来通过最末处理器信号导体9发 送通用信号。任选地，使用用于指示最末处理器部件状态的其它系统， 例如参考本发明第二和第三实施例之一所述的系统。
现在参考图7，图7显示了根据本发明第五优选实施例的流水线 处理器18的简化框图。流水线处理器18包括多个处理器部件(未显 示的处理器部件)阵列6a、6b和6c，例如阵列6a和6b的每一个都 支持256为加密操作，而阵列6c支持512位加密操作。阵列6a的最 末处理部件与阵列6b的最末处理部件通过硬件连接19a进行电通信， 并且阵列6b的第一处理部件与阵列6c的第一处理部件通过硬件连接 19b进行电通信。与阵列6a的第一处理部件通信的输入/输出端口3 用于接收由也在操作中与输入/输出端口3通信的客户站(未显示)提 供的数据，该数据要被阵列6a、6b和6c的串行配置处理。任选地， 提供单独的输入(未显示)，以便直接将数据选通到至少除阵列6a的 第一部件之外的处理器部件。
在此，阵列6b是双向的，并且因为流水线过程被实施为双向流水 线过程，因此一旦阵列6b完成了相对于其另一个方向上发生的操作的 处理，就有可能利用阵列6b的最末部件来开始。因而，大大地提高了 效率。
因为指示密钥长度的数据连同待处理的数据及加密密钥一起被提 供给处理器，因此处理器能够分配足够的处理单元给任务、并由此高 效地分配资源。所示的处理器18具有逻辑电路7，如先前参考图3a 和图3b所讨论的情况一样。因而，在该实施例中，逻辑电路计算被处 理器18处理的位数，将计数与指示加密密钥长度的数据进行比较，以 及根据指示加密数据结束的比较，来通过最末处理器信号导体9发送 通用信号。任选地，使用用于指示最末处理器部件状态的其它系统， 例如参考本发明第二和第三实施例之一所述的系统。
图6和图7的流水线处理器16和18分别可以在以下模式下操作： 其中使被选通到阵列6a的最末处理器部件的数据可以被阵列6b的最 末处理器部件得到。例如，当某一特殊处理操作需要超过256个处理 器部件时，通过在第二个不同阵列中继续该处理操作来增加处理器阵 列的有效长度。当然，当某一特殊处理操作需要超过512个处理器部 件时，通过在第三个不同阵列中继续该处理操作来增加处理器阵列的 有效长度。例如，图6和图7中所示的流水线处理器中的任何一个都 可以操作以便执行：利用一个阵列的256位加密；利用两个不同阵列 的512位加密；以及利用所有3个不同阵列的1024位加密。
有利的是，因为知道处理器什么时候将完成处理，因此有可能指 示那个处理器进行另一个处理器的下游的处理。例如，假定处理器6a 具有用于处理256位加密操作的处理部件，并开始处理256位加密操 作。假定6b是类似的处理器。如果，有时在处理部件6a开始处理之 后并且在它被完成之前用于512位操作的处理请求到来了，则有可能 在知道当数据被传播到处理阵列6a的最末部件时那个部件将完成当 前处理中的处理工作的处理的处理部件6b上开始操作。这通过减少处 理器的停机时间同时等待其它处理器可以用来支持连起来的阵列处 理，提高了整体系统性能。
基于Montgomery的加密数据流水线处理
应用Montgomery算法，模取幂的成本被降低到一系列的超长整 数的加法。位避免乘法/加法体系结构中的进位传送，几种解决方法是 周知的。这些解决方法将Montgomery算法与冗余基数系统或余数系 统结合使用。
在S.E.Eldridge and C.D.Walter.Hardware implementation of Montgomery’s modular algorithm.IEEE Transactions on Computers， 42(6)：693-699，July 1993一文中，Montgomery模乘算法适于高效的硬 件实施。由于更简单的组合逻辑，由更高的时钟频率获得了速度的增 加。与基于Brickell算法的现有技术相比，报道了加速系数2。
在J.E.Vuillemin，P.Bertin，D.Roncin，M.Shand，H.H.Touati，and P.Boucard.Programmable active memories：Reconfigurable systems come of age.IEEE Transactions on VLSI Systems，4(1)：56-59，March 1996和 M.Shand and J.Vuillemin.Fast implementations of RSA cryptography.In Proceedings11th IEEE Symposium on Computer Arithmetic，pages 252-259，1993中报道的Research Laboratory of Digital Equipment Corp. (数字设备公司研究实验室)，使用包括中国余数定理、异步进位完成 加法器和开窗口取幂方法的几种加速方法的16个XILINX 3090 FPGA (现场可编程门阵列)的阵列用于实施模取幂。该实施过程以185kb/s 的速率计算970位RSA解密(每970位解密5.2ms)，以及以超过 300kb/s的速率计算512位RSA解密(每512位解密1.7ms)。该解决 方法的缺点是，模数的二进制表示被硬连接到逻辑表示(logic representation)中，使得必须重新为体系结构配置每个新的模数 (modulus)。
在Montgomery模乘算法中使用高基数的问题是更复杂地确定商。 该行为造成了算法流水线操作不直接进行。在H.Orup.Simplifying quotient determination in high-radix modular multiplication.In Proceedings 12th Symposium on Computer Arithmetic，pages 193-9，1995 中，算法被重写以避免在确定商的过程中涉及的任何操作。只为给定 的模数执行一次必需的预先计算。
P.A.Wang在New VLSI architectures of RSA public key crypto systems.In Proceedings of 1997 IEEE International Symposium on Circuits and Systems，volume 3，pages 2040-3，1997文章中提出了用于 Montgomery模乘算法的新VLSI体系结构。确定时钟速度的关键途径 是流水线。这是通过使算法的每次迭代交错来实现的。与先前的提议 相比，报道了系数2的时间面积乘积的改进。
J.Bajard，L.Didier，and P.Kornerup在An RNS Montgomery modular multiplication algorithm.IEEE Transactions on Computers，47(7)：766-76， July 1998文章中描述了一种使用余数系统(RNS)的新方法。在n个 相当简单的处理器商利用RNS中的n个模数来实施该算法。由此引起 的处理时间为O(n)。
当然，以上引用的参考文献的大多数都涉及几乎没有或没有灵活 性的处理器硬件实施。
也有许多用于模运算的脉动阵列体系结构的提议。这些提议在复 杂性和灵活性方面不同。
在E.F.Brickell.A survey of hardware implementations of RSA.In Advances in Cryptology-CRYPTO’89，pages 368-70.Springer-Verlag， 1990文章中，E.F.Brickell总结了1990年可得的用于执行RSA加密的 芯片。
在N.Takagi.A radix-4 modular multiplication hardware algorithm efficient for iterative modular multiplication operations.In Proceedings 10th IEEE Symposium on Computer Arithmetic，pages 35-42，1991文章 中，作者提出了一种基4(radix-4)硬件算法。冗余数被使用，并由 此避免了加法中的进位传送。与先前工作相比，报道了大约6倍的处 理加速。
更近一些，提出了这样一种方法，该方法利用预先计算的模数的 补数，并且基于J.Yong-Yin and W.P.Burleson.VLSI array algorithms and architectures for RSA modular multiplication.IEEE Transactions on VLSI Systems，5(2)：211-17，June 1997文章中的迭代Horner规则。与 Montgomery算法相比，这些方法利用中间结果的最高有效位来决定要 减去模数的哪些乘。这些解决方法的缺点是，它们或者需要大量存储 空间、或者需要许多时钟周期，来完成模乘。
最流行的模取幂算法是自乘与乘(square & multiply)算法。公开 密钥加密系统典型地基于模取幂或重复的点加法(point addition)。这 两种操作是由自乘与乘(square & multiply)算法执行的最基本形式。
方法1.1计算Z＝XE mod M，其中
1.Z＝X
2.FOR i＝n-2down to 0 DO
3.Z＝Z2 mod M
4.IF ei＝1 THEN Z＝Z·X mod M
5.END FOR
方法1.1在最坏情况下需要2(n-1)次操作，并且平均需要1.5(n-1) 次操作。为并行地计算自乘和乘法，可以使用以下型式的自乘与乘 (square & multiply)方法：
方法1.2计算p＝XE mod M，其中
1.P0＝1，Z0＝X
2.FOR i＝1to n-1DO
3.Zi+1＝Zi2mod M
4.IF ei＝1THEN Pi+1＝Pi·Zi mod M
ELSE Pi+1＝Pi
5.END FOR
方法1.2在最坏情况下需要2n次操作，并且平均需要1.5n次操作。 通过应用l-ary方法，如D.E.Knuth，The Art of Computer Programming. Volume 2：Seminumerical Algorithms.Addison-Wesley，Reading， Massachusetts，2nd edition，1981中公开的作为方法1.1的一般化的l-ary 方法，来实现加速。l-ary方法每次处理1阶位。在此的缺点是必须预 先计算并存储X的(21-2)次乘。减少到21-1次预先计算是有可能的。最 后所得的复杂性粗略地为n/1次乘法操作和n次自乘操作。
如上所示，利用Montgomery方法将模取幂简化为一系列的模乘 操作和自乘步骤。P.L.Montgomery在P.L.Montgomery.Modular multiplication without trial division.Mathematics of Computation， 44(170)：519-21，April 1985文章中提出了用于下述模乘的方法。该方 法是使两个整数相乘并以M为模、同时避免除以M的方法。其思想 是将整数变换成m余数，并计算这些m余数的乘法。最后，表示被 变换回到其正规表示。只有当计算变换域中的一系列乘法操作(例如 模取幂)时，该方法才有益。
为计算Montgomery乘法，基数R＞M，并选择gcd(M，R)＝1。除以 R优选地是计算量小的，因而如果 则最佳的选择是R＝2m。 x的m余数是xR mod M。也计算M’＝M-1 mod R。提供函数MRED(T) 来计算TR-1mod M。假定T是m余数，该函数计算T的正规表示。
方法1.3MRED(T)：计算T的Montgomery简化
T＜RM，R＝2m， gcd(M，R)＝1
1.U＝TM’mod R
2.t＝(T+UM)/R
3.IF t≥M return t-M
ELSE return t
MRED(T)的结果是t＝TR-1mod M。
现在使两个整数a和b在变换域中相乘，其中它们各自的表示是 (aR mod M)和(bR mod M)，将这两个表示的乘积提供给MRED(T)。
MRED((aR mod M)·(bR mod M))＝abR2R-1＝abR mod M
对于模取幂，依据方法1.1或1.2重复该步骤许多次，以便获得最 终结果ZRmod M或PnR mod M。将这些值之一提供给MRED(T)，以 获得Z mod M或Pn mod M。
初始变换步骤仍然需要代价高的模简化，为避免涉及除法，利用 除法计算R2mod M。只需要为给定密码系统执行一次该步骤。为获得 变换域中的a和b，执行MRED(a·R2mod M)和MRED(b·R2mod M)， 以获得aR mod M和bR mod M。显然，可以照这样变换任何变量。
对于方法1.3的硬件实施：利用m×m位乘法和2m位加法来计 算步骤2。中间结果可以具有和2m一样多的位。不是立刻计算U，而 是每次计算r基表示的一个数位。选择基数r，使得gcd(M，r)是优选的。 除以r优选地也是计算量小的，因而最佳选择是r＝2k。现在，所有变 量都以r基表示来表示。另一个改进是在算法中包括乘法A×B。
方法1.4用于计算A·B mod M的Montgomery模乘，其中
A，B＜M；M＜R＝2km；M′＝-M-1mod2k；gcd(2k，M)＝1
1.S0＝0
2.FOR i＝0to m-1DO
3.qi＝(((Si+aiB)mod 2k)M’)mod 2k
4.Si+1＝(Si+qiM+aiB)/2k
5 END FOR
6.IF Sm≥M返回Sm-M
ELSE返回Sm
应用方法1.4的结果是Sm＝ABR-1mod M。对于基数2k，需要最多 两个k×k位乘法操作和k位加法来计算步骤3。对于步骤4，需要两 个k×m位乘法操作和两个m+k位加法。与方法1.3的2m位相比，S 的最大位长被减小到m+k+2位。
方法1.5是相对于r＝2的方法1.4的简化。对于基数r＝2，对方法 1.4的步骤3中的操作执行模2。由于条件gcd(M，2k)＝1，使得模数M 为奇数。立即得出，M＝1mod 2。因此，M’＝-M-1mod 2也退化为M’＝1。
因而，任选地省略步骤3中的乘M’mod 2。
方法1.5用于计算A·B mod M的Montgomery模乘(基数r＝2)，
其中
A，B＜M；M＜R＝2m；gcd(2，M)＝1
1.S0＝0
2.FOR i＝0 to m-1DO
3.qi＝(Si+aiB)mod 2
4.Si+1＝(Si+qiM+aiB)/2
5 END FOR
6.IF Sm≥M返回Sm-M
ELSE返回Sm
方法1.5的步骤6中的最终比较和减法执行起来是高代价的，因 为m位比较是很慢的，并且在资源使用方面是高花费的。它也使算法 的流水线执行成为不可能。可以容易地验证，如果A，B＜M，则Si+1＜2M 总是保持。然而，Sm不能重新用作下一次模乘的输入A或B。如果在 am+1＝0且输入A，B＜2M的情况下来执行for循环的两次多余运行，则 满足不等式Sm+2＜2M。现在，Sm+2可以用作下一次模乘的输入B。
为进一步减小方法1.5的复杂性，使B上移一个位置，即使B乘 以2。这导致ai·B mod 2＝0，并且避免了步骤3中的加法。在Si+1的更 新期间，用(Si+qiM)/2+aiB来代替(Si+qiM+aiB)/2。该简化的成本是在 am+2＝0的情况下多运行一次循环。以下方法包括这些优化。
方法1.6用于计算A·B mod M的Montgomery模乘(基数r＝2)，
其中
A，B＜2M；M＜R＝2m+2；gcd(2，M)＝1
1.S0＝0
2.FOR i＝0to m+2DO
3.qi＝Si mod 2
4.Si+1＝(Si+qiM)/2+aiB
5 END FOR
以上算法计算Sm+3＝(2-(m+2)AB)mod M。为得到正确的结果，执行 额外的Montgomery模乘22(m+2)mod M。然而，如果如在取幂算法中 一样需要进一步的乘法操作，最好使所有的输入预先乘以系数22(m+2) mod M。因而，每个中间结果都携带系数22(m+2)。使结果与“l”进行 Montgomery相乘来消除该系数。
与“l”的最终Montgomery乘确保了最终的结果小于M。
高基数Montgomery算法
通过避免代价高的步骤6的比较和减法操作、并将条件改变为 4M＜2km且A，B＜2M，产生了相对于在硬件中实施方法1.4的某些优化。
其代价是多运行两次循环。最终所得的方法如下：
方法1.7用于计算A·B mod M的Montgomery模乘，其中
M′＝-M-1mod2k
1.S0＝0
2.FOR i＝0至m-1 DO
3.qi＝(Si+aiB)mod 2k
4.
5 END FOR
通过用B·2k代替B，进一步减小商qi确定的复杂性。因为aiB md 2k＝0，步骤3被简化为qi＝Si mod 2k。以附加的循环迭代为代价来避免 步骤3中的加法，以补偿B中的额外系数2k。为硬件实施而优化的 Montgomery方法如下所示：
方法1.8用于计算A·B mod M的Montgomery模乘，其中
M′＝-M-1mod2k
1.S0＝0
2.FOR i＝0to m-1DO
3.qi＝Si mod 2k
4.
5 END FOR
然后，使最终结果与“l”进行Montgomery相乘，以消除如上所 述的其中的系数。
在此处被引入作为参考的、Thomas Blum于1999年4月8日提交 给Faculty of the Worcester Polytechnic Institute的题为Modular Exponentiation on Reconfigurable Hardware的论题中，Thomas Blum提 出了两种不同的用于利用模乘和Montgomery空间执行加密功能的流 水线体系结构：基于方法1.6的面积高效体系结构和速度高效体系结 构。使用Xilinx XC4000系列设备作为目标设备。
一般2基脉动阵列使用m×m处理部件，其中m为模数的位数， 并且每一部件处理一位。可以同时处理2m个模乘操作，以每时钟周 期一个模乘的处理量以及2m个周期的等待时间为特色。因为对于现 代公开密钥方案中所需的典型位长、该方法导致了不实际的大CLB计 数，因此只实施一行处理部件。利用该方法，可以同时处理2个模乘 操作，而执行降低到每2m个周期2个模乘操作的处理量。等待时间 保持为2m周期。
第二考虑事项是基数r＝2k的选择。增大k将减少方法1.8中要执 行的步骤的数量。然而，这种方法需要更多的资源。主要的花费在于 2k与M和B相乘的计算。这些或者被预先计算并存储在随机存储器 (RAM)中，或者被多路复用器网络计算。无疑，对于r＝2、CLB基 数变成最小，因为不必计算或预先计算M或B的乘。
利用基数r＝2，来计算依据方法1.6的方程式。为进一步减少所需 的CLB数量，任选地采取以下措施：每个单元处理多于一位。单个加 法器用于预先计算B+M，以及执行正常处理期间的其它加法操作。并 行地计算自乘和乘法操作。该设计按等级被分为三个级别。
处理部件：计算模乘的u位。
模乘：处理部件阵列计算模乘
模取幂：将模乘操作与根据算法1.2的模取幂相结合 处理部件
图8显示了处理部件的实施过程。
在处理部件中，存在以下寄存器：
·M-Reg(u位)：存储模数
·B-Reg(u位)：存储B乘数
·B+M-Reg(u位)：存储中间结果B+M
·S-Reg(u+1位)：存储中间结果(包括进位)
·S-Reg-2(u-1位)：存储中间结果
·Control-Reg(3位)：控制多路复用器和时钟使能
·ai、qi(2位)：乘数A、商Q
·Result-Reg(u位)：存储乘法最后的结果
寄存器需要总共(6u+5)/2个CLB，加法器需要u/2+2个CLB，多 路复用器需要4·u/2个CLB，以及解码器需要2个CLB。将寄存器重 新用于组合逻辑的可能性允许CLB的某些节省。将MuxB和MuxRes 实施在B-Reg和Result-Reg的CLB中，将Mux1和Mux2部分地实施 在M-Reg和B+M-Reg中。最终所得的成本是大约每u位处理单元3u+4 个CLB。即，每位3到4个CLB，这取决于单元大小u。
在单元能够计算模乘之前，必须加载系统参数。将M存储到单元 的M-Reg中。在模乘开始时，根据多路复用器B-Mux的选择线，从 B-in或S-Reg加载操作数B。下一步是计算一次M+B，并将结果存储 在B+M-Reg中。该操作需要两个时钟周期，因为结果首先随着时钟 进入到S-Reg中。分别通过ai或控制字来控制Mux1和Mux2的选择线。
在接着的2(m+2)个周期中，根据方法1.6来计算模乘。多路复用 器Mux1根据二进制变量ai和qi的值，来选择要馈入加法器中的其输 入0、M、B、B+M之一。Mux2将先前结果S-Reg2的u-1个最高有效 位加上下一单元(除以2/右移)的最低有效结果位馈入加法器的第二 输入端。将结果存储在S-Reg中一个周期。最低有效位进入向右的单 元(除以2/右移)，而进位进入向左的单元。在该周期中，利用更新 的S-Reg2、ai、qi值在加法器中计算第二模乘。第二模乘使用相同的 操作数B，但是不同的操作数A。
在模乘的末尾，在加法器的输出端处，Sm+3在一个周期内有效。 将该值存储到Result-Reg中，如通过S-Reg馈入B-Reg中一样。在一 个周期之后将第二乘法的结果馈入Result-Reg中。
图9显示了处理部件怎样连接到用于计算m位模乘的阵列。为执 行相对于m的方法，使用每单元处理u位的m/u+1个单元。Unit0只 有u-1个B输入，因为B0被加到移位值Si+qiM上。根据Montgomery 算法的特性，结果位S-Reg0总是为0。Unitm/u处理B的最高有效位以 及中间结果Si+1的临时溢出。没有到该单元的M输入。
单元的输入和输出以以下方式相互连接。控制字、qi和ai被从右 向左泵送(bumped)通过单元。结果从左向右泵送。carry-out(载出) 信号被馈给向右的carry-in(载入)输入。输出S_0_Out总是连接到向 右的单元的输入S_0_In。这代表方程式除以2。
首先将模数M馈入单元中。为允许信号有足够的时间传播到所有 单元，M在两个时钟周期内有效。我们使用两个M-Bus，M-even-Bus 连接到所有的偶数单元、M-odd-Bus连接到所有的奇数单元，该方法 允许每时钟周期将u位馈给单元。因而，需要m/u个周期来加载完整 模数M。
类似地加载操作数B。信号也在两个时钟周期内有效。在加载操 作数B之后，方法1.6的步骤的执行就开始了。
从最右边的单元unit0开始，将控制字、ai和qi馈入它们的寄存器 中。加法器根据ai和qi、在一个时钟周期内计算S-Reg-2加上B、M 或B+M。读回结果的最低有效位作为下一次计算的qi+1。将所得到的 进位位、控制字、ai和qi泵入向左的单元中，其中在下一个时钟周期 中发生相同的计算。
以这种脉动的形式，将控制字、ai、qi和进位位从右向左泵送通过 整个单元阵列。方法1.6中的除以2也导致了右移操作。单元的加法 (S0)的最低有效位总是被反馈到向右的单元中。在完成模乘之后， 将结果从左向右泵送通过单元、并连续地存储在RAM中用于进一步 处理。
单个处理部件计算Si+1＝(Si+qi·M)/2+ai·B的u位。在时钟周期i中， unit0计算Si的位0…u。在时钟周期i+1中，unit1使用所得的进位、并 计算Si的位u…2u。unit0在时钟周期i+2中、利用Si(S0)的右移(除以 2)位u来计算Si+1的位0…u-1。在单元unit0中时钟周期i+1是非生 产性的、同时等待unit1的结果。通过依据方法1.2并行地计算自乘和 乘法操作，来避免这种低效率。pi+1和zi+1都取决于zi。因此，将中间 结果zi存储在B-Register中，并将zi和pi一起馈入单元的ai输入中用 于自乘和乘法。
图10显示了单元阵列怎样用于模取幂。在设计的核心是具有以下 17种状态的有限状态机(FSM)：空闲状态，用于加载系统参数的4 种状态，以及用于计算模取幂的4×3种状态。实际的模取幂是在预先 计算1、预先计算2、计算和计算后4种主要状态下执行的。这些主要 状态的每一种都细分为3种子状态：load-B、B+M和计算乘法。根据 状态来对馈入control-in的控制字编码。以二分之一时钟频率对FSM 计时。同样对加载和读取RAM和DP RAM元件也成立。该措施确保 最大传播时间是在单元中。因而，最小时钟周期时间和最终所得的模 取幂的速度与单元中的有效计算时间有关，而与计算开销无关。
在计算模取幂之前，加载系统参数。从I/O将模数M的2u位读 入M-Reg中。从低数位开始向高数位读。从M-Reg将M的u位交替 地馈给M-even-Bus和M-odd-Bus。每次信号在两个周期内有效。当时， 从I/O读取指数E的16位、并存储到Exp-RAM中。来自I/O的最初 16位宽的字指定了指数的位长。直到64个后面的字包含了实际的指 数。当时，从I/O读出预先计算系数22(m+2)mod M的2u位。将该2u 位存储到Prec-RAM中。
在预先计算1状态下，我们从I/O读取X值，每个时钟周期u位， 并将它存储到DP RAM Z中。同时，从Prec-RAM读出预先计算系数 22(m+2)mod M、并且每时钟周期将u位交替地通过B-even-Bus和 B-odd-Bus馈给单元的B-Register。在接下来的两个时钟周期中，在单 元中计算B+M。
用于方法1.2的初值是可得的。两个值都必须乘以2，这可以被并 行地执行，因为两个乘法操作都使用已经存储在B中的公共操作数 22(m+2)modM。时分复用(TDM)单元从DP RAM Z读出X，并将X 与1复用。在2(m+3)个时钟周期之后，结果的低数位出现在Result-Out， 并被存储在DP RAM Z中。在一个周期之后，下一个结果的低数位出 现在Result-Out，并被存储在DP RAM P中。该过程重复2m个周期， 直到两个结果的所有数位都被存储在DP RAM Z和DP RAM P中为 止。结果X·2m+2mod M也被存储在单元的B-Register中。
在预先计算2状态下，方法1.2的实际步骤开始。对于Z1和P1 两者的计算，都将Z0用作操作数。该值被存储在B-Register中。第二 操作数Z0或P0分别从DP RAM Z和DP RAM P被读出，并作为ai、 通过TDM被“泵”入单元中。在另外的2(m+3)个时钟周期之后，Z1 和P1的结果的低数位出现在Result-Out。Z1被存储在DP RAM Z中。 只有当指数e0的第一位等于“1”时，才需要P1。取决于e0，P1被 存储在DP RAM P中、或者被丢弃。
在计算状态下，方法1.2的循环被执行n-1次。在每个周期之后 DP RAM Z中的Zi都被更新，并作为ai被“泵”回到单元中。只有当 指数ei的相关位等于“1”时，才更新DP RAM P中的Pi。这样，总 是最后存储的P被“泵”回到单元中。
在en-1的处理之后，FSM进入计算后状态。为了从结果Pn消除系 数2m+2，计算最终的Montgomery乘1。首先交替地通过B-even-Bus 和B-odd-Bus、将向量0，0，…0，1馈入单元的B-Register中。从DP RAM P将Pn作为ai泵入单元中。在执行计算后状态之后，结果Pn＝XE mod M的u位在I/O端口处有效。每两个时钟周期另外的u位出现在I/O 处。现在可以立即重新进入预先计算1状态，以计算另一X值。
在2(n+2)(m+4)个时钟周期内计算完整的模乘。那是从把X的最 初u位插入设备中，直到最初的u个结果位出现在输出处为止的延迟。 在那一点上，另一个X值可以进入设备中。在附加的m/u个时钟周期 的等待时间之后，最后的u位出现在输出总线上。
以下，说明图10中的功能块。图11显示了DP RAM Z的设计。 m/u×u位DP RAM在该单元的核心。它具有分开的写(A)和读 (DPRA)地址输入。计数直到m/u的写计数器计算写地址(A)。当 Zi的最初u位出现在data-in时，写计数器在B-load子状态下开始计数 (时钟使能)。同时，DP RAM的使能信号有效，并且数据被存储在 DP RAM中。当达到m/u时，终端计数(terminal-count)使DP RAM的 计数使能和写使能复位。在计算子状态下，读计数器被允许操作。当 读计数器达到其上限m+2时，终端计数(terminal-count)触发FSM 转换为子状态B-load。读计数器值(q-out)的log2(m/u)最高有效位对 DP RAM的DPRA寻址。每u个周期读出DP RAM中存储的另一个 值。当q-out的log2(u)最低有效位达到0时，将该值加载到移位寄存 器中。在接下来的u个周期，u位逐位地出现在移位寄存器的串行输 出处。Zi的最后值被存储在u位寄存器中。该办法允许我们选择m/u ×u位DP RAM，而不是2m/u×u位DP RAM(m＝2x，x＝8，9，10)。
DP RAM P几乎以同样的方式工作。它具有附加的输入ei，在ei＝1 的情况下，ei激活DP RAM的写使能信号。
图12显示了Exp RAM的设计。在加载指数状态(load-exponent state)的第一周期中，从I/O读出第一个字，并存储到10位寄存器中。 它的值指定了指数的位长。在后续的周期中，每次读出指数的16位、 并存储在RAM中。通过6位写计数器来计算存储地址。在每一个计 算状态开始时，10位读计数器都被允许操作。它的6个最高有效位计 算存储器地址。因而，每第16次激活，就从RAM读出新的值。在读 计数器的4个最低有效位等于0的同时，将该值存储在16位移位寄存 器中。当读计数器达到10位寄存器中指定的值时，终端计数 (terminal-count)信号触发FSM进入计算后状态。
图13显示了Prec RAM的设计。在加载预先系数状态下，当时从 I/O读出预先计算系数的2u位、并存储在RAM中。计数直到m/2u 的计数器对RAM寻址。当所有的m/2u个值都被读出时，终端计数 (terminal-count)信号触发FSM离开加载预先系数状态。
在预先计算1状态下，从RAM读出预先计算系数，并馈给单元 的B-Register。每个时钟周期都递增计数器，并将2u位加载到2u位 寄存器中。每个时钟周期的正沿从那里将u位馈在B-even-Bus上。在 负时钟边沿，将u位馈在B-odd-Bus上。
速度高效体系结构
以上设计是在资源使用方面进行优化的。利用基数r＝2k，k＞1， 将使方法1.6中的步骤数量减少k倍。方法1.8的计算倍执行m+3次 (i＝0至m+2)。
很容易按等级将速度高效设计分为3个级别。
处理部件：计算模乘的4位
模乘：处理部件阵列计算模乘
模取幂：将模乘操作与根据方法1.2的模取幂相结合
图14显示了处理部件的实施。
提供了以下元件：
·B-Reg(4位)：存储B乘数
·B-Adder-Reg(5位)：存储B的倍数
·S-Reg(4位)：存储中间结果Si
·Control-Reg(3位)：控制多路复用器和时钟使能
·ai-Reg(4位)：乘数A
·qi-Reg(4位)：商Q
·Result-Reg(4位)：存储在乘法末尾的结果
·B-Adder(4位)：将B加到先前计算的B的倍数上
·B+M~-Adder(4位)：将M~的乘加到B的倍数上
·S+B+M~-Adder(5位)：将M~Si加到B+M~-Adder上
·B-RAM(16×4位)：存储B的16倍数
·M~-RAM(16×4位)：存储M~的16倍数
从以上参考的T.Blum的论题，以及从图的回顾，单元的操作是显 然的。
图15显示了处理部件怎样连接到用于计算全尺寸模乘的阵列。
图16显示了单元阵列怎样用于模取幂。
图17显示了DP RAM Z的设计。m×4位DP RAM位于该单元的 核心。它具有分开的写(A)和读(DPRA)地址输入。计数直到m+2 的两个计数器计算这些地址。当Zi的第一数位出现在data-in时，写 计数器在B-load子状态下开始计数(时钟使能)。同时，DP RAM的 使能信号有效，并且数据被存储在DP RAM中。当达到m+2时，写 计数器的终端计数(terminal-count)信号使两个使能信号复位。在计 算子状态下读计数器被允许操作。DP RAM的数据被读计数器的q-out 寻址、并立即出现在DPO处。当读计数器达到m+2时，终端计数 (terminal-count)触发FSM转变为B-load子状态。最后两个zi值的 每一个都被存储在4位寄存器中。
该办法允许我们选择100％利用的m×4位DP RAM，而不是仅仅 50％利用的2m×4位DP RAM。DP RAM P几乎以同样的方式工作。 它具有附加的输入ei，在ei＝“1”的情况下，ei激活DP RAM的写使 能信号。
因为以上的流水线处理器体系结构体现了许多流水线处理部件， 所以常常难以、并且代价高地在同一集成电路内使每个部件与时钟脉 冲源同步。因此，本发明的极其有利之处在于，通过简化时钟分配问 题来减少总的资源需求。而且，因为在一个方向上需要加法，而在另 一个方向上需要乘法，所以显然沿一条路径所需的时间比沿另一条路 径所需的时间多，因此根据本发明的实施例，路径的时间平均是有可 能的。
在不背离本发明的精神和范围的情况下，可以设想大量的其它实 施例。
参考图1，图1显示了根据现有技术的流水线处理器1的简化框 图。处理器1包括多个处理部件，例如支持256位加密的串行阵列2。 输入/输出端口3与阵列2的第一处理部件(未显示)通信，用于从例 如也在操作中与端口3通信的客户站(client station)(未显示)接收 要被处理器1处理的数据。
为了执行加密操作，将预定长度的加密密钥提供给处理器1，并 且执行加密操作。作为替换，如果加密密钥少于预定长度，则填补加 密密钥以使加密密钥变成预定长度，然后执行操作。在任何一种情况 下，操作都花费近似相同的预定量时间。不幸的是，当密钥长度变得 更长时，用于处理以前的更短密钥的现有技术处理器1的效率降低了。 例如，被设计成可供256位密钥使用的处理器将以用于处理仅仅40 位密钥的大约六分之一“高效”时间，来处理被填补到256位的40 位密钥。这是很差的资源分配。为了更好地分配资源，一些处理器包 括多个处理器阵列，每个处理器阵列用于处理不同长度的加密密钥， 如图2所示。因而，处理器将包括40位加密处理器阵列2a，128位加 密处理器阵列2b和256位加密处理器阵列2c。输入/输出端口3分别 与每个阵列2a、2b、2c的第一处理部件通信，用于从例如也在操作中 与端口3通信的客户站(未显示)接收要被处理器4处理的数据。这 种高效实施的资源使用的效率低，因而是不合需要的。
现在参考图3a，图3a显示了根据本发明第一实施例用于以相似 的效率来处理任意密钥位长加密操作的流水线处理器5的简化框图。 流水线处理器5包括至少一个阵列，并且在图3a中显示了多个处理器 部件(处理器部件未显示)阵列6a、6b、6c，例如阵列6a和6b的每 一个都支持256位加密，而阵列6c支持512位加密。输入/输出端口3 分别与每个阵列6a、6b、6c的第一处理部件通信，用于从也在操作中 与端口3通信的客户站(未显示)接收要被流水线处理器5处理的数 据。另外，逻辑电路7与输入/输出端口3以及与末位信号导体 (conductor)9进行电通信，该导体9以曲折的形式沿着每个阵列6a、 6b、6c内的每个部件延伸。逻辑电路7用于接收指示加密密钥长度的 数据、以及取决于所述数据而通过导体9向每个阵列6a、6b、6c内的 每个部件提供信号。
现在参考图3b，图3b显示了包括处理器部件81、82、83、…、及 8n的串行阵列6a(为简明起见省略了阵列6b和6c)的简化框图。每 个处理器部件8分别通过连接11与末位信号导体9进行电通信。作为 特例，每个处理器部件是8位处理器部件，以致于串行阵列6a包括 32个单独的处理器部件以便支持256位加密。因而，处理器资源的最 有效分配需要5个单独的处理器部件来执行40位加密操作，8个单独 处理器部件来执行64位加密操作，以及16个单独处理器部件来执行 128位加密操作等等。任选地，可以使用不同于8位处理器部件的处 理器部件。
说明性地考虑特定例子，例如需要至少5个单独的8位处理器部 件来完成的40位加密操作。在使用中，客户站(未显示)通过端口3 提供要加密的数据，例如作为总计包括完整数据文件的单个数据块的 流。在第一处理周期开始时，阵列6a中的第一处理器部件81从端口3 的缓冲存储器(未显示)接收第一数据块，并对第一数据块执行预定 的第一阶段处理。在该例子中，第一阶段处理对应于利用加密密钥的 8位段的加密操作。当然，第一处理器部件81与端口3的缓冲存储器 (未显示)，以及与逻辑电路7是时间同步的，以致数据块的流被同步 地选通到第一处理器部件81。在第二处理周期开始时，第一处理器部 件81通过端口3接收第二数据块。近似同时地，第一处理器部件81 以第一数据块的形式将输出沿正向处理路径提供给第二处理器部件 82。另外，第一处理器部件81把在其中计算的第一结果沿返回处理路 径提供给端口3的缓冲存储器。这种处理数据的流水线方法继续，直 到最终结果沿返回处理路径被提供给端口3的缓冲存储器为止。
有利地，数据块的流被同步地选通到第一处理器部件81，如前面 所述的。在每个处理周期开始时，逻辑电路7使指示加密密钥长度的 数据递减预定量。在该例子中，加密密钥长度是40，需要5个处理器 部件来完成加密操作，因而指示加密密钥长度的数据代表5值。于是， 在第一处理周期开始时，逻辑电路7使值5递减1，以指示剩下4个 处理周期。在第二至第五处理周期开始时，该值进一步被递减，此时 逻辑电路7返回零值。如果指示加密数据已结束的零值产生了，则逻 辑电路7通过末位信号导体9向每个处理器部件发送末位信号。刚好 沿正向处理路径收到末位信号的处理器部件，在该情况下为第五处理 器部件，立刻“知道”它是最末处理器部件、并使数据转向，以致数 据不沿正向处理路径传播通过所述处理器部件。在最末处理器部件之 前的每一个处理器部件在末位信号被发送时，既沿正向处理路径又沿 返回处理路径接收数据，这表示不是最末部件状态。
当然，如果在特殊处理周期期间逻辑电路7的值达到非零值，则 处理正常地继续。例如，在第二处理周期期间，第一处理器部件81对 第二数据块执行相同的第一处理操作，并且第二处理器部件82对第一 数据块执行第二处理操作。在第二处理周期末尾，第一数据块沿着第 二处理器部件82与第三处理器部件83之间的正向处理路径传播。同 时，第二数据块沿着第一处理器部件81与第二处理器部件82之间的正 向处理路径传播。另外，第二处理器部件82把在其中计算的结果沿着 返回处理路径提供给第一处理器部件81。当然，同时沿着相邻处理器 部件之间的正向处理路径及返回处理路径选通数据块典型地涉及同步 定时。
利用所示的双向流水线设计，高效地计算结果而与密钥长度无关， 并且避免了附加的处理周期。用于支持不同长度密钥的处理器在设备 中的使用同时支持多个高效加密过程一每个过程都具有最大的密钥大 小。也就是说，在普通加密处理系统中，容易将统计学用于选择处理 器大小，以便在统计学上为给定的资源使用提供最佳的性能。
作为替换，末位信号导体9只与处理器部件8的子集进行电连接。 例如，在串行阵列6a中，末位信号导体9任选地连接到每第四个处理 器部件。因此利用8位处理器部件，处理器5将加密数据处理为一系 列的32位段。对于支持通过32位段处理的直到256位加密的处理器， 支持8种可能的长度。有利的是，用于将末位信号从逻辑电路7引导 至处理器部件的数据路进的数量从32减少到仅仅8个单独的数据路 径，大大方便了处理器5的制造的容易。不幸的是，对于不能被32 位除的加密密钥长度，例如在处理之前被填补到至少64位的40位加 密密钥，处理资源以较低效率被分配。因而，数据在第八个处理器部 件而不是在如上所讨论的第五个处理器部件被转向。
现在参考图4a和图4b，图4a和4b显示了根据本发明第二实施 例用于以相似的效率来处理任意密钥位长加密操作的流水线处理器 20的简化框图。在此，与先前参考图3a和图3b描述的部件相同的部 件具有相同的附图标记，并且为简洁起见省略了对它们的论述。例如 包括一系列门(gate)的开关网络21另外与输入/输出端口3电通信， 以及与一系列硬连线的(hardwired)可寻址数据路径22电通信。开 关网络21用于接收指示加密密钥长度的数据，以及用于通过一系列硬 连线的可寻址数据路径22将信号提供给确定的处理部件。在使用中， 指示加密密钥长度的数据被提供给开关网络21，以致该一系列门确定 指示最末处理部件状态的信号要发送给哪个处理器部件8。开关网络 21通过硬连线的可寻址数据路径22的选定数据路径将所述信号发送 给确定的处理部件。例如，该信号用于将确定的处理部件的位设置为 指示最末处理部件状态的值。有利地，当确定的处理部件完成数据加 密处理时，该处理部件立即使数据转向，使得数据被端口3的缓冲存 储器(未显示)读出。当然，任选地在开关网络21与处理部件的预定 子集，例如每第四个处理部件之间提供数据路径。有利的是，数据路 径的总数以及开关网络的复杂性减小了。不幸的是，对于不能被32 位除的加密密钥长度，例如在处理之前被填补到至少64位的40位加 密密钥，处理资源以较低效率被分配。
现在参考图5a和图5b，图5a和5b显示了根据本发明第三实施 例用于以相似的效率来处理任意密钥位长加密操作的流水线处理器 12的简化框图。在此，与先前参考图3a和图3b描述的部件相同的部 件具有相同的附图标记，并且为简洁起见省略了对它们的论述。根据 本发明第三实施例，每个单独处理部件14都包括专用逻辑电路15。 在使用中，指示加密密钥长度的数据连同要加密的数据一起被提供给 第一处理器部件141。第一处理器部件141对第一数据块执行预定的第 一阶段处理，并且另外使指示加密密钥长度的数据递减预定量。递减 的指示加密密钥长度的数据连同第一数据块一起被提供给第二处理器 部件142。第二处理器部件142的逻辑电路接收该递减的指示加密密钥 长度的数据，并使所述数据递减附加的预定量。如果第二处理器部件 142的逻辑电路计算零值，则第二处理器部件142的逻辑电路在第二处 理器部件142内部产生指示最末处理器部件状态的信号。近似与第二 处理器部件142完成预定的第二阶段处理同时地，第二处理器部件142 使数据转向，并且经过处理的数据被读出串行阵列13a，并被读入端 口3的缓冲存储器(未显示)。
参考图6，图6显示了根据本发明第四优选实施例的流水线处理 器16的简化框图。流水线处理器16包括多个处理器部件(未显示的 处理器部件)阵列6a、6b和6c，例如阵列6a和6b的每一个都支持 256为加密操作，而阵列6c支持512位加密操作。虚线17a和17b分 别表示用于在阵列6a的最末处理部件与阵列6b的最末处理部件之间 提供电通信的任选电耦合，以及用于在阵列6b的第一处理部件与阵列 6c的第一处理部件之间提供电通信的任选电耦合。与每个阵列6a、6b、 6c的第一处理部件通信的输入/输出端口3用于接收由也在操作中与 输入/输出端口3通信的客户站(未显示)提供的数据，该数据要被阵 列6a、6b和6c中的一个专门阵列处理。在此，提供了三个处理器， 每个处理器具有支持的最大加密密钥大小，但是其中三个处理器可任 选地被连接以形成一个1024位处理器。当然，也有可能装备任意长度 的处理器，但是这常常招致大量的寻址开销，而这是不合乎需要的。 当然，当希望最大限度的灵活性时，按照该实施例来把许多例如用于 处理64位密钥的较小处理阵列连在一起。
因为指示密钥长度的数据连同待处理的数据及加密密钥一起被提 供给处理器，因此处理器能够分配足够的处理单元给任务，并由此高 效地分配资源。所示的处理器16具有逻辑电路7，如先前参考图3a 和图3b所讨论的情况一样。因而，在该实施例中，逻辑电路计算被处 理器16处理的位数，将计数与指示加密密钥长度的数据进行比较，以 及取决于指示加密数据结束的比较，来通过最末处理器信号导体9发 送通用信号。任选地，使用用于指示最末处理器部件状态的其它系统， 例如参考本发明第二和第三实施例之一所述的系统。
现在参考图7，图7显示了根据本发明第五优选实施例的流水线 处理器18的简化框图。流水线处理器18包括多个处理器部件(未显 示的处理器部件)阵列6a、6b和6c，例如阵列6a和6b的每一个都 支持256为加密操作，而阵列6c支持512位加密操作。阵列6a的最 末处理部件与阵列6b的最末处理部件通过硬件连接19a进行电通信， 并且阵列6b的第一处理部件与阵列6c的第一处理部件通过硬件连接 19b进行电通信。与阵列6a的第一处理部件通信的输入/输出端口3 用于接收由也在操作中与输入/输出端口3通信的客户站(未显示)提 供的数据，该数据要被阵列6a、6b和6c的串行配置处理。任选地， 提供单独的输入(未显示)，以便直接将数据选通到至少除阵列6a的 第一部件之外的处理器部件。
在此，阵列6b是双向的，并且因为流水线过程被实施为双向流水 线过程，因此一旦阵列6b完成了相对于其另一个方向上发生的操作的 处理，就有可能利用阵列6b的最末部件来开始。因而，大大地提高了 效率。
因为指示密钥长度的数据连同待处理的数据及加密密钥一起被提 供给处理器，因此处理器能够分配足够的处理单元给任务、并由此高 效地分配资源。所示的处理器18具有逻辑电路7，如先前参考图3a 和图3b所讨论的情况一样。因而，在该实施例中，逻辑电路计算被处 理器18处理的位数，将计数与指示加密密钥长度的数据进行比较，以 及根据指示加密数据结束的比较，来通过最末处理器信号导体9发送 通用信号。任选地，使用用于指示最末处理器部件状态的其它系统， 例如参考本发明第二和第三实施例之一所述的系统。
图6和图7的流水线处理器16和18分别可以在以下模式下操作： 其中使被选通到阵列6a的最末处理器部件的数据可以被阵列6b的最 末处理器部件得到。例如，当某一特殊处理操作需要超过256个处理 器部件时，通过在第二个不同阵列中继续该处理操作来增加处理器阵 列的有效长度。当然，当某一特殊处理操作需要超过512个处理器部 件时，通过在第三个不同阵列中继续该处理操作来增加处理器阵列的 有效长度。例如，图6和图7中所示的流水线处理器中的任何一个都 可以操作以便执行：利用一个阵列的256位加密；利用两个不同阵列 的512位加密；以及利用所有3个不同阵列的1024位加密。
有利的是，因为知道处理器什么时候将完成处理，因此有可能指 示那个处理器进行另一个处理器的下游的处理。例如，假定处理器6a 具有用于处理256位加密操作的处理部件，并开始处理256位加密操 作。假定6b是类似的处理器。如果，有时在处理部件6a开始处理之 后并且在它被完成之前用于512位操作的处理请求到来了，则有可能 在知道当数据被传播到处理阵列6a的最末部件时那个部件将完成当 前处理中的处理工作的处理的处理部件6b上开始操作。这通过减少处 理器的停机时间同时等待其它处理器可以用来支持连起来的阵列处 理，提高了整体系统性能。
基于Montgomery的加密数据流水线处理
应用Montgomery算法，模取幂的成本被降低到一系列的超长整 数的加法。位避免乘法/加法体系结构中的进位传送，几种解决方法是 周知的。这些解决方法将Montgomery算法与冗余基数系统或余数系 统结合使用。
在S.E.Eldridge and C.D.Walter.Hardware implementation of Montgomery’s modular algorithm.IEEE Transactions on Computers， 42(6)：693-699，July 1993一文中，Montgomery模乘算法适于高效的硬 件实施。由于更简单的组合逻辑，由更高的时钟频率获得了速度的增 加。与基于Brickell算法的现有技术相比，报道了加速系数2。
在J.E.Vuillemin，P.Bertin，D.Roncin，M.Shand，H.H.Touati，and P.Boucard.Programmable active memories：Reconfigurable systems come of age.IEEE Transactions on VLSI Systems，4(1)：56-59，March 1996和 M.Shand and J.Vuillemin.Fast implementations of RSA cryptography.In Proceedings11th IEEE Symposium on Computer Arithmetic，pages 252-259，1993中报道的Research Laboratory of Digital Equipment Corp. (数字设备公司研究实验室)，使用包括中国余数定理、异步进位完成 加法器和开窗口取幂方法的几种加速方法的16个XILINX 3090 FPGA (现场可编程门阵列)的阵列用于实施模取幂。该实施过程以185kb/s 的速率计算970位RSA解密(每970位解密5.2ms)，以及以超过 300kb/s的速率计算512位RSA解密(每512位解密1.7ms)。该解决 方法的缺点是，模数的二进制表示被硬连接到逻辑表示(logic representation)中，使得必须重新为体系结构配置每个新的模数 (modulus)。
在Montgomery模乘算法中使用高基数的问题是更复杂地确定商。 该行为造成了算法流水线操作不直接进行。在H.Orup.Simplifying quotient determination in high-radix modular multiplication.In Proceedings 12th Symposium on Computer Arithmetic，pages 193-9，1995 中，算法被重写以避免在确定商的过程中涉及的任何操作。只为给定 的模数执行一次必需的预先计算。
P.A.Wang在New VLSI architectures of RSA public key crypto systems.In Proceedings of 1997 IEEE International Symposium on Circuits and Systems，volume 3，pages 2040-3，1997文章中提出了用于 Montgomery模乘算法的新VLSI体系结构。确定时钟速度的关键途径 是流水线。这是通过使算法的每次迭代交错来实现的。与先前的提议 相比，报道了系数2的时间面积乘积的改进。
J.Bajard，L.Didier，and P.Kornerup在An RNS Montgomery modular multiplication algorithm.IEEE Transactions on Computers，47(7)：766-76， July 1998文章中描述了一种使用余数系统(RNS)的新方法。在n个 相当简单的处理器商利用RNS中的n个模数来实施该算法。由此引起 的处理时间为O(n)。
当然，以上引用的参考文献的大多数都涉及几乎没有或没有灵活 性的处理器硬件实施。
也有许多用于模运算的脉动阵列体系结构的提议。这些提议在复 杂性和灵活性方面不同。
在E.F.Brickell.A survey of hardware implementations of RSA.In Advances in Cryptology-CRYPTO’89，pages 368-70.Springer-Verlag， 1990文章中，E.F.Brickell总结了1990年可得的用于执行RSA加密的 芯片。
在N.Takagi.A radix-4 modular multiplication hardware algorithm efficient for iterative modular multiplication operations.In Proceedings 10th IEEE Symposium on Computer Arithmetic，pages 35-42，1991文章 中，作者提出了一种基4(radix-4)硬件算法。冗余数被使用，并由 此避免了加法中的进位传送。与先前工作相比，报道了大约6倍的处 理加速。
更近一些，提出了这样一种方法，该方法利用预先计算的模数的 补数，并且基于J.Yong-Yin and W.P.Burleson.VLSI array algorithms and architectures for RSA modular multiplication.IEEE Transactions on VLSI Systems，5(2)：211-17，June 1997文章中的迭代Horner规则。与 Montgomery算法相比，这些方法利用中间结果的最高有效位来决定要 减去模数的哪些乘。这些解决方法的缺点是，它们或者需要大量存储 空间、或者需要许多时钟周期，来完成模乘。
最流行的模取幂算法是自乘与乘(square & multiply)算法。公开 密钥加密系统典型地基于模取幂或重复的点加法(point addition)。这 两种操作是由自乘与乘(square & multiply)算法执行的最基本形式。
方法1.1计算Z＝XE mod M，其中
1.Z＝X
2.FOR i＝n-2down to 0 DO
3.Z＝Z2 mod M
4.IF ei＝1 THEN Z＝Z·X mod M
5.END FOR
方法1.1在最坏情况下需要2(n-1)次操作，并且平均需要1.5(n-1) 次操作。为并行地计算自乘和乘法，可以使用以下型式的自乘与乘 (square & multiply)方法：
方法1.2计算p＝XE mod M，其中
1.P0＝1，Z0＝X
2.FOR i＝1to n-1DO
3.Zi+1＝Zi2mod M
4.IF ei＝1THEN Pi+1＝Pi·Zi mod M
ELSE Pi+1＝Pi
5.END FOR
方法1.2在最坏情况下需要2n次操作，并且平均需要1.5n次操作。 通过应用l-ary方法，如D.E.Knuth，The Art of Computer Programming. Volume 2：Seminumerical Algorithms.Addison-Wesley，Reading， Massachusetts，2nd edition，1981中公开的作为方法1.1的一般化的l-ary 方法，来实现加速。l-ary方法每次处理1阶位。在此的缺点是必须预 先计算并存储X的(21-2)次乘。减少到21-1次预先计算是有可能的。最 后所得的复杂性粗略地为n/1次乘法操作和n次自乘操作。
如上所示，利用Montgomery方法将模取幂简化为一系列的模乘 操作和自乘步骤。P.L.Montgomery在P.L.Montgomery.Modular multiplication without trial division.Mathematics of Computation， 44(170)：519-21，April 1985文章中提出了用于下述模乘的方法。该方 法是使两个整数相乘并以M为模、同时避免除以M的方法。其思想 是将整数变换成m余数，并计算这些m余数的乘法。最后，表示被 变换回到其正规表示。只有当计算变换域中的一系列乘法操作(例如 模取幂)时，该方法才有益。
为计算Montgomery乘法，基数R＞M，并选择gcd(M，R)＝1。除以 R优选地是计算量小的，因而如果 则最佳的选择是R＝2m。 x的m余数是xR mod M。也计算M’＝M-1 mod R。提供函数MRED(T) 来计算TR-1mod M。假定T是m余数，该函数计算T的正规表示。
方法1.3MRED(T)：计算T的Montgomery简化
T＜RM，R＝2m， gcd(M，R)＝1
1.U＝TM’mod R
2.t＝(T+UM)/R
3.IF t≥M return t-M
ELSE return t
MRED(T)的结果是t＝TR-1mod M。
现在使两个整数a和b在变换域中相乘，其中它们各自的表示是 (aR mod M)和(bR mod M)，将这两个表示的乘积提供给MRED(T)。
MRED((aR mod M)·(bR mod M))＝abR2R-1＝abR mod M
对于模取幂，依据方法1.1或1.2重复该步骤许多次，以便获得最 终结果ZRmod M或PnR mod M。将这些值之一提供给MRED(T)，以 获得Z mod M或Pn mod M。
初始变换步骤仍然需要代价高的模简化，为避免涉及除法，利用 除法计算R2mod M。只需要为给定密码系统执行一次该步骤。为获得 变换域中的a和b，执行MRED(a·R2mod M)和MRED(b·R2mod M)， 以获得aR mod M和bR mod M。显然，可以照这样变换任何变量。
对于方法1.3的硬件实施：利用m×m位乘法和2m位加法来计 算步骤2。中间结果可以具有和2m一样多的位。不是立刻计算U，而 是每次计算r基表示的一个数位。选择基数r，使得gcd(M，r)是优选的。 除以r优选地也是计算量小的，因而最佳选择是r＝2k。现在，所有变 量都以r基表示来表示。另一个改进是在算法中包括乘法A×B。
方法1.4用于计算A·B mod M的Montgomery模乘，其中
A，B＜M；M＜R＝2km；M′＝-M-1mod2k；gcd(2k，M)＝1
1.S0＝0
2.FOR i＝0to m-1DO
3.qi＝(((Si+aiB)mod 2k)M’)mod 2k
4.Si+1＝(Si+qiM+aiB)/2k
5 END FOR
6.IF Sm≥M返回Sm-M
ELSE返回Sm
应用方法1.4的结果是Sm＝ABR-1mod M。对于基数2k，需要最多 两个k×k位乘法操作和k位加法来计算步骤3。对于步骤4，需要两 个k×m位乘法操作和两个m+k位加法。与方法1.3的2m位相比，S 的最大位长被减小到m+k+2位。
方法1.5是相对于r＝2的方法1.4的简化。对于基数r＝2，对方法 1.4的步骤3中的操作执行模2。由于条件gcd(M，2k)＝1，使得模数M 为奇数。立即得出，M＝1mod 2。因此，M’＝-M-1mod 2也退化为M’＝1。
因而，任选地省略步骤3中的乘M’mod 2。
方法1.5用于计算A·B mod M的Montgomery模乘(基数r＝2)，
其中
A，B＜M；M＜R＝2m；gcd(2，M)＝1
1.S0＝0
2.FOR i＝0 to m-1DO
3.qi＝(Si+aiB)mod 2
4.Si+1＝(Si+qiM+aiB)/2
5 END FOR
6.IF Sm≥M返回Sm-M
ELSE返回Sm
方法1.5的步骤6中的最终比较和减法执行起来是高代价的，因 为m位比较是很慢的，并且在资源使用方面是高花费的。它也使算法 的流水线执行成为不可能。可以容易地验证，如果A，B＜M，则Si+1＜2M 总是保持。然而，Sm不能重新用作下一次模乘的输入A或B。如果在 am+1＝0且输入A，B＜2M的情况下来执行for循环的两次多余运行，则 满足不等式Sm+2＜2M。现在，Sm+2可以用作下一次模乘的输入B。
为进一步减小方法1.5的复杂性，使B上移一个位置，即使B乘 以2。这导致ai·B mod 2＝0，并且避免了步骤3中的加法。在Si+1的更 新期间，用(Si+qiM)/2+aiB来代替(Si+qiM+aiB)/2。该简化的成本是在 am+2＝0的情况下多运行一次循环。以下方法包括这些优化。
方法1.6用于计算A·B mod M的Montgomery模乘(基数r＝2)，
其中
A，B＜2M；M＜R＝2m+2；gcd(2，M)＝1
1.S0＝0
2.FOR i＝0to m+2DO
3.qi＝Si mod 2
4.Si+1＝(Si+qiM)/2+aiB
5 END FOR
以上算法计算Sm+3＝(2-(m+2)AB)mod M。为得到正确的结果，执行 额外的Montgomery模乘22(m+2)mod M。然而，如果如在取幂算法中 一样需要进一步的乘法操作，最好使所有的输入预先乘以系数22(m+2) mod M。因而，每个中间结果都携带系数22(m+2)。使结果与“l”进行 Montgomery相乘来消除该系数。
与“l”的最终Montgomery乘确保了最终的结果小于M。
高基数Montgomery算法
通过避免代价高的步骤6的比较和减法操作、并将条件改变为 4M＜2km且A，B＜2M，产生了相对于在硬件中实施方法1.4的某些优化。
其代价是多运行两次循环。最终所得的方法如下：
方法1.7用于计算A·B mod M的Montgomery模乘，其中
M′＝-M-1mod2k
1.S0＝0
2.FOR i＝0至m-1 DO
3.qi＝(Si+aiB)mod 2k
4.
5 END FOR
通过用B·2k代替B，进一步减小商qi确定的复杂性。因为aiB md 2k＝0，步骤3被简化为qi＝Si mod 2k。以附加的循环迭代为代价来避免 步骤3中的加法，以补偿B中的额外系数2k。为硬件实施而优化的 Montgomery方法如下所示：
方法1.8用于计算A·B mod M的Montgomery模乘，其中
M′＝-M-1mod2k
1.S0＝0
2.FOR i＝0to m-1DO
3.qi＝Si mod 2k
4.
5 END FOR
然后，使最终结果与“l”进行Montgomery相乘，以消除如上所 述的其中的系数。
在此处被引入作为参考的、Thomas Blum于1999年4月8日提交 给Faculty of the Worcester Polytechnic Institute的题为Modular Exponentiation on Reconfigurable Hardware的论题中，Thomas Blum提 出了两种不同的用于利用模乘和Montgomery空间执行加密功能的流 水线体系结构：基于方法1.6的面积高效体系结构和速度高效体系结 构。使用Xilinx XC4000系列设备作为目标设备。
一般2基脉动阵列使用m×m处理部件，其中m为模数的位数， 并且每一部件处理一位。可以同时处理2m个模乘操作，以每时钟周 期一个模乘的处理量以及2m个周期的等待时间为特色。因为对于现 代公开密钥方案中所需的典型位长、该方法导致了不实际的大CLB计 数，因此只实施一行处理部件。利用该方法，可以同时处理2个模乘 操作，而执行降低到每2m个周期2个模乘操作的处理量。等待时间 保持为2m周期。
第二考虑事项是基数r＝2k的选择。增大k将减少方法1.8中要执 行的步骤的数量。然而，这种方法需要更多的资源。主要的花费在于 2k与M和B相乘的计算。这些或者被预先计算并存储在随机存储器 (RAM)中，或者被多路复用器网络计算。无疑，对于r＝2、CLB基 数变成最小，因为不必计算或预先计算M或B的乘。
利用基数r＝2，来计算依据方法1.6的方程式。为进一步减少所需 的CLB数量，任选地采取以下措施：每个单元处理多于一位。单个加 法器用于预先计算B+M，以及执行正常处理期间的其它加法操作。并 行地计算自乘和乘法操作。该设计按等级被分为三个级别。
处理部件：计算模乘的u位。
模乘：处理部件阵列计算模乘
模取幂：将模乘操作与根据算法1.2的模取幂相结合 处理部件
图8显示了处理部件的实施过程。
在处理部件中，存在以下寄存器：
·M-Reg(u位)：存储模数
·B-Reg(u位)：存储B乘数
·B+M-Reg(u位)：存储中间结果B+M
·S-Reg(u+1位)：存储中间结果(包括进位)
·S-Reg-2(u-1位)：存储中间结果
·Control-Reg(3位)：控制多路复用器和时钟使能
·ai、qi(2位)：乘数A、商Q
·Result-Reg(u位)：存储乘法最后的结果
寄存器需要总共(6u+5)/2个CLB，加法器需要u/2+2个CLB，多 路复用器需要4·u/2个CLB，以及解码器需要2个CLB。将寄存器重 新用于组合逻辑的可能性允许CLB的某些节省。将MuxB和MuxRes 实施在B-Reg和Result-Reg的CLB中，将Mux1和Mux2部分地实施 在M-Reg和B+M-Reg中。最终所得的成本是大约每u位处理单元3u+4 个CLB。即，每位3到4个CLB，这取决于单元大小u。
在单元能够计算模乘之前，必须加载系统参数。将M存储到单元 的M-Reg中。在模乘开始时，根据多路复用器B-Mux的选择线，从 B-in或S-Reg加载操作数B。下一步是计算一次M+B，并将结果存储 在B+M-Reg中。该操作需要两个时钟周期，因为结果首先随着时钟 进入到S-Reg中。分别通过ai或控制字来控制Mux1和Mux2的选择线。
在接着的2(m+2)个周期中，根据方法1.6来计算模乘。多路复用 器Mux1根据二进制变量ai和qi的值，来选择要馈入加法器中的其输 入0、M、B、B+M之一。Mux2将先前结果S-Reg2的u-1个最高有效 位加上下一单元(除以2/右移)的最低有效结果位馈入加法器的第二 输入端。将结果存储在S-Reg中一个周期。最低有效位进入向右的单 元(除以2/右移)，而进位进入向左的单元。在该周期中，利用更新 的S-Reg2、ai、qi值在加法器中计算第二模乘。第二模乘使用相同的 操作数B，但是不同的操作数A。
在模乘的末尾，在加法器的输出端处，Sm+3在一个周期内有效。 将该值存储到Result-Reg中，如通过S-Reg馈入B-Reg中一样。在一 个周期之后将第二乘法的结果馈入Result-Reg中。
图9显示了处理部件怎样连接到用于计算m位模乘的阵列。为执 行相对于m的方法，使用每单元处理u位的m/u+1个单元。Unit0只 有u-1个B输入，因为B0被加到移位值Si+qiM上。根据Montgomery 算法的特性，结果位S-Reg0总是为0。Unitm/u处理B的最高有效位以 及中间结果Si+1的临时溢出。没有到该单元的M输入。
单元的输入和输出以以下方式相互连接。控制字、qi和ai被从右 向左泵送(bumped)通过单元。结果从左向右泵送。carry-out(载出) 信号被馈给向右的carry-in(载入)输入。输出S_0_Out总是连接到向 右的单元的输入S_0_In。这代表方程式除以2。
首先将模数M馈入单元中。为允许信号有足够的时间传播到所有 单元，M在两个时钟周期内有效。我们使用两个M-Bus，M-even-Bus 连接到所有的偶数单元、M-odd-Bus连接到所有的奇数单元，该方法 允许每时钟周期将u位馈给单元。因而，需要m/u个周期来加载完整 模数M。
类似地加载操作数B。信号也在两个时钟周期内有效。在加载操 作数B之后，方法1.6的步骤的执行就开始了。
从最右边的单元unit0开始，将控制字、ai和qi馈入它们的寄存器 中。加法器根据ai和qi、在一个时钟周期内计算S-Reg-2加上B、M 或B+M。读回结果的最低有效位作为下一次计算的qi+1。将所得到的 进位位、控制字、ai和qi泵入向左的单元中，其中在下一个时钟周期 中发生相同的计算。
以这种脉动的形式，将控制字、ai、qi和进位位从右向左泵送通过 整个单元阵列。方法1.6中的除以2也导致了右移操作。单元的加法 (S0)的最低有效位总是被反馈到向右的单元中。在完成模乘之后， 将结果从左向右泵送通过单元、并连续地存储在RAM中用于进一步 处理。
单个处理部件计算Si+1＝(Si+qi·M)/2+ai·B的u位。在时钟周期i中， unit0计算Si的位0…u。在时钟周期i+1中，unit1使用所得的进位、并 计算Si的位u…2u。unit0在时钟周期i+2中、利用Si(S0)的右移(除以 2)位u来计算Si+1的位0…u-1。在单元unit0中时钟周期i+1是非生 产性的、同时等待unit1的结果。通过依据方法1.2并行地计算自乘和 乘法操作，来避免这种低效率。pi+1和zi+1都取决于zi。因此，将中间 结果zi存储在B-Register中，并将zi和pi一起馈入单元的ai输入中用 于自乘和乘法。
图10显示了单元阵列怎样用于模取幂。在设计的核心是具有以下 17种状态的有限状态机(FSM)：空闲状态，用于加载系统参数的4 种状态，以及用于计算模取幂的4×3种状态。实际的模取幂是在预先 计算1、预先计算2、计算和计算后4种主要状态下执行的。这些主要 状态的每一种都细分为3种子状态：load-B、B+M和计算乘法。根据 状态来对馈入control-in的控制字编码。以二分之一时钟频率对FSM 计时。同样对加载和读取RAM和DP RAM元件也成立。该措施确保 最大传播时间是在单元中。因而，最小时钟周期时间和最终所得的模 取幂的速度与单元中的有效计算时间有关，而与计算开销无关。
在计算模取幂之前，加载系统参数。从I/O将模数M的2u位读 入M-Reg中。从低数位开始向高数位读。从M-Reg将M的u位交替 地馈给M-even-Bus和M-odd-Bus。每次信号在两个周期内有效。当时， 从I/O读取指数E的16位、并存储到Exp-RAM中。来自I/O的最初 16位宽的字指定了指数的位长。直到64个后面的字包含了实际的指 数。当时，从I/O读出预先计算系数22(m+2)mod M的2u位。将该2u 位存储到Prec-RAM中。
在预先计算1状态下，我们从I/O读取X值，每个时钟周期u位， 并将它存储到DP RAM Z中。同时，从Prec-RAM读出预先计算系数 22(m+2)mod M、并且每时钟周期将u位交替地通过B-even-Bus和 B-odd-Bus馈给单元的B-Register。在接下来的两个时钟周期中，在单 元中计算B+M。
用于方法1.2的初值是可得的。两个值都必须乘以2，这可以被并 行地执行，因为两个乘法操作都使用已经存储在B中的公共操作数 22(m+2)modM。时分复用(TDM)单元从DP RAM Z读出X，并将X 与1复用。在2(m+3)个时钟周期之后，结果的低数位出现在Result-Out， 并被存储在DP RAM Z中。在一个周期之后，下一个结果的低数位出 现在Result-Out，并被存储在DP RAM P中。该过程重复2m个周期， 直到两个结果的所有数位都被存储在DP RAM Z和DP RAM P中为 止。结果X·2m+2mod M也被存储在单元的B-Register中。
在预先计算2状态下，方法1.2的实际步骤开始。对于Z1和P1 两者的计算，都将Z0用作操作数。该值被存储在B-Register中。第二 操作数Z0或P0分别从DP RAM Z和DP RAM P被读出，并作为ai、 通过TDM被“泵”入单元中。在另外的2(m+3)个时钟周期之后，Z1 和P1的结果的低数位出现在Result-Out。Z1被存储在DP RAM Z中。 只有当指数e0的第一位等于“1”时，才需要P1。取决于e0，P1被 存储在DP RAM P中、或者被丢弃。
在计算状态下，方法1.2的循环被执行n-1次。在每个周期之后 DP RAM Z中的Zi都被更新，并作为ai被“泵”回到单元中。只有当 指数ei的相关位等于“1”时，才更新DP RAM P中的Pi。这样，总 是最后存储的P被“泵”回到单元中。
在en-1的处理之后，FSM进入计算后状态。为了从结果Pn消除系 数2m+2，计算最终的Montgomery乘1。首先交替地通过B-even-Bus 和B-odd-Bus、将向量0，0，…0，1馈入单元的B-Register中。从DP RAM P将Pn作为ai泵入单元中。在执行计算后状态之后，结果Pn＝XE mod M的u位在I/O端口处有效。每两个时钟周期另外的u位出现在I/O 处。现在可以立即重新进入预先计算1状态，以计算另一X值。
在2(n+2)(m+4)个时钟周期内计算完整的模乘。那是从把X的最 初u位插入设备中，直到最初的u个结果位出现在输出处为止的延迟。 在那一点上，另一个X值可以进入设备中。在附加的m/u个时钟周期 的等待时间之后，最后的u位出现在输出总线上。
以下，说明图10中的功能块。图11显示了DP RAM Z的设计。 m/u×u位DP RAM在该单元的核心。它具有分开的写(A)和读 (DPRA)地址输入。计数直到m/u的写计数器计算写地址(A)。当 Zi的最初u位出现在data-in时，写计数器在B-load子状态下开始计数 (时钟使能)。同时，DP RAM的使能信号有效，并且数据被存储在 DP RAM中。当达到m/u时，终端计数(terminal-count)使DP RAM的 计数使能和写使能复位。在计算子状态下，读计数器被允许操作。当 读计数器达到其上限m+2时，终端计数(terminal-count)触发FSM 转换为子状态B-load。读计数器值(q-out)的log2(m/u)最高有效位对 DP RAM的DPRA寻址。每u个周期读出DP RAM中存储的另一个 值。当q-out的log2(u)最低有效位达到0时，将该值加载到移位寄存 器中。在接下来的u个周期，u位逐位地出现在移位寄存器的串行输 出处。Zi的最后值被存储在u位寄存器中。该办法允许我们选择m/u ×u位DP RAM，而不是2m/u×u位DP RAM(m＝2x，x＝8，9，10)。
DP RAM P几乎以同样的方式工作。它具有附加的输入ei，在ei＝1 的情况下，ei激活DP RAM的写使能信号。
图12显示了Exp RAM的设计。在加载指数状态(load-exponent state)的第一周期中，从I/O读出第一个字，并存储到10位寄存器中。 它的值指定了指数的位长。在后续的周期中，每次读出指数的16位、 并存储在RAM中。通过6位写计数器来计算存储地址。在每一个计 算状态开始时，10位读计数器都被允许操作。它的6个最高有效位计 算存储器地址。因而，每第16次激活，就从RAM读出新的值。在读 计数器的4个最低有效位等于0的同时，将该值存储在16位移位寄存 器中。当读计数器达到10位寄存器中指定的值时，终端计数 (terminal-count)信号触发FSM进入计算后状态。
图13显示了Prec RAM的设计。在加载预先系数状态下，当时从 I/O读出预先计算系数的2u位、并存储在RAM中。计数直到m/2u 的计数器对RAM寻址。当所有的m/2u个值都被读出时，终端计数 (terminal-count)信号触发FSM离开加载预先系数状态。
在预先计算1状态下，从RAM读出预先计算系数，并馈给单元 的B-Register。每个时钟周期都递增计数器，并将2u位加载到2u位 寄存器中。每个时钟周期的正沿从那里将u位馈在B-even-Bus上。在 负时钟边沿，将u位馈在B-odd-Bus上。
速度高效体系结构
以上设计是在资源使用方面进行优化的。利用基数r＝2k，k＞1， 将使方法1.6中的步骤数量减少k倍。方法1.8的计算倍执行m+3次 (i＝0至m+2)。
很容易按等级将速度高效设计分为3个级别。
处理部件：计算模乘的4位
模乘：处理部件阵列计算模乘
模取幂：将模乘操作与根据方法1.2的模取幂相结合
图14显示了处理部件的实施。
提供了以下元件：
·B-Reg(4位)：存储B乘数
·B-Adder-Reg(5位)：存储B的倍数
·S-Reg(4位)：存储中间结果Si
·Control-Reg(3位)：控制多路复用器和时钟使能
·ai-Reg(4位)：乘数A
·qi-Reg(4位)：商Q
·Result-Reg(4位)：存储在乘法末尾的结果
·B-Adder(4位)：将B加到先前计算的B的倍数上
·B+M~-Adder(4位)：将M~的乘加到B的倍数上
·S+B+M~-Adder(5位)：将M~Si加到B+M~-Adder上
·B-RAM(16×4位)：存储B的16倍数
·M~-RAM(16×4位)：存储M~的16倍数
从以上参考的T.Blum的论题，以及从图的回顾，单元的操作是显 然的。
图15显示了处理部件怎样连接到用于计算全尺寸模乘的阵列。
图16显示了单元阵列怎样用于模取幂。
图17显示了DP RAM Z的设计。m×4位DP RAM位于该单元的 核心。它具有分开的写(A)和读(DPRA)地址输入。计数直到m+2 的两个计数器计算这些地址。当Zi的第一数位出现在data-in时，写 计数器在B-load子状态下开始计数(时钟使能)。同时，DP RAM的 使能信号有效，并且数据被存储在DP RAM中。当达到m+2时，写 计数器的终端计数(terminal-count)信号使两个使能信号复位。在计 算子状态下读计数器被允许操作。DP RAM的数据被读计数器的q-out 寻址、并立即出现在DPO处。当读计数器达到m+2时，终端计数 (terminal-count)触发FSM转变为B-load子状态。最后两个zi值的 每一个都被存储在4位寄存器中。
该办法允许我们选择100％利用的m×4位DP RAM，而不是仅仅 50％利用的2m×4位DP RAM。DP RAM P几乎以同样的方式工作。 它具有附加的输入ei，在ei＝“1”的情况下，ei激活DP RAM的写使 能信号。
因为以上的流水线处理器体系结构体现了许多流水线处理部件， 所以常常难以、并且代价高地在同一集成电路内使每个部件与时钟脉 冲源同步。因此，本发明的极其有利之处在于，通过简化时钟分配问 题来减少总的资源需求。而且，因为在一个方向上需要加法，而在另 一个方向上需要乘法，所以显然沿一条路径所需的时间比沿另一条路 径所需的时间多，因此根据本发明的实施例，路径的时间平均是有可 能的。
在不背离本发明的精神和范围的情况下，可以设想大量的其它实 施例。