Раздел5_11

Для проверки подписи необходимо убедиться, что:

YAAB [mod P] = GM [mod P].

Каждая новая подпись требует нового значения K, и это значение

должно выбираться случайным образом.

Если злоумышленник раскроет K, используемое Алисой, он сможет раскрыть секретный ключ Алисы X.

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

В целом, модульная экспонента с основанием А по модулю N пред-

	функцию (A и N – целые числа, такие, что 1 A < N):
ставляет собой
f A,N ( x ) AX mod N ,		(5.4)
где х – целое число, 1 х (N–1).

Термин "по модулю N" и символ modN отражают так называемую "арифметику часов", например: 3 ч дня + 14 ч 5 ч утра (mod12). Это вычисление записывается, как 17 5(mod12), и читается: "17 сравнимо с 5 по модулю 12". Запись в общем виде выглядит следующим образом: a b(mod N) , и читается как "а" сравнимо с "b" по модулю N. То есть a = b + kN для некоторых k.

Если у = AX, то х = loqАy. Поэтому задачу обращения функции

fA,N(x) называют задачей нахождения дискретного логарифма.

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

образом: для известных A, N и y найти целое число х, такое, что

AX(mod N) = у.

(5.6)

Алгоритм этого вычисления за приемлемое время пока не найден и

модульная экспонента считается условно однонаправленной функцией.

Теория целых чисел даёт оценку: при А 2664 и N 2664 потребуется около 1026

операций.

Также существует класс однонаправленных функций с

«ПОТАЙНЫМ ХОДОМ».

Функция f: X→Y относится к этому классу в том случае, если она

является однонаправленной и возможно эффективное вычисление обратной функции, если известен «потайной ход» (секретное число,

строка или другая информация, ассоциирующаяся с данной функцией).

Современная ТЕХНОЛОГИЯ ШИФРОВАНИЯ часто основана на

применении двух различных ключей.

Одноразовый псевдослучайный сеансовый ключ используется для шифрования (дешифрования) в течение одного сеанса.

А долговременный ключ используется для шифрования (дешифрования)

сеансовых ключей [5].

Применение асимметричных (двухключевых) криптосистем ведёт к задержкам при шифровании (дешифровании) по сравнению с симметричными криптосистемами.

Для минимизации задержки применяют гибридную схему, где асим-

метричная криптосистема применяется для шифрования КОРОТКОГО СЕАНСОВОГО КЛЮЧА: отправитель выполняет

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

А информационные потоки в течение сеанса шифруются с использованием ключей симметричной криптосистемы.

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

а сеансовый принадлежит симметричной криптосистеме (с его помощью шифруются сообщения). Данный метод называется методом «цифрового конверта» (digital envelope).

5.6 Квантовая криптография

Задача безопасной пересылки ключей может быть решена с помощью

квантовой рассылки ключей QKD (Quantum Key Distribution).

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

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

Степень надёжности в данной методике выше, чем в случае применения алгоритмов с парными ключами, например, RSA. Здесь ключ может генерироваться во время передачи по совершенно открытому оптическому каналу.

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

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

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

Отправитель кодирует отправляемые данные, задавая определённые квантовые состояния, получатель регистрирует эти состояния. Затем получатель и отправитель совместно обсуждают результаты наблюдений. В конечном итоге со сколь угодно высокой достоверностью можно быть уверенным, что переданная и принятая кодовые последовательности тождественны. Обсуждение результатов касается ошибок, внесённых шумами или злоумышленником, и ни в малейшей мере не раскрывает содержимого переданного сообщения. Может обсуждаться чётность сообщения, но не отдельные биты. При передаче данных контролируется поляризация фотонов. Поляризация может быть ортогональной (горизонтальной или вертикальной), циркулярной (левой или правой) и диагональной (450 или 1350).

В качестве источника света может использоваться светоизлучающий диод или лазер. Свет фильтруется, поляризуется и формируется в виде коротких импульсов малой интенсивности. Поляризация каждого импульса модулируется отправителем произвольным образом в соответствии с одним из четырёх перечисленных состояний (горизонтальная, вертикальная, левоили право-циркулярная).

Получатель измеряет поляризацию фотонов, используя произвольную последовательность базовых состояний (ортогональная или циркулярная). Получатель открыто сообщает отправителю, какую последовательность базовых состояний он применил. Отправитель открыто уведомляет получателя о том, какие базовые состояния использованы корректно. Все измерения, выполненные при неверных базовых состояниях, отбрасываются. Измерения интерпретируются согласно двоичной схеме: лево-циркулярная поляризация или горизонтальная – 0, правоциркулярная или вертикальная – 1. Реализация протокола осложняется присутствием шума, который может вызвать ошибки. Вносимые ошибки могут быть обнаружены и устранены с помощью подсчёта чётности, при этом один бит из каждого блока отбрасывается. Беннет в 1991 году предложил следующий протокол.

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

2 Строки делятся на блоки размера k (k выбирается так, чтобы вероятность ошибки в блоке была ма-

ла).

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

4 Для каждого блока, где чётность оказалась разной, получатель и отправитель производят итерационный поиск и исправление неверных битов.

5 Чтобы исключить кратные ошибки, которые могут быть не замечены, операции пунктов 1–4 повторяются для большего значения k.

6 Для того, чтобы определить, остались или нет необнаруженные ошибки, получатель и отправитель повторяют псевдослучайные проверки:

–получатель и отправитель открыто объявляют о случайном перемешивании позиций половины бит

вих строках;

–получатель и отправитель открыто сравнивают чётности. Если строки отличаются, чётности должны не совпадать с вероятностью 0,5;

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

Если отличий нет, после m итераций получатель и отправитель получают идентичные строки с вероятностью ошибки 2–m.