Криптография с открытым ключом

       

Криптография с открытым ключом


Криптография с открытым ключом

Автор: Комкин С.А., гр.8331

В 1976 г. У.Диффи и М.Хеллманом был предложен новый тип криптографической системы - система с открытым ключом [public key cryptosystem]. В схеме с открытым ключом имеется два ключа, открытый [public] и секретный [private, secret], выбранные таким образом, что их последовательное применение к массиву данных оставляет этот массив без изменений.

Диффи и Хеллман ввели понятие односторонней функции с потайным ходом, в качестве которой использовали функцию дискретного возведения в степень

f(x) =  ?x (mod p),

где x – целое число, 1 ? x ? p-1, p – k-битовое простое число. Причем выбирается такое число ? < p, степени которого по модулю p представляют собой упорядоченное множество чисел {?1,?2,…,?p-1}, являющееся некоторой перестановкой чисел {1,2,…,p-1}. (Такое число ? называется первообразным корнем по модулю p).

            Даже для очень больших модулей p (например, при k = 1024 бит) для данного x легко вычислить значение этой функции. Эта процедура называется дискретным возведением в степень. Для ее выполнения достаточно выполнить около 2log2p операций умножения k-битовых чисел (или log2p умножений и log2p делений 2k-битовых чисел на k-битовые). Процедура дискретного возведения в степень основана на предварительном вычислении значений (по модулю p)

?1,?2,?4,?8,…,?2k-1.

Обратной к функции дискретного возведения в степень является функция f -1(y), которая ставит в соответствие заданному значению y такое значение x, для которого выполняется условие ?x = y (mod p). Задачей нахождения такого х является задача дискретного логарифмирования. Дискретные логарифмы сложно вычисляются, когда число p–1 содержит один большой простой множитель, например, когда оно представимо в виде  p–1 = 2p?, где p? – простое число. При этом условии трудоемкость задачи нахождения дискретного логарифма равна примерно умножений по модулю p. Решение такой задачи является вычислительно неосуществимым при больших значениях k (например при k ? 512), а следовательно при указанных условиях, накладываемых на выбор чисел p и ?, функция дискретного возведения в степень является односторонней.


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

Таким образом, шифрование с открытым ключом гарантирует конфиденциальность

Например, пользователь создал ключи шифрования и дешифрования Е и D. Шифрование сообщения "DATA" на ключе Ea показывается так: E(DATA)=ENDATA, а дешифрование на ключе D - D(ENDATA)=DATA. Предполагается, что знание D не раскрывает E и наоборот. Если опубликовать ключ шифрования, то любой пользователь может зашифровать сообщение на этом ключе, но только пользователи, обладающие соответствующим ключом дешифрования могут расшифровать эти сообщения. С другой стороны, если пользователь сохраняет в тайне ключ шифрования и публикует соответствующий ключ дешифрования, то любое лицо с помощью этого ключа может не только дешифровать сообщения, зашифрованные пользователем, но и убедиться в том, что сообщение не было изменено. Только пользователь, имеющий ключ шифрования, мог создать это сообщение. Это свойство, однозначно определяющее источник сообщения, позволяет пользователю, имеющему секретный ключ шифрования, посылать "подписанные" сообщения.


Содержание раздела