Теоретические основы информатики - Аветисян Р.Д.
Скачать (прямая ссылка):
70 дату появления первых шифрограмм. Можно лишь с уверенностью утверждать, что они появились значительно раньше пятого века до нашей эры, когда патриарх истории древнего мира Геродот упоминал о текстах, понятных лишь для одного адресата [3]. Попытки разгадывания секретных ключей начались практически одновремено с появлением первых шифрограмм. За все время своего существования различные методы шифрования систематически совершенствовались. Но столь же последовательно совершенствовались методы разгадывания секретных ключей. Одно лишь осталось неизменным - необходимость наличия секретного ключа, известного лишь двум сторонам - отправителю конфиденциальных сообщений и их получателю. А для обмена секретными ключами всегда требовалось наличие некоторого закрытого, недоступного для третьих сторон канала связи.
Так было до 1976 года, когда американские специалисты У. Диффи и М. Хеллман предложили новый принцип шифрования конфиденциальных сообщений - принцип открытого шифрования [12].
Чтобы оценить значимость, место и роль принципа открытого шифрования, вкратце рассмотрим некоторые простейшие алгоритмы шифрования, ориентированные на использование секретных ключей шифрования.
О КРИПТОСИСТЕМАХ, ИСПОЛЬЗУЮЩИХ СЕКРЕТНЫЕ КЛЮЧИ ШИФРОВАНИЯ
Одним из наиболее ранних методов шифрования является метод простой замены символов исходного текста конфиденциальных сообщений другими символами, согласно некоторой подстановке, выполняющей функции секретного ключа. В простейшем случае такая подстановка сводится к сдвигу всех букв алфавита влево или вправо на некоторую постоянную величину. Следующий пример иллюстрирует работу алгоритма постоянного сдвига применительно к русским текстам при допущении, что в передаваемых сообщениях отсутствуют заглавные буквы и знаки препинания, а буква ё отождествлена с буквой е. Иными словами, предполагается, что в сообщениях, подлежащих шифрованию, могут встречаться 33 различных символа, а именно: 32 буквы русского языка и символ пробела. Приняв, что сдвиг букв осуществляется вправо, а постоянная сдвига равна восьми буквам, получим следующую подстановку:
а б в г Д е ж 3 и й к л M H о п P с
Щ ъ ы ь э ю я - а б в г Д е ж 3 и й
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
T У Ф X Ц ч ш щ ъ ы ь э ю я -
к л M H о п P с T У ф X ц ч ш
18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
Обратим внимание, что символы, вышедшие в результате сдвига за
71
ГЛАВА 5 рамки алфавита (в приведенной выше подстановке эти символы подчеркнуты), занимают освободившиеся 8 позиций в начальной части алфавита. Естественно, что число таких символов равно постоянной сдвига (в нашем случае оно равно восьми). Если буквы алфавита пронумеровать в порядке возрастания занимаемых ими позиций в алфавите ('а' = 0, 'б' = 1, 'в' = 2, ..., 'я' = 31, = 32), то очередная буква исходного текста, которая в алфавите занимает і-ю позицию, будет заменена буквой, занимающей j-ю позицию алфавита, где
j = (і - к) mod(A0, (4.1)
к - постоянная сдвига, равная в нашем примере восьми, a N - число различных символов, равное в нашем примере тридцати трем. Например, в результате такого шифрования исходный текст "встреча у букиниста" примет форму шифрограммы "ы йкиюпщшлшълвае а й к щ". Чтобы расшифровать такую шифрограмму, необходимо очередную букву шифрограммы, занимающую і-ю позицию алфавита, заменить буквой, занимающей в алфавите j-ю позицию, где
j = (і + к) mod(A0. (4.2)
Поступая таким образом, из полученной только что шифрограммы получим исходный текст "встреча у букиниста".
В общем случае в качестве секретного ключа шифрования могут быть использованы произвольные подстановки, определенные на множестве из N символов. Примером может служить, например, подстановка
абвгде жз ий клмно пр й-абэ юя ъыь туфхц чш
X =
стуфхцчшщъыь э ю я -свгдежзи щклм нопр
Для расшифрования текстов, зашифрованных согласно некоторой подстановке X, используется обратная ей подстановка K = X-1, т.е. такая, чтобы имело место XY= E , где E - единичный элемент, представляющий тождественную подстановку:
абвгде жз ий клмнопр
абвгде жз ий клмнопр
E =
стуфхцчш щъы ь э ю я -стуфхцчш щъы ьэюя-
Подстановочные алгоритмы шифрования в классическом варианте их использования оказались легко взламываемыми. Основным "виновником" этого является присущая естественным языкам избыточность, в
72 данном случае выражающаяся в том, что различные буквы алфавита имеют различную вероятность встречаемости в текстах естественных языков. Путем компьютерной обработки достаточно представительных объемов текстов на английском, французском, венгерском, армянском, арабском, русском, украинском и др. языках нами получены таблицы вероятностей встречаемости различных букв алфавитов этих языков в соответствующих текстах. Некоторые из этих таблиц приведены, например, в [1, 2]. Применительно к русским текстам, например, на основе результатов статистической обработки свыше 0,5 млн. символов можно утверждать, что если какая-то буква имеет наименьшую встречаемость в шифрограмме, то скорее всего эта буква - результат преобразования какой-либо одной из букв 'ъ', 'ф', 'э' или 'щ'. И, наоборот, если какая-то буква имеет наивысшую встречаемость в шифрограммах, то скорее всего эта буква - результат преобразования какой-либо одной из букв 'о', 'е\ 'и' или 'п'. Руководствуясь аналогичными соображениями, методом проб и ошибок удается сравнительно легко взламывать подстановочные алгоритмы. Если же учесть, что для анализа могут быть использованы огромные возможности современных компьютеров, то, по крайней мере, в наши дни криптостойкость этих алгоритмов следует признать чрезвычайно низкой.
