Encryption and decryption devices for public-key cryptosystems and recording medium with their processing programs recorded thereon
AssigneeTelegraph and Telephone Corporation
InventorsShigenori Uchiyama, Tatsuaki Okamoto
Life of this patent
Estimating the term…
Abstract
In a public-key cryptosystem based on a multiplicative group, n=p2q, where p and q are odd primes, and g, selected from (Z/nZ)* such that gp=gr−1 mod p2 has an order of p in (Z/ p2Z)*, are made public. A plaintext m, a random number and n are used to calculate m+rn, and n and g are used to compute C=gm+rn mod n to generate it as ciphertext. For the ciphertext C, C mod p2 is calculated, then Cp=Cp−1 mod p2 is calculated to obtain (Cp−1)/p=L(Cp), and L(Cp) is multiplied by a secret key L(gp)−1 mod p to obtain the plaintext m.
Claims31
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.
A decryption device for a public-key cryptosystem comprising:
- Γ-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.
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.
A recording medium on which is recorded a program for executing a decryption process of a decryption device through the use of first and second public keys n and g, wherein said program comprises:
- 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.
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.
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.
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.
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.
Dependencies are inferred from the claim text.