Криптографические системы

1)
monoalphabetic; В
системах класса monoalphabetic символ исходного текста заменяется другим
символом таким образом, что между ними существует однозначное соответствие. То
есть каждый символ исходного текста однозначно заменяется его подстановкой.
Криптографическим ключем такой системы является таблица соответствия исходного
алфавита алфавиту подстановки. Например, для английского алфавита существует 26!
= 4*1026 различных криптографических систем первого класса. Наиболее простые
системы данного класса предполагают аналитическое описание подстановок. Так,
простейший шифратор, основанный на принципе подстановки, сдвигает каждую букву
английского алфавита на k позиций, где k является ключом шифра. В так называемом
алгоритме Цезаря i-я буква алфавита заменяется (i+k)-й буквой по модулю 26. Юлий
Цезарь использовал подобную систему для k=3. Аналитически криптосистема Цезаря
описывается выражением Например, в
соответствии с приведенным выражением буква A исходного английского алфавита,
имеющая номер i=0, заменяется буквой D, имеющей номер (i+k) mod 26 = (0+3) mod
26 = 3, а буква z (i=25) заменяется буквой C, имеющей номер (i+k) mod 26 =
(25+3) mod 26 = 2. Следующий пример иллюстрирует алгоритм шифрования Цезаря:
Алгоритм дешифрования имеет вид Существуют более сложные методы подстановки.
Шифраторы, основанные на умножении номера каждого символа исходного текста на
значение ключа k, описываются следующим отношением: где i - номер символа исходного текста, n - количество символов в
исходном алфавите (n=26 для английского алфавита и n=256 для ASCII-кодов), k -
ключ, n и k должны быть взаимно простыми.
Любой шифратор класса monoalphabetic может быть представлен в виде
полиномиального преобразования порядка t: Алгоритм Цезаря является полиномиальным
преобразованием нулевого порядка. В криптографических системах класса
homophonic имеется несколько вариантов замены исходного символа. Например, буква
A может быть заменена цифрами 24, 35, 37, а буква B - цифрами 41, 17, 76. Тогда
слово ABBA может быть зашифровано как (37, 17, 76, 24), или (35, 41, 76, 37) и
т. д. Подобные системы характеризуются значительно большей криптографической
стойкостью, чем системы класса homophonic. Криптографические системы класса
polyalphabetic основаны на использовании нескольких различных ключей .
Большинство шифраторов подобного типа являются периодическими с периодом P.
Исходный текст вида Ek(X)= Ek1(x1) Ek2(x2) ... Ekp(xp)
Ek1(xp+1) ... Ekp(x2p) (1.6) Один из таких алгоритмов был предложен в XVI веке французом
Вигеном (Vigenere). где ki (1 <= i <= p)
представляет собой число сдвигов в исходном алфавите. где i -номер
символа исходного текста, Kj - ключ, j Пусть ключем является слово BAD. Тогда слово CRYPTOGRAPHY будет
зашифровано следующим образом: Криптосистемы третьего класса, основанные на
полиалфавитной подстановке, широко использовались и используются на практике. На
их основе разработано целое семейство роторных шифраторов, которые широко
применялись во время второй мировой войны и в послевоенное время. Среди них
можно выделить машину Хагелина M-209 (США), немецкую шифровальную машина
"Энигма", японский "Пурпурный код". Криптографические системы класса polygram
характеризуются подстановкой не одного, а нескольких символов в исходном тексте.
В общем случае n символов исходного текста заменяются n символами
шифротекста. Наиболее простым и эффективным методом взлома всех шифров,
основанных на подстановке, является метод статистического анализа. В любом языке
существют определенные вероятности появления того или иного символа в тексте.
Например, доля различных символов в стандартном английском тексте: C
0.0306 J 0.0016 Q 0.0011 W 0.0192 G
0.0196 N 0.0709 Если вычислить процент различных символов в шифротексте и
сравнить с приведенной таблицей, то можно легко получить таблицу
подстановок. Синхронные потоковые шифраторы
формируют ключ в виде потока (последовательности) символов
K=k , который несложным образом комбинируется с
последовательностью символов исходного текста M=m .
Алгоритм формирования К должен быть детерминированным и воспроизводимым, а сама
последовательность - случайной или псевдослучайной. -
начальное состояние генераторовключа. Оба генератора должны иметь одинаковое
начальное состояние и функционировать синхронно. C При дешифрации выполняется
обратное преобразование D: i i Генераторы M-последовательностей. При выборе генератора
ключа (ГК) необходимо учитывать следующие факторы: аппаратные затраты на
реализацию ГК, временные затраты на генерацию ключа. Широкое распространение
получили генераторы на основе сдвигового регистра с линейными обратными связями.
Они описываются следующим отношением: ak ai-k, k=0,1,2,... , (2.1) {0,1} -
биты формируемой последовательности; ai {0,1} -
постоянные коэффициенты; - операция
суммирования по модулю 2. Генератор, описываемый отношением (2.1), показан на
рис. 2.1. Свойства генерируемой последовательности определяются постоянными
коэффициентами ai. Их можно исследовать, анализируя характеристический
полином Å При соответствующем выборе коэффициентов генерируемая последовательность
{ ai } будет иметь максимально возможный период, равный 2m-1, где m -
разрядность сдвигового регистра и одновременно старшая степень порождающего
полинома. Последовательность максимально возможного периода называется M-
последовательностью. Основная задача синтеза генератора рассматриваемого типа -
нахождение характеристического полинома, формирующего М-
последовательность. Полиномы, формирующие последовательность максимального
периода, называются примитивными. С ростом m их количество становится очень
большим. Среди множества примитивных полиномов степени m можно найти полиномы с
наименьшим числом единичных коэффициентов a . Генераторы, построенные
на их основе, имеют наиболее простую техническую реализацию. В табл. 2.1
приведен перечень полиномов с минимальным количеством ненулевых коэффициентов
для значений m <=16. Для формирования M-последовательности наряду с
примитивным полиномом g(x) может использоваться и обратный ему полином g ). Полученная в этом случае
последовательность максимальной длины будет инверсной по отношению к
последовательности, формируемой g(x). Например, для полинома g(x)=1 обратным полиномом будет g x Главное преимущество описываемого метода формирования псевдослучайных
последовательностей - простота его реализации. Генератор M-последовательности
содержит лишь m-разрядный регистр сдвига и набор сумматоров по модулю два в цепи
обратной связи. Регистр сдвига выполняет функции хранения m бит M-
последовательности и сдвига m-разрядного кода на один разряд вправо. Сумматоры
по модулю два вычисляют очередное значение младшего разряда сдвигового
регистра. 2 (k) - состояние i-го разряда,
i=1,m, Последовательное применение соотношений (1) или (2) для s = 0 позволяет
формировать соответственно одно- или многоразрядные псевдослучайные
последовательности, которые характеризуется рядом статических свойств. 1. Период
последовательности, описываемой выражением (1), определяется старшей степенью
порождающего полинома g(x) и равен L= 2 2. Для заданного
полинома g(x) существует L различных M-последовательностей, отличающихся фазовым
сдвигом. Так, полиному g(x)=1 соответствует 15 M-
последовательностей. , k=0,1,..., L-1, M-последовательности соответственно равно
2 m-
1 и при увеличении m
достигает значений, сколь угодно близких к 1/2. {1,2,...,m-1}, одинаковых символов ( нулейили единиц ) в M-
последовательности максимально близки к соответствующим вероятностям для
случайной последовательности. s<L )
существует такое r s ( 1 -
s}={a Использование линейных сдвиговых регистров для создания
криптосистем предполагает их уязвимость, если взломщик обладает парой: исходный
текст - шифротекст длиной не менее 2m бит. Действительно, имея исходный текст
M=(m 2m 1 c ). Тогда задача взлома криптосистемы при известном
начальном состоянии сводится к решению системы из m линейных уравнений с m
неизвестными, где неизвестными являются коэффициенты порождающего полинома. 1 Å Å 3 m+2 3 Å m+3 m Å 2m Первые криптографические
системы с открытым ключем появились в конце 1970-х годов. От классических
алгоритмов они отличаются тем, что для шифрования данных используется один ключ
( ). Данные,
зашифрованные открытым ключем, можно расшифровать секретным
ключем. Следовательно, открытый ключ может распространяться через обычные
коммуникационные сети и другие открытые каналы. Таким образом, устраняется
главный недостаток стандартных криптографических алгоритмов: необходимость
использовать специальные каналы связи для распределения ключей. Разумеется,
секретный ключ не может быть вычислен из открытого ключа. В настоящее время
лучшим криптографическим алгоритмом с открытым ключем считается RSA (по имени
создателей: Rivest, Shamir, Adelman). Перед изложением метода RSA определим
некоторые термины. Взаимно простыми Под результатом операции Наиболее важной частью алгоритма RSA, как и
других алгоритмов с открытым ключем, является процесс создания пары
открытый/секретный ключи. В RSA он состоит из следующих шагов. 2. Вычисляется r=p * 4.
Выбираются открытый (Ко) и секретный (Кс) ключи, которые являются взаимно
простыми с Кс) mod 1) разбить исходный
текст на блоки, каждый из которых может быть представлен в виде числа M(i)=0, 1,
..., n-1; где последовательность чисел C(i) представляет
шифротекст. M(i)=(C(i)Кс) mod n.
Приведем простой пример использования метода RSA для шифрования сообщения "CAB".
Для простоты будем использовать малые числа (на практике используются намного
большие числа). 4. Выберем секретный ключ
Кс, который является взаимно простым с вычислим
открытый ключ Ко. Для этого можно использовать расширение алгоритма
Евклида: i +v i+1 Kо=vi-1; В
соответствии с алгоритмом получаем Ко=7. 6. Представим шифруемое сообщение
как последовательность целых чисел в диапазоне 2...28. Пусть букве А
соответствует число 2, букве В - число 3, а букве С - число 4. Тогда сообщение
"CAB" можно представить в виде последовательности чисел {5, 3, 4}. Зашифруем
сообщение, используя открытый ключ Ко=7: C3 = (47) mod 33 = 16384 mod 33 =
16. M1 = (143) mod 33 = 2744 mod 33 = 5, Таким образом, в
результате дешифрования сообщения получено исходное сообщение {5, 3, 4}
("CAB"). Криптостойкость алгоритма RSA основывается на предположении, что
исключительно трудно определить секретный ключ по открытому, поскольку для этого
необходимо решить задачу о существовании делителей целого числа. Данная задача
является NP-полной, то есть не имеет эффективного (полиномиального) решения.
Вопрос существования эффективных алгоритмов решения NP - полных задач является
до настоящего времени открытым. Традиционные же методы для чисел, состоящих из
200 цифр (именно такие числа рекомендуется использовать), требуют выполнения
огромного числа операций (около 1023). В последнее время все большее распространение получают программы,
предназначенные для защиты электронной информации. Они предоставляют
пользователям возможность зашифровывать файлы (PGP), санкционировать доступ к
накопителям (adm.sys), создавать секретные логические области на дисках (Norton
Diskreet). Средства защиты данных все чаще встраивают в обычное ПО (например,
СУБД). Наилучшую защиту обеспечивают методы, основанные на шифровании
информации. Они преобразуют данные в понятной форме (открытый текст) в
непонятную форму (шифротекст). При этом становится невозможным извлечь из них
смысл или изменить его. Для получения исходного текста из шифротекста
выполняется обратный процесс - дешифрование. Метод преобразования информации
называется криптографическим алгоритмом. Существует немало криптографических
алгоритмов, обеспечивающих достаточный уровень защиты информации (DES, RSA и др.
). Как правило, их программная реализация несложна, и они могут послужить
основой хорошей системы защиты данных. Однако выбор и реализация алгоритма
шифрования - не единственная и не самая важная проблема при создании подобных
систем. Необходимо разработать и реализовать еще как минимум два компонента: В соответствии с
современными взглядами криптографический алгоритм должен удовлетворять следующим
требованиям: 1) обладать известной криптостойкостью, выраженной в числе
операций или количестве времени, необходимых для его взлома; Последнее требование означает, что секретным должен
являться не алгоритм шифрования данных, а ключ, с помощью которого данные были
зашифрованы. То есть знание алгоритма без знания ключа не дает возможности
восстановить исходный текст из шифротекста. Соблюдение данного требования
означает, что самой важной частью системы защиты данных является подсистема
управления ключами. Управление ключами включает в себя: генерирование,
хранение, распределение ключей. Способ решения каждой из этих проблем сильно
влияет на дизайн всей системы и ее эффективность. Сложность генерирования ключей
заключается в том, что хороший криптографический ключ должен быть случайным
числом. Встроенные генераторы псевдослучайных чисел, имеющиеся в большинстве
систем программирования, не обеспечивают достаточного уровня случайности. При
использовании их для генерирования ключей последние могут быть легко предугаданы
или даже вычислены, что недопустимо. Проблема хранения подразумевает обеспечение
секретности сгенерированных ключей. Большинство систем позволяют хранить ключи
на диске вместе с информацией, защищая их паролем. Но данный метод нельзя
признать приемлемым, потому что создание надежного доступа по паролю для PC
проблематично. Проблема распределения ключей особенно остра в сетевых
приложениях. Чтобы обмениваться зашифрованной информацией, удаленные
пользователи должны иметь возможность обмениваться ключами. Очевидно, что в
момент передачи ключей по обычным каналам связи они могут быть перехвачены.
Решение этой проблемы требует применения специальных алгоритмов. Интерфейс с
пользователем должен обеспечивать простое и понятное выполнение всех функций
системы, способствовать быстрому освоению работы с программой. Предпочтительным
является интуитивно понятный оконный интерфейс с развитой системой
контекстуально зависимой помощи. Программа Pretty Good Privacy (PGP) фирмы
Phil's Pretty Good Software использует шифрование с открытым ключом для защиты
файлов данных и электронной почты. Программа PGP обладает многими полезными
качествами, работает быстро, позволяет осуществлять сложные манипуляции с
ключами, реализует электронные подписи, позволяет сжимать данные и хорошо
эргономически спроектирована. подписание текстового файла секретным
ключом; Основные функции работы с
ключами: ведение каталогов открытых и секретных
ключей; Кроме того, PGP выполняет множество
дополнительных функций, которые расширяют ее возможности и повышают удобство
работы с программой. Основной особенностью системы является реализация
криптографического алгоритма с открытым ключом RSA. Применение RSA обеспечивает
секретность передачи данных через сети коммуникации, так как данные шифруются
открытым ключом, а расшифровываются секретным. Открытые ключи могут свободно
распространяться по любым каналам, потому что с их помощью невозможно
декодировать сообщение. Таким образом, PGP эффективно решает важную проблему
распределения криптографических ключей. Алгоритм шифрования с открытым
ключом значительно медленнее, чем стандартное шифрование с одним ключом. Поэтому
PGP шифрует сообщения с помощью высококачественного быстрого стандартного
алгоритма шифрования с одним ключом, используя временный произвольный ключ.
Открытый ключ получателя используется только для шифровки этого временного
стандартного ключа, который посылается вместе с зашифрованным текстом
получателю. Получатель использует свой собственный секретный ключ, чтобы
восстановить временный ключ, и затем применяет его для выполнения быстрого
стандартного алгоритма декодирования с одним ключом, чтобы декодировать все
зашифрованное сообщение. Данный подход позволяет совместить преимущества
алгоритмов с открытым ключом с высокой надежностью и быстродействием стандартных
алгоритмов. pgp.c - головной модуль; basslib2.c - санкционирование
доступа по паролю; random.c - подпрограммы генерирования случайных
чисел; lfsr.c - подпрограмма
реализации линейного сдвигового регистра (LFSR); Головной модуль pgp.c обеспечивает интерфейс системы
с пользователем и взаимодействие ее компонентов. Входящая в него функция main()
производит разбор командной строки, через которую пользователь указывает
команду. В соответствии с командой main() производит последовательный вызов
необходимых подпрограмм, обеспечивая их согласованную работу. Модуль
basslib.c реализует алгоритм BassOmatic. Это стандартный блоковый шифратор
размером блока 256 байт. Он использут ключи размером 512, 1024 и 2048 бит (в
зависимости от необходимого уровня криптостойкости). Он может использовать
шифрование в режиме обратной связи. Модуль keygen.c генерирует пару
открытый/секретный ключи алгоритма RSA. Это непростая задача, требующая
реализации многих численных алгоритмов. В kegen.c реализованы алгоритмы проверки
простых чисел, быстрого просеивания простых чисел, проверки взаимной простоты
двух чисел, алгоритм Евклида. Все эти алгоритмы оперируют со 100-битными
числами. Модуль random.c реализует подпрограмму генерирования случайных
чисел, используемых для создания ключей алгоритмов RSA и BassOmatic. Случайные
значения вычисляются как промежутки времени между нажатием пользователем на
клавиатуру. Каждый полученный байт помещается в специальный буфер и становится
доступным для функций модулей keygen и basslib. Модуль rsalib.c
реализует математические функции (в частности, возведение в степень) над
операндами произвольной длины. Эти функции необходимы для
шифрования/дешифрования данных алгоритмом RSA. Схема 4.1. Генерирование пары открытый/секретный ключи для
алгоритма RSA. Схема
4.2. Шифрование файла стандартным криптографическим алгоритмом. Схема
4.3. Шифрование файла открытым ключем получателя.