If you want to give me SSH access to your server, use this public key (line breaks were added to not mess up the formatting):

1 2 3 4 5 6 7 8 9 10 | ```
ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAACAQ
+Ondergetekende+/+Ondergetekende+/+Ondergetekende+/+Ondergetekende+/+Ondergetekende+/
+Ondergetekende+/+Ondergetekende+/+Ondergetekende+/+Ondergetekende+/+Ondergetekende+/
+Ondergetekende+/+Ondergetekende+/+Ondergetekende+/+Ondergetekende+/+Ondergetekende+/
+Ondergetekende+/+Ondergetekende+/+Ondergetekende+/+Ondergetekende+/+Ondergetekende+/
K4CVktnyUNz5qrKzT3kJgXfktU9ufFqVLD/GqlDCV+5swUZohICigzegEE10B+FjzXAHltTrzdLPb+U7ibuRq
o4E+XBQ7DyDhrzwYmAd1RZFJRK/Wwf16/UTsxdXtSD9sMYPaOz4q1CGaqD/Xg7hhcbd5umh/Epjyn3vp1V+U1
Ee40/3nWrs3kulLPpZJkCAwQ8/fp0wEkW3UCC+i1tR1M+RhlLi2LSpv4lxxxLWg2Zn7X4E6v0qjm8APisC5LK
vMfCfFM1hf+aVn4VMK2A4U2/oxDTPW4N7pisi96N5MhUawuacH2j5jVUYydcuXDb0alwx7/aT981Z6swtIFbi
Zj9w==
``` |

Notice the repeated `/+Ondergetekende+/`

? Yes, that is intentional. My public
key is clearly marked as being mine, and yes, I actually have the private key
that goes with it.

An OpenSSH RSA public key contains a header, a number called *E* and a number
called *N*. These parts are stored together in base64 encoding. *E* is a
relatively small prime number, typically it’s just 65537. *N* is the product
of two large prime numbers, called *P* and *Q*. These prime numbers (*P* and *Q*)
are randomly chosen when the key is generated, and *N* is computed from that.

In a public key, *N* takes up the most space. Of the 724 characters in my
public key, 686 are entirely devoted to storing *N*. This means that if we can
choose *N*, we can influence what a significant portion of the base64
representation looks like. Obviously, we’re limited to base64 characters, but
given that that’s the entire alphabet, the numbers and two filler characters,
that still gives a lot of options.

Of course, *N* needs to be a valid number for a public key, so we can’t just
pick any *N*. But, we do have significant freedoms. Prime numbers are really
common, and every prime number is valid for an RSA key. So if we manage to
find two primes that multiply together to a number that’s close to *N*, we can
control the first few digits, and its representation.

We start out with a freshly generated public key. We take the base64
representation and replace a part of it with our injected text. Of course, now
the key is no longer valid. Also, it’s just a public key, and we also need a
private key. To obtain those, we read the (now invalid) *N* from the public
key. Remember that we need multiply two primes, *P* and *Q* to form *N*. To build
the private key, we also need to know what those two primes are. One of these
(*P*) primes can chosen at random, as long as it’s a prime number. The other
(*Q*) can be estimated by dividing *N* over *P*. The result of this division
is not likely to be prime, but if we can find a prime close to it, the value
of *P*Q* is probably close enough to our *N*, that the injected text still
remains there.

After we’ve found P and Q, there’s some supporting numbers we need to compute, in order to produce a full private and public key, but with a basic understanding of RSA math, that’s a trivial thing to do.

As usual, the code is on github. The tool is capable of generating keys in OpenSSH and PEM format. The code depends on cryptography. Also, the code will run faster if you install gmpy2. Without it, generating a 4096 bit key takes 10 minutes, with it, it’s less than 10 seconds.

Yes. I believe this tool produces keys that are as hard to crack as any other well-generated key.

As usual with cryptographic tools, you need to be weary of tools made by malicious or incompetent actors. Obviously I claim not to be a malicious actor, and as the code is just a few lines long, it shouldn’t be hard to verify my code doesn’t share your generated keys with the KGB.

While I’m quite familiar with the RSA math involved here, I’m not a true cryptography expert. My code actively tries to avoid biases in prime selection, I delegate as much as possible to trusted libraries, and my code adheres to all best practices I’m aware of. Still, cryptography is a complicated field where a small mistake can break your security easily. Proceed with caution.

Back To Home
## Comments