公開rsa金鑰中的後門 | 安全圈 | 专注于最新网络信息安全讯息新闻

你好，%username%！

當我看到它的工作原理時，說我震驚是什麼也沒說。這是一個非常簡單的技巧，但是在閱讀本文之後，您將永遠不會像以前那樣查看RSA。這不是劫持RSA的方法，但會讓你的妄想症大增。

囙此，假設您可以訪問RSA金鑰的生成器，並且您希望給某人一個機會來獲得私密金鑰，而不需要任何因數分解和其他量子電腦。我們需要做什麼？

我將使用C#，BouncyCastle和Chaos.NaCl（這個庫實現Curve25519）。

1）是的。珠江三角洲

我們需要一個用秘密值初始化的PRNG。我要在CTR模式下使用AES。

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）是的。讓我們回顧一下great Curve25519，即任何32位元組序列對於其私密金鑰都是有效的。同時，公開金鑰也總是32位元組。讓我們預先生成主金鑰並將其分配給一個常數變數：

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

對於每個生成的RSA金鑰對，我們還將生成一個隨機金鑰對Curve25519，然後從該對的公開金鑰和我們的私密金鑰計算共亯金鑰。這個秘密是第一步的關鍵。

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公開金鑰，我們將使用它來計算種子是一個有效載荷。我們將嘗試將其放入RSA公開金鑰中。

3）是的。使用PRNG和我們的種子生成RSA金鑰對。

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();

值得一提的是，基於金鑰的RSA始終是兩個素數p和q，它們的乘積稱為“模”，是公開金鑰的一部分。在這種情況下，在PRNG的幫助下蒐索兩個2048比特的數位，然後用它們構建一個金鑰對。

4）是的。現在，用我們的有效載荷替換p*q模中的一些位元組。替換更重要的位元組是有意義的，這樣以後就不會删除它們。80位元組的移位就足够了。

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

5）是的。我們現在有了一個新的n'模量，需要重新生成剩餘的參數，同時考慮n'：

5.1條）。計算新q’。我們不知道現階段會是什麼樣子，但並不可怕：

q'=n'/p5.2.）。基於q'尋找一個新的素數。當我們找到它時，最低有效比特將被删除。但最重要的仍然是一樣的。這正是我們需要的。

q' = n' / p

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

一旦我們有了一個新的q，我們再次計算除了p以外的所有金鑰對參數。

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

結果，我們獲得了一個有效的金鑰對，它的公開金鑰中包含我們的有效負載，也就是，關於如何獲取種子的資訊，然後是私密金鑰本身。

我們可以選取有效載荷：

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

計算種子並再次執行相同的過程以獲取私密金鑰：

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

囙此，通過擁有Curve25519私密金鑰，只有我們才能獲得任何後門RSA的私密金鑰。

在哪裡可以應用？任何地方！你永遠無法證明銀行發給你的鑰匙對上沒有這種標記。這是不可能證明的！所以試著自己生成金鑰。如果可能的話，停止使用RSA。

原始程式碼。

感謝https://gist.github.com/ryancdotorg原始實現https://gist.github.com/ryancdotorg/18235723e926be0afbdd。