1
$\begingroup$
  1. In the first step of key generation phase in Paillier cryptosystem given here.

    It's given that

    $$\operatorname{length}(p) = \operatorname{length}(q) ) \implies \operatorname{gcd}(pq,(p-1)(q-1))=1$$

    where

    $\operatorname{length}(k)$ = # bits in binary representation of $k$

    $\operatorname{gcd}(a,b)$= greatest common divisor of $a,b$

    How to prove the above equation, or where has it been proven?

  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^*$.

    What I am wondering 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 $\operatorname{gcd}(g,n^2)=1$ and $\operatorname{gcd}(r,n)=1$ or is there any simple method while coding cryptosystem.

  3. In the first step of encryption, it 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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – D.W. Jul 10 '14 at 6:48
1
$\begingroup$
  1. Since $p$ and $q$ are primes, the only factors you need 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 GCD must be $1$.

  2. If you just pick a random $g$ modulo $n^2$ the odds that it is 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 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$ .

    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.

$\endgroup$
  • $\begingroup$ 2) how to select r randomly . Is $r=p-1$ suits well? $\endgroup$ – hanugm Jul 9 '14 at 8:28
  • $\begingroup$ @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. $\endgroup$ – otus Jul 9 '14 at 8:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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