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):
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.
Code coverage is a tool used to make sure that the test suite actually tests the entire application. It does this by executing the test suite, and checking which parts of the code get used during the tests. Code that isn’t executed during the test, is marked as uncovered …
Read More
A common need when working with data, is to find the top 10 in a larger list. An easy solution is to use the built-in sort function to sort the entire list, and then just take the first 10 items. While this works, it feels wasteful …
Read More
In Internet discussions, showing user icons really helps to show who’s saying what. Humans need more time to read a users name than they need to recognize a picture. As the old saying goes: a picture is worth a thousand words - that’s quite an impressive compression ratio.
Many …
Read More