Лекции по криптографии. М.: Мцнмо, . -е изд., стереотип. с. Брошюра издана по материалам лекций по криптографии, прочи
жүктеу/скачать 460.25 Kb. Pdf көрінісі
|
| Задача дискретного логарифмирования
Рассмотрим в качестве шифрующей функции выражение F(x) = a x mod p, () где p — большое простое число, a — некоторое специально подобран- ное целое число, зависящее от выбора p. Тогда для вычисления F(x) имеются эффективные алгоритмы, реа- лизующие возведение целого числа в большую степень. В то же время, вычисление x по известному F(x) — это «трудная» математическая задача, известная как задача дискретного логарифмирования, для которой нет эффективных алгоритмов. Поэтому () — односторонняя функция и на ее основе построено большое количество криптографи- ческих схем. Учитывая указанную «множественность» криптографических ал- горитмов, часто в тех случаях, когда не требуется специально указы- вать, какой именно алгоритм использовался для шифрования и рас- шифрования, многие авторы применяют символические обозначения для этих процессов. Пусть x, как обычно, обозначает исходный текст. Тогда процесс шифрования (и зашифрованный текст) обозначают E(x), а соответ- ствующий процесс расшифрования, применяемый к зашифрованно- му тексту, обозначают D(E(x)). То, что алгоритмы E и D соответству- ют друг другу, выражается тождеством D(E(x)) = x для любого исход- ного текста x. Зашифрованный текст E(x) Исходный (открытый) текст x Расшифрованный (исходный) текст D(E(x)) Шифрование E Расшифрование D Рис. . Шифрование и расшифрование исходного текста 1.3. Математическая формализация 25 Если применяемые алгоритмы шифрования и расшифрования ис- пользуют открытый (K1) и закрытый (K2) ключи, соответствующие процессы записываются следующим образом. Шифрование с исполь- зованием открытого ключа K1 обозначается через E K1 ( x), расшифро- вание с использованием закрытого ключа K2 — через D K2 ( E K1 ( x)), а тот факт, что алгоритмы E и D, а также конкретные значения ключей K1 и K2 соответствуют друг другу, выражается тождеством D K2 ( E K1 ( x)) = x. Зашифрованный текст E k 1 (x) Исходный (открытый) текст x Расшифрованный (исходный) текст D k 2 (E k 1 (x)) Шифрование E k 1 Расшифрование D k 2 Рис. . Шифрование и расшифрование исходного текста с использованием пары клю- чей: открытого — k 1 и закрытого — k 2 2. Криптографические протоколы 2.1. Что такое криптографические протоколы Концепция односторонних функций и функций с секретом по- явилась как математическая формализация процессов шифрования и расшифрования. Однако очень быстро было замечено, что эта концепция может быть с успехом применена к решению и многих других не менее важных задач криптографии, т. е. таких задач, когда, взаимодействуя с удаленным партнером по компьютерным сетям, необходимо обеспечить надежность передачи информации своему партнеру, а с другой стороны, гарантировать, что эта информация не будет перехвачена противником. Кроме того, широкое развитие пере- дачи информации по сетям поставило и ряд совсем новых вопросов. Нужно, например, убедиться, что удаленный партнер именно тот, за кого он себя выдает, а если даже и тот, то нужны гарантии того, что он вас не обманет. Например, не откажется от своей подписи, или не откажется подписать контракт после того, как получит вашу подпись. Большое количество подобных задач нашло свое решение в виде так называемых криптографических протоколов. В простейшем слу- чае криптографический протокол — это последовательность взаимо- действий двух удаленных пользователей (которые не видят друг дру- га и не слишком друг другу доверяют), предназначенная для реше- ния какой-либо простейшей задачи. Тем не менее, точное выполнение протокола заведомо гарантирует строгое выполнение поставленной задачи, даже если один из пользователей попытается обмануть друго- го. Такие криптографические протоколы называются примитивными, и в различных публикациях по криптографии их приводится несколь- ко десятков. Объединяя в нужной последовательности несколько примитивных протоколов, можно получить прикладные криптографические схемы, в которых участвует практически неограниченное число пользо- вателей и которые предназначены для решения вполне серьезных и вполне актуальных задач, например, организации электронных торгов, или электронного голосования, или организации электрон- ной платежной системы. Важно подчеркнуть, что, как и в случае примитивных протоколов, прикладные криптографические схемы 2.2. Протокол подбрасывания монеты по телефону 27 разрабатываются таким образом, чтобы обеспечить надежность и за- щиту информации и самой схемы от возможных атак противников. Ниже приведено несколько примеров как примитивных протоко- лов с двумя участниками, так и упомянутых протоколов организации электронных торгов и электронного голосования. И наконец, последнее замечание. Большинство описанных в по- следующих разделах протоколов приведены в форме, использующей алгоритм RSA. Однако именно это не является обязательным. Учиты- вая то, что было сказано в п. .., нетрудно понять, что для конкрет- ной реализации того или иного криптографического протокола могут быть применены разные односторонние функции, основанные на ис- пользовании различных «трудных» математических задач. В резуль- тате получаются различные варианты одного и того же протокола, решающие одну и ту же задачу, но обладающие различными характе- ристиками, например, по быстродействию или по каким-либо другим параметрам []. 2.2. Протокол подбрасывания монеты по телефону Подбрасывание монеты, пожалуй, наиболее распространенная форма организации жребия между двумя участниками. Она предель- но проста, если оба участника присутствуют при жеребьевке лично. Однако ситуация сильно изменяется, если оба участника жеребьевки пытаются бросить жребий, находясь на разных концах телефонного провода или будучи связаны компьютерной сетью. Ситуация еще более ухудшается, если оба участника не слишком доверяют друг другу. Действительно, пусть два сослуживца обсуждают по телефону во- прос «кто первый сообщит неприятную новость начальнику» и пыта- ются решить его с помощью жеребьевки. Один из них подбрасыва- ет монету, а его партнер на другом конце провода пытается угадать результат этого подбрасывания. При этом проверка этого угадыва- ния целиком будет опираться только на честность подбрасывающего монетку участника и, по всей видимости, вероятность того, что со- общать новость начальнику придется его телефонному собеседнику, в этой ситуации значительно превысит одну вторую. Казалось бы, подобная задача не имеет решения. Тем не менее она решается, и даже довольно несложно, с помощью аппарата односто- ронних функций. Рассмотрим одностороннюю функцию f (x), удовлетворяющую следующим условиям: 28 2. Криптографические протоколы ) f (x) определена на некотором множестве целых чисел, которое содержит одинаковое количество четных и нечетных чисел; ) функция f (x) такова, что если f (x 1 ) = жүктеу/скачать 460.25 Kb. Достарыңызбен бөлісу:
|