Patent ID: 7356140

Claim:
An encrypting device comprising: key generation means for generating two prime numbers p and q of which product is n=pq as a private key and generating as a public key g1 and g2 respectively given by the following Equations (1) and (2) using two random numbers s and t and a maximal generator g in a multiplicative group of integers modulo n; and encrypting arithmetic means for, in response to receipt of a plaintext m, generating a ciphertext C=(C1, C2) respectively given by the following Equations (3) and (4) using the public key {g1, g2}, a private key n, and random numbers r1 and r2, g 1 =g s(pâˆ’1) (mod n),â€ƒâ€ƒ(1) g 2 =g t(qâˆ’1) (mod n),â€ƒâ€ƒ(2) C 1 =mÂ·g 1 r1 (mod n),â€ƒâ€ƒ(3) C 2 =mÂ·g 2 r2 (mod n),â€ƒâ€ƒ(4) where gcd{s, qâˆ’1}=1 and gcd{t, pâˆ’1}=1.