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

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.

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

Кстати, пользуясь случаем, вновь призываю вас поддержать нашу кампанию на BoomStarter по сбору средств на запись второго сезона EaxCast. Поддержать можно как рублем, так и рассказав о кампании друзьям. Помогите нам сделать хороший, годный программерский подкаст!

Метки: , , , , , .

Подпишитесь на блог с помощью RSS, E-Mail, Google+ или Twitter.

Понравился пост? Поделитесь с другими: