Slow Public Key Generation

[therealOri]

Introduction

So, As the title says, I am trying to generate a key using the following.
key = ElGamal.generate(4098, Random.new().read)

And it's been about an hour now and it still isn't done..

I am using pycryptodomex as perhaps maybe it'd be a bit faster or maybe something would be different, but I can confirm that it doesn't matter if I use pycryptodome or pycryptodomex. It's just not generating a key.

---

Here is my code:

import os
from Cryptodome import Random
from Cryptodome.Random import random
from Cryptodome.PublicKey import ElGamal
from Cryptodome.Util.number import GCD

def clear():
	os.system('clear||cls')


clear()
message = input("Message to encrypt: ")
bmsg = bytes(message, 'utf-8')
clear()

print('Generating key...Please be patient...')
key = ElGamal.generate(4098, Random.new().read) # <--- Code never gets past this point. It's been 1hr+...
clear()

# debugging
print(key) # <--- This is never called/executed.
input()

while 1:
    k = random.StrongRandom().randint(1, key.p - 1)

    if GCD(k, key.p - 1) == 1:
        break

h = key.encrypt(bmsg, k)
print(h)
d = key.decrypt(h)
print(d)

What I am trying to achieve here is an encrypted message (just playing around with stuff). And a decrypted message.
However, I am never able to get to the rest of the code to be able to test things and mess around as the key just never generates.

Any info on why this may be the case would be very helpful and if you have any ways to fix this, It'd also be really helpful and i'd appreciate it.

---

Extra info:

version:

• pycryptodomex==3.15.0

System Info: (from neofetch)

• OS: Manjaro Linux x86_64
• Host: HP Pavilion Laptop 15-cs2xxx
• Kernel: 5.15.72-1-MANJARO
• CPU: Intel i7-8565U (8) @ 4.600GHz
• GPU: Intel WhiskeyLake-U GT2 [UHD Graphics 620]
• Memory: 5166MiB / 7835MiB (laptop has 8GB of ram)

[therealOri]

I'm going to assume that no one else really knows why as well.

[Varbin]

The parameter $p$ of an ElGamal key should be a safe prime so $(p-1)/2 \in \mathbb{P}$. The general algorithm for generating such prime is:

1. $\text{\textbf{while} true \textbf{do}}$
   1. $p = randomPrime(bitsize)$
   2. $\text{\textbf{if}}~ (p-1)/2 \in \mathbb{P} ~\text{\textbf{then}}$
      • break
2. $\text{\textbf{end}}$

(Or alternatively, what PyCryptodome does:)

1. $\text{\textbf{while} true \textbf{do}}$
   1. $q = randomPrime(bitsize - 1)$
   2. $\text{\textbf{if}}~ (q\cdot2 + 1) \in \mathbb{P} ~\text{\textbf{then}}$
      • break
2. $\text{\textbf{end}}$

As already finding a single prime with the given size takes quite a time, finding a safe prime takes significantly more time. You can try to run openssl dhparam -noout -text 4096 and check if it is faster.

See also the following profile of ElGamal.generate(1536, os.urandom) (canceled after a while), that shows PyCryptodome doing safe prime generation most of the time:

         82184632 function calls in 201.950 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000  201.950  201.950 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 ElGamal.py:179(__init__)
        1    0.000    0.000  201.950  201.950 ElGamal.py:34(generate)
      230    1.441    0.006    9.229    0.040 Primality.py:119(lucas_test)
      752    0.000    0.000    0.000    0.000 Primality.py:144(alternate)
   131482    0.893    0.000  198.213    0.002 Primality.py:222(test_probable_prime)
  1314820    0.172    0.000    0.172    0.000 Primality.py:267(<lambda>)
      231    0.401    0.002  201.611    0.873 Primality.py:280(generate_probable_prime)
   131252    0.018    0.000    0.018    0.000 Primality.py:316(<lambda>)
        1    0.001    0.001  201.950  201.950 Primality.py:338(generate_probable_safe_prime)
   131482    1.767    0.000  177.951    0.001 Primality.py:45(miller_rabin_test)
   313852    1.015    0.000    3.791    0.000 _IntegerBase.py:297(random)
   131942    0.870    0.000    8.066    0.000 _IntegerBase.py:345(random_range)
  6256984    1.553    0.000    2.347    0.000 _IntegerGMP.py:118(new_mpz)
  4410070   10.274    0.000   14.553    0.000 _IntegerGMP.py:153(__init__)
   131482    8.124    0.000    8.872    0.000 _IntegerGMP.py:196(__int__)
   313852    0.859    0.000    1.584    0.000 _IntegerGMP.py:267(from_bytes)
  2826678    1.995    0.000    9.267    0.000 _IntegerGMP.py:290(_apply_and_return)
  1712770    1.244    0.000    7.486    0.000 _IntegerGMP.py:295(__eq__)
   748186    0.502    0.000    3.499    0.000 _IntegerGMP.py:305(__lt__)
   315064    0.130    0.000    0.334    0.000 _IntegerGMP.py:308(__le__)
   314542    0.229    0.000    1.910    0.000 _IntegerGMP.py:314(__ge__)
   262690    0.151    0.000    0.151    0.000 _IntegerGMP.py:317(__nonzero__)
   394632    0.172    0.000    0.172    0.000 _IntegerGMP.py:321(is_negative)
   132402    0.187    0.000    1.231    0.000 _IntegerGMP.py:325(__add__)
   527308    0.753    0.000    4.726    0.000 _IntegerGMP.py:337(__sub__)
      230    0.001    0.000    0.003    0.000 _IntegerGMP.py:349(__mul__)
   262690  152.520    0.001  152.932    0.001 _IntegerGMP.py:388(inplace_pow)
   262690    0.196    0.000  153.766    0.001 _IntegerGMP.py:427(__pow__)
   527559    0.351    0.000    0.489    0.000 _IntegerGMP.py:454(__iadd__)
  1058460    1.097    0.000    1.361    0.000 _IntegerGMP.py:490(__imul__)
  1058040    1.511    0.000    1.581    0.000 _IntegerGMP.py:509(__imod__)
   131252    0.214    0.000    1.395    0.000 _IntegerGMP.py:533(__or__)
   967315    0.754    0.000    0.754    0.000 _IntegerGMP.py:556(__irshift__)
   352820    0.335    0.000    1.935    0.000 _IntegerGMP.py:586(get_bit)
   705220    0.282    0.000    0.282    0.000 _IntegerGMP.py:600(is_odd)
   525811    0.253    0.000    0.253    0.000 _IntegerGMP.py:603(is_even)
   263884    0.237    0.000    1.445    0.000 _IntegerGMP.py:606(size_in_bits)
      230    0.000    0.000    0.000    0.000 _IntegerGMP.py:617(is_perfect_square)
   529020    0.610    0.000    0.766    0.000 _IntegerGMP.py:634(multiply_accumulate)
  1411280    0.744    0.000    0.826    0.000 _IntegerGMP.py:656(set)
      522    0.001    0.000    0.007    0.000 _IntegerGMP.py:719(jacobi_symbol)
  4410062    2.346    0.000    2.346    0.000 _IntegerGMP.py:732(__del__)
        1    0.000    0.000    0.000    0.000 __init__.py:46(new)
  3438976    0.710    0.000    1.462    0.000 abc.py:117(__instancecheck__)
   313852    0.160    0.000    0.160    0.000 py3compat.py:115(bchr)
   313852    0.042    0.000    0.042    0.000 py3compat.py:122(bord)
  7711747    1.363    0.000    1.963    0.000 py3compat.py:146(is_native_int)
  3438976    0.753    0.000    0.753    0.000 {built-in method _abc._abc_instancecheck}
  6256984    0.794    0.000    0.794    0.000 {built-in method _ctypes.byref}
  1715432    0.176    0.000    0.176    0.000 {built-in method builtins.abs}
        1    0.000    0.000  201.950  201.950 {built-in method builtins.exec}
 21635321    2.371    0.000    3.833    0.000 {built-in method builtins.isinstance}
   313852    0.046    0.000    0.046    0.000 {built-in method builtins.len}
   262690    0.129    0.000  153.896    0.001 {built-in method builtins.pow}
   627704    0.890    0.000    0.890    0.000 {built-in method posix.urandom}
  1715432    0.152    0.000    0.152    0.000 {method 'bit_length' of 'int' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
  1470019    0.157    0.000    0.157    0.000 {method 'pop' of 'dict' objects}

I do not know if it has downside to (re)use a pre-generated safe prime.

Nevertheless using openssl dhparam -noout -text <bitsize> for generating a safe prime is a lot faster.

[therealOri]

If that's the case and it is indeed working fine..what would be the estimated time I'd have to wait before a key gets generated?

Also using the command you have provided does go faster. 4098 is still unknown as it took to long before I just cancelled it. Anything less than 4098 went quickly and moderately fast.

[Legrandin]

I am afraid the code is simply very slow, and speed degrades exponentially with the bit size.
In theory it could optimized (like openssl's code is, or via multi-threading).

However, I don't think it is worthy - ElGamal keys should not be used in the first place. Support for ElGamal remains available purely for legacy reasons.

I will therefore close this issue.