0
$\begingroup$

As far as I understood, the core of the RSA algorithm is to have 2 (large) primes ‘p’ and ‘q’, so that ‘n=pq’. Then ‘n’ is the public key, and ‘p’ the private one. The security comes from the fact that given ‘n’ is not easy to obtain ‘p’ and ‘q’, whereas it’s trivial to check that ‘p’ does factorise ‘n’.

My question is, how does SSH get these numbers in a less than a second? Does it have a “library of prime numbers”? How does it make sure that your ‘p’ and ‘q’ are unique for you? Are there so many “large prime numbers” that fulfill the requirements of the algorithm without obvios collisions?

$\endgroup$
2

1 Answer 1

3
$\begingroup$

Let's say you want "n" to be 2048 bits (RSA 2048). Then "p" and "q" would each be 1024 bits.

The computer generates a random 1024 bit number (almost instantaneous) and tests it for primality. There are different kinds of primality tests, most of them are statistical. They are very fast (I know this is not quantified, but I work on embedded microcontrollers running at 100MHz with no cache, so I have no idea about speed on desktop).

So generating a bunch of 1024 bit numbers, finally you'll hit one that passes multiple iterations of primality tests. (not going into the details here about the statistics and what is "good enough", it's all easy enough to find). Do the same to get your "q", multiply them, you have your modulus "n". "n" plus your "e" (probably 65537) are your public key.

As you can imagine, prime density decreases as the numbers get bigger; there are ways to estimate prime density based on the size of the prime you are trying to generate. 40% of numbers under 10 are prime, but only 25% density for numbers under 100, and even less for 1024-bit numbers. If I recall correctly, on average, you'll have to try the generate/primality test cycle ~360 times to find a 1024-bit number that tests as prime. It's not thousands or millions. And for 512 bit numbers it's probably under 100 attempts.

Because the number space 2^1024 is so huge, it's incredibly unlikely that your p & q will match anyone else's. In fact, each of those 1024 bit strings have probably never existed on any computer in the history of the earth.

I hope that gives you enough of a sense of how it works. It's basically that simple. I've omitted some details, discussion of strong primes, etc. because it gets into details that are outside the scope of your question.

$\endgroup$
6
  • $\begingroup$ First, this: The GCD strikes back to RSA in 2019 - Good randomness is the only solution? and secondly, OP asking ssh, your answer is generic, doesn't provide the details in ssh! $\endgroup$
    – kelalaka
    Dec 11, 2021 at 21:32
  • $\begingroup$ Good points. But regarding the first, there is much, much more to say about the key generation, and you can go down a rabbit hole, but I tried to answer what I believed to be the essence of OP's question. And I've looked at a lot of RSA keygen code in many TLS stacks, they've all been very similar, I don't have any reason to believe an SSH implementation would do it differently. Do you have information to the contrary? $\endgroup$
    – Dan
    Dec 11, 2021 at 21:36
  • $\begingroup$ for example, the usual practice first choose $e$ then select prime and if $\gcd(\lambda(pq),e) \neq 1$ then new primes are selected. some old q 1 $\endgroup$
    – kelalaka
    Dec 11, 2021 at 21:55
  • $\begingroup$ Thanks, this is exactly the level of detail I was looking for. I’ll have to search for those primality tests… I find it extremely counterintuitive that it’s so easy to find random primes. I’d have guessed that the chance of finding a prime by generating random numbers of size 1024 is almost zero. Requiring just about 360 tries blows my mind. Also, it completely puzzles me that you can test primality so cheaply, whereas finding the factors of a number is in practice unaforadable. Really counterintuitive stuff going on here! $\endgroup$
    – Pythonist
    Dec 11, 2021 at 22:15
  • 1
    $\begingroup$ Which SSH? OpenSSH? Putty? JSCh? Paramiko? Or any of dozens of others? $\endgroup$ Dec 12, 2021 at 1:25

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.