EP0239749B1
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Cryptographic method and processor for carrying out this method
Assignee: Individual
•
Filing: 1987-02-05
•
Granted: 1990-07-25
•
Expires: 2007-02-05
Abstract
Abstract A cryptographic processer and method for utilizing the "public key code" method of Rivest, Shamir, and Adleman ("RSA method"), for enciphering and deciphering messages wherein two large prime numbers, p and q, and a third large number, E are selected and multiplied to form, N=p*q, converting the message to be encrypted into a series of elements Pi preferably of equal length and having numerical values less than that of N, encrypting these elements Pi by raising each to the power E and subsequently reducing modulus N, to give the numbers Ci=Pi Emodulus N, carrying out the above involution step by means of a series of multiplications, performing modulus-reduction operation following the series of multiplications, by carrying out a multiplication in the remainder class ring N, carrying out the aforesaid multiplication by breaking down the operation into individual steps, whereby the multiplication is essentially converted to a series of additions, and carrying out the aforesaid modulus-reduction as a series of subtractions, according to the classical division algorithm, wherein a first look-ahead technique is used for the division and the multiplication is also carried out with a second look-ahead technique.
Inventors
- 👤 Holger Sedlak
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-30 01:39
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/60; G06F7/72; G06F7/721; G06F7/722; H; H04; H04L; H04L9/00; H04L9/30; H04L9/3006; H04L9/302; H04N; H04N25/00; H04N25/70; H04N25/76; H04L2209/00; H04L2209/12; H04L2209/125
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
200 words
Cryptographic method according to the public key code method of Rivest, Shamir, and Adleman (RSA method), for enciphering and deciphering messages comprising the steps of: selecting two large prime numbers p and q and a further large number E; forming the product N = p-q; converting the message to be encrypted into a series of elements P preferably of equal length and having numerical values less than that of N; encrypting these elements P by raising each to the power E and subsequently formation of modulo N, (i.e. the numbers C = p I E modulo N are obtained); replacing the above involution step by means of a series of multiplications and after each multiplication a modulo operation is immediately performed, (i.e. by carrying out a multiplication in the remainder class ring over N); the aforesaid multiplication is broken down into individual steps, so that from multiplication is formed a series of additions; and the modulo operation according to the classical division algorithm is replaced by a series of subtractions, characterized by the use of a first look-ahead technique for the division (fig. 5) so that the multiplication can also be carried out by a second look-ahead technique (fig. 4).
Claim 2
Dependent Claim
200 words
Cryptographic method according to the public key code method of Rivest, Shamir, and Adleman (RSA method), for enciphering and deciphering messages comprising the steps of: selecting two large prime numbers p and q and a further large number E; forming the product N = p-q; converting the message to be encrypted into a series of elements P preferably of equal length and having numerical values less than that of N; encrypting these elements P by raising each to the power E and subsequently formation of modulo N, (i.e. the numbers C = p I E modulo N are obtained); replacing the above involution step by means of a series of multiplications and after each multiplication a modulo operation is immediately performed, (i.e. by carrying out a multiplication in the remainder class ring over N); the aforesaid multiplication is broken down into individual steps, so that from multiplication is formed a series of additions; and the modulo operation according to the classical division algorithm is replaced by a series of subtractions, characterized by the use of a first look-ahead technique for the division (fig. 5) so that the multiplication can also be carried out by a second look-ahead technique (fig. 4).
Claim 3
Dependent Claim
23 words
Cryptographic method according to claim 1, characterized in that look-ahead algorithms are used to reduce the maximum necessary number of additions and/or subtractions.
Claim 4
Dependent Claim
60 words
Cryptographic method according to claim 2, characterized in that for said first look-ahead technique for the modulo operation, is selected such that the probability-theoretical expected value of the number of operations skipped in the first look-ahead technique is exactly the same as the probability-theoretical expected value of the number of operations skipped in the second look-ahead technique for the multiplication.
Claim 5
Dependent Claim
74 words
Cryptographic method according to claim 3, characterized by uncoupling the two look-ahead techniques, each of the two look-ahead techniques generating a shift amount (sz or sn), respectively representing the number of bits the intermediate result (Z) for the multiplication, or the modulo (N), respectively, is to be shifted per cycle, the intermediate result (Z) being shifted absolutely by sz bits, and modulo (N) is shifted by sn bits relative to the intermediate result (Z).
Claim 6
Dependent Claim
55 words
Cryptographic method according to one of the claims 1 to 4, characterized in that the addition and subtraction of the multiplication step and modulo step, respectively, are combined into a single operation (a 3-operand addition) wherein three and not two operands being added per step, as follows: said 3-operand addition being divided into two segments.
Claim 7
Dependent Claim
85 words
Cryptographic method according to claim 5, characterized by selecting the first of the two segments such that a sum of the three bits of the operands A, Band C is formed at each binary position, with the sum A[i] + B[i] + C[i] lying between 0 and 3, said sum being binary and capable of being represented by two bits, S1 and S0, and generating two new numbers X and Y from the two sum bits, as follows: and (where i = 0, ..., max).
Claim 8
Dependent Claim
64 words
Cryptographic method according to claims 5 and 6, characterized by selecting the second segment such that the numbers X and Y are added together in per se known manner with carry, and performing the bit addition without carry of the first segment at a point in time at which normal additional logic is prepared for the next cycle by means of a precharge signal.
Claim 9
Dependent Claim
77 words
Cryptographic method according to claim 7, characterized in that said addition comprises the steps of: a) breaking down the long or large numbers X and Y into small blocks (32); b) simultaneously calculating the carry bits within the blocks (32) according to a per se known carry-look-ahead (CLA) method; and c) passing on the carry bits of each block to the following block, for the case where the carry bits of neighbouring blocks are not thereby affected.
Claim 10
Dependent Claim
48 words
Cryptographic method according to claim 8, characterized by providing an interrupter (62) which is activatable by the blocks (32 (fig. 4), said interrupter, in the case where carry bits have effects beyond neighbouring blocks, making the necessary time available for said carry bits to be calculated and processed.
Claim 11
Dependent Claim
101 words
Cryptographic processor for carrying out the cryptographic method according to claim 1, characterized by a sequence of specialized elementary cells (10) for calculating the individual operations; assembled blocks each of which comprises a plurality of elementary cells (10) (fig. 8) being in each case combined in stages to larger blocks (32) (fig. 9); a tree-like hierarchical CLA element (30) being associated with each block (28; 32), which ensures that in the normal case the time for the addition of two number is independent of the length of these numbers, and in each block (32) the carry operations are performed in parallel.
Claim 12
Dependent Claim
154 words
Cryptographic processor according to claim 10, characterized in that the elementary cells (10) (fig. 7) contain the following register and logic components: a register (12) for the multiplier (M); a code register (14); a data register (16); a UD (up/down) shift register (18) which contains a multiple of the modulo N during the calculation, and which in addition to its storage function has the capability of shifting the modulo N by a plurality of positions in one of the two directions, in a single step; a barrel shifter (20), which can shift the result of the addition, an intermediate result (Z) by several bits; a bit adder (22) without carry bit, which carries out the first step of the 3-operand operation; a full adder (24) for adding two numbers obtained in said bit adder (22) and storing the result as an intermediate result (Z); and a CIA element (26) for calculating a carry bit.
Claim 13
Dependent Claim
16 words
Cryptographic processor according to claim 11, characterized in that all the components (12-26) operate in parallel.
Claim 14
Dependent Claim
110 words
Cryptographic processor according to one of the claims 10 to 12, characterized by combining a plurality of blocks (28) of elementary cells (10) into larger blocks (32), the carry being passed serially from one block to the next, the CLA elements (30) of the bocks (32) being once again given a tree-like structure, the carry being calculated simultaneously on each superordinate CLA element (30) of a block, so that a signal from the carry calculations can optionally actuate an interrupter (62) which processes the signal coming from the CLA elements (30) and interrupts the clocks for about 8 cycles if a CLA element of a block (32) emits a signal.
Claim 15
Dependent Claim
161 words
Cryptographic processor according to one of the claims 10 to 13, characterized by a mult-mod control unit (36) (fig. 12) for controlling the functions of said elementary cells (10), said mult-mod control unit (36) comprising: a shift logic (50) for the multiplication; a shift logic (52) for the modulo operation; a comparator (38) which compares the topmost bits of the intermediate result (Z) of said full adder (24) with the topmost bits of 1/3, 1/6, 1/12, etc. of modulo N, parallel to each other; a first limiter (54) for the multiplication,which limits the maximum shift amount of intermediate result (Z); and a second limiter (56), for the modulo operation, which limits the maximum shift amount of said UD shift register (18) when needed; and two counters (58, 60), the first of said counters (58) registering the number of bits of register (12) still to be processed, and said second counter (60) registering the position of modulo N in a buffer (34).
Claim 16
Dependent Claim
74 words
Cryptographic processor according to one of the claims 1 to 14, characterized by an elementary block configured as a buffer (34) having a length of about 20 bits, for uncoupling said look-ahead algorithm for the multiplication from the look-ahead algorithm for the modulo operation, N penetrating said buffer (34), the mult-mod control unit (36) ensuring via said limiters (58,60) that modulo N does not exit either the upper or lower boundary of the buffer.
Claim 17
Dependent Claim
21 words
Cryptographic processor according to claim 10, characterized in that each 20-cell block (32) comprises an aggregation of 20 elementary cells (10).
Claim 18
Dependent Claim
43 words
Cryptographic processor according to claim 10, characterized by an encryption and decryption unit (40) (fig. 11), a variable-configuraton register block (46), an input/output unit (44), and a main control unit (42), in active communication with said encryption and decryption unit via data buses.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.