This is the
talk page for discussing improvements to the
Probabilistic encryption article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
![]() | This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||
|
Would it not use a pseudo-random generator? -- KayEss 07:53, 9 Oct 2004 (UTC)
The Goldwasser-Micali scheme is simple and secure (under an appropriate hardness assumption). I think it might be a better example than OAEP or the general "pad-then-encrypt" discussion, because there are problems with the security of OAEP.
In the GM cryptosystem, (n,y) is the public key, where n is a product of two large primes p,q, and y is a non-square (mod n) of Jacobi symbol 1. (p,q) is the secret key. Encryption is bit-by-bit. To encrypt a 0, send a random square mod n. That is, pick r from Z_n^* and send r^2 mod n. To encrypt a 1, send a random non-square mod n. That is, pick r from Z_n^* and send y*r^2 mod n.
The recipient knows (p,q) and can determine whether a number is a square or not, mod n. Therefore he can decrypt the message bit-by-bit.
This is the
talk page for discussing improvements to the
Probabilistic encryption article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
![]() | This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||
|
Would it not use a pseudo-random generator? -- KayEss 07:53, 9 Oct 2004 (UTC)
The Goldwasser-Micali scheme is simple and secure (under an appropriate hardness assumption). I think it might be a better example than OAEP or the general "pad-then-encrypt" discussion, because there are problems with the security of OAEP.
In the GM cryptosystem, (n,y) is the public key, where n is a product of two large primes p,q, and y is a non-square (mod n) of Jacobi symbol 1. (p,q) is the secret key. Encryption is bit-by-bit. To encrypt a 0, send a random square mod n. That is, pick r from Z_n^* and send r^2 mod n. To encrypt a 1, send a random non-square mod n. That is, pick r from Z_n^* and send y*r^2 mod n.
The recipient knows (p,q) and can determine whether a number is a square or not, mod n. Therefore he can decrypt the message bit-by-bit.