1
$\begingroup$

In the key generation step of paillier cryptosystem ,

In order to satisfy $\gcd(pq,(p-1)(q-1))=1$ , we can take equal length primes.

Instead of taking(length as parameter to generate $p,q$) equal length primes , is there any time efficient method to generate $p,q$ that assures $pq,(p-1)(q-1)$ are relatively prime ? Or is it mandatory to take equal length primes for efficient implementation .

Just out of curiosity I want to know whether there are any public-key cryptosystems in which primes of equal length are mandatory. If there is , please list names of few of them.

Some work :

Let $p,q$ be the primes such that $p<q$.

Then $p\not|(p-1)$ and $q\not|(q-1)$

Since $p<q$ , $q\not|(p-1)$

So , the only chance to violate the condition $\gcd(pq,(p-1)(q-1))=1$ is $p|(q-1)$

More generally largest prime number minus one does not consists of smallest prime number as a prime factor .

How to ensure this without taking equal length primes ?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

In your question, you already pointed out, that the necessary condition is

More generally largest prime minus one does not consists of smallest prime as a prime factor

therefore, it is sufficient to just check if $p$ divides $q-1$ by computing division. You can just verify this condition during the key generation. I don't know of a more efficient way, anyway, it should be efficient enough for key generation. The main drawback for efficiency would occur if you repeatedly generate unsuitalbe keys, but the probability of that would depend on the length difference you allow for the two primes.

However, in general I think that the security of the scheme depends on the size of the smallest prime, however, the efficiency depends on the size of the obtained modulus $N = pq$, therefore it is probably reasonable to just use equal size primes for the best security and efficiency. Hence, I would guess that the main reason for noting that this property can be ensured by taking equal length primes, is to make sure that no additional work is required to check this during key generation.

I can not point out any schemes that definitely require equal length primes.

Improve this answer
$\endgroup$
3
  • $\begingroup$ After generating $p,q$ we can check that condition . But my point is that, we have to generate $p,q$ in such a way that $\gcd(pq,(p-1)(q-1))=1$ but $p,q$ are of any length . $\endgroup$
    – hanugm
    Commented Sep 11, 2014 at 9:08
  • 1
    $\begingroup$ @hanu I don't know of any way to do this. I think there is an inherent problem that the primes have to be random and independent, but in general ensuring this property might enforce more dependencies between the primes than required by this condition. Any algorithm that does this generation would have to take care not to add any other dependencies between the generated primes. $\endgroup$
    – DragonMouse
    Commented Sep 11, 2014 at 9:25
  • $\begingroup$ One could compute $q$ as 1 more than [something-coprime-to-$p$ times something-smaller-than-$p$]. $\hspace{.48 in}$ $\endgroup$
    – user991
    Commented Sep 12, 2014 at 4:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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