Embed a backdoor in the RSA public key

Hi% username%!
When I saw how it works, to say that I was in shock was to say nothing. This is a pretty simple trick, but after reading this article you will never look at RSA again. This is not a hack of RSA, it is something that will make your paranoia swell very much.


So, imagine that you have access to the RSA key generator and you want to give someone the opportunity to recognize the private key in the future without any factorization or other quantum computers. What do we need for this?

I will immediately throw myself at C # code that uses BouncyCastle and Chaos.NaCl (this library implements Curve25519 )

1) PRNG

We need a PRNG that is initialized with a secret value. We will use AES s CTR mode



2) Recall about the wonderful Curve25519 , namely the fact that any 32-byte sequence is a valid private key for it, and the public key is also always 32 bytes.
We will generate a master key in advance and write it somewhere in a constant.

        private const string MY_PUBLIC_STR = "06F1A4EDF328C5E44AD32D5AA33FB7EF10B9A0FEE3AC1D3BA8E2FACD97643A43";
        private static readonly byte[] MY_PUBLIC = StringToByteArray(MY_PUBLIC_STR);
        private const string MY_PRIVATE_STR = "BDB440EBF1A77CFA014A9CD753F3F6335B1BCDD8ABE30049F10C44243BF3B6C8";
        private static readonly byte[] MY_PRIVATE = StringToByteArray(MY_PRIVATE_STR);

For each RSA key pair that we will generate, we will also generate a random Curve25519 key pair, and then take the shared secret from the private key of this pair and our public one. This secret will be the key to our PRSP from Clause 1



the Curve25519 public key, which we will use later to calculate the seed, is a “payload” or payload . We will try to push it into the RSA public key

3) We generate the RSA key pair using this PRNG and our seed .

			var publicExponent = new BigInteger("10001", 16);
			var keygen = new RsaKeyPairGenerator();
			keygen.Init(new RsaKeyGenerationParameters(publicExponent, new SecureRandom(new SeededGenerator(seed)), 2048, 80));
			var pair = keygen.GenerateKeyPair();

It is worth recalling that the basis of RSA keys is always two primes p and q. Their work is called the “module” and is part of the public key. In this case, using our PRNG, two numbers of 2048 bits are searched for and then a key pair is constructed from them.

4) We take the p * q module and replace part of the bytes in it with our payload. Let’s take older bytes so that they do not fray in the future. An offset of 80 bytes should work.

			var paramz = ((RsaPrivateCrtKeyParameters) pair.Private);
			var modulus = paramz.Modulus.ToByteArray();
			Replace(modulus, payload, 80); // 80 - это смещение

4) We now have a new module n ', We need to regenerate the remaining parameters taking into account the new n', namely:

4.1) We consider the new q '. We have at this stage it will be damn what, but it's not scary
q '= n' / p
4.2.) From the new q 'we are looking for a new prime number. When we find it, the lower bits will be rubbed. But the top ones will remain the same. This is what we sought.

			var p = paramz.P;
			var n = new BigInteger(modulus);
			var preQ = n.Divide(p);
			var q  = preQ.NextProbablePrime();

After we have a new q, we count all the parameters of the key pair, except, p, again.

		public AsymmetricCipherKeyPair ComposeKeyPair(BigInteger p, BigInteger q, BigInteger publicExponent)
		{
			if (p.Max(q).Equals(q))
			{
				var tmp = p;
				p = q;
				q = tmp;
			}
			var modulus = p.Multiply(q);
			var p1 = p.Subtract(BigInteger.One);
			var q1 = q.Subtract(BigInteger.One);
			var phi = p1.Multiply(q1);
			var privateExponent = publicExponent.ModInverse(phi);
			var dP = privateExponent.Remainder(p1);
			var dQ = privateExponent.Remainder(q1);
			var qInv = q.ModInverse(p);
			var priv =  new RsaPrivateCrtKeyParameters(modulus, publicExponent, privateExponent, p, q, dP, dQ, qInv);
			return new AsymmetricCipherKeyPair(new RsaKeyParameters(false, priv.Modulus, publicExponent), priv);
		}

And in the end, we get a valid key pair in the public key of which our Payload hid - namely, information on how to get seed, and then the coveted private key.

We can extract payload

		public byte[] ExtractPayload(RsaKeyParameters pub)
		{
			var modulus = pub.Modulus.ToByteArray();
			var payload = new byte[32];
			Array.Copy(modulus, 80, payload, 0, 32);
			return payload;
		}

Compute seed and run the process again to get the private key

		public AsymmetricCipherKeyPair BuildKeyFromPayload(byte[] payload)
		{
			var seed = MontgomeryCurve25519.KeyExchange(payload, MY_PRIVATE);
			return BuildKey(seed, payload);
		}

Thus, only we, owning the Curve25519 private key, can calculate the private key of any RSA key that we have backed up.

Where can this be applied? Yes, anywhere. You will never prove that there are no such bookmarks in the key pairs given to you by banks and other sources you do not control. It is impossible to determine the presence of such a bookmark! Therefore, try to generate them yourself with software that knows how it works.

Sorcerers to play here

Upd:

Corrected the code, now honestly for implementation we need our public key, and we get the seed using the private