Математические основы криптологии
 Скачать 1.3 Mb.
|
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ТАГАНРОГСКИЙ ГОСУДАРСТВЕННЫЙ РАДИОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ  Кафедра безопасности информационных технологий  Галуев Г.А. МАТЕМАТИЧЕСКИЕ ОСНОВЫ КРИПТОЛОГИИ Учебно-методическое пособие  Таганрог 2003УДК 681.3.067(075.8) Галуев Г.А. Математические основы криптологии: Учебно-методическое пособие. Таганрог: Изд-во ТРТУ 2003.-120с. В настоящем пособии изложены математические элементы теории чисел и теории поля, лежащие в основе построения современных криптографических систем, а также вопросы синтеза и анализа криптоалгоритмов. Пособие предназначено для изучения лекционного курса "Математические основы криптологии" студентами специальностей 075400, 075300, 075600. Табл. 4. Ил. 7. Библиогр.: 7 назв. Рецензент И. А. Каляев, д.т.н., профессор, директор НИИ МВС  СОДЕРЖАНИЕ 1. Основные понятия криптографии. История развития криптографии, примеры классических криптосистем. Современные криптосистемы. Схемы атаки на шифр (группы методов дешифрования). 4 2. Стойкость криптографических систем и алгоритмов. Информационно - теоретический подход и подход на основе теории сложности. 15 3. Элементы теории чисел: основные понятия и теоремы. 24 4. Элементы конечного поля. Основные понятия и свойства алгебраических структур. 38 5. Элементы теории конечного поля. Основные понятия и теоремы. 48 6. Элементы теории конечного поля. Строение конечных полей. Основные свойства и методы построения конечных полей. 56 7. Элементы теории конечного поля. Многочлены над конечными полями. 64 8. Элементы теории конечного поля. Линейные рекуррентныепоследовательности над конечными полями. 74 9. Дополнительные математические элементы криптографии. 82 10. Общая характеристика различных типов шифров и классов криптосистем. 90 11. Методы формирования псевдослучайных последовательностей. Схема открытого распределения ключей Диффи и Хеллмана. 99 12. Алгоритм RSA и алгоритм Эль Гамаля работы криптосистем с открытым ключом. Цифровая подпись. Алгоритм цифровой подписи Эль Гамаля. 106 Список рекомендуемой литературы. 117 Основные понятия криптографии. История развития криптографии, примеры классических криптосистем. Современные криптосистемы. Схемы атаки на шифр (группы методов дешифрования). Криптология – наука о создании и анализе систем безопасности связи. Говоря о криптологии, иногда имеют в виду не безопасную, а секретную связь. Однако секретность является только одним элементом безопасности или целостности информации. Целостность информации связана с вопросами подлинности, своевременности, согласованности и т.д., а также со всеми вопросами, обычно возникающими с документными записями. Криптологию принято делить на две части: криптографию и криптоанализ. Криптография - это наука о методах обеспечения секретности и подлинности (идентичности) данных при их передаче по линиям связи или хранении. Криптоанализ – это наука о методах раскрытия или подделки данных. Иными словами криптография и криптоанализ нацелены на решение взаимно обратных задач. Цели криптографии менялись на протяжении всей её истории. Сначала она служила только для обеспечения секретности, чтобы препятствовать несанкционированному доступу к информации, передаваемой по военным и дипломатическим каналам связи. По мере развития информатики криптография носила широкое применение для защиты информации во многих прикладных областях: истории болезни, юридические и финансовые документы, закрытые коммерческие данные и т.п. В настоящие время криптография используется не только не только для защиты информации от несанкционированного доступа, но и для обеспечения её подлинности и целостности криптографических систем применяются физическая защита, различные организационно - технические мероприятия и стеганография. Стеганография занимается методами скрытия самого факта передачи сообщения (симпатические чернила, молоко для написания текста, шумоподобные методы радиопередачи и д.р.). Наиболее эффективная защита информации обеспечивается сочетанием всех этих способов. Открытым текстом называют исходные сообщение, которое должен защищать криптограф. Шифр - это множество обратимых преобразований формы открытого текста, проводимых с целью его защиты. Процесс применения обратимого преобразования шифра к открытому тексту называется зашифрованием, а результат этого преобразования - шифротекстом или криптограммой. Соответственно процесс обратного преобразования шифротескта в открытый текст называется расшифрованием. Совокупность данных, определяющих конкретное преобразование из множества преобразований шифра, называют ключом. Такой ключ, в частности, может передаваться отправителем получателю заранее до отправления криптограммы каким - либо надежно защищенным способом. Дешифрование - атака на шифр, раскрытие шифра со стороны взломщика. Специальным видом шифра является код. Код - это своего рода словарь, где элементы открытого текста (буквы, сочетания букв, слова и даже фразы) так называемые кодвеличины заменяются группами символов (букв, цифр, других знаков). Эти группы символов называют кодообозначениями. Принципиальной разницы между шифром и кодом нет. Одним из основных понятий криптографии является стойкость. Стойкость - это способность противостоять попыткам хорошо вооруженного современной техникой и знаниями криптоаналитика дешифровать перехваченный шифротекст, раскрыть ключи шифра или нарушить целостность и подлинность информации. В истории развития криптографии можно условно выделить три основных этапа. Первый период - эра донаучной криптологии, являющейся уделом узкого круга искусных умельцев. Началом второго периода можно считать 1949 год, когда появилась работа известного американского ученого Клода Шеннона «Теория связи в секретных системах». В этой работе проведено фундаментальное научное исследование шифров и вопросов их стойкости, благодаря чему криптология оформилась как прикладная математическая наука. Третий период связывают с появлением в 1976 году работы У. Диффи и М. Хеллмана «Новые направления в криптографии, « где показано, что секретная связь возможна без предварительной передачи секретного ключа. Ещё несколько веков назад само применение письменности можно было рассматривать как способ закрытия информации, т.к. владение письменностью было уделом немногих. Один из самых древних шифротекстов, написанных клинописью, был обнаружен в Месопотамии и датируется XX веком до н.э. Известны также древнеегипетские религиозные и медицинские шифротексты. В середине IX века до н.э. использовалось шифрующие устройство - скиталь для получения шифра перестановки. При шифровании слова писались на узкую ленту, намотанную на цилиндр, вдоль образующей этого цилиндра (скиталя). После этого лента разматывалась и на ней оставались переставленные буквы исходного текста. Ключом в этом случае являлся диаметр этого цилиндра.  В начале нашей эры создается шифр замены. Так в 56 году н.э. во время войны с галлами Юлий Цезарь использует шифр простой замены, строящийся следующим образом: Под алфавитом открытого текста пишется тот же алфавит со сдвигом на три позиции по циклу. При шифровании буквы открытого текста у верхнего алфавита заменялись буквами нижнего алфавита. А Б В Г Д Е Ж … Э Ю Я Г Д Е Ж … Э Ю Я А Б В Более сложной разновидностью шифра замены является «квадрат Полибия».
При шифровании буквы открытого текста заменяются парой чисел: номер столбца и номер строки соответствующей буквы в таблице
В начале XV века н.э. Альберти предложил оригинальный шифр замены, на основе двух концентрических кругов, по окружности которых записывались алфавиты открытого текста и шифротекста. При этом шифроалфавит был не последовательным АБВГ… ЭЮЯ, а произвольным АЭВЮГ… и мог быть еще и смещен на любое число позиций.  Здесь была впервые реализована идея увеличения стойкости шифросистемы путем повторения шифрования с помощью разных шифросистем (меняя последовательность шифроалфавита и его сдвиг относительно алфавита открытого текста). В XVI веке н.э. французский дипломат Вижинер предложил оригинальный шифр сложной замены, получивший впоследствии название системы Виженера
АЛГОРИТМ ШИФРОВАНИЯ: 1. Под каждой буквой открытого текста записываются буквы ключи, повторяющие ключ требуемое число раз (чтобы покрыть все буквы текста). 2. Шифруемый текст по подматрице МОРЕ заменяется буквами, расположенными на пересечении линий, соединяющих буквы первой строки и буквы ключа, находящейся под ней.
В строках М,О,Р,Е отыскиваются буквы шифрованного текста и заменяются буквами первой строки. Это шифр сложной замены или многоалфавитный шифр замены. В тоже время Ф. Бекон впервые предложил представление букв алфавита пятизначным двоичным кодом: А - 00001, Б - 00010… Такой способ шифрования обладал слабой стойкостью, однако эта идея, через три столетия легла в основу электрической и электронной связи на основе кодов Морзе, Бодо, телеграфных кодов. Известный математик К. Гаусс в 18 - 19 веках создал шифр с многократной подстановкой или равночастный шифр в основе которого лежит прием рандомизации (random - случайный) открытого текста, который преобразовался в шифротекст, содержащий символы большего алфавита. При этом часто встречающиеся буквы открытого текста заменяются случайными символами из большего алфавита. В результате все символы шифротекста равночастны. В нашем столетии американский ученый Вернам предложил систему побитового шифрования открытого текста, представленного телеграфным двоичным кодом, когда каждый бит преобразуется с использованием бита ключа по алгоритму  Сложение по модулю два. Вернам предполагал использовать ключ только один раз. Длина ключа равна длине шифруемого открытого текста. Впоследствии К. Шеннон доказал что такой шифр не раскрываем. Однако сложности формирования, хранения и передачи ключа, длина которого равна длине открытого текста делают такой метод очень непрактичным и дорогостоящим В целом при построении шифров могут использоваться ключи разных типов: долговременные, суточные и сеансовые (для передачи каждого конкретного сообщения). В настоящие время вместо понятия шифра используется понятие криптографической системы с секретным ключом, которая задается следующими пятью компонентами: 1.   - пространство открытых текстов2.  - пространство шифрованных текстов3.  - пространство ключей4.  - ( ) множество преобразований зашифрования 5.  ( ) - множество преобразований расшифрования  Преобразования и для всех ( ) и любого открытого текста  должны удовлетворять условию  Согласно основному правилу Керкхофа множества и могут быть известны не только криптографу, но и криптоаналитику. Секретность же сообщения обеспечивается сокрытием того факта, какое именно преобразование из известного множества используется для зашифрования.Современные криптосистемы с секретным ключом подразделяются на блочные и потоковые. Блочная криптосистема разбивает открытый текст  на блоки и зашифровывает каждый блок с помощью одного и того - же обратимого преобразования , выбранного в соответствии с ключом К Для повышения стойкости блочных криптосистем используется режим сцепления блоков шифра (СВС). Если обозначить через преобразование зашифрования в режиме сцепления блоков  шифрованного текста из блоков открытого текста, то процесс этого зашифрования в режиме сцепления блоков шифра описывается соотношением Начальные значение  является несекретным и передается вместе с шифротекстом.Соответственно процесс расшифрования описывается соотношением Иногда используют более сложные режимы сцепления блоков шифра   Поточная криптосистема разбивает открытый текст М на буквы или биты m1,m2,… и зашифровывает каждый знак  с помощью обратимого преобразования , выбранного в соответствии со знаком  ключевого потока  . Такие системы иногда называют системами гаммирования, а последовательность называют гаммой.Примерами поточной криптосистемы является система Вернама (о которой говорилось выше), где  В свою очередь поточные криптосистемы делятся на синхронные и самосинхронизирующиеся. Синхронные поточные криптосистемы характеризуются тем, что, в отличие от самосинхронизирующихся, в них ключевой поток получается независимо от открытого и шифрованного текстов.Самосинхронизирующиеся поточные криптосистемы характеризуется тем, что каждый знак ключевого потока (гаммы) в любой момент времени определяется фиксированным числом предшествующих знаков шифротекста. Алгоритм, который вырабатывает ключевой поток (гамму) может быть либо детерминированным, либо случайным, Этот алгоритм называют генератором ключевого потока. Если такой генератор детерминированный, то он должен зависеть от секретного ключа. Если он случайный то сам является секретным ключом, но очень большой длины, что непрактично. Описать работу генератора ключевого потока можно на языке теории автоматов, используя понятия функции переходов F и функции выходов f. Тогда работу синхронной поточной криптосистемы описать соотношениями  Начальные значения  (начальное состояние автомата) может быть функцией от ключа k.Соответственно работа самосинхронизирующейся поточной криптосистемы описывается соотношением  Сложность построения поточных криптосистем связана с необходимостью построения хороших генераторов ключей, чтобы, например, нельзя было бы по известному отрезку открытого и шифрованного текстов восстановить всю ключевую последовательность. Одним из эффективных подходов и построению генераторов ключей является счетчиковым метод, предположенный Диффи и Хеллманом. В общем случае работа генератора ключей описывается соотношением  Функция перехода F не зависит от ключа, но преобразование F выбирается так что генерирует перебор всех или почти всех возможных состояний генератора при изменении времени i=1,2,… В качестве F используется преобразование регистров сдвига с линейной обратной связью, вырабатывающие последовательности максимального периода, или просто счетчики (состояния которых меняются пребыванием единицы) с заданным коэффициентом пересчета (счетчики о заданному модулю). В качестве функции выхода f используется преобразование зашифрования блочного шифра.В последнее время широкое распространение получили криптосистемы с открытым ключом, построенные на основе предложенных Диффи и Хеллманом принципов открытого шифрования и открытого распределения ключей (1976 г.). Также криптосистемы называют также двух ключевыми криптосистемами или асимметричными криптосистемами, в то время как обычные криптосистемы с секретным ключом называют симметричными криптосистемами. Принципы построения таких криптосистем и лежащих в их основе криптоалгоритмов рассмотрим на последующих лекциях. Современный уровень развития электронной и информационной технологий позволяет криптоаналитику относительно легко получить доступ к передаваемым по линиям и системам связи сообщениям, как обычного типа, так и секретным в виде криптограмм или шифротекстов. В связи с этим, основной задачей криптоаналитиков является атака на криптограмму при неизвестном ключе с целью раскрытия (дешифрования) шифра. В целом, в зависимости от уровня доступной криптоаналитику информации, можно выделить четыре возможные схемы атаки на шифр или четыре типа методов дешифрования: 1. Схема атаки на шифр (методы расшифрования) на основе знания только шифротекста  2. Схема атаки на шифр (методы дешифрования) при известных открытом M и шифрованном C текстах.  Такая ситуация возможна когда приходится шифровать общеизвестные данные, например, дипломатические документы, секретные только до момента их опубликования, или когда с достаточной степенью вероятности можно предполагать наличие в тексте тех или иных слов и выражений. 3. Схема атаки на шифр (методы дешифрования) по выбираемому открытому тексту и соответствующему ему шифрованному тексту, т.е. атака на основе тестирования. Выбираемые  Такая ситуация возможна когда криптоаналитик имеет доступ к шифровальному аппарату или шифрующему преобразованию и может получить для любого выбранного открытого текста соответствующий ему шифротекст.4.Схема атаки на шифр (методы дешифрования для криптосистем с открытым ключом) по выбранным шифротекстам и соответствующим открытым текстам Выбираемые Такая ситуация возможна, когда криптоаналитик имеет доступ к преобразованию расшифрования и может получать для выбранных шифротекстов С соответственно открытые тексты М. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||