Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1998-08-28
2003-05-06
Hayes, Gail (Department: 2131)
Cryptography
Particular algorithmic function encoding
C708S491000, C708S492000, C380S030000
Reexamination Certificate
active
06560336
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to encryption techniques for data security, and more particularly to a system for distributing a public key for network users to share a secret key through the use of a public key, a public key encryption system such as an El-Gamal type encryption system for network users to make a mutual secret communication through the use of a public key, and an El-Gamal type verification system, which is one of electronic signature systems, for network users to verify a correspondence and/or a transmitter, and apparatuses for operating a bivector, to be used for those systems, such as an apparatus for multiplying a bivector by an integer.
2. Description of the Related Art
Various techniques belonging to a public key encryption system wherein secret communication is made in open network base security thereof on difficulty in solving an issue of a discrete logarithm in a finite field GF(p).
For instance, a system of distributing DH type public key having been suggested by W. Diffie and M. Hellman, New directions in cryptography, IEEE, Trans. Inf. Theory, IT-22, 6, pp. 644-654, and El-Gamal cryptography and signature systems having been suggested by T. E. El-Gamal, A public key cryptosystem and a signature scheme based on discrete logarithm, Proc. Crypto 84, 1984, base security thereof on that an issue of a discrete logarithm in a finite field GF(p) is quite difficult to solve.
Hereinbelow is explained the issue of a discrete logarithm in a finite field GF(p). It is now supposed that p indicates a prime number, and that GF(p) operates an integer N equal to or greater than 0, but smaller than p (N=0, 1, 2, - - - , p−1), with the prime number being used as a modulo. It is also supposed that the following equation is established.
Y=&agr;
X
mod
p
(1
≦X≦p
−1)
In the equation, a indicates &agr; certain fixed primitive root of GF(p). That is, elements of GF(p), 1, 2 - - - , p−1, other than 0 can be represented in the form of &agr;
K
where K indicates a certain number. Under those suppositions, X is called a logarithm of Y in GF(p) with the prime number p acting as a base.
It is easy to calculate Y on the basis of X. Specifically, what is required to do so is to merely conduct multiplication by the number of 2×log
2
X. To the contrary, it is quite difficult to calculate X on the basis of Y, even if there would be employed an algorithm which is best among presently known algorithms. An amount of calculation for obtaining X on the basis of Y is almost the same as an amount of calculation for prime factor factorization of a composite number having almost the same magnitude as that of the prime number p. A difficulty in calculating X on the basis of Y is called a discrete logarithm problem.
In accordance with the above-mentioned DH type public key distribution system, a first user A and a second user B can share a common key K, which is secret data, with the common key K being kept secret to others, even though open network is utilized. This is based on that the above-mentioned discrete logarithm problem is quite difficult to solve.
A prime number p and a primitive root &agr; are in advance informed to others as open data. The first user A randomly selects an integer X
A
in the range of 0 and (p−1), and the thus selected integer X
A
is kept secret. Similarly, the second user B randomly selects an integer X
B
in the range of 0 and (p−1), and the thus selected integer X
B
is kept secret. The first user A calculates the following equation.
Y
A
=&agr;
XA
mod
p
(1
≦Y
A
≦p
−1)(“XA” means “X
A
”. The same applies to “XB”, “XU” etc., hereinbelow.)
Then, the first user A transmits a calculation result Y
A
to the second user B. Similarly, the second user B calculates the following equation.
Y
B
=&agr;
XB
mod
p
(1
≦Y
B
≦p
−1)
Then, the second user B transmits a calculation result Y
B
to the first user A.
After the calculation results Y
A
and Y
B
have been exchanged, the first user A calculates the common key K, as follows.
K=Y
B
XA
mod
p
=(&agr;
XB
mod
p
)
XA
mod
p=&agr;
XAXB
mod
p
(1
≦K≦p
−1)
Similarly, the second user B calculates the common key K, as follows.
K=Y
A
XB
mod
p=(&agr;
XA
mod
p
)
XB
mod
p=&agr;
XAXB
mod
p
(1
≦K≦p
−1)
Thus, the first and second users A and B can share the common key K (K=&agr;
XAXB
mod p) in secret.
Thereafter, the first and second users A and B can make secret communication therebetween through the use of the common key K. In the above-mentioned procedure, only the calculation results Y
A
and Y
B
are on open network. Since it would be necessary to solve the discrete logarithm problem in order to obtain the integers X
A
and X
B
both of which are secret data, a third party cannot know the common key K on the premise that the discrete logarithm problem is quite difficult to solve.
In accordance with the above-mentioned El-Gamal encryption system, it is possible to make a secret communication on open network as follows, based on the fact that the discrete logarithm problem is difficult to solve.
A prime number p and a primitive root &agr; are in advance informed to others as open data. Each of users U randomly selects an integer X
U
, and the thus selected integer X
U
is kept secret. In addition, each of users U calculates the following equation.
Y
U
=&agr;
XU
mod
p
(1
≦Y
U
≦p
−1)
Then, each of users U transmits the calculation result Y
U
to other users as a public key.
Herein, it is supposed that a first user A transmits a correspondence M to a second user B in secret. First, the first user A makes the following ciphers C
1
and C
2
through the use of a random number K which only the first user A knows, and a public key Y
B
of the second user B.
C
1
=&agr;
K
mod
p
C
2
=
M×Y
B
K
mod
p
Then, the first user A transmits the ciphers C
1
and C
2
to the second user B. The second user B having received the ciphers can obtain the correspondence M by calculating the following equation through the use of an integer X
B
which only the second user B knows.
M=C
1
−XB
×C
2
mod
p
In the above-mentioned El-Gamal encryption system, only the ciphers C
1
and C
2
are on open network. Since it would be necessary to solve the discrete logarithm problem in order to obtain the random number K and the correspondence M both of which are secret data, a secret communication can be made on the premise that the discrete logarithm problem is quite difficult to solve.
In accordance with the above-mentioned El-Gamal signature system, electronic signature can be accomplished as follows, based on the fact that it is quite difficult to solve the discrete logarithm problem.
A prime number p and a primitive root &agr; are in advance informed to others as open data. A certifier U randomly selects an integer X
U
as a signature key, and the thus selected integer X
U
is kept secret. In addition, the certifier U calculates the following equation.
Y
U
=&agr;
XU
mod
p
(1
≦Y
U
≦p
−1)
Then, the certifier U discloses the calculation result Y
U
to others as a verification key.
Herein, it is supposed that a verifier V verifies a signature made to a correspondence M of the certifier U. First, the certifier U makes the following signatures R and S through the use of a random number K which only the certifier knows, and a signature key X
U
of the certifier U itself.
R=&agr;
K
mod
p
S
=(
M=X
U
×R
)×K
−1
mod
p
Then, the certifier U transmits a correspondence M together with the signatures R and S to the verifier V. The verifier V having received the signatures R and S verifies whether the following equation is established through the use of a verification key Yu of the certifier U.
&agr;
M
=Yu
R
×R
S
mod
p
In the above-mentioned El-Gamal signature system, only the correspondence M and the signature
Foley & Lardner
Hayes Gail
Seal James
LandOfFree
Apparatus for operating double vector and encrypting system... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus for operating double vector and encrypting system..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus for operating double vector and encrypting system... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3001059