# Backdoor in a Public RSA Key

Information SecurityHello, %username%!

When I saw how it works, say that I was shocked is to say nothing. It’s a pretty simple trick, but after reading this article, you will never look at the RSA as before. This is not a way to hijack RSA, but something that will make your paranoia greatly swell.

So, imagine that you have access to the generator of an RSA key and you want to give someone the opportunity to get the private key without any factorization and other quantum computers. What we need to do?

I’m going to use C#, BouncyCastle and Chaos.NaCl (this library implements Curve25519).

1). PRNG

We need a PRNG which is initialized with a secret value. I’m going to use AES in CTR mode.

```
using System;
using System.ComponentModel;
using Org.BouncyCastle.Crypto.Engines;
using Org.BouncyCastle.Crypto.Parameters;
using Org.BouncyCastle.Crypto.Prng;
using Org.BouncyCastle.Security;
namespace RsaBackdoor.Backdoor
{
class SeededGenerator:IRandomGenerator
{
private readonly AesFastEngine _engine = new AesFastEngine();
private readonly byte[] _counter = new byte[16];
private readonly byte[] _buf = new byte[16];
private int bufOffset = 0;
public SeededGenerator(byte[] key)
{
_engine.Init(true, new KeyParameter(key));
MakeBytes();
}
private void MakeBytes()
{
bufOffset = 0;
_engine.ProcessBlock(_counter, 0, _buf, 0);
IncrementCounter();
}
public void IncrementCounter()
{
for (int i = 0; i < _counter.Length; i++)
{
_counter[i]++;
if (_counter[i] != 0)
break;
}
}
public void AddSeedMaterial(byte[] seed)
{
}
public void AddSeedMaterial(long seed)
{
}
public void NextBytes(byte[] bytes)
{
NextBytes(bytes, 0, bytes.Length);
}
public void NextBytes(byte[] bytes, int start, int len)
{
var count = 0;
while (count < len)
{
var amount = Math.Min(_buf.Length - bufOffset, len - count);
Array.Copy(_buf, bufOffset, bytes, start + count, amount);
count += amount;
bufOffset += amount;
if (bufOffset >= _buf.Length)
{
MakeBytes();
}
}
}
}
}
```

2). Let us recall about great Curve25519, namely the fact that any 32-byte sequence is valid for its private key. At the same time, the public key is always 32 bytes also. Let’s pre-generate the master key and assign it to a constant variable:

```
private const string MY_PRIVATE_STR = "BDB440EBF1A77CFA014A9CD753F3F6335B1BCDD8ABE30049F10C44243BF3B6C8";
private static readonly byte[] MY_PRIVATE = StringToByteArray(MY_PRIVATE_STR);
```

For each generated RSA key pair we will also generate a random key pair of Curve25519 and then calculate the shared secret from the public key of the pair, and our private key. This secret is the key to PRNG from step 1.

Seed generation for PRNG:

```
private void MakeSeedAndPayload(out byte[] seed, out byte[] payload)
{
var rnd = new SecureRandom();
var priv = new byte[32];
rnd.NextBytes(priv);
payload = MontgomeryCurve25519.GetPublicKey(priv);
seed = MontgomeryCurve25519.KeyExchange(payload, MY_PRIVATE);
}
```

Curve25519 public key, which we will use to calculate the **seed** is a **payload**. We will try to put it into the RSA public key.

3). Generate RSA key pair by using 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’s worth saying that key-based RSA is always two prime numbers p and q. Their product is called «modulus» and is part of the public key. In this case, two 2048 bits numbers are searched with the help of our PRNG and then a single key pair is built from them.

4). Now, replace some bytes from **p*q** modulus with our **payload**. It makes sense to replace more significant bytes, so that they are not deleted later. 80 bytes-shifting should be enough.

```
var paramz = ((RsaPrivateCrtKeyParameters) pair.Private);
var modulus = paramz.Modulus.ToByteArray();
Replace(modulus, payload, 80);
```

5). We now have a new **n’** modulus and need to regenerate the remaining parameters, taking **n’** into account:

5.1). Calculate new **q’**. We have no idea what it’s gonna be like on the current stage, but it’s not terrible:

`q' = n' / p`

5.2.). Look for a new prime number basing on **q’**. When we find it, least significant bits will be deleted. But the most significant ones will remain the same. That’s exactly what we need.

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

Once we have a new **q**, we calculate all the key-pair parameters, 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);
}
```

As a result, we obtain a valid key pair, which has our **payload** in its public key — namely, the information on how to get the seed and then private key itself.

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;
}
```

Calculate the seed and do the same process one more time in order to get the private key:

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

Thus, by owning a Curve25519 private key, only we can obtain a private key of any backdoored RSA.

Where it can be applied? Anywhere! You’ll *never* prove that the key pairs issued to you by banks do not have these type of markings. **It’s impossible to prove!** So try to generate keys by yourself. Well, and stop using RSA, if possible.

Thanks https://gist.github.com/ryancdotorg for the original implementation https://gist.github.com/ryancdotorg/18235723e926be0afbdd.

## Comments

Osman Aydemir

Joozek Goliński

Alexandre Carmel-Veilleux

andrew

RyanC

This port does have some subtle implementation errors, though.

The embedded key is the master *private* key, so anyone with this code can recover any RSA keys generated with it. I submitted a pull request on github that fixes it.

For those asking «who uses private keys generated by untrusted sources» — this could be implemented in hardware, for example a smart card. Binaries you don’t have the source for or didn’t compile yourself could also be affected.

Amir Kh

That would apply then to any algorithm, operating system, random number generator, or anything you use in life, not just RSA. Pretty weak argument against RSA

David Cervigni

andrew

David Cervigni

CodesInChaos

^{1}⁄_{32}.