<< Предыдущая

стр. 20
(из 48 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

ID?А


Рис. 5.4. Схема непрерывной проверки подлинности отправителя

Другой вариант непрерывной проверки подлинности использует вместо идентификатора от-
правителя его секретный пароль. Заранее подготовленные пароли известны обеим сторонам. Пусть
РА и РВ – пароли пользователей А и В соответственно. Тогда пользователь А создает крипто-
грамму
С = ЕК (РА, М).
Получатель криптограммы расшифровывает ее и сравнивает пароль, извлеченный из этой крипто-
граммы, с исходным значением. Если они равны, получатель признает эту криптограмму.
Процедура рукопожатия была рассмотрена в предположении, что пользователи А и В уже
имеют общий секретный сеансовый ключ. Реальные процедуры предназначены для распределения
ключей между подлинными партнерами и включает как этап распределения ключей, так и этап собст-
венно подтверждения подлинности партнеров по информационному обмену. Такие процедуры будут
рассмотрены в гл. 7.


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

Упрощенная схема идентификации с нулевой передачей знаний
Схему идентификации с нулевой передачей знаний предложили в 1986 г. У.Фейге, А.Фиат и
А.Шамир. Она является наиболее известным доказательством идентичности с нулевой передачей
конфиденциальной информации.
Рассмотрим сначала упрощенный вариант схемы идентификации с нулевой передачей зна-
ний для более четкого выявления ее основной концепции. Прежде всего выбирают случайное значе-
ние модуля n, который является произведением двух больших простых чисел. Модуль n должен
иметь длину 512…1024 бит. Это значение n может быть представлено группе пользователей, кото-
рым придется доказывать свою подлинность. В процессе идентификации участвуют две стороны:
• сторона А, доказывающая свою подлинность,
• сторона В, проверяющая представляемое стороной А доказательство.
Для того чтобы сгенерировать открытый и секретный ключи для стороны А, доверенный ар-
битр (Центр) выбирает некоторое число V, которое является квадратичным вычетом по модулю n.
Иначе говоря, выбирается такое число V, что сравнение
x2 ? V (mod n)
имеет решение и существует целое число
V –1 mod n.
Выбранное значение V является открытым ключом для А. Затем вычисляют наименьшее
значение S, для которого
S ? sqrt (V –1) (mod n).
Это значение S является секретным ключом для А.
Теперь можно приступить к выполнению протокола идентификации.
1. Сторона А выбирает некоторое случайное число r, r < n. Затем она вычисляет
x = r 2 mod n
и отправляет x стороне В.
2. Сторона В посылает А случайный бит b.
3. Если b=0, тогда А отправляет r стороне В. Если b=1, то А отправляет стороне В
y = r ? S mod n.
4. Если b = 0, сторона В проверяет, что
x = r2 mod n,
чтобы убедиться, что А знает sqrt (x). Если b=1, сторона В проверяет, что
x = y2 ?V mod n,
чтобы быть уверенной, что А знает sqrt (V –1).
Эти шаги образуют один цикл протокола, называемый аккредитацией. Стороны А и В по-
вторяют этот цикл t раз при разных случайных значениях r и b до тех пор, пока В не убедится, что А
знает значение S.
Если сторона А не знает значения S, она может выбрать такое значение r, которое позволит
ей обмануть сторону В, если В отправит ей b=0, либо А может выбрать такое r, которое позволит
обмануть В, если В отправит ей b=1. Но этого невозможно сделать в обоих случаях. Вероятность
того, что А обманет В в одном цикле, составляет 1/2. Вероятность обмануть В в t циклах равна
(1/2)t.
Для того чтобы этот протокол работал, сторона А никогда не должна повторно использовать
значение r. Если А поступила бы таким образом, а сторона В отправила бы стороне А на шаге 2
другой случайный бит b, то В имела бы оба ответа А. После этого В может вычислить значение S,
и для А все закончено.

Параллельная схема идентификации с нулевой передачей знаний
Параллельная схема идентификации позволяет увеличить число аккредитаций, выполняемых
за один цикл, и тем самым уменьшить длительность процесса идентификации.
Как и в предыдущем случае, сначала генерируется число n как произведение двух больших
чисел. Для того, чтобы сгенерировать открытый и секретный ключи для стороны А, сначала выбира-
ют К различных чисел V1, V2, ..., VК, где каждое Vi является квадратичным вычетом по модулю n.
Иначе говоря, выбирают значение Vi таким, что сравнение
x2 ? Vi mod n
имеет решение и существует Vi–1 mod n. Полученная строка V1, V2, ..., VК является открытым клю-
чом.
Затем вычисляют такие наименьшие значения Si, что
Si = sqrt (Vi–1) mod n.
Эта строка S1, S2, ..., SK является секретным ключом стороны А.
Протокол процесса идентификации имеет следую-щий вид:
1. Сторона А выбирает некоторое случайное число r, r<n. Затем она вычисляет x=r2 mod n и
посылает x стороне В.
2. Сторона В отправляет стороне А некоторую случайную двоичную строку из K бит: b1, b2,
..., bK.
3. Сторона А вычисляет
b b b
y = r ? (S1 1 ? S2 2 ? ... ? SK K) mod n.
Перемножаются только те значения Si, для которых bi=1. Например, если b1=1, то сомножитель S1
входит в произведение, если же b1=0, то S1 не входит в произведение, и т.д. Вычисленное значение
y отправляется стороне В.
4. Сторона В проверяет, что
b b b
x = y2 ? (V1 1 ? V2 2 ? ... ? VK K) mod n.
Фактически сторона В перемножает только те значения Vi, для которых bi=1. Стороны А и В по-
вторяют этот протокол t раз, пока В не убедится, что А знает S1, S2, ..., SK.
Вероятность того, что А может обмануть В, равна (1/2)Кt. Авторы рекомендуют в качестве
контрольного значения брать вероятность обмана В равной (1/2)20 при К=5 и t=4.
Пример. Рассмотрим работу этого протокола для небольших числовых значений [102]. Если n = 35 (n – произведе-
ние двух простых чисел 5 и 7), то возможные квадратичные вычеты будут следующими:
2
1: x ?1 (mod 35) имеет решения: x =1, 6, 29, 34;
2
4: x ? 4 (mod 35) имеет решения: x = 2, 12, 23, 33;
2
9: x ? 9 (mod 35) имеет решения: x = 3, 17, 18, 32;
2
11: x ?11 (mod 35) имеет решения: x = 9, 16, 19, 26;
2
14: x ?14 (mod 35) имеет решения: x = 7, 28;
2
15: x ?15 (mod 35) имеет решения: x = 15, 20;
2
16: x ?16 (mod 35) имеет решения: x = 4, 11, 24, 31;
2
21: x ? 21 (mod 35) имеет решения: x =14, 21;
2
25: x ? 25 (mod 35) имеет решения: x = 5, 30;
2
29: x ? 29 (mod 35) имеет решения: x = 8, 13, 22, 27;
2
30: x ? 30 (mod 35) имеет решения: x =10, 25.
Заметим, что 14, 15, 21, 25 и 30 не имеют обратных значений по модулю 35, потому что они не являются взаимно
простыми с 35. Следует также отметить, что число квадратичных вычетов по модулю 35, взаимно простых с n = p ? q = 5 ? 7 =
35 (для которых НОД (x, 35) =1), равно
(p –1) (q –1)/4 = (5 –1) (7 –1)/4 = 6.
Составим таблицу квадратичных вачетов по модулю 35, обратных к ним значений по модулю 35 и их квадратных
корней.

V –1 S = sqrt (V –1)
V

1 1 1
4 9 3
9 4 2
11 16 4
16 11 9
29 29 8

Итак, сторона А получает открытый ключ, состоящий из К=4 значений V:
[4, 11, 16, 29].
Соответствующий секретный ключ, состоящий из К = 4 значений S:
[3 4 9 8].
Рассмотрим один цикл протокола.
1. Сторона А выбирает некоторое случайное число r = 16, вычисляет
2
x =16 mod 35 =11
и посылает это значение x стороне В.
2. Сторона В отправляет стороне А некоторую случайную двоич-
ную строку
[1, 1, 0, 1].
3. Сторона А вычисляет значение
b b b 1 1 0 1
y = r ? ( S11 ? S 22 ?...? SKK ) mod n =16 ? (3 ? 4 ? 9 ? 8 ) mod 35 = 31
и отправляет это значение y стороне В.
4. Сторона В проверяет, что
b b b
2 2 1 1 0 1
x = y ? ( V1 1 ? V2 2 ?...? VK K ) mod n = 31 ? (4 ?11 ?16 ? 29 ) mod 35 =11.
Стороны А и В повторяют этот протокол t раз, каждый раз с разным случайным числом r,
пока сторона В не будет удовлетворена.
При малых значениях величин, как в данном примере, не достигается настоящей безопасно-
сти. Но если n представляет собой число длиной 512 бит и более, сторона В не сможет узнать ни-
чего о секретном ключе стороны А, кроме того факта, что сторона А знает этот ключ.
В этот протокол можно включить идентификационную информацию [123].
Пусть I – некоторая двоичная строка, представляющая идентификационную информацию о
владельце карты (имя, адрес, персональный идентификационный номер, физическое описание) и о
карте (дата окончания действия и т.п.). Эту информацию I формируют в Центре выдачи интеллекту-
альных карт по заявке пользователя А.
Далее используют одностороннюю функцию f (·) для вычисления f (I, j), где j – некоторое
двоичное число, сцепляемое со строкой I. Вычисляют значения
Vj = f (I, j)
для небольших значений j, отбирают К разных значений j, для которых Vj являются квадратичны-
ми вычетами по модулю n. Затем для отобранных квадратичных вычетов Vj вычисляют наименьшие
квадратные корни из Vj–1(mod n). Совокупность из К значений Vj образует открытый ключ, а сово-
купность из К значений Sj – секретный ключ пользователя А.

Схема идентификации Гиллоу – Куискуотера
Алгоритм идентификации с нулевой передачей знания, разработанный Л.Гиллоу и
Ж.Куискуотером [121], имеет несколько лучшие характеристики, чем предыдущая схема идентифи-
кации. В этом алгоритме обмены между сторонами А и В и аккредитации в каждом обмене доведе-
ны до абсолютного минимума – для каждого доказательства требуется только один обмен с одной
аккредитацией. Однако объем требуемых вычислений для этого алгоритма больше, чем для схемы
Фейге–Фиата–Шамира.
Пусть сторона А – интеллектуальная карточка, которая должна доказать свою подлинность
проверяющей стороне В. Идентификационная информация стороны А представляет собой битовую
строку I, которая включает имя владельца карточки, срок действия, номер банковского счета и др.
Фактически идентификационные данные могут занимать достаточно длинную строку, и тогда их хэ-
шируют к значению I.
Строка I является аналогом открытого ключа. Другой открытой информацией, которую ис-
пользуют все карты, участвующие в данном приложении, являются модуль n и показатель степени
V. Модуль n является произведением двух секретных простых чисел.
Секретным ключом стороны А является величина G, выбираемая таким образом, чтобы вы-
полнялось соотношение
I ? GV ? 1 (mod n).
Сторона А отправляет стороне В свои идентификационные данные I. Далее ей нужно дока-
зать стороне В, что эти идентификационные данные принадлежат именно ей. Чтобы добиться этого,
сторона А должна убедить сторону В, что ей известно значение G.
Вот протокол доказательства подлинности А без передачи стороне В значения G:
1. Сторона А выбирает случайное целое r, такое, что
1 < r ? n – 1. Она вычисляет
Т = rV mod n
и отправляет это значение стороне В.
2. Сторона В выбирает случайное целое d, такое, что
1 < d ? n – 1, и отправляет это значение d стороне А.
3. Сторона А вычисляет
D = r ? Gd mod n
и отправляет это значение стороне В.
4. Сторона В вычисляет значение
Т? = DV Id mod n.
Если T?T? (mod n),
то проверка подлинности успешно завершена.
Математические выкладки, использованные в этом протоколе, не очень сложны:
Т?= DV ?d = (r Gd)V Id = rV GdV Id = r V (I GV )d = rV ?T(mod n),
поскольку G вычислялось таким образом, чтобы выполнялось соотношение
IGV?1 (mod n).
ГЛАВА 6. ЭЛЕКТРОННАЯ ЦИФРОВАЯ ПОДПИСЬ

6.1. Проблема аутентификации данных и
электронная цифровая подпись
При обмене электронными документами по сети связи существенно снижаются затраты на
обработку и хранение документов, убыстряется их поиск. Но при этом возникает проблема аутенти-
фикации автора документа и самого документа, т.е. установления подлинности автора и отсутствия
изменений в полученном документе. В обычной (бумажной) информатике эти проблемы решаются за
счет того, что информация в документе и рукописная подпись автора жестко связаны с физическим
носителем (бумагой). В электронных документах на машинных носителях такой связи нет.
Целью аутентификации электронных документов является их защита от возможных видов
злоумышленных действий, к которым относятся:
• активный перехват – нарушитель, подключившийся к сети, перехватывает документы (файлы) и
изменяет их;
• маскарад – абонент С посылает документ абоненту В от имени абонента А;
• ренегатство – абонент А заявляет, что не посылал сообщения абоненту В, хотя на самом деле
послал;
• подмена – абонент В изменяет или формирует новый документ и заявляет, что получил его от
абонента А;
• повтор – абонент С повторяет ранее переданный документ, который абонент А посылал абонен-
ту В.
Эти виды злоумышленных действий могут нанести сущест-венный ущерб банковским и ком-
мерческим структурам, государственным предприятиям и организациям, частным лицам, применяю-
щим в своей деятельности компьютерные информационные технологии.
При обработке документов в электронной форме совершенно непригодны традиционные спо-
собы установления подлинности по рукописной подписи и оттиску печати на бумажном документе.
Принципиально новым решением является электронная цифровая подпись (ЭЦП).
Электронная цифровая подпись используется для аутенти-фикации текстов, передаваемых
по телекоммуникационным каналам. Функционально она аналогична обычной рукописной подписи и
обладает ее основными достоинствами:
• удостоверяет, что подписанный текст исходит от лица, поставившего подпись;
• не дает самому этому лицу возможности отказаться от обязательств, связанных с подписанным
текстом;
• гарантирует целостность подписанного текста.
Цифровая подпись представляет собой относительно небольшое количество дополнительной
цифровой информации, передаваемой вместе с подписываемым текстом.
Система ЭЦП включает две процедуры: 1) процедуру постановки подписи; 2) процедуру про-
верки подписи. В процедуре постановки подписи используется секретный ключ отправителя сообще-
ния, в процедуре проверки подписи – открытый ключ отправителя.
При формировании ЭЦП отправитель прежде всего вычисляет хэш-функцию h(M) подписы-
ваемого текста M. Вычисленное значение хэш-функции h(M) представляет собой один короткий блок
информации m, характеризующий весь текст M в целом. Затем число m шифруется секретным
ключом отправителя. Получаемая при этом пара чисел представляет собой ЭЦП для данного текста
M.

<< Предыдущая

стр. 20
(из 48 стр.)

ОГЛАВЛЕНИЕ

Следующая >>