ыми длинными цифровыми кодами для защиты секретных сведений в своих компьютерных базах данных...» Пока это сообщение не подтверждено научными публикациями, ясно лишь, что речь идет о том, что удалось разложить на множители то 129-значное число, которое было использовано в 1977 году. Но уже давно в реальных системах RSA используются более длинные числа.
Подумайте сами:
1. Разберите примеры работы системы RSA, приведённые на стр. 241–243 книги М. Гарднера «От мозаик Пенроуза к надёжным шрифтам».
3.6. Открытое распределение ключей
Кроме принципа построения криптосистемы с открытым ключом, Диффи и Хеллмэн в той же работе предложили еще одну новую идею — открытое распределение ключей. Они задались вопросом: можно ли организовать такую процедуру взаимодействия абонентов A и B по открытым каналам связи, чтобы решить следующие задачи:
1) вначале у A и B нет никакой общей секретной информации, но в конце процедуры такая общая секретная информация (общий ключ) у A и B появляется, т.е. вырабатывается;
2) противник, который перехватывает все передачи информации и знает, что хотят получить A и B, тем не менее не может восстановить выработанный общий ключ A и B.
Диффи и Хеллмэн предложили решать эти задачи с помощью функции F(x) = αx(modp), где p — большое простое число, x — произвольное натуральное число, α — некоторый примитивный элемент поля GF(p).
Примитивным называется такой элемент a из GF(p), что каждый элемент поля, за исключением нуля, может быть представлен в виде степени a. Можно доказать, хотя это и не просто, что примитивный элемент всегда существует.
Общепризнано, что инвертирование функции αx(modp), т.е. дискретное логарифмирование, является трудной математической задачей (см. этюд 3.4).
Сама процедура или, как принято говорить, протокол выработки общего ключа описывается следующим образом.
Числа p и α считаются общедоступными.
Абоненты A и B независимо друг от друга случайно выбирают по одному натуральному числу — скажем x(A) и x(B). Эти элементы они держат в секрете. Далее каждый из них вычисляет новый элемент:
y(A)=αx(A)(modp), y(B)=αx(B)(modp).
Потом они обмениваются этими элементами по каналу связи. Теперь абонент A, получив y(B) и зная свой секретный элемент x(A), вычисляет новый элемент
y(B)x(A)(modp)=(αx(B))x(A)(modp).
Аналогично поступает абонент B:
y(A)x(B)(modp)=(αx(A))x(B)(modp).
Из свойств поля следует, что тем самым у A и B появился общий элемент поля, равный αx(A)x(B). Этот элемент и объявляется общим ключом A и B.
Из описания протокола видно, что противник знает p, α, αx(A), αx(B), не знает x(A) и x(B) и хочет узнать ax(A)x(B). В настоящее время нет алгоритмов действий противника, более эффективных, чем дискретное логарифмирование, а это — трудная математическая задача. (Рекомендуем самостоятельно найти за противника общий ключ, используя алгоритм дискретного логарифмирования и не принимая во внимание вопросы его сложности.)
3.7. Цифровая подпись
Идея цифровой подписи (иногда ее еще называют электронной подписью) была предложена Диффи и Хеллмэном. Суть идеи — в использовании односторонней функции с секретом FK (см. этюд 3.2). В настоящее время эта идея реализована в большом количестве систем передачи данных, особенно банковских. Сообщение, подписанное цифровой подписью, можно представлять себе как пару (x, y), где x — сообщение (платежное поручение в примере с банком и т.п.), FK: X→Y — односторонняя функция, известная всем взаимодействующим абонентам, y — решение уравнения FK(y)=x. Из определения функции FK (см. этюд 3.2) очевидны следующие достоинства цифровой подписи:
1) подписать сообщение x, т.е. решить уравнение FK(y)=x, может только абонент — обладатель данного секрета K; другими словами, подделать подпись невозможно;
2) проверить подлинность подписи может любой абонент, знающий открытый ключ, т.е. саму функцию FK;
3) при возникновении споров отказаться от подписи невозможно в силу ее неподделываемости;
4) подписанные сообщения (x, y) можно, не опасаясь ущерба, пересылать по любым каналам связи.
Именно перечисленные достоинства и обусловили широкое распространение систем цифровой подписи. Опишем, как практически выглядит использование цифровой подписи, на простейшем примере: работа банка с платежными поручениями своих клиентов. Все абоненты этой сети знают одностороннюю функцию FK, и каждый клиент имеет свой собственный, никому не известный секрет K. Клиент подписывает платежное поручение x с помощью функции FK со своим секретом K и посылает подписанное платежное поручение в банк. Банк, получив сообщение от клиента и зная открытый ключ, проверяет подлинность подписи клиента и только после этого выполняет его платежное поручение. В силу отмеченных выше достоинств цифровой подписи и банк, и клиент уверены, что их интересы не пострадают.
Широкое развитие систем электронных платежей, электронной почты и других систем передачи данных потребовало большого разнообразия цифровых подписей. Это привело к развитию теории протоколов цифровой подписи, которая в настоящее время составляет большой раздел теоретической криптографии. В рамках этой теории систематизированы различные виды атак противника на систему цифровой подписи, различные виды успехов, которые противник может достигнуть, различные виды стойкости схем цифровой подписи. Удалось также доказать в некотором смысле эквивалентность существования двух гипотетических объектов: односторонней функции и стойкой схемы цифровой подписи.
Подумайте сами:
1. Пользуясь общей схемой из этюда 3.2, опишите схему цифровой подписи RSA.
3.8. Что такое криптографический протокол
Под криптографическим протоколом понимают такую процедуру взаимодействия абонентов, в результате которой абоненты (не противники!) достигают своей цели, а противник — не достигает.
Успехи, достигнутые в разработке схем цифровой подписи и открытого распределения ключей, позволили применить эти идеи также и к другим задачам взаимодействия удаленных абонентов. Так возникло большое новое направление теоретической криптографии — криптографические протоколы. В настоящее время здесь еще нет устоявшихся определений и общепринятой терминологии, однако мы считаем необходимым дать читателю неформальное представление об этой новой интересной области.
Объектом изучения теории криптографических протоколов являются удаленные абоненты, взаимодействующие по открытым каналам связи. Целью взаимодействия абонентов является решение какой-то задачи. Имеется также противник, который преследует собственные цели. При этом противник в разных задачах может иметь разные возможности: например, может взаимодействовать с абонентами от имени других абонентов или вмешиваться в обмены информацией между абонентами и т.д. Противником может даже оказаться один из абонентов или несколько абонентов, вступивших в сговор.
Полезно самостоятельно продумать введенные понятия на примерах изученных ранее протоколов открытого распределения ключей и цифровой подписи.
Приведем еще несколько примеров задач, решаемых удаленными абонентами.
1. Взаимодействуют два не доверяющих друг другу абонента. Они хотят подписать контракт. Это надо сделать так, чтобы не допустить следующую ситуацию: один из абонентов получил подпись другого, а сам не подписался.
Протокол решения этой задачи принято называть протоколом подписания контракта.
2. Взаимодействуют два не доверяющих друг другу абонента. Они хотят бросить жребий с помощью монеты. Это надо сделать так, чтобы абонент, подбрасывающий монету, не мог изменить результат подбрасывания после получения догадки от абонента, угадывающего этот результат.
Протокол решения этой задачи принято называть протоколом подбрасывания монеты.
Опишем один из простейших протоколов подбрасывания монеты по телефону (так называемая схема Блюма-Микали). Для его реализации у абонентов A и B должна быть односторонняя функция f: X→Y, удовлетворяющая следующим условиям:
1) X — конечное множество целых чисел, которое содержит одинаковое количество четных и нечетных чисел;
2) любые числа x1,x2∈X, имеющие один образ f(x1)=f(x2), имеют одну четность;
3) по заданному образу f(x) «трудно» вычислить четность неизвестного аргумента x.
Роль подбрасывания монеты играет случайный и равновероятный выбор элемента x∈X, а роль орла и решки — четность и нечетность x соответственно. Пусть A — абонент, подбрасывающий монету, а