1. In the first step of key generation phase in Paillier cryptosystem given here
ID: 652666 • Letter: 1
Question
1. In the first step of key generation phase in Paillier cryptosystem given here.
It's given that
( length(p) == length(q) )==> gcd(pq,(p?1(q?1)))=1
where
length(k) = # bits in binary representation of k
gcd(a,b)=greatest common divisor of a,b
Give me a reference if proof for above equation complex otherwise provide a proof.
2. In the third step of key generation , we have to select a random integer g where g ? Z*n2 and in the step 2 of encryption we have to select a random integer r where r?Z*n.
My doubt is "what is the known efficient way to select g,r randomly". I mean whether we have to check in Z*n2,Z*n for such g,r until gcd(g,n2)=1 and g(r,n)=1 or is there any simple method while coding cryptosystem.
3. In the first step of encryption , its is given that plain text m?Zn .
So m<n .
Suppose we are going to encrypt k-bit messages , so our n must be l-bit number, where l>k
We know that product of two s-bit numbers gives a number whose number of bits is between s+1 to 2s , Suppose we are taking the equal length primes to ensure the property gcd(pq,(p?1)(q?1))=1, then it is necessary to take k-bit primes since m<n .
Is this correct?
Explanation / Answer
1. Since p and q are primes, the only factors you needs to rule out are those two numbers.
Suppose p divides (p?1)(q?1). Then it divides either p?1 (clearly not true) or q?1. The latter means q?1=p?x, for some x?2 (if x=1 either p or q is even, which is only possible if the numbers are 2 and 3). However, then q?2p+1, so its binary representation is longer.
A similar argument proves q can't be a factor. Thus, the greatest common divisor must be 1.
2. If you just pick a random g modulo n^2 the odds that it's a good choice are high (for large primes), so you usually only have to verify once. However, like your Wikipedia link states, you can just choose g=n+1 (when your primes are as long).
For r you are also likely to get a good number randomly, but there you do have to check that neither p nor q divides it.
3. We know that product of two s-bit numbers gives a number whose number of bits is between s+1 to 2s, Suppose we are taking the equal length primes to ensure the property gcd(pq,(p?1)(q?1))=1, then it is necessary to take k-bit primes , since m
If you multiply two s-bit numbers the product is always either a 2s?1-bit number or a 2s-bit number. (Here an s-bit number means one which has its sth bit set.) To allow any k-bit messages, it is necessary that 2s?1>k, so s=k/2+1 is enough.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.