Long prime numbers are used for RSA keys. You only generate RSA keys when creating a new identity (webserver certificate, client certificate, SSH key, etc). The

Long prime numbers are used for RSA keys. You only generate RSA keys when creating a new identity (webserver certificate, client certificate, SSH key, etc). Then, you do search for "a new prime number that hopefully won't get guessed". It can take from a few seconds to several minutes, depending on the hardware and the desired key length. The usual approach is to take a random odd number of desired length and then have a probabilistic primality test (much faster than what would be needed for a formal proof). Several attacks rely on bad entropy or bad pseudo random number generators (PRNG) to guess what prime was selected.