Некоторые протоколы доверенной цифровой подписи
ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА
2021 Математические методы криптографии №1(11)
МАТЕМАТИЧЕСКИЕ МЕТОДЫ КРИПТОГРАФИИ
УДК 519.7
НЕКОТОРЫЕ ПРОТОКОЛЫ ДОВЕРЕННОЙ ЦИФРОВОЙ ПОДПИСИ
Е. А. Толюпа
Ярославский государственный университет им. П. Г. Демидова, г. Ярославль, Россия
E-mail: [email protected]
Предложены усовершенствование протокола доверенной цифровой подписи (ДЦП) авторов J.-Y Lee, J.-H. Cheon и S. Kim, устранившее его уязвимость, позволяющую сторонам создавать доверенный ключ подписания независимо друг от друга, и протокол коллективной ДЦП, который можно использовать при реализации процедуры голосования.
Ключевые слова: электронная цифровая подпись, доверенная цифровая подпись, анализ безопасности, голосование, коллективная подпись.
Введение
Традиционные протоколы цифровой подписи (ЦП) позволяют пользователю выполнить подпись под документом самостоятельно, и любой участник электронного информационного обмена может убедиться в верности подписи, однако эти протоколы не позволяют одному участнику, скажем A, делегировать свои права другому участнику — B, который может подписывать сообщения от имени A. Такая необходимость возникает, когда, например, руководитель организации по той или иной причине (по состоянию здоровья или техническим возможностям) не может подписать документ сам. В этой ситуации он может доверить право подписывать документы от своего имени другому лицу, например своему заместителю. Заместитель, получив такое право, может подписывать сообщения от лица руководителя, а проверяющий будет знать, кто и от чьего имени поставил данную подпись. Решить подобную задачу позволяют протоколы доверенной цифровой подписи (ДЦП, или proxy signature).
Основоположниками теории протоколов ДЦП и разработчиками первого такого протокола являются М. Mambo, K. Usudaи E. Okamoto [1]. Ими были сформулированы первые требования к безопасности протоколов ДЦП [1, 2], расширенные позже в [3, 4]. Безопасная ДЦП должна удовлетворять следующим требованиям:
1. Проверяемость — проверяющий может быть убежден, что подпись поставлена с согласия доверителя.
2. Стойкость к фальсификации — только назначенная доверителем сторона может создать верную доверенную подпись от лица доверителя. Другими словами, участник A и третья сторона, не выбранная им в качестве доверенного подписчика, не смогут создать верную ДЦП от имени доверенного участника B.
3. Строгая идентификация — каждый может идентифицировать соответствующую доверенную сторону из доверенной подписи.
4. Неотрекаемость — если доверенный подписчик создает подпись под документом, то в дальнейшем он не сможет заявить, что подпись выполнена кем-то другим.
5. Противостояние злоупотреблению — доверенная сторона не должна использовать ключ подписания для целей, не разрешенных доверителем в информации о полномочиях. В случае злоупотребления ответственность доверенного подписчика должна определяться явно.
В данной работе изложены базовый протокол ДЦП, предложенный в [1], его модификация ЬСК из [5] на случай открытого канала связи и атака на нее из [6], демонстрирующая нарушение в ней требования 2 к безопасности. Предложено усовершенствование протокола ЬСК, устранившее его уязвимость этой атакой и сохранившее его пригодность для открытого канала. Предложен также протокол коллективной ДЦП с защищенным каналом связи, который можно использовать при реализации процедуры голосования. Все протоколы основаны на общей идее распределения ключевой информации, которая позволяет делегировать права подписи доверенной стороне, и построены по следующей общей схеме.
1. Общая схема протокола ДЦП
Основная идея, используемая при создании доверенных подписей, —построить такую схему распределения ключевой информации, чтобы можно было использовать уже существующие алгоритмы цифровой подписи. В распределении ключевой информации лежит следующий принцип.
Пусть имеются два участника информационного обмена Л и И — соответственно доверитель права цифровой подписи и его доверенная сторона (доверенное лицо), получающая право подписывать от имени доверителя. Каждый из участников Л и В имеет свою пару ключей — (Ха,Уа) и (хв,ув) соответственно, где первый ключ (х) в паре закрытый, а второй (у) открытый. Л генерирует доверенность на право подписания от его имени и вместе с информацией о полномочиях (период действия доверенной подписи, типы документов, которые разрешено подписывать доверенной стороне, идентификаторы доверителя и доверенного лица и т.п.) передает (по защищенному или открытому каналу) участнику В, который на основании информации, содержащейся в доверенности, идентифицирует Л и создает пару доверенных ключей (хр ,уР), предназначенных соответственно для создания и проверки цифровой подписи по некоторому известному алгоритму. Теперь при помощи хр он может подписывать сообщения от лица Л, применяя этот алгоритм. Любой проверяющий должен самостоятельно вычислить ключ ур участника В, используя информацию из доверенности участника Л. Таким образом, убедившись, что ключ участнику В действительно доверил участник Л, можно проверить подпись с помощью процедуры верификации из того же алгоритма цифровой подписи.
Общая схема протокола ДЦП, реализующая эту основную идею, выглядит следующим образом.
Действия доверителя Л:
1. Генерирует случайное обязательство к и вычисляет его свидетельство К = f (к), где f — некоторая односторонняя функция.
2. Создает в а, зависящую от величин из {ха,Ув , к,К} и возможных полномочий , и величины в а, К и, возможно, , составляющие доверенность, отправляет доверенному лицу В.
Действия доверенной стороны В:
1. Проверяет (с целью идентификации Л) выполнение некоторого идентификационного условия, зависящего от у а, ув и полученных в а и К.
2. Если оно выполнено, то вычисляет доверенные ключи: xp — в зависимости от Sa,Xb, yа,Ув и, возможно, mw; yp = f (xp).
3. С помощью подходящего алгоритма ЦП подписывает некоторый документ M, используя xp в качестве ключа подписания. Созданную так подпись обозначает Sign(M, xp). Формирует доверенную подпись под M как a = (Sign(M, xp), K, yA, yB, mw), возможно, без mw.
Действия проверяющего:
1. Вычисляет ключ yp, применяя некоторый алгоритм к данным Уа,Ув, K и, возможно, mw, содержащимся в a.
2. По ключу yp проверяет подпись Sign(M, xp) под документом M при помощи процедуры верификации соответствующего алгоритма ЦП.
Конкретные протоколы, построенные по этой схеме, различаются друг от друга алгоритмами выполнения перечисленных в ней действий участников протокола, которые (алгоритмы), в свою очередь, зависят и от применяемого математического аппарата, и от характера используемого канала передачи данных — открытый или закрытый, и от вида информации о полномочиях, в том числе от ее наличия или отсутствия.
В рассматриваемых далее конкретных протоколах ДЦП используется аппарат теории чисел. В них, кроме уже обозначенного, используются: p и q — большие простые числа, причем q|p — 1; д Е Z*, порядок д равен q и д является общеизвестным. Считается, что вычисление дискретного логарифма — трудоёмкая задача. Соответственно в роли односторонней функции f (к) выступает дк mod p. Первый и второй ключи (x и y) в паре ключей каждого участника и в паре доверенных ключей связаны соотношением y = дх mod p. Действие 3 участника B и действие 2 проверяющего из общей схемы сохраняются во всех протоколах, с тем лишь уточнением, что в последних используется алгоритм ЦП, базирующийся на сложности задачи дискретного логарифмирования. В приводимых ниже описаниях протоколов эти действия опущены.
2. Протокол MUO
Этот протокол предложили М. Mambo, K. Usuda и E. Okamoto (MUO) в [1]. Именно он и является базовым для модификаций, рассматриваемых в данной работе.
Действия A:
1. Генерирует случайное число к Е Z* и вычисляет K = дк mod p.
2. Вычисляет Sa = (xa к • K) mod q и посылает (sa, K) участнику B по защищенному каналу связи.
Действия B:
1. Для идентификации A проверяет сравнение: дЯА = уа • KK(mod p).
2. Если оно выполнено, то вычисляет доверенный ключ подписания
xp = (sa xb • Ув) mod q.
Действия проверяющего:
1. Зная (из подписи) свидетельство K, открытые ключи доверителя (уа) и доверенной стороны (ув), вычисляет доверенный ключ yp для проверки подписи по правилу
yp = У а • KK • yyB mod p.
Заметим, что данный протокол не удовлетворяет пятому требованию безопасности, поскольку действие 2 участника A не включает в себя передачу информации о полномочиях.
В приводимых ниже модификациях протокола MUO действие 1 участника A то же самое, что и в базовом протоколе, в связи с чем в их описаниях оно опущено.
3. Протокол LCK
Протокол MUO требует наличия защищенного канала между доверителем и доверенной стороной. В своей работе [5] J.-Y. Lee, J.-H. Cheon и S. Kim (LCK) модифицировали его, что позволило передавать доверенность по открытому каналу.
Действия A:
2. Вычисляет sa = (xa k ■ ув) mod q и пару (sa, К) отправляет участнику B по общедоступному каналу.
Действия B:
1. Проверяет идентификационное условие = Уа ■ КУв(modp).
2. Если оно выполнено, то B вычисляет доверенный ключ подписания:
Xp = (sa хв ■ уа) mod q.
Действия проверяющего:
1. Вычисляет ключ yp по следующему правилу: yp = Уа ■ KУв ■ уВА mod p.
В [6] показано, что такая модификация протокола MUO приводит его к уязвимости, позволяющей:
1) сторонам A и B доверенный ключ подписания создавать независимо друг от друга, т. е. без участия их в выполнении протокола, и тем самым участнику A доверенную подпись за участника B ставить без его ведома, а участнику B подпись от имени A ставить, не имея на то доверенности от последнего;
2) третьей стороне C доверенный ключ подписания создать независимо от участников A и B, т. е. без их участия в выполнении протокола, и тем самым поставить доверенную подпись;
3) третьей стороне C доверенность для B модифицировать под себя, т. е. изменить её таким образом, как если бы участник A доверил право подписи стороне C, а не участнику B.
Первая атака выглядит следующим образом. Если A возьмет случайное число s и
вычислит K = ■ yByA Ув mod p и xp = (xA s ■ yB) mod q, то это xp будет обладать
свойством доверенного ключа подписания, а именно: подпись, поставленную этим ключом, любой проверяющий ее на ключе yp примет за подпись, поставленную стороной B
от имени стороны A, ибо yp = yA ■ Kув ■ ууА mod p = yA ■ у-УА У_ j уВА mod p =
= Уа ■ gsyB mod p = gXAgsyB mod p = mod p, т. е. (xp, yp) является доверенной парой ключей.
Обратно, если участник B возьмет случайное s и изготовит K = ■ УаУв mod p и
xp = (s ■ уБ xb ■ Уа) mod q, то будет yp = Уа ■ KУв ■ ууА mod p = Уа ■ у-1 gsyB ■ УуА mod p = = ^*Ув^ХвУА mod p = mod p, что означает, что и это xp является доверенным ключом подписания.
Вторая атака выглядит следующим образом. Если C возьмет случайное число s и вычислит K = у-Ув ■ у-УА Ув ■ mod p и xp = s ■ yB mod q, то это xp будет также обладать свойствами доверенного ключа подписания, так как yp = Уа ■КУв ■ уУА mod p =
1 1 Ув
УаУ- ■ У-УА’У_ ■ 9J УбА mod p = Уа ■ yA1 ■ У-УА ■ ^^’Ув ■ УбА mod p = ^5’Ув mod p = = mod p.
Третья атака заключается в следующем: имея (из открытого канала) доверенность (sa,K), предназначенную участником A для B, сторона C берёт случайное число k G Z*, вычисляет К = КУв’Ус 1 ■ mod p и sA = sA k ■ yC mod q и получает пару
(sa, К), обладающую свойствами доверенности, сгенерированной участником A для C, так как д5А mod p = g^ yc mod p = дЖА кУв kyc mod p = yA ■ g(kУв ‘y_1 k)yc mod p = = yA ^KУв ■y-1 ■ gkj mod p = yA ■ КУс mod p.
4. Авторская модификация протокола MUO
Предлагается следующая модификация протокола MUO с передачей доверенности по открытому каналу и без уязвимости предыдущей модификации.
Действия A:
2. Вычисляет sa = (xa k ■ yB ■ К) mod q и пару (sa, К) отправляет участнику B по общедоступному каналу связи.
Действия B:
1. Проверяет сравнение д5А = Уа ■ КУв^K(modp).
2. Если оно выполнено, то B вычисляет доверенный ключ подписания как
xp = (sa xb ■ уа) mod q.
Действия проверяющего:
1. Зная (из подписи) свидетельство К, открытые ключи доверителя (уа) и доверенной стороны (ув), вычисляет доверенный ключ yp для проверки подписи по правилу
yp = Уа ■ КУв ■K ■ уУА mod p.
Здесь, как и в протоколе LCK, доверенность sa зависит от значения у в. Предположим, что злоумышленник C воспользуется переданной по открытому каналу доверенностью и создаст секретный ключ xp = sa xc ■ Уа. В этом случае соответствующий открытый ключ имеет вид yp = gXp mod p = Уа ■ КУв ‘K ■ уУА mod p. Злоумышленник подписывает документ и заявляет, что сделал это по доверенности от A. Согласно протоколу, лицо, проверяющее эту подпись a = (Sign(M, xp), К, Уа, yc), располагая только свидетельством К, открытыми ключами доверителя (уа) и злоумышленника (yc), не сможет корректно вычислить yp и проверить подпись а, не подставив в выражение для yp значения открытого ключа ув того участника B, для которого в действительности предназначалась доверенность, и тем самым уличит мошенника. Таким образом, добавив в доверенность зависимость sa от ув, доверитель A однозначно определил доверенную сторону, что позволило использовать открытый канал для передачи доверенности.
Покажем, что при невозможности взятия дискретного логарифма атаки из [6], описанные выше, на этот протокол невозможны.
В самом деле, реализация первых двух атак выглядит следующим образом.
В первой атаке участник A должен взять такие s и К, чтобы для xp = (xa s ■ ув) mod q выполнилось равенство gXp mod p = yp, т. е. сравнение
Уа ■ #5Ув = Уа ■ КУв■K ■ уУА (modp),
или, что то же самое,
КK = gs ■ у~вА’У_1 (modp).
С другой стороны, участник B должен подобрать s и К так, чтобы для xp = (s ■ ув xB ■ Уа) mod q выполнилось равенство gXp mod p = yp, т. е. сравнение
КK = gs ■ yAy_ (mod p).
Для реализации второй атаки злоумышленник C должен подобрать значения s и К так, чтобы для xp = s ■ ув mod q выполнялось равенство gXp mod p = yp, т. е. сравнение
КK = gs ■ yAУ_ 1 ■ уВУА У_ 1 (mod p).
Для реализации третьей атаки злоумышленнику C необходимо подобрать такие значения k и К, чтобы выполнилось сравнение
gM fc^c = yA ■ КУс K(mod p),
или, что то же самое,
КK = gk ■ КУв’Vc ‘K(modp).
Следовательно, в каждом случае злоумышленник должен создать такие x и y, которые удовлетворяют сравнению уУ = agx(modp) для заданных a, g и p. При выбранном y нахождение нужного x требует вычисления дискретного логарифма, а при выбранном x нахождение нужного у представляется не менее сложной задачей.
Таким образом, добавив в протокол LCK зависимость sa от К, удалось убрать его слабость к атакам из [6].
5. Протокол коллективной ДЦП
Построим протокол ДЦП, в котором участвуют доверитель A и доверенное множество B, состоящие из n доверенных сторон B1, B2, …, Bn. Доверенная подпись, поставленная любым из участников множества B, должна удовлетворять следующим условиям.
1) Проверяющий может убедиться, что подпись поставил один из участников B, но не должен узнать, кто именно.
2) Доверитель A может однозначно идентифицировать участника множества B, подписавшего документ.
Пусть для каждого i = 1, 2,… , n имеются: xj — секретный и у^ — открытый ключи участника Bj, связанные соотношением у^ = gxi mod p.
Действия A:
1. Генерирует случайные числа r1,…,rn G Z* и публикует набор чисел R1 = = gr1 mod p, … , Rn = grn mod p без указания их соответствия участникам из множества B. Все значения R1,… , Rn должны быть различны.
2. Для каждого i = 1, 2,… ,n вычисляет Sj = (xa Г ■ Rj) mod q и посылает (Si, Ri) участнику B» по защищенному каналу связи. Значение R необходимо передавать участнику Bj, так как последний не знает, какой именно элемент из опубликованных следует применять в вычислениях при идентификации A.
Действия множества B:
Для каждого i = 1, 2,… , n участник B» производит следующие действия:
1. Для идентификации участника A проверяет сравнение gSi = уа ■ RRi (mod p) и, если оно выполнено, то принимает Sj.
2. Выбирает случайное k G Z*, вычисляет К» = gki mod p и s» = k x» ■ К» mod q. Отправляет пару (sj, Kj) как доверенность участникам множества B по защищенному каналу связи. На этом шаге B» доверил право подписи другим участникам множества B.
Таким образом, каждый участник Bj располагает набором
(Sj , Rj , s1 , . . . , sn, К1 , . . . , Kn) .
Действия подписывающего участника В^
1. Вычисляет секретный ключ (для доверенного подписания)
П
xVi = Si Y, Sj(mod q). j=i
2. Доверенная подпись под документом M, поставленная с использованием ключа xPi, имеет вид a = (Sign(M, xPi); уа; Ri; yi,… , y« Ki,… , K«). Документ с подписью помещается на общедоступный ресурс.
Действия проверяющего:
1. Проверяет, что значение Ri из a содержится в наборе, опубликованном доверителем.
2. Вычисляет открытый ключ (для проверки доверенной подписи)
n
ypi = Уа ■ rRi П (Kj ■ yjKj ) mod p. (1)
j=i
(Непосредственно проверяется, что ypi = gXpi mod p, т. е. ypi —действительно ключ для проверки подписи Sign(M, xpi).)
В подписи a под документом M содержится открытый ключ доверителя (уа) и параметр Ri, который использовался при вычислении доверенности участника A участнику Bi в B. При вычислении открытого ключа (1) эти параметры позволяют убедиться, что подпись поставлена с согласия доверителя A одним из участников в B. Остальные n множителей имеют вид Kj ■ y- j. Исходя из этой информации, проверяющий не может сделать вывод, кто именно из участников множества B поставил подпись. Доверитель же A по элементу Ri может установить, кто из участников в B подписал сообщение.
Протокол коллективной ДЦП можно использовать для реализации процедуры голосования. Пусть доверитель хочет, чтобы n доверенных лиц проголосовали от его имени. Для этого он наделяет их соответствующими полномочиями, выполняя указанный протокол. Каждое доверенное лицо вычисляет свой секретный ключ и подписывает сообщение (голос). Проверяющий в момент вычисления открытого ключа контролирует, что значение Ri не повторяется. Это является залогом того, что каждое доверенное лицо проголосовало единожды. Проверяющий не может проверить, как проголосовал каждый из участников. Доверитель может идентифицировать подписавшего по значению Ri, что является борьбой со злоупотреблением со стороны доверенного лица.
Заключение
Таким образом, автору удалось убрать уязвимость протокола LCK и создать более безопасный протокол, в котором для передачи доверенности не требуется защищенный канал связи. Однозначное определение доверителем доверенной стороны можно считать особенностью предложенного протокола, которую целесообразно использовать и при реализации протоколов с секретным каналом. Предложен протокол голосования на базе алгоритма коллективной ДЦП. Автор считает, что разработка прикладных протоколов на базе существующих протоколов ДЦП является интересным направлением, позволяющим найти им применение в существующих задачах.
ЛИТЕРАТУРА
1. Mambo M., Usuda K., and Okamoto E. Proxy signatures: Délégation of the power to sign
messages // IEICE Trans. Fundamentals. 1996. V. E79-A. No. 9. P. 1338-1353.
2. Mambo M., Usuda K., and Okamoto E. Proxy signatures for delegating signing operation // Proc. of 3rd ACM Conference on Computer and Communications Security (CCS’96). ACM Press, 1996. P. 48-57.
3. Kim S., Park S., and Won D Proxy signatures, revisited // Information and Communications Security (ICICS’97). 1997. LNCS. V. 1334, P.223-232.
4. Lee B., Kim H., and Kim K. Strong proxy signature and its applications // Proc. of the 2001 Symposium on Cryptography and Information Security (SCIS’01), Oiso, Japan, Jan. 23-26, 2001. V. 2/2. P. 603-608.
5. Lee J.-Y., Cheon J.-H., and Kim S. An analysis of proxy signatures: Is a secure channel necessary? // LNCS. 2003. V. 2612. P. 68-79.
6. Wang G., Bao F., Zhou J., and Deng R. H. Security Analysis of Some Proxy Signatures // LNCS. 2004. V. 2971. P. 305-319.
Пример шифра
Теперь, когда даны основные определения, рассмотрим одну из простейших систем шифрования, которая носит имя “шифр Юлия Цезаря”. Предполагается, что знаменитый римский император и полководец, живший в 1 веке до нашей эры, использовал этот шифр в своей переписке.
Шифр Цезаря применительно к русскому языку
пример
1.1 состоит в следующем. Каждая буква сообщения заменяется на другую, которая в русском алфавите отстоит от исходной на три позиции дальше.
Таким образом, буква A заменяется на Г , Б на Д и так далее вплоть до буквы Ь , которая заменялась на Я , затем Э на A , Ю на Б и, наконец, Я на В .
Так, например, словоЗАМЕНА после шифрования методом Цезаря превратится в КГПЗРГ .
Это не очень сложный метод, тем более что при шифровании сообщений из нескольких слов сразу становится понятным, сколько слов содержал исходный текст. Кроме того, можно получить некоторую информацию по анализу повторов букв в зашифрованном сообщении.
Например, в зашифрованном КГПЗРГ одна из букв повторяется дважды. Тем не менее, Цезарь вошел в историю криптографии, а “шифр Юлия Цезаря”, как его до сих пор называют, служит примером одной из первых систем шифрования.
Для расшифрования сообщения КГПЗРГ необходимо знать только сам алгоритм шифрования. Любой человек, знающий способ шифрования, легко может расшифровать секретное сообщение. Таким образом, ключом в данном методе является сам алгоритм.
Каким образом можно усовершенствовать шифр Цезаря? Можно было бы попытаться расширить алфавит с 33 до 36 символов и более за счет включения знаков препинания и пробелов. Это увеличение алфавита замаскировало бы длину каждого отдельного слова.
В криптографии принято считать, что противник может знать использованный алгоритм шифрования, характер передаваемых сообщений и перехваченный шифротекст, но не знает секретный ключ. Как уже упоминалось выше, это называется принципом Керкхоффса.
Усовершенствуем шифр Цезаря с учетом правила Керкхоффса.
Предположим, что буквы сдвигаются не на три знака вправо, а на n (0<n<33). В этом случае в системе
шифрования появляется ключ – число n – параметр сдвига.
Отправитель и получатель могут каким-либо
образом договариваться (например, лично) и иногда менять значение ключа. Так как n может принимать разные значения, знание одного только алгоритма не позволит противнику расшифровать секретное сообщение.
Каким же образом может действовать в том случае злоумышленник, чтобы узнать содержание сообщения? Пусть,
например, перехвачено секретное сообщение ЧСЮЭЮЪ. Противнику известно, что ключ (параметр сдвига
n) может принимать значения от 1 до 32.
Пытаясь найти значение секретного
ключа, мы будем проводить атаку по шифротексту. Рассмотрим способ последовательного перебора всех возможных ключей
(это так называемый метод “грубой силы”).
Запишем на 32 строчках все варианты, которые получаются сдвигом
каждой буквы на 1, 2, 3, … , 32 позиции соответственно. Эту операцию можно проводить вручную, а можно
составить несложную программу, которая запишет все варианты перебора параметра n в файл. Одна из этих
32 строк будет содержать исходное сообщение (
таблица
1.1).
Мы видим, что единственное слово, имеющее смысл, – это ЗВОНОК. Это слово располагается на 17 месте. Следовательно, если шифрованный текст сдвинуть на 17 позиций вперед получится открытый текст.
Это означает, что для получения шифрованного текста открытый текст нужно сдвинуть на (33-17)=16 позиций. Таким образом, получили, что при шифровании ключn=16.
Так как ни при каком другом сдвиге не получилось осмысленного сообщения, то, скорее всего, мы правильно дешифровали это сообщение. Такое допущение о единственности решения вполне обоснованно, когда исходное сообщение составлено на одном из естественных языков (в рассмотренном примере – русском) и содержит более пяти-шести знаков.
Так, например, пусть исходный алфавит состоит из арабских цифр, то есть имеет вид
Один из абонентов желает переслать другому секретный код замка, состоящий из пяти цифр и равный
12345. Отправитель и получатель заранее договорились о том, что ключ шифрованияn будет
равен 3.
Отправитель шифрует выбранным ключом исходное сообщение 12345, получает
45678 и переправляет полученное значение своему абоненту. Возможно, противник перехватит криптограмму и
попытается вскрыть ее, используя, как и раньше, метод последовательного перебора.
Так как исходный алфавит состоял
из 10 символов, то значение ключа может лежать в диапазоне от 1 до 9.
Видно, что все полученные варианты равнозначны и злоумышленник не может понять, какая именно комбинация истинна. Анализируя шифротекст, он не может найти значения секретного ключа. Конечно, один из приведенных в таблице вариантов подойдет к кодовому замку, но в столь простом методе шифрования нельзя рассчитывать на большую секретность.
В первом примере сообщение — текст на русском языке, поэтому оно подчиняется многочисленным правилам, различные буквы и их сочетания имеют различные вероятности и, в частности, многие наборы букв вообще запрещены. (Это свойство называется избыточностью текста).
Поэтому-то и удалось легко подобрать ключ и дешифровать сообщение, т.е. избыточность позволила “взломать” шифр. В противоположность этому, во втором примере все комбинации цифр допустимы.
“Язык” кодового замка не содержит избыточности. Поэтому даже простой шифр, примененный к сообщениям этого языка, становится невскрываемым в случае атаки только по шифротексту. Если же мы имеем возможность проводить атаку и по открытому тексту, то есть имеем пары “открытое сообщение” – “зашифрованное сообщение”, то раскрытие становится совершенно простым как в случае использования символов-букв, так и в случае символов-цифр.
Приведенные простые примеры показывают, что вероятность успешного криптоанализа зависит от многих факторов: от системы шифрования, от длины перехваченного сообщения, от языка и алфавита исходного сообщения. В последующих лекциях постараемся подробнее рассмотреть все эти факторы.
Сведения из истории криптографии
Исторически криптография развивалась как практическая дисциплина, изучающая и разрабатывающая способы шифрования письменных сообщений. В распоряжении историков имеются данные, что криптографические методы применялись в Древнем Египте, Индии, Месопотамии. Так, например, в записях египетских жрецов есть сведения о системах и способах составления шифрованных посланий.
Древние греки оставили документальные подтверждения о различных применяемых ими шифровальных системах. Греками, а вернее спартанцами, во время многочисленных войн применялось одно из первых шифровальных устройств – Сцитала. Сцитала представляла собой цилиндрический жезл определенного диаметра.
На Сциталу виток к витку наматывалась узкая полоска папируса (или кожаного ремня). На намотанной ленте вдоль оси жезла писали открытое сообщение. Затем ленту разматывали и переправляли адресату. После снятия папируса с жезла выходило как будто буквы сообщения написаны в беспорядке поперек ленты.
Если папирус попадал в руки противника, то секретное сообщение прочитать было невозможно. Для получения исходного текста была необходима Сцитала точно такого же диаметра – на нее наматывалась полученная полоска папируса, строки сообщения совмещались, и в результате можно было прочитать секретное послание.
Ключом в данном методе шифрования являлся диаметр Сциталы. Интересно, что изобретение дешифровального “устройства” приписывается Аристотелю. Предполагается, что именно он предложил использовать конусообразное “копье”, на которое наматывалась перехваченная лента с зашифрованным сообщением. Лента с буквами передвигалась вдоль оси конуса до тех пор, пока не появлялся осмысленный текст.
В Древней Греции использовались и другие шифры. Так, например, там был изобретен шифр, который в дальнейшем стал называться “квадратом Полибия”. Согласно этому шифру буквы сообщения заменялись числами, представляющими собой координаты в квадрате 5×5, в который вписаны символы алфавита. Многочисленные исторические документы подтверждают, что в политике и в военном деле широко применялись различные шифры.
В арабских странах шифрование сообщений довольно широко использовалось как в военных, так и в политических целях и даже в переписке между торговыми партнерами. Кстати, слово “шифр” арабского происхождения, так же как и слово “цифра”.
В VIII – XV веках на свет появляются научные труды, содержащие сведения по криптографии: описания различных шифров и даже некоторых методов криптоанализа. Так, в многотомной энциклопедии “Шауба аль-Аша” упоминается о частотном криптоанализе (то есть анализе, основанном на частоте встречаемости букв открытого и зашифрованного сообщений). В этой же энциклопедии приводится таблица частотных характеристик букв арабского языка.
В средние века криптографические методы использовались, прежде всего, в военном деле, шпионаже, дипломатии. Изучением шифров занимались священники, ученые и дипломаты. На практике применялись различные шифры. Первые труды по криптографии созданы в XIV – XVI веках Чикко Симоннети (сотрудником папской канцелярии)
, Габлиэлем де Лавиндой (секретарем папы Клементия XII), Леоном Баттистой Альберти (знаменитым итальянским архитектором и философом), аббатом Иоганнесом Тритемием, жившем в Германии. Все указанные деятели внесли большой вклад в развитие криптографии, так как не только рассматривали в своих трудах существующие шифры, но и предлагали различные усовершенствованные методы шифрования, а также некоторые простейшие методы криптоанализа.
Так, например, в трудах Симоннети и де Лавинды предлагаются шифры пропорциональной замены, в которых наиболее часто встречаемым буквам ставится в соответствие несколько символов для выравнивания частоты встречаемости знаков в шифротексте. Леон Альберти, вероятно, первым предложил так называемые полиалфавитные шифры.
Нововведение Альберти состояло в том, чтобы использовать несколько замен в соответствии с ключом. Предполагается, что он также изобрёл первую автоматическую шифровальную машину — шифровальный диск, который осуществлял частичную реализацию его изобретения.
В XVII-XVIII веках во многих государствах Европы появились специальные шифровальные службы. В России датой появления криптографической службы специалисты называют 1549 год, когда был создан “посольский приказ”, в котором имелось “цифирное” отделение.
В различные времена криптографией занимались многие политики и ученые. Среди них Пифагор, Аристотель, Платон, Галилей, Д. Порта, Д. Кардано, Л. да Винчи, Ф. Виет, Д. Валлис, Б. Паскаль, И. Ньютон, Ф. Бекон, Х. Гольбах, Ф. Эпинус, Л. Эйлер, П.Ф. Шиллинг, Ч. Беббидж и другие.
Огромное влияние на развитие криптографии оказывают достижения научно-технического прогресса. Так, например, в середине XIX века после изобретения телеграфа появилось несколько дипломатических и коммерческих шифров, ориентированных на применение телеграфа.
Возрастание скорости передачи данных требовало увеличения скорости шифрования. В конце XIX века появились механические шифраторы Т. Джефферсона и Ч. Уитстона. С конца XIX века криптография стала серьезной отраслью научных знаний и стала изучаться как отдельная наука в военных академиях.
В XX веке появились новые возможности по передаче информации на большие расстояния с большой скоростью. В связи с применением радиосвязи расширились возможности доступа к шифрованной информации в процессе ее передачи. Научно-технический прогресс преобразил криптографию, которая стала вначале электромеханической, а затем электронной.
В XX веке возникает специализация в криптографической деятельности. Появляются специалисты по шифрованию, по перехвату зашифрованных сообщений, по дешифрованию шифров противника.
В 20-х годах XX века для автоматизации процесса шифрования появились многочисленные механические устройства. В частности, широко использовались роторные шифровальные машины, в которых для выполнения операций замены символов применялись механические колеса – роторы.
Шифровальные машины преобразовывали открытый текст в зашифрованный, состоящий из символов того же алфавита. После преобразования зашифрованная информация могла передаваться различными способами, например, по радиоканалу.
В середине ХХ века разработкой криптографических алгоритмов стали заниматься профессиональные математики и специалисты в области информатики. Существенное влияние на развитие криптографии оказала работа американского инженера-математика К.
С 50-х годов ХХ века в криптографии используется электронная вычислительная техника. Начинается создание так называемых блочных шифров, которые позволяют обрабатывать информацию целыми фрагментами или блоками. Первоначально для операций блочного шифрования разрабатывали аппаратные устройства с жесткой логикой, однако стремительное развитие возможностей вычислительной техники позволило создать программные аналоги блочных систем шифрования.
С развитием информационных технологий криптография не только приобрела новые сферы применения, но и претерпела значительные изменения. В древние времена в процессе обмена зашифрованными сообщениями участвовало только две стороны, поэтому ключом шифрования необходимо было обеспечить только эти две стороны.
В современных информационных системах в процессе передачи информации задействовано множество абонентов, и все они заинтересованы в надежных и удобных каналах получения ключей шифрования. Проблема распределения ключей была решена в двадцатом веке благодаря изобретению нового принципа шифрования – асимметричного шифрования или шифрования с открытым ключом (70-е годы ХХ в.).
Основоположниками этого метода шифрования считаются У. Диффи и М. Хеллман. В асимметричных алгоритмах шифрования используются специальные математические функции – односторонние функции. Открытие асимметричных криптосистем позволило еще больше расширить сферы применения криптографии.
Именно шифрование с открытым ключом лежит в основе процедур формирования цифровой подписи и проверки подлинности, а следовательно, и в основе принципов работы банковских пластиковых карт, “электронных” денег и других современных технологий.
Новые сферы применения криптографии привлекают математиков к решению криптографических проблем, а также к созданию новых направлений в математике, теории информации и других смежных науках.
Управление открытыми ключами
Благодаря асимметричной криптографии проблема распределения секретных ключей, рассмотренная нами в лекции 8, была решена, вернее, ликвидирована, однако, появилась новая проблема – проблема подтверждения подлинности открытых ключей. Эта проблема заключается в том, что, получая открытый ключ некоторого абонента А, пользователь должен быть уверен, что ключ принадлежит именно абоненту А, а не кому-то другому.
Дело в том, что в исходном виде система распределения ключей, предлагавшаяся Диффи и Хеллманом, давала возможность проведения различного рода атак, основанных на перехвате и подмене открытых ключей абонентов. Так, например, в лекции 11 нами была рассмотрена атака “человек-в-середине”, позволявшая злоумышленнику осуществлять полный контроль над передаваемой в системе связи информацией.
Большую роль в решении проблемы сертификации открытых ключей сыграло создание цифровой подписи. В системах связи с большим количеством абонентов, применяющих асимметричные криптосистемы, стали использовать специальные организационные структуры, выполняющие функции управления ключами абонентов и занимающиеся сертификацией открытых ключей.
Эти организационные структуры играют роль доверенной третьей стороны и заверяют открытые ключи абонентов своими цифровыми подписями. Таким образом, в распределенных системах связи, использующих криптосистемы с открытыми ключами, вводится понятие инфраструктуры открытых ключей (Public Key Infrastructure – PKI), включающей комплекс программно-аппаратных средств, а также организационно-технических и административных мероприятий, обеспечивающих абонентам системы связи необходимый сервис для управления их открытыми ключами.
Основным элементом инфраструктуры открытых ключей является центр сертификации ( удостоверяющий центр ) (Certification authority, CA), который обеспечивает контроль за выполнением всех процедур, связанных с изготовлением, регистрацией, хранением и обновлением ключей, сертификатов открытых ключей и списков отозванных сертификатов.
Сертификат представляет собой информацию, заверенную цифровой подписью центра, и включающую открытый ключ и другие данные об абоненте. Такими данными являются, например, идентификатор алгоритма электронной подписи, имя удостоверяющего центра, срок годности сертификата, имя пользователя, которому принадлежит сертификат. Международный стандартISO X.
Сертификат обладает следующими свойствами:
Так как сертификаты не могут быть подделаны, их можно опубликовать, поместив в общедоступный справочник.
Каждый пользователь системы связи может быть владельцем одного или нескольких сертификатов, сформированных удостоверяющим центром. Открытый ключ абонента может быть извлечен из сертификата любым пользователем, знающим открытый ключ администратора удостоверяющего центра.
В распределенных системах связи с большим числом абонентов может быть создано несколько центров сертификации. Центры сертификации объединяются в древовидную структуру, в корне которой находится главный удостоверяющий центр. Главный центр выдает сертификаты подчиненным ему центрам сертификации, тем самым заверяя открытые ключи этих центров.
Открытый ключ пользователя формируется на основе закрытого ключа. Каждый пользователь должен хранить свой закрытый ключ таким образом, чтобы никто другой не смог узнать его значение.
Если же у владельца ключа есть основания полагать, что ключ стал известен кому-либо еще, то такой закрытый ключ считается скомпрометированным, и потерпевший, допустивший компрометацию своего ключа, должен оповестить всех остальных абонентов системы связи, что его открытый ключ следует считать недействительным.
Сертификаты открытых ключей имеют период действия, однако любой сертификат может быть выведен из обращения (отозван) до истечения этого периода, если соответствующий сертификату секретный ключ пользователя скомпрометирован или скомпрометирован ключ удостоверяющего центра, использованный при формировании сертификата. Удостоверяющий центр должен информировать своих абонентов об отозванных сертификатах.
При такой организации администратор удостоверяющего центра не имеет доступа к секретным ключам пользователей, а значит, и к защищаемой с их помощью информации. Администратор может лишь подменить в справочнике сертификатов открытые ключи одного из абонентов или включить фиктивного абонента, от его имени войти в контакт и получить предназначенное ему сообщение. Для исключения таких конфликтов может применяться следующая схема подготовки и рассылки ключей.
- Администратор удостоверяющего центра генерирует пару (закрытый ключ, открытый ключ) и сообщает свой открытый ключ всем своим абонентам.
- Пользователь А выбирает закрытые ключи для выполнения операций шифрования и формирования ЭЦП, а также вычисляет соответствующие открытые ключи.
- Открытые ключи шифрования и подписи зашифровываются открытым ключом администратора и предъявляются в удостоверяющий центр для регистрации.
- Администратор удостоверяющего центра проверяет (расшифровывает своим закрытым ключом) открытые ключи пользователя А; изготавливает и подписывает сертификаты открытых ключей пользователя А и помещает их в справочники открытых ключей шифрования и открытых ключей подписей. Каждый из справочников предоставляется в распоряжение абонентов удостоверяющего центра.
- Любой пользователь системы может извлечь из справочника сертификат необходимого абонента, проверить подпись администратора под сертификатом (расшифровать его открытым ключом администратора) и извлечь открытый ключ.
Такая схема подготовки и распределения открытых ключей выглядит несколько тяжеловесной, однако она защищает абонентов системы связи от разнообразных конфликтных ситуаций. На практике рассмотренная схема дополняется метками времени в цифровых подписях, проверками дополнительных полей в сертификатах (например, срока действия) и другими проверками, повышающими безопасность функционирования всей системы в целом.
Необходимо отметить, что в настоящее время в связи с широким использованием асимметричных криптоалгоритмов для банковских, платежных и других систем инфраструктура открытых ключей постоянно совершенствуется.
