Журнал "Information Security/ Информационная безопасность" #4, 2019

Американский нацио- нальный институт стандар- тов (англ. American National Standards Institute, ANSI) осуществляет надзор за разработкой и использова- нием стандартов путем аккредитации процедур организаций, разрабаты- вающих стандарты. ANSI также определяет конкрет- ные стандарты как амери- канские национальные стан- дарты, или ANS. – https://ru.wikipedia.org кривой, то и точка (x, -y) тоже. Таким образом, каждой x-коор- динате соответствуют две точки, а значит количество различных координат можно оценить как откуда следует, что количество значений, не являющихся x- координатами, оценивается как Мы видим, что почти полови- на значений не являются коор- динатами точек эллиптической кривой, т.е. никогда не будут выработаны генератором без усечения, а следовательно такой генератор вырабатывает не всевозможные битовые стро- ки, а только какое-то подмно- жество. По утверждению авто- ров алгоритма [2], отсечение 13 старших (левых) бит позво- ляет избавиться от этого недо- статка, поскольку "валидные" и "невалидные" значения x рас- пределены достаточно хаотично (к сожалению, точного объясне- ния, откуда взялось число 13, нигде не приводилось, как и многие другие пояснения к предложенной конструкции). Итак, пусть необходимо выра- ботать requested_number_of_bits бит, генератор ранее инициа- лизирован (s – внутреннее состояние), на вход подана строка additional_input (если не задана, то считаем additional_input = 0). Обозначим за TRUNC_R(a, len) – правые (младшие) len бит строки a, а за TRUNC_L(a, len) – левые (старшие) len бит стро- ки a. Тогда алгоритм работает следующим образом: 1. temp = Null; 2. s = s ⊕ additional_input; 3. s = φ (x(sP)); 4. r = φ (x(sQ)); 5. temp = temp||TRUNC_R(r, outlen); 6. Если len(temp) < reque- sted_number_of_bits, то перейти к 3; 7. returned_bits = TRUNC_L(temp, requested_number_of_bits). В данном описании мы опу- стили некоторые шаги, связан- ные с переинициализацией гене- ратора, проверкой корректности всех длин данных, дополнитель- ной обработкой additional_input. Заметим, кстати, что при выра- ботке достаточно длинной бито- вой строки additional_input используется только в первом блоке данных. К этому аспекту мы еще вернемся, когда будем рассматривать структуру лазей- ки в данном алгоритме. Модификация алгоритма В обновленной версии стан- дарта NIST 2012 г. алгоритм Dual EC был немного модифи- цирован [21]. В конце алгоритма был добавлен еще один шаг: s = φ (x(sP)), т.е. было сделано дополнитель- ное обновление внутреннего состояния. В комментариях к изменениям необходимость данного изменения объяснена "обеспечением стойкости к стойкости к раскрутке гене- ратора в обратную сторону" 7 . Однако более вероятна версия, что данное исправление делает лазейку в алгоритме более уни- версальной, об этом мы рас- скажем чуть позже. Лазейка с защитой Сама математическая струк- тура алгоритма Dual EC позво- ляет легко спроектировать лазейку. Действительно, так как P – порождающий элемент под- группы группы точек эллипти- ческой кривой, а Q – нетриви- альный элемент этой же под- группы, то существует число d: Q = dP. Далее будем называть d клю- чом лазейки. Мы покажем, что знание d помогает вычислять внутреннее состояние генера- тора на основе полученной битовой строки. Напомним, что r – порядок подгруппы, порож- денной точкой P. Пусть e зада- ется формулой: e = d -1 mod r. Тогда P = eQ. Для начала рассмотрим схему без additional_input. Из формул (1) и (2) следует: (3) где S i+1 = s i P и R i = s i Q – соот- ветствующие точки эллиптиче- ской кривой. Таким образом, если знать ключ лазейки и точку R i для некоторого момента времени i, то можно вычислить все после- дующие внутренние состояния генератора и, соответственно, определить все его дальнейшие выходы. Правда, в алгоритме Dual EC известна только часть x-коор- динаты точки R i . Тем не менее всю точку R i можно восстано- вить перебором. Шумов и Фергюсон [8] пред- ложили следующий алгоритм для подбора "кандидатов" на внутренние состояния. Дано: o j – блок выходной битовой строки ключевого гене- ратора. Найти: множество возмож- ных внутренних состояний Если y = √ _ z mod p существует, то A = (x, y) – точка кривой, тогда Σ = Σ U { φ (eA)}. Мощность множества Σ при- близительно равна 2 15 , посколь- ку всего есть 2 16 вариантов • 39 КРИПТОГРАФИЯ www.itsec.ru Рис. 3. Алгоритм Dual EC [6] 7 Provide Backtracking Resistance [16].