Эллиптическая криптография на практике

22 декабря 2010

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

1. Представление больших чисел

Большими числами в контексте этой заметки будут называться числа, разрядность которых превышает разрядность процессора, которому эти самые числа предстоит обрабатывать. Например, 32-х разрядный процессор может с легкостью обрабатывать целые числа от 0 до 232-1. Однако в современных программах, особенно криптографических, приходится иметь дело с числами порядка 24096. И поскольку появление 4096-и разрядных процессоров в обозримом будущем не предвидится, для работы с такими числами приходится использовать специальные алгоритмы.

В школе всех нас учили оперировать цифрами в десятичной системе счисления. Припоминаете что-то про сложение и умножение в столбик? Так вот, в основу алгоритмов работы с большими числами положены те же идеи, только «цифр» будет не 10, а 216 для 32-х разрядных машин и 232 для 64-х разрядных. Почему мы используем только половину доступных разрядов, будет рассказано в следующем пункте.

/*
 *  (c) Alexandr A Alexeev 2010 | http://eax.me/
 */


/* беззнаковое целое, используемое для хранения одного разряда числа
для 32-х разрядных машин - unsiged short,
для 64-х разрядных - unsigned int */

typedef unsigned short bignum_digit_t;

/* максимальный размер числа в байтах */
#define BIGNUM_MAX_SIZE 32

/* максимально допустимое кол-во разрядов в числе */
#define BIGNUM_MAX_DIGITS  (BIGNUM_MAX_SIZE / sizeof(bignum_digit_t))

/* макрос, вычисляющий кол-во разрядов в числе по его размеру */
#define BIGNUM_DIGITS(x) (( x ) / sizeof(bignum_digit_t) )

/* макрос, вычисляющий размер числа по кол-ву разрядов в нем */
#define BIGNUM_SIZE(x) (( x ) * sizeof(bignum_digit_t) )

Вот так выглядит объявление большого целого числа:

/* здесь мы объявляем число максимальной разрядности,
   но если память дорога, а число сравнительно небольшое,
   то разрядов может быть и меньше BIGNUM_MAX_DIGITS */

bignum_digit_t alpha[BIGNUM_MAX_DIGITS];

Используется порядок байт от младшего к старшему (little-endian). Массив, заполненный нулями, соответствует числу 0, заполненный единицами — 2BIGNUM_MAX_SIZE × 8-1. Другими словами, имеет место то же самое представление беззнакового целого числа, что и в большинстве современных процессоров, только памяти выделяется побольше, а единица хранения — не байт, а слово или двойное слово, в зависимости от разрядности процессора.

2. Операции над большими числами

Давайте рассмотрим операцию сложения двух больших чисел:

/* прибавить b к a. digits - кол-во разрядов в числах */
void bignum_add(bignum_digit_t* a, bignum_digit_t* b, int digits) {
  int i;
  bignum_double_t carry = 0;

  for(i = 0; i < digits; i++)
    a[i]= carry= ((bignum_double_t)a[i] + b[i]
                 + (carry >> BIGNUM_DIGIT_BITS));
}

Здесь к числу a прибавляется число b, результат сложения записывается в a. Это аналогично оператору языка си += и тому, как работает ассемблерная команда add. Преимущества такого подхода перед «add(a, b, result)» заключается в использовании меньшего числа аргументов функции и более простой ее реализации.

Функция должна вызываться следующим образом:

  bignum_digit_t arg1[BIGNUM_MAX_DIGITS];
  bignum_digit_t arg2[BIGNUM_MAX_DIGITS];
  /* ... */
  bignum_add(arg1, arg2, BIGNUM_DIGITS(sizeof(arg1)));

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

Как видите, здесь реализовано обыкновенное сложение в столбик, прекрасно знакомое всем со школы. Чтобы с переносом (переменной carry) было проще и быстрее работать, наши «цифры» (не путать цифры и числа!) имеют в два раза меньше разрядов, чем разрядность процессора. Об этом уже говорилось в предыдущем пункте.

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

/* выполнить деление a на b, найти частное и остаток
для корректной работы функции mmul мы вынуждены поддерживать числа,
содержащие BIGNUM_MAX_DIGITS*2 разрядов */

void bignum_div(bignum_digit_t* a, /* делимое */
                bignum_digit_t* b, /* делитель */
                bignum_digit_t* q, /* частное: a, b или NULL */
                bignum_digit_t* r, /* остаток: a, b или NULL */
                int digits) { /* кол-во разрядов в числах */
  /* нормализованный делитель */
  bignum_digit_t td[BIGNUM_MAX_DIGITS * 2];
  /* частное */
  bignum_digit_t tq[BIGNUM_MAX_DIGITS * 2];
  /* нормализованный остаток */
  bignum_digit_t tr[BIGNUM_MAX_DIGITS * 2 + 1];
  /* произведение двух чисел */
  bignum_double_t qhat, rhat, product, carry;
  bignum_signed_double_t temp;
  int i, j, n, shift = 0;

  bignum_setzero(tq, BIGNUM_MAX_DIGITS * 2);

  /* определяем старший ненулевой разряд делителя */
  n = digits;
  while((n > 1) && !b[n - 1]) n--;

  if(n == 1) {
    /* делитель имеет всего один разряд -
       производим деление простым способом.
       это не оптимизация - оставшаяся часть алгоритма
       требует, чтобы делитель имел хотя бы два разряда */

    carry = 0;
    for(j = digits - 1; j >= 0; j--) {
      tq[j] = ((carry << BIGNUM_DIGIT_BITS) | a[j]) / b[0];
      carry = ((carry << BIGNUM_DIGIT_BITS) | a[j]) - tq[j] * b[0];
    }

    if(q) /* сохраняем частное */
      bignum_cpy(q, tq, digits, BIGNUM_MAX_DIGITS * 2);

    if(r) {
      bignum_setzero(r, digits);
      r[0] = carry; /* сохраняем остаток */
    }
    return;
  }

  /* определяем shift - на сколько бит влево нужно сдвиднуть
  делитель, чтобы старший разряд стал равен единице */

  while(!((b[n - 1] << shift) & (1 << (BIGNUM_DIGIT_BITS - 1))))
    shift++;

  bignum_setzero(td, BIGNUM_MAX_DIGITS * 2);
  bignum_setzero(tr, BIGNUM_MAX_DIGITS * 2 + 1);

  /* на x64 тип bignum_digit_t представляет собой int. при shift = 0
  a[digits - 1] >> 32 == a[digits - 1], вот почему необходимо
  приведение типа */

  tr[digits] = (bignum_double_t)a[digits - 1]
               >> (BIGNUM_DIGIT_BITS - shift);
  for(i = digits - 1; i > 0; i--)
    tr[i] = (a[i] << shift)|((bignum_double_t)a[i-1]
            >> (BIGNUM_DIGIT_BITS-shift));
  tr[0] = a[0] << shift;

  /* производим нормализацию делителя */
  for(i = n - 1; i > 0; i--)
    td[i] = (b[i] << shift)|((bignum_double_t)b[i-1]
            >> (BIGNUM_DIGIT_BITS-shift));
  td[0] = b[0] << shift;

  for(j = digits - n; j >= 0; j--) { /* главный цикл */
    /* вычисляем оценку j-го разряда частного и
       соответсвующего остатка */

    qhat = (((bignum_double_t)tr[j+n]<<BIGNUM_DIGIT_BITS)|tr[j+n-1])
           / td[n-1];
    rhat=(((bignum_double_t)tr[j+n]<<BIGNUM_DIGIT_BITS)|tr[j+n-1])
         - qhat*td[n-1];

    while((qhat >= ((bignum_double_t)1 << BIGNUM_DIGIT_BITS)) ||
          (qhat * td[n - 2] > ((rhat << BIGNUM_DIGIT_BITS)
                               | tr[j + n - 2]))) {
      qhat--;
      rhat += td[n - 1];
      if(rhat >= ((bignum_double_t)1 << BIGNUM_DIGIT_BITS))
        break;
    }

    carry = 0; /* умножение и вычитание */
    for(i = 0; i < n; i++) {
      tr[i+j] = temp = tr[i+j]-carry
                - ((product=qhat*td[i]) & BIGNUM_DIGIT_MASK);
      carry = (product >> BIGNUM_DIGIT_BITS)
              - (temp >> BIGNUM_DIGIT_BITS);
    }

    tr[j + n] = temp = tr[j + n] - carry;
    tq[j] = qhat; /* сохраняем разряд частного */
    if(temp < 0) {
      /* вычли слишком много - возвращаем назад. из-за этого
         сравнения t должен иметь знаковый тип. данное условие
         выполняется крайне редко - пример чисел есть в Вельшенбахе */

      tq[j]--; carry = 0;
      for(i = 0; i < n; i++) {
        /* преобразование типов здесь необходимо для amd64 */
        tr[i + j] = temp = (bignum_double_t)tr[i + j]
                    + td[i] + carry;
        carry = temp >> BIGNUM_DIGIT_BITS;
      }
      tr[j + n] += carry;
    }
  } /* конец главного цикла */

  if(q) /* сохраняем частное */
    bignum_cpy(q, tq, digits, BIGNUM_MAX_DIGITS * 2);

  if(r) { /* денормализуем остаток и сохраняем его */
    bignum_setzero(r, digits);
    for(i = 0; i < n; i++)
      r[i]=(tr[i]>>shift)|((bignum_double_t)tr[i+1]
           << (BIGNUM_DIGIT_BITS-shift));
  }
}

Целых 100 строк кода — не слабо для какого-то там деления столбиком, правда? Припоминаю, что мне стоило больших усилий разобраться в этом алгоритме, а потом еще и написать его (хочется верить) без ошибок. Нехорошо ведь, когда люди пытаются объяснить вещи, в которых они далеко не эксперты, верно? В связи с чем отсылаю вас к литературе, по которой я сам пытался во всем разобраться:

  • Генри Уоррен «Алгоритмические трюки для программистов» (стр 142);
  • Михаел Велшенбах «Криптография на Си и C++ в действии» (стр 64);
  • Дональд Кнут «Искусство программирования, том 2 — получисленные алгоритмы, 3-е издание» (стр 310).

Чем выше книга в списке, тем доступнее, по моему субъективному мнению, в ней расписан алгоритм.

3. Модульная арифметика

Модульная арифметика прекрасно знакома всем людям, закончившим школу, хотя и не каждый об этом подозревает. Рассмотрим простую задачу, иллюстрирующую повседневное использование модульной арифметики.

Часы показывают 20:00. На какое время нужно поставить будильник, чтобы он зазвонил ровно через 8 часов?

Ответ, как несложно догадаться, — 4:00. Производя операции над часами, мы работаем с числами в поле вычетов по модулю 24. Аналогично для минут используется поле вычетов по модулю 60, для месяцев — по модулю 12, для дня недели — 7 и так далее. Если вы еще не до конца поняли, о чем идет речь, загляните на соответствующую страницу Википедии.

За выполнение операций сложения, вычитания, умножения и деления в поле вычетов отвечают функции моей библиотеки bignum_madd, bignum_msub, bignum_mmul и bignum_mdiv соответственно. Первые три не заслуживают особого внимания, потому что логика их работы проста. Сначала вычисляем обычную сумму/разность/произведение, и возвращаем остаток от деления на модуль. А вот функция bignum_mdiv заслуживает особого внимания.

Существует такое понятие, как число, мультипликативно обратное данному. Пусть p — число в поле вычетов по модулю m. Тогда число q называется мультипликативно обратным к p, если для любого x, принадлежащего полю вычетов, выполняется условие:

y = x × p (mod m) ⇔ x = y × q (mod m)

или, что то же самое:

p × q = 1 (mod m)

Такое q находится с помощью расширенного алгоритма Евклида, которому в моей библиотеке соответствует функция bignum_inv.

/* найти элемент, мультипликативно обратный к num
   в поле вычетов по модулю m */

void bignum_inv(bignum_digit_t* num, bignum_digit_t* m, int digits) {
  /* r, q, d, d1 = 1, d2 = 0, u = m, v = num; */
  bignum_digit_t r[BIGNUM_MAX_DIGITS];
  bignum_digit_t q[BIGNUM_MAX_DIGITS];
  bignum_digit_t d[BIGNUM_MAX_DIGITS];
  bignum_digit_t d1[BIGNUM_MAX_DIGITS];
  bignum_digit_t d2[BIGNUM_MAX_DIGITS];
  bignum_digit_t u[BIGNUM_MAX_DIGITS];
  bignum_digit_t *pu=u, *pv=num, *pr=r, *pd=d, *pd1=d1, *pd2=d2, *pt;

  bignum_cpy(u, m, digits, digits);
  bignum_setzero(d2, digits);
  bignum_setzero(d1, digits);
  d1[0]++;

  while(!bignum_iszero(pv, digits)) { /* while(v != 0) */
    /* r = u % v; q = (u - r) / v; */
    bignum_div(pu, pv, q, pr, digits);

    /* d = d2 - q*d1 (mod m) */
    bignum_mmul(q, pd1, m, digits);
    bignum_cpy(pd, pd2, digits, digits);
    bignum_msub(pd, q, m, digits);

    /* u = v; v = r; d2 = d1; d1 = d; */
    pt = pu; pu = pv; pv = pr; pr = pt;
    pt = pd2; pd2 = pd1; pd1 = pd; pd = pt;
  }

  /* если u = 1, то d2 - число, обратное num в поле вычетов
     по модулю m, иначе - обратного элемента не сущетсвует */

  if(pd2 != num) bignum_cpy(num, pd2, digits, digits);
}

Если m — простое число, то для любого числа, принадлежащего полю вычетов по модулю m, найдется мультипликативно обратное.

Несложно проследить связь между вышесказанным и операцией деления. В поле вычетов оно происходит в два этапа — (1) найти число, мультипликативно обратное к делителю, а затем (2) умножить его на делимое. То есть операция деления сводится к операции умножения. Ну разве не красиво?

4. Эллиптические кривые

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

y2 = x3 + a x + b (mod m)

причем:

4 a3 + 27 b2 ≠ 0 (mod m)

Коэффициенты a и b — это параметры кривой. Помимо точек, принадлежащих кривой (координаты которых удовлетворяют уравнению y2 = …), вводится так называемая «несобственная» точка, то есть не лежащая на кривой. Если со школьного курса вы припоминаете что-то про «точку на бесконечности», то вот это она и есть. Будем обозначать ее буквой «O».

С учетом вышесказанного, операция сложения двух точек P = (xP; yP) и Q = (xQ; yQ) на эллиптической кривой определяется следующим образом:

P + O = O + P = P
P − P = P + (−P) = O, где -P = (xP; −yP)

R = P + Q = (xR; yR)
xR = λ2 − xP − xQ
yR = λ ( xP − xR) − yP

λ = (3 xP2 + a) / (2 yP), если P = Q
λ = (yP − yQ) / (xP − xQ), если P ≠ Q

Все это — в поле вычетов по простому модулю. А если ввести обозначения

P + P = 2 P
P + P + P = 3 P

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

#include "bignum.h"

/*
 *  (c) Alexandr A Alexeev 2010 | http://eax.me/
 */


/* число разрядов в числах, используемых модулем,
   <= BIGNUM_MAX_DIGITS */

#define ECCRYPT_BIGNUM_DIGITS BIGNUM_MAX_DIGITS

/* точка на эллиптической кривой */
struct eccrypt_point_t {
  bignum_digit_t x[ECCRYPT_BIGNUM_DIGITS]; /* координата x */
  bignum_digit_t y[ECCRYPT_BIGNUM_DIGITS]; /* координата y */
  int is_inf; /* является ли точка несобственной */
};

/* параметры кривой:
   коэффициенты уравнения y^2 = x^3 + a*x + b
   в поле вычетов по модулю m
   и генерирующая точка */

struct eccrypt_curve_t {
  bignum_digit_t a[ECCRYPT_BIGNUM_DIGITS];
  bignum_digit_t b[ECCRYPT_BIGNUM_DIGITS];
  bignum_digit_t m[ECCRYPT_BIGNUM_DIGITS];
  struct eccrypt_point_t g;
};

Здесь все должно быть понятно, за исключением предпоследней строки. Что это еще за «генерирующая точка» такая? Это такая точка G на эллиптической кривой, что минимальное значение n, такое, что n × G = O, является очень большим простым числом. Другими словами, генерируя случайные числа и умножая их на G, мы может гарантировано получить много-много точек, принадлежащих кривой.

На мой взгляд, в приведенном куске кода имеет место нарушение абстракции. Генерирующую точку и число n стоило бы отнести к абстракции «криптографические параметры», а не «эллиптическая кривая». Но поскольку код писался давно и переписывать его сейчас не хочется, я привожу его, как есть.

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

Сложение двух точек эллиптической кривой реализовано в функции eccrypt_point_add. Там все полностью соответствует теоретической части, так что разбирать ее не интересно. А вот умножение — более интересная операция. Дело в том, что вычислять произведение точки на большое число k в цикле из k итераций, полностью в соответствии с определением, — довольно долго. Спрашивается — что делать?

/* умножение точек эллиптической кривой */
void eccrypt_point_mul(struct eccrypt_point_t* rslt, /* результат */
                       struct eccrypt_point_t* p, /* точка */
                       bignum_digit_t* k, /* множитель */
                       struct eccrypt_curve_t* curve) { /* кривая */
  struct eccrypt_point_t point; /* копия точки */
  bignum_digit_t digit; /* значение текущего разряда множителя */
  int digit_num = 0; /* номер разряда */
  int bits = 0; /* кол-во необработанных бит в разряде */
  int n = ECCRYPT_BIGNUM_DIGITS; /* число значащих разрядов */

  if(p->is_inf) {
    rslt->is_inf = 1;
    return; /* n * O = O */
  }

  /* определяем старший значащий разряд */
  while((n > 0) && !k[n - 1]) n--;
  /* создаем копию точки */
  if(n) eccrypt_point_cpy(&point, p);

  /* несобственная точка, раньше мы не могли менять rslt,
  так как возможна ситуация rslt == p */

  rslt->is_inf = 1;

  /* пока есть необработанные биты */
  while((digit_num < n) || digit) {
    if(digit_num) /* это итерация не первая по счету */
      eccrypt_point_add(&point, &point, &point, curve); /* point*=2 */

    if(!bits) {
      /* текущий разряд уже обработан или еще не инициализирован */
      digit = k[digit_num++];
      bits = sizeof(bignum_digit_t) * 8;
    }

    if(digit & 1) /* rslt += point */
      eccrypt_point_add(rslt, rslt, &point, curve);

    digit >>= 1;
    bits--;
  }
}

Здесь мы использовали двоичное представление числа k. Например, чтобы найти 8 × P, мы вычисляем 2 × ( 2 × ( 2 × P ) ), что требует лишь трех операций сложения вместо семи. Аналогично можно написать алгоритм возведения большого числа в степень:

k11 = ((k2)2 × k)2 × k

Другими словами, алгоритм умножения точки эллиптической кривой на число состоит в следующем. Сначала полагаем результат равным несобственной точке. Затем просматриваем биты числа n от старших к младшему. Если встретили 0, умножаем текущее значение результата на 2. Если встретили 1 — умножаем результат на 2, после чего прибавляем P. Таким образом, для нахождения результата потребуется порядка log2(k) шагов вместо k.

5. Криптография на эллиптических кривых

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

Национальный институт стандартов и технологий США (NIST) рекомендует использовать в криптографических приложениях следующую эллиптическую кривую:

a = -3
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
m = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
xG = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
yG = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5

Кривая называется P-256. Здесь m — это модуль поля вычетов, а n — количество точек, которое может генерировать G, оба числа простые. Числа a и m специально подобраны с целью ускорения вычислений. Не знаю, как вы, а я не математик и тем более не криптограф, так что придется положиться на мнение экспертов.

Теперь рассмотрим схему обмена ключами на базе ЭК. Пусть пользователи A и B хотят обменяться ключами, но их трафик прослушивает злоумышленник E. Решение следующее:

  1. Пользователь А генерирует случайно число dA в диапазоне [1; n-1]. Это число будет его закрытым ключом.
  2. Затем A вычисляет QA = dAG и посылает координаты точки пользователю B. QA — открытый ключ пользователя A.
  3. Пользователь B выполняет те же шаги.
  4. Пользователь A получает QB, вычисляет R = dAQB и считает, что xR — это общий ключ.
  5. Пользователь B повторяет предыдущий шаг.

Оба пользователя получили один и тот же ключ xR, потому что dAQB = dAdBG = dBdAG = dBQA.

Злоумышленник E видит только QA и QB. Поскольку эффективный алгоритм, позволяющий определить dA или dB по QA или QB, пока что не найден и в обозримом будущем вряд ли найдется, для нахождения R злоумышленнику понадобится перебрать все (n-1) его возможных значений. Если предположить, что за секунду перебирается 2128 значений (нереально большое число!), то на полный перебор уйдет более 1030 лет. Для сравнения — считается, что возраст Вселенной составляет около 1010 лет.

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

Пусть некий пользователь хочет подписать сообщение. Как и в предыдущем примере, d и Q — его закрытый и открытый ключи соответственно. Открытый ключ должен быть доступен всем, закрытый — хранится в строжайшем секрете.

Алгоритм вычисления цифровой подписи:

  1. Вычислить h — значение хэш-функции (например, SHA256) для подписываемого сообщения.
  2. Выбрать случайное число k из диапазона [1; n-1], вычислить k × G = (x; y) и r = x (mod n).
  3. Если r = 0, перейти к шагу 2.
  4. Вычислить s = (h + d × r) / k (mod n). Если s = 0, перейти к шагу 2.
  5. Вернуть цифровую подпись r || s.

Алгоритм проверки цифровой подписи:

  1. Проверить, что Q принадлежит ЭК и что n × Q = O (последнее должно выполнятся, потому что n × Q = n × d × G = d × n × G = d × O = O). Если это не так, открытый ключ неверен.
  2. Проверить, что r и s принадлежат интервалу [1; n-1]. Если это не так, подпись неверна.
  3. Вычислить h — значение хэш-функции для подписанного сообщения.
  4. Вычислить (x; y) = (h / s) G + (r / s) Q, а затем v = x (mod n).
  5. Если v = r, подпись верна, иначе — не верна.

Значения v и r должны быть равны, потому что

(h / s) G + (r / s) Q = ( h / s) G + (r / s) × d × G = ( (h + d × r) / s) G = k × G

Если не понятно, посмотрите еще раз, как считались r, v и s.

Чтобы подделать подпись, нужно определить закрытый ключ d по открытому ключу Q, что, как мы уже знаем, нереально. С помощью s определить d невозможно, потому что последнее надежно скрыто неизвестным случайным числом k. Определить k с помощью r невозможно по тем же соображениям, по которым d невозможно определить по Q.

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

6. Безопасность, оптимизация и тестирование

Безопасность алгоритма Диффи-Хеллмана и цифровых подписей на основе эллиптических кривых (ECDH и ECDSA соответственно), описанных выше, гарантируется в силу причин, описанных в пункте 5. Действующий в России стандарт цифровых подписей, ГОСТ Р 34.10-2001, использует эллиптические кривые над полем вычетов по модулю порядка 2256. И кстати, ГОСТ Р 34.10-2001 практически полностью идентичен ECDSA. Разве доверие российских криптографов к эллиптическим кривым можно игнорировать? Наконец, эллиптическая криптография существует более 25 лет (против 35 лет «классических» алгоритмов Диффи-Хеллмана и RSA). За это время ее стойкость, похоже, ничуть не пошатнулась. Зато рекомендуемая длина ключа RSA успела увеличиться в 4 раза.

Однако само использование эллиптических кривых не делает ваше приложение автоматически безопасным. Уязвимость может быть в блочном шифре или функции хэширования, используемом протоколе или генераторе случайных чисел. Тайминг-атаки и переполнение буфера также никто не отменял. В моей библиотеке даже не реализована проверка аргументов функции (вдруг там нулевой указатель или другое недопустимое значение?) и очистка памяти, отведенной под переменные, которые стали ненужными. Так что расслабляться, облокотившись на спинку табурета, преждевременно.

Теперь — что касается оптимизации. Есть множество способов ускорить работу библиотеки. Например, используя метод Карацубы или Шёнхаге-Штрассена в функции умножения. Однако в уже упомянутой мной книге Велшенбаха показано, что данные методы бессмысленно использовать, пока речь идет о числах менее 22048. Таким образом, само использование эллиптических кривых (вместо медленного RSA) является главной оптимизацией! Нет смысла переписывать простой и понятный код с целью выиграть сотые доли секунды, особенно если выясняется, что обращение к сети приводит к еще большим задержкам. Здесь нужно сначала получить готовое приложение, и только потом, вооружившись профилировщиком, искать узкие места.

По поводу тестирования библиотеки. Первый тип ошибок, которые нам следует искать, это явные косяки, например, что x − x ≠ 0, y × 1 ≠ y, a × (b + c) ≠ a × b + a × c, сумма двух точек ЭК отлична от O и при этом не принадлежит самой ЭК и тд. Кого интересует полный список таких тестов, загляните в Perl-скрипты из каталога test в прилагающемся к заметке архиве.

Также следует проверить, что наши тесты покрывают если не 100% тестируемого кода, то хотя бы большую его часть. Например, если мы видим в функции условный оператор, то следует убедиться, что мы проверили как ветку if, так и ветку else. Особенно это касается функции, отвечающую за деление больших чисел. Условие ‘if(temp < 0)' (см пункт 2) выполняется чрезвычайно редко, так что вероятность допустить ошибку в окрестностях этого условия очень высока. К счастью, на CD, идущем вместе к Вельшенбахом, можно найти специальные числа для тестирования этого участка кода (файл testdiv.c, если у кого-нибудь из читателей есть эта книга).

Будет совсем не лишним сравнить результаты вычислений нашей библиотеки и какой-нибудь другой, давно отлаженной, программы. Например, интерпретатора Python. Он, к нашей великой радости, может производить математические операции над числами с произвольной точностью. Заодно убедимся, что преобразование строк в числа и обратно в нашей библиотеке реализовано без ошибок.

И наконец, для полной очистки совести, следует проверить библиотеку на практике. Например, подписав какие-нибудь данные с помощью ECDSA, как описано выше. А затем написать скрипт, который рекурсивно обходит файловую систему и подписывает каждый найденный файл, после чего сам же проверяет подпись. Запускаем его перед новогодними праздниками на двух машинах (с 32-х и 64-х разрядным процессором) и проверяем результат 10-го января.

7. Заключение

Здесь вы можете скачать обещанный архив с исходниками. Несмотря на тщательное тестирование библиотеки, мне будет спокойнее, если вы еще раз протестируете ее на своей машине и отпишите в комментариях о результатах. Не забудьте указать ОС и модель процессора.

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

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

На этом у меня, пожалуй, все. Надеюсь, заметка вам понравилась. Если это так, вас, возможно, также заинтересует пост Памятка по созданию безопасного канала связи.

Дополнение: Исходники к посту теперь доступны и на GitHub. Также вас может заинтересовать статья Основные криптографические алгоритмы на языке Си.

Метки: , , , .


Вы можете прислать свой комментарий мне на почту, или воспользоваться комментариями в Telegram-группе.