专利快速检索-快速检索全球专利，免费商用专利数据库-IPRDB

1. 发明公开

US20230401037A1 OPTIMIZATION TECHNIQUE FOR MODULAR MULTIPLICATION ALGORITHMS 审中-公开
公开(公告)号：US20230401037A1
公开(公告)日：2023-12-14
申请号：US18237859
申请日：2023-08-24
申请人： Intel Corporation
发明人： Erdinc OZTURK , Kirk S. YAP , Tomasz KANTECKI
IPC分类号： G06F7/72
CPC分类号： G06F7/722 , G06F7/728
摘要： Methods and apparatus for optimization techniques for modular multiplication algorithms. The optimization techniques may be applied to variants of modular multiplication algorithms, including variants of Montgomery multiplication algorithms and Barrett multiplication algorithms. The optimization techniques reduce the number of serial steps in Montgomery reduction and Barrett reduction. Modular multiplication operations involving products of integer inputs A and B may be performed in parallel to obtain a value C that is reduced to a residual RES. Modular multiplication and modular reduction operations may be performed in parallel. The number of serial steps in the modular reductions are reduced to L, where L serial steps, where w is a digit size in bits, and L is a number of digits of operands=[k/w].

2. 发明申请

US20180181374A1 APPARATUS AND METHOD FOR MODULAR MULTIPLICATION 审中-公开
公开(公告)号：US20180181374A1
公开(公告)日：2018-06-28
申请号：US15807888
申请日：2017-11-09
申请人： ELECTRONICS AND TELECOMMUNICATIONS RESEARCH INSTITUTE
发明人： Yun-Koo LEE , Dong-Geon LEE , Min-Kyu JOO , Yoen-Cheol LEE , Sang-Woon YANG
IPC分类号： G06F7/523 , G06F7/50
CPC分类号： G06F7/523 , G06F7/50 , G06F7/722 , G06F7/728
摘要： An apparatus and method for modular multiplication. The modular multiplication apparatus includes a first operation unit for performing a first operation based on a structure of at least one of a serial multiplier and a serial squarer-based multiplier; a second operation unit for performing a second operation based on a structure of at least one of the serial multiplier and the serial squarer-based multiplier; an adder unit for outputting the sum of results of the first operation and the second operation, inputting an intermediate value stream to the first input unit, which calculates the product of the intermediate value stream and a zeta parameter, and outputting a High-Order Term as a result of Montgomery Modular Multiplication, wherein the first and second operation units output a result in digit-serial format in order from the least significant digit to the most significant digit.

3. 发明授权

US08909689B2 Arithmetic device 有权
标题翻译：算术设备
公开(公告)号：US08909689B2
公开(公告)日：2014-12-09
申请号：US13361074
申请日：2012-01-30
申请人： Hideo Shimizu , Yuichi Komano , Koichi Fujisaki , Shinichi Kawamura
发明人： Hideo Shimizu , Yuichi Komano , Koichi Fujisaki , Shinichi Kawamura
IPC分类号： G06F7/72
CPC分类号： G06F7/728
摘要： According to one embodiment, a first shift amount calculation unit counts the number of continuous zeros from a less significant bit toward a more significant bit of an intermediate result of a computation of Montgomery multiplication result z and calculates a first shift amount. A second shift amount calculation unit counts the number of continuous zeros from a less significant bit toward a more significant bit of redundant-binary-represented integer x and calculates a second shift amount. An addition/subtraction unit calculates the intermediate result by adding/subtracting, with respect to the intermediate result which has been bit-shifted by the first shift amount, the integer p, and the integer y which has been bit-shifted by the second shift amount. An output unit outputs, as the Montgomery multiplication result z, the intermediate result when the sum of the first shift amounts is equal to the number of bits of the integer p.
摘要翻译：根据一个实施例，第一移位量计算单元从蒙哥马利乘积结果z的计算的中间结果的较低有效位向更高有效位对连续零的数进行计数，并计算第一移位量。第二移位量计算单元将来自冗余二进制表示的整数x的较低有效位朝向更高有效位的连续零的数目计数，并计算第二移位量。加法/减法单元相对于已被移位了第一移位量的中间结果，整数p和已被位移第二移位的整数y加/减来计算中间结果量。当第一移位量的和等于整数p的位数时，输出单元输出作为蒙哥马利乘数结果z的中间结果。

4. 发明申请

US20140294174A1 Efficient Prime-Number Check 有权
标题翻译：高效的Prime-Number检查
公开(公告)号：US20140294174A1
公开(公告)日：2014-10-02
申请号：US14354455
申请日：2012-10-25
申请人： GIESECKE & DEVRIENT GMBH
发明人： Jurgen Pulkus
IPC分类号： H04L9/14
CPC分类号： H04L9/14 , G06F7/72 , G06F7/728 , G06F2207/7204 , H04L9/0869
摘要： In a method for checking whether a value represents a prime number, for a cryptographic application, a Fermat test is carried out, which includes a modular exponentiation of a base with an exponent (e) and a module (m). The exponent (e) and the module (m) respectively depend on the value to be checked, and the modular exponentiation is executed employing Montgomery operations. A device and a computer program product have corresponding features. The method can be particularly efficiently implemented on suitable platforms.
摘要翻译：在用于检查值是否表示素数的方法中，对于密码应用，执行费马测试，其包括具有指数（e）和模块（m）的基数的模幂运算。指数（e）和模块（m）分别取决于要检查的值，并且采用蒙哥马利运算执行模幂运算。设备和计算机程序产品具有相应的特征。该方法可以在合适的平台上特别有效地实现。

5. 发明授权

US08799343B2 Modular exponentiation with partitioned and scattered storage of Montgomery Multiplication results 有权
标题翻译：使用蒙哥马利乘法结果的分区和分散存储进行模块化取幂
公开(公告)号：US08799343B2
公开(公告)日：2014-08-05
申请号：US13241137
申请日：2011-09-22
申请人： Shay Gueron , Vlad Krasnov
发明人： Shay Gueron , Vlad Krasnov
IPC分类号： G06F7/38
CPC分类号： G06F7/723 , G06F7/728 , G06F2207/7257
摘要： Embodiments of techniques and systems for side-channel-protected modular exponentiation are described. In embodiments, during a modular exponentiation calculation, Montgomery Multiplication (“MM”) results are produced. These MM results are scattered through a table for storage, such that storage of the values may not lead to discovery of a secret exponent value by a spy process through a side-channel attack. The scattering may be performed in order to reduce a number of per-result memory operations performed during each MM result storage or retrieval. In embodiments, a window size of 4 may be used in the modular exponentiation, along with partitioning of the MM result into 32-bit partition values which are scattered with offsets of 64-bytes. In embodiments, while use of a window size of 4 may result in additional MM calculations during modular exponentiation than other window sizes, the reduction in memory operations may provide a positive performance offset.
摘要翻译：描述了用于侧信道保护的模幂运算的技术和系统的实施例。在实施例中，在模幂乘计算期间，产生蒙哥马利乘法（“MM”）结果。这些MM结果分散在一个表中用于存储，这样，存储值可能不会导致间谍进程通过侧信道攻击发现秘密指数值。可以执行散射以便减少在每个MM结果存储或检索期间执行的每结果存储器操作的数量。在实施例中，可以在模幂运算中使用4的窗口大小，以及将MM结果划分为以64字节的偏移散布的32位分区值。在实施例中，尽管窗口大小为4的使用可能导致在模幂运算期间的额外的MM计算，而不是其他窗口大小，但存储器操作的减少可以提供正的性能偏移。

6. 发明授权

US08532286B2 System and method for reducing the computation and storage requirements for a montgomery-style reduction 有权
标题翻译：减少montgomery风格减少的计算和存储要求的系统和方法
公开(公告)号：US08532286B2
公开(公告)日：2013-09-10
申请号：US12838999
申请日：2010-07-19
申请人： Robert John Lambert
发明人： Robert John Lambert
IPC分类号： H04K1/00
CPC分类号： H04L9/30 , G06F7/728 , H04L2209/122
摘要： A system and method are described that provide an alternative way in which to produce a Montgomery reduction from below by storing a new precomputed value used to substantially replace the μ and n values used in Montgomery reduction with a single value. By modifying the Montgomery reduction mechanism in this way, the number of multiplications and registers required to effect the Montgomery reduction can be reduced. To avoid having to store both μ and n, a modified reduction value or a logical shift or signed version of such a value can be used in place of μ and n for the bulk of the low-order reduction.
摘要翻译：描述了一种系统和方法，其提供了通过存储用于基本上以单个值来代替蒙哥马利减少中使用的mu和n值的新的预计算值来从下方产生蒙哥马利减少量的替代方式。通过以这种方式修改蒙哥马利减排机制，可以减少影响蒙哥马利削减所需的乘法和寄存器的数量。为了避免存储mu和n，可以使用修改的缩减值或这种值的逻辑移位或签名版本代替mu和n用于低阶缩减的大部分。

7. 发明授权

US08527570B1 Low cost and high speed architecture of montgomery multiplier 失效
标题翻译： montgomery乘法器的低成本和高速架构
公开(公告)号：US08527570B1
公开(公告)日：2013-09-03
申请号：US12855340
申请日：2010-08-12
申请人： Chang Shu , Heng Tang , Sean Lee
发明人： Chang Shu , Heng Tang , Sean Lee
IPC分类号： G06F7/38
CPC分类号： G06F7/728
摘要： A system to perform Montgomery multiplication includes a first multiplier array configured to multiply w bits of an operand X by W bits of an operand Y, where w and W are integers and w is less than W. A second multiplier array is configured to multiply w bits of an operand Q by W bits of a modulo M. An adder array is configured to add outputs of the first and second multiplier arrays to generate a sum. A partial sum array is configured to store a left portion of the sum. A memory is configured to store a right portion of the sum. Q computation logic includes a lookup table and a half-multiplier that compute W bits of the operand Q sequentially in 2 · W w cycles or W w cycles. The W bits of the operand Q are stored in the fourth buffer for use by subsequent W×W operations.
摘要翻译：执行蒙哥马利乘法的系统包括：第一乘法器阵列，被配置为将操作数X的W位乘以操作数Y的W位，其中w和W是整数，并且w小于W.第二乘法器阵列被配置为将w 操作数Q的位由模M的W位构成。加法器阵列被配置为添加第一和第二乘法器阵列的输出以产生和。部分和数组被配置为存储和的左部分。存储器被配置为存储总和的右部分。 Q计算逻辑包括查找表和半乘法器，其以2WW周期或Ww周期顺序地计算操作数Q的W位。操作数Q的W位存储在第四缓冲器中，以供随后的W×W操作使用。

8. 发明授权

US08433736B2 Scalable Montgomery multiplication architecture 有权
标题翻译：可扩展的蒙哥马利乘法架构
公开(公告)号：US08433736B2
公开(公告)日：2013-04-30
申请号：US12714992
申请日：2010-03-01
申请人： Miaoqing Huang , Krzysztof Gaj
发明人： Miaoqing Huang , Krzysztof Gaj
IPC分类号： G06F7/38 , G06F7/00 , G06F15/00
CPC分类号： G06F7/728
摘要： A Montgomery multiplication device calculates a Montgomery product of an operand X and an operand Y with respect to a modulus M and includes a plurality of processing elements. In a first clock cycle, two intermediate partial sums are created by obtaining an input of length w−1 from a preceding processing element as w−1 least significant bits. The most significant bit is configured as either zero or one. Then, two partial sums are calculated using a word of the operand Y, a word of the modulus M, a bit of the operand X, and the two intermediate partial sums. In a second clock cycle, a selection bit is obtained from a subsequent processing element and one of the two partial sums is selected based on the value of the selection bit. Then, the selected partial sum is used for calculation of a word of the Montgomery product.
摘要翻译：蒙哥马利乘法装置相对于模数M计算操作数X和操作数Y的蒙哥马利乘积，并且包括多个处理要素。在第一时钟周期中，通过从前一处理元件获得长度w-1的输入作为w-1个最低有效位来创建两个中间部分和。最高有效位被配置为零或一。然后，使用操作数Y的字，模M的字，操作数X的位和两个中间部分和来计算两个部分和。在第二时钟周期中，从后续处理元件获得选择位，并且基于选择位的值选择两个部分和之一。然后，所选择的部分和用于计算蒙哥马利产品的单词。

9. 发明授权

US08386802B2 Method and apparatus for processing arbitrary key bit length encryption operations with similar efficiencies 失效
公开(公告)号：US08386802B2
公开(公告)日：2013-02-26
申请号：US13096470
申请日：2011-04-28
申请人： Hafid Zaabab
发明人： Hafid Zaabab
IPC分类号： H04L29/06
CPC分类号： G06F7/728
摘要： A calculating apparatus, or system, having a plurality of stages, such as in a pipeline arrangement, has the clocking rail or conductor positioned alongside the stages. With a large number, i.e., hundreds, of stages arranged in parallel sub-arrays, the clocking conductor is snaked alongside the sub-arrays. In individual stages it is arranged that the shortest of the two calculations taking place in a stage, takes place in the return path. An array can be divided into separate sections for independent processing.

10. 发明授权

US08352529B2 Modular multiplication calculation apparatus used for montgomery method 有权
标题翻译：用于montgomery方法的模块化乘法计算装置
公开(公告)号：US08352529B2
公开(公告)日：2013-01-08
申请号：US12218060
申请日：2008-07-11
申请人： Kazuyoshi Furukawa , Masahiko Takenaka
发明人： Kazuyoshi Furukawa , Masahiko Takenaka
IPC分类号： G06F7/38
CPC分类号： G06F7/728
摘要： REDC (A*B) is calculated for the values A and B by using a Montgomery's algorithm REDC. The part related to the A*B is performed by the three-input two-output product-sum calculation circuit. One digit ai of the value A, one digit bj of the value B and a carry value c1 are input to the product-sum calculation circuit, and ai*bj+c1 is calculated thereat. The higher-order digit of the r-adic two-digit of the calculation result is used as the carry value c1, and the lower digit is used for a later calculation. Further, one digit ni of a modulo N for the REDC, a predetermined value m and a carry value c2 are input into the product-sum calculation circuit, and n*ni+c2 is calculated thereat. The higher-order digit is used as the carry value c2, and the lower digit is used for a later calculation.
摘要翻译：通过使用蒙哥马利的算法REDC计算值A和B的REDC（A * B）。与A * B相关的部分由三输入双输出积和计算电路进行。值A的一位数ai，值B的一位数bj和进位值c1被输入到乘积和计算电路，并且在其计算ai * bj + c1。将计算结果的r-adic两位数的高阶数字用作进位值c1，将下位数用于后续计算。此外，对于REDC，模N的一位数ni，预定值m和进位值c2被输入到乘积和计算电路中，并且在那里计算n * ni + c2。高位数字用作进位值c2，下位数用于后续计算。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式