Асимметричные криптоалгоритмы

Алгоритм Лемпеля-Зива

Классический алгоритм Лемпеля-Зива - LZ77, названный так по году своего опубликования, предельно прост.

Он формулируется следующим образом «если в прошедшем ранее выходном потоке уже встречалась подобная последовательность байт, причем запись о ее длине и смешении от текущей позиции короче, чем сама эта последовательность, то в выходной файл записывается ссылка (смещение, длина), а не сама последовательность» Так фраза:

КОЛОКОЛ ОКОЛО КОЛОКОЛЬНИ

закодируется как

КОЛО(-4, 3)_(-5, 4)0_(-14, 7)ЬНИ

Так как системы шифрования данных часто используются для кодирования текстовой информации: переписки, счетов, платежей электронной коммерции, и при этом криптосистема должна быть абсолютно прозрачной для пользователя, то над выходным потоком криптосистемы часто производится транспортное кодирование, то есть дополнительное кодирование (не шифрование!) информации исключительно для обеспечения совместимости с протоколами передачи данных.

Все дело в том, что на выходе криптосистемы байт может принимать все 256 возможных значений, независимо от того был ли входной поток текстовой информацией или нет. А при передаче почтовых сообщений многие системы ориентированы на то, что допустимые значения байтов текста лежат в более узком диапазоне: все цифры, знаки препинания, алфавит латиницы, плюс, возможно, национального языка. Первые 32 символа набора ASCII служат для специальных целей. Для того чтобы они и некоторые другие служебные символы никогда не появились в выходном потоке, используется транспортное кодирование.

Наиболее простой метод состоит в записи каждого байта двумя шестнадцатеричными цифрами-символами. Так байт 252 будет записан двумя символами «FC»; байт с кодом 26, попадающий на специальный символ CTRL-Z, будет записан двумя допустимыми символами «1А». Но эта схема очень избыточна: в одном байте передается только 4 бита информации.

Симметричные схемы несмотря на множество преимуществ, обладают одним рьезным недостатком. Связан он с ситуацией, когда общение между собой производят не три четыре человека, а сотни и тысячи людей. В этом случае для каждой пары, переписывающейся между собой, необходимо создавать свой секретный симметричный ключ. Это в итоге приводит к существованию в системе из N пользователей N²/2 ключей. А это уже очень «приличное» число. Кроме того, при нарушении конфиденциальности какой-либо рабочей станции злоумышленник получает доступ ко всем ключам этого пользователя и может отправлять, якобы от его имени, сообщения всем абонентам, с которыми «жертва» вела переписку.

Своеобразным решеием этой проблемы явилось появление асимметричной криптографии. Эта область криптографии очень молода. Первая схема, имевшая прикладную значимость, была предложена всего около 20 лет назад. Но за это время асимметричная криптография превратилась в одно из основных направлений криптологии, и используется в современном мире также часто, как и симметричные схемы.

Асимметричная криптография изначально задумана как средство передачи сообщений от одного объекта к другому (а не для кониденциального хранения информации, которое обеспечивают только симметричные алгоритмы). Далее мы будем использовать термины «отправитель» - лицо, шифрующее, а затем отправляющее информацию по незащищенному каналу и «получатель» - лицо, принимающее и восстанавливающее информацию в ее исходном виде. Основная идея асимметричных криптоалгоритмов состоит в том, что для шифрования сообщения используется один ключ, а при дешифровании - другой.

Кроме того, процедура шифрования выбрана так, что она необратима даже по известному ключу шифрования - это второе необходимое условие асимметричной криптографии. То есть, зная ключ шифрования и зашифрованный текст, невозможно восстановить исходное сообщение - прочесть его вы имеете возможность только с помощью второго ключа - ключа дешифрования. А раз так, то ключ шифрования для отправки писем какому-либо лицу можно вообще не скрывать - зная его все равно невозможно прочесть зашифрованное сообщение. Поэтому, ключ шифрования называют в асимметричных системах «открытым ключом», а вот ключ дешифрования получателю сообщений необходимо держать в секрете - он называется «закрытым ключом». Напрашивается вопрос: «Почему, зная открытый ключ, нельзя вычислить закрытый ключ?» - это третье необходимое условие асимметричной криптографии - алгоритмы шифрования и дешифрования создаются так, чтобы зная открытый ключ, невозможно вычислить закрытый ключ.

В целом система переписки при использовании асимметричного шифрования выглядит следующим образом. Для каждого из N абонентов, ведущих переписку, выбрана своя пара ключей: «открытый» E_j и «закрытый» D_j, где j - номер абонента. Все открытые ключи известны всем пользователям сети, каждый закрытый ключ, наоборот, хранится только у того абонента, которому он принадлежит. В случае, если абонент, скажем под номером 7, собирается передать информацию абоненту под номером 9, он шифрует данные ключом шифрования Е₉ и отправляет ее абоненту 9.

Несмотря на то, что все пользователи сети знают ключ Е₉ и, возможно, имеют доступ к каналу, по которому идет зашифрованное послание, они не могут прочесть исходный текст, так как процедура шифрования необратима по открытому ключу. И только абонент номер 9, получив послание, производит над ним преобразование с помощью известного только ему ключа D₉ и восстанавливает текст послания. Заметьте, что если сообщение нужно отправить в противоположном направлении (от абонента 9 к абоненту 7), то нужно будет использовать уже другую пару ключей (для шифрования ключ Е₇, а для дешифрования - ключ D₇)

В асимметричных системах количество существующих ключей связано с количеством абонентов линейно (в системе из N пользователей используются 2*N ключей), а не квадратично, как в симметричных системах. Во-вторых, при нарушении конфиденциальности k-ой рабочей станции злоумышленник узнает только ключ D_k: это позволяет ему читать все сообщения, приходящие абоненту к, но не позволяет выдавать себя за него при отправке писем.

Дата добавления: 2014-01-11