Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
102
Содержание
ТЕОРЕТИЧЕСКАЯ ЧАСТЬ ………………………………………… 4
ЛАБОРАТОРНАЯ РАБОТА №1.
ПРИМЕНЕНИЕ РАЗЛИЧНЫХ МЕТОДОВ КРИПТОГРАФИЧЕСКОЙ ЗАЩИТЫ ТЕКСТОВОЙ ИНФОРМАЦИИ ………………………… 27
ЛАБОРАТОРНАЯ РАБОТА №2
ИССЛЕДОВАНИЕ РАЗЛИЧНЫХ МЕТОДОВ ЗАЩИТЫ ТЕКСТОВОЙ ИНФОРМАЦИИ И ИХ СТОЙКОСТИ
НА ОСНОВЕ ПОДБОРА КЛЮЧЕЙ …………………………………… 47
ЛАБОРАТОРНАЯ РАБОТА №3
ИЗУЧЕНИЕ ПЕРСОНАЛЬНЫХ СРЕДСТВ ЗАЩИТЫ ИНФОРМАЦИИ НА ПРИМЕРЕ ПРОГРАММНОГО СРЕДСТВА КРИПТОГРАФИЧЕСКОЙ ЗАЩИТЫ PGP 5.5 ……………………….. 95
ЛАБОРАТОРНАЯ РАБОТА №4.
ГЕНЕРАЦИЯ ПРОСТЫХ ЧИСЕЛ, ИСПОЛЬЗУЕМЫХ В
КРИПТОАЛГОРИТМАХ С ОТКРЫТЫМ КЛЮЧОМ …………… 101
ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
1. Введение
Защита информации методами криптографического преобразования заключается в изменении её составных частей (слов, букв, слогов, цифр) с помощью специальных алгоритмов либо аппаратных решений и кодов ключей, то есть в приведении её к неявному виду.
Для ознакомления с шифрованной информацией применяется обратный процесс: декодирование (дешифрование). Использование криптографии является одним из распространённых методов, значительно повышающих безопасность передачи данных в сетях ЭВМ, данных, хранящихся в удалённых устройствах памяти и при обмене информацией между удалёнными объектами.
Для преобразования (шифрования), обычно используется некоторый алгоритм или устройство, реализующее заданный алгоритм, которые могут быть известны широкому кругу лиц. Управление процессом шифрования осуществляется с помощью периодически меняющегося кода ключа, обеспечивающего каждый раз оригинальное представление информации при использовании одного и того же алгоритма или устройства. Знание ключа позволяет просто и надёжно расшифровать текст. Однако без знания ключа эта процедура может быть практически невыполнима даже при известном алгоритме шифрования.
Даже простое преобразование информации является весьма эффективным средством, дающим возможность скрыть её смысл от большинства неквалифицированных нарушителей.
Коды и шифры использовались в течении многих веков задолго до появления ЭВМ. Между кодированием и шифрованием не существует отчётливой разницы. Заметим только, что в последнее время на практике слово "кодирование" применяют в целях цифрового представления информации при её обработке на технических средствах, а "шифрование" - при преобразовании информации в целях защиты от НСД. В настоящее время некоторые методы шифрования хорошо проработаны и являются классическими.
Множество современных методов защитных преобразований можно классифицировать на четыре большие группы: перестановки, замены (подстановки), аддитивные и комбинированные методы.
Методы перестановки и подстановки обычно характеризуются короткой длиной ключа, а надёжность их защиты определяется сложностью алгоритмов преобразования.
Для аддитивных методов характерны простые алгоритмы преобразования, а их криптостойкость основана на увеличении длины ключа.
Все перечисленные методы относятся к симметричному шифрованию: один и тот же ключ используется для шифрования и дешифрования. Сейчас также распространены методы несимметричного шифрования: один ключ для шифрования (открытый), второй - для дешифрования (закрытый).
1. Методы шифрования
1.1. Одноалфавитный метод
Данный метод, пожалуй, самый древний из всех известных методов. В его основе лежит простой способ шифрования: отправитель и получатель закодированного документа заранее договариваются об определённом смещении букв относительно их обычного местоположения в алфавите. Например, если смещение равно 1, то “А” соответствует букве “Б”, “Б” – “В”, и так далее, а когда алфавит подходит к концу, то начинают брать буквы из начала списка. И выходит, например, следующее: из слова “КОДИРОВАНИЕ” получается “ЛПЕЙСПГБОЙЖ”.
Частным случаем данного метода является так называемый шифр Цезаря. Очевидно, что произвольный шифр из класса одноалфавитных методов не является шифром Цезаря (если мощность алфавита текста равна n, то число шифров Цезаря равно n, а число всех одноалфавитных шифров равно n!).Однако и для таких методов легко предложить способы дешифрования, основанные на статистических свойствах шифрованных текстов поскольку открытый и закрытый тексты имеют одинаковые статистические характеристики.
В первой лабораторной работе рассматриваются два варианта одноалфавитного метода с фиксированным смещением и с произвольным (задаваемым) смещением.
Методы замены (подстановки). Методы шифрования заменой заключаются в том, что символы исходного текста (блока), записанные в одном алфавите, заменяются символами другого алфавита в соответствии с принятым ключом преобразования.
Одним из простейших методов считается прямая замена исходных символов их эквивалентом из вектора замен. Для очередного символа открытого текста отыскивается его местоположение в исходном алфавите. Эквивалент из вектора замены выбирается как отстоящий на полученное смещение от начала алфавита. При дешифровании поиск выполняется в векторе замен, а эквивалент выбирается из исходного алфавита. Полученный таким методом текст имеет сравнительно низкий уровень защиты, так как открытый и закрытый тексты имеют одинаковые статистические характеристики.
Более стойкой в отношении раскрытия считается схема шифрования, основанная на таблице Вижинера. Таблица представляет собой квадратную матрицу с числом элементов К, где К – количество символов в алфавите. В первой строке матрицы записываются буквы в порядке их очередности в алфавите, во второй – та же последовательность букв, но со сдвигом влево на одну позицию, в третьей – со сдвигом на две позиции и т.д. Освободившиеся места справа заполняются вытесненными влево символами, записываемыми в естественной последовательности.
Для шифрования текста устанавливается ключ, представляющий собой некоторое слово или набор символов. Далее из полной матрицы выбирается подматрица шифрования, включающая, например, первую строку матрицы и строки, начальные буквы которых являются последовательностью ключа.
Процесс шифрования включает следующую последовательность действий:
Раскрыть текст, полученный по данному алгоритму, только на основе статистических характеристик языка невозможно, так как одни и те же символы открытого текста могут быть заменены различными символами закрытого текста. С другой стороны различные буквы открытого текста могут быть заменены одинаковыми знаками шифрованного текста.
Для дешифрования необходимо знать ключ, который может быть введен пользователем со своего терминала или храниться в памяти ЭВМ в зашифрованном виде. Для шифрования ключа можно использовать другую систему шифрования.
Расшифровка текста выполняется в следующей последовательности:
Один из недостатков метода шифрования по таблице Вижинера – ненадежность алгоритма при небольшой длине ключа и сложность формирования длинных ключей. Так как в ключе не допускается повторение букв (в противном случае шифрование будет неоднозначным), а сам ключ должен легко запоминаться, последовательность букв, не имеющих определенного смысла, запомнить трудно.
1.2. Шифрование методом перестановки символов
Суть методов перестановки состоит в том, что входной поток исходного текста делится на блоки, в каждом из которых выполняется перестановка символов по определённым правилам, при этом используются только символы исходного (незашифрованного) текста.
Перестановки в классической криптографии обычно получаются в результате записи исходного текста и чтения шифрованного текста по разным путям геометрической фигуры.
Простейшим примером перестановки являются запись исходного текста по строкам некоторой матрицы и чтение его по столбцам этой матрицы.
Последовательность заполнения строк и чтения столбцов может быть любой и задаётся ключом. Таким образом, для матрицы размером 8*8 (длина блока 64 символа) возможно 1,6*109 ключей, что позволяет на современных ЭВМ путём перебора расшифровать заданный текст. Однако для матрицы размером 16*16 (длина блока 256 символов) имеется 1,4*1026 ключей, и перебор их с помощью современных средств вычисления весьма затруднителен.
Примером применения метода перестановки может быть также восьмиэлементная таблица, обладающая совокупностью маршрутов, носящих название маршрутов Гамильтона. Последовательность заполнения таблицы каждый раз соответствует нумерации её элементов. Если длина шифруемого текста не кратна числу элементов, то при последнем заполнении в свободные элементы заносится произвольный символ. Выборка из таблицы для каждого заполнения может выполняться по своему маршруту, при этом маршруты могут использоваться как последовательно, так и в порядке, задаваемом ключом.
Для методов перестановки характерны простота алгоритма, возможность программной реализации и низкий уровень защиты. При большой длине исходного текста в его зашифрованном варианте проявляются статистические закономерности ключа, что и позволяет его быстро раскрыть. Другой недостаток этих методов - лёгкое раскрытие, если удаётся направить в систему для шифрования несколько специально подобранных сообщений. Так, если длина блока в исходном тексте равна К символам, то для раскрытия ключа достаточно пропустить через шифровальную систему К-1 блоков исходного текста, в которых все символы, кроме одного, одинаковы.
Существуют и другие способы перестановки, которые можно реализовать программным и аппаратным путём. Например, реализованный аппаратным путём блок перестановки, который для преобразования информации использует электрические цепи, по которым она передаётся параллельным способом. Преобразование текста заключается в "перепутывании" порядка разрядов в цифровой кодограмме путём изменения электрического монтажа схемы в блоке. Для дешифрации на приёмном пункте устанавливается другой блок, восстанавливающий порядок цепей.
1.3.Шифрование инверсными символами (по дополнению до 255)
Данный метод шифрования, является частным случаем одноалфавитной замены в алфавите мощности 256 (двоично-восьмеричные вектора). Суть метода заключается в замене символа ASCII с номером i на символ с номером 255-i. Аналогично проводится и операция расшифрования.
1.4.Многоалфавитные методы
Многоалфавитное шифрование (многоалфавитная замена) заключается в том, что для последовательных символов шифруемого текста используются одноалфавитные методы с различными ключами.
Например, первый символ заменяется по методу Цезаря со смещением 18, второй – со смещением 12 и так далее до конца заданного ключа. Затем процедура продолжается периодически. Более общей является ситуация, когда используется не шифр Цезаря, а последовательность произвольных подстановок, соответствующих одноалфавитным методам.
Более наглядным примером подобного шифрования является метод гаммирования.
Данный способ преобразования заключается в том, что символы закрываемого текста последовательно складываются с символами некоторой специальной последовательности именуемой гаммой. Такое преобразование иногда называют наложением гаммы на открытый текст.
Собственно процедура наложения может осуществляться одним из двух способов:
1. Символы закрываемого текста и гаммы заменяются цифровыми эквивалентами, а затем складываются по модулю К, где К – кол-во символов алфавита, т.е.
Тш = (То + Тг) mod K, (1)
где Тш — закрываемый;
То — открытый текст;
Тг — гамма.
2. Символы текста и гаммы представляются в двоичных кодах, а затем каждая пара двоичных разрядов складывается по модулю 2. Сложение по модулю 2 может быть расширено до преобразования по правилу логической эквивалентности или логической неэквивалентности.
Нетрудно видеть, что такое расширение равносильно введению ещё одного ключа, именно - правил замены.
Стойкость закрытия способом гаммирования определяется, главным образом, качеством гаммы, которое определяется двумя характеристиками: длиною периода и случайностью распределения по периоду.
Длиною периода гаммы называется минимальное количество символов, после которого последовательность начинает повторяться. Случайность распределения символов по периоду означает отсутствие закономерностей между появлением различных символов в пределах периода.
По длине периода различаются гаммы с конечным и бесконечным периодом. Конечные гаммы, в свою очередь, могут быть разделены на короткие и длинные, хотя это деление является, в известной мере, условным.
При хорошем качестве гаммы по характеристике случайности стойкость закрытия определяется исключительно длиною её периода. При этом, если длина периода гаммы превышает длину закрываемого текста, то такое преобразование теоретически является абсолютно стойким, т.е. его нельзя вскрыть на основе статистической обработки закрытого текста. Однако теоретическая невозможность вскрытия не означает, что вскрытие вообще невозможно; при наличии некоторой дополнительной информации открытый текст может быть полностью или частично разгадан даже при бесконечной гамме.
В качестве гаммы может быть использована любая последовательность случайных символов: например, последовательность цифр основания натуральных логарифмов числа е, числа Р и т.п. .
Если же закрытие осуществляется на ЭВМ, то такие последовательности можно генерировать с помощью датчика псевдослучайных чисел (ПСЧ). К настоящему времени известно несколько таких датчиков, которые обеспечивают удовлетворительное качество гаммы.
Если, например, в качестве датчика (ПСЧ) принять последовательность
X(i+1)= aX(i) + C(mod m), (2)
где m = 2^k (k>=2 - целое), то наибольший период будет тогда, когда С - нечётное и а* mod 4 = 1.
Более сложным является датчик
X(i+1)=X(i)+X(i-L)(mod m), (3)
где m = 2 и b = 35 начальная последовательность X1, X2,..., X(L) генерируется по датчику (2).
Для начала работы задаётся X0, содержащее 6 цифр. С помощью этого числа определяется L как сумма числа 16 и числа, определяемого шестью битами X0. Определив L, по датчику (2) генерируется последовательность X1, X2,... XL, после чего по датчику (3) генерируется последовательность из N чисел гаммы, причём N определяется как сумма числа 2^k и числа, определяемого K младшими битами числа XL.
При этом, если требуется высокая надёжность закрытия, то используется значение K = 18, в других K = 12.
После того, как будет получено число X(L+n), процедура начинается сначала, но вместо числа Х0 используется число ХL.
Известны и более сложные датчики ПСЧ.
В лабораторной работе рассматриваются три варианта многоалфавитного метода – с фиксированным ключом, с ключом фиксированной длины и с ключом произвольной длины.
1.5. Общие сведения
Основные требования, которые предъявляются к методам защитного преобразования информации:
Перечисленные требования характерны в основном для традиционных средств защитных преобразований. С развитием устройств памяти, позволяющих с большей плотностью записывать и надёжно хранить длительное время большие объёмы информации, ограничение на размер ключа может быть значительно снижено. Появление и развитие электронных элементов позволили разработать недорогие устройства, обеспечивающие преобразование информации.
1.6. Вскрытие шифра.
Во второй лабораторной работе рассматривается способ вскрытия шифра, основанный на переборе всех вариантов ключа. Критерием правильности варианта служит наличие в тексте «вероятного слова».
Перебирается множество всех возможных ключей, шифрованный текст расшифровывается на каждом ключе. В получившемся «псевдооткрытом» тексте ищется вероятное слово. Если такого слова нет, текущий текст бракуется, осуществляется переход к следующему ключу. Если такое слово найдено, на экран выводится вариант ключа. Затем перебор ключей продолжается до тех пор, пока не исчерпается все множество вариантов. Возможно обнаружение нескольких ключей, при которых в «псевдооткрытых текстах» имеется вероятное слово.
После завершения перебора необходимо расшифровать текст на найденных ключах. «Псевдооткрытый текст» выводится на экран для визуального контроля. Если оператор признает текст открытым, то работа по вскрытию заканчивается. Иначе, данный вариант ключа бракуется и осуществляется переход к следующему ключу.
2. Гистограмма текста
Одним из главных методов криптоанализа является изучение статистических характеристик шифрованных текстов. Графическое отображение совокупности частот встречаемости символов в тексте называют гистограммой этого текста.
Предположим, что мы имеем дело с методом одноалфавитного шифрования. Зная частоту встречаемости букв в алфавите, можно предположить, какая буква была заменена на данную. Например, часто встречаемая буква “О” заменена на редко встречающуюся букву “Щ”. Для наглядности в лабораторной работе используются двойные гистограммы, отображающие частоту встречаемости символов в исходном и зашифрованном текстах.
При просмотре гистограмм имеется возможность их масштабирования для более точного определения частоты встречаемости того или иного символа текста.
Следует иметь в виду, что вид гистограммы для стандартного распределения зависит от вида исходного текста следующим образом: если исходный текст содержит символы кириллицы и латинского алфавита, то выводится статистическое распределение для кириллицы и латиницы, если только кириллицы (латиницы), то выводится статистическое распределение для кириллицы (латиницы).
Технология увеличения или уменьшения масштаба гистограмм будет подробно описана ниже.
3. Описание программы PGP и
электронной цифровой подписи
PGP 5.5 представляет собой программное средство криптографической защиты информации (СКЗИ), обеспечивающее защиту данных от несанкционированного доступа с помощью шифрования и несанкционированного изменения с помощью электронной цифровой подписи (ЭЦП) [1].
PGP 5.5 работает на прикладном уровне и позволяет защитить файлы и письма электронной почты.
Протокол работы цифровой подписи для большинства схем изображен на рис. 1.
Исходным документом для постановки цифровой подписи может быть текст или любой другой файл данных.
Математические формулы схемы цифровой подписи обычно требуют использования исходного текста фиксированной длины. Чтобы привести исходный документ к фиксированной длине, используется хеш-функция.
Секретный и открытый ключи генерируются в результате процедуры генерации ключей.
Цифровая подпись генерируется путем математических преобразований из хеш-функции и секретного ключа.
Исходный документ и цифровая подпись передаются по каналу связи вместе.
На приемной стороне по принятому документу снова вычисляется значение хеш-функции и выполняется процедура проверки соответствия между принятым документом и цифровой подписью.
Если процедура проверки цифровой подписи закончилась с положительным результатом, то документ был передан без искажений (с точностью до надежности схемы цифровой подписи и хеш-функции).
Если процедура проверки окончилась с отрицательным результатом, то переданный документ либо цифровая подпись были искажены при передаче.
Для выработки криптографических ключей используются криптосистемы с асимметричными ключами. Такие системы основываются на односторонней функции, для которой существует алгоритм быстрого вычисления; при этом определение обратной функции сложно (как правило, требует полного перебора).
В PGP 5.5 возможно использовать ключи RSA для ЭЦП и шифрования либо ключей Diffie-Hellman для шифрования, а также ключей DSS для ЭЦП. Криптосистема RSA поддерживается для совместимости с ранними версиями, рекомендуется применять более современные и надежные криптосистемы Diffie-Hellman и DSS.
Криптосистема RSA [2] основывается на односторонней функции перемножения двух простых чисел большой разрядности. Разложение многоразрядного числа на множители – трудновычислимая задача.
Ниже описана схема цифровой подписи RSA.
На начальном этапе подписывающий абонент выбирает большие простые числа p и q, вычисляет их произведение
N = pq.
Выбирает случайное число е так, чтобы
(e,Ф(N)) = 1, т.е. е и Ф(N) взаимно просты,
где
Ф(N) = (p-1)(q-1) –
функция Эйлера от N. Далее вычисляется такое d, что
de =1 (mod Ф(N)).
Число d является несекретным и передается проверяющей стороне.
В качестве подписи сообщения х используется число
M = [h(x)]^e (mod N).
Проверяющая сторона при проверке цифровой подписи проверяет условие
h(x) = M^d (mod N).
Нарушение этого условия означает, что подпись М не соответствует сообщению х, и, следовательно, сообщение (или подпись) было искажено. Если это условие выполнено, то сообщение считается подлинным.
Криптосистемы Diffie-Hellman и DSS [2] основываются на односторонней функции возведения в степень по модулю. Обратная задача дискретного логарифмирования решается только перебором.
Схема цифровой подписи DSS представляет собой одну из модификаций схемы цифровой подписи Эль-Гамаля [3].
Кроме защиты информации от несанкционированного искажения с помощью цифровой подписи, программное средство PGP 5.5 предусматривает возможность защиты данных при их передаче и хранении с помощью шифрования.
Для шифрования используются симметричные криптосистемы CAST, TripleDES или IDEA [3], так как симметричные алгоритмы работают намного быстрее. Чтобы избежать необходимости передавать симметричные ключи по закрытому каналу, генерируется случайный сеансовый ключ, который шифруется асимметричным алгоритмом в соответствии с протоколом, изображенным на рис 2.
Рис. 2
Ключ, необходимый для работы симметричного алгоритма, генерируется случайно на время сеанса связи и называется сеансовым. На этом ключе выполняется зашифрование исходного сообщения.
Сеансовый ключ зашифровывается по схеме с открытым ключом с помощью открытого ключа и передается по открытому каналу связи вместе с зашифрованным сообщением.
На приемной стороне вначале расшифровывается сеансовый ключ по схеме с открытым ключом с помощью закрытого ключа, а затем с помощью полученного в результате сеансового ключа расшифровывается посланное сообщение.
Описанный протокол позволяет зашифровывать и расшифровывать сообщения по симметричному алгоритму, имеющему значительно более высокое быстродействие, и при этом избежать необходимости распространять секретные ключи по закрытому каналу связи.
Защита с помощью цифровой подписи и с помощью шифрования может применяться одновременно.
PGP 5.5 предоставляет возможность задавать разрядность ключей при их создании от 768 до 4096 бит для криптосистем Diffie-Hellman и DSS и от 512 до 2048 бит для криптосистемы RSA. Объем вычислений, который необходимо провести для атаки на криптографическую систему, возрастает экспоненциально при увеличении разрядности ключа. При современных вычислительных мощностях разработчики PGP рекомендуют использовать 1024-битные ключи для алгоритмов Diffie-Hellman и DSS и 2048-битные ключи для алгоритма RSA. При использовании таких значений объем полного перебора, который необходимо выполнить для взлома схемы с открытым ключом, составляет 1024 варианта. Однако следует учитывать, что для разложения на простые числа существуют более эффективные алгоритмы, чем полный перебор.
Оценим, приблизительно, требуемое время полного перебора.
Пусть Pentium III 600 способен перебрать 600*106 вариантов в секунду (реально на много меньше, так как на перебор одного варианта уходит несколько тактов). Тогда для перебора 21024, что примерно составляет 10340, потребуется более чем 10331 с, что составит более 10323 лет.
Таким образом, атака на рассмотренную систему методом полного перебора практически нереализуема.
4. Использование простых чисел в алгоритме RSA
Для аутентификации (определения подлинности) сообщений (файлов) в сетях ЭВМ используются алгоритмы с открытым ключом.
Один из самых известных алгоритмов с открытым ключом – алгоритм RSA.
Пусть h(x) – хеш–функция сообщения х. В качестве подписи используется число
M = [h(x)]e (mod N),
где h(x) – хеш–функция сообщения x;
N = p*q, p, q – простые числа;
e – показатель степени, такой что
(e, f (N)) = 1,
где f(N) = (p–1)*(q–1) – функция Эйлера от модуля N.
Подписывающая сторона вычисляет такое d, что:
de = 1(mod f(N)).
Число d является не секретным и передаётся проверяющей стороне. Проверяющая сторона при проверке подписи проверяет условие:
h(x) = Md (mod N).
Отметим, что процедура симметрична относительно e и d. Здесь секретный ключ подписывающего: числа p, q, e; открытый ключ проверяющего подпись – пара чисел N, d.
Для того, чтобы описанная схема была достаточно стойкой от подделки, числа p и q должны быть случайными большими простыми числами и иметь в своей двоичной записи несколько сотен бит.
Проблема генерации многоразрядных случайных простых чисел представляет собой весьма важную задачу, поскольку от выбранного алгоритма генерации существенно зависят такие параметры криптосхемы, как время работы (на этапе настройки программы – создания образца подписи) и стойкость, т.е. устойчивость к подделке подписи.
Если пренебречь требованием случайности, предъявляемым к генерируемым простым числам (то есть выбирать их из какого – то фиксированного множества чисел), то нарушителю для вскрытия схемы достаточно перебрать это множество чисел и найти то, которое делит модуль N без остатка.
Если в результате генерации хотя бы одно из чисел p или q окажется не простым, то и вся система подписи окажется неработоспособной: может найтись такой реальный подлинный документ, проверка подписи которого не подтвердит его подлинность.
5. Методы проверки чисел на простоту
Рассмотрим методы проверки чисел на простоту.
Задача проверки простоты чисел имеет давнюю историю. Так, например, проверка простоты чисел Ферма
Fk = 22^k+1, k = 1, 2, …
связана с возможностью построения циркулем и линейкой правильных многоугольников. Для криптографических целей требуется проверять очень большие случайные числа. Простейшим методом проверки простоты натурального числа N является метод пробных делений: для d=2, 3, 4 … мы проверяем выполнение условия (d, N)>1. (Здесь (d, N) – наибольший общий делитель чисел d и N) . Число операций, требуемых для этого метода, имеет порядок корня из N.
Поэтому уже для чисел порядка 1030–1040 он неприменим.
По существу, этот метод не только проверяет простоту, но и находит нетривиальный делитель в случае составного N.
Отметим ещё алгоритмы Румели и Адлемана (давшего букву А в названии RSA), проверяющие простоту N за
O((log N)(c*log log log N))
шагов для некоторой константы c. Перечисленные выше тесты дают 100% гарантию простоты числа N, то есть, если какой – либо тест на выходе объявляет число N простым, то это можно считать строгим математическим доказательством простоты N. Однако эти тесты практически не используются ввиду значительного времени их работы.
В отличие от таких “детерминированных“ тестов существуют ещё “вероятностные“ тесты проверки простоты. Для исследуемого числа проверяется выполнение некоторых, связанных со случайными числами, условий. Если какое-либо из этих условий не выполнено, то N – составное число. Если же все условия выполнены, то с некоторой вероятностью можно утверждать, что N – простое число. Эта вероятность тем ближе к 1, чем большее количество случайных чисел мы проверим.
Обычно эти условия основаны на малой теореме Ферма, утверждающей, что для любого положительного числа b, не превосходящего некоторого простого числа p:
b(p–1) = 1(mod p).
Например, 26 = 64 = 63+1 = 1(mod 7). Если требуется определить, является ли целое число r простым, то можно выбрать любое положительное целое число b, меньшее r, и проверить, выполнено ли равенство
b(r–1) = 1(mod r).
Если равенство не выполнено, то на основании теоремы Ферма можно быть совершенно уверенным, что r – не простое число. Если же равенство выполнено, то можно лишь предполагать, что r – простое число и поэтому назвать его “псевдопростым по основанию b“. Вероятность P(x) того, что составное число x окажется псевдопростым по случайному основанию, убывает с ростом x.
К сожалению, существуют так называемые числа Кармайкла – такие составные числа, которые обладают свойством:
b(r–1) = 1(mod r) для всех b из интервала [1, r],
которые взаимно просты с r.
Примером числа Кармайкла является число 561 = 3*11*17.
Применение теста Ферма к таким числам с большой вероятностью даст положительный результат, то есть этот тест объявит такие числа простыми. До сих пор неизвестно, конечно или бесконечно множество чисел Кармайкла. Однако тест Ферма можно существенно усилить.
Дадим определение строго псевдопростого числа. Пусть N – нечётное число, N–1 = d*2s, d – нечётно. Число N называется строго псевдопростым в базе a, если ad= 1(modN) или
a(d*2^r) = - 1(mod N) при некотором r, 0<r<s.
Вероятностный тест на простоту, основанный на проверках на строгую псевдопростоту по случайным базам называют тестом Селфриджа. Аналогов чисел Кармайкла (т.е. чисел, строго псевдопростых по всем базам, не превышающим самого числа) в этом случае нет.
Поскольку тесты, основанные на теореме Ферма, требуют значительного времени для вычислений, на практике проверяемое число делят вначале на маленькие простые числа. Если проверяемое число разделилось на одно из них, то оно заведомо не простое, если же нет, то тогда применяют один из описанных выше вероятностных тестов.
Классический результат теории чисел – теорема Чебышева – показывает, что доля положительных целых чисел, меньших некоторого целого m и являющихся простыми, близка к 1/(ln m). Например, доля целых чисел, меньших 10100 и являющихся простыми, близка к 1/(ln10100) = 1/230. Поскольку 90% этих чисел лежат между 1099 и 10100, то доля простых чисел в этом диапазоне также составляет около 1/230.
Поэтому, если наугад выбрать число с 99–ю значащими десятичными цифрами, т.е. в диапазоне от 1099 до 10100, то оно окажется простым с вероятностью около 1/230.
Таким образом, если мы выберем случайно большое целое положительное нечётное число x и будем последовательно проверять на простоту числа x, x+1, x+2, … , то в среднем мы впервые встретим простое число на шаге с номером ln x.
ЛАБОРАТОРНАЯ РАБОТА №1.
ПРИМЕНЕНИЕ РАЗЛИЧНЫХ МЕТОДОВ КРИПТОГРАФИЧЕСКОЙ ЗАЩИТЫ ТЕКСТОВОЙ ИНФОРМАЦИИ
1. Введение
Данная лабораторная работа направлена на изучение студентами различных криптографических методов защиты информации от несанкционированного чтения. В лабораторной работе представлено семь простейших видов шифрования.
2. Работа с программой
Для запуска лабораторной работы необходимо вызвать на исполнение файл L_LUX.EXE. На экране дисплея появляется окно, с размещённым в его центре текстовым редактором, предназначенном для отображения шифрованных и расшифрованных текстов. В верхней строке окна расположено главное меню, позволяющее пользователю выполнить требуемое действие. Чуть ниже основного меню расположена панель инструментов, для управления быстрыми командными кнопками и другими “горячими” элементами управления. В самом низу окна, под текстовым редактором, находится строка состояния, в которой указывается “горячая” подсказка и выводится дополнительная информация. Клавиши панели инструментов, для удобства, снабжены всплывающими подсказками.
Для того чтобы попасть в основное меню, необходимо нажать клавишу F10. Передвижение по главному меню осуществляется клавишами перемещения курсора. Чтобы вызвать пункт меню, нужно нажать клавишу “ENTER”, вернуться в главное меню или вовсе выйти из него – “ESC”.
Для удобства в программе предусмотрена работа с мышью. В этом случае указатель подводится к нужному пункту главного меню или к нужной кнопке на панели инструментов и нажимается левая клавиша мыши, аналогичным образом выбираются нужные пункты подменю основных меню, для отказа достаточно нажать клавишу “ESC”.
Кроме основных функций главного меню (“Открыть файл”, “Шифрование”, “Дешифрование” и так далее) панель инструментов содержит клавиши преобразования текстов из формата DOS в формат WINDOWS и наоборот.
А теперь более подробно рассмотрим каждый из пунктов главного меню.
2.1. Редактор
Данный пункт основного меню содержит подпункты: создать документ, открыть файл, сохранить файл, выход из программы.
Предварительно, сразу после запуска программы, текстовый редактор – недоступен, также недоступными являются почти все пункты главного меню (кроме создания документа, открытия файла, выхода из программы, информации о программе) и большая часть клавиш панели управления (за исключением создания документа, открытия файла и выхода из программы).
Создать документ (Ctrl+N) – данный подпункт делает доступным для работы тестовый редактор (пользователь получает право создать свой текстовый файл, который впоследствии можно будет использовать при работе с программой), также появляется возможность использовать все недоступные до этого пункты основного меню и клавиши панели управления.
Открыть файл (Ctrl+L) – при выборе этого пункта появляется диалоговое окно, предоставляющее возможность выбора файла для загрузки. При этом содержимое файла будет отображено в окне редактора текстов.
Аналогично пункту “Создать документ” доступным для работы становится текстовый редактор с отображаемым текстом, а также появляется возможность использовать все недоступные до этого пункты основного меню и клавиши панели управления.
Сохранить файл (Ctrl+S) - при выборе этого пункта появляется диалоговое окно, позволяющее сохранить на диск содержимое редактора текстов.
Выход из программы (Ctrl+X) - при выборе этого пункта появляется диалоговое окно, позволяющее выйти из программы.
2.2. Гистограмма
Вывод на экран двух гистограмм, отображающих частоту встречаемости символов в тексте. Внимание! До выполнения шифрования и дешифрования вызывать гистограмму не имеет смысла, так как ещё не сформированы тексты, для которых будет просматриваться гистограмма.
Имеется возможность просмотра следующих сочетаний гистограмм:
В гистограммах с целью масштабирования используются левая и правая клавиши мыши.
Например, после шифрования текста большого объёма пользователь хочет посмотреть гистограммы исходного и шифрованного файла. Поскольку размеры текста достаточно большие, то на экран будут выведены две гистограммы с большим количеством столбиков в каждой, (столбик соответствует одному символу текста), однако трудно будет сказать, какой из этих столбцов соответствует тому или иному символу текста, и какова частота встречаемости данного символа.
Поэтому у пользователя есть возможность увеличить масштаб любой из двух гистограмм с целью более точного определения требуемого значения частоты встречаемости конкретного символа.
Для этого необходимо навести указатель мыши на левую границу того участка гистограммы, который требуется увеличить, затем нажать левую клавишу мыши, и не отпуская её растянуть прямоугольник так, чтобы его нижний правый угол совпал с правой границей увеличиваемого участка гистограммы. После этого следует отпустить левую клавишу мыши и на экране появится увеличенное изображение нужного участка.
Причём, нажав и не отпуская правую клавишу мыши можно двигать гистограмму в любом направлении с целью изучения всего полученного распределения в увеличенном масштабе.
Для того, чтобы от увеличенного масштаба вернуться к исходному виду, нужно навести указатель мыши на гистограмму, затем нажать левую клавишу мыши, и, не отпуская её снизу вверх растянуть небольшой по размерам прямоугольник, после этого следует отпустить левую клавишу мыши и на экране появится исходное изображение гистограммы.
2.3. Шифрование
Выполнение шифрования текстового файла одним из семи методов, рассматриваемых в лабораторной работе:
Выбор метода шифрования производится как мышкой, так и клавишами перемещения курсора и клавишей “ENTER”.
Затем появляется окно, в котором в зависимости от метода шифрования требуется указать те или иные параметры, и либо подтвердить процесс кодировки, либо отказаться от него.
После этого в окно редактора будет выдан зашифрованный текст.
2.4. Дешифрование
“Дешифрование” – выполнение расшифрования зашифрованного текста.
Примечание: Обычно термин ДЕШИФРОВАНИЕ применяют, когда известен ключ, а термин РАСШИФРОВАНИЕ – когда ключ не известен.
Аналогично предыдущему пункту выбирается метод расшифрования (должен соответствовать методу, которым был зашифрован файл).
Снова появляется окно, в котором в зависимости от метода расшифрования требуется указать те или иные параметры, и либо подтвердить процесс раскодировки, либо отказаться от него.
После этого в окно редактора будет выдан расшифрованный текст.
При правильном дешифровании полученный текст совпадает с исходным. Если какой – либо задаваемый параметр не точен, то исходный и дешифрованный текст не совпадают, то есть расшифрование проведено неверно.
2.5. Помощь
Имеется возможность посмотреть данный текст ('Помощь Ctrl+F9'), справочную информацию об используемых методах шифрования ('О методах Ctrl+F10'), сведения о программе ('О программе Ctrl+F11').
2.6. Конец работы
Выход из программы.
3. Пример работы с программой
В качестве примера рассмотрим одноалфавитное шифрование с фиксированным ключом.
Нажав клавиши Ctrl+L, либо выбрав в меню пункт «Открыть файл», загрузите в окно редактора исходный текст.
Затем вызовите пункт меню “Шифрование”, выберите одноалфавитный метод (с фиксированным смещением). В появившемся окне нажмите клавишу “Зашифровать”.
После того, как шифрование выполнено, можно также просмотреть в редакторе зашифрованный текст.
Затем перейдите к пункту меню «Гистограмма». Выберите тип гистограмм, отображающий гистограммы исходного и шифрованного файлов. Проанализируйте гистограммы. Они должны иметь примерно одинаковый вид.
Чтобы узнать ключ шифра, (смещение второго алфавита относительно первого), необходимо найти по гистограммам символы, имеющие одинаковую частоту встречаемости. Например, самый частый символ в первой гистограмме при шифровании должен перейти в самый частый символ во второй гистограмме.
Таким образом, найдя два самых часто встречаемых символа в обеих гистограммах, можно по стандартной таблице кодов IBM PC вычислить смещение.
Зная смещение и таблицу кодировки символов, текст можно легко расшифровать.
Вызвав пункт меню “Дешифрование”, можно провести те же действия в автоматическом режиме.
Примечание: при шифровании и дешифровании из таблицы кодировки не используются символы с кодами: 176 – 223 и 240 – 255. То есть при ручной расшифровке эти символы следует пропускать, и считать, что, например, символ “Я” имеет код не 159, а – 223, аналогично “п” не 175, а – 239.
Иногда в гистограммах под столбиками, показывающими частоту встречаемости символов, изображены не сами символы, а их табличные коды в квадратных скобках.
1.Настройка параметров программы.
2.Одноалфавитный метод с фиксированным смещением:
3. Одноалфавитный метод с задаваемым смещением:
4. Метод перестановки символов:
5. Инверсный метод:
6. Многоалфавитный метод с фиксированным ключом:
7. Многоалфавитный метод с ключом фиксированной длины:
8. Многоалфавитный метод с ключом произвольной длины:
4. Дополнительные сведения
Так как, для всех выше перечисленных методов ключи шифрования представляют собой совершенно разные, даже несовместимые типы данных (одноалфавитные методы – длина сдвига, перестановка – массив неповторяющихся цифр, многоалфавитные методы – строки), а для их отображения используется один и тот же элемент окна, то все они (ключи) на интерфейсном уровне общения с пользователем представляются строками, оставаясь внутри программы соответствующими своему изначальному виду.
При запуске утилит шифрования и расшифрования у пользователя спрашивается подтверждение на правильность выбранного метода для работы.
Во время работы длительных по исполнению процедур запускается прогресс процесса и гасится окно текстового редактора. По полоске прогресса можно наблюдать и оценивать примерную скорость работы алгоритма и время окончания текущего процесса.
Операционная среда: WIN’ 95, WIN’ 98 и WIN NT.
Минимальная конфигурация: На которой запускается WINDOWS.
Будьте внимательны при установке параметров работы, так как в процессе вычисления по ходу работы эти параметры изменить уже не удастся.
Конвертация DOS – текстов. При запуске этой опции сразу (без подтверждения со стороны пользователя) происходит прокрутка окна текстового редактора. После окончания конвертации происходит отображение в окне текстового редактора нового (конвертированного) текста.
Примечание:
Не пытайтесь конвертировать файлы с win-кодировкой, так как последствия будут непредсказуемые. Если при открытии файла на экране были псевдографические символы, а после конвертации вид файла не улучшился (не приблизился к русскоязычному варианту), то скорее всего это был не Dos-овский файл, а какой-нибудь ещё системы.
О программе. Краткая информация об авторах программы, и руководителях проекта.
Выгрузка системы.
У пользователя запрашивается подтверждение на выход из программы.
При утвердительном ответе закрываются все открытые файлы, с запросом о сохранении любых изменений; останавливаются все текущие процессы.
Происходит полный выход из системы.
Описание "горячих клавиш":
Shift+F10 - ‘О программе’
Ctrl+X - ‘Выход из программы’
Ctrl+N - New - ‘Файл\Создать’
Ctrl+L - Load - ‘Файл\Открыть’
Ctrl+S - Save - ‘Файл\Сохранить’
Шифрование:
Ctrl+F1 - ‘Одноалфавитный метод (с фиксированным смещением)’
Ctrl+F2 - ‘Одноалфавитный с задаваемым смещением (от 2 до 20)’
Ctrl+F3 - ‘Перестановка символов’
Ctrl+F4 - ‘По дополнению до 255 (инверсный метод)’
Ctrl+F5 - ‘Многоалфавитный метод с фиксированным ключом’
Ctrl+F6 - ‘Многоалфавитный метод с ключом фиксированной длины‘
Ctrl+F7 - ‘Многоалфавитный метод с ключом произвольной длины ‘
Дешифрование:
Shift+F1 - ‘Одноалфавитный метод (с фиксированным смещением)’
Shift+F2 - ‘Одноалфавитный с задаваемым смещением (от 2 до 20)’
Shift+F3 - ‘Перестановка символов’
Shift+F4 - ‘По дополнению до 255 (инверсный метод)’
Shift+F5 - ‘Многоалфавитный метод с фиксированным ключом’
Shift+F6 -‘Многоалфавитный метод с ключом фиксированной длины‘
Shift+F7 - ‘Многоалфавитный метод с ключом произвольной длины‘
Гистограммы:
Shift+Ctrl+F1 - ‘Исходного и шифрованного файла‘
Shift+Ctrl+F2 - ‘Шифрованного и расшифрованного файла‘
Shift+Ctrl+F3 - ‘Стандартного распределения и шифрованного текста‘
Shift+Ctrl+F4-‘Стандартного распределения и расшифрованного текста‘
Помощь:
Ctrl+F9 - 'Помощь'
Ctrl+F10 - 'О методах'
Ctrl+F11 - 'О программе'
Задание
Для этого:
- просмотреть предварительно созданный с помощью редактора свой текстовый файл;
- выполнить для этого файла шифрование;
- просмотреть в редакторе зашифрованный файл;
- просмотреть гистограммы исходного и зашифрованного текстов,
описать гистограммы (в чем похожи, чем отличаются) и определить, с каким смещением было выполнено шифрование;
- дешифровать зашифрованный текст:
В отчете для каждого метода шифрования описывается последовательность выполняемых действий, имена всех использованных файлов, описываются полученные гистограммы, указывается найденное смещение, описывается процесс дешифрования.
Преподавателю предоставляются: отчет о проделанной работе и все использованные и созданные файлы (на рабочей дискете).
Для этого необходимо определить закон перестановки символов открытого текста. Создайте небольшой файл длиной в несколько слов с известным вам текстом, зашифруйте его, просмотрите гистограммы (опишите их; ответьте, можно ли извлечь из них полезную для дешифрации информацию). Сравните (с помощью редактора) ваш исходный и зашифрованный тексты и определите закон перестановки символов.
Дешифруйте файл:
Для этого нужно создать свой файл, состоящий из строки одинаковых символов, выполнить для него шифрование и по гистограмме определить способ шифрования и набор смещений.
Контрольные вопросы
а) метод многоалфавитного кодирования?
б) метод Цезаря?
в) метод шифрования инверсными символами?
Список литературы
ЛАБОРАТОРНАЯ РАБОТА №2
ИССЛЕДОВАНИЕ РАЗЛИЧНЫХ МЕТОДОВ ЗАЩИТЫ ТЕКСТОВОЙ ИНФОРМАЦИИ И ИХ СТОЙКОСТИ
НА ОСНОВЕ ПОДБОРА КЛЮЧЕЙ
1. Введение
Цель лабораторной работы – изучение методов шифрования перестановкой символов, заменой, гаммированием и таблицей Вижинера, механизма дешифрования. А также исследование и сравнение стойкости различных методов, на основе атак путем перебора всех возможных ключей.
2. Работа с программой
В Программный пакет, необходимый для выполнения лабораторной работы входят следующие приложения и сопровождающие файлы:
Первые два исполняемых файла предназначены для запуска и выполняют следующие функции:
Crypto.exe – содержит программу, которая позволяет выполнять:
Система поддерживает следующие методы криптографического преобразования информации:
Содержится набор второстепенных функций обеспечивающих более удобную работу пользователей:
открытие файла и вывод результатов шифрования/дешифрования происходит в уже существующее окно.
Redactor.exe – простенький текстовый редактор, позволяющий организовать работу с текстами, например, их набивку, подготовку для шифрования, внесения некоторых изменений для проверки корректности работы методов шифрования. Предоставляет следующую функциональность:
Обе программы поддерживают работу с английским и с русским алфавитом (данные языки должны быть предустановленны в операционной системе).
Остальные файлы: *.txt, *.zkr, *.otk – являются соответственно простыми текстовыми файлами (распознаваемыми встроенной в MS Windows программой NotePad), зашифрованными и расшифрованными программой Crypto.exe файлами, ее индивидуального формата.
Для запуска лабораторной работы необходимо вызвать на исполнение файл Crypto.exe. На экране дисплея появляется окно с размещённым текстовым окном (для отображения шифрованных и расшифрованных текстов), в верхней части окна расположено главное меню, позволяющее пользователю выполнить требуемое действие, чуть ниже основного меню расположена панель инструментов (для управления быстрыми командными кнопками и другими “горячими” элементами управления), а в самом низу окна, под тестовым редактором, находится строка состояния, в которой указывается “горячая” подсказка и выводится дополнительная информация. Клавиши панели инструментов, для удобства, снабжены всплывающими подсказками.
Для того чтобы попасть в основное меню, необходимо нажать клавишу F10 или клавишу Alt. Передвижение по главному меню осуществляется клавишами перемещения курсора. Чтобы вызвать пункт меню, нужно нажать клавишу “ENTER”, вернуться в главное меню или вовсе выйти из него – “ESC”.
Для удобства в программе предусмотрена работа с мышью. В этом случае указатель подводится к нужному пункту главного меню или к нужной кнопке на панели инструментов и нажимается левая клавиша мыши, аналогичным образом выбираются нужные пункты подменю основных меню, для отказа достаточно нажать клавишу “ESC”.
Пустое окно программы, в которое еще не загружен ни один документ. Здесь изображена рабочая зона приложения, в которой могут располагаться дочерние окна с открытыми или преобразованными документами.
Так выглядит окно приложения при старте - автоматически создается пустое дочернее окно.
Так может выглядеть приложение во время активной работы с ним пользователя.
А теперь более подробно рассмотрим каждый из пунктов главного меню программы Crypto.exe.
2.1. Описание программы Crypto
2.1.1. File – работа с файлами
Данный пункт основного меню содержит подпункты:
Предварительно, сразу после запуска программы, текстовое окно недоступно, также недоступными являются почти все пункты главного меню (кроме создания нового документа, открытия файла, выхода из программы, информации о программе) и большая часть клавиш панели управления (за исключением создания документа, открытия файла и вызова информации о программе).
Создать документ (Ctrl+N) – данный подпункт делает доступным для работы тестовое окно (создается новое окно, в которое можно загрузить текстовый или ранее зашифрованный файл, который впоследствии можно будет использовать при работе с программой).
Открыть файл (Ctrl+О) – при выборе этого пункта появляется диалоговое окно, предоставляющее возможность выбора файла для загрузки. При этом содержимое файла будет отображено в окне.
Также появляется возможность использовать все недоступные до этого пункты основного меню и клавиши панели управления.
Закрыть файл (Ctrl+F4) – закрывается текущее активное окно.
Сохранить файл (Ctrl+S) – при выборе этого пункта появляется диалоговое окно, позволяющее сохранить на диск содержимое редактора текстов.
Сохранить файл (Save As) – при выборе этого пункта появляется диалоговое окно, предоставляющее возможность выбора имени файла для записи.
Выход из программы (Ctrl+X) – при выборе этого пункта производится из программы и закрытие всех открытых окон.
2.1.2. View – управление настройками просмотра документов
Здесь представлены следующие подпункты:
2.1.3. Crypto – Шифрование/дешифрование и подбор ключа методом протяжки вероятного слова.
Вид и описание диалогов приведены ниже в главе диалоги программы Crypto см. п. 3.1.7.
Шифрование текстового файла выполняется одним из четырех методов, рассматриваемых в лабораторной работе:
Дешифрование» – выполнение расшифрования зашифрованного текста.
П р и м е ч а н и е : Обычно термин ДЕШИФРОВАНИЕ применяют, когда известен ключ, а термин РАСШИФРОВАНИЕ – когда ключ не известен.
Аналогично предыдущему пункту выбирается метод расшифрования (должен соответствовать методу, которым был зашифрован файл).
После этого в окно будет выдан расшифрованный текст.
При правильном дешифровании полученный текст совпадает с исходным. Если какой – либо задаваемый параметр не точен, то исходный и дешифрованный текст не совпадают, то есть дешифрование проведено неверно.
2.1.4. Convert – преобразование кодировок символов текста
2.1.5. Window – управление дочерними окнами приложения
2.1.6. Help – Помощь
About CyptoLab (F1) – вызов информации о программе: версии, дате создания, разработчиках и контактах.
2.1.7. Описание диалогов программы Crypto
Диалог о программе –
“About CryptoLab”
Данный диалог содержит следующую информацию:
а также контакт для разрешения проблем, приема замечаний и пожеланий к развитию программного продукта.
Диалог Шифрования-Дешифрования –
“Code DeCode Dialog”
В данном диалоге содержится 4 секции для каждого из методов шифрования. Переключение между методами шифрования (дешифрования) осуществляется кликом левой кнопкой мышки на соответствующей круглой радио-кнопке.
Для метода Замена необходимо ввести сдвиг в поле ввода. Осуществляется набором с клавиатуры или мышью, задействуя кнопки прокрутки. Допустимый диапазон для ввода от 0 до 255.
Для метода Перестановка необходимо указать длину ключа (от 1 до 10), то есть число входящих в него цифр. Для изменения длины ключа используется кнопка Set Length. После задания длины ключа становятся доступными кнопки с цифрами, которые и позволяют ввести нужный ключ. Механизм отключения кнопок реализует ввод уникальной последовательности из неповторяющихся цифр, которая далее используется в качестве ключа шифрования.
При шифровании методом гаммирования ключом выступает строка символов. Длина строки неограниченна, и автоматически определяется программой. Когда Вы хотите вскрыть файл, закрытый методом гаммирование, то длина ключа не должна превышать 10 символов.
Для шифрования методом Гаммирования или Таблицей Вижинера, необходимо выбрать нужный метод и ввести желаемый ключ шифрования.
Кнопка ОК производит шифрование или дешифрование, в зависимости от контекста вызова, а Cancel – отменяет все действия пользователя.
Диалог вскрытия шифра методом протяжки вероятного слова –
“Hack Dialog”
Данный диалог предлагает пользователю набор функциональностей для быстрого подбора ключей к шифрованному тексту и удобного просмотра правильности найденных возможных ключей.
В левом верхнем углу расположена секция “Методы Шифрования”, где пользователь может задать метод шифрования.
Под ней расположено поле задания силы ключа, диапазон для ввода – от 0 до 10. Данное поле не учитывается при использовании метода Замена, т.к. там ключом является смещение символа и это смещение задается одним байтом.
В поле “Вероятное слово” вводится предположительное слово, сочетание слов или фрагмент слова, которое, по мнению пользователя, встречается (желательно неоднократно) в раскрываемом шифре.
Справа расположен список подобранных ключей (изначально он пустой) и клавиши управления и работы с этим списком ключей.
По нажатию на кнопку “Подобрать ключ” происходит процесс подбора ключа заданной длины по выбранному методу шифрования. В поле списка ключей появляется запись метода шифрования, по которому производилось вскрытие, курсор мыши переходит в состояние ожидания, список ключей начинает заполняться найденными вероятными ключами.
Справа от описанных элементов расположена секция управления списком найденных ключей. В списке отражаются вероятные ключи, если все ключи не умещаются в видимой части списка, справа появляется полоса прокрутки, используя которую можно прокручивать весь список вверх и вниз. Также можно использовать клавиши управления курсором вверх и вниз, когда список ключей находится в фокусе, и клавишу Enter для активизации проверки ключа.
По двойному щелчку на ключе из списка можно запустить проверку корректности ключа. Проверка происходит методом шифрования, выбранным в данный момент в списке. Дешифруется фрагмент текста из трех строк, чтобы оператор визуально мог определить верность или неверность ключа по псевдооткрытому тексту.
Опишем кнопки управления списком ключей. Сначала дадим определения курсора в списке ключей. Курсор в списке ключей – отмеченный пользователем ключ, который в данный момент подсвечен в списке. Все операции производятся над ключом, на который указывает курсор.
“Add Key” – добавить ключ. Сверху данной кнопки расположено поле для ввода ключа. Ключ будет добавлен в список в месте текущего положения курсора в списке. Если в данный момент курсор в списке отсутствует, то добавление ключа происходит в конец списка.
“Remove Key” – удалить ключ. Производиться удаление ключа, на котором в данный момент стоит курсор.
“Check Key” – проверить ключ. Равнозначен двойному нажатию на ключ в списке. Проверяется фрагмент текста на дешифрование ключом, но котором находиться курсор.
“Find Key” – найти ключ. Реализует циклический поиск сверху вниз по всему списку ключей. Поиск производиться по ключевым символам, введенным в поле ввода, расположенном под данной кнопкой. Ищется ключ, начинающийся с группы заданных символов. Также символ для поиска может быть один, тогда будут найдены все ключи, начинающиеся с него.
“Clear the same” – убрать повторяющиеся ключи. Часто в процессе подбора ключей, выпадают совершенно одинаковые ключи. Данный факт может определенно помочь в поиске ключа, т.к. если ключ неоднократно повторяется, то он наиболее вероятен, как правильный. Но это не всегда так, чтобы не проверять одинаковые ключи по несколько раз, можно удалить их из списка, оставив только по одному экземпляру.
“Clear no Text” – отфильтровать список ключей, разрешая оставлять в списке только ключи, состоящие из определенного набора символов, цифр или знаков препинания. Вызывается диалог задания состава возможного ключа, который описан ниже.
“Clear All” – полностью очистить список ключей от содержимого.
В самой нижней части диалога расположены два текстовых поля, недоступных для записи. Верхнее содержит фрагмент из вскрываемого текста, а нижние заполняется псевдооткрытым фрагментом этого же шифрованного текста, когда происходит проверка ключа, содержащегося в списке. В случае, когда псевдооткрытый текст признается оператором полностью читабельным, то считается, что был подобран правильный ключ шифрования к данному шифру.
Самая последняя кнопка в диалоге – “Close” – осуществляет закрытие диалога с сохранением всех измененных пользователем настроек. Сохраняются и при следующем открытии диалога будут восстановлены следующие параметры: метод шифрования, сила ключа, вероятное слово для подбора. Содержимое списка ключа, при каждом новом открытии диалога, очищается.
Диалог задания состава возможного ключа –
“Set Valid Symbols in Keys Dialog”
В этом диалоге можно настроить фильтр отбора ключей, задав наборы разрешенных символов, из которых может состоять ключ. Только ключи, все символы которых полностью удовлетворяют комбинации заданных фильтров, останутся в списке. Фильтры комбинируются логической функцией «или». Разрешенными являются наборы или типы символов, отмеченные галочками.
Наборы символов могут быть следующими:
Последний набор символов покрывает все наборы, описанные выше, кроме русских символов. Примечание: из-за расхождений в кодировках символов MS Windows, при подборе ключа, коды, соответствующие русским символам, не показываются в списке ключей, как русские символы, поэтому опция оставить русские символы была закрыта в последней версии программы.
Пример: если пользователю необходимо отфильтровать все ключи, состоящие только из английских букв и десятичных цифр, он оставляет соответствующие фильтры и нажимает на ОК.
При нажатии на ОК происходит фильтрация и обновления списка ключей. Также сохраняются все настройки по примененным фильтрам.
По клавише Cancel, происходит закрытие этого диалога без сохранения изменений, совершенных пользователем, не производиться никаких действий со списком ключей.
Диалог открытия файла
Данный диалог является стандартным диалогом открытия файла MS Windows. Он позволяет осуществлять навигацию по дискам, дереву каталогов, поддерживает обработку одинарных и двойных щелчков мыши.
Для открытия требуемого файла, необходимо, чтобы его имя появилось в поле напротив “Имя файла”, и задействовать кнопку “Открыть”. Выбранный файл загрузиться в окно приложения.
Диалог сохранения файла с новым именем
Данный диалог является стандартным диалогом сохранения файла MS Windows. Он позволяет осуществлять навигацию по дискам, дереву каталогов, поддерживает обработку одинарных и двойных щелчков мыши.
Необходимо выбрать каталог для записи файла и ввести желаемое имя файла. Кнопка “Сохранить” позволяет записать содержимое окна в файл на диске. Если файл с таким именем уже существует, то системы выведет диалог о перезаписи файла, если такого файла не существовало, то будет создан новый файл с заданным именем.
2.1.8. Описание набора инструментов программы Crypto
Ниже перечислены в порядке слева на право функции, выполняющиеся соответствующим значком.
2.1.9. Описание “горячих клавиш” используемых в программе Crypto
2.2. Описание программы Redactor
Приложение Redactor представляет собой отдельный программный модуль, способный работать параллельно с основной шифрующей программой Crypto. Redactor предназначен для создания, изменения и просмотра текстовых файлов, которые затем могут быть использованы программой Crypto, также Redactor поддерживает работу с форматом файлов, задаваемым программой Crypto при шифровании/дешифровании текстовой информации.
Общий вид программы Redactor:
Далее приведено более подробное описание программы Redactor.
2.2.1. Меню File – работа с файлами
Данный пункт основного меню позволяет выполнить следующие операции:
Предварительно, сразу после запуска программы создается пустое текстовое окно, но недоступными являются почти все пункты главного меню (кроме создания нового документа, открытия файла, выхода из программы, информации о программе) и большая часть клавиш панели управления (за исключением создания документа, открытия файла и вызова информации о программе).
New – Создать документ (Ctrl+N) – данный подпункт делает доступным для работы тестовое окно (создается новое окно, в которое можно загрузить текстовый файл, произвести набор текста, который впоследствии можно будет сохранить на диск и использовать при работе с программой Crypto).
Open – Открыть файл (Ctrl+О) – при выборе этого пункта появляется диалоговое окно, предоставляющее возможность выбора файла для загрузки. При этом содержимое файла будет отображено в окне.
Close – (Ctrl+F4) Закрыть файл – закрывается текущее активное окно.
Save – Сохранить файл (Ctrl+S) – при выборе этого пункта появляется диалоговое окно, позволяющее сохранить на диск содержимое редактора текстов.
Save As - Сохранить файл – при выборе этого пункта появляется диалоговое окно, предоставляющее возможность выбора имени файла для записи.
Print – Распечатать документ.
Print Preview – Предварительный просмотр расположения содержимого документа на бумаге.
Print Setup – Вызов диалога управления настройками принтера.
Примечание: для возможности печати из программы, необходимо наличие подключенного к компьютеру или локальной сети принтера, а также корректные настройки и драйвера Операционной Системы.
Далее расположен список файлов, с которыми недавно велась работа.
Exit - Выход из программы (Alt+F4) – при выборе этого пункта производится из программы и закрытие всех открытых окон.
2.2.2. Меню Edit – редактирование текста
Undo – Отменить (Ctrl+Z) – отменить последнее действие пользователя.
Cut – Вырезать в буфер (Ctrl+X) – Меню становится доступным, если в тексте есть выделенный участок. Выделение можно производить следующими способами: удерживая левую клавишу мыши провести над необходимым для выделения участком или используя курсоры, придерживая нажатой клавишу Shift. Выделенный участок (это может быть один символ, слово, строка, несколько абзацев) удаляется из текста и заносится в буфер операционной системы. Текст из буфера может быть доступен различным приложениям запускаемым в этой операционной системе.
Copy – Скопировать в буфер (Ctrl+C) – выделенный участок копируется в буфер и остается в тексте.
Paste – Вставить из буфера (Ctrl+V) – в редактируемый текст, в месте положения курсора вставляется текст, занесенный ранее в буфер.
2.2.3. Меню View - управление настройками просмотра документов
2.2.4. Меню Window – управление дочерними окнами приложения
2.2.5. Меню Help – Помощь
Вызов информации о программе: версии, дате создания, разработчиках и контактах.
2.2.6. Описание диалогов программы Redactor
Диалог о программе –
“About Redactor”
Данный диалог содержит записи о следующей информации:
Диалог настройки установок принтера – “Настройка Печатии”
Используя данный диалог, пользователь может совершить следующие действия:
Диалоги Отрыть и Сохранить Файл идентичны таким же диалогам, описанным в программе Crypto.
2.2.7. Описание набора инструментов программы Redactor
Ниже перечислены в порядке слева на право функции, выполняющиеся соответствующим значком.
2.2.8. Описание “горячих клавиш” используемых в программе Redactor
2.3. Конец работы
Для того чтобы завершить работу над лабораторным заданием, необходимо осуществить выход из программы Crypto и Redactor. Не забудьте сохранить те данные, которые могут Вам понадобиться при дальнейшей работе с этими программами.
3. Пример работы с программами
Рассмотрим более подробно этапы работы с лабораторным программным комплексом для осуществления шифрации/дешифрации/вскрытия шифрованного текста.
В качестве первого примера рассмотрим одно-алфавитное шифрование (метод замены).
Если файл, предназначенный для шифрования уже существует, то его можно загрузить в приложение Crypto, вызвав диалог “Open File”. Для этого можно воспользоваться пунктом меню File/Open или значком на панели инструментов (Ctrl + L). В статус баре и в выплывающих строках, появляющихся при движении курсора мыши над кнопкой, содержаться подсказки для пользователей.
Если Вам необходимо открыть файл в новое окно, то предварительно его нужно создать посредством меню File/New или соответствующей иконкой на панели инструментов (Ctrl + N). Появится новое пустое окно, в которое можно загружать файл с диска.
В случае отсутствия готового текстового файла для шифрования, Вы можете воспользоваться программой Redactor для его создания. Для этого необходимо запустить приложение Redactor. Далее, как и в программе Crypto, создать новое пустое окно. Во время первого запуска программы Redactor пустое окно создается автоматически.
В пустое окно необходимо набить текст, предназначенный для шифрования. После окончания занесения текста, его можно сохранить в файле формата *.txt (универсальный) или в формате *.otk (принимаемый программой Crypto).
На данном этапе мы загрузили файл в программу Crypto. В окне отражается загруженная информация.
В случае, если текст не читаем, возможно применена иная раскладка (для MS DOS), чтобы перейти в MS Windows раскладку, необходимо из меню Convert вызвать операцию Oem To Ansi (F10). Функция Ansi To Oem (F9) выполняет обратное преобразование.
Теперь можно переходить непосредственно к самому шифрованию. Для этого надо вызвать диалог Шифрования/Дешифрования (F5). Выбрать метод шифрования, который будет использоваться. В данном примере нам необходим пункт “Замена”.
После этого необходимо задать ключ шифрования. Для метода одно-алфавитного шифрования ключом является сдвиг кода символа по модулю длины алфавита. Используется кодировка ASKII, таким образом, в качестве ключа шифрования для метода Замены может выступать целое положительное число от 0 до 255.
После того, когда желаемый ключ будет выбран – ключ можно вводить как с клавиатуры, так и с помощью мыши, необходимо нажать на кнопку ОК для произведения шифрования. Система не позволит ввести число меньшее 0 или большее 255.
Когда процесс шифрования закончится, диалог Шифрования закроется, а в окне, где был исходный файл, отобразится результат проделанной операции.
Для дешифрования закрытого файла, который был получен после шифрования, необходимо выбрать опцию дешифрование (F6). Далее все параметры для дешифрования задаются аналогично параметрам для шифрования. Процесс дешифрования запускается по кнопке ОК. Результат выводится в то же текстовое окно.
В случае совпадения ключей, использованного для шифрования и дешифрования, дешифрованный текст должен быть идентичен исходному открытому.
Если в целях тестирования необходимо изменить шифрованный текст и проверить, как он расшифруется на том же ключе, необходимо сохранить зашифрованный файл на диске и загрузить его в Redactor. При этом нет необходимости выгружать тот же файл из Crypto. Далее в редакторе производятся необходимые изменения и сохраняются в файле. Этот файл надо загрузить в Crypto, чтобы продолжить работу над ним.
Также имеется возможность печати файлов в Redactorе. Этой возможностью можно воспользоваться, когда необходимо распечатать результаты шифрования текстового файла.
Для того, чтобы попытаться подобрать ключ шифрования, необходимо, имея в текстовом окне зашифрованный файл, вызвать диалог Вскрытия. Для этого можно воспользоваться соответствующей иконкой или опцией меню Code/Hack (F8).
В этом диалоге необходимо указать метод шифрования, размер ключа, который мы хотим подобрать. В случае замены размер ключа не используется, так как он равен одному байту. Для других методов размер ключа определяет число символов или цифр, входящих в ключ.
Далее задается вероятное слово, которое предполагается встретить в зашифрованном тексте. Размер слова влияет на скорость работы алгоритмов вскрытия, на число и качество найденных ключей. Вероятное слово можно задавать, исходя из априорной информации, известной о зашифрованном документе. Необходимо руководствоваться темой, к которой он относиться, или некоторой стандартной формой заполнения, как часто бывает в отчетной и иной финансовой документации.
Чтобы осуществить поиск возможных ключей, необходимо нажать на кнопку “Подобрать ключ”. В списке найденных ключей появиться набор возможных ключей (если поиск был успешным). С этим списком ключей можно осуществлять следующие действия:
Программа находит те ключи, при использовании которых в открытом тексте должны получиться сочетания символов, совпадающие с заданным вероятным словом. Чтобы отобрать правильный ключ, который позволить получить открытый текст целиком и корректно, необходима работа оператора. Оператор визуально проверяет каждый ключ. Производится попытка расшифровать фрагмент текста текущим ключом. Выводится псевдооткрытый текст, если оператор признает его корректным – ключ принимается за правильный, иначе ключ отбраковывается.
При попытке расшифровать фрагмент текста возможным ключом из списка проверяется, чтобы предлагаемый ключ начинался с цифры (нескольких цифр), которая (которые) и будут ключом дешифрования. Также проверяется допустимый диапазон значения ключа от 0 до 255.
Формула для времени вскрытия
Если найденный список не привел к положительным результатам, то необходимо изменить параметры подбора ключей, а именно:
Для завершения работы с диалогом вскрытия, используйте кнопку “Close”.
Далее кратко опишем действия пользователя при шифровании другими методами. Подготовка, загрузка и сохранение файлов, а также вызов необходимых для работы диалогов производится описанным выше образом.
Для метода перестановки, необходимо, в диалоге шифрования выбрать этот метод, и указать длину ключа, то есть число входящих в него цифр. После задания длины ключа становятся доступными кнопки с цифрами, которые и позволяют ввести нужный ключ. Механизм отключения кнопок реализует ввод уникальной последовательности из неповторяющихся цифр, которая далее используется в качестве ключа шифрования.
Для вскрытия файла, защищенного методом перестановки, применяется ускоренный алгоритм. Скорость выполнения предложенного алгоритма прямо пропорциональна длине проверяемого текста и длине ключа. В то время как трудоемкость других алгоритмов, в том числе путем полного перебора всех возможных комбинаций, имеет экспоненциальную зависимость от длины подбираемого ключа. Что практически не приемлемо для выполнения задания за время одного лабораторного занятия.
Хотя заложенный алгоритм не обеспечивает 100% успеха при поиске ключей, даже если заданный фрагмент действительно встречается в тексте. Необходимо, чтобы он попал на границу разбиения строки по фрагментам, равным длине ключа. Данный побочный эффект можно преодолеть, задавая достаточно длинное вероятное слово (примерно равное удвоенной длине искомого ключа). Также этот алгоритм показывает более успешные результаты работы, при отсутствии в предлагаемом слове повторяющихся букв (стоящих ближе, чем длина подбираемого ключа), так как в этом случае программа не знает, как правильно переместить и расставить одинаковые символы.
При проверке ключа из списка ключей, происходит его предварительная проверка, которая устанавливает, представляется ли возможным использовать предложенный ключ для дешифрования методом перестановки. Ключ для перестановки должен состоять из непрерывающейся последовательности целых чисел из диапазона, равного длине ключа, без повторяющихся цифр. В случае несоответствия ключа перечисленным требованием, об этом будет оповещен пользователь, так как проверка такого ключа невозможна.
При шифровании методом гаммирования ключом выступает строка символов. Длина строки неограниченна, и автоматически определяется программой. Когда Вы хотите вскрыть файл, закрытый методом гаммирования, то длина ключа не должна превышать 10 символов.
Для шифрования методом гаммирования необходимо выбрать соответствующую строчку в диалоге и задать строку символов в поле ввода ключа. Вскрытие файла, зашифрованного методом гаммирования происходит аналогично алгоритму, описанному ранее.
Вся последовательность действий при работе с методом шифрования “таблицей Вижинера” полностью соответствует этапам шифрования методом гаммирования. Ключом для “таблицы Вижинера” выступает также символьная строка, неограниченной длины.
4. Дополнительные сведения
Примечание:
Не пытайтесь конвертировать файлы с win-кодировкой, так как последствия будут непредсказуемые. Если при открытии файла на экране были псевдографические символы, а после конвертации вид файла не улучшился (не приблизился к русскоязычному варианту), то, скорее всего, это был не Dos-овский файл, а какой-нибудь ещё системы.
5. Задание
Ознакомиться с описанием лабораторной работы и заданием.
Для метода замены (одноалфавитного метода):
Для метода перестановки:
Для гаммирования:
Для таблицы Вижинера все действия повторяются из п. 4 (метод гаммирования).
Специальное задание:
На каждую бригаду выдается уникальное задание, детали которого уточняются преподавателем. Бригада получает пакет закрытых файлов, ей (бригаде) сообщается только, к какой теме относится информация, содержащаяся в этом пакете. Нет данных о методе шифрования, ключе шифрования и даже о языке, на котором составлен исходный текст, он может оказаться не только русским, но и любым иностранным (английским или немецким).
В задачу бригаде ставится раскрытие любого из представленного файла (желательно, конечно, полное раскрытие пакета) за приемлемое время (продолжительность лабораторного занятия), используя только средства предлагаемой программы, любой из четырех доступных методов шифрования и подбор ключа по вероятному слову.
Необходимо установить: какое слово может наиболее часто встречаться в тексте по предложенной тематике, угадать метод и длину ключа. Затем, по полученному списку возможных ключей, совершить визуальную проверку на раскрытие информации (осуществляется по двойному щелчку по ключу, содержащемся в списке найденных ключей). Представить список найденных ключей, которых можно считать подходящими для раскрытия какого-либо файла и получившийся результат раскрытия.
В отчете для каждого метода шифрования описывается последовательность выполняемых действий, имена всех использованных файлов, указываются найденные исходные и найденные ключи, описывается процесс дешифрования.
Преподавателю предоставляется отчет о проделанной работе и все использованные файлы (на рабочей дискете).
6. Контрольные вопросы:
5. Чем отличается “псевдооткрытый” текст (текст, полученный при расшифровке по ложному ключу) от настоящего открытого текста?
6. Как зависит время вскрытия шифра описанным выше способом подбора ключей от длины “вероятного” слова?
7. Зависит ли время вскрытия шифра гаммирования (или таблицы Вижинера) от мощности алфавита гаммы?
7. Список литературы
ЛАБОРАТОРНАЯ РАБОТА №3
ИЗУЧЕНИЕ ПЕРСОНАЛЬНЫХ СРЕДСТВ ЗАЩИТЫ ИНФОРМАЦИИ НА ПРИМЕРЕ ПРОГРАММНОГО СРЕДСТВА КРИПТОГРАФИЧЕСКОЙ ЗАЩИТЫ PGP 5.5
1. Введение
Цель – изучение основных возможностей персональных средств защиты информации на примере программного средства криптографической защиты PGP 5.5.
Для выполнения лабораторной работы необходимо знание общих сведений о ПЭВМ IBM PC (работа в Windows 95).
2. Работа с программой
Программное СКЗИ PGP 5.5 позволяет выполнить следующие функции:
- создать пару ключей “закрытый-открытый”;
- зашифровать файл открытым ключом;
- расшифровать файл закрытым ключом;
- подписать файл ЭЦП закрытым ключом;
- проверить ЭЦП открытым ключом.
Кроме того, PGP 5.5 предоставляет возможность защищать письма электронной почты и тома файловой системы (сквозное шифрование диска), а также включает возможность безопасного удаления файлов. В данной лабораторной работе эти возможности не рассматриваются.
Подробное руководство пользователя приведено в [4].
Оперативная информация об изменениях, исправлениях и новых версиях доступна на Web-сайте компании Pretty Good Privacy Inc. www.pgp.com.
Программа PGP 5.5 состоит из двух основных частей PGPtools и PGPkeys; PGPtools содержит средства шифрования и ЭЦП; PGPkeys – средства управления ключами и способно создавать пары ключей и экспортировать открытые ключи на внешние носители для их распространения другим абонентам.
Запуск программы PGP 5.5 осуществляется из меню Start/Progpams/Pretty Good Privacy/PGPtools (или /PGPkeys).
Для того чтобы начать работать с PGP следует создать пару ключей “открытый-закрытый” и распространить открытый ключ по всем абонентам, с которыми Вы хотите обмениваться защищенной информацией. Для этого следует запустить PGPkeys, выбрать пункт меню Keys/New Key и следовать инструкциям программы. Для распространения открытого ключа необходимо выбрать пункт меню Keys/Export, сохранить открытый ключ в файле и передать абонентам по каналу, защищенному от подмены информации.
Для зашифровки файла запускают PGPtools и нажимают кнопку Encrypt и следуют указаниям программы. Аналогично для постановки цифровой подписи нажимают кнопку Sign, а для расшифровки или проверки подписи – Decrypt/Verify.
3. Требования к протоколу
В протоколе следует фиксировать следующие данные:
Для пунктов 1-4:
- краткое описание производимых действий;
- с помощью каких ключей выполняются действия – открытые или закрытые, и какого абонента;
- параметры ключа при его генерации;
- результаты проверки подписи и расшифровки (стал ли файл читаем).
Для пунктов 5-7:
- графики зависимости и результаты измерения в табличном виде;
- предположения о характере зависимости.
Задание
1. Запустите программу PGPkeys и создайте пару ключей “открытый-закрытый”. Рекомендуемые параметры ключа: тип Diffie-Hellman/DSS, длина 1024 бит.
Задайте пароль для защиты закрытого ключа.
Экспортируйте открытый ключ в текстовый файл. Просмотрите этот файл в Notepad.
Импортируйте открытый ключ из текстового файла.
Передайте открытый ключ соседней бригаде с помощью дискеты или сети и получите их открытый ключ. Импортируйте полученный ключ.
2. Создайте текстовый файл и наберите произвольный текст. Зашифруйте файл. Убедитесь, что текст стал нечитаем (просмотрите в Notepad). Расшифруйте файл. Каким ключом файл был зашифрован? Каким расшифрован?
Зашифруйте файл для передачи соседней бригаде и передайте его с помощью дискеты или сети. Получите зашифрованный файл от них и расшифруйте его.
3. Подпишите текстовый файл. Просмотрите как выглядит ЭЦП. Проверьте подпись. Внесите изменение в файл. Проверьте подпись. Каким ключом файл был подписан? Каким проверялась ЭЦП?
4. Подпишите файл для передачи соседней бригаде и передайте его с помощью дискеты или сети. Получите подписанный файл от них и проверьте его подпись.
5. Постройте зависимость времени генерации ключа от его длины для алгоритма Diffie-Hellman - DSS (от 768 до 4096 бит). Для построения примерного графика снимите 6-8 точек. Каков характер этой зависимости? Почему именно такой?
6. Постройте зависимость времени генерации ключа от его длины для алгоритма RSA (от 512 до 2048 бит). Для построения примерного графика снимите 6-8 точек. Каков характер этой зависимости? Почему именно такой?
7. Постройте зависимость времени шифрования и времени постановки цифровой подписи от длины файла для алгоритмов Diffie-Hellman – DSS и RSA. Рекомендуется диапазон 1 … 10Mb для Pentium 100. Если машина мощнее, выберете большие файлы для более точного измерения времени. Для построения примерного графика снимите 6-8 точек. Каков характер этой зависимости? Почему именно такой?
Контрольные вопросы
1. Что такое асимметричная криптографическая система? В чем их преимущества перед симметричными? В чем недостатки?
2. Какие ключи должны присутствовать на Вашей машине и машине абонента А чтобы:
- зашифровать файл для посылки абоненту А;
- расшифровать файл полученный от абонента А;
- подписать файл для посылки абоненту А;
- проверить подпись на файле, полученном от абонента А?
3. На каких односторонних функциях основываются криптографические системы Diffie-Hellman, DSS и RSA?
4. Как зависит объем вычислений, который необходимо провести для атаки на криптографическую систему от разрядности ключа?
5. Каков характер зависимости времени генерации ключа от его длины?
6*. Почему рекомендуемая длина ключей для алгоритма RSA в два раза больше чем для Diffie-Hellman и DSS?
Литература
1. Мельников Ю.Н. Общие принципы защиты банковской информации//Банковские технологии. № 7. 1995. C. 21-27.
2. Варфоломеев А.А., Пеленицын М.Б. Методы криптографии и их применение в банковских технологиях: Учебное пособие. М.: Издательство МИФИ. 1995. 116 с.
3. Мафтик С. Механизмы защиты в сетях ЭВМ. М.: Мир, 1993. 216 с.
4. PGP for Business Security. User’s Guide. Pretty Good Privacy Inc.
ЛАБОРАТОРНАЯ РАБОТА №4.
ГЕНЕРАЦИЯ ПРОСТЫХ ЧИСЕЛ, ИСПОЛЬЗУЕМЫХ В
КРИПТОАЛГОРИТМАХ С ОТКРЫТЫМ КЛЮЧОМ
1. Введение
Для того, чтобы схема цифровой подписи была достаточно стойкой от подделки, числа, на которых она строиться должны быть случайными большими простыми числами и иметь в своей двоичной записи несколько сотен бит.
Проблема генерации многоразрядных случайных простых чисел представляет собой весьма важную задачу, поскольку от выбранного алгоритма генерации существенно зависят такие параметры криптосхемы, как время работы (на этапе настройки программы – создания образца подписи) и стойкость, т.е. устойчивость к подделке подписи.
Данная лабораторная работу предоставляет возможность глубоко проанализировать проблему генерации многоразрядных простых и случайных чисел.
2. Описание программы
Для запуска лабораторной работы необходимо вызвать на исполнение файл L_PROST.EXE. На экране дисплея появляется окно, с размещённым в его центре текстовым редактором, предназначенном для отображения информации об осуществлённых программой действиях. В верхней строке окна расположено главное меню. Чуть ниже основного меню расположена панель инструментов для управления быстрыми командными кнопками и другими “горячими” элементами управления. В самом низу окна, под тестовым редактором, находится строка состояния, в которой указывается “горячая” подсказка и выводится дополнительная информация. Клавиши панели инструментов, для удобства, снабжены всплывающими подсказками.
Для того чтобы попасть в основное меню, необходимо нажать клавишу F10. Передвижение по главному меню осуществляется клавишами перемещения курсора. Чтобы вызвать пункт меню, нужно нажать клавишу “ENTER”, “ESC” – выход из основного меню.
Для удобства в программе предусмотрена работа с мышью. В этом случае указатель подводится к нужному пункту главного меню или к нужной кнопке на панели инструментов и нажимается левая клавиша мыши, для отказа достаточно нажать клавишу “ESC”.
Кроме основных функций главного меню (“Генерация простого P”, “Поиск в интервале”, “Проверка на простоту” и так далее) панель инструментов содержит клавишу, по нажатии на которою, выводится информация о программе.
А теперь более подробно рассмотрим каждый из пунктов главного меню.
2.1. Генерация простого числа P
Возможность генерации простого числа; количество разрядов генерируемого числа задаётся пользователем (от 1 до 5).
2.2. Поиск в интервале
Возможность поиска простых чисел в задаваемом интервале. Пользователем задаётся: начало интервала – значение x, затем длина интервала – значение L. Поиск будет осуществляться в интервале (x, x+L).
При проверке на простоту каждого числа интервала сначала выполняется тест пробных делений на первые по порядку простые числа, а затем проверка по тесту Ферма. Для задания способов проверки на простоту необходимо левой клавишей мыши отметить флажок рядом с названием нужного метода, а затем указать все необходимые данные для начала поиска.
В методе пробных делений исходные данные – количество первых простых чисел для деления, а в тесте Ферма надо указать количество оснований и их значения
По окончании расчёта на экран выведутся найденные простые числа и их количество. Полную картину результатов работы можно просмотреть в пункте меню “Вывод результатов“.
2.3. Проверка на простоту
Возможность проверки на простоту любого числа. Необходимо ввести число и параметры расчёта аналогично поиску в интервале.
2.4. Вывод результатов
Возможность просмотра всех результатов последней обработки. При входе в программу, когда никаких расчётов ещё не производилось, предоставляется возможность просмотра исходного файла первых простых чисел, используемых для теста пробных делений.
2.5. Выход
Завершение работы программы.
3. Пример работы с программой
1.Генерация простого числа Р:
2. Поиск в интервале:
- для теста пробных делений это количество первых простых чисел для деления (вводится с клавиатуры);
- для теста Ферма это количество оснований от 1 до 5 (вводится путём нажатия соответствующей кнопки) и значения этих оснований (вводится с клавиатуры);
3. Проверка на простоту:
- для теста пробных делений это количество первых простых чисел для деления (вводится с клавиатуры);
4.Вывод результатов:
Дополнительные сведения
7.1. У пользователя запрашивается подтверждение на выход из программы.
7.2. При утвердительном ответе закрываются все открытые файлы, останавливаются все текущие процессы.
7.3. Происходит полный выход из системы.
Ctrl+F1 - ‘Генерация простого P’
Ctrl+F2 - ‘Поиск в интервале’
Ctrl+F3 - ‘Проверка на простоту’
Ctrl+F4 - ‘Вывод результатов’
Ctrl+X - ‘Выход из программы’
Для правильного функционирования программы, в рабочей директории (вместе с файлом l_prost.exe) обязательно должны находиться файлы prost.txt и work.txt. Не рекомендуется вносить какие–либо изменения в эти текстовые файлы, иначе последствия могут быть самые непредсказуемые.
Задание
2. Распределение простых чисел.
2.1. Задан интервал вида [х, x+L]. Вычислить количест во П(х, L) простых чисел в интервале и сравнить с величиной L/ln(x). При каких условиях П(x,L)/L близко к 1/ln(x)? Для IBM PC рекомендуется:
х=2000, L=500,
количество простых чисел для деления: 5-15,
количество оснований: 1—2.
2.2. Найти в заданном интервале все простые числа. Пусть L(i) - разность между двумя соседними простыми числами. Построить гистограмму для L(i). Вычислить выборочное среднее Lсред. Сравнить с величиной ln(x), где х - середина интервала. Для IBM PC рекомендуется:
Интервал: (1000, 1000+300),
количество простых чисел для деления: 5-20,
количество оснований: 1-3.
2.3. Для заданного набора чисел {k} оценить относительную погрешность формулы для k – го простого числа:
p(k)=k.ln(k), k={10, 15, 20, 30, 35}.
3. Методы генерации простых чисел.
3.1. В заданном преподавателем интервале построить график относительного количества натуральных чисел, проходя щих «решето Эратосфена» (т. е. не делящихся на первые k простых).
Для IBM PC рекомендуется: Интервал: (500, 500+200).
Расчет производится для всех k<==10.
3.2. Для заданного интервала:
а) рассчитать точное количество РО простых чисел в ин тервале, т.е. при проверке задать только тест на делимость.
Количество первых простых чисел для деления определя ется из расчета: максимальное число для деления равно квадратному корню из максимального значения интервала.
б) составить тест с небольшим количеством пробных де лений и одним основанием в тесте Ферма. Вычислить количество Р1 вероятно простых чисел, удовлетворяющих этому тесту.
в) составить тест с большим, чем в предыдущем случае, количеством пробных делений и двумя или тремя основания ми в тесте Ферма. Вычислить количество Р2 вероятно простых чисел, удовлетворяющих этому тесту.
Для IBM PC рекомендуется:
Интервал: (1500,1500 + 300).
Проанализировать полученные данные.
3.3. Известно, что в заданном интервале имеются числа Кармайкла. Найти их.
Варианты интервалов: (1050, 1050 + 100)
(1700, 1700 + 100)
(2400, 2400 + 100)
4. Домашнее задание: рассчитать оптимальную страте гию получения простого числа — выбрать соотношение меж ду количеством малых простых чисел и количеством тестов Ферма. Цель - минимизировать время проверки заданного числа на простоту.
Контрольные вопросы
1. Почему в качестве первого основания в тестах типа теста Ферма для проверки на простоту очень больших чи сел целесообразно использовать число 2?
2. Какова вероятность Р(х) того, что наугад взятое нечет ное очень большое число, не превосходящее х, окажется простым?
3. В качестве теста на простоту используется тест Ферма с двумя основаниями: 2 и 4. Является ли такой выбор оснований удачным?
4. Вычислить:
1812 (mod 13), 127 (mod7),2'°°(mod 11).
Литература
1. Виноградов И. М. Основы теории чисел. М.:1981. 176 с.