Method of implementing elliptic curve cryptosystems in digital signatures or verification and privacy communication

Claim 1

A method of implementing a privacy communication comprising following procedures: (1) a network provider provides E{GF(p)} and a basepoint BP to be used for the privacy communication to each user; (2) each user who received E{GF(p)} and the basepoint BP selects an arbitrary natural number to find a value by adding said basepoint BP the selected natural number of times on E{GF(p)}; (3) each user keeps his arbitrary selected natural number in secret, while notifying the value obtained by adding the BP said natural number of times on E{GF(p)} as his public key to a user to whom he would like to send a message; (4) two users, who are to communicate, find a value by adding the public key their respective natural number of times on E{GF(p)} as a common key; (5) the two users make an agreement on a method of arithmetic operation for the public key and the message to encipher and decipher the message using the common key; (6) one of the two users enciphers the message in accordance with the agreement using the common key to send an enciphered message to the other user; and (7) the other user, upon the receipt of the enciphered message, deciphers the enciphered message in accordance with the agreement using the common key, wherein {E(GF(p)} is defined as follows: let d be a positive integer such that gives an imaginary quadratic field Q{(-d) 1/2 } a small class number; let p be a prime number such that a prime factor of 4×p-a 2 is d×square number where a is an integer, such that one of p+1-a and p+1+a is divisible by a prime number of 30 or more digits, and such that is expressed as 2 t ±α, where t is a positive integer and α is a small positive integer; then an elliptic curve E has a finite field GF(p) as a definition field which has a solution modulo p for a class polynomial H d (x)=0 which is determined by d as a j-invariant.

Claim 2

A method of implementing a privacy communication comprising following procedures: (1) a network provider provides E{GF(p)} and a basepoint BP to be used for the privacy communication to each user; (2) each user who received E{GF(p)} and the basepoint BP selects an arbitrary natural number to find a value by adding said basepoint BP the selected natural number of times on E{GF(p)}; (3) each user keeps his arbitrary selected natural number in secret, while notifying the value obtained by adding the BP said natural number of times on E{GF(p)} as his public key to a user to whom he would like to send a message; (4) two users, who are to communicate, find a value by adding the public key their respective natural number of times on E{GF(p)} as a common key; (5) the two users make an agreement on a method of arithmetic operation for the public key and the message to encipher and decipher the message using the common key; (6) one of the two users enciphers the message in accordance with the agreement using the common key to send an enciphered message to the other user; and (7) the other user, upon the receipt of the enciphered message, deciphers the enciphered message in accordance with the agreement using the common key, wherein {E(GF(p)} is defined as follows: let d be a positive integer such that gives an imaginary quadratic field Q{(-d) 1/2 } a small class number; let p be a prime number such that a prime factor of 4×p-a 2 is d×square number where a is an integer, such that one of p+1-a and p+1+a is divisible by a prime number of 30 or more digits, and such that is expressed as 2 t ±α, where t is a positive integer and α is a small positive integer; then an elliptic curve E has a finite field GF(p) as a definition field which has a solution modulo p for a class polynomial H d (x)=0 which is determined by d as a j-invariant.

Claim 34

A method of implementing a privacy communication comprising following procedures: (1) a network provider provides E{GF(p)} and a basepoint BP to be used for the privacy communication to each user; (2) each user who received E{GF(p)} and the basepoint BP selects an arbitrary natural number to find a value by adding said basepoint BP the selected natural number of times on E{GF(p)}; (3) each user keeps his arbitrary selected natural number in secret, while notifying the value obtained by adding the BP said natural number of times on E{GF(p)} as his public key to a user to whom he would like to send a message; (4) two users make an agreement on a method of arithmetic operation for the public key, a random number, and a message to encipher and decipher the message using the notified common key and the random number; (5) one of the two users who received the public key enciphers the message in accordance with the agreement based on a random number he selected and the public key notified by the other user; (6) the one of the users sends an enciphered message to the other user who notified the public key; and (7) the other user deciphers the message enciphered in accordance with the agreement using his integer selected and kept in secret upon receipt of the enciphered message, wherein (E{GF(p)} is defined as follows: let d be a positive integer such that gives an imaginary quadratic field Q{(-d) 1/2 } a small class number; let p be a prime number such that a prime factor of 4 ×p-a 2 is d×square number where a is an integer, such that one of p+1-a and p+1+a is divisible by a prime number of 30 or more digits, and such that is expressed as 2 t ±α, where t is a positive integer and α is a small positive integer; then an elliptic curve E has a finite field GF(p) as a definition field which has a solution modulo p for a class polynomial H d (x)=0 which is determined by d as a j-invariant.

Claim 35

A method of implementing a privacy communication comprising following procedures: (1) a network provider provides E{GF(p)} and a basepoint BP to be used for the privacy communication to each user; (2) each user who received E{GF(p)} and the basepoint BP selects an arbitrary natural number to find a value by adding said basepoint BP the selected natural number of times on E{GF(p)}; (3) each user keeps his arbitrary selected natural number in secret, while notifying the value obtained by adding the BP said natural number of times on E{GF(p)} as his public key to a user to whom he would like to send a message; (4) two users make an agreement on a method of arithmetic operation for the public key, a random number, and a message to encipher and decipher the message using the notified common key and the random number; (5) one of the two users who received the public key enciphers the message in accordance with the agreement based on a random number he selected and the public key notified by the other user; (6) the one of the users sends an enciphered message to the other user who notified the public key; and (7) the other user deciphers the message enciphered in accordance with the agreement using his integer selected and kept in secret upon receipt of the enciphered message, wherein (E{GF(p)} is defined as follows: let d be a positive integer such that gives an imaginary quadratic field Q{(-d) 1/2 } a small class number; let p be a prime number such that a prime factor of 4 ×p-a 2 is d×square number where a is an integer, such that one of p+1-a and p+1+a is divisible by a prime number of 30 or more digits, and such that is expressed as 2 t ±α, where t is a positive integer and α is a small positive integer; then an elliptic curve E has a finite field GF(p) as a definition field which has a solution modulo p for a class polynomial H d (x)=0 which is determined by d as a j-invariant.