Криптографические хэш функции реферат
Обновлено: 02.07.2024
Хеширование есть разбиение множества ключей (однозначно характеризующих элементы хранения и представленных, как правило, в виде текстовых строк или чисел) на непересекающиеся подмножества (наборы элементов), обладающие определенным свойством. Это свойство описывается функцией хеширования, или хеш-функцией, и называется хеш-адресом. Решение обратной задачи возложено на хеш-структуры (хеш-таблицы): по хеш-адресу они обеспечивают быстрый доступ к нужному элементу. В идеале для задач поиска хеш-адрес должен быть уникальным, чтобы за одно обращение получить доступ к элементу, характеризуемому заданным ключом (идеальная хеш-функция). Однако, на практике идеал приходится заменять компромиссом и исходить из того, что получающиеся наборы с одинаковым хеш-адресом содержат более одного элемента.
Как отмечает Дональд Кнут [3], идея хеширования впервые была высказана Г.П. Ланом при создании внутреннего меморандума IBM в январе 1953 г. с предложением использовать для разрешения коллизий хеш-адресов метод цепочек. Примерно в это же время другой сотрудник IBM – Жини Амдал – высказала идею использования открытую линейную адресацию. В открытой печати хеширование впервые было описано Арнольдом Думи (1956), указавшим, что в качестве хеш-адреса удобно использовать остаток от деления на простое число. А. Думи описывал метод цепочек для разрешения коллизий, но не говорил об открытой адресации. Подход к хешированию, отличный от метода цепочек, был предложен А.П. Ершовым (1957, [2]), который разработал и описал метод линейной открытой адресации. Среди других исследований можно отметить работу Петерсона (1957, [4]). В ней реализовывался класс методов с открытой адресацией при работе с большими файлами. Петерсон определил открытую адресацию в общем случае, проанализировал характеристики равномерного хеширования, глубоко изучил статистику использования линейной адресации на различных задачах. В 1963 г. Вернер Букхольц [6] опубликовал наиболее основательное исследование хеш-функций.
Разные люди понимают под шифрованием разные вещи. Дети играют в игрушечные шифры и секретные языки. Это, однако, не имеет ничего общего с настоящей криптографией. Настоящая криптография ( strong cryptography ) должна обеспечивать такой уровень секретности, чтобы можно было надежно защитить критическую информацию от расшифровки крупными организациями --- такими как мафия, транснациональные корпорации и крупные государства. Настоящая криптография в прошлом использовалась лишь в военных целях. Однако сейчас, с становлением информационного общества, она становится центральным инструментом для обеспечения конфиденциальности.
По мере образования информационного общества, крупным государствам становятся доступны технологические средства тотального надзора за миллионами людей. Поэтому криптография становится одним из основных инструментов обеспечивающих конфиденциальность, доверие, авторизацию, электронные платежи, корпоративную безопасность и бесчисленное множество других важных вещей.
Криптография не является более придумкой военных, с которой не стоит связываться. Настала пора снять с криптографии покровы таинственности и использовать все ее возможности на пользу современному обществу. Широкое распространение криптографии является одним из немногих способов защитить человека от ситуации, когда он вдруг обнаруживает, что живет в тоталитарном государстве, которое может контролировать каждый его шаг.
Базовая терминология
Алгоритмы с использованием ключа делятся на два класса: симметричные (или алгоритмы секретным ключом) и асиметричные (или алгоритмы с открытым ключом). Разница в том, что симметричные алгоритмы используют один и тот же ключ для шифрования и для дешифрования (или же ключ для дешифровки просто вычисляется по ключу шифровки). В то время как асимметричные алгоритмы используют разные ключи, и ключ для дешифровки не может быть вычислен по ключу шифровки.
Смметричные алгоритмы подразделяют на потоковые шифры и блочные шифры . Потоковые позволяют шифровать информацию побитово, в то время как блочные работают с некоторым набором бит данных (обычно размер блока составляет 64 бита) и шифруют этот набор как единое целое. Начальное представление о них можно получить в статье об алгоритмах.
Современные алгоритмы шифровки/дешифровки достаточно сложны и их невозможно проводить вручную. Настоящие криптографические алгоритмы разработаны для использования компьютерами или специальными аппаратными устройствами. В большинстве приложений криптография производится программным обеспечением и имеется множество доступных криптографических пакетов.
Многие качественные криптографические алгоритмы доступны широко - в книжном магазине, библиотеке, патентном бюро или в Интернет. К широко известным симметричным алгоритмам относятся DES и IDEA, Наверное самым лучшим асимметричным алгоритмом является RSA. На страничке литературы приведен список хороших учебников по криптографии и смежным вопросам.
Цифровые подписи
Некоторые из асимметричных алгоритмов могут использоваться для генерирования цифровой подписи . Цифровой подписью называют блок данных, сгенерированный с использованием некоторого секретного ключа. При этом с помощью открытого ключа можно проверить, что данные были действительно сгенерированы с помощью этого секретного ключа. Алгоритм генерации цифровой подписи должен обеспечивать, чтобы было невозможно без секретного ключа создать подпись, которая при проверке окажется правильной.
Цифровые подписи также можно использовать для удостоверения ( сертификации --- to certify ) того, что документ принадлежит определенному лицу. Это делается так: открытый ключ и информация о том, кому он принадлежит подписываются стороной, которой доверяем. При этом доверять подписывающей стороне мы можем на основании того, что ее ключ был подписан третьей стороной. Таким образом возникает иерархия доверия. Очевидно, что некоторый ключ должен быть корнем иерархии (то есть ему мы доверяем не потому, что он кем-то подписан, а потому, что мы верим a-priori, что ему можно доверять). В централизованной инфраструктуре ключей имеется очень небольшое количество корневых ключей сети (например, облеченные полномочиями государственные агенства; их также называют сертификационными агенствами --- certification authorities ). В распределенной инфраструктуре нет необходимости иметь универсальные для всех корневые ключи, и каждая из сторон может доверять своему набору корневых ключей (скажем своему собственному ключу и ключам, ею подписанным). Эта концепция носит название сети доверия ( web of trust ) и реализована, например, в PGP.
Свободно доступны несколько методов создания и проверки цифровых подписей. Наиболее известным является алгоритм RSA.
Криптографические хэш-функции
Криптографические хэш-функции обычно производят значения длиной в 128 и более бит. Это число значительно больше, чем количество собщений, которые когда-либо будут существовать в мире.
Много хороших криптографических хэш-функций доступно бесплатно. Широко известные включают MD5 и SHA.
Криптографические генераторы случайных чисел
Криптографические генераторы случайных чисел производят случайные числа, которые используются в криптографических приложениях, например - для генерации ключей. Обычные генераторы случайных чисел, имеющиеся во многих языках программирования и программных средах, не подходят для нужд криптографии (они создавались с целью получить статистически случайное распределение, криптоаналитики могут предсказать поведение таких случайных генераторов).
В идеале случайные числа должны основываться на настоящем физическом источнике случайной информации, которую невозможно предсказать. Примеры таких источников включают шумящие полупроводниковые приборы, младшие биты оцифрованного звука, интервалы между прерываниями устройств или нажатиями клавиш. Полученный от физического источника шум затем "дистиллируется" криптографической хэш-функцией так, чтобы каждый бит зависел от каждого бита. Достаточно часто для хранения случайной информации используется довольно большой пул (несколько тысяч бит) и каждый бит пула делается зависимым от каждого бита шумовой информаци и каждого другого бита пула криптографически надежным ( strong ) способом.
Когда нет настоящего физического источника шума, приходится пользоваться псевдослучайными числами. Такая ситуация нежелательна, но часто возникает на компьютерах общего назначения. Всегда желательно получить некий шум окружения --- скажем от величины задержек в устройствах, цифры статистики использования ресурсов, сетевой статистики, прерываний от клавиатуры или чего-то иного. Задачей является получить данные, непредсказуемые для внешнего наблюдателя. Для достижения этого случайный пул должен содержать как минимум 128 бит настоящей энтропии.
Криптографические генераторы псевдослучайных чисел обычно используют большой пул (seed-значение), содержащий случайную информацию. Биты генерируется путем выборки из пула с возможным прогоном через криптографическую хэш-функцию, чтобы спрятать содержимое пула от внешнего наблюдателя. Когда требуется новая порция бит, пул перемешивается путем шифровки со случайным ключом (его можно взять из неиспользованной пока части пула) так, чтобы каждый бит пула зависел от каждого другого бита. Новый шум окружения должен добавляться к пулу перед перемешиваниям, дабы сделать предсказание новых значений пула еще более сложным.
Несмотря на то, что при аккуратном проектировании криптографически надежный генератор случайных чисел реализовать не так уж и трудно, этот вопрос часто упускают из вида. Таким образом, следует подчеркнуть важность криптографического генератора случайных чисел --- если он сделан плохо, он может легко стать самым уязвимым элементом системы.
Доступны несколько примеров криптографических генераторов случайных чисел.
Обеспечиваемая шифром степень защиты
Хорошие криптографические системы создаются таким образом, чтобы сделать их вскрытие как можно более трудным делом. Можно построить системы, которые на практике невозможно вскрыть (хотя доказать сей факт обычно нельзя). При этом не требуется очень больших усилий для реализации. Единственное, что требуется --- это аккуратность и базовые знания. Нет прощения разработчику, если он оставил возможность для вскрытия системы. Все механизмы, которые могут использоваться для взлома системы надо задокументировать и довести до сведения конечных пользователей.
Теоретически, любой шифровальный алгоритм с использованием ключа может быть вскрыт методом перебора всех значений ключа. Если ключ подбирается методом грубой силы ( brute force ), требуемая мощность компьютера растет экспоненциально с увеличением длины ключа. Ключ длиной в 32 бита требует 2^32 (около 10^9) шагов. Такая задача под силу любому дилетанту и решается на домашнем компьютере. Системы с 40-битным ключом (например, экспортный американский вариант алгоритма RC4) требуют 2^40 шагов --- такие компьютерные мощности имеются в большинстве университетов и даже в небольших компаниях. Системы с 56-битными ключами (DES) требуют для вскрытия заметных усилий, однако могут быть легко вскрыты с помощью специальной аппаратуры. Стоимость такой аппаратуры значительна, но доступна для мафии, крупных компаний и правительств. Ключи длиной 64 бита в настоящий момент, возможно, могут быть вскрыты крупными государствами и уже в ближайшие несколько лет будут доступны для вскрытия преступными организацими, крупными компаниями и небольшими государствами. Ключи длиной 80 бит могут в будущем стать уязвимыми. Ключи длиной 128 бит вероятно останутся недоступными для вскрытия методом грубой силы в обозримом будущем. Можно использовать и более длинные ключи. В пределе нетрудно добиться того, чтобы энергия, требуемая для вскрытия (считая, что на один шаг затрачивается минимальный квантовомеханический квант энергии) превзойдет массу солнца или вселенной.
Однако, длина ключа это еще не все. Многие шифры можно вскрыть и не перебирая всех возможных комбинаций. Вообще говоря, очень трудно придумать шифр, который нельзя было бы вскрыть другим более эффективным способом. Разработка собственных шифров может стать приятным занятием, но для реальных приложений использовать самодельные шифры не рекомендуется если вы не являетесь экспертом и не уверены на 100 процентов в том, что делаете.
Вообще говоря, следует держаться в стороне от неопубликованных или секретных алгоритмов. Часто разработчик такого алгоритма не уверен в его надежности, или же надежность зависит от секретности самого алгоритма. Вообще говоря, ни один алгоритм, секретность которого зависит от секретности самого алгоритма не явяется надежным. В частности, имея шифрующую программу, можно нанять прграммиста, который дизассемблирует ее и восстановит алгоритм методом обратной инженерии. Опыт показывает, что большинство секретных алгоритмов, ставших впоследствии достоянием общественности, оказались до смешного ненадежными.
Длины ключей, используемых в криптографии с открытым ключом обычно значительно больше, чем в симметричных алгоритмах. Здесь проблема заключается не в подборе ключа, а в воссоздании секретного ключа по открытому. В случае RSA проблема эквивалентна разложению на множители большого целого числа, которое является произведением пары неизвестных простых чисел. В случае некоторых других криптосистем, проблема эквивалентна вычислению дискретного логарифма по модулю большого целого числа (такая задача считается примерно аналогичной по трудности задаче разложения на множители). Имеются криптосистемы, которые используют другие проблемы.
Чтобы дать представление о степени сложности вскрытия RSA, скажем, что модули длиной 256 бит легко факторизуются обычными программистами. Ключи в 384 бита могут быть вскрыты исследовательской группой университета или компании. 512-битные ключи находятся в пределах досягаемости крупных государств. Ключи длиной в 768 бит вероятно не будут надежны продолжительное время. Ключи длиной в 1024 бит могут считаться безопасными до тех пор, пока не будет существенного прогресса в алгоритме факторизации; ключи длиной в 2048 большинство считает надежными на десятилетия. Более подробную информацию о длинах ключей RSA можно почерпнуть из статьи Брюса Шнайера (Bruce Scheier).
Важно подчеркнуть, что степень надежности криптографической системы определяется ее слабейшим звеном . Нельзя упускать из вида ни одного аспекта разработки системы --- от выбора алгоритма до политики использования и распространения ключей.
Криптоанализ и атаки на криптосистемы
Одним из способов предотвратить такой тип атак заключается в том, что стороны при обмене ключами вычисляют криптографическую хэш-функцию значения протокола обмена (или по меньшей мере значения ключей), подписывают ее алгоритмом цифровой подписи и посылают подпись другой стороне. Получатель проверит подпись и то, что значение хэш-функции совпадает с вычисленным значением. Такой метод используется, в частности, в системе Фотурис (Photuris).
- Атака с помощью таймера ( timing attack ): Этот новый тип атак основан на последовательном измерении времен, затрачиваемых на выполнение операции возведения в стенень по модулю целого числа. Ей подвержены по крайней мере следующие шифры: RSA, Диффи-Хеллман и метод эллиптических кривых. В статье Пола Кочера подробно рассмотрен этот метод.
Имеется множество других криптографических атак и криптоаналитических подходов. Однако приведенные выше являются, по-видимому, наиболее важными для практической разработки систем. Если кто-либо собирается создавать свой алгоритм шифрования, ему необходимо понимать данные вопросы значительно глубже. Одно из мест, где можно начать систематическое изучение информации --- это замечательная книга Брюса Шнейера "Прикладная криптография" (Bruce Schneier, Applied Cryptography).
Схема защищённого хранения паролей с помощью хеширования. Конкретные криптографические хеш-функции. Хеш-функции в электронно-цифровой подписи. Функции шифрования MySQL. Обратимое и необратимое шифрование. Логика выполнения и основные шаги алгоритма MD5.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 23.09.2016 |
| Размер файла | 759,8 K |
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Безопасное хранение паролей с помощью хеш-функций
Пусть есть у нас социальная сеть, база данных или прочее, где может быть вход по логину и паролю. Чтобы система проверила, правильно ли введён пароль, требуется где-то хранить пароли. Если они хранятся в "сыром" виде, то их можно отыскать. Проще всего порыться в чужих паролях будет администраторам. То есть если пароли в файле хранения никак не маскируются, то даже пользователь, не щёлкающий по подозрительным ссылкам и придумывающий сверхдлинные пароли, не будет в безопасности.
Можно хранить пароли в зашифрованном виде. Это чуть лучше, чем в сыром, но бесполезно, если кто-то, способный найти файл хранения, знает алгоритм и ключ шифра. А вот если прибегнуть к хешированию - использовать хеш-функции с длинными хеш-значениями (скажем, 256, 512, 1024 бит), то завладеть чужим аккаунтом сложно любому, кто не знает всего одного - пароля. Предполагается, что пользователь не придумал тупой пароль вроде "111".
Вместо паролей будем хранить их хеш-значения. Пользователь вводит при входе логин и пароль. В файле по логину ищется нужный хеш. Он сравнивается с хешем того, что введено в поле "пароль" пользователем. Если значения равны, то пользователя пропускают, иначе - нет. Может быть, что пароль неправильный, но хеш-значения совпали. Если хеш-значение длинное, то такой прокол маловероятен и может произойти только чудом.
Если кто-то откроет файл с данными пользователей, вместо паролей он увидит хеш - значения. Чтобы злоумышленник не мог быстро придумать по какому-то из них подходящую строку-пароль, и введено требование стойкости к восстановлению прообраза.
Наглядно эту схему защищённого хранения паролей с помощью хеширования можно нарисовать следующим образом:
Список пользователей
1111000010120
Введите логин и пароль
Эта схема неплохо усиливает безопасность пользователей, но она не всесильна. Если пользователь придумывает пароли вроде даты рождения, имени, слова password, "111" или клички домашнего животного, а также держит на виду у окружающих бумажку, где записан пароль, то создатели хеш-функций тут ни при чём.
Хеш-функции в электронно-цифровой подписи
Хеш-функции обычно являются частью механизма электронно-цифровой подписи. Технология ЭЦП является современной заменой обычной бумажной подписи и часто удобнее её. Даже сложные закорючки обычной подписи при должном старании реально подделать. Изучив, что такое ЭЦП, легко понять, что её подделать крайне трудно. И вообще рост известности понятия ЭЦП вполне согласуется с явлением роста электронного документооборота.
Другие применения хеш-функций
Конкретные криптографические хеш-функции
Большинство хорошо известных хеш-функции разработана на западе. Особо известны семейства SHA и MD, из них самые знаменитые - SHA1 и MD5, хотя они уже не лучшие представители своих "семей". Об этих хеш-функциях часто говорят в статьях и на форумах. Из других зарубежных хеш-функций можно рассмотреть, например, RIPEMD-160, разработанную в Бельгии.
Но не следует зацикливаться только на иностранных функциях хеширования. У нас есть ГОСТ Р34.11-2012 - российский стандарт хеширования с 256-битными хеш-значениями. Заметим: SHA1 даёт только 160-битный хеш. Принципиальная особенность ГОСТовского хеширования: оно базируется на ГОСТовском же алгоритме шифрования.
Также заслуживает внимание семейство Skein, обеспечивающее хеширование с выходами 256, 512, 1024 бит. Заметим: самая "длинная" из хвалёных хеш-функций SHA2 даёт хеш в 512 бит.
Безопасность и MySQL
Здесь будут рассмотрены многочисленные функции шифрования данных, которые входят в состав СУБД MySQL. Чаще всего шифрованию подвергаются пароли. В случае взлома базы данных злоумышленник получит доступ только к зашифрованным записям, на расшифровку которых потребуется время, за которое пароли могут стать не актуальными.
Функции шифрования MySQL
Различают два вида шифрования: обратимое и необратимое. При обратимом шифровании зашифрованный текст может быть подвергнут дешифровке. При необратимом шифровании результатом является хэш, который невозможно восстановить в исходный текст.
Примечание. Если функции передается в качестве одного из аргументов значение NULL, она также возвращает NULL.
Таблица. Функции шифрования MySQL
Принимает в качестве первого аргумента зашифрованную при помощи AES_ENCRYPT() строку. Ключ key_str при этом должен совпадать как в первой так и во второй строках. Если функция AES_DECRYPT() обнаруживает некорректные данные или некорректное заполнение строки, должно возвращаться значение NULL. Однако AES_DECRYPT() вполне может вернуть величину отличную от NULL, или просто "мусор"
Шифрует строку str, используя аргумент pass_str как секретный ключ
Дешифрует строку crypt_str, зашифрованную функцией AES_DECRYPT(). Аргумент pass_str используется как секретный ключ
Шифрует строку str, используя аргумент pass_str как секретный ключ. В качестве второго необязательного параметра может выступать строка key_string, задающая секретрый ключ. В случае использования секретного ключа необходимо приводить его в качестве второго параметра и в функции дешифровки DES_DECRYPT(). Вместо секретного ключа можно указать номер key_number, принимающий значение от 0 до 9. Номер указывает на запись в ключевом DES-файле сервера, местоположение которого можно задать при старте сервера MySQL в параметре --des-key-file
Дешифрует строку str, зашифрованную при помощи функции DES_ENCRYPT(). Если при шифровании в качестве второго параметра функции DES_ENCRYPT() было передано число или второй параметр был опущен, то параметр key_string функции DES_DECRYPT() указывать уже не требуется, так как он прописывается в зашифрованную строку. Такой подход, когда секретный ключ хранится на сервере и не передается через сетевое соединение, значительно безопаснее, поскольку значение ключа невозможно извлечь из сетевого трафика. Если второй параметр не указывается, то предполагается, что используется первая строка DES-файла
Подвергает строку str необратимому шифрованию, используя вызов системной функции crypt() UNIX. Если второй необязательный параметр salt не указывается, то результат каждый раз получается новым.
Подвергает необратимому шифрованию данные str. Именно эта функция используется для шифрования паролей в MySQL
Эмулирует работу функции PASSWORD() версий MySQL, предшествующих MySQL 4.1
Вычисляет 160-битную контрольную сумму по алгоритму SHA1(Secure Hach Algorithm) для строки str
При обратимом шифровании, как правило, предоставляется две функции для шифровки и расшифровки данных.
Рассмотрим примеры с использованием функций AES_ENCRYPT (str, key_str) и AES_DECRYPT(crypt_str, key_str), оисание которых дано в таблице.
Функция AES_ENCRYPT(str, key_str)
А теперь рассмотрим шифрование поля email, в таблице users базы данных wet. Шифрование данного поля позволит уберечь пользователей от спамеров в случае, если база данных попадет им в руки. Создадим таблицу users и заполним ее поля.
Шифрование e-mail
хеширование криптографический шифрование
Как видно из листинга, прямой просмотр поля email приводит к выводу "мусора". Для того чтобы узнать настоящие адреса email, необходимо воспользоваться функцией дешифровки AES_DECRYPT() и знать секретный ключ.
Дешифровка данных
Функция MD5() осуществляет необратимое шифрование.
Использование функции MD5()
Примечание. Алгоритм MD5() часто используется для создания уникального хэш-кода объемных файлов, которые передаются по сети. Загрузив файл, всегда можно проверить его целостность, вычислив код по алгоритму MD5() и сравнив полученный результат с хэш-кодом, представленным распространителем. Это позволяет отследить повреждения файла, вызванные передачей через сеть, а также предотвращает фальсификацию дистрибутива.
Необратимое шифрование может применяться для шифрования паролей -- в базе данных хранятся не сами пароли, а их MD5-хэши. Во время аутентификации пароль, введенный пользователем, также подвергается обработке функцией MD5(), после чего MD5-хэши подвергаются сравнению. Такая схема позволяет хранить пароли в защищенном виде, и никто, даже администратор базы данных, не имеет возможности узнать пользовательские пароли. В последнее время такой вид аутентификации приобретает все большую популярность. Поскольку в следствии применения паузы после ввода некорректного пароля время, необходимое для подбора пароля, многократно возросло, средства подбора единичных паролей по сети практически вышли из употребления -- злоумышленники стараются получить всю базу с паролями. Если же в базе храняться только MD5-хэши, злоумышленнику придется восстанавливать методом перебора каждый из зашифрованных паролей.
Функция PASSWORD() подвергает необратимому шифрованию данные и используется для шифрования паролей MySQL в столбце password в таблице привлегий user системной базы даны хmysql.
Использование функции PASSWORD()
Функция PASSWORD() используется в системе аутентификации в сервер MySQL, поэтому ее не следует использовать в приложениях -- лучше пользоваться функциями MD5() и SHA1().
Арифметика остатков и теория сравнений
Немецкий математик Карл Фридрих Гаусс предложил запись
для двух чисел a и b, если они имеют одинаковые остатки от деления на m (читается a сравнимо с b по модулю m). Например,
Сравнения обнаруживают полезные для математиков и криптографов свойства, во многом похожие на свойства равенств. Эти свойства позволяют существенно упрощать арифметические вычисления, если нас интересует только остаток от деления на некоторое число m. Так, например, свойства сравнений полезны при расчетах в алгоритмах шифрования с открытым ключом.
Проблема защиты информации путем ее преобразования, исключающего ее прочтение посторонним лицом волновала человеческий ум с давних времен. История криптографии - ровесница истории человеческого языка. Более того, первоначально письменность сама по себе была криптографической системой, так как в древних обществах ею владели только избранные.
Священные книги Древнего Египта, Древней Индии тому примеры.
С широким распространением письменности криптография стала формироваться как самостоятельная наука. Первые криптосистемы встречаются уже в начале нашей эры. Так, Цезарь в своей переписке использовал уже более менее систематический шифр, получивший его имя.
Бурное развитие криптографические системы получили в годы первой и второй мировых войн. Начиная с послевоенного времени и по нынешний день появление вычислительных средств ускорило разработку и совершенствование криптографических методов.
Почему проблема использования криптографических методов в информационных системах (ИС) стала в настоящий момент особо актуальна?
С одной стороны, расширилось использование компьютерных сетей, в частности глобальной сети Internet, по которым передаются большие объемы информации государственного, военного, коммерческого и частного характера, не допускающего возможность доступа к ней посторонних лиц.
С другой стороны, появление новых мощных компьютеров, технологий сетевых и нейронных вычислений сделало возможным дискредитацию криптографических систем еще недавно считавшихся практически не раскрываемыми.
В первой главе данной работы можно познакомиться с основными понятиями современной криптографии, требованиям к ним, возможностями ее практического применения.
Во второй главе работы с протоколами распределения криптографических ключей, понятием электронной подписи и протоколами электронной подписи..
Третья глава данной работы рассказывает о хэш-функциях и (методах) алгоритмах их построения.
В четвертой главе будет рассказано о модернизации электронной подписи Эль Гамаля и задаче дискретного логарифмирования.
Глава 1. Основные понятия современной криптографии
Проблемой защиты информации путем ее преобразования занимается криптология (kryptos - тайный, logos - наука). Криптология разделяется на два направления - криптографию и криптоанализ. Цели этих направлений прямо противоположны.
Криптография занимается поиском и исследованием математических методов преобразования информации.
Сфера интересов криптоанализа - исследование возможности расшифровывания информации без знания ключей.
В этой работе основное внимание будет уделено криптографическим методам.
Современная криптография включает в себя четыре крупных раздела:
Криптосистемы с открытым ключом.
Системы электронной подписи.
Криптография дает возможность преобразовать информацию таким образом, что ее прочтение (восстановление) возможно только при знании ключа.
В качестве информации, подлежащей шифрованию и дешифрованию, будут рассматриваться тексты, построенные на некотором алфавите. Под этими терминами понимается следующее.
Алфавит - конечное множество используемых для кодирования информации знаков.
Текст - упорядоченный набор из элементов алфавита.
В качестве примеров алфавитов, используемых в современных ИС можно привести следующие:
алфавит Z33 - 32 буквы русского алфавита и пробел;
алфавит Z256 - символы, входящие в стандартные коды ASCII и КОИ-8;
бинарный алфавит - Z2 = ;
восьмеричный алфавит или шестнадцатеричный алфавит;
Шифрование - преобразовательный процесс: исходный текст, который носит также название открытого текста, заменяется шифрованным текстом.
Дешифрование - обратный шифрованию процесс. На основе ключа шифрованный текст преобразуется в исходный.
Ключ - информация, необходимая для беспрепятственного шифрования и дешифрования текстов.
Криптографическая система представляет собой семейство T преобразований открытого текста. Члены этого семейства индексируются, или обозначаются символом k; параметр k является ключом. Пространство ключей K - это набор возможных значений ключа. Обычно ключ представляет собой последовательный ряд букв алфавита.
Криптосистемы разделяются на симметричные и с открытым ключом.
В симметричных криптосистемах и для шифрования, и для дешифрования используется один и тот же ключ.
Криптостойкостью называется характеристика шифра, определяющая его стойкость к дешифрованию без знания ключа (т.е. криптоанализу). Имеется несколько показателей криптостойкости, среди которых:
количество всех возможных ключей;
среднее время, необходимое для криптоанализа.
Преобразование Tk определяется соответствующим алгоритмом и значением параметра k. Эффективность шифрования с целью защиты информации зависит от сохранения тайны ключа и криптостойкости шифра.
Процесс криптографического закрытия данных может осуществляться как программно, так и аппаратно. Аппаратная реализация отличается существенно большей стоимостью, однако ей присущи и преимущества: высокая производительность, простота, защищенность и т.д. Программная реализация более практична, допускает известную гибкость в использовании.
Для современных криптографических систем защиты информации сформулированы следующие общепринятые требования:
число операций, необходимых для расшифровывания информации путем перебора всевозможных ключей должно иметь строгую нижнюю оценку и выходить за пределы возможностей современных компьютеров (с учетом возможности использования сетевых вычислений);
знание алгоритма шифрования не должно влиять на надежность защиты;
структурные элементы алгоритма шифрования должны быть неизменными;
длина шифрованного текста должна быть равной длине исходного текста;
не должно быть простых и легко устанавливаемых зависимостью между ключами, последовательно используемыми в процессе шифрования;
любой ключ из множества возможных должен обеспечивать надежную защиту информации;
алгоритм должен допускать как программную, так и аппаратную реализацию, при этом изменение длины ключа не должно вести к качественному ухудшению алгоритма шифрования.
Глава 2. Протоколы распределения криптографических ключей и протоколы электронной подписи.
Как бы ни были сложны и надежны криптографические системы - их слабое мест при практической реализации - проблема распределения ключей. Для того, чтобы был возможен обмен конфиденциальной информацией между двумя субъектами ИС, ключ должен быть сгенерирован одним из них, а затем каким-то образом опять же в конфиденциальном порядке передан другому. Т.е. в общем случае для передачи ключа опять же требуется использование какой-то криптосистемы.
Для решения этой проблемы на основе результатов, полученных классической и современной алгеброй, были предложены системы с открытым ключом.
Исходный текст шифруется открытым ключом адресата и передается ему. Зашифрованный текст в принципе не может быть расшифрован тем же открытым
Криптографические системы с открытым ключом используют так называемые необратимые или односторонние функции, которые обладают следующим свойством: при заданном значении x относительно просто вычислить значение f(x), однако если y=f(x), то нет простого пути для вычисления значения x.
Множество классов необратимых функций и порождает все разнообразие систем с открытым ключом. Однако не всякая необратимая функция годится для использования в реальных ИС.
В самом определении необратимости присутствует неопределенность. Под необратимостью понимается не теоретическая необратимость, а практическая невозможность вычислить обратное значение используя современные вычислительные средства за обозримый интервал времени. Поэтому чтобы гарантировать надежную защиту информации, к системам с открытым ключом (СОК) предъявляются два важных и очевидных требования:
1. Преобразование исходного текста должно быть необратимым и исключать его восстановление на основе открытого ключа.
2. Определение закрытого ключа на основе открытого также должно быть невозможным на современном технологическом уровне. При этом желательна точная нижняя оценка сложности (количества операций) раскрытия шифра.
Алгоритмы шифрования с открытым ключом получили широкое распространение в современных информационных системах. Так, алгоритм RSA стал мировым стандартом де-факто для открытых систем и рекомендован МККТТ.
Вообще же все предлагаемые сегодня криптосистемы с открытым ключом опираются на один из следующих типов необратимых преобразований:
Разложение больших чисел на простые множители.
Вычисление логарифма в конечном поле.
Вычисление корней алгебраических уравнений.
Алгоритм Диффи-Хеллмана .
Диффи и Хелман предложили для создания криптографических систем с открытым ключом функцию дискретного возведения в степень.
Необратимость преобразования в этом случае обеспечивается тем, что достаточно легко вычислить показательную функцию в конечном поле Галуа состоящим из p элементов. (p - либо простое число, либо простое в любой степени). Вычисление же логарифмов в таких полях - значительно более трудоемкая операция.
Если y=ax,, 1 Cr1>…>Crn = Cj, где Cl-1 непосредственно доминирует Cl для всех L = 1,…,n. Абонент Ci, зная Ki и Pr1, вычисляет по формуле (**), затем, зная Kr1 и Pr2, вычисляет Kr2 по той же формуле и т.д.; после n шагов будет вычислен Krn = Kj.
Электронная подпись
В чем состоит проблема аутентификации данных?
В конце обычного письма или документа исполнитель или ответственное лицо обычно ставит свою подпись. Подобное действие обычно преследует две цели.
Во-первых, получатель имеет возможность убедиться в истинности письма,
сличив подпись с имеющимся у него образцом. Во-вторых, личная подпись является юридическим гарантом авторства документа. Последний аспект особенно важен при заключении разного рода торговых сделок, составлении доверенностей, обязтельств и т.д.
Если подделать подпись человека на бумаге весьма непросто, а установить авторство подписи современными криминалистическими методами - техническая деталь, то с подписью электронной дело обстоит иначе. Подделать цепочку битов, просто ее скопировав, или незаметно внести нелегальные исправления в документ сможет любой пользователь.
С широким распространением в современном мире электронных форм документов (в том числе и конфиденциальных) и средств их обработки особо актуальной стала проблема установления подлинности и авторства безбумажной документации.
Итак, пусть имеются два пользователя Александр и Борис.
От каких нарушений и действий злоумышленника должна защищать система аутентификации.
Для исключения этого нарушения используется электронная (или цифровая) подпись.
Для защиты от модификации, подделки и маскировки используются цифровые сигнатуры.
В этом случае для защиты также используется электронная подпись.
Наиболее действенным методом защиты от повтора являются
Протоколы электронной подписи
Протоколы (схемы) электронной подписи являются основными криптографическим средством обеспечения целостности информации.
Схема Эль Гамаля.
Пусть обоим участникам протокола известны некоторое простое число p, некоторой порождающей g группы Z*p и некоторая хэш-функция h.
s = u-1(h(m) +xr) mod (p-1). Параметр u должен быть секретным и может быть уничтожен после генерации подписи.
Вера в стойкость схемы Эль Гамаля основана на (гипотетической) сложности задачи дискретного логарифмирования по основанию g.
Схема Фиата – Шамира.
Для ее обеспечения центр обеспечения безопасности должен выбрать псевдослучайную функцию f, криптографическую хэш-функцию h, а также выбрать различные большие простые числа p, q и вычислить n = pq. Число n и функции f и h являются общедоступными и публикуются центром, а числа p и q должны быть секретными. Кроме того, схема использует два натуральных параметра l и t.
Для каждого пользователя центр обеспечения безопасности генерирует идентификационную информацию I, содержащую, например, имя пользователя, его адрес, идентификационный номер и т. п., и для каждого j = 1,…,l вычисляет
yi = f(I,j), отбирает среди них квадратичные вычеты по модулю n (изменив обозначения, мы считаем, что yi для всех j = 1,…,l являются квадратичными вычетами по млдулю n), и вычисляет xi – наименьший квадратичный корень по модулю n из yi-1 modn. Числа yi играют роль открытого ключа, а xi – секретного. Так как эти ключи вычисляются с использованием I, схема Фивта – Шамира относится к схемам, основанным на идентификационной информации (identitybased). В другом варианте схемы Фиата – Шамира сразу выбираются (псевдослучайным образом) параметру yi. На практике идентификационная информация I и/или открытый ключ (y1,…,yl) каждого пользователя помещаются в некоторый справочник, доступный всем пользователям для чтения, но не доступный для записи. Для обеспечения аутентичности, данные в этом справочнике заверяются подписью центра обеспечения безопасности. Секретный ключ (x1,…,xl) и идентификационная информация I могут быть помещены на интеллектуальную карточку пользователя.
Для генерации подписи для обеспечения m подписывающий
выбирает uiÎRZn (каждое ui – независимо друг от друга) и вычисляет ri = ui2 modn для i = 1,…,t;
вычисляет h(m,r1,…,rt) и полагает биты eij(i = 1,…,t, j = 1,…,t) равными первым lt битам h(m,r1,…,rt);
вычисляет для i = 1,…,t.
вычисляет vj = h(I,j) для j = 1,…,l или берет их из общедоступного справочника и сравнивает их с имеющимися в подписи (если обнаружено несовпадение – подпись отвергается);
вычисляет для i = 1,…,t.
Подпись принимается тогда и только тогда, когда первые lt битов h(m,z1,…,zt) равны eij.
Несомненным достоинством схемы Фмата – Шамира является отсутствие дискретного экспонентрирования, что делает схему весьма эффективной. Но с другой стороны, в этой схеме длины ключей и подписи значительно больше, чем в схемах типа Эль Гамаля.
Схема стандарта электронной подписи ANSI США (DSA)
Читайте также: