Skip to main content
Cryptography

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

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$ Commented 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$ Commented 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$ Commented Dec 11, 2021 at 21:55
  • 1
    $\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$ Commented Dec 11, 2021 at 22:15
  • 1
    $\begingroup$ Which SSH? OpenSSH? Putty? JSCh? Paramiko? Or any of dozens of others? $\endgroup$ Commented Dec 12, 2021 at 1:25