Source: https://patents.google.com/patent/US6480605?oq=5%2C870%2C513
Timestamp: 2018-03-24 21:07:23
Document Index: 336768592

Matched Legal Cases: ['art 110', 'art 130', 'art 140', 'art 210', 'art 220', 'art 230', 'art 240', 'art 210', 'art 220', 'art 210', 'art 230', 'art 230', 'art 220', 'art 220', 'art 210', 'art 230', 'art 230', 'art 220', 'art 220', 'art 210', 'art 230', 'art 230', 'art 220', 'art 230', 'art 240', 'art 230', 'art 520', 'art 520', 'art 520', 'art 520']

US6480605B1 - Encryption and decryption devices for public-key cryptosystems and recording medium with their processing programs recorded thereon - Google Patents
Encryption and decryption devices for public-key cryptosystems and recording medium with their processing programs recorded thereon Download PDF
US6480605B1
US6480605B1 US09213927 US21392798A US6480605B1 US 6480605 B1 US6480605 B1 US 6480605B1 US 09213927 US09213927 US 09213927 US 21392798 A US21392798 A US 21392798A US 6480605 B1 US6480605 B1 US 6480605B1
US09213927
That is, the use of public-key cryptosystem permits the implementation of digital signature schemes, and ensures verification of the opponent of communication. It is well-known in the art that the public-key cryptosystem can be implemented through utilization of what is called a trapdoor one-way function. A one-way function is one that allows ease in computation in one direction but makes computation in the opposite direction infeasible in terms of computational complexity. The trapdoor one-way function mentioned herein is a one-way function with a trick “knowledge of some secret allows ease in computation in the opposite direction as well.” The trick is called a “trapdoor.”
For the elliptic curve and elliptic curve cryptosystems, see, for example, Menezes, A. J., “Elliptic Curve Public Key Cryptosystems,” Kluwer Academic Publishers (1993) (hereinafter referred to as Literature 1). The cryptosystems described in this literature are typical examples expected to use the one-way function. Typical and practical ones of public-key cryptosystems proposed at present are, for instance, the RSA cryptosystem, the Rabin cryptosystem, the ElGamal cryptosystem, and the elliptic curve cryptosystem (elliptic ElGamal cryptosystem). The RSA and Rabin cryptosystems are based on the intractability of IFP, the ElGamal cryptosystem is based on the intractability of DLP, and the elliptic curve cryptosystem is an Elgamal cryptosystem in a group of points on an elliptic curve over a finite field, which is based on the intractability of ECDLP.
The RSA cryptosystem is disclosed in Rivest, R. L. et al “A Method for Obtaining digital Signatures and Public-Key Cryptosystems,” Communication of the ACM, vol. 21, pp. 120-126 (1978) (hereinafter referred to as Literature 2). The Rabin cryptosystem is disclosed in Rabin, M. O. “Digital signatures and Public-Key Functions as in tractable as Factorization,” MIT, Technical Report, MIT/LSC/TR-212 (1979) (hereinafter referred to as Literature 3). The ElGamal cryptosystem is disclosed in ElGamal, T. “A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms,” IEEE Trans. on Information Theory, IT-31, 4, pp. 469-472 (1985) (hereinafter referred to as Literature 4). The elliptic curve cryptosystem was proposed by Miller, V. S. and Kolblitz, N. separately in 1985, and this scheme is described in Miller, V. S. “Use of Elliptic Curves in Cryptography,” Proc. of Crypto '85, LCNCS 218, springer-Verlag, pp. 417-426 (1985) (hereinafter referred to as Literature 5) and in Kolblitz, N., “Elliptic Curve Cryptosystems,” Math. Comp., 48, 177, pp. 203-209 (1987) (hereinafter referred to as Literature 6).
The Rabin cryptosystem is constructed as follows: Choose p, q and n in the same manner as in the above, and determine the integer b which satisfies 0bn. The encryption process E(M) and the description process D(c) are defined by the following equations using (n, b) as public keys and (p, q) as secret keys. C ≡ E  ( M ) ≡ M  ( M + b )   ( mod   n ) ( 4 ) M ≡  D  ( C ) ≡ ( - b ± ( b 2 + 4  C ) 1 / 2 ) / 2   ( mod   p ) ≡  ( - b ± ( b 2 + 4  C ) 1 / 2 ) / 2   ( mod   q ) ( 5 )
The Rabin cryptosystem involves solving simultaneous equations in decryption, but since the quadratic equation possesses two solutions, the calculation in this case brings about four solutions, giving rise to a problem that the decryption cannot uniquely be performed under the above conditions. This can be settled as a problem of system operation by using some additional information for communication; and the Rabin cryptosystem has also been improved for unique description. This is described in Kaoru Krosawa et al., “Public-Key Cryptosystems Using Reciprocals which are as Intractable as Factoring,” Journal of IEICE, Vol. J70-A, No. 11, pp. 1632-1636 (1987) (hereinafter referred as to Literature 7).
E(a, b): y 2 =x 3 +ax+b
where a, bεF p, and 4a 3+27b 2≠0
The RSA cryptosystem may be completely be analyzed by a method other than that of factoring the public key n into a prime factor, but it has been proven that only the factoring of the public key n is effective in complete analysis of the Rabin cryptosystem. That is, although it is still unknown whether the analysis of the RSA cryptosystem is equivalent to solving the IF problem, it has been proved that complete analysis of the Rabin cryptosystem is equivalent to solving the IF problem. The same is true of an inverse version of the Rabin cryptosystem. This finding on the Rabin cryptosystem has demonstrated for the first time that a certain kind of security of the cryptosystem can be proved by the assumption of the intractability of a basic problem (the IF problem in this case). This means that the security of above-described public-key cryptosystems against the passive attacks has been proved on the assumption of the intractability of the IF problem. Conversely, this is a proof that the Rabin cryptosystem is weak against the active attacks. An efficient cryptosystem, which is secure against the chosen ciphertext attack, is disclosed, for example, in Bellare et al., “Optimal Asymmetric Encryption,” Proc. of Eurocrypt 194, LCNCS 950, Springer-Verlag, pp. 92-111, 1995 (hereinafter referred to as Literature 8).
As regards fractional or partial cryptoanalysis, it has been proved on the RSA and Rabin cryptosystem that the computation of the least significant bit of the plaintext M from the ciphertext is as difficult as the computation of the whole plaintext M from the ciphertext C. It has also been proved that the portion of the plaintext corresponding to log k bits continuing from its least significant bit possesses similar security. This is described in Alexi, W. et al., “RSA and Rabin functions: certain parts Are as Hard as the Whole,” SIAM Journal of computing, 17, 2, pp. 449-457 (1988) (hereinafter referred to as Literature 9).
As described above, the public-key cryptosystems solves the key management problem raised in the conventional common-key cryptosystem, and permit implementation of digital signature schemes. However, the public-key cryptosystems, for which a certain kind of security can be proved by assuming the intractability of the basic problem are limited only to the Rain cryptosystem and its modifications. That is, actually usable one-way functions are only IFP, DLP and ECDLP. No provably secure public-key cryptosystem has been implemented which uses a new “trapdoor” based on such a known one-way function.
It is therefore an object of the present invention to provide encryption and decryption devices for public-key cryptosystems which use IFP as a one-way function but uses a new “trapdoor” and which can be proved to be secure against passive adversaries based on the assumption that IFP is intractable.
FIG. 1 is a block diagram illustrating the functional configuration of an embodiment of each of encryption and decryption devices in a “public-key cryptosystem based on a multiplicative group” according to the present invention;
FIG. 3 is a block diagram illustrating the functional configuration of “modification 1 of the public-key cryptosystem based on the multiplicative group” employing other embodiments of the encryption and encryption devices according to the present invention;
FIG. 8 is a block diagram illustrating the functional configuration of each of embodiments of encryption and decryption devices in a “public-key cryptosystem based on elliptic curves” according to the present invention;
More specifically, the present invention offers two kinds of public-key cryptosystem: (a) a public-key cryptosystem which is constructed on a modular-n reduced residue class group (Z/nZ)*, where n=p2q, p and q being primes; and (b) a public-key cryptosystem which is constructed on an elliptic curve En defined on a modular-n reduced residue class group Z/nZ, where n=pq. The former will hereinafter be called a “public-key cryptosystem based on a multiplicative group” and the latter a “public-key cryptosystem based on an elliptic curve.”
Through utilization of this property, it is possible to construct a novel “trapdoor” and hence a novel public-key cryptosystem.
The public-key cryptosystem based on the multiplicative group according to the present invention will be described below as being applied to a public-key cryptosystem which is constructed on a modular-n reduced residue class group (Z/nZ)*, where n=p2q, p and q being primes. From the Chinese remainder theorem (for example, Okamoto and Yamamoto, “Modem Cryptography,” pp.15, Sangyo Tosho (1997) (hereinafter referred to as Literature 12), the following equations hold:
(Z/nZ)*≅(Z/p 2 Z)*×(Z/qZ)* (20)
≅Γ×(Z/pZ)*×(Z/qZ)* (21)
Therefore, the “public-key cryptosystem based on the multiplicative group” is defined as described below. Determine g in gε(Z/nZ)* such that gp=gp−1 mod p2εΓ satisfies L(gp)≠0 mod p, and let n, g, k be public keys, where k is the numbers of bits of primes p and q. Assuming that the plaintext m is a natural number chosen in the range of 0≦m≦2k−1, r is arbitrarily selected from Z/nZ and the encryption is defined by
In the “public-key cryptosystem based on the multiplicative group” according to the present invention, the encryption device comprises an exponent generation part which combines a plaintext and a random number to generate an exponent part for a modular-n exponentiation, and an n-exponentiator for performing a modular-n exponentiation. A ciphertext generated by the n-exponentiator is provided onto a communication line, for instance. On the other hand, the decryption device comprises a Γ-transformation part for performing a p−1 exponentiation modulo p2, and a discrete logarithm solution part for solving a discrete logarithm problem in a subgroup Γ to decrypt the ciphertext.
A description will be given first of the basic functional configuration of the “public-key cryptosystem based on the multiplicative group” according to the present invention and then of embodiments of each part thereof.
C p−1 =g (p−1)(m+rn) =g p m ×g p rnmod p 2 =g p mmod p 2 (25)
Now, it will be proved that the “public-key cryptosystem based on the multiplicative group” is secure against passive adversaries or attacks, by proving that the analysis of the cryptosystem is equivalent to the factorization of n.
If an algorithm is available which factorizes n with non-negligible probability, it is possible to construct a probabilistic polynomial time algorithm for analyzing the “public-key cryptosystem based on the multiplicative group.” Hence, only the following fact will be proved in this instance.
“If an algorithm A is available which analyzes the ‘public-key cryptosystem’ with non-negligible probability, then it is possible to construct a probabilistic polynomial time algorithm for factoring.”
What is intended to mean by the “algorithm for facotring n with non-negligible probability” is an algorithm which ensures factoring of n by repeatedly applying the algorithm on the order of a polynomial using the number of bits of the input n as a variable. The same holds true in the following description (see Literature 12 for its strict definition).
Now, given a composite number n (=p2q), gε(Z/nZ)* randomly selected can be used as a parameter of the public-key cryptosystem of the present invention with non-negligible probability. Next, it is possible to prove that the difference between the distribution of x mod p LCM(p−1, q−1), where x is randomly selected from Z/nZ, and the distribution of m+rn mod p LCM(p−1, q−1) for m+rn, which appears in the encryption procedure of the public-key cryptosystem according to the present invention is negligible. For this reason, the algorithm A recognizes that C calculated by C=gx mod n, where x is randomly selected from Z/nZ, is a ciphertext with non-negligible probability, and the algorithm A outputs a plaintext x0 corresponding to C. Now, since the probability that x is a number in the range of x<2k−1 is negligible, it may be set such that x≧2k−1 with non-negligible probability. In this case, x≡x0 (mod p) does not hold, and x≡x0 (mod n) does not hold because of xo<2k−1. Accordingly, if GCD(x−x0, n) is calculated, it value becomes any one of p, pq and p2, permitting factoring of n. Thus, it is possible to factor n in a time on the order of probabilistic polynomial using its bit number as a variable. In other words, the analysis of the public-key cryptosystem of the present invention is equivalent to factoring of n—this proves that the cryptosystem is secure against passive adversaries.
Next, a description will be given of a concrete example of the “public-key cryptosystem based on the multiplicative group” according to the present invention. As illustrated in FIG. 1, an encryption device 100 and a decryption device 200 are connected via a communication line 300. The encryption device 100 comprises an exponent generation part 110, a modular-n exponentiator 120, a storage part 130 for storing predetermined values n and g, and a control part 140 for controlling operations of these parts. The decryption device 200 comprises a Γ-transform part 210, a discrete logarithm solution part 220, a storage part 230 and a control part 240 for controlling operations of these parts.
Next, the decryption process in the decryption device 200 will be described below. A detailed configuration of the Γ-transform part 210 in the decryption device 200 is depicted in FIG. 2A. A detailed configuration of the discrete logarithm solution part 220 is depicted in FIG. 2C. Upon receiving the ciphertext C from the communication line 300, the Γ-transform part 210 in the decryption device 200 calculates mod p2 in a mod p2-reducer 211 using a value p2 read out of the storage part 230, and inputs the value mod p2 into a Γ-transformer 212. The Γ-transformer 212 computes Cp=Cp−1 mod p2 using p2 and p read out of the storage part 230, and provides the value Cp to the discrete logarithm solution part 220. The discrete logarithm solution part 220 provides the value Cp from the Γ-transform part 210 to a logarithm calculator 221, which calculates L(Cp) by Eq. (16) using the value p read out of the storage part 230. The value L(Cp) is input into a multiplier 222, which calculates L(Cp)×L(gp)−1 mod p using L(gp)−1 mod p read out of the storage part 230. The discrete logarithm solution part 220 outputs the thus obtained value as a decrypted plaintext m.
C p−1 =g (p−1)(M+rn)=g p M ×g p rnmod p 2 =g p Mmod p 2 (34)
C p−1 =g (p−1)(M+Rn) =g p M ×g p Rnmod p 2 =g p Mmod p 2
Accordingly, M can similarly be computed by Eqs. (35), (36), (37) and (38), and the plaintext m can be obtained from the high-order k0 bits of M and thus decrypted.
The discrete logarithm solution part 220 provides the value Cp from the Γ-transform part 210 to the logarithm calculator 221, which calculates L(Cp). The value L(Cp) and L(gp)−1 mod p read out of the storage part 230 are input into the multiplier 222, which calculates M=L(Cp)×L(gp)−1 mod p. The value M and k0 read out of the storage part 230 are provided to a bit separator 223 to extract the high-order k0 bits of the value M, and this value is output as the decrypted plaintext m from the discrete logarithm solution part 220. The sequential control of the respective parts and the readout control of the storage part 230 are effected by the control part 240. It is also possible to store only p and g in the storage part 230 and obtain p2 and L(gp)−1 mod p through calculation.
An elliptic curve over the finite field Fp, which has order p, will hereinafter referred to as an anomalous elliptic curve. It is described in Jounal Takakazu Satoh et al., “Fermat Quotients and the Polynomial Time Discrete Log Algorithm for Anomalous Elliptic Curves,” COMMENTARII MATHEMATICI UNIVERSITATIS SANCTI PAULI, Vol 47, No. 1 1998 (hereinafter referred to as Literature 11) that the discrete logarithm problem on the anomalous elliptic curve can be computed with high efficiency. An algorithm for solving the discrete logarithm problem on the anomalous elliptic curve will hereinafter be referred to as an SSA algorithm.
Now, let Ep be anomalous elliptic curve and Eq a non-anomalous elliptic curve. As is the case with the above-described “public-key cryptosystem based on the multiplicative group,” n, En, the point G on En(Z/nZ) and k are published as a public key. In this instance, however, the point G is set at a value of sufficiently higher order (for example, equal to n in the number of bits), and k represents the numbers of bits of the primes p and q. Letting the plaintext be selected in the range of 0<m<2k−1, r is arbitrarily selected from Z/nZ, and the encryption is defined by the following equation:
In the “public-key cryptosystem based on elliptic curves” according to the second embodiment, the encryption device comprises an exponent generation part which combines a plaintext and a random number into an exponent part for an exponentiation in En(z/nZ), and an En-exponentiator which performs an exponentiation in En(z/nZ), and the ciphertext generated by the En-exponentiator is sent over a communication line. On the other hand, the decryption device comprises a mod p-reducer which transforms a point on En(Z/nZ) to a point on Ep(Fp), and an SSA algorithm part which solves the discrete logarithm problem on Ep(Fp) for decryption of the ciphertext.
Next, a description will be given of the method of construction of cryptography of the “public-key cryptosystem based on elliptic curves” and the equivalence of its analysis to the modified factoring problem.
#E q(F q)=q′=q+1−t
which are assumed to satisfy −2q½≦t≦2q½ and t≠1, q′≠p. The symbol # represents the number of elements of a set. As a method for constructing an elliptic curve with an expected order there is proposed a relatively efficient method which utilizes a complex multiplication theory; in particular, the generation of the anomalous elliptic curve is described, for example, in Miyaji, A., “Elliptic Curve Suitable for Cryptography,” IEICE Trans. Fundamentals, E76-A, 1, pp. 50-54 (1993) (hereinafter referred to as Literature 13). Assume that point Gp and Gq on the elliptic curves Ep(Fp) and Eq(Fq) are chosen which have orders ord(Gp)=p and ord(Gq)=q′. Although the elliptic curve Eq(Fq) does not usually form a cyclic group, it is assumed so here for the sake of brevity. In general, it is possible to choose such that q′ has a sufficiently large prime and select, as Gq, the point where the order is the large prime. This is followed by constructing the elliptic curve En on Z/nZ through the use of the Chinese remainder theorem.
By proving that the analysis of the “public-key cryptosystem based on elliptic curves” is equivalent to factoring of n based on information such as the public keys (n, En, G, k), it is proved that the public-key cryptosystem based on elliptic curves is secure against passive adversaries.
If there is available an algorithm which factors n with non-negligible probability, a probabilistic polynomial time algorithm which analyzes the “public-key cryptosystem based on elliptic curves” can apparently be constructed. Accordingly, only the following fact will be proved.
“If an algorithm B is available which analyzes the ‘public-key cryptosystem based on elliptic curves’ with non-negligible probability, it is possible to construct a probabilistic polynomial time algorithm for factoring n”
Next, a description will be given of an embodiment of the “public-key cryptosystem based on elliptic curves.”
Next, the decryption process in the decryption device 500 will be described below. A detailed configuration of the SSA algorithm part 520 in the decryption device 500 is depicted in FIG. 9B. Upon receiving the ciphertext (C) from the communication line 600, the mod p-reducer 510 in the decryption device 500 calculates Cp=C mod pεEp(Fp), and inputs Cp into the SSA algorithm part 520. As depicted in FIG. 9B, upon receiving Cp from the mod p-reducer 510, the SSA algorithm part 520 provides it to a logarithm calculator 521 to calculate λ(Cp) using the isomorphism λ and the prime p, and inputs the calculation result into a multiplier 522, which calculates λ(Cp)×λ(Gp)−1 mod p using precalculated λ(Gp)−1 mod p. The SSA part 520 outputs the thus obtained value as a decrypted plaintext m.
The table of FIG. 11 give a comparison of the cryptosystem of the first embodiment of the present invention and typical common-key cryptosystems considered practical at present, RSA, Rabin and ElGamal schemes, in terms of the computational complexities involved in encryption and decryption and security. The computation amounts are estimated using, as one unit, a modular multiplication with a natural number of 1024 bits. The parameter used in RSA is e=216+1 and the random number used in ElGamal is about 130-bit. As for security, the double circle indicates that equivalence to the basic problem (the factoring problem or discrete logarithm problem) is provable; the white circle “O” indicates that equivalence to a problem (the afore-mentioned p subgroup problem, for instance), which is a little easier than the basic problems, is provable; the cross “x” indicates that equivalence to the basic problems is not provable; and the question mark “?” Indicates that equivalence to the basic problems has not been proved.
1. An encryption device for a public-key cryptosystem comprising:
exponent generating means for generating an exponent by combining an input plaintext m and a random number r; and
exponentiating means for generating a ciphertext by exponentiating a second public key g with said exponent in a modular-n reduced residue class group, where said n is a first public key which is a composite number defined by n=p2q where p and q are odd primes having the same number k of bits.
2. The encryption device of claim 1, wherein said second public key g is selected from a modular-n reduced residue class group (Z/nZ)* such that gp=gp−1 mod p2 has an order of p in (Z/p2Z)*.
h-function operating means for transforming said plaintext m to h(m) through calculation with a hash function;
bit concatenating means for concatenating said h(m) and said plaintext m to obtain a value M=m∥h(m);
random generating means for generating said random number r;
multiplying means for multiplying said random number r and said first public key n; and
adding means for adding the multiplication result rn and said plaintext m to provide the addition result as the output from said exponent generating means.
5. The encryption device of claim 4, wherein said second public key g is selected from a modular-n reduced residue class group (Z/nZ)* such that gp=gp−1 mod p2 has an order of p in (Z/p2Z)*, the number of bits of said h(m) is k−k0−1 where 0<k0<k, and the number of bits of said plaintext m is k0.
bit concatenating means for concatenating said plaintext m and said random number to obtain a value M=m∥r;
h-function operating means for transforming said value M to R=h(M) through calculation with a hash function;
multiplying means for multiplying said R and said first public key n; and
adding means for adding the multiplication result Rn and said M to provide the addition result as the output from said exponent generating means.
7. The encryption device of claim 6, wherein said second public key g is selected from a modular-n reduced residue class group (Z/nZ)* such that gp=gp−1 mod p2 has an order of p in (Z/p2Z)*, the number of bits of said random number r is k−k0−1 where 0<k0<k, and the number of bits of said plaintext m is k0.
Γ-transform means for transforming, through the use of a first secret key, an input ciphertext C to an element Cp of a modular-n reduced residue class group, where said n is a first public key which is a composite number defined by n=p2q wherein p and q are odd primes; and
discrete logarithm solution means for solving a discrete logarithm in said transformed element Cp through the use of a second secret key.
9. The decryption device of claim 8, wherein let said input ciphertext C be an integer in the range of 0<C<n and prime to said n, said p be said first secret key and said n be said first public key, and wherein said Γ-transform means comprises:
p2-reducing means for calculating C mod p2ε(Z/p2Z)*; and
transform means for performing a modular-p2 exponentiation with p−1 on the calculation result C mod p2 to obtain said element Cp.
10. The decryption device of claim 8 or 9, wherein let gp and said Cp be integers in the ranges of 0<gp and Cp<p2 and satisfying gp≡Cp≡1 (mod p) and gp≠1 (mod p2 ), and [(gp−1)/p]−1 mod p be said second secret key, and wherein said discrete logarithm solution means comprises:
logarithm calculating means supplied with said element Cp, for calculating L(Cp)=(Cp−1)/p; and
multiplying means for performing a modular multiplication of the calculation result L(Cp) and said second secret key [(gp−1)/p]−1 mod p with said p and for outputting a decrypted plaintext.
11. The decryption device of claim 8, which, letting k be the number of bits of said odd prime p where 0<k0<k, further comprises means for outputting, as a decrypted plaintext, high-order k0 bits of the solution of said discrete logarithm solution means.
p2reducing means for calculating C mod p2ε(Z/p2Z)*; and
transform means for performing a modular-p2 exponentiation of the calculation result C mod p2 with p−1 to obtain said element Cp.
13. The decryption device of claim 12, wherein let gp and said Cp be integers in the ranges of 0<gp and Cp<p2 and satisfying gp≡Cp≡1 (mod p) and gp≠1 (mod p2 ), and [(gp−1)/p]−1 mod p be said second secret key, and wherein said discrete logarithm solution means comprises:
multiplying means for performing a modular multiplication of the calculation result L(Cp) and said second secret key [(g−1)/p]−1 mod p with said p and for outputting a decrypted plaintext.
14. A recording medium on which there is recorded a program for executing an encryption process of an encryption device through the use of first and second public keys n and g, wherein said program comprises:
an exponent generating step of generating an exponent by combining an input plaintext m and a random number r; and
an exponentiating step of generating a ciphertext C by exponentiating said second public key g with said exponent in a modular-n reduced residue class group, where said n is said first public key which is a composite number defined by n=p2q where p and q are odd primes.
15. The recording medium of claim 14, wherein said exponent generating step of said program comprises the steps of:
generating said random number r;
multiplying said random number r and said first public key n; and
adding the multiplication result rn and said plaintext m and outputting the addition result m+rn as said exponent; and
wherein said ciphertext C generating step is a step of generating said ciphertext C by performing a modular-n exponentiation of said public key g with said addition result m+rn, where said n is said first public key.
16. The recording medium of claim 14 or 15, wherein p and q have the same number of bits, and said second public key g is selected from a modular-n reduced residue class group (Z/nZ)* such that gp=gp−1 mod p2 has an order of p in (Z/p2Z)*.
multiplying said random number r and said first public key n;
transforming said plaintext m to h(m) through calculation with a hash function;
bit concatenating said h(m) and said plaintext m to obtain value M=m∥h(m); and
adding the multiplication result rn and said value M and outputting the addition result M+rn as said exponent; and
18. The recording medium of claim 17, wherein said p and q have the same number k of bits, said second public key g is selected from a modular-n reduced residue class group (Z/nZ)* such that gp=gp−1 mod p2 has an order of p in (Z/p2Z)*, the number of bits of said h(m) is k−k0−1 where 0<k0<k, and the number of bits of said plaintext m is k0.
bit concatenating said random number r and said first public key n to obtain a value M=n∥r;
transforming said value M to R=h(M) through calculation with a hash function h;
multiplying said value R and said first public key n; and
adding the multiplication result nR and said value M and outputting the addition result M+nR as said exponent; and
wherein said ciphertext C generating step is a step of generating said ciphertext C by performing a modular-n exponentiation of said public key g with said addition result M+nR, where said n is said first public key.
20. The recording medium of claim 19, wherein said p and q have the same number k of bits, said second public key g is selected from a modular-n reduced residue class group (Z/nZ)* such that gp=gp−1 mod p2 has an order of p in (Z/p2Z)*, the number of bits of said random number r is k−k0−1 where 0<k 0<k, and the number of bits of said plaintext m is k0.
a Γ-transforming step of transforming, through the use of a first secret key, an input ciphertext C to an element Cp of a modular-n reduced residue class group, where said n is said first public key which is a composite number defined by n=p2q where p and q are odd primes; and
a discrete logarithm solving step of solving a discrete logarithm in said transformed element Cp through the use of a second secret key.
22. The recording medium of claim 21 on which is recorded a program for executing a decryption process, wherein let said input ciphertext C be an integer in the range of 0<C<n and prime to said n, and wherein said Γ-transforming step in said program comprises the steeps of:
calculating an element of a modular-p2 reduced residue class group, C mod p2, for said input ciphertext C; and
performing a modular-p2 exponentiation of the calculation result C mod p2 with p−1 to obtain said element Cp.
23. The recording medium of claim 21 or 22 on which is recorded a program for executing a decryption process, wherein let gp and said Cp be integers in the ranges of 0<gp and Cp<p2 and satisfying gp≡Cp≡1 (mod q) and gp≠1 (mod p2), and said second secret key be [(gp−1)/p]−1 mod p, and wherein said discrete logarithm solving step in said program comprises the steps of:
calculating (Cp−1)/p through the use of said C and said p; and
performing a modular-p multiplication of the calculation result (Cp−1)/p by said second secret key to obtain a decrypted plaintext.
24. The recording medium of claim 21 on which is recorded a program for executing a decryption process, wherein, letting k be the number of bits of said odd prime p and 0<k0<k, said program further comprises a step of outputting, as a decrypted plaintext, high-order k0 bits of the solution obtained by said discrete logarithm solving step.
p2-reducing step for calculating C mod p2ε(Z/p2Z)*; and
transform step for performing a modular-p2 exponentiation of the calculation result C mod p2 with p−1 to obtain said element Cp.
26. The recording medium of claim 25 on which is recorded a program for executing a decryption process, wherein let gp and said Cp be integers in the ranges of 0<gp and Cp<p2 and satisfying gp≡Cp≡1 (mod p) and gp≠1 (mod p2 ), and [(gp−1)/p]−1 mod p be said second secret key, and wherein said discrete logarithm solution step comprises:
logarithm calculating step for calculating L(Cp)=(Cp−1)/p for said element Cp; and
multiplying step for performing a modular multiplication of the calculation result L(Cp) and said second secret key [(gp−1)/p]−1 mod p with said p and for outputting a decrypted plaintext.
27. An encryption device for a public-key cryptosystem comprising:
exponent generating means for generating an exponent by combining an input plaintext and a random number; and
exponentiating means for generating a ciphertext by performing a modular exponentiation of a second public key with said exponent in an elliptic curve En over a modular-n residue class ring Z/nZ with a first public key n which is a composite number defined by n=pq where p and q are odd primes.
28. A decryption device for a public-key cryptosystem comprising:
reducing means for transforming an input ciphertext to an element Cp of an elliptic curve Ep over a finite field Fp having a number p of Fp-rational points which are non-infinite points Gp and Cp; and
SSA algorithm means for calculating a discrete logarithm for said element Cp and for outputting a decrypted plaintext.
29. The decryption device of claim 28, wherein, letting p be an odd prime larger than 5 and λ(Gp)−1 mod p be a secret key, said SSA algorithm means comprises:
logarithm calculating means supplied with said element Cp, said elliptic curve Ep and said function λ, for calculating λ(Cp); and
multiplying means supplied with said λ(Cp) and said secret key, for performing a modular multiplication of said λ(Cp) and said secret key with said p and for outputting said decrypted plaintext.
30. A recording medium on which there is recorded a program for executing an encryption process of an encryption device which uses an elliptic curve En over a modular-n residue ring Z/nZ where said n is obtained by the Chinese remainder theorem from a public key, an elliptic curve Ep over a finite field Fp having a number p of Fp-rational points and an elliptic curve Eq over a finite field Fq having a number q of Fq-rational points, said program comprising:
a step of generating a random number r;
a step of multiplying said random number r by said public key n;
a step of adding the multiplication result m and an input plaintext m; and
a step of generating a ciphertext by performing a modular exponentiation of a second public key with said exponent in an elliptic curve over a modular residue ring Z/nZ with a first public key which is a composite number.
31. A recording medium on which there is recorded a program for executing a decryption process of a decryption device for decrypting an input ciphertext C, wherein let p be an odd prime larger than 5, Ep be an elliptic curve over a finite field Fp and having a number p of Fp-rational points, its two Fp-rational points be non-infinite points Gp and Cp and λ(Gp)−1 mod p be a secret key, said program comprising:
a step of performing a modular-p transformation of said input ciphertext C to one element Cp of said elliptic curve Ep over said finite field Fp, where p is said odd prime;
a step of obtaining λ(Cp) by calculating, for said element Cp, an isomorphism function λ from E(Fp) to Fp; and
a step of outputting a decrypted plaintext by performing a modular-p multiplication of said λ(Cp) and said secret key, where p is said odd prime.
US09213927 1997-12-17 1998-12-17 Encryption and decryption devices for public-key cryptosystems and recording medium with their processing programs recorded thereon Active US6480605B1 (en)
JP9-347613 1997-12-17
JP34761397A JP3402441B2 (en) 1997-12-17 1997-12-17 Public key encryption apparatus, the public key encryption decoding apparatus and decoding program recording medium
JP3156198A JP3402444B2 (en) 1998-02-13 1998-02-13 Public key encryption apparatus, the public key encryption decoding apparatus and a program recording medium
JP10-031561 1998-02-13
US6480605B1 true US6480605B1 (en) 2002-11-12
ID=26370050
US09213927 Active US6480605B1 (en) 1997-12-17 1998-12-17 Encryption and decryption devices for public-key cryptosystems and recording medium with their processing programs recorded thereon
US (1) US6480605B1 (en)
EP (1) EP0924895B1 (en)
CA (1) CA2256179C (en)
DE (1) DE69840959D1 (en)
US20130182839A1 (en) * 2011-11-28 2013-07-18 Renesas Electronics Corporation Semiconductor device and ic card
EP1249963B1 (en) * 2001-04-11 2013-01-16 Hitachi, Ltd. Method of a public key encryption and a cypher communication both secure against a chosen-ciphertext attack
CN100452695C (en) * 2002-11-29 2009-01-14 北京华大信安科技有限公司 Elliptic curve encryption and decryption method and apparatus
WO2016195552A1 (en) * 2015-06-02 2016-12-08 Telefonaktiebolaget Lm Ericsson (Publ) Method and encryption node for encrypting message
FR2759806A1 (en) 1997-02-19 1998-08-21 Gemplus Card Int cryptographic system comprising an encryption system and deciphering and key escrow system, and associated apparatus and devices
Alfered J. Menezes/handbook of applied cryptography/1997/library of congress/294-298. *
K. Koyama, "Security of Okamoto Public-Key Cryptosystem," Electronics Letters, vol. 22, No. 20, Sep. 25, 1986, pp. 1033-1034.
Taher EIGamal/a public key cryptosystem and a signature scheme based on discrete logarithms/1985/IEEE.* *
Vanstone, S.A., et al., "Elliptic Curve Cryptosystems using Curves of Smooth Order over the Ring Zn," IEEE Transactions on Information Theory, Jul. 1997, vol. 43, No. 4, pp. 1231-1237.
US8817980B2 (en) * 2011-11-28 2014-08-26 Renesas Electronics Corporation Semiconductor device and IC card
DE69840959D1 (en) 2009-08-20 grant
CA2256179C (en) 2002-05-07 grant
CA2256179A1 (en) 1999-06-17 application
EP0924895B1 (en) 2009-07-08 grant
EP0924895A3 (en) 2000-08-02 application
EP0924895A2 (en) 1999-06-23 application
Joux 2002 The Weil and Tate pairings as building blocks for public key cryptosystems
US5272755A (en) 1993-12-21 Public key cryptosystem with an elliptic curve
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:UCHIYAMA, SHIGENORI;OKAMOTO, TATSUAKI;REEL/FRAME:009688/0884