Современная криптография. Электронная подпись

 Нас эти семейства интересуют в основном как инструмент для определения  и построения семейств односторонних  хэш-функций.

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

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

У каждой хэш-функции h Î H имеется достаточно короткое описание h и существуют два эффективных алгоритма, первый из которых по запросу и выдает случайное h Î H, а второй по h аргументу x вычисляет h{x).

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

В-третьих, для криптографических приложений иногда требуется так называемое свойство доступности коллизий (collision accessibility). Оно требует существования эффективного алгоритма, который по данным х₁ и х₂ выбирает h Î H такую, что

h(х₁) = h(х₂), равновероятным образом среди всех функций из Н, удовлетворяющих этому свойству. 

1. Пусть F = GF(2^k) и chop: {0,1}^k ® {0,1}^k-1 - функция, которая просто отбрасывает последний бит. Тогда семейство хэш-функций {chop(ax+b)} является 2-универсальным и удовлетворяет свойству доступности коллизий.   
2. Пусть А = {0,1}ⁿ и В {0,1}^m. Для х Î {0,1}ⁿ и у Î {0,1}^n+m-1 определим конволюцию у о х элементов у и х как вектор длины m, i-я координата которого

    определяется по формуле  

Тогда семейство H = { (a о х) Å b | a Î {0,1}^n+m-1 , b Î {0,1}^m} представляет собой универсальное семейство хэш-функций.

Семейства односторонних хэш-функций. 

 Пусть {n_1i} и { n_0i} - две возрастающие последовательности натуральных чисел такие) что для всех i n_1i ³ n_0i и существует такой полином q, что q(n_0i,) ³ n₁.

(такие  последовательности полиномиально связаны).

  Пусть Н_k - коллекция функций такая, что для всех h Î H_k  

и пусть . 

Предположим, что А  - вероятностный алгоритм, работающий за поли-номиальное время, который на входе k выдает строку x Î {0,1}^n1k, называемую исходным значением, и затем для данной случайной h Î H_k пытается найти у Î {0,1}^n1k такое, что h{x) = h{y), но х ¹  у. 

 Определение 2. Семейство U называется универсальным семейством односторонних хэш-функций, если для всех полиномов р, для всех полиномиальных вероятностных алгоритмов А и всех достаточно больших k выполняются следующие условия: 

1. x Î {0,1}^{n1k -} исходное значение для А, то

   Рг[А(h,x) = у, h{x) - h(y), у ¹ х] < 1/p(n_1k),

где вероятность берется по всем h из H_k и по всем случайным выборам алгоритма А.

2. Для любой h Î H_k существует описание h. полиномиальной (от n_1k) длины такое, что по этому описанию и по х значение h(x) вычислимо за полиномиальное время. 

3. Коллекция H_k доступна, т. е. существует алгоритм G, который на входе k равномерно по вероятности генерирует описание функции h Î H_k .

 Заметим, что H_k рассматривается как набор описаний функций: два разных описания могут соответствовать одной и той же функции.

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

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

Глава 4. Модернизация электронной  подписи Эль Гамаля. Задача дискретного логарифмирования.

    Модернизация  электронной подписи  Эль Гамаля. 

    Также, как и в обычной схеме, секретный ключ x Î_R Z^*_p-1 и открытый ключ   y = g^-x mod p. Пространством сообщений в данной схеме является Z_p-1 .

    Подписывающие выбирают случайные u₁,…u_n , так, чтобы они были взаимно простые (т.е gcd (u_n,p-1) = 1).

Тогда  

  Подписью в этом случае является набор (r₁,…,r_n,s) .

Для проверки подписи (r₁,…,r_n,s) для сообщения m необходимо сначала проверить условия r₁,…,r_n Î Z^*_p и s Î Z_p-1 . Если хотя бы одно из них ложно, то подпись отвергается. В противном случае подпись принимается и только тогда, когда                                     .   

      Идея метода состоит в том, что можно подписывать коллективом из n человек, что значительно усложнит задачу раскрытия этой подписи т.к. нам неизвестны все u₁,…u_n . 

Задача  дискретного логарифмирования. 

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

Постановка  задачи.

Пусть G – некоторая мультипликативно записываемая группа, а a и b – некоторые элементы этой группы, связанные равенством b = aⁿ при некотором целом n. Любое целое x, удовлетворяющее уравнению b = a^x, называется дискретным логарифмом элемента b по основанию a. Задача дискретного логарифмирования в группе G состоит в отыскании по данным a и b вышеуказанного вида некоторого дискретного логарифма b по основанию a. Если a имеет бесконечный порядок, то дискретный логарифм любого элемента по основанию a определен однозначно. В противном случае все дискретные логарифмы b по основаниям a можно получить из некоторого такого дискретного логарифма x⁰ по формуле x = x⁰ + km, где km – порядок элемента a, а параметр k пробегает Z.

      Для криптографических приложений наиболее важна задача дискретного логарифмирования в мультипликативных группах  конечных полей GF(q) и колец Zn Как известно, группа GF(q)* циклическая и имеет порядок q –1, поэтому если в качестве a берется некоторый порождающий этой группы, то дискретный логарифм любого элемента GF(q)* по основанию a существует и определен однозначно. Если логарифмировать по фиксированному основанию, которое является порождающим g группы GF(q)*, то можно находить дискретные логарифмы по произвольному основанию. Действительно, чтобы найти дискретный логарифм  x элемента b по основанию a, достаточно вычислить дискретные логарифмы y и z  элементов a и b по основанию a и решить уравнение xy = z(mod q – 1) относительно z. Для краткости обозначим дискретный логарифм y произвольного элемента gÎGF(q)* по основанию a, удовлетворяющий неравенству 0 < y < q – 2, через log. Очевидно, что log – взаимно однозначное отображение GF(q)* на Z_q-1, удовлетворяющее обычному свойству логарифма: log gh = (log  g + log  h) mod (q-1) для произвольных g,h ÎGF(q)*.