наглый копипаст:


Привет, %username%!
Когда я увидел, как это работает, сказать, что я был в шоке — ничего не сказать. Это довольно простой трюк но после прочтения этой статьи вы больше никогда не будете смотреть на RSA по-прежнему. Это не взлом RSA, это нечто, что заставит вашу паранойю очень сильно разбухнуть.


Итак, представьте, что у вас есть доступ к генератору ключей RSA и вы хотите в дальнейшем дать кому-то возможность узнавать закрытый ключ безо всяких факторизаций и прочих квантовых компьютеров. Что нам для этого понадобится?

Я буду сразу же бросаться кодом на C#, который использует BouncyCastle и [Только зарегистрированные могут видеть это. ] (эта библиотечка реализует [Только зарегистрированные могут видеть это. ])

1) PRNG

Нам нужен ГПСЧ, который инициализируется секретным значением. Будем использовать AES s режиме CTR

Код ГПСЧ


2) Вспомним про замечательную [Только зарегистрированные могут видеть это. ], а именно тот факт, что любая 32байтная последовательность является для неё валидным закрытым ключом, а открытый ключ получается тоже всегда 32 байта.
Заранее сгенерируем мастер ключ и запишем его куда-нибудь в константу.

Код:
        private const string MY_PRIVATE_STR = "BDB440EBF1A77CFA014A9CD753F3F6335B1BCDD8ABE30049F10C44243BF3B6C8";
        private static readonly byte[] MY_PRIVATE = StringToByteArray(MY_PRIVATE_STR);
Для каждой ключевой пары RSA, которую мы будем генерировать, мы так же будем генерировать случайную ключевую пару Curve25519, а потом считать общий секрет от публичного ключа этой пары и нашего приватного. Этот секрет будет ключом для нашего ГПСЧ из п.1

Генерация seed для ГПСЧ


Открытый ключ Curve25519, который мы в дальнейшем используем для вычисления seed — это «полезная нагрузка» или payload. Мы будем пытаться запихнуть его в открытый ключ RSA

3) Генерируем ключевую пару RSA, используя этот ГПСЧ и наш 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();
Здесь стоит напомнить, что основа ключей RSA — это всегда два простых числа p и q. Их произведение называется «модуль» и является частью открытого ключа. В данном случае при помощи нашего ГПСЧ ищутся два числа размером 2048 бит и далее из них конструируется ключевая пара.

4) Берем модуль p*q и заменяем в нем часть байт на наш payload. Возьмем байты постарше, чтобы их не перетёрло в дальнейшем. Смещение в 80 байт должно сработать.
Код:
            var paramz = ((RsaPrivateCrtKeyParameters) pair.Private);
            var modulus = paramz.Modulus.ToByteArray();
            Replace(modulus, payload, 80); // 80 - это смещение
4) У нас теперь есть новый модуль n', Нужно перегенерить остальные параметры с учетом нового n', а именно:

4.1) Считаем новую q'. У нас на данном этапе она будет черт пойми чем, но это не страшно
q' = n' / p

4.2.) От новой q' ищем новое простое число. Когда мы его найдем, нижние биты будут перетёрты. Но верхние останутся такими же. Это то, чего мы добивались.
Код:
            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);
        }
И в итоге получаем валидную ключевую пару, в публичном ключе которой скрылся наш Payload — а именно, информация о том, как получить seed, а затем и вожделенный закрытый ключ.

Мы можем извлечь 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;
        }
Вычислить seed и прогнать процесс заново, чтобы получить закрытый ключ
Код:
public AsymmetricCipherKeyPair BuildKeyFromPayload(byte[] payload)
        {
            var seed = MontgomeryCurve25519.KeyExchange(payload, MY_PRIVATE);
            return BuildKey(seed, payload);
        }
Таким образом, только мы, владея закрытым ключом Сurve25519 можем вычислить закрытый ключ любого забекдоренного нами RSA ключа.

Где это можно применить? Да где угодно. Вы никогда не докажете, что в ключевых парах, выдаваемых вам банками и другими неконтролируемыми вами источниками нет таких закладок. Определить наличие такой закладки невозможно! Поэтому старайтесь генерировать их сами. Ну и уходите с RSA по возможности.

Сорцы для поиграть [Только зарегистрированные могут видеть это. ]



з.ы.
напоминаю, что всё это нагло скопипастено мною с [Только зарегистрированные могут видеть это. ]
дабы это читанули все, а не только те, кому не лень переходить по непонятным хабрассылочкам и читать там