Шифрование информации

Размещено на http://www.allbest.ru/

Содержание

шифрование информация программирование авторизованный

Введение

1. Постановка задачи

1.1 Методы шифрования

1.2 Симметричное шифрование

1.3 Асимметричное шифрование (с открытым ключом)

2. Шифр Цезаря

2.1 Skipjack

2.2 Классификация методов шифрования

3. Выбор языка программирования

3.1 Достоинства языка программирования

3.2 Недостатки языка программирования

4. Метод шифрования с открытым ключом

4.1 Алгоритм RSA

4.2 Алгоритм на основе задачи об укладке ранца

4.3 Вероятностное шифрование

4.4 Алгоритм шифрования Эль-Гамаля

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

Заключение

Список используемых источников

Приложение



Введение

С самим появлением человеческой цивилизации появилась надобность передачи информации нужным людям так, чтобы она не делалась известной посторонним. Поначалу люди употребляли для трансляции сообщений только голос и жесты.

С появлением письменности вопрос обеспечения засекреченности и подлинности транслируемых сообщений стал особенно важным. Вследствие этого именно после изобретения письма возникло искусство криптографии, способ «тайно писать» - набор методик, предназначенных для тайной передачи записанных сообщений от одного посвященного человека другому.

Шифрование возникло именно как практический предмет, изучающий и разрабатывающий методы шифрования информации, то есть при трансфере сообщений - не скрывающий сам факт передачи, а делающий текст сообщения недоступным для прочтения непосвященными людьми. Ради этого текст сообщения должен быть записанным таким образом, чтобы с его содержанием не мог ознакомиться ни один человек за исключением самих адресатов.

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

Некоторые из криптографических систем дошли до нас из дремучей древности. Вероятнее всего они родились одновременно с письменностью в IV тысячелетии до нашей эры. Способы тайной переписки были придуманы независимо во многих древних государствах, таких как Египет, Греция и Япония, но детальный состав криптологии в них сейчас неизвестен. Криптограммы находятся даже в древнее время, хотя из-за применявшейся в древнем мире идеографической письменности в виде стилизованных пиктограмм они были довольно примитивны. Шумеры, судя по всему, пользовались искусством тайнописи.

Археологами был найден ряд глиняных клинописных табличек, в которых первая запись часто замазывалась толстым слоем глины, на котором и производилась вторая запись. Появление подобных странных табличек вполне могло быть обосновано и тайнописью, и утилизацией. Поскольку количество знаков идеографического письма насчитывало более тысячи, их запоминание представляло собой довольно таки трудную задачу - тут становилось не до шифрования. Однако, коды, появившиеся в одно время со словарями, были очень хорошо знакомы в Вавилоне и Ассирийском государстве, а древние египтяне пользовались по крайней мере тремя системами шифрования. С происхождением фонетического письма письменность сразу же упростилась. В древнесемитском алфавите во II тысячелетии до нашей эры существовало всего лишь около 30 знаков. Ими обозначались согласные, а также некоторые гласные звуки и слоги. Упрощение письменности вызвало развитие криптографии и шифрования.

Даже в книгах Библии мы можем найти примеры шифровок, хотя почти никто их не замечает. В книге пророка Иеремии (22,23) мы читаем: "...а царь Сессаха выпьет после них. " Этого царя и такого царства не существовало - неужели ошибка автора? Нет, просто иногда священные иудейские манускрипты шифровались обычной заменой. Вместо первой буквы алфавита писали последнюю, вместо второй - предпоследнюю и так далее. Этот старый способ криптографии называется атбаш. Читая с его помощью слово СЕССАХ, на языке оригинала мы имеем слово ВАВИЛОН, и весь смысл библейского манускрипта может быть понят даже теми, кто не верит слепо в истинность писания.

Шифрование -- обратимое преобразование информации в целях сокрытия от неавторизованных лиц, с предоставлением, в это же время, авторизованным пользователям доступа к ней. Главным образом, шифрование служит задачей соблюдения конфиденциальности передаваемой информации. Важной особенностью любого алгоритма шифрования является использование ключа, который утверждает выбор конкретного преобразования из совокупности возможных для данного алгоритма.

Пользователи являются авторизованными, если они обладают определенным аутентичным ключом. Вся сложность и, собственно, задача шифрования состоит в том, как именно реализован этот процесс.

В целом, шифрование состоит из двух составляющих -- зашифрование и расшифрование.

С помощью шифрования обеспечиваются три состояния безопасности информации:

Конфиденциальность.

Шифрование используется для скрытия информации от неавторизованных пользователей при передаче или при хранении.

Целостность.

Шифрование используется для предотвращения изменения информации при передаче или хранении.

Идентифицируемость.

Шифрование используется для аутентификации источника информации и предотвращения отказа отправителя информации от того факта, что данные были отправлены именно им.

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

Шифрование применяется для хранения важной информации в ненадёжных источниках и передачи её по незащищённым каналам связи. Такая передача данных представляет из себя два взаимно обратных процесса:

Перед отправлением данных по линии связи или перед помещением на хранение они подвергаются зашифрованию.

Для восстановления исходных данных из зашифрованных к ним применяется процедура расшифрования.

Шифром называется пара алгоритмов, реализующих каждое из указанных преобразований. Эти алгоритмы применяются к данным с использованием ключа. Ключи для шифрования и для расшифрования могут различаться, а могут быть одинаковыми. Секретность второго (расшифровывающего) из них делает данные недоступными для несанкционированного ознакомления, а секретность первого (шифрующего) делает невозможным внесение ложных данных. В первых методах шифрования использовались одинаковые ключи, однако в 1976 году были открыты алгоритмы с применением разных ключей. Сохранение этих ключей в секретности и правильное их разделение между адресатами является очень важной задачей с точки зрения сохранения конфиденциальности передаваемой информации. Эта задача исследуется в теории управления ключами (в некоторых источниках она упоминается как разделение секрета).

В настоящий момент существует огромное количество методов шифрования. Главным образом эти методы делятся, в зависимости от структуры используемых ключей, на симметричные методы и асимметричные методы.



1. Постановка задачи

Передо мной была поставлена задача разработать программу, которая выполняет функции шифрования и дешифрования методом открытого ключа, т.е. шифрование и дешифрование осуществляется с помощью разных ключей. Средой, для написания программы, был выбран объектно-ориентированный язык программирования Delphi 7. Благодаря тому, что Delphi является объектно-ориентированной средой это упрощает создание единообразного интерфейса. Диалог пользователя с программой, а именно введение текста, подлежащего шифрованию, осуществляется посредством диалоговых окон программы.

1.1 Методы шифрования

В симметричных криптосистемах для шифрования и расшифрования используется один и тот же ключ. Отсюда название -- симметричные. Алгоритм и ключ выбирается заранее и известен обеим сторонам. Сохранение ключа в секретности является важной задачей для установления и поддержки защищённого канала связи. В связи с этим, возникает проблема начальной передачи ключа (синхронизации ключей). Кроме того существуют методы криптоатак, позволяющие так или иначе дешифровать информацию не имея ключа или же с помощью его перехвата на этапе согласования. В целом эти моменты являются проблемой криптостойкости конкретного алгоритма шифрования и являются аргументом при выборе конкретного алгоритма.

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

Схема реализации

Задача. Есть два собеседника -- Алиса и Боб, они хотят обмениваться конфиденциальной информацией.

Генерация ключа.

Боб (или Алиса) выбирает ключ шифрования и алгоритм (функции шифрования и расшифрования), затем посылает эту информацию Алисе (Бобу).

Шифрование и передача сообщения.

Алиса шифрует информацию с использованием полученного ключа .

И передает Бобу полученный шифротекст . То же самое делает Боб, если хочет отправить Алисе сообщение.

Расшифрование сообщения.

Боб(Алиса), с помощью того же ключа , расшифровывает шифротекст .

В настоящее время симметричные шифры - это:

1.2 Симметричное шифрование

Блочные шифры. Обрабатывают информацию блоками определённой длины (обычно 64, 128 бит), применяя к блоку ключ в установленном порядке, как правило, несколькими циклами перемешивания и подстановки, называемыми раундами. Результатом повторения раундов является лавинный эффект - нарастающая потеря соответствия битов между блоками открытых и зашифрованных данных.

Поточные шифры, в которых шифрование проводится над каждым битом либо байтом исходного (открытого) текста с использованием гаммирования. Поточный шифр может быть легко создан на основе блочного (например, ГОСТ 28147-89 в режиме гаммирования), запущенного в специальном режиме.

Большинство симметричных шифров используют сложную комбинацию большого количества подстановок и перестановок. Многие такие шифры исполняются в несколько (иногда до 80) проходов, используя на каждом проходе «ключ прохода». Множество «ключей прохода» для всех проходов называется «расписанием ключей» (key schedule). Как правило, оно создается из ключа выполнением над ним неких операций, в том числе перестановок и подстановок.

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

Операция перестановки перемешивает биты сообщения по некоему закону. В аппаратных реализациях она тривиально реализуется как перепутывание проводников. Именно операции перестановки дают возможность достижения «эффекта лавины». Операция перестановки линейна - f(a) xor f(b) == f(a xor b)

Операции подстановки выполняются как замена значения некоей части сообщения (часто в 4, 6 или 8 бит) на стандартное, жестко встроенное в алгоритм иное число путем обращения к константному массиву. Операция подстановки привносит в алгоритм нелинейность.

Зачастую стойкость алгоритма, особенно к дифференциальному криптоанализу, зависит от выбора значений в таблицах подстановки (S-блоках). Как минимум считается нежелательным наличие неподвижных элементов S(x) = x, а также отсутствие влияния какого-то бита входного байта на какой-то бит результата - то есть случаи, когда бит результата одинаков для всех пар входных слов, отличающихся только в данном бите.

На рисунке 1 представлены различные виды ключей.

Рис 1. Виды ключей

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

1.3 Асимметричное шифрование (с открытым ключом)

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

Данная схема решает проблему симметричных схем, связанную с начальной передачей ключа другой стороне. Если в симметричных схемах злоумышленник перехватит ключ, то он сможет как «слушать», так и вносить правки в передаваемую информацию. В асимметричных системах другой стороне передается открытый ключ, который позволяет шифровать, но не расшифровывать информацию. Таким образом, решается проблема симметричных систем, связанная с синхронизацией ключей. Первыми исследователями, которые изобрели и раскрыли понятие шифрования с открытым кодом, были Уитфилд Диффи и Мартин Хеллман из Стэнфордского университета и Ральф Меркле из Калифорнийского университета в Беркли. В 1976 году их работа «Новые направления в современной криптографии» открыла новую область в криптографии, теперь известную как криптография с открытым ключом.

Схема реализации

Задача. Есть два собеседника -- Алиса и Боб, Алиса хочет передавать Бобу конфиденциальную информацию.

Генерация ключевой пары.

Боб выбирает алгоритм и пару открытый, закрытый ключи -- и посылает открытый ключ Алисе по открытому каналу.

Шифрование и передача сообщения.

Алиса шифрует информацию с использованием открытого ключа Боба



И передает Бобу полученный шифротекст .

Расшифрование сообщения.

Боб, с помощью закрытого ключа , расшифровывает шифротекст .

. Если необходимо наладить канал связи в обе стороны, то первые две операции необходимо проделать на обеих сторонах, таким образом, каждый будет знать свои закрытый, открытый ключи и открытый ключ собеседника. Закрытый ключ каждой стороны не передается по незащищенному каналу, тем самым оставаясь в секретности.



2. Шифр Цезаря

Шифр Цезаря, также известный как шифр сдвига, код Цезаря или сдвиг Цезаря -- один из самых простых и наиболее широко известных методов шифрования.

Шифр Цезаря -- это вид шифра подстановки, в котором каждый символ в открытом тексте заменяется символом, находящимся на некотором постоянном числе позиций левее или правее него в алфавите. Например, в шифре со сдвигом вправо на 3, А была бы заменена на Г, Б станет Д, и так далее.

Шифр назван в честь римского императора Гая Юлия Цезаря, использовавшего его для секретной переписки со своими генералами.

Шаг шифрования, выполняемый шифром Цезаря, часто включается как часть более сложных схем, таких как шифр Виженера, и все ещё имеет современное приложение в системе ROT13. Как и все моноалфавитные шифры, шифр Цезаря легко взламывается и не имеет практически никакого применения на практике.

Если сопоставить каждому символу алфавита его порядковый номер (нумеруя с 0), то шифрование и дешифрование можно выразить формулами модульной арифметики:

где -- символ открытого текста, -- символ шифрованного текста, -- мощность алфавита, а -- ключ.

С точки зрения математики шифр Цезаря является частным случаем аффинного шифра.

Шифр Цезаря называют в честь Юлия Цезаря, который согласно «Жизни двенадцати цезарей» Светония использовал его со сдвигом 3, чтобы защищать военные сообщения. Хотя Цезарь был первым зафиксированным человеком, использующим эту схему, другие шифры подстановки, как известно, использовались и ранее.

Есть доказательства, что Юлий Цезарь использовал также и более сложные схемы.

Неизвестно, насколько эффективным шифр Цезаря был в то время, но, вероятно, он был разумно безопасен, не в последнюю очередь благодаря тому, что большинство врагов Цезаря были неграмотными, и многие предполагали, что сообщения были написаны на неизвестном иностранном языке. Нет никаких свидетельств того времени касательно методов взлома простых шифров подстановки. Самые ранние сохранившиеся записи о частотном анализе -- это работы Ал-Кинди 9-го века об открытии частотного анализа.

2.1 Skipjack

Секретный в прошлом блочный алгоритм, который ассоциируется с микросхемой Clipper (описание стало открытым в июне 1989 года). Алгоритм представляет собой альтернативу решениям, предлагаемым в алгоритмах IDEA и Safer (развитие идей DES, Lucifer и Blowfish). Блок исходных данных также как и в idea разбиваются на четыре группы. Алгоритм легко реализуется на обычной ЭВМ. Skipjack включает в себя 32 цикла шифрования. Эти циклы имеют две разновидности (А и В). Цикл А выполняет следующие операции.

Первая группа бит исходного текста подвергается шифрованию с использованием G-перестановок (четырех цикличный шифр Файстела - специальный класс блочных шифров, где зашифрованный текст получается из исходного путем многократного использования одного и того же преобразования, напоминает шифр DES. Исходный текст разделяется на две части. Функция преобразования f и ключ используются для преобразования одной из половин а результат объединяется со второй частью исходного кода с помощью операции исключающее ИЛИ. После этого части меняются местами и процедура повторяется и т.д.). Для полученного результата и номера цикла (RN = 1-32) и четвертой группы исходного текста (W4) выполняется операция XOR. После этого производится перенос: W1 -> W2; W2 -> W3; W3 -> W4; W4 -> W1.

Цикл В осуществляет следующие преобразования.

Для второй группы бит исходного текста (W2) выполняется операция XOR с номером цикла и первой группой бит исходного текста (W2 = (W2 XOR RN) XOR W1). Затем первая группа блока (W1) подвергается шифрованию с использованием G-перестановок. После этого производится перенос данных: W1 -> W2; W2 -> W3; W3 -> W4; W4 -> W1.

Последовательность выполнения алгоритма Skipjack предполагает выполнение 8 циклов типа А, 8 циклов В, 6 циклов А и 8 циклов В.

Рис. 2. Блок-схема алгоритма шифрования Skipjack



G-перестановки включают в себя разделение группы из 16 бит на две подгруппы по 8 бит. Подобно DES левая половина кода не изменяется в процессе реализации цикла шифрования, а используется в качестве входного параметра F-функции, для результата которой и правой части кода выполняется операция XOR. В отличии от DES половины кода меняются местами лишь после завершающего цикла.

F-функция G-перестановок достаточно проста: входные данные и субключ цикла объединяются операцией XOR, а результат заменяется кодом из таблицы просмотра (lookup-таблица - F). Субключи для G имеют длину 8 бит и являются первыми четырьмя байтами 80-битового исходного ключа. Первые 4 байта используются в первом цикле, следующие 4 - во втором, последние 2 байта вместе с первыми двумя - в третьем и т.д.

Первый цикл типа А отображен вместе со схемой реализации G-функции. Для следующих 7 циклов типа А G-функция отмечена квадратиком с буквой G. Цифрами (1-12) отмечен ввод данных для цикла с соответствующим номером. При реализации F-функции используется таблица (16*16) перестановок кодов 0-255.

В случае дешифровки циклы выполняются в обратном порядке. Аналогом цикла А при дешифровке является последовательность операций:

Для групп бит W1 и W2 и номера цикла выполняется операция XOR (циклы здесь нумеруются, начиная с 32 до 1). Затем W2 подвергается обратной G-перестановке, после чего выполняется перенос: W1 -> W4; W2 -> W1; W3 -> W2; W4 -> W3. Аналог цикла типа В при дешифровке включает в себя следующие операции:

Группа бит W2 подвергается обратной G-перестановке. W3 объединяется с номером цикла и группой бит W2 с помощью операции исключающее ИЛИ. После чего производится перемещение: W1 -> W4; W2 -> W1; W3 -> W2; W4 -> W3.



2.2 Классификация методов шифрования

В качестве основного критерия классификации криптографических алгоритмов будем использовать тип выполняемого над исходным текстом преобразования. Классификация по этому критерию представлена на рис. 3.

Рис. 3. Общая классификация криптографических алгоритмов

Тайнопись предполагает, что отправитель и получатель производят над сообщением преобразования, известные только им двоим. Сторонним лицам неизвестны выполняемые алгоритмом изменения над открытым текстом, что и является гарантией нераскрываемости данных на этапе анализа.

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

Криптосистемы с ключом делятся на симметричные и асимметричные системы шифрования. Модель симметричной системы шифрования представлена на рис. 4.

Рис. 4. Обобщенная модель симметричной системы шифрования

Отличительной чертой симметричных алгоритмов шифрования является наличие одного ключа шифрования (k на рис. 2), который должен быть известен только отправителю и получателю сообщения. Отправитель на ключе k шифрует сообщение, получатель дешифрует полученный шифротекст ключом k. Криптоаналитик может перехватить шифротекст Y, передаваемый по открытым каналам связи, но, так как он не знает ключа, задача вскрытия шифротекста является очень трудоемкой. Принципиальным моментом является необходимость наличия секретного канала связи между получателем и отправителем для передачи ключа шифрования без возможности его перехвата криптоаналитиком.

Асимметричная система шифрования работает по схеме, представленной на рис. 5.



Рис. 5. Обобщенная модель асимметричной системы шифрования

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

В зависимости от размера блока шифруемой информации криптоалгоритмы делятся на блочные и поточные шифры. Единицей кодирования в потоковых шифрах является один бит. Результат кодирования не зависит от прошедшего ранее входного потока. Схема применяется в системах передачи потоков информации, то есть в тех случаях, когда передача информации начинается и заканчивается в произвольные моменты времени и может случайно прерываться. Для блочных шифров единицей кодирования является блок из нескольких байтов. Результат кодирования зависит от всех исходных байтов этого блока. Схема применяется при пакетной передаче информации и кодировании файлов.

Еще одним критерием классификации криптоалгоритмов является тип выполняемых преобразований над блоками открытого текста. По этому критерию криптоалгоритмы разделяют на подстановочные и перестановочные. В перестановочных шифрах блоки информации не изменяются сами по себе, но изменяется их порядок следования, что делает информацию недоступной стороннему наблюдателю. Подстановочные шифры изменяют сами блоки информации по определенным законам.

Деление криптоалгоритмов на моноалфавитные и многоалфавитные характерно для подстановочных шифров:

Моноалфавитные криптоалгоритмы заменяют блок входного текста (символ входного алфавита) на один и тот же блок шифротекта (символ выходного алфавита). В многоалфавитных шифрах одному и тому же блоку входного текста могут соответствовать разные блоки шифротекста, что существенно затрудняет криптоанализ. По степени секретности криптоалгоритмы делятся на абсолютно стойкие и практически стойкие. Абсолютно стойкие шифры невозможно вскрыть. На практике этого можно добиться, только если размер используемого ключа шифрования превышает размер кодируемого сообщения и при этом ключ используется однократно. Практически стойким называется шифр, для которого не существует более эффективного способа взлома, кроме как полным перебором всех возможных ключей шифрования.

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

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



3. Выбор языка программирования

Рождение новых подходов к программированию обуславливается прежде всего стремлением к повышению производительности труда программиста. Разработчики нововведений стремятся облегчить разработку крупномасштабных программных проектов, в которых задействовано большое число программистов, прежде всего за счет более удобных средств расчленения задачи на отдельные составляющие, а также за счет более продуктивных методов защиты от ошибок в программах - их верификации, ужесточения синтаксических требований и т. д. Наиболее важными нововведениями последних лет стали объектное и событийное программирование, а также развивающийся в последнее время визуальный подход к программированию.

Последняя на сегодняшний день версия - 2009. Delphi является мощным и универсальным средством разработки приложений, RAD-оболочкой. Ее вместе с библиотекой VCL, на которой оболочка основана и написана, можно назвать действительно революционной. Сравнение с C++ Builder 4 показывает, что производительность Pascal-кода, сгенерированного Delphi, всего на 4-5% меньше, чем кода C++.

Возможности языка практически не ограничены. Конечно, Object Pascal накладывает определенные ограничения, но для тех вещей, для которых ее писали, Delphi подходит практически оптимально. Из понравившихся (но, разумеется, нестандартных) "улучшений", внесенных Borland в Object Pascal, хотелось бы выделить свойства (properties) и перегружаемость процедур и функций (overloading).

Определенные неудобства при работе с низкоуровневыми функциями API может вызвать то, что стандартным языком для API все же является С, и именно на нем пишутся все новые Software Development Kit (SDK) и заголовочные файлы к ним. Это ни в коем случае не означает, что вы не сможете работать с новыми SDK, просто вам придется написать несложный (но, возможно, объемный) код на Pascal, в котором определить интерфейсы данного SDK. Не поленитесь, однако, поискать на серверах, посвященных Delphi.

3.1 Достоинства языка программирования

Простота, скорость и эффективность Delphi объясняют ее популярность. Delphi имеет один из самых быстрых компиляторов, порождающий, тем не менее, весьма и весьма неплохой объектный код. Есть и другие достоинства: простота изучения Object Pascal; облегчающие жизнь нововведения - вроде свойств (properties); программы, написанные на Delphi, не требуется снабжать дополнительными библиотеками (в отличие от связки C++/MFC). В самом деле, VCL предоставляет удобный, легко расширяемый объектно-ориентированный интерфейс к Windows, что ни в коей мере не мешает программисту опускаться в самые глубины Windows API. Создателям оригинальных компонентов это приходится делать довольно часто, в отличие от "просто программистов". Как было сказано выше, модель программирования в Delphi - компонентная, что позволяет пользоваться компонентами, написанными другими разработчиками, даже не имея их исходного кода и уж подавно не изучая его. В Интернете есть огромное количество компонентов, значительная часть которых распространяется бесплатно. Применение компонентной модели приводит к тому, что довольно многое в поведении объектов программировать не нужно вообще, и многое, на что в других средах ушли бы недели, можно сделать за часы или даже минуты. Оно и понятно - это ведь RAD-среда. К достоинствам можно отнести очень быстрый браузер классов и мгновенный вывод подсказки автозавершения кода (code completion). Если кратко - может все. Конечно, Object Pascal накладывает определенные ограничения, но для тех вещей, для которых ее писали, Delphi подходит практически оптимально. Из понравившихся (но, разумеется, нестандартных) "улучшений", внесенных Borland в Object Pascal, хотелось бы выделить свойства (properties) и перегружаемость процедур и функций (overloading). Определенные неудобства при работе с низкоуровневыми функциями API может вызвать то, что стандартным языком для API все же является С, и именно на нем пишутся все новые Software Development Kit (SDK) и заголовочные файлы к ним. Это ни в коем случае не означает, что вы не сможете работать с новыми SDK, просто вам придется написать несложный (но, возможно, объемный) код на Pascal, в котором определить интерфейсы данного SDK. Не поленитесь, однако, поискать на серверах, посвященных Delphi. Очень может быть, что эту работу кто-то уже сделал.

3.2 Недостатки языка программирования

Их мало, но они есть. Главный, на мой взгляд, недостаток (и одновременно достоинство) - статическое присоединение (linking) библиотеки VCL и компонентов к исполняемому файлу. Справедливости ради надо сказать, что VCL можно линковать и динамически, но тогда с каждым своим приложением вам придется распространять еще и VCL, а это более 3 Мбайт. Однако если не увлекаться интерфейсными "наворотами" и использовать в программе минимально необходимое число компонентов, то исполняемый файл будет невелик. Другой недостаток (и опять же достоинство) состоит в том, что в используемой в Delphi парадигме форм (Forms) вся информация о форме, включая свойства, настройки компонентов, значения по умолчанию, хранится в exe-файле, причем не оптимальным образом. Анализ исходного кода VCL показывает, что при создании формы фактически происходит чуть ли не синтаксический разбор данных инициализации, что не может ее не замедлять. Третий недостаток, который кто-нибудь тоже может назвать достоинством, - это Object Pascal. Несмотря на простоту, эффективность и легкость в изучении, ему не хватает очень многих мощных средств C++. Мне, например, не достает шаблонов, перегрузки операторов и объектной модели, похожей на объектную модель C++ . Разочаровала Delphi и малым числом параметров оптимизации кода. Кроме того, заметна тенденция к "разрастанию" exe-файлов, генерируемых Delphi. Так, большинство небольших проектов, разработанных в Delphi 4, при перекомпиляции в Delphi 5 "растолстели" на 40-70 Кбайт, при этом, разумеется, не обретя новой функциональности.



4. Метод шифрования с открытым ключом

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

Начало асимметричным шифрам было положено в работе «Новые направления в современной криптографии» Уитфилда Диффи и Мартина Хеллмана, опубликованной в 1976 г. Находясь под влиянием работы Ральфа Меркле (Ralph Merkle) о распространении открытого ключа, они предложили метод получения секретных ключей для симметричного шифрования, используя открытый канал. В 2002 г. Хеллман предложил называть данный алгоритм «Диффи - Хеллмана - Меркле», признавая вклад Меркле в изобретение криптографии с открытым ключом.

Хотя работа Диффи-Хеллмана создала большой теоретический задел для открытой криптографии, первой реальной криптосистемой с открытым ключом считают алгоритм RSA (названный по имени авторов - Рон Ривест (Ronald Linn Rivest), Ади Шамир (Adi Shamir) и Леонард Адлеман (Leonard Adleman)).

Справедливости ради следует отметить, что в декабре 1997 г. была обнародована информация, согласно которой британский математик Клиффорд Кокс (Clifford Cocks), работавший в центре правительственной связи (GCHQ) Великобритании, описал систему, аналогичную RSA, в 1973 г., а несколькими месяцами позже в 1974 г. Малькольм Вильямсон изобрел математический алгоритм, аналогичный алгоритму Диффи - Хеллмана - Меркле.

Суть шифрования с открытым ключом заключается в том, что для шифрования данных используется один ключ, а для расшифрования другой (поэтому такие системы часто называют ассиметричными).

Основная предпосылка, которая привела к появлению шифрования с открытым ключом, заключалось в том, что отправитель сообщения (тот, кто зашифровывает сообщение), не обязательно должен быть способен его расшифровывать. Т.е. даже имея исходное сообщение, ключ, с помощью которого оно шифровалось, и зная алгоритм шифрования, он не может расшифровать закрытое сообщение без знания ключа расшифрования.

Первый ключ, которым шифруется исходное сообщение, называется открытым и может быть опубликован для использования всеми пользователями системы. Расшифрование с помощью этого ключа невозможно. Второй ключ, с помощью которого дешифруется сообщение, называется секретным (закрытым) и должен быть известен только законному получателю закрытого сообщения.

Алгоритмы шифрования с открытым ключом используют так называемые необратимые или односторонние функции. Эти функции обладают следующим свойством: при заданном значении аргумента х относительно просто вычислить значение функцииf(x), однако, если известно значение функции y = f(x), то нет простого пути для вычисления значения аргумента x. Например, функция SIN. Зная x, легко найти значение SIN(x) (например, x = , тогда SIN() = 0). Однако, если SIN(x) = 0, однозначно определить х нельзя, т.к. в этом случае х может быть любым числом, определяемым по формуле i * , где i - целое число.

Однако не всякая необратимая функция годится для использования в реальных криптосистемах. В их числе и функция SIN. Следует также отметить, что в самом определении необратимости функции присутствует неопределенность. Под необратимостью понимается не теоретическая необратимость, а практическая невозможность вычислить обратное значение, используя современные вычислительные средства за обозримый интервал времени.

Поэтому чтобы гарантировать надежную защиту информации, к криптосистемам с открытым ключом предъявляются два важных и очевидных требования.

1. Преобразование исходного текста должно быть условно ф

2. Определение закрытого ключа на основе открытого также должно быть невозможным на современном технологическом уровне.

Все предлагаемые сегодня криптосистемы с открытым ключом опираются на один из следующих типов односторонних преобразований.

1. Разложение больших чисел на простые множители (алгоритм RSA).

2. Вычисление дискретного логарифма или дискретное возведение в степень (алгоритм Диффи-Хелмана-Меркле, схема Эль-Гамаля).

3. Задача об укладке рюкзака (ранца) (авторы Хелман и Меркл).

4. Вычисление корней алгебраических уравнений.

5. Использование конечных автоматов (автор Тао Ренжи).

6. Использование кодовых конструкций.

7. Использование свойств эллиптических кривых.

4.1 Алгоритм RSA

Стойкость RSA основывается на большой вычислительной сложности известных алгоритмов разложения числа на простые сомножители (делители). Например, легко найти произведение двух простых чисел 7 и 13 даже в уме - 91. Попробуйте в уме найти два простых числа, произведение которых равно 323 (числа 17 и 19). Конечно, для современной вычислительной техники найти два простых числа, произведение которых равно 323, не проблема. Поэтому для надежного шифрования алгоритмом RSA, как правило, выбираются простые числа, количество двоичных разрядов которых равно нескольким сотням.

В августе 1977 г. знаменитый американский писатель и популяризатор науки Мартин Гарднер озаглавил свою колонку по занимательной математике в журнале Scientific American так: «Новый вид шифра, на расшифровку которого потребуются миллионы лет». После объяснения принципа системы шифрования с открытым ключом он показал само зашифрованное сообщение и открытый ключ N, используемый в этом шифре:

N = 114 381 625 757 888 867 669 235 779 976 146 612 010 218 296 721 242 362 562 561 842 935 706 935 245 733 897 830 597 123 563 958 705 058 989 075 147 599 290 026 879 543 541.

Гарднер призвал читателей попробовать расшифровать сообщение, используя предоставленную информацию, и даже дал подсказку: для решения необходимо разложить число N на простые множители р и q. Более того, Гарднер назначил приз в размере $100 (приличная сумма на тот момент) тому, кто первым получит правильный ответ. Каждый, кто захочет побольше узнать о шифре, писал Гарднер, может обратиться к создателям шифра -- Рону Ривесту, Ади Шамиру и Лену Ад-леману из Лаборатории информации Массачусетского технологического института.

Правильный ответ был получен лишь через 17 лет. Он стал результатом сотрудничества более чем 600 человек. Ключами оказались р = 32 769 132 993 266 709 549 961 988 190 834 461 413 177 642 967 992 942 539 798 288 533 и q = 3 490 529 510 847 650 949 147 849 619 903 898 133 417 764 638 493 387 843 990 820 577, а зашифрованная фраза звучала так: «Волшебные слова -- это брезгливый ягнятник».

Авторы RSA поддерживали идею её активного распространения. В свою очередь, Агентство национальной безопасности (США), опасаясь использования этого алгоритма в негосударственных структурах, на протяжении нескольких лет безуспешно требовало прекращения распространения системы. Ситуация порой доходила до абсурда. Например, когда программист Адам Бек (Adam Back) описал на языке Perl алгоритм RSA, состоящий из пяти строк, правительство США запретило распространение этой программы за пределами страны. Люди, недовольные подобным ограничением, в знак протеста напечатали текст этой программы на своих футболках.

Первым этапом любого асимметричного алгоритма является создание получателем шифрограмм пары ключей: открытого и секретного. Для алгоритма RSA этап создания ключей состоит из следующих операций.

Таблица 1. Процедура создания ключей

Примечания.

1) Простое число -- натуральное число, большее единицы и не имеющее других натуральных делителей, кроме самого себя и единицы.

2) Результат расчета функция Эйлера (n) равен количеству положительных чисел, не превосходящих n и взаимно простым с n. Некоторые случаи и способы расчета функции Эйлера приведены в следующей таблице.



Таблица 2. Способы расчета функции Эйлера

3) Взаимно простые числа - числа, не имеющие общих делителей, кроме 1, т.е. наибольший общий делитель которых равен 1.

4) Обратными числами по модулю m называются такие числа n и n^-1, для которых справедливо выражение (n * n^-1) mod m = 1. Для вычисления обратных чисел по модулю обычно используется расширенный алгоритм Евклида. В безмодульной математике обратное число n^-1 (обратное значение, обратная величина) - число, на которое надо умножить данное число n, чтобы получить единицу (n * n^-1 = 1). Пара чисел, произведение которых равно единице, называются взаимно обратными. Например: 5 и 1/5, -6/7 и -7/6.

Процедуры шифрования и дешифрования выполняются по следующим формулам

C = Т^e mod n, (1)

Т = C^d mod n. (2)

где Т, C - числовые эквиваленты символов открытого и шифрованного сообщения.

Пример шифрования по алгоритму RSA приведен в следующей таблице. Коды букв соответствуют их положению в русском алфавите (начиная с 1).

Таблица 3. Пример шифрования по алгоритму RSA

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

Алгоритм RSA требует много машинного времени и очень мощных процессоров. До 1980-х гг. только правительства, армия и крупные предприятия имели достаточно мощные компьютеры для работы с RSA. В результате у них была фактически монополия на эффективное шифрование. Летом 1991 г. Филипп Циммерман, американский физик и борец за сохранение конфиденциальности, предложил бесплатную систему шифрования PGP (англ. Pretty Good Privacy -- «достаточно хорошая степень конфиденциальности»), алгоритм которой мог работать на домашних компьютерах. PGP использует классическое симметричное шифрование, что и обеспечивает ей большую скорость на домашних компьютерах, но она шифрует ключи по асимметричному алгоритму RSA.

Циммерман объяснил причины этой меры в открытом письме, которое заслуживает быть процитированным здесь, по крайней мере, частично из-за пророческого описания того, как мы живем, работаем и общаемся два десятилетия спустя.

«Это личное. Это конфиденциальное. И это только ваше дело и ничье другое. Вы можете планировать политическую кампанию, обсуждать ваши налоги или иметь тайную любовную связь. Или вы можете заниматься тем, что вам не кажется незаконным, хотя таковым является. Что бы то ни было, вы не хотите, чтобы ваши личные электронные письма или конфиденциальные документы были прочитаны кем-то еще. Нет ничего плохого в том, чтобы охранять вашу частную жизнь. Частная жизнь неприкосновенна, как Конституция...

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

Спецслужбы обладают лучшими криптографическими технологиями. Как и торговцы оружием и наркотиками. Как и военные подрядчики, нефтяные компании и другие корпорации-гиганты. Но обычные люди и общественные организации практически не имеют недорогих защитных криптографических технологий с открытым ключом. До сих пор не имели.

PGP дает людям возможность самим защищать свою конфиденциальность. Сегодня существует растущая социальная потребность в этом. Вот почему я написал PGP».

В заключении следует отметить стойкость данного алгоритма. В 2003 г. Ади Шамир и Эран Тромер разработали схему устройства TWIRL, которое при стоимости $ 10 000 может дешифровать 512-битный ключ за 10 минут, а при стоимости $ 10 000 000 - 1024-битный ключ меньше, чем за год. В настоящее время Лаборатория RSA рекомендует использовать ключи (параметр n) размером 2048 битов.



4.2 Алгоритм на основе задачи об укладке ранца

В 1978 г. Меркль и Хеллман предложили использовать задача об укладке ранца (рюкзака) для асимметричного шифрования . Она относится к классу NP-полных задач и формулируется следующим образом. Дано множество предметов различного веса. Спрашивается, можно ли положить некоторые из этих предметов в ранец так, чтобы его вес стал равен определенному значению? Более формально задача формулируется так: дан набор значений M₁, M₂, ..., М_n и суммарное значение S; требуется вычислить значения b_i такие что

S = b₁М₁ + b₂М₂ + ... + b_nМ_n, (3)

где n - количество предметов;

b_i - бинарный множитель. Значение b_i = 1 означает, что предмет i кладут в рюкзак, b_i = 0 - не кладут.

Например, веса предметов имеют значения 1, 5, 6, 11, 14, 20, 32 и 43. При этом можно упаковать рюкзак так, чтобы его вес стал равен 22, использовав предметы весом 5, 6 и 11. Невозможно упаковать рюкзак так, чтобы его вес стал равен 24.

В основе алгоритма, предложенного Мерклом и Хеллманом, лежит идея шифрования сообщения на основе решения серии задач укладки ранца. Предметы из кучи выбираются с помощью блока открытого текста, длина которого (в битах) равна количеству предметов в куче. При этом биты открытого текста соответствуют значениям b, a текст является полученным суммарным весом. Пример шифрограммы, полученной с помощью задачи об укладке ранца, показан в следующей таблице.



Таблица 4. Пример шифрования на основе задачи об укладке ранца

Суть использования данного подхода для шифрования состоит в том, что на самом деле существуют две различные задачи укладки ранца - одна из них решается легко и характеризуется линейным ростом трудоемкости, а другая, как принято считать, нет. Легкий для укладки ранец можно превратить в трудный. Раз так, то можно применить в качестве открытого ключа трудный для укладки ранец, который легко использовать для шифрования, но невозможно - для дешифрования. А в качестве закрытого ключа применить легкий для укладки ранец, который предоставляет простой способ дешифрования сообщения.

В качестве закрытого ключа (легкого для укладки ранца) используется сверхвозрастающая последовательность. Сверхвозрастающей называется последовательность, в которой каждый последующий член больше суммы всех предыдущих. Например, последовательность {2, 3, 6, 13, 27, 52, 105, 210} является сверхвозрастающей, а {1, 3, 4, 9, 15, 25, 48, 76} - нет.

Решение для сверхвозрастающего ранца найти легко. В качестве текущего выбирается полный вес, который надо получить, и сравнивается с весом самого тяжелого предмета в ранце. Если текущий вес меньше веса данного предмета, то его в рюкзак не кладут, в противном случае его укладывают в рюкзак. Уменьшают текущий вес на вес положенного предмета и переходят к следующему по весу предмету в последовательности. Шаги повторяются до тех пор, пока процесс не закончится. Если текущий вес уменьшится до нуля, то решение найдено. В противном случае, нет.

Например, пусть полный вес рюкзака равен 270, а последовательность весов предметов равна {2, 3, 6, 13, 27, 52, 105, 210}. Самый большой вес - 210. Он меньше 270, поэтому предмет весом 210 кладут в рюкзак. Вычитают 210 из 270 и получают 60. Следующий наибольший вес последовательности равен 105. Он больше 60, поэтому предмет весом 105 в рюкзак не кладут. Следующий самый тяжелый предмет имеет вес 52. Он меньше 60, поэтому предмет весом 52 также кладут в рюкзак. Аналогично проходят процедуру укладки в рюкзак предметы весом 6 и 2. В результате полный вес уменьшится до 0. Если бы этот рюкзак был бы использован для дешифрования, то открытый текст, полученный из значения шифртекста 270, был бы равен 10100101.

Открытый ключ представляет собой не сверхвозрастающую (нормальную) последовательность. Он формируется на основе закрытого ключа и, как принято считать, не позволяет легко решить задачу об укладке ранца. Для его получения все значения закрытого ключа умножаются на число n по модулю m. Значение модуля m должно быть больше суммы всех чисел последовательности, например, 420 (2+3+6+13+27+52+105+210=418). Множитель n должен быть взаимно простым числом с модулем m, например, 31. Результат построения нормальной последовательности (открытого ключа) представлен в следующей таблице.

Таблица 5. Пример получения открытого ключа

Для шифрования сообщение сначала разбивается на блоки, по размерам равные числу элементов последовательности в рюкзаке. Затем, считая, что единица указывает на присутствие элемента последовательности в рюкзаке, а ноль -- на его отсутствие, вычисляются полные веса рюкзаков - по одному рюкзаку для каждого блока сообщения.

В качестве примера возьмем открытое сообщение «АБРАМОВ», символы которого представим в бинарном виде в соответствии с таблицей кодов символов Windows 1251. Результат шифрования с помощью открытого ключа {62, 93, 186, 403, 417, 352, 315, 210} представлен в следующей таблице.

Таблица 6. Пример шифрования

Для расшифрования сообщения получатель должен сначала определить обратное число n^-1, такое что (n * n^-1) mod m = 1. После определения обратного числа каждое значение шифрограммы умножается на n^-1 по модулю m и с помощью закрытого ключа определяются биты открытого текста.

В нашем примере сверхвозрастающая последовательность равна {2, 3, 6, 13, 27, 52, 105, 210}, m = 420, n = 31. Значение n^-1 равно 271 (31*271 mod 420 = 1).

Таблица 7. Пример расшифрования

В своей работе авторы рекомендовали брать длину ключа, равную 100 (количество элементов последовательности). В заключении следует отметить, что задача вскрытия данного способа шифрования успешно решена Шамиром и Циппелом в 1982 г.

4.3 Вероятностное шифрование

Вероятностное шифрование является разновидностью криптосистем с открытым ключом (авторы - Шафи Гольдвассер (Shafi Goldwasser) и Сильвио Микали (Silvio Micali)). Данный вид шифрования относят к допускающим неоднозначное вскрытие. Основной целью вероятностного шифрования является устранение утечки информации в криптографии с открытым ключом. Поскольку криптоаналитик всегда может зашифровать случайные сообщения открытым ключом, он может получить некоторую информацию. При условии, что у него есть шифртекст С (С = Е_k1(T)) и он пытается получить открытый текст T, он может выбрать случайное сообщение T' и зашифровать: С' = Е_k1(T'). Если С' = С, то он угадал правильный открытый текст. В противном случае он делает следующую попытку.