Score:0

How does SSH generate keys for RSA algorithm?

nz flag

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?

kelalaka avatar
in flag
https://github.com/openssl/openssl/blob/4cedf30e995f9789cf6bb103e248d33285a84067/crypto/bn/bn_prime.c
kelalaka avatar
in flag
For the collision [Proff Lindell gave the standard answer here](https://crypto.stackexchange.com/a/76766/18298)
Score:3
mu flag
Dan

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.

kelalaka avatar
in flag
First, this: [The GCD strikes back to RSA in 2019 - Good randomness is the only solution?](https://crypto.stackexchange.com/q/76757/18298) and secondly, OP asking ssh, your answer is generic, doesn't provide the details in ssh!
mu flag
Dan
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?
kelalaka avatar
in flag
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](https://crypto.stackexchange.com/a/27294/18298)
Pythonist avatar
nz flag
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!
kelalaka avatar
in flag
Since they use OpenSSL https://github.com/openssl/openssl/blob/4cedf30e995f9789cf6bb103e248d33285a84067/crypto/bn/bn_prime.c
Swashbuckler avatar
mc flag
Which SSH? OpenSSH? Putty? JSCh? Paramiko? Or any of dozens of others?
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.