HPUNIX Сайт о ОС и не только!

Эллиптическая тайнопись на практике

30 августа 2012 - unix
Эллиптическая криптография на практике

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

1. Представление огромных чисел

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

Но в современных программках, в особенности криптографических, приходится иметь дело с числами порядка 24096. И так как возникновение 4096-и разрядных микропроцессоров в обозримом будущем не предвидится, для работы с такими числами приходится использовать особые методы.

В школе всех нас учили оперировать цифрами в десятичной системе счисления. Припоминаете что-то про сложение и умножение в столбик?

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

/*
*  (c) Alexandr A Alexeev Две тыщи 10 | http://eax.me/
 */

/* беззнаковое целое, применяемое для хранения 1-го разряда числа
для 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. Операции над большенными числами

Давайте разглядим операцию сложения 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)));

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

Видите ли, тут реализовано обычное сложение в столбик, отлично знакомое всем со школы. Чтоб с переносом (переменной 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 * Два + 1];
  /* произведение 2-ух чисел */
  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 * Два + 1);

  /* на x64 тип bignum_digit_t представляет собой int. при shift = 0
  a[digits - 1] >> 30 два == 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);
  • Дональд Кнут «Искусство программирования, том Два — получисленные методы, 3-е издание» (стр 310).

Чем выше книжка в перечне, тем доступнее, по моему личному воззрению, в ней расписан метод.

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

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

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

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

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

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

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

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

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

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

p × q = Один (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. Эллиптические кривые

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

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

при этом:

4 a3 + 20 семь b2 ≠ Нуль (mod m)

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

Если со школьного курса вы припоминаете что-то про «точку на бесконечности», то вот это она и есть. Будем обозначать ее буковкой «O».

С учетом вышесказанного, операция сложения 2-ух точек 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 = Два P
P + P + P = Три P

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

#include "bignum.h"

/*
 *  (c) Alexandr A Alexeev Две тыщи 10 | 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 стоило бы отнести к абстракции «криптографические параметры», а не «эллиптическая кривая». Но так как код писался издавна и переписывать его на данный момент не охото, я привожу его, как есть.

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

Сложение 2-ух точек эллиптической кривой реализовано в функции 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) /* это итерация не 1-ая по счету */
      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. К примеру, чтоб отыскать Восемь × P, мы вычисляем Два × ( Два × ( Два × P ) ), что просит только 3-х операций сложения заместо 7. Аналогично можно написать метод возведения огромного числа в степень:

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

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

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

Если повстречали 0, умножаем текущее значение результата на 2. Если повстречали Один — умножаем итог на 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) его вероятных значений.

Если представить, что в секунду перебирается Две тыщи 100 20 восемь значений (нереально огромное число!), то на полный перебор уйдет более Одна тыща 30 лет. Для сопоставления — считается, что возраст Вселенной составляет около Одна тыща 10 лет.

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

Пусть некоторый юзер желает подписать сообщение. Как и в прошлом примере, 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.

Метод проверки цифровой подписи:

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

    Разве доверие русских криптографов к эллиптическим кривым можно игнорировать? В конце концов, эллиптическая тайнопись существует более 20 5 лет (против 30 5 лет «классических» алгоритмов Диффи-Хеллмана и RSA). За этот период времени ее стойкость, похоже, никак не пошатнулась.

    Зато рекомендуемая длина ключа RSA успела возрости вчетверо.

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

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

    Сейчас — что касается оптимизации. Есть огромное количество методов ускорить работу библиотеки. К примеру, используя способ Карацубы либо Шёнхаге-Штрассена в функции умножения.

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

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

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

    Также следует проверить, что наши испытания покрывают если не 100% тестируемого кода, то хотя бы огромную его часть. К примеру, если мы лицезреем в функции условный оператор, то следует убедиться, что мы проверили как ветку if, так и ветку else. В особенности это касается функции, отвечающую за деление огромных чисел. Условие ‘if(temp >

    Теги:
    Рейтинг: 0 Голосов: 97 1043 просмотра
    Комментарии (0)

    Нет комментариев. Ваш будет первым!

    Найти на сайте: параметры поиска

    Windows 7

    Среда Windows 7 на первых порах кажется весьма непривычной для многих.

    Windows 8

    Если резюмировать все выступления Microsoft на конференции Build 2013.

    Windows XP

    Если Windows не может корректно завершить работу, в большинстве случаев это

    Windows Vista

    Если к вашему компьютеру подключено сразу несколько мониторов, и вы регулярно...