ВОПРОСЫ ПО КУРСУ. Вопросы по курсу симметричные криптосистемы. Исторические шифры. Шифр замены, шифр сдвига
Скачать 0.7 Mb.
|
ВОПРОСЫ ПО КУРСУ СИММЕТРИЧНЫЕ КРИПТОСИСТЕМЫ. ИСТОРИЧЕСКИЕ ШИФРЫ. ШИФР ЗАМЕНЫ, ШИФР СДВИГА. Симметричные криптосистемы – способ шифрования, в котором для шифрования и дешифрования применяется один и тот же криптографический ключ. Исторические (т. е. использовавшиеся до 1960 г, докомпьютерная эпоха.) шифры, симметричные по своей природе, служат основой многих современных криптосистем. Алгоритм шифрования (или шифр) — это перевод открытого текста в текст зашифрованный (или шифротекст) с помощью секретного ключа. Этот процесс называют шифрованием. С = Ек(m) где m — открытый текст, Е — шифрующая функция, к — секретный ключ и С — шифротекст. Обратный процесс называют расшифрованием и пишут m = Dk{C) Шифр сдвига Процесс шифрования заключается в замене каждой буквы на другую, отстоящую от исходной на определенное число позиций в алфавите в зависимости от значения ключа. Так, например, если ключ равен 3, то буква «а» исходного текста в шифровке изображается «D», вместо буквы «Ь» появится «Е» и т. д. Математическая модель Если сопоставить каждому символу алфавита его порядковый номер (нумеруя с 0), то шифрование и дешифрование можно выразить формулами модульной арифметики: где x — символ открытого текста, y — символ шифрованного текста, n — мощность алфавита, а k — ключ. Шифротекст возникает после того, как к каждому числу в этой последовательности прибавляется значение ключа к по модулю 26, k, очевидно, — целое число между 0 и 26. Таким образом, шифр сдвига можно интерпретировать как поточный шифр с потоком ключей в виде повторяющейся последовательности. Этот поток, естественно, далек от случайного, вследствие чего криптостойкость шифра сдвига крайне низка. Наивный путь атаки на шифр сдвига состоит в простом переборе возможных значений ключа до тех пор, пока не получится осмысленный текст. Шифр замены Основной недостаток шифра сдвига заключается в том, что существует слишком мало возможных ключей, всего 25. В целях устранения указанного недостатка был изобретен шифр замены. Чтобы описать ключ такого шифра, сначала выписывается алфавит, а непосредственно под ним — тот же алфавит, но с переставленными буквами. Это дает нам правило, по которому буквы открытого текста замещаются символами шифровки. Например, abcdefghi j к Imno p qr s tuvwx y z GOYDSIPELUAVCRJWXZNHBQFTM K Шифрование состоит в замене каждой буквы в открытом тексте на соответствующую ей нижнюю букву. Чтобы расшифровать шифротекст, нужно каждую его букву найти в нижней строке таблицы и заменить ее соответствующей верхней. Количество всех возможных ключей такого шифра совпадает с числом всевозможных перестановок 26 элементов. Если шифр сдвига можно считать поточным шифром, когда шифротекст получается комбинацией открытого текста с потоком ключей, шифр замены похож на более современный блочный шифр, блок в котором состоит из одной английской буквы. Метод взлома – частотный анализ Шифр Виженера Основной недостаток шифров сдвига и замены заключается в том, что каждая буква открытого текста при шифровании заменяется раз и навсегда фиксированным символом. Поэтому при взломе шифра эффективно работает статистика подлежащего языка. Секретный ключ здесь — это короткая последовательность букв (т.е. слово, часто называемое лозунгом), которое повторяется снова и снова, формируя поток ключей. Кодирование заключается в сложении букв открытого текста с буквами потока ключей (воспринимаемых как числа). Заметим, что и в этом примере буква «а» замещается различными символами в зависимости от того, на каком месте открытого текста она стоит. Шифр Виженера все же не очень сложно взломать, опираясь на статистику подлежащего языка. Как только мы узнаем длину ключевого слова, нам останется несколько раз применить тактику взлома шифра сдвига. Существует способ, с помощью которого можно определить длину лозунга, генерирующего поток ключей. Этот способ называют тестом Казисского. Его идея основана на периодичности потока ключей. Кроме того, в естественном языке существуют часто встречаемые буквосочетания: биграммы и триграммы. Учитывая это, возникает надежда, что повторяющиеся наборы символов в шифротексте — след повторений популярных биграмм и триграмм открытого текста. Расстояние между повторениями в таком случае должно быть кратно длине лозунга. Следовательно, вычислив наибольший общий делитель всех таких расстояний, мы получим рабочую гипотезу о длине ключа. Затем применяем каждой n-ой букве (n-длина ключа) частотный анализ, используя частотные гистограммы. СИММЕТРИЧНЫЕ КРИПТОСИСТЕМЫ И КРИПТОСИСТЕМЫ С ОТКРЫТЫМ КЛЮЧОМ. Криптографическая система с открытым ключом (разновидность асимметричного шифрования, асимметричного шифра) — система шифрования при которой открытый ключ передаётся по открытому (то есть незащищённому) каналу и используется для шифрования сообщения. Для расшифровки сообщения используется закрытый ключ. Взаимосвязанность ключей Например, если Алиса отправляет Бобу сообщение защищенное симметричным шифрованием, ей необходимо предоставить Бобу тот же ключ, который она использовала для шифрования, чтобы он смог прочитать сообщение. Это означает, что если злоумышленник перехватит его, он сможет получить доступ к зашифрованной информации. Однако, если Алиса использует вместо этого асимметричный метод, она шифрует сообщение с помощью открытого ключа Боба, поэтому Боб сможет расшифровать его с помощью своего приватного ключа. Таким образом, асимметричное шифрование обеспечивает более высокий уровень безопасности, потому что даже если кто-то и перехватит ваши сообщения и найдет открытый ключ, он не сможет ничего с этим сделать. Длина ключей Другое функциональное различие между симметричным и асимметричным шифрованием связано с длиной ключей, которые измеряются в битах и напрямую связаны с уровнем безопасности каждого алгоритма. В симметричных системах ключи подбираются случайным образом, а их общепринятая длина варьируется между 128 и 256 бит в зависимости от требуемого уровня безопасности. В асимметричном шифровании между открытым и приватным ключами должна существовать математическая связь, то есть их связывает определенная математическая формула. По этой причине злоумышленники могут использовать этот шаблон для взлома шифра, в свою очередь асимметричные ключи должны быть намного длиннее, чтобы обеспечить эквивалентный уровень безопасности. Разница в длине ключа настолько существенная, что 128-битный симметричный ключ и 2048-битный асимметричный ключ обеспечивают примерно одинаковый уровень безопасности. Преимущества и недостатки У этих двух видов шифрования присутствуют как преимущества так и недостатки относительно друг друга. Алгоритмы симметричного шифрования намного быстрее и требуют меньше вычислительной мощности, но их основным недостатком является распределение ключей. Поскольку один и тот же ключ используется для шифрования и дешифрования информации, этот ключ должен быть передан всем, кому потребуется доступ, что естественно создает определенные риски (как это было описано ранее). В свою очередь, асимметричное шифрование решает проблему распределения ключей, используя открытые ключи для шифрования, а приватные для дешифрования. Компромисс заключается в том, что асимметричные системы очень медленны по сравнению с симметричными и требуют гораздо большей вычислительной мощности из-за длины ключа. БЛОЧНЫЕ ШИФРЫ. АЛГОРИТМ DES. DES (англ. Data Encryption Standard) — алгоритм для симметричного шифрования, разработанный фирмой IBM и утверждённый правительством США в 1977 году как официальный стандарт. Размер блока для DES равен 64 битам. В основе алгоритма лежит сеть Фейстеля с 16 циклами (раундами) и ключом, имеющим длину 56 бит. Алгоритм использует комбинацию нелинейных (S-блоки) и линейных (перестановки E, IP, IP-1) преобразований. Схема шифрования алгоритма DES Исходный текст — блок 64 бит. Процесс шифрования состоит из начальной перестановки, 16 циклов шифрования и конечной перестановки. Начальная перестановка Исходный текст T (блок 64 бит) преобразуется c помощью начальной перестановки IP которая определяется таблицей 1:
По таблице первые 3 бита результирующего блока{IP}(T) после начальной перестановки {IP} являются битами 58, 50, 42 входного блока T, а его 3 последние бита являются битами 23, 15, 7 входного блока. Циклы шифрования Основная функция шифрования (функция Фейстеля) Таблица 2. Функция расширения E 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 Генерирование ключей {\displaystyle k_{i}} Ключи k_i получаются из начального ключа k (56 бит = 7 байтов или 7 символов в ASCII) следующим образом. Добавляются биты в позиции 8, 16, 24, 32, 40, 48, 56, 64 ключа k таким образом, чтобы каждый байт содержал нечетное число единиц. Это используется для обнаружения ошибок при обмене и хранении ключей. Затем делают перестановку для расширенного ключа (кроме добавляемых битов 8, 16, 24, 32, 40, 48, 56, 64). Такая перестановка определена в таблице 5. Блочные шифры. Алгоритм AES (Rijndael). Блочные шифры. ГОСТ 28147-89. РЕЖИМЫ РАБОТЫ БЛОЧНЫХ ШИФРОВ. Режим шифрования — метод применения блочного шифра (алгоритма), позволяющий преобразовать последовательность блоков открытых данных в последовательность блоков зашифрованных данных. При этом для шифрования одного блока могут использоваться данные другого блока. Обычно режимы шифрования используются для изменения процесса шифрования так, чтобы результат шифрования каждого блока был уникальным вне зависимости от шифруемых данных и не позволял сделать какие-либо выводы об их структуре. Это обусловлено, прежде всего, тем, что блочные шифры шифруют данные блоками фиксированного размера, и поэтому существует потенциальная возможность утечки информации о повторяющихся частях данных, шифруемых на одном и том же ключе. - ЕСВ. Этот режим прост в обращении, но слабо защищен от возможных атак с удалениями и вставками. Ошибка, допущенная в одном из битов шифротекста, влияет на целый блок в расшифрованном тексте. - СВС— наилучший способ эксплуатации блочного шифра, поскольку предназначен ^\ля предотвращения потерь в результате атаки с использованием удалений и вставок. Здесь ошибочный бит шифротекста при расшифровании не только превраш;ает в ошибочный блок, в котором содержится, но и портит один бит в следующем блоке открытого текста, что можно легко определить и интерпретировать как сигнал о предпринятой атаке. - OFB. При таком методе блочный шифр превращается в поточный. Режим обладает тем свойством, что ошибка в один бит, просочившаяся в шифротекст, дает только один ошибочный бит в расшифрованном тексте. - CFB. Как и в предыдущем случае, здесь блочный шифр трансформируется в поточный. Отдельная ошибка в криптограмме при этом влияет как на блок, в котором она была допущена, так и на следующий блок, как при режиме СВС. Режим ЕСВ Режим ЕСВ (Electronic Code Book — электронная кодовая книга) является простейшим среди стандартных способов использования блочного шифра. Данные т , которые предстоит зашифровать, делятся на блоки по п битов: m1, m2, ... , mq. Последний из них, при необходимости, дополняют до длины п. По ним определяются блоки Ci, ... , Cq как результат воздействия шифрующей функции С режимом ЕСВ связан ряд проблем. Первая возникает из-за того, что при равенстве mi=mj МЫ получим одинаковые блоки шифротекста Ci = Cj, т.е. одинаковые блоки на входе индуцируют совпадающие блоки на выходе. Это, действительно, проблема, поскольку шаблонные начало и конец сообщений совпадают. Вторая проблема связана тем, что удаление из сообщения какого-либо блока не оставляет следов, и атакующий может таким образом исказить передаваемую информацию. Третья очень близка ко второй, но связана со вставкой блоков из других сообщений. Пусть дано сообщение P (открытый текст, последовательность бит, данные). Во время шифрования выполняются следующие действия: Сообщение делится на блоки одинакового размера. Размер (длина) блока равен n и измеряется в битах. В результате получается последовательность блоков P_{1},P_{2},...,P_{q} Последний блок при необходимости дополняется до длины n. Каждый блок P_{i} шифруется алгоритмом шифрования E_k с использованием ключа k: Недостатки ECB: сохранение статистических особенностей открытого текста (поскольку одинаковым блокам шифротекста соответствуют одинаковые блоки открытого текста). Достоинства ECB: - постоянная скорость обработки блоков (скорость определяется эффективностью реализации шифра); - возможно распараллеливание вычислений (так как блоки не связаны между собой). Режим СВС Один из путей обхода проблем, возникающих при использовании режима ЕСВ, состоит в «зацеплении» шифра, т.е. в добавлении к каждому блоку шифротекста контекстного идентификатора. Самый простой способ сделать это — применить режим «сцепления блоков шифра» или СВС (сокращение от «Cipher Block Chaining»). В этом режиме открытый текст, как обычно, разбивается на серию блоков: m1, m2, ... , mq. Как и в предыдущем режиме, последний блок может потребовать дополнения, чтобы длина открытого текста стала кратной длине блока. Шифрование осуществляется согласно формулам Обратите внимание на то, что в вычислении первого блока шифротекста участвует величина IV (начальное значение), которую следует отнести к заданию шифрующей функции. Величину IV привлекают к шифрованию с тем, чтобы шифрованные версии одинаковых частей открытого текста выглядели по разному. Нет необходимости скрывать значение IV, и на практике ее передают в открытом виде как часть сообщения. Естественно, величина IV участвует и в расшифровании. Этот процесс выглядит следующим образом Сообщение разбивается на блоки одинакового размера. Размер (длина) блока равен n и измеряется в битах. При необходимости последний блок дополняется до длины n. Шифрование очередного (i-го) блока сообщения (P_{i}) выполняется с использованием предыдущего зашифрованного ((i-1)-го) блока (C_{{i-1}}). Для первого блока (P_1) зашифрованного блока (C_{0}) не существует, поэтому первый блок шифруют с использованием «вектора инициализации» (англ. initialization vector, IV): C_{0}=IV (вектор инициализации — случайное число) Размер (длина) IV равна размеру блока (n). В функцию шифрования E_k передаётся сумма по модулю 2 («⊕», «xor») текущего блока сообщения P_{i} и предыдущего зашифрованного блока {C_{{i-1}}: Расшифровка выполняется функцией D_{k} с использованием тех же ключа k и вектора инициализации IV: Недостатки CBC: возможность изменения блока шифротекста C_{{i-1}} путём изменения блока сообщения P_{i}; невозможность распараллеливания шифрования (поскольку для шифрования каждого i-го блока требуется блок, зашифрованный на предыдущем шаге (блоки связаны между собой)). Достоинства CBC: постоянная скорость обработки блоков (скорость определяется эффективностью реализации шифра; время выполнения операции «xor» пренебрежимо мало); отсутствие статистических особенностей, характерных для режима ECB (поскольку каждый блок открытого текста «смешивается» с блоком шифротекста, полученным на предыдущем шаге шифрования); Режим OFB Режим, называемый «обратной связью по выходу», или OFB (Output Feedback), адаптирует блочный шифр к его поточному использованию. Для этого выбирается переменная j (1 <= j <=n), обозначающая число битов на выходе генератора потока ключей при каждой итерации. С помощью блочного шифра создается поток ключей, j битов за один раз. Рекомендуется брать j равное n, поскольку при этом ожидаемая длина периода потока ключей получается большей, нежели при других значениях. Как и ранее, мы разбиваем открытый текст на серию блоков: m1, m2, ... , mq. Но на этот раз, в отличие от предыдущих случаев, блоки состоят из j битов. Процесс шифрования происходит по следующей схеме (рис. 5.12). Прежде всего, переменной x1 присваивается начальное значение IV, Затем, при i = 1, 2, ... , q, делаются преобразования: Режим (OFB)[4] обратной связи вывода превращает блочный шифр в синхронный шифр потока: он генерирует ключевые блоки, которые являются результатом сложения с блоками открытого текста, чтобы получить зашифрованный текст. Так же, как с другими шифрами потока, зеркальное отражение в зашифрованном тексте производит зеркально отражённый бит в открытом тексте в том же самом местоположении. Это свойство позволяет многим кодам с исправлением ошибок функционировать как обычно, даже когда исправление ошибок применено перед кодированием. Из-за симметрии операции сложения, шифрование и расшифрование похожи: Каждая операция блочного шифра обратной связи вывода зависит от всех предыдущих и поэтому не может быть выполнена параллельно. Однако, из-за того, что открытый текст или зашифрованный текст используются только для конечного сложения, операции блочного шифра могут быть выполнены заранее, позволяя выполнить заключительное шифрование параллельно с открытым текстом. Обратная связь по выходу на k разрядов не рекомендуется из соображений криптостойкости. Режим OFB имеет следующее преимущество по сравнению с режимом CFB: ошибки, возникающие в результате передачи по каналу с шумом, при дешифровании не «размазываются» по всему шифротексту, а локализуются в пределах одного блока. Однако открытый текст может быть изменён путём определённых манипуляций с блоками шифротекста. Несмотря на то, что OFB-шифрование не поддаётся распараллеливанию, эффективность процедуры может быть повышена за счёт предварительной генерации независимой последовательности блоков.[1] Режим CFB Последний режим, который мы рассмотрим, носит название «обратной связи по шифротексту» или СРВ (Cipher FeedBack). Он похож на режим OFB , но блочный шифр в нем трансформируется в поточный. Напомним, что в предыдущем режиме начало потока ключей получается из значения IV, а остальной поток формируется пошагово, в результате шифрования значения шифрующей функции, вычисленного на предыдущей стадии. В случае СРВ поток ключей возникает в результате еще одного шифрования блоков криптограммы (рис. 5.14): ______________________________________________________________________________ Режим обратной связи по шифротексту, режим гаммирования с обратной связью (англ. cipherfeedbackmode, CFB)[4]. Во время шифрования каждый блок открытого текста складывается по модулю 2 с блоком, зашифрованным на предыдущем шаге. Криптостойкость CFB определяется криптостойкостью используемого шифра. Блоки открытого текста «смешиваются» («маскируются») с блоками шифротекста. Если в режиме CFB с полноблочной обратной связью имеется два идентичных блока шифротекста, результат, например, шифрования алгоритмом DES на следующем шаге будет тем же. Скорость шифрования режима CFB с полноблочной обратной связью та же, что и у блочного шифра, причём возможности распараллеливания процедуры шифрования ограничены[1]. Выбор режима шифрования Выбор режима шифрования зависит от поставленной вами цели. Для обычного открытого текста можно использовать CBC, CFB или OFB. Для шифрования файлов лучше пользоваться CBC: значительно увеличивается безопасность, при появлении ошибок в хранимых данных почти никогда не бывает сбоев синхронизации. Конкретный режим зависит от ваших требований. В целом выбор метода шифрования - это поиск компромисса между эффективностью и производительностью[8]. ПОТОЧНОЕ ШИФРОВАНИЕ, GSM СТАНДАРТ. Пото́чный шифр — это симметричный шифр, в котором каждый символ открытого текста преобразуется в символ шифрованного текста в зависимости не только от используемого ключа, но и от его расположения в потоке открытого текста. Поточный шифр реализует другой подход к симметричному шифрованию, нежели блочные шифры. При блочном шифровании открытый текст разбивается на блоки равной длины, при этом совпадающие блоки при данном ключе всегда шифруется одинаково, при поточном шифровании это не так. А5 — это поточный алгоритм шифрования, используемый для обеспечения конфиденциальности передаваемых данных между телефоном и базовой станцией в европейской системе мобильной цифровой связи GSM (Groupe Spécial Mobile). Шифр основан на побитовом сложении по модулю два (булева операция «исключающее или») генерируемой псевдослучайной последовательности и шифруемой информации. В A5 псевдослучайная последовательность реализуется на основе трёх линейных регистров сдвига с обратной связью. Регистры имеют длины 19, 22 и 23 бита соответственно. Сдвигами управляет специальная схема, организующая на каждом шаге смещение как минимум двух регистров, что приводит к их неравномерному движению. Последовательность формируется путём операции «исключающее или» над выходными битами регистров. Структура А5 В этом алгоритме каждому символу открытого текста соответствует символ шифротекста. Текст не делится на блоки (как в блочном шифровании) и не изменяется в размере. Для упрощения аппаратной реализации и, следовательно, увеличения быстродействия используются только простейшие операции: сложение по модулю 2 (XOR) и сдвиг регистра. Формирование выходной последовательности происходит путём сложения потока исходного текста с генерируемой последовательностью (гаммой). Особенность операции XOR заключается в том, что применённая чётное число раз, она приводит к начальному значению. Отсюда, декодирование сообщения происходит путём сложения шифротекста с известной последовательностью. В реальных системах создаётся ключ заданного размера, который без труда передаётся по закрытому каналу. Последовательность генерируется на его основе и является псевдослучайной. Большой класс поточных шифров (в том числе A5) составляют шифры, генератор псевдослучайной последовательности которой основан на регистрах сдвига с линейной обратной связью. Криптография с открытым ключом. Математические задачи, на которых она основывается. Сейчас известно достаточно много различных асимметричных криптосистем. Стойкость таких систем основывается на некоторой сложной математической проблеме. Одной из таких проблем является задача разложения числа N на простые множители, такая задача носит название задачи факторизации (англ. factor - множитель). В частности данная задача представляет интерес, когда N является произведением двух простых чисел. Понятно, что если N небольшое, то решить эту задачу не так сложно. Можно перебирать последовательно все простые числа, меньшие N, и пытаться нацело делить N на перебираемое простое число. Но если же N большое, то в общем случае данная задача является весьма сложной. Одной из самых известных криптосистем с открытым ключом в основе построения которой лежит задача разложения большого числа на большие множители является система RSA (от имен своих разработчиков: Rivest, Shamir, Adleman). Суть системы заключается в следующем. Выбираются большие простые числа p и q, которые держаться в секрете. Публикуется их произведение N=pq, а также выработанный определенным образом ключ зашифрования. Ключ расшифрования держится в секрете и вырабатывается так же определенным образом, используя знание факторизации числа N(то есть знание p иq). Далее, любой желающий отправить, скажем нам, сообщение зашифрует его на нашем открытом ключе зашифрования и отправит нам криптограмму. При этом любой, отличный от нас пользователь, который перехватит криптограмму не сможет ее расшифровать, так как он не сможет выработать ключ расшифрования, поскольку не знает факторизации N. Другой важный класс задач связан с дискретным логарифмированием. Пусть (G, •) — конечная абелева группа, например, мультипликативная группа конечного поля или эллиптическая кривая над конечным полем. Проблема вычисления дискретных логарифмов [ПДЛ) состоит в определении целого числа ж, которое при данных А, В принадлежит G удовлетворяет соотношению Аx = В. Криптография с открытым ключом. Алгоритм RSA. Криптография с открытым ключом. Алгоритм рюкзак. Криптография с открытым ключом. Алгоритм Эль-Гамаль. Распределение ключей с помощью криптографии с открытым ключом. Алгоритм Диффи-Хэлмана и использование RSA для передачи ключей. ЦИФРОВЫЕ ПОДПИСИ. ИСПОЛЬЗОВАНИЕ СИММЕТРИЧНОЙ КРИПТОГРАФИИ, КРИПТОГРАФИИ С ОТКРЫТЫМ КЛЮЧОМ И ХЭШ-ФУНКЦИИ ДЛЯ СОЗДАНИЯ ЦИФРОВОЙ ПОДПИСИ. DIGITAL SIGNATURE ALGORITHM. Цифровая подпись - это криптографический механизм, который используется для проверки подлинности и целостности цифровых данных. Мы можем рассматривать его как цифровую версию обычных рукописных подписей, но с более высоким уровнем сложности и безопасности. В основном цифровые подписи предназначены для достижения трех результатов: целостности данных, аутентификации и неотрекаемости. Целостность данных. Боб может удостовериться, что сообщение Алисы не изменялось на протяжении своего пути. Последствием любых изменений в сообщении будет генерация совершенно другой подписи. Аутентификация. Пока приватный ключ Алисы хранится в секрете, Боб может использовать ее публичный ключ, чтобы подтвердить факт того, что цифровые подписи были созданы именно Алисой и никем другим. Неотрекаемость. После того, как подпись была сгенерирована, Алиса не сможет отрицать свое отношение к ней в будущем, только в случае, если ее приватный ключ был каким-то образом скомпрометирован. Алгоритмы Существует несколько схем построения цифровой подписи: На основе алгоритмов симметричного шифрования. Данная схема предусматривает наличие в системе третьего лица — арбитра, пользующегося доверием обеих сторон. Авторизацией документа является сам факт зашифрования его секретным ключом и передача его арбитру.[4] На основе алгоритмов асимметричного шифрования. На данный момент такие схемы ЭП наиболее распространены и находят широкое применение. Кроме этого, существуют другие разновидности цифровых подписей (групповая подпись, неоспоримая подпись, доверенная подпись), которые являются модификациями описанных выше схем.[4] Их появление обусловлено разнообразием задач, решаемых с помощью ЭП. Использование хеш-функций Поскольку подписываемые документы — переменного (и как правило достаточно большого) объёма, в схемах ЭП зачастую подпись ставится не на сам документ, а на его хеш. Для вычисления хеша используются криптографические хеш-функции, что гарантирует выявление изменений документа при проверке подписи. Хеш-функции не являются частью алгоритма ЭП, поэтому в схеме может быть использована любая надёжная хеш-функция. Использование хеш-функций даёт следующие преимущества: Вычислительная сложность. Обычно хеш цифрового документа делается во много раз меньшего объёма, чем объём исходного документа, и алгоритмы вычисления хеша являются более быстрыми, чем алгоритмы ЭП. Поэтому формировать хеш документа и подписывать его получается намного быстрее, чем подписывать сам документ. Совместимость. Большинство алгоритмов оперирует со строками бит данных, но некоторые используют другие представления. Хеш-функцию можно использовать для преобразования произвольного входного текста в подходящий формат. Целостность. Без использования хеш-функции большой электронный документ в некоторых схемах нужно разделять на достаточно малые блоки для применения ЭП. При верификации невозможно определить, все ли блоки получены и в правильном ли они порядке. Симметричная схема Симметричные схемы ЭП менее распространены, чем асимметричные, так как после появления концепции цифровой подписи не удалось реализовать эффективные алгоритмы подписи, основанные на известных в то время симметричных шифрах. Первыми, кто обратил внимание на возможность симметричной схемы цифровой подписи, были основоположники самого понятия ЭП Диффи и Хеллман, которые опубликовали описание алгоритма подписи одного бита с помощью блочного шифра. В связи с этим симметричные схемы имеют следующие преимущества: Стойкость симметричных схем ЭП вытекает из стойкости используемых блочных шифров, надежность которых также хорошо изучена. Если стойкость шифра окажется недостаточной, его легко можно будет заменить на более стойкий с минимальными изменениями в реализации. Однако у симметричных ЭП есть и ряд недостатков: Нужно подписывать отдельно каждый бит передаваемой информации, что приводит к значительному увеличению подписи. Подпись может превосходить сообщение по размеру на два порядка. Сгенерированные для подписи ключи могут быть использованы только один раз, так как после подписывания раскрывается половина секретного ключа. Асимметричная схема Асимметричные схемы ЭП относятся к криптосистемам с открытым ключом. Но в отличие от асимметричных алгоритмов шифрования, в которых шифрование производится с помощью открытого ключа, а расшифровка — с помощью закрытого (расшифровать может только знающий секрет адресат), в асимметричных схемах цифровой подписи подписание производится с применением закрытого ключа, а проверка подписи — с применением открытого (расшифровать и проверить подпись может любой адресат). ХЭШ-ФУНКЦИИ. MD-5, SHA Хеш-функция, или функция свёртки — функция, осуществляющая преобразование массива входных данных произвольной длины в выходную битовую строку установленной длины, выполняемое определённым алгоритмом. Преобразование, производимое хеш-функцией, называется хешированием. Исходные данные называются входным массивом, «ключом» или «сообщением». Хеш-функции применяются в следующих случаях: при построении ассоциативных массивов; при поиске дубликатов в последовательностях наборов данных; при построении уникальных идентификаторов для наборов данных; при вычислении контрольных сумм от данных (сигнала) для последующего обнаружения в них ошибок (возникших случайно или внесённых намеренно), возникающих при хранении и/или передаче данных; при сохранении паролей в системах защиты в виде хеш-кода (для восстановления пароля по хеш-коду требуется функция, являющаяся обратной по отношению к использованной хеш-функции); при выработке электронной подписи (на практике часто подписывается не само сообщение, а его «хеш-образ»); Для того, чтобы хеш-функция H считалась криптографически стойкой, она должна удовлетворять трём основным требованиям, на которых основано большинство применений хеш-функций в криптографии: необратимость: для заданного значения хеш-функции m должно быть вычислительно неосуществимо найти блок данных X, для которого H(X)=m; стойкость к коллизиям первого рода: для заданного сообщения M должно быть вычислительно неосуществимо подобрать другое сообщение N, для которого {\displaystyle H(N)=H(M); стойкость к коллизиям второго рода: должно быть вычислительно неосуществимо подобрать пару сообщений (M,M'), имеющих одинаковый хеш. ГОМОМОРФНОЕ ШИФРОВАНИЕ Гомоморфное шифрование — форма шифрования, позволяющая производить определённые математические действия с зашифрованным текстом и получать зашифрованный результат, который соответствует результату операций, выполненных с открытым текстом. Например, один человек мог бы сложить два зашифрованных числа, не зная расшифрованных чисел, а затем другой человек мог бы расшифровать зашифрованную сумму — получить расшифрованную сумму, не имея расшифрованных чисел. Гомоморфное шифрование позволило бы предоставлять различные услуги, не предоставляя открытые пользовательские данные для каждой услуги. Области применения Облачные вычисления, электронное голосование, защищенный поиск информации… КРИПТОГРАФИЧЕСКИЕ ПРОТОКОЛЫ Криптографический протокол (англ. Cryptographic protocol) — это абстрактный или конкретный протокол, включающий набор криптографических алгоритмов, часто являющихся последовательностью криптографических примитивов. В основе протокола лежит набор правил, регламентирующих использование криптографических преобразований и алгоритмов в информационных процессах для обмена сообщениями между двумя и более участниками, а также описание используемых структур. Криптографический протокол имеет следующие функции[5]: Формирование ключей Обмен ключами Аутентификация сторон Доказательство целостности и происхождения данных (ЭЦП) Разделение ключей Безопасные распределённые вычисления Обеспечение конфиденциальности данных Обеспечение невозможности отказа Обеспечение целостности данных Обеспечение целостности соединения Разграничение доступа Состав Протокол делится на проходы (англ. pass) или циклы (англ. round), являющиеся интервалом времени активности только одного участника. В протоколах, рассчитанных на количество участников большее двух, при необходимости их синхронизации циклом называют период времени между двумя точками синхронизации[6]. Проход, в свою очередь, состоит из шагов (англ. step, action) — конкретных законченных действий, выполняемых участником[6]. Например: генерация случайного значения вычисление значений функции проверка сертификатов, ключей, подписей, и др. приём и отправка сообщений Реализация протокола или даже теоретическое её описание для конкретных участников, каждый из которых имеет одну или несколько ролей, называется сеансом (англ. session). В другом сеансе протокола участники могут поменяться ролями и выполнять уже совсем другие функции[6]. Таким образом, протокол описывает правила поведения каждой абстрактного участника в протоколе. А сеанс описывает уже состоявшейся в прошлом конкретную реализацию протокола[6]. _____________________________________ Протокол (protocol) — описание распределенного алгоритма, в процессе выполнения которого два участника (или более) последовательно выполняют определенные действия и обмениваются сообщениями. В качестве участников (иначе — субъектов, сторон) протокола могут выступать не только пользователи или абоненты, но и процессы, выполняющие какую-либо функциональную роль, например клиентские и серверные приложения. Последовательность шагов протокола группируется в циклы. Цикл (проход) протокола (round, pass of cryptographic protocol) — в криптографических протоколах с двумя участниками — временной интервал, в котором активен только один из участников. Цикл (проход) завершается формированием и отсылкой сообщения с последующим переходом активного участника в состояние ожидания и передачей активности другому участнику. Шаг (протокола) (step of a protocol, protocol action) — конкретное законченное действие, выполняемое участником (протокола) во время одного цикла (прохода) протокола. Например, шагами протокола могут быть: — вычисление значения некоторой функции; — проверка правильности сертификата ключа; — генерация случайного числа; — отправка сообщения и т. п. Сеанс (session) — это конкретная реализация протокола с конкретными участниками. КРИПТОАНАЛИЗ Криптоана́лиз (от др.-греч. κρυπτός «скрытый» + «анализ») — наука о методах дешифровки зашифрованной информации без предназначенного для этого ключа, а также сам процесс такой дешифровки. В большинстве случаев под криптоанализом понимается выяснение ключа; криптоанализ включает также методы выявления уязвимости криптографических алгоритмов или протоколов. Попытку раскрытия конкретного шифра с применением методов криптоанализа называют криптографической атакой на этот шифр. Криптографическую атаку, в ходе которой раскрыть шифр удалось, называют «взломом» или «вскрытием» шифра. Частотный анализ Полный перебор ключей Анализ ключевого генератора Факторизация/дискретное логарифмирование Метод встречи посередине Разностный анализ Линейный анализ Метод коллизий Анализ по побочным каналам Квантовый анализ |