Алгебраические основы. Вопросы Криптография основные термины
 Скачать 5.55 Mb.
|
|
КРИПТОГРАФИЯ: ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ Вопросы: 1.1. Криптография: основные термины 1.2. Простейшие шифры 1.3. Криптоанализ 1.4. Безопасность данных 1.5. Криптосистемы 1.6. Требования к секретности и достоверности 1.7. Классификация криптосистем ОСНОВНЫЕ ТЕРМИНЫ Под ключом понимается некая секретная последовательность символов, используемая алгоритмом для криптографического преобразования данных. Шифр – совокупность обратимых преобразований комплекса открытых данных на комплекс зашифрованных данных, которые представлены в виде алгоритма криптографического преобразования. Шифрование представляет собой процесс зашифрования или расшифрования данных. Зашифрование данных – процесс преобразования открытых данных в закрытые при помощи шифра. Расшифрование данных – процесс преобразования зашифрованных данных в открытые, используя при этом шифр. Гаммирование - процесс наложения с помощью некоего закона гамма-шифра на открытые данные. Гамма-шифр – это псевдослучайная двоичная последовательность, генерируемая по заданному алгоритму с целью зашифрования и дешифрования данных. Дешифрирование – процесс трансформации зашифрованных данных в открытый текст без знания ключа и, скорее всего, алгоритма. Под криптостойкостью понимается характеристика шифра, которая определяет его устойчивость к дешифрованию. Чаще всего подобная характеристика определяется периодом времени, необходимым для декодирования. Имитозащита – специальный набор символов, который добавляется к сообщению и предназначен для обеспечения его целостности и аутентификации источника данных. Криптографическая защита – это защита данных при помощи криптографического преобразования, которое включает в себя преобразование информации и (или) выработкой имитовставки. Уравнение зашифрования (расшифрования) – соотношение, которое описывает процесс создания зашифрованных (открытой) данных из открытых (зашифрованных) данных посредством преобразований, заданных алгоритмом криптографического преобразования. Синхропосылка – открытые исходные параметры алгоритма криптографического преобразования. Требования к секретности и достоверности Аппаратная реализация. • высокая скорость работы; • высокая надежность; • высокая стоимость. Программная реализация: • доступность; • простота в использовании; • дешевизна; • низкая надежность ТРЕБОВАНИЯ К СОВРЕМЕННЫМ ШИФРСИСТЕМАМ 1. Шифротекст не должен значительно превышать объем информации. исходной 2. Криптостойкость должна быть обеспечена только секретностью ключа. 3. Стоимость шифрования должна соответствовать стоимости преобразующейся информации. 4. Устойчивость шифра, противолежащего криптоанализу, должна обеспечивать такой уровень, при котором вскрытие шифра невозможно без решения задачи полного перебора ключей. 5. Время шифрования не должно быть большим. 6. Ошибки в шифровании, не должны приводить к искажению и потере информации. ОСНОВНЫЕ ТРЕБОВАНИЯ К СОВРЕМЕННЫМ ШИФРСИСТЕМАМ 1. Алгоритм шифрования должен позволять аппаратную и программную реализацию. 2. Обладание знанием об алгоритме шифрования не должно влиять на степень защиты, устойчивость шифра должна определяться лишь секретностью ключа. 3. Невозможность криптоаналитической атаки открытого текста 4. Небольшое изменение ключа шифрования или открытого текста должно привести к значительному изменению вида зашифрованного текста. 5. Единственный возможный способ раскрытия зашифрованного осуществляться лишь при дешифрации его на секретном ключе, текста а поиск должен ключа дешифрования должен заключаться лишь в полном их переборе. 6. Избыточность информации, которая вносится в зашифрованный текст путем шифрования, желательно должна быть незначительным. 7. Закрытые данные должны поддаваться чтению лишь обладателям секретного ключа шифрования. ТИПЫ КРИПТОГРАФИЧЕСКИХ АТАК 1. Криптоаналитическая атака при наличии лишь известного закрытого текста. 2. Криптоаналитическая атака при наличии лишь известного закрытого текста С. 3. Криптоаналитическая атака методом анализа частотности закрытого текста. 4. Криптоаналитическая атака методом полного перебора всех возможных ключей. ОБЩАЯ СХЕМА ПЕРЕДАЧИ КЛЮЧЕЙ 1. Шифры перестановки: 1.1. Шифр перестановки ―скитала‖ (цилиндр + намотанная кожа). 1.2. Шифрующие таблицы (запись цифр алфавита в матрицу). 1.3. Применение магических квадратов. Все традиционные криптографические системы можно подразделить на: Шифрование перестановкой заключается в том, что символы шифруемого текста переставляются по определенному правилу в пределах некоторого блока этого текста. При достаточной длине блока, в пределах которого осуществляется перестановка, и сложном неповторяющемся порядке перестановки можно достигнуть приемлемой для простых практических приложений стойкости шифра. 2. Шифры простой замены: 2.1. Полибианский квадрат. 2.2. Система шифрования Цезаря (сдвиг текста на определенное число позиций). 2.3. Аффинная система подстановок Цезаря. 2.4. Система Цезаря с ключевым словом. 2.5. Шифрующие таблицы Трисемуса. 2.6. Биграммный шифр Плейфейра. 2.7. Криптосистема Хилла. 2.8. Система омофонов. Шифрование заменой (подстановкой) заключается в том, что символы шифруемого текста заменяются символами того же самого (простая замена), также одно или нескольких других алфавитов (сложная замена) в соответствии с заранее обусловленной схемой замены. 3. Шифры сложной замены: 3.1. Шифр Гронсфельда. 3.2. Система шифрования Вижинера. 3.3. Шифр ―двойной квадрат‖ Уитстона. 3.4. Одноразовая система шифрования. 3.5. Шифрование методом Вернама. 3.6. Роторные машины. 4. Шифрование методом гаммирования. Шифрование гаммированием заключается в том, что символы шифруемого текста складываются с символами некоторой случайной последовательности, именуемой гаммой шифра. Стойкость шифрования определяется в основном длиной (периодом) неповторяющейся части гаммы шифра. Данный способ является одним из основных для шифрования информации в автоматизированных системах. 5. Шифрование, основанное на аналитических преобразованиях шифруемых данных. Шифрование аналитическим преобразованием заключается в том, что шифруемый текст преобразуется по некоторому аналитическому правилу (формуле). Например, можно использовать правило умножения вектора на матрицу, причем умножаемая матрица является ключом шифра, а символами умножаемого вектора последовательно служат символы шифруемого текста. Другим примером может служить использование так называемых однонаправленных функций для построения криптосистем с открытым ключом КЛАССИФИКАЦИЯ МЕТОДОВ КРИПТОГРАФИЧЕСКОГО ЗАКРЫТИЯ ИНФОРМАЦИИ КЛАССИФИКАЦИЯ СОВРЕМЕННЫХ КРИПТОГРАФИЧЕСКИХ СИСТЕМ Классические криптографические методы и алгоритмы разделяют на два основных типа: симметричные (с секретным ключом), асимметричные (с открытым ключом) В симметричных методах для шифрования и расшифровывания используется один и тот же секретный ключ. СИММЕТРИЧНОЕ ШИФРОВАНИЕ Общая технология использования симметричного метода шифрования К достоинствам симметричных методов относят высокое быстродействие и простоту. Основным недостатком указанных методов является то, что ключ должен быть известен и отправителю, и получателю. Это существенно усложняет процедуру назначения и распределения ключей между пользователями. По существу, в открытых сетях должен быть предусмотрен физически защищенный канал передачи ключей. Названный недостаток послужил причиной разработки методов шифрования с открытым ключом – асимметричных методов Наиболее известным стандартом на симметричное шифрование с закрытым ключом является стандарт для обработки информации в государственных учреждениях США DES (Data Encryption Standard). Коммерческий вариант алгоритма DES использует ключ длиной 56 бит, что требует от злоумышленника перебора 72·10^12 возможных ключевых комбинаций. Более криптостойкая (но втрое менее быстродействующая) версия алгоритма DES - Triple DES (тройной DES) позволяет задать ключ длиной 112 бит IDEA (International Data Encryption Algorithm), отличающийся применением ключа длиной 128 бит. Он считается более стойким, чем DES. Отечественный стандарт шифрования данных - ГОСТ 28147-89 “Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования” определяет алгоритм симметричного шифрования с ключом длиной до 256 бит. Асимметричные методы используют два взаимосвязанных ключа: для шифрования и расшифрования. Один ключ является закрытым и известным только получателю. Его используют для расшифрования. Второй из ключей является открытым, т.е. он может быть общедоступным по сети и опубликован вместе с адресом пользователя. Его используют для выполнения шифрования. Использование асимметричного метода шифрования с открытым ключом Как отмечалось, основным недостатком асимметричных алгоритмов является их низкое быстродействие: данные алгоритмы в несколько тысяч раз медленнее симметричных алгоритмов. Поэтому для исключения данного недостатка используют технологии сочетания симметричных и асимметричных методов шифрования. В частности, текст шифруется быстродействующим симметричным алгоритмом, а секретный (случайный) ключ, сопровождающий текст, - асимметричным алгоритмом В настоящее время наиболее известными и надежными являются следующие асимметричные алгоритмы: алгоритм RSA (Rivest, Shamir, Adleman); алгоритм Эль Гамаля. СИММЕТРИЧНЫЕ СИСТЕМЫ С ЗАКРЫТЫМ (СЕКРЕТНЫМ) КЛЮЧОМ Различают три основных способа шифрования: поточные шифры; блочные шифры; блочные шифры с обратной связью. Криптосистем и их основные характеристики Поточное шифрование состоит в том, что биты открытого текста складываются по модулю 2 с битами псевдослучайной последовательности. К достоинствам поточных шифров относятся высокая скорость шифрования, относительная простота реализации и отсутствие размножения ошибок. Недостатком является необходимость передачи информации синхронизации перед заголовком сообщения, которая должна быть принята до расшифрования любого сообщения. Это обусловлено тем, что если два различных сообщения шифруются на одном и том же ключе, то для расшифрования этих сообщений требуется одна и та же псевдослучайная последовательность. Такое положение может создать угрозу криптостойкости системы. Поэтому часто используют дополнительный, случайно выбираемый ключ сообщения, который передается в начале сообщения и применяется для модификации ключа шифрования. В результате разные сообщения будут шифроваться с помощью различных последовательностей. При блочном шифровании открытый текст сначала разбивается на равные по длине блоки, затем применяется зависящая от ключа функция шифрования для преобразования блока открытого текста длиной m бит в блок шифртекста такой же длины. Достоинством блочного шифрования является то, что каждый бит блока шифртекста зависит от значений всех битов соответствующего блока открытого текста, и никакие два блока открытого текста не могут быть представлены одним и тем же блоком шифртекста. Поэтому в настоящее время подавляющее большинство применяемых на практике как симметричных систем с закрытым (секретным) ключом так и асимметричных систем с открытым ключом представляют собой блочные системы, как правило, с длиной блоков в 64 бита. Алгоритм блочного шифрования может использоваться в различных режимах. Четыре режима шифрования алгоритма DES практически применимы к любому блочному шифру. Наиболее часто применяются системы блочного шифрования с обратной связью. Как и при простом блочном шифровании, сообщения разбиваются на ряд блоков. Для преобразования этих блоков в блоки шифртекста используются специальные функции шифрования. Однако, если в блочном шифре такая функция зависит только от ключа, то в блочных шифрах с обратной связью она зависит как от ключа, так и от одного или более предшествующих блоков шифртекста. Достоинством криптосистем с блочного шифрования с обратной связью является возможность применения их для обнаружения манипуляций сообщениями, производимых активными перехватчиками. При этом используется факт размножения ошибок в таких шифрах, а также способность этих систем легко генерировать код аутентификации сообщений. Основным недостатком систем блочного шифрования с обратной связью является размножение ошибок и сложность при разработке и реализации. Математические основы криптографии Вспомним какие бывают числа Используемые в математике числовые множества включают в себя: • Натуральные числа — числа, получаемые при естественном счѐте: • Целые числа — числа, получаемые объединением натуральных чисел с множеством чисел противоположных натуральным и нулѐм: • Рациональные числа — числа, представимые в виде дроби m/n (n ≠ 0), где m — целое число, а n — натуральное число. ℚ = *… − 1, − 1 2 , 0, 1 2 , 1, … + • Действительные (вещественные) числа — множество чисел, представляющее собой расширение множества рациональных чисел, включающее иррациональные числа (те, которые нельзя представить в виде дроби с целыми числами, например 2 3 ) • Комплексные числа — расширение множества действительных чисел, включающее мнимую единицу 𝑖 = −1 (ℂ) Что для нас важно? Главным образом в криптографии используются НАТУРАЛЬНЫЕ числа. Мы не работаем с дробными, иррациональными и комплексными числами. В криптографии используются целые числа!!! Целые числа делятся на: • простые; • составные. Целое число d является делителем n, тогда и только тогда, когда можно записать произведение n = k · d и записывается d | n. Целое число р (р≥1) является простым, если его делителями являются только 1 и р. Например: 2, 3, 5, 7, 11, 13, 17<и т.д. Числа, имеющие более 2–х делителей являются составными. Целые числа Любое целое число n>1 может быть представлено единственным образом как произведение простых чисел в соответствующих степенях. Такое представление называется каноническим разложением Евклида. Процедура получения такого разложения называется разложением на простые сомножители или факторизацией числа. На настоящий момент не известны быстрые алгоритмы разложения чисел. На этом основаны большинство современных криптосистем. Получение простых чисел является одной из основных задач криптографии. Евклид показал, что существует бесконечное множество простых чисел, однако их удельный вес среди других чисел невелик. Алгоритмы получения простых чисел Один из первых алгоритмов был предложен во времена Евклида. Базируется на следующих теоремах: Алгоритм Эратосфена построения последовательности простых чисел в ряду целых чисел, не превосходящих данного целого N. Выписываем ряд чисел 1,2,<, N (1.6) Первое простое число в ряду (1.6) – 2. Вычеркиваем из ряда (1.6) все числа кратные 2, кроме самого числа 2. Первое, оставшееся после 2, простое число – 3. Вычеркиваем из ряда (1.6) все числа кратные 3, кроме самого числа 3. Первое, следующее за 3, невычеркнутое простое число 5. Вычеркиваем из ряда (5) все числа кратные 5, кроме числа 5. И т.д. Когда указанным способом вычеркнуты все числа, кратные простых, меньше простого p, то все невычеркнутые меньшие 𝑝 2 будут простые. Пример. 2, 3, 4, 5, 6, 7, 8, 9, 10. √10 ≈ 3 2, 3 < 10 => вычеркиваем те числа, которые делятся на 2 и 3. Все оставшиеся после вычеркивания числа – простые. Попытка формальным образом определить простые числа привела к отрицательному результату. Составные числа Определение Если a делится на b нацело, мы будем говорить, что b делит a. При этом а называется кратным числа b, b – делителем числа а. Число а можно представить как a = q *b , где q – полное частное. Таким образом, k представляется произведением b на целое число ( и тем самым делится на b по определению l. Что и требовалось доказать. Бинарный алгоритм Определение. Два числа называются попарно простыми, если их НОД равен 1 Пример Алгоритм Евклида Исторически одним из первых инструментов определения взаимно простых чисел стал алгоритм Евклида. Алгоритм Евклида Расширенный алгоритм Евклида Расширенный алгоритм Евклида Одним из существенных недостатков алгоритма Евклида является применение операций деления. Это увеличивает его вычислительную сложность. Пример Доказать, являются ли числа попарно простыми: Алгебраические свойства Что еще для нас важно? В криптографии как правило используется не бесконечное множество натуральных чисел, а вполне себе конечное. О чем речь? Об алгебраических структурах. Алгебраическая структура – некоторое множество элементов (не обязательно чисел) с определенных на ней операциях алгебры. То есть их бывает много? Как правило 9. Чтобы понять в чем их отличие нужно разобрать некоторые алгебраические свойства Давайте на время забудем про известные нам операции алгебры , такие как сложение, умножение, деление и т.д. Вместо этого будем говорить, что у нас есть некоторая неопределенная операция « ∘ » И пусть она будет бинарной, то есть, операцией над двумя элементами. Какие алгебраические свойства у операции бывают? Коммутативность – свойство операции ∘ при которой a ∘ b = b ∘ a Сможете сказать какие известные вам операции являются коммутативными? 1) Конечно же + (известно со школы – от перестановки слагаемых сумма не меняется). 3+2 = 2+3. Еще? 2) Произведение. Ее, вы знали. 3*2 = 2*3. Может что-то из дискретной математики? 3) Молодец! Конъюнкция и дизъюнкция. А из теории множеств? 4) Объединение, пересечение и симметрическая разность. Супер! ∧ ∨ + ∙ ∪ ∩ Ок, это было просто, а какие тогда не коммутативны? 1) Хм. Это ты сам догадался или мне послышалось? Возведение в степень , да. 2 3 ≠ 3 2 2) Матрицы, матрицы... Ага. Перемножение матриц ! Какие они бывают? Ассоциативность – свойство операции ∘ при которой (a ∘ b) ∘ c = a ∘ (b ∘ c). Тут и без примеров поймете (: Дистрибутивность – определяется как проявление двух бинарных операций (бинарные – операции над двумя элементами) (возьмем ∘ и ∴) для которых (a ∘ b) ∴ c = a ∴ c ∘ b ∴ c. Сложно? Да бросьте! Например, для операций (+, *): (a+b)*c = a*c + b*c Идемпотентность – когда повторная операция уже не меняет значения. Например, −5 = 5; −5 = 5 и тд. Сколько бы не брали модуль от модуля ничего уже не изменится Даже обидно. Вроде разобрались. У нас есть некоторые операции и свойства этих операций. А еще мы будем работать с натуральными числами. Все супер, переходим к алгебраическим структурам. Так так так стоп! Ничего не понятно, что за нейтральный элемент , что за обратный элемент и нужны же примеры ! Ок, справедливо. Давайте разберѐмся. Кольцо - Множество с двумя операциями (сложение и умножение), обладающими свойством ассоциативности (a ∙ b) ∙ c = a ∙ (b ∙ c), (a+b)+c=a+(b+c) - При этом сложение коммутативно 𝑎 + 𝑏 = 𝑏 + 𝑎 - Имеется нейтральный элемент по сложению 𝑎 + 0 = 0 + 𝑎 = 𝑎 - Имеется обратный элемент по сложению 𝑎 + −𝑎 = −𝑎 + 𝑎 = 0 - Выполняется дистрибутивность этих двух операций 𝑎 + 𝑏 ∙ 𝑐 = 𝑎 ∙ 𝑐 + (𝑏 ∙ 𝑐) 𝑐 ∙ 𝑎 + 𝑏 = 𝑐 ∙ 𝑎 + (𝑐 ∙ 𝑏) Поле - Группа с четырьмя операциями, имеющие свойства, близкие к свойствам четырех основных операций с числами (сложения, умножения, вычитания, деления) - Выполняются коммутативность, ассоциативность и дистрибутивность для сложения и умножения - Имеется нейтральный и обратный элемент по сложению и по умножению Поле Галуа (конечное поле) - Поле, количество элементов в котором не бесконечно. |