Все мы знаем популярную задачу о рюкзаке. Все мы также знаем, что такое асимметричное шифрование и для чего оно используется. А если не знаете - то вот и повод узнать, потому что в этой статье мы попытаемся на основе задачи о рюкзаке написать свою систему шифрования с открытым ключом на C#. Основную логику криптосистемы спрячем в отдельный NuGet-пакет, который затем используем для написания собственного простого web-сервера (тоже на C#, конкретней на ASP.NET Core) с БД. Этот сервер будет представлять собой мессенджер, где пользователи смогут регистрироваться и посылать друг другу сообщения, а также проверять свою почту на наличие оных. Собственная система шифрования позволит нам обмениваться информацией между клиентами и сервером, а в случае перехвата противник не сможет её дешифровать (или, по крайней мере, сможет, но не сразу). Автор не гарантирует 100% адекватность кода или 100% применимость в жизни. Здесь вы найдёте лишь простой пример своей криптосистемы, основанной на известной задаче. Для тех, кто не знает, что такое криптосистемы с открытым ключом, эта статья - шанс потрогать их руками. Пристёгивайтесь, будет жарко.

Описание криптосистемы

Вступление

Кратко и простыми словами: криптосистема с открытым ключом - это как замóк или серия одинаковых замкóв, ключ к которым есть только у одного человека - производителя замкóв.

Задача о рюкзаке

Перейдём к описанию алгоритма. Итак, пусть есть абонент #1 и все другие абоненты. Абонент #1 хочет позволить им отправлять ему зашифрованные сообщения. Для этого нам нужна пара ключей.

Создадим приватный ключ. Для этого генерируем сильно возрастающую последовательность целых чисел, где каждый следующий элемент будет больше суммы предыдущих:

Нам также понадобится два взаимно-простых числа - M и t. Первое должно быть больше суммы всех элементов, второе - меньше:

Публичный ключ определим через последовательность A, умножив каждый элемент на t и взяв остаток от деления на M:

Обратите внимание: A была монотонно возрастающей, а B - наш приватный ключ, не обладает этим свойством.

Вот и всё. Можете раздавать последовательность B каждому, кому хотите.

Тройка (A, M, t) является вашим приватным ключом, ничто из перечисленного никому отдавать нельзя.

Передача сообщения

Абонент #2 хочет передать абоненту #1 своё сообщение. Ему известен публичный ключ - последовательность B, в которой n элементов. А дальше я скажу очевидное: любую конечную информацию можно представить в виде конечной последовательности ноликов и единичек. Числа и строки не исключение. Не теряя общности будем считать, что надо передать последовательность нулей и единичек:

Здесь, например, сообщением является число 165. За раз мы можем передать последовательность состоящую из не более чем n элементов (потому что ключ длины n). Каждому биту исходного сообщения сопоставляем элемент из последовательности публичного ключа.

Складываем те числа b_j, у которых стоит бит 1, получаем шифртекст C.

В примере выше C = b₁ + b₃ + b₆ + b₈. Этот шифртекст и передаётся по каналу.

Дешифровка

Пусть первый абонент получил шифртекст. Первый абонент имеет закрытые (приватные) ключи, которыми мы и воспользуемся, чтобы получить обратно сообщение.

Для этого для начала умножаем на обратный элемент к t по модулю M:

Нетрудно догадаться, что этой операцией мы получили сумму тех элементов из последовательности A, у которых в исходном сообщении Message установлен бит 1. Дальше мы решаем задачу о рюкзаке. Только вот есть один нюанс: последовательность A монотонно возрастает, а это значит, что алгоритм нахождения соответствующих a_i будет намного проще.

Чуть конкретней: начинаем с самых больших a_i и если число меньше чем текущая сумма, то вычитаем его из суммы, одновременно занося в память информацию о том, что мы нашли очередной бит, установленный в единицу. Так продолжаем до самого начала последовательности A. В итоге мы получили последовательность единиц и нулей, а это значит, восстановили сообщение Message.

Недостатки

Теперь вы знаете алгоритм шифрования на основе задачи о рюкзаке. Любой другой абонент #3, если захочет получить исходную последовательность нулей и единиц, должен будет решить задачу о рюкзаке, где C - сумма весов вещей в рюкзаке, а B - последовательность весов предметов. Долго, но просто. Но не так просто как для #1, у которого есть приватный ключ, и у которого задача сильно упрощается.

Недостатки у нашей модельной криптосистемы, конечно, есть (иначе бы ею пользовались). Например, если злоумышленник получит несколько последовательностей шифртекста и плейнтекста (исходного сообщения), то сможет взломать приватный ключ. Или, если последовательность B достаточно маленькая, то взломать отдельный шифртекст также становится проще.

Всегда помните правило: если хотите криптостойкость, никогда не делайте свою криптосистему! Потому что всё уже сделали за вас, и RSA или те же эллиптические кривые уже придуманы и реализованы, а их устойчивость доказана и исследована.

Но перейдём к реализации.

Реализация на языке C#

Описание классов

Напишем простой NuGet пакет, который выполняет генерацию пар ключей, их сохранение в виде файла, шифрование и дешифрование.

В папке, где будете хранить проект, создайте файл решения и добавьте шаблон библиотеки:

dotnet new sln
mkdir src
dotnet new classlib -o src/Backpack.Crypto
vim src/Backpack.Crypto/Backpack.Crypto.csproj  # Добавьте информацию о пакете.
dotnet sln add src/Backpack.Crypto/Backpack.Crypto.csproj

Для пользователей Visual Studio - можете воспользоваться IDE, выбрав нужный шаблон.

CipherText

Начать лучше с CipherText, так как он самый простой. Его представление в виде строки - это просто большое число, которое можно смело скормить BigInteger.Parse. В методе Get() просто возвращаем поле класса. Кстати, конструктор CipherText(BigInteger cipher) можно сделать internal, - он будет использоваться только другими классами пакета и не должен быть виден снаружи.

PrivateKey

Основная сложность заключается в том, что в строке, которая передаётся аргументом в конструктор и которая используется в экспорте, должна быть вся необходимая информация: последовательность чисел A, числа M и t. В качестве типа данных для хранения больших чисел опять же используем BigInteger, для последовательности дополнительно List над ним. В публичном конструкторе всё просто - копируем содержимое аргументов в поля объекта.

# установка зависимости черех cli:
dotnet add package Newtonsoft.Json --version 13.0.2
# cat Backpack.Crypto.csproj
<Project Sdk="Microsoft.NET.Sdk">
  <PropertyGroup>
    ...
  </PropertyGroup>

  <ItemGroup>
    ...
    <PackageReference Include="Newtonsoft.Json" Version="13.0.2" />
  </ItemGroup>
</Project>

using Newtonsoft.Json;
//...
  public PrivateKey(string json) {
    PrivateKey? me = JsonConvert.DeserializeObject<PrivateKey>(json);
    // копируем содержимое me...
  }
//...
  public override string ToString() {
    return JsonConvert.SerializeObject(this, Formatting.None);
  }

dotnet new console -o src/Sample.Console
dotnet sln add src/Sample.Console/Sample.Console.csproj

# cat Sample.Console.csproj
<Project Sdk="Microsoft.NET.Sdk">
  <PropertyGroup>
    ...
  </PropertyGroup>

  <ItemGroup>
    <ProjectReference Include="../Backpack.Crypto/Backpack.Crypto.csproj" />
  </ItemGroup>
</Project>

// src/Sample.Console/test.cs
using System.Numerics;
using Backpack.Crypto;

public class Test {
    public static int Main(string[] args) {

        Console.WriteLine("Hello, World!");
        string s = "{\"a\":[12],\"M\":1277,\"t\":34}";
        PrivateKey key = new PrivateKey(s);
        Console.WriteLine(key.ToString());
        return 0;
    }
}

Остались DecipherLong & DecipherString. В обоих случаях нам понадобится найти обратный элемент к t по модулю M. Вынесем эту логику в отдельную статическую приватную функцию BigInteger ModuleReverse(BigInteger x, BigInteger M). Конечно, есть алгоритмы, решающую эту задачу эффективно. Просто перебрать тоже получится, но вряд ли это то, что нам нужно, учитывая какие числа мы сейчас будем генерировать. Можно вдохновиться здесь. Но cool programmer не станет писать велосипед за 5 минут, а будет искать решение в интернете 15 минут.

dotnet add package BouncyCastle --version 1.8.9
# cat Backpack.Crypto.csproj
<Project Sdk="Microsoft.NET.Sdk">
  <PropertyGroup>
    ...
  </PropertyGroup>
  <ItemGroup>
    ...
    <PackageReference Include="BouncyCastle" Version="1.8.9" />
  </ItemGroup>
</Project>

using BouncyCastleBigInteger = Org.BouncyCastle.Math.BigInteger;
//...
private static BigInteger ModuleReverse(BigInteger x, BigInteger M) {
  BouncyCastleBigInteger xBouncyCastle = new BouncyCastleBigInteger(x.ToString());
  return BigInteger.Parse(xBouncyCastle.ModInverse(new BouncyCastleBigInteger(M.ToString())).ToString());
}

public static int Main(string[] args) {
  Console.WriteLine(PrivateKey.ModuleReverse(BigInteger.Parse("30000000000000000000000000001"), BigInteger.Parse("90000000000000000000000000000000000000000000000000001")));
  return 0;
}

Процесс дешифровки был показан выше в описании алгоритмов. В случае с DecipherLong надо:

1. Проверить, что кол-во элементов в последовательности A больше или равна 64. Иначе тип long нельзя было шифровать.

2. Найти сумму искомых элементов A умножением шифртекста на обратный к t по модулю M.

3. При желании перебрать все элементы в A у которых индекс больше или равен 64 и если хоть один из них меньше или равен суммы из предыдущего пункта, то мы получили в аргументе не long, а шифрованную строку.

4. Перебрать остальные элементы и для каждого уменьшать сумму на соответствующий и устанавливать бит в нужной позиции.

На самом деле, для этой задачи можно написать метод, который и будет перебирать элементы последовательности A, вызывая лямбду, переданную в аргументе, для каждого установленного в 1 бита. В этом случае выглядеть метод DecipherString будет совсем коротко:

public string? DecipherString(CipherText c) {
  BigInteger sum = c.Get() * ModuleReverse(this.t, this.M) % this.M;
  char[] chars = new char[this.a.Count * BITS_IN_CHAR];
  // Первые 2 аргумента: начиная с какой позиции и сумма.
  if (GetSetBits(this.a.Count - 1, sum, i => {
          int charIndex = i / BITS_IN_CHAR;
          int charBit = i % BITS_IN_CHAR;
          chars[charIndex] = XorBitInChar(chars[charIndex], BITS_IN_CHAR - 1 - charBit);
      }))
  {
    // Возвращает true если сумма обнулилась, когда дошли до i==0.
    return new string(chars);
  }
  throw new FormatException("Incorrect cipher!");
}

private bool GetSetBits(int startIndex, BigInteger sum, Action<int> trigger)
{
  for (int i = startIndex; i >= 0; i--)
  {
    if (this.a[i] <= sum)
    {
      sum -= this.a[i];
      trigger(i);
    }
  }
  return sum == BigInteger.Zero;
}

PublicKey

В конструкторе internal PublicKey(List<BigInteger> b) сохраняем значение в приватную переменную. Как сохранять в строку и извлекать из строки мы уже умеем - см. выше. Кстати, можете сразу кинуть ошибку, если DeserializeObject вернул null:

public PublicKey(string json) {
  PublicKey me = JsonConvert.DeserializeObject<PublicKey>(json) 
                 ?? throw new FormatException("Json convertion returned null!");
  this.b = me.b;
}

В CipherText Encrypt(long value) также проверяем, что кол-во элементов в последовательности B больше или равно 64. Создаём локальную переменную sum, инициализируем нулём. Проходимся по последовательности, одновременно проверяя биты value. Для каждого бита прибавляем элемент последовательности к sum, в конце возвращаем новый объект CipherText, передав ему в конструктор эту сумму. Всё просто.

Так же, как и в случае с PrivateKey, где мы создали XorBitInChar, тут бы я добавил приватную GetBitInChar. Основной цикл public CipherText Encrypt(string value) тогда выглядел бы так:

for (int i = 0; i < value.Length * BITS_IN_CHAR; i++)
{
  int charIndex = i / BITS_IN_CHAR;
  int charBit = i % BITS_IN_CHAR;
  if (GetBitInChar(value[charIndex], BITS_IN_CHAR - 1 - charBit))
  {
      sum += this.b[i];
  }
}

Для получения char-а в конкретной позиции используем операцию [].

KeyPair

Сразу создаём приватные поля:

    [JsonProperty]
    private PublicKey PublicKey { get; }
    [JsonProperty]
    private PrivateKey PrivateKey { get; }

Нам надо создать пару ключей в public static KeyPair Generate(int n=128). Это довольно просто. Создадим A, потом по сумме всех элементов подберём M и t и останется только посчитать B. Первый элемент A можно положить 1, каждый последующий должен быть больше суммы предыдущих. Для этого сумму предыдущих достаточно увеличить на какое-то случайное значение, скажем, от 50000 до 1000000.

BouncyCastleBigInteger t = new BouncyCastleBigInteger((sum - MAX_ADDITIVE).ToString()).NextProbablePrime();
BouncyCastleBigInteger M = new BouncyCastleBigInteger((sum + MAX_ADDITIVE).ToString()).NextProbablePrime();
while (t.Gcd(M) != BouncyCastleBigInteger.One) {
  t = t.Subtract(new BouncyCastleBigInteger(MAX_ADDITIVE.ToString()));
  if (t.CompareTo(BouncyCastleBigInteger.Two) < 0) {
    throw new ApplicationException("Can not calculate 2 primary numbers!");
  }
  t = t.NextProbablePrime();
  M = M.Add(new BouncyCastleBigInteger(MAX_ADDITIVE.ToString())).NextProbablePrime();
}

Вспоминаем определение последовательности B: умножить каждый элемент из последовательности A на t и взять по модулю M.

public static int Main(string[] args)
{
  KeyPair gen = KeyPair.Generate(500);
  CipherText text = gen.PublicKey.Encrypt("eye boy cool hat you know!");
  Console.WriteLine(text);
  Console.WriteLine(gen.PrivateKey.DecipherString(text));
  return 0;
}

Ошибки, которые я встретил, и которые пришлось дебажить:

1) Кол-во битов в одном char не 8, как мы привыкли, а 16.

2) Метод SetBit у BouncyCastleBigInteger возвращает новый BouncyCastleBigInteger, поэтому надо делать так: value = value.SetBit(Constants.BITS_IN_LONG - 1 - i);

3) Не забывайте взять по модулю шифртекст, когда умножаете его на обратный к t:

BigInteger sum = (c.Get() * ModuleReverse(this.t, this.M)) % this.M;

Заключение

Статья получилась довольно обширной, поэтому здесь не всё, что было запланированно. В следующих мы поговорим о том, как нашу либу экспортировать в NuGet пакет, возможно, настроим ci/cd в gitlab, добавим тестов, потом напишем сервер на C#, потом поднимем его в k8s, потом напишем клиента на Android. Короче, планов много!

Результат (код) могу дать как zip-пакет или скинуть ссыль по личному запросу.

Спасибо за внимание.