METHOD AND DEVICE FOR CRYPTOGRAPHIC KEY GENERATION
A method and a device for generation of a cryptographic key pair for use in a (generalized) Goldwasser-Micali cryptosystem. The device generates a first prime p≡1 (mod 2 k ), where k≧1 is an integer, and a second prime q≡3 (mod 4) or q≡1 (mod 4); computes a modulus N=pq; picks an integer y∈ N \ N , where N is a set of integers whose Jacobi symbol is 1 and N is a set of quadratic residues; and outputs a public key pk={N,y,k} and a private key sk={p,k}.
1 . A method for generation of a cryptographic key comprising, in a device:
generating a first prime p≡1 (mod 2 k ), where k≧1 is an integer;
generating a second prime q≡3 (mod 4) or q≡1 (mod 4), q≡1 (mod 2 k );
computing a modulus N that is a multiple of the product between the first prime p and the second prime q;
picking an integer y∈ N \ N , where N is the set of integers whose Jacobi symbol is 1 and N is the set of quadratic residues; and
outputting a public key pk={N,y,k}.
2 . The method of claim 1 , further comprising generating a private key sk={p,k}.
3 . The method of claim 2 , further comprising storing the private key sk.
4 . The method of claim 1 , wherein the public key pk is for use in a cryptosystem in which a message m∈ , where ={0,1} k , is encrypted by picking a random x∈ N * and calculating a ciphertext c=y m x 2 k mod N.
5 . A cryptographic device comprising at least one processing unit configured to:
generate a first prime p≡1 (mod 2 k ), where k≧1 is an integer;
generate a second prime q≡3 (mod 4) or q≡1 (mod 4), q≡1 (mod 2 k );
compute a modulus N that is a multiple of the product between the first prime p and the second prime q;
pick an integer y∈ N \ N , where N is the set of integers whose Jacobi symbol is 1 and N is the set of quadratic residues; and
output a public key pk={N,y,k}.
6 . The cryptographic device of claim 5 , wherein the at least one processing unit is further configured to generate a private key sk={p,k}.
7 . The cryptographic device of claim 6 , wherein the at least one processing unit is configured to store the private key sk.
8 . The cryptographic device of claim 7 , wherein the at least one processing unit is configured to store the private key sk in a memory or in the at least one processing unit.
9 . The cryptographic device of claim 5 , wherein the at least one processing unit is configured to output the public key via a communication interface.
10 . The cryptographic device of claim 9 , wherein the at least one processing unit is configured to use a communication protocol to output the public key via the communication interface.
11 . The cryptographic device of claim 5 , wherein the cryptographic device belongs to one of the group of: a mobile device, a communication device, a game device, a set top box, a TV set, a tablet, a laptop and a cryptographic chip.
12 . The cryptographic device of claim 5 , wherein the public key pk is for use in a cryptosystem in which a message m∈ , where ={0,1} k , is encrypted by picking a random x∈ N * and calculating a ciphertext c=y m x 2 k mod N.
13 . A non-transitory computer program product storing instructions that, when executed by a at least one processor, perform the method of claim 1 .