Криптография с открытым ключом
Криптография с открытым ключом
Автор: Комкин С.А., гр.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 и наоборот. Если опубликовать ключ шифрования, то любой пользователь может зашифровать сообщение на этом ключе, но только пользователи, обладающие соответствующим ключом дешифрования могут расшифровать эти сообщения. С другой стороны, если пользователь сохраняет в тайне ключ шифрования и публикует соответствующий ключ дешифрования, то любое лицо с помощью этого ключа может не только дешифровать сообщения, зашифрованные пользователем, но и убедиться в том, что сообщение не было изменено. Только пользователь, имеющий ключ шифрования, мог создать это сообщение. Это свойство, однозначно определяющее источник сообщения, позволяет пользователю, имеющему секретный ключ шифрования, посылать "подписанные" сообщения.
