Skip to main content
Cryptography

Return to Answer

added 464 characters in body
Source Link
DragonMouse
DragonMouse
  • 49
  • 3

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.

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.

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. I can not point out any schemes that require equal length primes.

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.

Source Link
DragonMouse
DragonMouse
  • 49
  • 3

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.

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. I can not point out any schemes that require equal length primes.