Patent ID: 7164765

Claim:
A public-key encryption method where a sender-side apparatus encrypts transmission data by using a public key of a receiver, said public-key encryption method being implemented by said sender-side apparatus performing the steps of: (a) creating a secret key given by an expression: p, q: prime numbers p≡ 3(mod 4), q≡ 3(mod 4) and further, (b) creating said public key given by an expression: N=p d q (d is odd number) k=|N| G: {0,1} k 0 →{0,1} n+k 1 hash function, H: {0,1} n+k 1 →{0,1} k 0 hash function wherein (I) said sender-side apparatus performs the steps of: (c) selecting a random number rε{0, 1} k0 for a plaintext x (xε{0, 1} n ), and (d) calculating an expression: s=x 0 k 1 ⊕G ( r ), t=H ( s )⊕ r, where, n+k 0 +k 1 =k, and further, (e) calculating an expression: w=s∥t, and (f) calculating an expression: y=w 2 mod N and defining this result y as a ciphertext so as to transmit said ciphertext to a receiver-side apparatus, (II) said receiver-side apparatus, using said secret key of itself, performs the steps of: (g) calculating, from said ciphertext y, an expression: α 0 = y p + 1 4 ⁢ mod ⁢ ⁢ p , β 0 = α 0 , α k = 1 2 ⁢ β k - 1 ⁢ ( y ⁢ ⁢ mod ⁢ ⁢ p k + 1 - β k - 1 2 p k ) ⁢ mod ⁢ ⁢ p , ⁢ ( k ⁢ > _ ⁢ 1 ) β k = ∑ i = 0 k ⁢ ⁢ α i ⁢ p i . ⁢ ( k ⁢ > _ ⁢ 1 ) , and, using this result, (h) calculating an expression: x p = ∑ i = 0 d - 1 ⁢ ⁢ α i ⁢ p i and further, (i) calculating an expression: x q = y q + 1 4 ⁢ mod ⁢ ⁢ q and, concerning each of expressions φ(x p , x q ), φ(−x p , x q ), φ(x p , −x q ), and φ(−x p , −x q ) (where, φ designates a ring isomorphism mapping from Z/(p)×Z/(q) to Z/(pq) by Chinese remainder theorem), (j) setting each of said expressions to be as given by an expression: s′∥t′ (s′ε{0,1} n+k 1 , t′ε{0,1} k 0 ) and (k) calculating an expression: r′=H ( s′ )⊕ t′, x′∥z′=s′⊕G ( r′ ) (x′ε{0,1} n , z′ε{0,1} k 1 ) and (I) obtaining a decryption result given by an expression: { x ′ if ⁢ ⁢ z ′ = 0 k 1 * otherwise where, it is stipulated that, in a case where said decryption result is * or invalid, said receiver-side apparatus denies said ciphertext, wherein p and q are prime numbers, wherein (N, k, G, H) represents a public key, and each of N, k, G, and H represent a function of the public key, wherein n is a natural number, wherein r is a random number, wherein Z represents an aggregate of integers, and wherein d is an integer.