Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-11-21
2004-06-01
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C380S028000
Reexamination Certificate
active
06745220
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates generally to computer implemented exponentiation methods and more specifically to a method for exponentiation that is faster and has lower memory requirements than other computer implemented methods.
The encryption of data for communication and storage utilizing a computer system is well known in the art. The encrypting of data is accomplished by applying a cipher to the data to be encrypted. The cipher can be known only to the encrypter and recipient (a “symmetric encryption” scheme) or can be a combination of a widely known cipher coupled with a securely held cipher (a “public key” scheme).
Some of the more popular methods, because of the ease of use and the relative invulnerability to breaking, are “public key” systems of cryptography. These methods utilize complex mathematical formulas employing large exponents (i.e., exponents of several hundred bits or more) to increase the difficulty of unauthorized decryption.
One example of this method is the RSA method, named for its developers Rivest, Shamir, and Adleman. The RSA method is more fully described in RFC-2437 entitled “PKCS #1: RSA Cryptography Specifications Version 2.0.
An RSA public key consists of two components: n, the modulus, a nonnegative integer and e, the public exponent, also a nonnegative integer. In a valid RSA public key, the modulus n is a product of two odd prime numbers p and q, and the public exponent e is an integer between 3 and n−1 satisfying gcd (e, \lambda(n))=1, where \lambda(n)=1 cm (p−1, q−1), gcd (x, y) is the greatest common divisor of x and y, and 1 cm (x, y) is the least common multiple of x and y.
The RSA method involves solving the equation
c=m
e
mod n
where (n, e) are the RSA public key; m is the message representative, an integer between 0 and n−1, and c is the encrypted result of the exponentiation and modulo division.
The message is decrypted by the receiver by calculating m=c
d
mod n, where d is a private exponent. Thus, exponentiation is used both to encode and decode the message.
Another popular method of encryption is the Public Key Cryptosystem (PKC) proposed by T. ElGamal. According to this method, a prime number p is chosen and a primitive root g of p is chosen. User U selects an arbitrary number u and calculates g
u
=&agr; mod p, where &agr; is a residue of g to the u'th power modulo p. User V selects an arbitrary number v and calculates &bgr;=g
v
mod p. The parties exchange the residues &agr; and &bgr;, and each then calculates a common key value; for User U, k=&bgr;
u
modulo p and for User V, k=&agr;
v
modulo p. The data to be encrypted is then processed arithmetically, using k to transform the data; for example, by forming the exclusive-OR of the data and k. The same operation is used to decrypt the data. Again, exponentiation is used both by the message sender and the message receiver to calculate the key that is used to encrypt or decrypt the data.
Extremely large exponential values, however, extract a cost to the user in terms of the number of multiplications required and/or the amount of computer memory that is used to perform the operations. These types of multiply operations are costly because the values to be multiplied exceed the bit-length of the processor and, thus, are implemented as multi-precision operations.
A number a raised to an exponent e can always be calculated by multiplying that number by itself the number of time represented by the exponent, or in mathematical terms:
a
e
=a*a*a . . . e
number of times.
Another method, which is significantly faster, is the multiply chain algorithm. In this case, let e=e
n−1
e
n−2
. . .e
1
e
0
be an n-bit exponent e
i
∈{0,1}, 0≦i≦n−1and e
n−
1=1. The algorithm starts with p
1
=a, then
p
i+1
=p
i
2
if
e
n−1−i
=0 or
a*p
i
2
if
e
n−1−i
=1, where 1
≦i≦n
−2.
Several methods are known in the art to reduce either the number of multiplications or the amount of computer memory needed to produce efficient exponentiation of the base value.
One method known to reduce the number of multiplication is the signed digit algorithm. In this method, the exponent is represented as a string of bits comprising the values 0 and 1. Within the bit string, sequences (or “runs”) of 1's are replaced by 0's, with a 1 being placed in the next higher bit position to the most significant bit (MSB) position of the run, and “−1” being inserted in the least significant bit (LSB) position of the run. By thus efficiently recoding the exponent bit string, the expected number of multiplications is reduced from n/2 to n/3.
Another method known in the art for reducing the number of multiplications by utilizing memory, is the “sliding window method.” In this method, the exponent is again represented as a string of 0 and 1 bits. Substrings of a predetermined fixed length are extracted and examined against a reference look-up table, which contains the base value raised to specific powers. The substring under examination is used as a reference value to look-up the value of the base raised to the power represented by the numerical value of the bit string, and the intermediate value is stored, with a reference to the position of the least significant bit in the bit string that corresponds to the pattern. After traversal of the exponent bit string, the intermediate values are then multiplied together using a multiply chain algorithm to determine the base value raised to the original exponent value.
Computer based means of encryption and decryption of communication are well known in the art. However, most advanced encryption and decryption methods are too time consuming or memory intensive, or both, for use on small devices with limited computer usage cycles or memory. As such, there is a need for a more efficient exponentiation method in terms of both the computer cycles used and the amount of memory that is consumed.
SUMMARY OF THE INVENTION
The present invention combines two recoding methods for exponentiation in a novel way. The first method is the “signed digit algorithm” and the second is a modified “sliding window” method referred to below as the string replacement method. The combination these two methods allow data to be encrypted and decrypted using a smaller number of computer cycles and less memory than prior techniques.
The subject invention is embodied in an encryption/decryption system that performs an exponentiation operation on a base number where both the base number and the exponent may be extremely large numbers (i.e., anywhere from 100 to several thousand bits long). The exponent is expressed as a bit string. The bit string is then re-coded utilizing the signed digit algorithm to eliminate runs of ‘1's’, by replacing them with patterns of runs of ‘0's’ delimited by a ‘1’ at the bit position just above the most significant bit and ‘−1’ as the least significant bit position of the run. Predetermined substring patterns are then extracted from the exponent in a manner similar to the sliding window method. The extracted strings are compared to a previously constructed look-up table containing exponent values for only a relatively small number of predetermined substrings. At each non-zero bit in the exponent, the longest such substring ending at that position is found in the lookup table and the corresponding bits in the exponent are set to zero except the rightmost bit. In this bit position is stored a reference to the corresponding entry in the look-up table. The value returned from the look-up table is the base value raised to the power represented by the substring. The exponent bit string is traversed from right to left (i.e. from the least significant bit position to the most significant bit position) until all such substrings have been extracted and corresponding references to the look-up table have been stored. The remainin
Matsushita Electric - Industrial Co., Ltd.
Ngo Chuong Dinh
RatnerPrestia
LandOfFree
Efficient exponentiation method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient exponentiation method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient exponentiation method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3316341