Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
  1. In the first step of key generation phase in Paillier cryptosystem given here.

    It's given that

    ( length($p$) == length($q$) )$\implies$ 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 \in \mathbb{Z}_{n^2}^*$ and in the step 2 of encryption we have to select a random integer $r$ where $r \in \mathbb{Z}_n^*$.

    My doubt is "what is the known efficient way to select $g,r$ randomly". I mean whether we have to check in $\mathbb{Z}_{n^2}^*,\mathbb{Z}_n^*$ for such g,r until gcd($g,n^2$)=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\in \mathbb{Z}_n$ .

    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 2$s$ , Suppose we are taking the equal length primes to ensure the property $\operatorname{gcd}(pq,(p-1)(q-1))=1$, then it is necessary to take $k$-bit primes since $m<n$ .

    Is this correct?

share|improve this question
    
I can't understand what you are asking. What does "Give me a reference if proof for above equation complex otherwise provide a proof." mean? Also, what research have you done? Did you read the original research paper? –  D.W. Jul 10 at 6:48
add comment

1 Answer 1

up vote 1 down vote accepted
  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 \cdot x$, for some $x \ge 2$ (if $x = 1$ either $p$ or $q$ is even, which is only possible if the numbers are 2 and 3). However, then $q \ge 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 $s$th bit set.) To allow any $k$-bit messages, it is necessary that $2s-1>k$, so $s=k/2+1$ is enough.

share|improve this answer
    
2) how to select r randomly . Is $r=p-1$ suits well? –  chanu Jul 9 at 8:28
    
@chanu, no. A new random $r$ must be chosen for every message. You can pick a random number modulo $n$, then find if $p$ or $q$ divides. There may be some shortcut I'm forgetting right now, but that's easy enough. –  otus Jul 9 at 8:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.