Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-03-10
2003-05-20
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06567832
ABSTRACT:
This application is based on an application No. H11-069104 filed in Japan, the content of which is hereby incorporated by reference.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to exponentiation techniques and elliptic curve exponentiation techniques for use in areas such as cryptography.
2. Description of the Prior Art
Cryptographic communications allow specific terminals to securely communicate with each other in a network coupled to a plurality of terminals. One of cryptographic systems used for such cryptographic communications is the so-called public key cryptosystem. Examples of public key cryptosystems are the RSA (Rivest-Shamir-Adelman) and ElGamal systems. These public key cryptosystems perform exponentiation in encryption or decryption processing, in such a way as to exponentiate a message by an encryption key or exponentiate a ciphertext by a decryption key.
Another type of public key cryptosystems is a cryptosystem that uses elliptic curves. While other public key cryptosystems take a finite field as the domain of definition, the elliptic curve cryptosystem takes an elliptic curve as the domain of definition and performs elliptic curve exponentiation in encryption or decryption processing.
It is to be noted that exponentiation and elliptic curve exponentiation are used not only in the public key cryptosystems but in digital signature and message authentication schemes.
Knuth's binary method (see D. E. Knuth “Seminumerical Algorithms”
The Art of Computer Programming
, vol. 2 (1981)) is widely known as an algorithm for exponentiation and elliptic curve exponentiation. Also, the signed binary method (see F. Morain & J. Olivos “Speeding up the Computations on an Elliptic Curve using Addition-Subtraction Chains”
Theoretical Informatics and Applications
, vol. 24, no.6 (1990)) and the small window method (see the same document by Knuth) are known as improvements to the binary method. Further, Japanese Laid-Open Patent Application No. H07-049769 devises an improved signed binary method.
These conventional techniques are outlined below, taking modular exponentiation as an example.
(Binary Method)
The binary method, when given a binary representation ki(n>i≧0) (where ki takes 0 or 1) of some exponent k, performs n−1 modular squarings and a number of modular multiplications equivalent to a number of ones in ki, to obtain a modular exponentiation value.
Let the binary representation ki(4>i≧0))=1011. The binary method computes an exponentiation A
1011
using arithmetic expressions given in FIG.
8
.
First, 1 is assigned to x as an initial value. The most significant bit (MSB) of the exponent is interpreted as the first bit. If the first bit is 1, an operation of squaring x and setting x
2
as x and an operation of multiplying x by A are performed in sequence. If the first bit is 0, only an operation of squaring x and setting x
2
as x is performed. The same is repeated for each of the other bits of lesser significance. Consequently, x obtained after the least significant bit (LSB) has been processed is the exponentiation value A
1011
.
FIG. 9
is a flowchart showing the procedure of the binary method. In descending order from i=n−1, the value of ki is checked (S
71
and S
76
). If and only if ki=1 (S
74
), a modular multiplication is performed (S
75
). Meanwhile, a modular squaring is performed regardless of whether ki is 1 or 0 (S
73
). For a randomly chosen exponent k, this method takes n/2 modular multiplications on average. Also, since the exponent k is expressed in the ordinary binary representation, the method requires a storage of n bits for the exponent k.
FIG. 4
is a block diagram showing the general construction of a modular exponentiation device that carries out the above modular exponentiation.
In the figure, an exponent processing unit
101
processes an exponent k and also controls an exponentiation operation in an operating unit
106
. Once the exponent k of n bits has been inputted in the modular exponentiation device through an input line
102
, the exponent processing unit
101
accepts the exponent k as an initial value and processes the exponent k. The exponent processing unit
101
then outputs a control signal via an output line
103
to the operating unit
106
, to control the exponentiation operation in the operating unit
106
. In the meantime, a base A to be exponentiated by the exponent k is inputted in the modular exponentiation device via an input line
104
and received by the operating unit
106
. The operating unit
106
performs the exponentiation operation, including modular squarings and modular multiplications, modulo a prime p for the base A, in accordance with the control signal. As a result, a modular exponentiation value A
k
mod p is obtained and outputted from the operating unit
106
via an output line
105
. Here, the prime p which acts as the modulus has been retained in the modular exponentiation device beforehand.
FIG. 10
is a block diagram showing the detailed construction of the exponent processing unit
101
.
In the figure, a holding register
601
has an n-bit storage for holding the exponent k. The exponent k inputted in the modular exponentiation device is passed through an input line
602
to the holding register
601
as the initial value. A shifting unit
605
shifts the content of the holding register
601
by 1 bit to the left, as a result of which the MSB is shifted out and abandoned. This MSB is outputted from the holding register
601
via an output line
606
to the operating unit
106
as the control signal, according to which the processing content of the operating unit
106
is determined.
FIG. 11
is a block diagram showing the detailed construction of the operating unit
106
. An intermediate value register
701
holds an intermediate value generated during the exponentiation operation. A constant
1
is inputted via an input line
702
into the intermediate value register
701
as an initial value. A squaring unit
703
performs a modular squaring on the intermediate value held in the intermediate value register
701
and outputs the result. A multiplying unit
704
performs a modular multiplication on the output of the squaring unit
703
by the base A and outputs the result. A selector
707
selects a new intermediate value to be stored in the intermediate value register
701
, according to the control signal given from the exponent processing unit
101
. If the control signal is 0, the selector
707
selects the output of the squaring unit
703
, whereas if the control signal is 1, the selector
707
selects the output of the multiplying unit
704
. After the above procedure is repeated for all n bits of the exponent k, A
k
mod p is outputted through an output line
708
.
(Signed Binary Method)
The signed binary method, when given a binary representation ki(n>i≧0) (where ki takes 0 or 1) of some exponent k, transforms ki into a signed binary representation k′i(n≧i≧0) (where k′i takes 0, 1, or −1), and performs n modular squarings and a number of modular multiplications equivalent to a number of ones and minus ones in k′i, to obtain a modular exponentiation value. For instance, letting the binary representation ki(4>i≧0)=1111, then the signed binary representation is k′i(4≧i≧0))=1000(−1). Thus, when ki has a large number of consecutive ones, k′i will end up having a large number of zeros, thereby reducing the number of modular multiplications by the increase of zeros.
FIG. 12
is a flowchart showing the procedure of the signed binary method. In the figure, steps S
101
~S
106
constitute the process of transforming a binary representation ki into a signed binary representation k′i, and steps S
107
~S
114
constitute the process of applying the binary algorithm to the signed binary representation k′i. The latter process is analogous to the original binary method described above.
To transform the binary representation ki into
Matsuzaki Natsume
Ono Takatoshi
Do Chat C.
Ngo Chuong Dinh
LandOfFree
Device, method, and storage medium for exponentiation and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Device, method, and storage medium for exponentiation and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Device, method, and storage medium for exponentiation and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3001698