Check out my new TLS certificate: yes, Let's Encrypt signed this and yes, it works.
2 Boosts
2 Likes
@divVerent@vivaldi.net Not quite, but close:
(p, q) = gen_rsa_key(); n = p * q; vanity_n = hide_message(n); vanity_q = vanity_n / p; vanity_q = find_next_prime(vanity_q); return (p, vanity_q);
If you already have one of the primes and want a particular public key, it's possible to calculate what the other "prime" by division. However, the resulting number is very unlikely to actually be a prime or even an integer.
The trick is that since p and q have a similar size, incrementing q will only change the least-significant half of the modulus. Therefore, simply rounding to an integer and finding a nearby prime to the "ideal" q value will preserve a message hidden in the upper half of the modulus.
@nothacking To be fair, this is in the _public_ key.
In your case, the string is part of the RSA modulus, which is supposed to be a product of two primes.
It also seems to be in the topmost bits of the modulus, as your entire modulus appears to be:
```
AMcZO8ePaEDz3mW2///You+dont+actually+have+to+pick+random+private+keys//No+on
e+checks//A+certificate+aurthority+almost+got+away+with+the+number+4//9XhlXz
cfLmUaXN621MkimWfwBajCzHPIll9hk5eleHMsu6H//+JOdKml8zQV9pTF8eT2RDXqj/8b4aglZj
m7GkBfS06iA4s79jazZzmt11YtP9IFi2vHraubrq28diT7Z/+gizriunkGnE8el01suFQbtBB24o
fAVJqQzAEcIv1fPvI2wRuUm5kWfhs0ERoR10uEk=
```
The way I'd do this is:
- Choose prime p at random the usual RSA way.
- Choose prime q at random the usual RSA way, _except_ the RNG is constrained to only generate primes q such that p*q has the desired prefix.
- The `AMcZO8ePaEDz3mW2` part is probably fixed and chosen once.
- That way, you simply pick q between `AMcZO8ePaEDz3mW2///You+[...]+number+4/////...` / p and `AMcZO8ePaEDz3mW2///You+[...]+number+5AAAAA...` / p at random, as the only algorithm change.
- As the fixed prefix is much shorter than half the product, and as p and q are half the length of the product and prime density is 1/ln(n), there should be lots of q available for this to work.
I conclude your RSA key should actually be OK... kinda.