公开(公告)号：US20130198253A1

公开(公告)日：2013-08-01

申请号：US13793824

申请日：2013-03-11

Applicant: Samsung Electronics Co., Ltd.

Inventor： Young-sik Kim ,  Mi-Jung Noh ,  Kyoung-moon Ahn ,  Sun-soo Shin

IPC: G06F7/72

CPC classification number: G06F7/72 ,  G06F7/721 ,  G06F7/728

Abstract: Provided is a method of calculating a negative inverse of a modulus, wherein the negative inverse, which is an essential element in Montgomery multiplication, is quickly obtained. The method includes setting a modulus, defining P obtained by converting the modulus to a negative number, and defining S obtained by subtracting 1 from P, and calculating a negative inverse of the modulus by using P and S.

Abstract translation: 提供了一种计算模数的负逆的方法，其中快速获得作为蒙哥马利乘法中的基本要素的负逆。 该方法包括设定模量，通过将模数转换为负数来定义P，并定义通过从P中减去1获得的S，并且通过使用P和S计算模量的负逆。

公开(公告)号：US07574469B2

公开(公告)日：2009-08-11

申请号：US10535808

申请日：2003-12-15

Applicant: Róbert Lórencz

Inventor： Róbert Lórencz

IPC: G06F7/72

CPC classification number: G06F7/721

Abstract: The essence of the invention is an effective method for generating the multiplicative inverse in a finite field GF(p) where p is prime, i.e. for generating the modular inverse. This method is derived from the Extended Euclidean Algorithm (EEA). The method is for binary execution of operations during the process of generating the modular inverse, with respect to the lowest number of addition, subtraction and shift operations possible. The proposed method avoids redundant operations for converting odd and negative values, which are performed in methods currently in use. To achieve that, negative numbers are represented in the two's complement code, values in the control part of the EEA are shifted to the left, and a new definition of the boundary and control conditions is utilized in the procedure. Minimizing the number of additions and subtractions is desirable for calculations with large numbers often encountered in cryptography.

Abstract translation: 本发明的实质是在有限域GF（p）中产生乘法逆的有效方法，其中p是素数，即用于产生模数逆。 这种方法是从扩展欧几里德算法（EEA）得出的。 该方法用于在产生模数逆的过程中对于可能的最小加法，减法和移位操作数进行二进制执行。 所提出的方法避免了用于转换在当前使用的方法中执行的奇数和负值的冗余操作。 为了达到这一目的，负数表示在二进制补码中，EEA控制部分的值向左移动，并且在该过程中利用了边界和控制条件的新定义。 最小化加法和减法的数量对于在密码学中经常遇到的大量的计算是期望的。

公开(公告)号：US07457408B2

公开(公告)日：2008-11-25

申请号：US09978686

申请日：2001-10-18

Applicant: Erik Knudsen

Inventor： Erik Knudsen

IPC: H04L9/30 ,  H04L9/22

CPC classification number: G06F7/721 ,  G06F7/58

Abstract: A calculation unit in which the inverse of an integer modulo a large number is determined provides a series of binary numbers prime with the large number, divides those numbers into two groups at random, and effects the products of the numbers of each group.

Abstract translation: 其中确定大数模数的逆的计算单元提供一系列具有大数字的二进制数，将这些数字随机分成两组，并且影响每组的数量的乘积。

公开(公告)号：US20080201398A1

公开(公告)日：2008-08-21

申请号：US11915081

申请日：2006-05-19

Applicant: Bernd Meyer

Inventor： Bernd Meyer

IPC: G06F7/72

CPC classification number: G06F7/721 ,  G06F2207/7238

Abstract: In side-channel attack-resistant encoding methods, a return value (r) is determined as the modular inverse of an input value (a), by a module (M). A resistance to side-channel attack can be achieved with minimal restrictions on implementation on determination of the modular inverse with minimal technical complexity. To this end, in a first sub-step, a first product (d) of the input value (a) and a random number is generated (c), in a second sub-step, the modular inverse (e) of the first product (d) is determined by the module (M), in a third sub-step, a second product (b) of the random number (c) is determined by the modular inverse (e) and in a fourth sub-step the return value (r) is set to the same as the second product (b).

Abstract translation: 在侧信道抗攻击编码方法中，通过模块（M）将返回值（r）确定为输入值（a）的模数倒数。 在最小的技术复杂性的情况下，通过对确定模数逆的实现的最小限制，能够实现对侧信道攻击的抵抗。 为此，在第一子步骤中，在（c）中生成输入值（a）的第一乘积（d）和随机数（c），在第二子步骤中，第一子步骤 产品（d）由模块（M）确定，在第三子步骤中，随机数（c）的第二乘积（b）由模数逆（e）确定，在第四子步骤中 返回值（r）被设置为与第二乘积（b）相同。

公开(公告)号：US20060045263A1

公开(公告)日：2006-03-02

申请号：US10926598

申请日：2004-08-26

Applicant: Daniel Brokenshire ,  Mohammad Peyravian

Inventor： Daniel Brokenshire ,  Mohammad Peyravian

IPC: H04L9/30

CPC classification number: H04L9/30 ,  G06F7/721

Abstract: A method, an apparatus, and a computer program are provided for efficiently determining an inverse multiplicative modulo. In many public-key cryptographic algorithms, an inverse modulo is usually calculated in key generation. However, because many Reduced Instruction Set Computers (RISCs) do not have the hardware support for division, good results are often not yielded. Therefore, to efficiently calculate a inverse modulo, an modified algorithm that utilizes a minimum of 3 division and 2 multiplications in conjunction with shifts and addition/subtractions is employed. The modified algorithm then is able to efficiently utilize the properties of the RISC processors to yield good results, especially when developing keys for public-key cryptographic algorithms.

Abstract translation: 提供了一种方法，装置和计算机程序，用于有效地确定逆乘法模数。 在许多公钥加密算法中，通常在密钥生成中计算反模数。 然而，由于许多精简指令集计算机（RISC）没有对分区的硬件支持，因此通常不会产生良好的结果。 因此，为了有效地计算逆模，采用了利用最小3次除法和2次乘法结合偏移和加法/减法的修正算法。 然后，修改的算法能够有效地利用RISC处理器的属性产生良好的结果，特别是当为公钥密码算法开发密钥时。

公开(公告)号：US06917957B2

公开(公告)日：2005-07-12

申请号：US10091962

申请日：2002-03-05

Applicant: Josephus C. Ebergen ,  Sheueling Chang Shantz

Inventor： Josephus C. Ebergen ,  Sheueling Chang Shantz

IPC: G06F7/72 ,  G06F7/38 ,  G06F15/00

CPC classification number: G06F7/721

Abstract: One embodiment of the present invention provides a system that performs modular division. This system contains a number of registers, including: a register A that is initialized with a value X; a register U that is initialized with a value Y; a register B that is initialized with a value M; and a register V that is initialized with a value 0. The system also includes a counter CA that indicates an upper bound for the most-significant non-zero bit of register A. It also includes a counter CB that indicates an upper bound for the most-significant non-zero bit of register B. The system additionally includes a temporary register H, and a temporary register L. An updating mechanism is configured to iteratively reduce the contents of registers A and B to a value of one by applying a plurality of operations to registers A, B, U and V. During operation, this updating mechanism temporarily stores A+B in the temporary register H, and temporarily stores U+V in the temporary register L. Moreover, the updating mechanism is configured to use counters CA and CB to estimate the relative magnitudes of the values stored in registers A and B instead of performing an expensive comparison operation between register A and register B.

Abstract translation: 本发明的一个实施例提供一种执行模块划分的系统。 该系统包含多个寄存器，包括：用值X初始化的寄存器A; 用值Y初始化的寄存器U; 以值M初始化的寄存器B; 以及以值0初始化的寄存器V.系统还包括指示寄存器A的最高有效非零位的上限的计数器CA.其还包括指示上限的计数器CB 寄存器B的最重要的非零位。该系统还包括临时寄存器H和临时寄存器L.更新机构被配置为通过应用多个寄存器B将寄存器A和B的内容迭代地减小到1的值 的操作。在操作期间，该更新机构临时将A + B存储在临时寄存器H中，并将U + V临时存储在临时寄存器L中。此外，更新机构被配置为使用 计数器CA和CB估计存储在寄存器A和B中的值的相对大小，而不是在寄存器A和寄存器B之间执行昂贵的比较操作。

公开(公告)号：US20030195915A1

公开(公告)日：2003-10-16

申请号：US10419241

申请日：2003-04-21

Applicant: NIPPON TELEGRAPH AND TELEPHONE CORPORATION

Inventor： Kazumaro Aoki ,  Hiroki Ueda ,  Masayuki Kanda

IPC: G06F007/52

CPC classification number: G06F7/721 ,  G06F7/726 ,  G06F7/728 ,  H04L9/0625 ,  H04L2209/046 ,  H04L2209/122

Abstract: In a method for permuting and dividing 16 pieces of k-bit data held in 4 k-bit long registers T0. T1, T2 and T3, k being an integer, the data of each register Ti is ANDed with a desired one of mask data (00ffff00), (ff0000ff), (0000ffff) and (ffff0000), and such ANDs are ORed to obtain desired permuted data.

Abstract translation: 在用于置换和分割保存在4k位长寄存器T <下标> 0 中的16个k位数据的方法中。 T <下标> 1 ，T <下标> 2 和T <下标> 3 ，k为整数，每个寄存器T i 的数据为 与掩模数据（00ffff00），（ff0000ff），（0000ffff）和（ffff0000）中的期望的一个进行AND匹配，并且这样的“与”运算以获得期望的置换数据。

公开(公告)号：US06256656B1

公开(公告)日：2001-07-03

申请号：US09221911

申请日：1998-12-28

Applicant: Carroll Philip Gossett ,  Nancy Cam Winget

Inventor： Carroll Philip Gossett ,  Nancy Cam Winget

IPC: G06F700

CPC classification number: G06F7/729 ,  G06F7/721

Abstract: The integers involved in the computation are embedded into a modular system whose index (i.e., its modulus) is an integer M that is bigger than all of these integers involved. In other words, these integers are treated not as belonging to ordinary integers anymore, but as “modular integers” belonging to the modular system indexed by M. Having completed the embedding, CRT provides the bridge which connects the single modular system indexed by M (ZM) with a collection of k modular systems indexed by m1,m2, . . . , mk respectively (Zm1, Zm2, . . . , Zmk), where M factorizes as m1*m2*m3* . . . *mk, and where each mi is slightly smaller than single precision. Then, after numbers are manipulated within modular arithmetic, the answer is reconstructed via the algorithm of CRT, also known as CRA. Finally, the present invention introduces the process of dinking that overcomes the major weakness of implementing division with modular arithmetic. Particularly, within a composite modular arithmetic system, any theoretically impossible modular division is altered slightly [dinked] to a theoretical possible modular division whose quotient is closed enough to the true quotient sought, thus allowing all four arithmetic operations of modular arithmetic in high precision computation.

Abstract translation: 涉及计算的整数嵌入到一个模块化系统中，它的索引（即它的模数）是一个大于所有这些整数的整数M。 换句话说，这些整数被视为不属于普通的整数，而是属于由M索引的模块化系统的“模块化整数”。完成了嵌入后，CRT提供了连接由M（ ZM），其中包含由m1，m2指定的k个模块化系统的集合。 。 。 ，mk（Zm1，Zm2，...，Zmk），其中M因子分解为m1 * m2 * m3 *。 。 。 * mk，其中每个mi略小于单精度。 然后，在模数运算中操作数字之后，通过CRT的算法（也称为CRA）重构答案。 最后，本发明介绍了采用模块化算法实现划分的主要缺陷的烙印过程。 特别地，在复合模数运算系统中，任何理论上不可能的模块划分被稍微改变为理论上可能的模分割，其商商被关闭到满足所寻求的真商，从而允许在高精度计算中的所有四个算术运算 。

公开(公告)号：US5493522A

公开(公告)日：1996-02-20

申请号：US309641

申请日：1994-09-21

Applicant: Jonathan Rosenberg

Inventor： Jonathan Rosenberg

IPC: G06F7/72

CPC classification number: G06F7/726 ,  G06F7/727 ,  G06F7/721

Abstract: A circuit and method for carrying out high-speed ripple-through modulo division includes input registers for inputting two modulo 32 numbers A and B. The output of the circuit is a modulo 32 number Q, where A, B, and Q are related by the equation B*Q mod 32=A. The circuit generates a modulo division operator M.sub.B which is the inverse of B when B is odd, but which is equal to 2.sup.n, n=1, 2, 3, 4, when B is even. Combinational logic is used to calculate the product M.sub.B A, which is then divided by 2.sup.n, or sifted n places, to obtain Q.

Abstract translation: 用于进行高速纹波模数除法的电路和方法包括用于输入两个模32号码A和B的输入寄存器。该电路的输出是模32数Q，其中A，B和Q与 方程式B * Q mod 32 = A。 当B为奇数时，该电路产生一个模除法运算符MB，它是B的倒数，但当B为偶数时，它等于2n，n = 1,2,3,4。 组合逻辑用于计算产品MBA，然后将其除以2n或筛选的n个位置，以获得Q.

公开(公告)号：US5448639A

公开(公告)日：1995-09-05

申请号：US47103

申请日：1993-04-13

Applicant: Benjamin Arazi

Inventor： Benjamin Arazi

IPC: G06F7/72 ,  H04L9/32 ,  H04L9/30 ,  G06F7/52

CPC classification number: G06F7/721 ,  G06F7/728 ,  H04L9/06 ,  H04L9/302 ,  H04L9/3249 ,  H04L2209/12

Abstract: A Digital Signature Device includes hardware device for carrying out an operation AB2.sup.-n mod N and an operation AB mod N, and carrying out modular exponentiation and modular multiplication based on an operation AB2.sup.-n mod N and an operation AB mod N. A method of performing an operation AB2.sup.-n mod N, an operation AB mod N, modular exponentiation, and modular multiplication by using hardware device, such as electrical controller, feeder, and delay device, etc.

Abstract translation: 数字签名装置包括用于执行操作AB2-n mod N和操作AB mod N的硬件设备，并且基于操作AB2-n mod N和操作AB mod N执行模幂运算和模乘。一种方法 通过使用诸如电气控制器，馈线和延迟装置等硬件设备执行操作AB2-n mod N，操作AB mod N，模幂运算和模乘。