Pull to refresh

Пара слов о гибридном шифровании и эллиптических кривых

Reading time 8 min
Views 10K
Здравствуйте, уважаемые читатели. В качестве предисловия позвольте напомнить, что представляют собой гибридные криптосистемы и почему они получили такое широкое распространение.
Итак, гибридной криптосистемой принято называть способ передачи большого объема зашифрованных данных, при котором данные шифруются секретным ключом с применением симметричного алгоритма (например, AES или DES), а сам ключ передается зашифрованным асимметричным шифром (как, скажем, RSA). Такой способ получил широкое распространение за то, что он вбирает в себя преимущества как симметричной, так и асимметричной криптографии. Большой блок данных шифруется очень быстрым симметричным алгоритмом (и это избавляет от серьезных временных затрат), а ключ шифрования передается надежно зашифрованным с помощью асимметричного алгоритма (и это решает проблему распределения ключей, свойственную только симметричным методам). Все это достаточно широко известно, а поэтому перейдем к самому главному, а именно к вопросам реализации. И вот тут начинается много интересного.

Немного об общем


На первый взгляд наиболее оптимальным решением является комбинация RSA+блочный шифр. Однако этот способ не лишен некоторого количества подводных камней.
Самым очевидным среди них является семантическая слабость алгоритма RSA. Поэтому применять алгоритм RSA можно только с использованием схемы дополнения, такой как RSA-OAEP (прочитать о которой можно здесь). Кратко напомню, что в RSA-OAEP используется две криптографически стойкие хеш-функции а также такие методы как добавление к строке сообщения определенного количества нулевых бит. Что делает схему RSA-OAEP не самым эффективным с точки зрения реализации асимметричным алгоритмом. Из-за этого ограничения использование RSA, как наиболее простого варианта теряет всю свою привлекательность.
Еще одним недостатком совместного использования RSA и блочного шифра является отсутствие контроля целостности передаваемых данных. И это уже камень в огород не асимметричного шифра, все-таки RSA-OAEP с задачей проверки целостности получаемых данных отлично справляется. Сейчас речь идет непосредственно о блочном алгоритме.
Об этой неприятности я хочу рассказать подробнее. Как известно все блочные шифры поддерживают несколько режимов работы. Наибольшее распространение получили режимы ECB и CBC. В режиме ECB исходные данные разбиваются на блоки M1, M2,…, Mn определенного размера. А криптотекст состоит из блоков С1, С2,…, Сn, где Сi=E(Mi), а E(Mi)-функция шифрования, примененная к блоку Mi. Собственно недостаток такого режима сразу бросается в глаза. Злоумышленник может свободно подменить любой блок Сi на блок Со. Т.о. если при передачи данных один ключ используется несколько раз, то злоумышленник, может, перехватив новое сообщение заменить некоторые данные на более старые, причем законный получатель не заметит подвоха.
Режим CBC, по мнению многих способен устранить этот недостаток блочных шифров, но на самом деле это не так. В режиме CBC шифрование происходит следующим образом. Исходные данные разбиваются на блоки M1, M2, Mn определенного размера. А криптотекст состоит из блоков С1, С2, Сn, где Сi=E(Mi &#8853 Ci-1 ). При таком способе создается иллюзия, что все блоки шифротекста связаны и замена одного блока приведет к потере остальных. На самом деле это не так. Замена отдельно взятого блока повлияет на расшифровку только одного(!) следующего за ним блока. Поэтому злоумышленник может успешно подменить несколько блоков, а законный получатель получив эти данные и заметив, что только один блок получен неправильно вполне может и не придать этому значения.
Поэтому, говоря о гибридном шифровании необходимо понимать, что передаваемая таким способом информация должна состоять не из двух блоков, а из трех Easy(K)||Esym(M)||MACK(M), где Easy(K)-зашифрованный асимметричным алгоритмом ключ, Esym(M)-зашифрованные симметричным алгоритмом, с применением ключа K, данные M, MACK(M)-код аутентификации сообщения M, полученный с применением ключа K.
И в связи с этим появляются еще одно небольшое неудобство, связанное с применением асимметричной криптосистемы наподобие RSA в гибридных схемах. Это избыточные данные. Чтобы передать сообщение M, нам итак необходимо добавлять к криптотексту лишнюю строку бит MACK(M). А помимо этого еще и RSA, в силу большого размера модуля шифрования (в настоящее время рекомендуется 2048 бит), увеличивает исходный размер шифруемого ключа в разы. Конечно избыточность некритична всего 2048 бит ( с учетом MAC-функции), но наряду со сложностями реализации стоящими за RSA-OAEP это все дает повод поискать другой способ гибридного шифрования и такой способ есть. И называется он DHIES.

Коротко о главном


Схема гибридного шифрования DHIES (Diffie-Hellman Integrated Encryption Scheme) была предложена тремя авторами Michel Abdalla, Mihir Bellare и Phillip Rogaway в 2001 году. Идея лежащая в основе схемы основана на трудности решения задачи дискретного логарифма. Сама схема шифрования заключается в следующем.
Предположим, что Алиса хочет отправить Бобу зашифрованное симметричным алгоритмом сообщение и ключ к этому сообщению. Пусть у Боба имеется пара открытый/закрытый ключ (x, G, P, Y=Gx mod P), где G, P, Y – открытые данные, а x-секретный ключ Боба. Т.е. набор ключей Боба соответствует стандартам DSA и ГОСТ Р 34.10-2001 (это важно, потому что избавляет от необходимости генерировать дополнительную пару ключей).
Для отправки сообщения Алиса выполняет следующие действия:
  1. Генерирует случайное большое число k.
  2. Вычисляет U=Gk и V=Yk=Gkx.
  3. Определяет пару (K1, K2)=H(V||U), где H()-криптографически сильная хеш-функция.
  4. Находит C=EK1(M) и T=MACK2(С)
  5. Отправляет Бобу сообщение вида U||C||T.

Получив сообщение от Алисы, Боб используя свой секретный ключ x, может вычислить V=Ux. Зная V и U, Боб в состоянии получить пару ключей (K1, K2)=H(V||U). С помощью ключа K2, он проверяет целостность полученного шифра T=MACK2(С) и в случае если результат верен, расшифровывает текст при помощи ключа K1, M=DK1(С).

Преимущества схемы DHIES заключается в простоте реализации асимметричного шифрования. Так, чтобы получить надежно зашифрованный симметричный ключ и передать его необходимо всего два возведения в степень. В то время, как при использовании RSA-подобных систем еще необходимо будет позаботиться о схемах дополнения.
Во-вторых, схема основывается на задаче дискретного логарифма, а следовательно ее легко можно перенести на эллиптические кривые. Единственный нюанс использования DHIES на эллиптических кривых, заключается в том, что вычисление Gx на самом деле означает нахождение точки x*G, а в остальном все остается по-прежнему. Известно, что эллиптическая криптография работает на пространствах с гораздо меньшим размером (например 256 бит вместо 2048). И тем самым, применяя схему EC-DHIES, мы избавляемся от избыточных бит (тут речь, разумеется, идет не об экономии трафика, просто немного уменьшить избыточность — дело чести).
Ну а в третьих нет необходимости создавать дополнительную пару открытый/закрытый ключ для передачи шифрованных данных. Если получатель использует цифровую подпись с алгоритмом DSA или ГОСТ Р 34.10-2001, то для отправки сообщения можно использовать открытый ключ применяемый для верификации подписи.

И совсем чуть-чуть кода


И напоследок, небольшой класс для выполнения математических операций над точками эллиптических кривых, с помощью которого можно реализовать EC-DHIES.
//класс для умножения точек эллиптической кривой
  public class ECPoint
  {
    public BigInteger x;
    public BigInteger y;
    public BigInteger a;
    public BigInteger b;
    public BigInteger FieldChar;

    public ECPoint(ECPoint p)
    {
      x = p.x;
      y = p.y;
      a = p.a;
      b = p.b;
      FieldChar = p.FieldChar;
    }

    public ECPoint()
    {
      x = new BigInteger();
      y = new BigInteger();
      a = new BigInteger();
      b = new BigInteger();
      FieldChar = new BigInteger();
    }
    //сложение двух точек P1 и P2
    public static ECPoint operator +(ECPoint p1, ECPoint p2)
    {
      ECPoint p3 = new ECPoint();
      p3.a = p1.a;
      p3.b = p1.b;
      p3.FieldChar = p1.FieldChar;

      BigInteger dy = p2.y - p1.y;
      BigInteger dx = p2.x - p1.x;

      if (dx < 0)
        dx += p1.FieldChar;
      if (dy < 0)
        dy += p1.FieldChar;

      BigInteger m = (dy * dx.modInverse(p1.FieldChar)) % p1.FieldChar;
      if (m < 0)
        m += p1.FieldChar;
      p3.x = (m * m - p1.x - p2.x) % p1.FieldChar;
      p3.y = (m * (p1.x - p3.x) - p1.y) % p1.FieldChar;
      if (p3.x < 0)
        p3.x += p1.FieldChar;
      if (p3.y < 0)
        p3.y += p1.FieldChar;
      return p3;
    }
    //сложение точки P c собой же
    public static ECPoint Double(ECPoint p)
    {
      ECPoint p2 = new ECPoint();
      p2.a = p.a;
      p2.b = p.b;
      p2.FieldChar = p.FieldChar;

      BigInteger dy = 3 * p.x * p.x + p.a;
      BigInteger dx = 2 * p.y;

      if (dx < 0)
        dx += p.FieldChar;
      if (dy < 0)
        dy += p.FieldChar;

      BigInteger m = (dy * dx.modInverse(p.FieldChar)) % p.FieldChar;
      p2.x = (m * m - p.x - p.x) % p.FieldChar;
      p2.y = (m * (p.x - p2.x) - p.y) % p.FieldChar;
      if (p2.x < 0)
        p2.x += p.FieldChar;
      if (p2.y < 0)
        p2.y += p.FieldChar;

      return p2;
    }
    //умножение точки на число x, по сути своей представляет x сложений точки самой с собой
    public static ECPoint multiply(BigInteger x, ECPoint p)
    {
      ECPoint temp = p;
      while (x != 0)
      {

        if ((x % 2) != 0)
        {          
          if((temp.x==p.x)||(temp.y==p.y))
            temp=Double(temp);
          else
            temp = temp + p;
          x = x - 1;
        }
        x = x / 2;
        p = Double(p);
      }
      return temp;
    }
  }


* This source code was highlighted with Source Code Highlighter.


Заключение


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

Ссылки


  1. Описание метода DHIES(pdf).
  2. Библиотеку BigInteger можно скачать здесь.
  3. Список рекомендованных к использованию эллиптических кривых .
Tags:
Hubs:
+24
Comments 18
Comments Comments 18

Articles