Алгоритмы и стойкость шифрования

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

Алгоритмы и стойкость шифрования

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

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

Основной схемой классификации всех криптоалгоритмов является следующая:

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

- Криптография с ключом. Алгоритм воздействия на передаваемые данные известен всем сторонним лицам, но он зависит от некоторого параметра -- «ключа», которым обладают только отправитель и получатель.

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

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

Любой криптоалгоритм с ключом вы имеете возможность превратить в тайнопись, просто «зашив» в исходном коде программы некоторый фиксированный ключ.

Обратное же преобразование практически невозможно.

В зависимости от характера воздействий, производимых над данными, алгоритмы подразделяются на:

- Перестановочные. Блоки информации (байты, биты, более крупные единицы) не изменяются сами по себе, но изменяется их порядок следования, что делает информацию недоступной стороннему наблюдателю.

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

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

Уменьшение объема закодированного файла возможно только при наличии встроенного алгоритма архивации в криптосистеме и при условии сжимаемости информации (так, например, архивы, музыкальные файлы формата МРЗ, видеоизображения формата JPEG сжиматься более чем на 2-4% не будут).

В зависимости от размера блока информации криптоалгоритмы делятся на:

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

- Блочные шифры. Единицей кодирования является блок из нескольких байтов (в настоящее время 4-32). Результат кодирования зависит от всех исходных байтов этого блока. Схема применяется при пакетной передаче информации и кодировании файлов.

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

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

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

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

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

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

К широко известным симметричным алгоритмам относятся DES и IDEA, наверное самым лучшим асимметричным алгоритмом является RSA.

Алгоритмы шифрования DES, RSA, RC5 и AES.

[DES]

Один из самых распространненыха aлгоритмов шифрования - DES (Data Encryption Standart) - разработан в середине 70-x годов. Он используется во многих криптографических системах. Это блочный алгоритм шифрования с симметричным ключом. Ключ состоит из 64 битов, но лишь 56 из них применяются непосредственно при шифровании. Оставшиеся 8 предназначены для контроля четности: они устанавливаются так, чтобы каждый из 8 байтов ключа имел нечетное значение. Шифруемая информация обрабатывается блоками по 64 бита, причем каждый блок модифицируется с помощью ключа в интерационной процедуре, включающей 16 циклов. Да, кстати, DES создалa небезизвестная компания RSA.

DES уже морально устарел , он так же еще может применяться в различных девайсах, программных обеспечениях типа: AMT - банкомат, или проще говоря сейф . Различные транзакции и манипуляции производимые с банкоматом (AMT, и т.д.), шифруется именно им. Наверно кардеры с ним хорошо знакомы. Все дело в том, что предприятия использовали этот алгоритм долгое время и соответственно под него подстраивалось все что можно, ни хватает средств для полного перехода на этот алгоритм. Например, большое предприятие, или завод создавался долгое время, а позже он обанкротится, потому что мобильные предприятия быстро перешли на другое оборудование и т.д. Позже придумали некое подобие DES, это 3DES. Он отличается лишь тем, что у него как бы переходная длина ключа, то есть было в начале ~56, а стало ~64. Соответственно это очень затрудняло взлом этого алгоритма. Но он не слишком отличается дырявостью от простого DES.

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

Для большой надежности можно задействовать алгоритм Triple-DES

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

RC5 это довольно-таки быстрый блочный шифр разработанный Ривестом для RSA Data Security. Этот алгоритм параметричен, т.е. с переменным размером блока, длинной ключа и переменным числом проходов. Размер блока может быть 32, 64, или 128 битов. Количество проходов в промежутке от 0 до 2048 бит. Параметричность такого рода дает гибкость и эффективность шифрования.

RC5 состоит из ввода ключа (key expansion), шифрования и дешифрования. При вводе ключа вводятся также количество проходов, размер блока и т.д. Шифрование состоит из 3 примитивных операций : сложения, побитового XOR и чередования (rotation). Исключительная простота RC5 делает его простым в использовании, RC5 текст, также как и RSA, может быть дописан в конец письма в зашифрованном виде.

Безопасность RC5 основывается на зависящем от данных чередованием и смешиванием результатов различных операций. RC5 с размером блока 64 бита и 12 или более проходов обеспечивает хорошую стойкость против дифференциального и линейного криптоанализов

RSA - один из первых и весьма популярный алгоритм шифрования с открытым ключом - разработан основателями фирмы RSA (Rivest, Shmir, Adleman) в конце 70-x годов и назван по первым буквам их фамилий.

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

Сейчас ключи длиной 512 битов рассматриваются как недостаточно устойчивые, поэтому в криптографическом программном обеспечении рекомендуются 768 или 1024 битные ключи.

Часто используют комбинированный подход: сначала сообщение кодируются с помощью некоторого ключа по алгоритму типа DES, а затем ключ зашифровывается с применением RSA и передается вместе с закодированным сообщением. Это позволяет достичь высокой скорости обработки информации и в то же время обеспечивает надежную ее защиту.

Краткие основы RSA:

1. Выбираются большие простые числа M и N;

2. Вычисляется их произведение: Q=MxN;

3. Выбирается число D, которое должно быть взаимно простым с результатом умножения (M-1)x(N-1), т.е. не должно иметь с ним общих делителей, отличных от единицы;

4. Вычисляется число A из выражения (AxD) mod [(M-1)x(N-1)]=1;

Таким образом, пара чисел (A,Q) будет твоим открытым ключом, а пара чисел (D,Q) -- закрытым ключом. Понятно, что открытым ключом можно только закодировать исходный текст, для того, чтобы его раскодировать, нужен закрытый ключ.

Кодирование числа P: C=M^A mod Q;

Обратная операция: P=C^D mod Q;

Так вот, для того, чтобы поломать PGP (сиречь RSA), необходимо и достаточно уметь разложить число Q (которое мы возьмем, понятно, из открытого ключа, помещенного человеком в бурные воды, скажем, Fido и/или Internet) на простые множители. Вот тут-то и начинается самое интересное.

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

[AES]

Это альтернатива DES. На сегодняйший день, не замечено взломов этого алгоритма. Ну если и замечено, то его взломов почти нет . Он стал применяться в новых девайсах, в прогах. Все в скором времени должны на него перейти. AES применяется в WI-FI, длина ключа у него около 128 Бит. Судить тебе, что надежнее :).

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

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

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

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

Симметричные алгоритмы. Алгоритмы шифрования делятся на два больших класса: симметричные (AES, ГОСТ, Blowfish, CAST, DES) и асимметричные (RSA, El-Gamal). Симметричные алгоритмы шифрования используют один и тот же ключ для зашифровывания информации и для ее расшифровывания, а асимметричные алгоритмы используют два ключа - один для зашифровывания, другой для расшифровывания.

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

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

Если зашифровать одни и те же данные одним алгоритмом, но разными ключами, результаты получатся тоже разные.

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

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

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

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

Теоретическая и практическая стойкость.

В 1949 г. К.Э. Шеннон опубликовал статью "Теория связи в секретных системах". Шеннон рассматривал стойкость криптографических систем как Практическую и Теоритическую. Вывод по теоретической стойкости до сих пор остается пессимистическим: длина ключа должна быть равна длине открытого текста.

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

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

Взлом алгоритма шифрования

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

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

На практике это означает, что злоумышленник должен :

Иметь в распоряжении криптосистему (т.е. программу) и примеры зашифрованных сообщений.

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

Разработать и реализовать алгоритм перебора Ключей для этой криптосистемы.

Как определить, что ключ верный или нет ?

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

Один из самых распространенных алгоритмов шифрования - DES (Data Encryption Standart) - разработан в середине 70-x годов. Он используется во многих криптографических системах. Это блочный алгоритм шифрования с симметричным ключом. Ключ состоит из 64 битов, но лишь 56 из них применяются непосредственно при шифровании. Оставшиеся 8 предназначены для контроля четности: они устанавливаются так, чтобы каждый из 8 байтов ключа имел нечетное значение. Шифруемая информация обрабатывается блоками по 64 бита, причем каждый блок модифицируется с помощью ключа в итерационной процедуре, включающей 16 циклов. В данный момент при длине ключа в 56 битов алгоритм считается не устойчивым к взлому.

Для большой надежности можно задействовать алгоритм Triple-DES

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

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

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

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

* полное раскрытие. Противник находит путем вычислений секретный ключ системы;

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

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

* частичное раскрытие. Противник получает частичную информацию об используемом ключе или об открытом сообщении.

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

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

* конкретный объем перехваченных зашифрованных сообщений;

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

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

Абсолютно стойкие системы

Доказательство существования абсолютно стойких алгоритмов шифрования было выполнено Клодом Шенноном и опубликовано в работе «Теория связи в секретных системах».[1] Там же определены требования к такого рода системам:

ключ генерируется для каждого сообщения (каждый ключ используется один раз)

ключ статистически надёжен (то есть вероятности появления каждого из возможных символов равны, символы в ключевой последовательности независимы и случайны)

длина ключа равна или больше длины сообщения

исходный (открытый) текст обладает некоторой избыточностью (является критерием оценки правильности расшифровки)

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

Некоторыми аналитиками утверждается, что Шифр Вернама является одновременно абсолютно криптографически стойким и к тому же единственным[источник не указан 360 дней] шифром, который удовлетворяет этому условию.

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

вычислительная сложность полного перебора

известные на данный момент слабости (уязвимости) и их влияние на вычислительную сложность.

Размещено на Allbest.ru