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



Pdf просмотр
страница1/5
Дата15.02.2017
Размер1.13 Mb.
Просмотров601
Скачиваний0
  1   2   3   4   5


Введение.
В данном учебном пособии рассмотрены основные математические и криптографические понятия, необходимые для моделирования криптосистем. Учебное пособие состоит из четырех частей:
1. Основные понятия, используемые в криптографии;
2. Математические основы, используемые для анализа и построения криптосистем - теория сложности, теория информации, энтропия и неопределенность, теория чисел и другие;
3. Криптографические алгоритмы DES, AES, RSA, DSA;
4. Некоторые способы криптоанализа и ряд вопросов, связанных с анализом ключей.

















2
Раздел 1. Основные понятия
1.1 Терминология
Отправитель и получатель
Предположим, что отправитель хочет послать сообщение получателю. Более того, этот отправитель хочет послать свое сообщение безопасно: он хочет быть уверен, что перехвативший это сообщение не сможет его прочесть. Стороны, обменивающиеся шифрованной информацией, обычно обозначаются А и В. Довольно часто употребляют более дружественные имена: Алиса и Боб. Но не следует думать, что стороны, участвующие в процессе, обязательно люди. Используя эти имена, мы вполне можем описывать обмен секретной информацией между двумя автономными механизмами.
Подслушивающей стороне, «плохой девочке», которая взламывает шифротекст, обычно дают имя Ева.
Сообщения и шифрование
Само сообщение называется открытым текстом. Алгоритм шифрования (или
шифр) — это перевод открытого текста в текст зашифрованный (или шифротекст, шифрограмму, криптограмму) с помощью секретного ключа. Этот процесс называют шифрованием. Обозначим открытый текст как M (от message, сообщение), или P (от
plaintext, открытый текст). Это может быть поток битов, текстовый файл, битовое изображение, оцифрованный звук, цифровое видеоизображение. Для компьютера M - это просто двоичные данные. Открытый текст может быть создан для хранения или передачи. В любом случае, M - это сообщение, которое должно быть зашифровано.
Обозначим шифротекст как C (от ciphertext). Это тоже двоичные данные, иногда того же размера, что и M, иногда больше. Если шифрование сопровождается сжатием, C может быть меньше чем M. Само шифрование, однако, не обеспечивает сжатие информации. Функция шифрования E действует на M, создавая C.
Мы будем писать
С = Е
к
(M), где M — открытый текст, Е — шифрующая функция, K — секретный ключ, С — шифротекст.
Обратный процесс называют расшифрованием и пишут
M
= D
k
(C ).
Заметим, что алгоритмы шифрования и расшифрования

Е и

D открыты, и секретность исходного текста M в данном шифротексте С зависит от секретности ключа K.
Поскольку смыслом шифрования и последующего дешифрирования сообщения является восстановление первоначального открытого текста, должно выполняться следующее равенство:
D
k
(E
k
(M)) = M
Искусство и наука безопасных сообщений, называемая криптографией, воплощается в жизнь криптографами. Криптоаналитиками называются те, кто используют
криптоанализ, искусство и науку взламывать шифротекст - раскрывать то, что было зашифровано. Отрасль математики, охватывающая криптографию и криптоанализ, называется криптологией, а люди, которые ей занимаются - криптологами. Для создания криптосистемы, криптограф должен быть хорошим криптоаналитиком.

3
Проверка подлинности, целостность и неотрицание авторства
Кроме обеспечения конфиденциальности криптография часто используется для других функций:


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


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


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

E
K
(M)=C

D
K
(C)=M
При этом выполняется следующее равенство:
D
K
(E
K
(M))=M
Для некоторых алгоритмов при шифровании и дешифрировании используются различные ключи. То есть ключ шифрования, К
1
, отличается от соответствующего ключа дешифрирования, K
2
. В этом случае:
Рис. 1-1. Шифрование и дешифрирование

4
E
K
1
(M)=C
D
K
2
(C)=M
D
K
2
(E
K1
(M))=M
Безопасность этих алгоритмов полностью основана на ключах, а не на деталях алгоритмов. Это значит, что алгоритм может быть опубликован и проанализирован.
Продукты, использующие этот алгоритм, могут широко тиражироваться. Не имеет значения, что злоумышленнику известен алгоритм, если ему не известен конкретный ключ, то он не сможет прочесть сообщения.
Криптосистема представляет собой алгоритм плюс все возможные открытые тексты, шифротексты и ключи.
1.2 Симметричные алгоритмы
Существует два основных типа алгоритмов, основанных на ключах: симметричные и с открытым ключом. Симметричные алгоритмы, иногда называемые условными алгоритмами, представляют собой алгоритмы, в которых ключ шифрования может быть рассчитан по ключу дешифрирования и наоборот. В большинстве симметричных алгоритмов кличи шифрования и дешифрирования одни и те же. Эти алгоритмы, также называемые алгоритмами с секретным ключом или алгоритмами с одним ключом, требуют, чтобы отправитель и получатель согласовали используемый ключ перед началом безопасной передачи сообщений. Безопасность симметричного алгоритма определяется ключом, раскрытие ключа означает, что кто угодно сможет шифровать и дешифрировать сообщения. Пока передаваемые сообщения должны быть тайными, ключ должен храниться в секрете. Шифрование и дешифрирование с использованием симметричного алгоритма обозначается как:
E
K
(M)=C
D
K
(C)=M
Симметричные алгоритмы делятся на две категории. Одни алгоритмы обрабатывают открытый текст побитно (иногда побайтно), они называются потоковыми алгоритмами или потоковыми шифрами. Другие работаю с группами битов открытого текста.
Группы битов называются блоками, а алгоритмы - блочными алгоритмами или
блочными шифрами. До появления компьютеров алгоритмы обычно обрабатывали открытый текст посимвольно. Такой вариант может рассматриваться как потоковый алгоритм, обрабатывающий поток символов. Для алгоритмов, используемых в компьютерных модемах, типичный размер блока составляет 64 бита - достаточно
Ключ
Ключ
Рис. 1-2. Шифрование и дешифрирование с ключом
Ключ
Ключ
Рис. 1-3. Шифрование и дешифрирование с двумя различными ключами

5 большое значение, чтобы помешать анализу, и достаточно небольшое и удобное для работы.
1.3 Алгоритмы с открытым ключом
Алгоритмы с открытым ключом, называемые асимметричными алгоритмами, разработаны таким образом, что ключ, используемый для шифрования, отличается от ключа дешифрирования. Более того, ключ дешифрирования не может быть рассчитан по ключу шифрования. Алгоритмы называются "с открытым ключом", потому что ключ шифрования может быть открытым: кто угодно может использовать ключ шифрования для шифрования сообщения, но только конкретный человек с соответствующим ключом дешифрирования может расшифровать сообщение.
В этих системах ключ шифрования часто называется открытым ключом, а ключ дешифрирования - закрытым.
Открытый ключ может быть опубликован в справочнике наряду с именем пользователя. В результате любой желающий может зашифровать с его помощью свое письмо и послать закрытую информацию владельцу соответствующего секретного ключа.
Расшифровать посланное сообщение сможет только тот, у кого есть секретный ключ.
Более точно, имеют место преобразования: сообщение + ОТКРЫТЫЙ КЛЮЧ АЛИСЫ = ШИФРОТЕКСТ
ШИФРОТЕКСТ + секретный ключ Алисы = сообщение.
Таким образом, каждый может послать Алисе секретную информацию, воспользовавшись ее открытым ключом. Но только Алиса в состоянии расшифровать сообщение, поскольку лишь у нее есть соответствующий секретный ключ.
Шифрование с открытым ключом K обозначается как:
E
K
(M)=C
Хотя открытый и закрытый ключи различны, дешифрирование с соответствующим закрытым ключом об означается как:
D
K
(C)=M
Иногда сообщения шифруются закрытым ключом, а дешифрируются открытым, что используется для цифровой подписи.
1.4 Криптоанализ
Смысл криптографии - в сохранении открытого текста (или ключа, или и того, и другого) в тайне от злоумышленников (также называемых взломщиками, соперниками, врагами, перехватчиками). Предполагается, что злоумышленники полностью контролируют линии связи между отправителем и получателем.
Криптоанализ - наука получения открытого текста, не имея ключа. Успешно проведенный криптоанализ может раскрыть открытый текст или ключ, он также может обнаружить слабые места в криптосистемах, что в конечном итоге приведет к предыдущему результату. Раскрытие ключа не криптологическими способами называется компрометацией ключа.
Основное предположение криптоанализа, впервые сформулированное в девятнадцатом веке Датчманом А. Керкхоффом (Dutchman A. Kerckhoffs) состоит в том, что безопасность полностью определяется ключом. Шифрующая, так и расшифровывающая функции общеизвестны, и тайна сообщения, при известном шифротексте, зависит только от секретности ключа.

6
Существует семь основных типов криптоаналитического вскрытия. Для каждого из них, предполагается, что криптоаналитик обладает всей полнотой знания о используемом алгоритме шифрования:
1.
Вскрытие с использованием только шифротекста. У криптоаналитика есть шифротексты нескольких сообщений, зашифрованных одним и тем же алгоритмом шифрования. Задача криптоаналитика состоит в раскрытии открытого текста как можно большего числа сообщений или, что лучше, получении ключа
(ключей), использованного для шифрования сообщений, для дешифрирования других сообщений, зашифрованных теми же ключами.
Дано: C
1
=E
k
(P
1
), C
2
=E
k
(P
2
), . . . C
i
,=E
k
(P
i
).
Получить: Либо P
1
, P
2
, . . . Pi; k; либо алгоритм, как получать P
i
+
1
из
C
i
+
1
=E
k
(P
i
+
1
).
2.
Вскрытие с использованием открытого текста. У криптоаналитика есть доступ не только к шифротекстам нескольких сообщений, но и к открытому тексту этих сообщений. Его задача состоит в получении ключа (или ключей), использованного для шифрования сообщений, для дешифрирования других сообщений, зашифрованных тем же ключом (ключами).
Дано: P
1,
C
1
=E
k
(P
1
), P
2
, C
2
=E
k
(P
2
), . . ., P
i
, C
i
,=E
k
(P
i
).
Получить: Либо k; либо алгоритм, как получать P
i
+
1
из C
i
+
1
=E
k
(P
i
+
1
)
3.
Вскрытие
с
использованием
выбранного
открытого
текста.
У криптоаналитика не только есть доступ к шифротекстам и открытым текстам нескольких сообщений, но и возможность выбирать открытый текст для шифрования. Это предоставляет больше вариантов, чем вскрытие с использованием открытого текста, так как криптоаналитик может выбирать шифруемые блоки открытого текста, что может дать больше информации о ключе.
Его задача состоит в получении ключа (или ключей), использованного для шифрования сообщений, или алгоритма, позволяющего дешифрировать новые сообщения, зашифрованные тем же ключом (или ключами).
Дано: P
1,
C
1
=E
k
(P
1
), P
2
, C
2
=E
k
(P
2
), . . ., P
i
, C
i
,=E
k
(P
i
), где криптоаналитик может выбирать P
1
, P
2
, . . . P
i

Получить: Либо k; либо алгоритм, как получать P
i
+
1
из C
i
+
1
=E
k
(P
i
+
1
)
4.
Адаптивное вскрытие с использованием открытого текста. Это частный случай вскрытия с использованием выбранного открытого текста. Криптоаналитик не только может выбирать шифруемый текст, но также может строить свой последующий выбор на базе полученных результатов шифрования. При вскрытии с использованием выбранного открытого текста криптоаналитик мог выбрать для шифрования только один большой блок открытого текста, при адаптивном вскрытии с использованием выбранного открытого текста он может выбрать меньший блок открытого текста, затем выбрать следующий блок, используя результаты первого выбора и так далее.
5.
Вскрытие с использованием выбранного шифротекста. Криптоаналитик может выбрать различные шифротексты для дешифрирования и имеет доступ к дешифрированным открытым текстам. Например, у криптоаналитика есть доступ к "черному ящику", который выполняет автоматическое дешифрирование. Его задача состоит в получении ключа.
Дано: C
1
, P
1
=D
k
(C
1
), C
2
, P
2
=D
k
(C
2
), . . . ,C
i
, P
i
=D
k
(C
i
).

7
Получить: k
Такой тип вскрытия обычно применим к алгоритмам с открытым ключом.
Вскрытие с использование выбранного шифротекста иногда также эффективно против симметричных алгоритмов. Иногда вскрытие с использованием выбранного открытого текста и вскрытие с использованием выбранного шифротекста вместе называют вскрытием с использованием выбранного текста.
6.
Вскрытие с использованием выбранного ключа. Такой тип вскрытия означает не то, что криптоаналитик может выбирать ключ, а то, что у него есть некоторая информация о связи между различными ключами.
7.
Бандитский криптоанализ. Криптоаналитик угрожает, шантажирует или пытает кого-нибудь, пока не получит ключ. Взяточничество иногда называется
вскрытием с покупкой ключа. Это очень мощные способы вскрытия, часто являющиеся наилучшим путем взломать алгоритм.
Вскрытия с известным открытым текстом и с использованием выбранного открытого текста встречаются чаще, чем можно подумать. Многие сообщения имеют стандартные начало и окончание, что может быть известно криптоаналитику. Особенно уязвим шифрованный исходный код из-за частого использования ключевых слов: #define, struct, else, return. Те же проблемы и у шифрованного исполнимого кода: функции, циклические структуры и так далее. Вскрытия с известным открытым текстом (и вскрытия с выбранным шифротекстом) успешно использовались в борьбе с немцами и японцами в ходе Второй мировой войны.
Лучшими являются алгоритмы, разработанные открыто.
У криптоаналитиков не всегда есть доступ к алгоритмам, но часто они его получают.
Если алгоритм используется в коммерческой программе безопасности, то это просто вопрос времени и денег, удастся ли дезассемблировать программу и раскрыть алгоритм.
Если же алгоритм используется в системах военной связи, то это просто вопрос времени и денег купить (или украсть) аппаратуру и реконструировать алгоритм.

1.5 Безопасность алгоритмов.
Различные алгоритмы предоставляют различные степени безопасности в зависимости от того, насколько трудно взломать алгоритм. Если стоимость взлома алгоритма выше, чем стоимость зашифрованных данных, данный алгоритм можно считать безопасным.
Если время взлома алгоритма больше, чем время, в течение которого зашифрованные данные должны сохраняться в секрете, то данный алгоритм тоже можно считать вычислительно безопасным. Если объем данных, зашифрованных одним ключом, меньше, чем объем данных, необходимый для взлома алгоритма, то тогда алгоритм, скорее всего, тоже является безопасным.
Здесь употребляется "скорее всего", потому что существует вероятность новых прорывов в криптоанализе и значимость большинства данных падает со временем.
Значимость данных всегда оставалась меньше, чем стоимость взлома системы безопасности, защищающей данные.
Ларс Кнудсен (Lars Knudsen) разбил вскрытие алгоритмов по следующим категориям, приведенным в порядке убывания значимости:
1.
Полное вскрытие. Криптоаналитик получил ключ K, такой, что D
K
(C) = P.
2.
Глобальная дедукция. Криптоаналитик получил альтернативный алгоритм, A, эквивалентный D
K
(C) без знания K.

8 3.
Местная (или локальная) дедукция. Криптоаналитик получил открытый текст для перехваченного шифротекста.
4. Информационная дедукция. Криптоаналитик получил некоторую информацию о ключе или открытом тексте. Такой информацией могут быть несколько бит ключа, сведения о форме открытого текста и так далее.
Алгоритм является безусловно безопасным если, независимо от объема шифротекстов у криптоаналитика, информации для получения открытого текста недостаточно. Только шифрование одноразовым блокнотом невозможно вскрыть при бесконечных ресурсах.
Все остальные криптосистемы подвержены вскрытию с использованием только шифротекста простым перебором возможных ключей и проверкой осмысленности полученного открытого текста. Это называется вскрытием грубой силой.
Криптография больше интересуется криптосистемами, которые тяжело взломать вычислительным способом. Алгоритм считается вычислительно безопасным (или, как иногда называют, сильным), если он не может быть взломан с использованием доступных ресурсов сейчас или в будущем. Термин "доступные ресурсы" является достаточно расплывчатым. Сложность вскрытия можно измерить различными способами:
1.
Сложность данных. Объем данных, используемых на входе операции вскрытия.
2.
Сложность обработки. Время, нужное для проведения вскрытия. Часто называется коэффициентом работы.
3.
Требования к памяти. Объем памяти компьютера, необходимый для вскрытия.
В качестве эмпирического метода сложность вскрытия определяется по максимальному из этих трех коэффициентов. Ряд операций вскрытия предполагают взаимосвязь коэффициентов - более быстрое вскрытие возможно за счет увеличения требований к памяти.
Сложность выражается порядком величин. Если сложность обработки для данного алгоритма составляет 2 128
, то 2 128
операций требуется для вскрытия алгоритма. Если предполагается, что ваши вычислительные мощности способны выполнять миллион операций в секунду, и вы используете для решения задачи миллион параллельных процессоров, получение ключа займет свыше 10 19
лет, что в миллиард раз превышает время существования вселенной.
В то время как сложность вскрытия остается постоянной (пока не будет придуман лучшего способа вскрытия), мощность компьютеров растет. За последние полвека вычислительные мощности феноменально выросли, и нет никаких причин подозревать, что эта тенденция не будет продолжена. Многие криптографические взломы пригодны для параллельных компьютеров: задача разбивается на миллиарды маленьких кусочков, решение которых не требует межпроцессорного взаимодействия. Объявление алгоритма безопасным, потому, что его нелегко взломать, используя современную технику, в лучшем случае ненадежно. Хорошие криптосистемы проектируются устойчивыми к взлому с учетом развития вычислительных средств на много лет вперед.








9
Раздел 2. Математические основы
2.1 Теория информации
Теория информации — один из краеугольных камней вычислительной техники. В данной главе изучается ее отношение к криптографии.
На первом этапе нам потребуется общее представление о разнице между теоретико- информационной стойкостью (или теоретической стойкостью) и вычислительной защищенностью
(или практической стойкостью).
Говоря неформально, криптографическая система называется вычислительно защищенной (или вычислительно стойкой), если наилучший из возможных алгоритмов, взламывающих ее, требует неоправданно высоких затрат вычислительных ресурсов. Принимая во внимание мощность современных компьютеров, можно считать, что 280 операций, необходимых для взлома шифра, это тот предел, выходя за который алгоритмы взлома становятся слишком дорогостоящими. Таким образом, если минимальное число N операций, необходимых алгоритму, атакующему данную криптосистему, больше 280 то говорят, что она вычислительно защищена. Заметим, что никакую реальную систему нельзя обоснованно считать вычислительно защищенной, поскольку мы не сможем доказать оптимальность найденного метода взлома. Поэтому на практике мы утверждаем ее защищенность в вычислительном отношении в том случае, если лучший из известных алгоритмов для ее взлома требует недопустимо большого количества вычислений.
Другой практический подход, связанный с вычислительной защищенностью, состоит в том, чтобы свести взлом системы к решению хорошо изученных трудных проблем.
Например, мы можем попытаться показать, что вскрытие конкретной криптосистемы рав- носильно разложению данного большого целого числа на множители. Такие системы часто называют доказуемо стойкими. Однако при этом стойкость системы обосновывается сведением к трудной задаче, что нельзя считать корректным доказательством.
По существу, вычислительно, или доказуемо, стойкая криптосистема является стойкой по отношению к противнику, чьи вычислительные ресурсы ограничены. Даже в том случае, когда противник обладает большими, но ограниченными ресурсами, он все еще не сможет взломать систему.
При изучении вычислительно защищенных схем необходимо иметь четкие представления о некоторых проблемах:
Нужно позаботиться о длине ключа. Если размер ключа мал, то у противника вполне может хватить ресурсов для взлома криптосистемы.
Важно следить за последними алгоритмическими достижениями и развитием компьютерной техники.
Мы должны быть готовы к тому, что наша криптосистема в какой-то момент будет взломана либо из-за усовершенствования аппаратных средств, либо в результате крупного алгоритмического прорыва.
Большинство криптосистем, активно эксплуатирующихся в настоящее время, вычислительно защищены. Поэтому в каждой из последующих глав мы будем уделять много внимания вычислительной стойкости изучаемых криптосистем.
С другой стороны, система называется абсолютно стойкой или совершенной, если мы не ограничиваем вычислительной мощности противника. Иначе говоря, криптосистема совершенна, если ее нельзя взломать даже с помощью бесконечного числа операций. Сле- довательно, независимо от алгоритмических достижений и совершенства вычислительной техники, абсолютно стойкую схему взломать невозможно. В литературе можно встретить и другой термин, закрепленный за абсолютной стойкостью, а именно, теоретико- информационная стойкость.

10


Поделитесь с Вашими друзьями:
  1   2   3   4   5


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал