Классификация и области применения
Cимметричные шифр — способ шифрования, в котором для шифрования и расшифрования применяется один и тот же криптографический ключ.
Гаммирование — симметричный метод шифрования, основанный на «наложении» гамма-последовательности (случайной числовой последовательности, используемой для зашифровывания и расшифровывания данных) на открытый текст. Обычно это суммирование в каком-либо конечном поле, например в поле GF(2) такое суммирование принимает вид обычного «исключающего ИЛИ».
Длиною периода гаммы называется минимальное количество символов, после которого последовательность цифр в гамме начинает повторяться.
Поточные шифры
Синхронные шифры.
Самосинхронизирующиеся
шифры
Возможно несколько вариантов определения понятия "поточный шифр",поскольку поточная архитектура, вообще говоря, не имеет четких границ.Поточный шифр определяется как независимый от открытого текста шифрпобитового гаммирования.
Такой шифр гаммирования и блочный шифр в режиме простой замены являютсясвоеобразными полюсами в мире архитектур. На практике же преобладают
смешанные варианты дизайна алгоритмов. Например, блочный AES в режимесчетчика или обратной связи по шифртексту представляет собой синхронный
или самосинхронизирующийся поточный шифры соответственно. Надежностьтакого шифра сейчас не вызывает сомнений. Что же нужно еще дляприложений?
Достаточно универсальный AES в некоторых специфических приложениях либонедостаточно производителен, либо требует слишком много ресурсов. Притом же уровне надежности хочется либо более быстрой работы, как в случаепрограммного шифрования и высокопроизводительных аппаратныхшифраторов, либо меньшей ресурсоемкости, как в случае со встроеннымисистемами (embeddedsystems). Поточная архитектура позволяет достичь и тогои другого - вопрос в надежности поточных шифров и дополнительных свойствах,интересующих пользователей.
RC4
RC4 —это поточный шифр с переменным размером ключа, разработанный в 1987г.
Ривестом (R.Rivest) для RSA Data Security, Inc. Алгоритм работает в режиме OFB: потокключей не зависит от открытого текста. Используется S-блок размером 8×8: S0, S1, S2, …, S255. Элементы представляют собой перестановку чисел от 0 до 255, а перестановкаявляется функцией ключа переменной длины. В алгоритме применяются два счетчика, i и j, снулевыми начальными значениями. Для генерации случайного байта выполняютсяследующие вычисления:
i =(i +1)mod256;
j =(j +Si)mod256.
Поменять местами SiиSj.
t =(Si+Sj)mod256;
K=St.
Киспользуется в операции XOR с открытым текстом для получения шифротекста или воперации XOR с шифротекстом для получения открытого текста. Шифрование выполняетсяпримерно в 10 раз быстрее, чем в DES. Также несложна и инициализация S-блока. СначалаS-блок заполняется по правилу: S0=0, S1=1, …, S255=255. После этого ключзаписывается в массив: K0, K1, …, K255. Затем при начальном значении j =0 в циклевыполняются следующие вычисления:for i =0to 255do j = (j + Si+ Ki)mod256
Поменять местами SiиSj.
Компания RSA DataSecurity, Inc. утверждает, что алгоритм устойчив к дифференциальному илинейному криптоанализу и что он в высокой степени нелинеен. S-блок медленноизменяется при использовании: i и j обеспечивают случайное изменение каждого элемента.
10. Генераторы РРСП. Конгруэнтный генератор. Регистры сдвига с линейной обратной связью. Преобразование регистра сдвига максимального периода. Стандарт ANSIX9.17. Циклическое шифрование. Метод Фибоначчи с запаздываением. Криптографические генераторы. A5.
Генератор РРСП - устройство, позволяющее по запросу получить реализацию равномерно распределенной случайной последовательности длиной ; элементы этой реализации принято называть случайными числами. Существует три типа генераторов РРСП:
1. Табличный.
2. Физический.
3. Программный.
Линейным конгруэнтным генератором (ЛКГ) с параметрами () называется программный генератор РРСП, порождающий псевдослучайную последовательность ,, с помощью рекуррентного соотношения
Параметры этого генератора имеют следующий смысл:
- начальное или стартовое значение;
- не нулевой множитель;
- приращение;
- модуль, равный мощности алфавита .
Если приращение , то генератор () называется мультипликативным конгруэнтным генератором (МКГ), а если , то смешанным конгруэнтным генератором (СКГ).
«Слабость» ЛКГ и МКГ заключается в том, что если рассматривать последовательные биграммы , то точки , на плоскости будут лежать на прямых из семейства . Для устранения этого недостатка нелинейные конгруэнтные генераторы, среди которых известны: квадратичный конгруэнтный генератор; Генератор Эйхенауэра-Лена с обращением; конгруэнтный генератор, использующий умножение с переносом.
Регистр сдвига с линейной обратной связью (РСЛОС) — регистр сдвига битовых слов, у которого входной (вдвигаемый) бит является линейной функцией состояния остальных битов регистра до сдвига. Может быть организован как программными, так и аппаратными средствами и применяется для генерации псевдослучайных последовательностей битов, что находит применение, в частности, в криптографии.
В регистре сдвига с линейной обратной связью выделяют две части (модуля): собственно регистра сдвига и схемы (или подпрограммы) вычисляющих значение вдвигаемого бита. Регистр состоит из функциональных ячеек (или битов машинного слова или нескольких слов), в каждой из которой хранится текущее состояние одного бита. Количество ячеек 
, называют длиной регистра. Биты (ячейки) обычно нумеруются числами 
, каждая из которых способна хранить 
бит, причём в ячейку 
происходит вдвижение вычисленного бита, а из ячейки 
извлекается выдвигаемый очередной сгенерированный бит. Вычисление вдвигаемого бита обычно производится до сдвига регистра, и только после сдвига значение вычисленного бита помещается в ячейку .
Периодом регистра сдвига называют минимальную длину получаемой последовательности до начала её повторения. Так как регистр из битовых ячеек имеет только 
разных ненулевых состояний, то, принципиально, период регистра не может превышать это число. Если период регистра равен этому числу, то такой регистр называют регистром максимального периода.
Для РСЛОС функция обратной связи является линейной булевой функцией от состояний всех или некоторых битов регистра. Например, сумма по модулю два или её логическая инверсия является линейной булевой функцией (операция XOR, в формулах обозначают как 
) и наиболее часто применяется в таких регистрах.
При этом те биты, которые являются переменными функции обратной связи, принято называть отводами.
Управление регистром в аппаратных реализациях производится подачей сдвигающего импульса (иначе называемого тактового или синхроимпульса) на все ячейки, в программных — выполнением программного цикла, включающего вычисление функции обратной связи и сдвига битов в слове.
Вычисление примитивности многочлена — достаточно сложная математическая задача. Поэтому существуют готовые таблицы, в которых приведены номера отводных последовательностей, обеспечивающих максимальный период генератора.
Стандарт ANSI X9.17 определяет способ Генерации ключей. Он не создает легко запоминающиеся ключи, и больше подходит для генерации сеансовых ключей или псевдослучайных чисел в системе. Для генерации ключей используется криптографический алгоритм DES, но он может быть легко заменен любым другим алгоритмом.
Пусть EK(X) - это X, зашифрованный DES ключом K, специальным ключом, предусмотренным для генерации секретных ключей. V0 - это секретная 64-битовая стартовая последовательность. T - это метка времени. Для генерации случайного ключа Ri вычислим:
Ri= EK(EK(Ti) Å Vi)
Для генерации Vi+1, вычислим:
Vi+1= EK(EK(Ti) Å Ri)
Для превращения Ri в ключ DES, просто удалите каждый восьмой бит. Если вам нужен 64-битовый ключ, используйте ключ без изменения. Если вам нужен 128-битовый ключ, создайте пару ключей и объедините их.
Циклическое шифрование
В данном случае используется способ генерации ключа сессии из мастер-ключа. Счетчик с периодом N используется в качестве входа в шифрующее устройство. Например, в случае использования 56-битного ключа DES может использоваться счетчик с периодом 256. После каждого созданного ключа значение счетчика повышается на 1. Таким образом, псевдослучайная последовательность, полученная по данной схеме, имеет полный период: каждое выходное значение Х0, Х1,…XN-1 основано на разных значениях счетчика, поэтому Х0 X1 XN-1. Так как мастер-ключ является секретным, легко показать, что любой секретный ключ не зависит от знания одного или более предыдущих секретных ключей.
ANSI X9.17
ГПСЧ из стандарта ANSI X9.17 используется во многих приложениях финансовой безопасности и PGP. В основе этого ГПСЧ лежит тройной DES. Генератор ANSI X9.17 состоит из следующих частей:
1. Вход: генератором управляют два псевдослучайных входа. Один является 64-битным представлением текущих даты и времени, которые меняются каждый раз при создании числа. Другой является 64-битным исходным значением. Оно инициализируется некоторым произвольным значением и изменяется в ходе генерации последовательности псевдослучайных чисел.
2. Ключи: генератор использует три модуля тройного DES. Все три используют одну и ту же пару 56-битных ключей, которая держится в секрете и применяется только при генерации псевдослучайного числа.
3. Выход: выход состоит из 64-битного псевдослучайного числа и 64-битного значения, которое будет использоваться в качестве начального значения при создании следующего числа.
· DTi — значение даты и времени на начало i-ой стадии генерации.
· Vi — начальное значение для i-ой стадии генерации.
· Ri — псевдослучайное число, созданное на i-ой стадии генерации.
· K1, K2 — ключи, используемые на каждой стадии.
Тогда:
Ri = EDEK1,K2 [ EDEK1,K2 [ DTi] Vi ]Vi+1 = EDEK1,K2 [ EDEK1,K2 [ DTi] Ri]Схема включает использование 112-битного ключа и трех EDE-шифрований. На вход даются два псевдослучайных значения: значение даты и времени и начальное значение текущей итерации, на выходе получаются начальное значение для следующей итерации и очередное псевдослучайное значение. Даже если псевдослучайное число Ri будет скомпрометировано, вычислить Vi+1 из Ri не является возможным за разумное время, и, следовательно, следующее псевдослучайное значение Ri+1, так как для получения Vi+1 дополнительно выполняются три операции EDE.
Метод Фибоначчи с запаздываниями — один из методов генерации псевдослучайных чисел. Один из широко распространённых фибоначчиевых датчиков основан на следующей итеративной формуле:
где 
— вещественные числа из диапазона 
, 
— целые положительные числа, называемые лагами. При реализации через целые числа достаточно формулы 
(при этом будут происходить арифметические переполнения). Для работы фибоначчиеву датчику требуется знать 
предыдущих сгенерированных случайных чисел. При программной реализации для хранения сгенерированных случайных чисел используется конечная циклическая очередь на базе массива. Для старта фибоначчиевому датчику требуется случайных чисел, которые могут быть сгенерированы простым конгруэнтным датчиком.
Получаемые случайные числа обладают хорошими статистическими свойствами, причём все биты случайного числа равнозначны по статистическим свойствам. Период фибоначчиева датчика может быть оценен по следующей формуле:
,
где 
— число битов в мантиссе вещественного числа.
Выбор параметров
Лаги a и b — «магические» и их не следует выбирать произвольно. Рекомендуются следующие значения лагов: 
, 
или 
. Качество получаемых случайных чисел зависит от значения константы, a чем оно больше, тем выше размерность пространства, в котором сохраняется равномерность случайных векторов, образованных из полученных случайных чисел. В то же время, с увеличением величины константы a увеличивается объём используемой алгоритмом памяти.
Значения 
можно рекомендовать для простых приложений, не использующих векторы высокой размерности со случайными компонентами. Значения 
позволяют получать числа, удовлетворительные для большинства алгоритмов, требовательных к качеству случайных чисел. Значения 
позволяют получать очень качественные случайные числа и используются в алгоритмах, работающих со случайными векторами высокой размерности. Описанный фибоначчиев датчик случайных чисел (с лагами 20 и 5) используется в широко известной системе Matlab (автором первой версии этой системы был Д. Каханер).
Криптографические генераторы случайных чисел производят случайные числа, которые используются в криптографических приложениях, например - для генерации ключей. Обычные генераторы случайных чисел, имеющиеся во многих языках программирования и программных средах, не подходят для нужд криптографии (они создавались с целью получить статистически случайное распределение, криптоаналитики могут предсказать поведение таких случайных генераторов).
В идеале случайные числа должны основываться на настоящем физическом источнике случайной информации, которую невозможно предсказать. Примеры таких источников включают шумящие полупроводниковые приборы, младшие биты оцифрованного звука, интервалы между прерываниями устройств или нажатиями клавиш. Полученный от физического источника шум затем "дистиллируется" криптографической хэш-функцией так, чтобы каждый бит зависел от каждого бита. Достаточно часто для хранения случайной информации используется довольно большой пул (несколько тысяч бит) и каждый бит пула делается зависимым от каждого бита шумовой информаци и каждого другого бита пула криптографически надежным (strong) способом.
А5 — это поточный алгоритм шифрования, используемый для обеспечения конфиденциальности передаваемых данных между телефоном и базовой станцией в европейской системе мобильной цифровой связи GSM .
Шифр основан на побитовом сложении по модулю два (булева операция XOR) генерируемой псевдослучайной последовательности и шифруемой информации. В A5 псевдослучайная последовательность реализуется на основе трёхлинейных регистров сдвига с обратной связью. Регистры имеют длины 19, 22 и 23 бита соответственно. Сдвигами управляет специальная схема, организующая на каждом шаге смещение как минимум двух регистров, что приводит к их неравномерному движению. Последовательность формируется путём операции XOR над выходными битами регистров.
11. Асимметричные алгоритмы. Режимы шифрования. Методы криптоанализа. Основные способы использования асимметричных алгоритмов.
Методы криптоанализа
Криптоанализ
• Метод тотального перебора
• Атака на алгоритм
• Атака вероятного сообщения
Асимметричные алгоритмы шифрования позволяют получателю обеспечивать шифрование информации, направляемой ему неограниченным количеством отправителей. Кроме того, использование этих алгоритмов позволяет проводить аутентификацию участников обмена информацией и осуществлять контроль целостности передаваемой информации.
Общий принцип работы асимметричных алгоритмов заключается в следующем:
- участник информационного обмена генерирует пару ключей. При этом данные, зашифрованные одним из ключей, могут быть расшифрованы только другим ключом. Один из этих ключей является открытым (общедоступным), другой — закрытым (секретным). Секретный ключ участник хранит у себя, а открытый распространяет всем желающим отправлять ему шифрованные сообщения. Открытый ключ — это функция, при помощи которой отправитель может зашифровать свое сообщение, но ни он сам, ни кто-либо другой не может дешифровать это сообщение, используя открытый ключ. Для дешифрования сообщения (т. е. осуществления обратной операции — вычисления значения аргумента по значению функции) необходимо знать некоторый параметр указанной функции, который, по сути, и является закрытым ключом;
- отправитель сообщения шифрует информацию открытым ключом и передает ее получателю по каналам связи;
- получатель дешифрует сообщения, используя свой закрытый ключ.
Режим шифрования — метод применения блочного шифра, позволяющий преобразовать последовательность блоков открытых данных в последовательность блоков зашифрованных данных. При этом для шифрования одного блока могут использоваться данные другого блока. Обычно режимы шифрования используются для модификации процесса шифрования так, чтобы результат шифрования каждого блока был уникальным вне зависимости от шифруемых данных и не позволял сделать какие-либо выводы об их структуре. Это обусловлено, прежде всего, тем, что блочные шифры шифруют данные блоками фиксированного размера, и поэтому существует потенциальная возможность утечки информации о повторяющихся частях данных шифруемых на одном и том же ключе.
ElectronicCodebook (ECB)
Основная статья: Режим электронной кодовой книги
Каждый блок открытого текста заменяется блоком шифротекста. В ГОСТ 28147—89 называется режимом простой замены.
CipherBlockChaining (CBC)
Основная статья: Режим сцепления блоков шифротекста
Каждый блок открытого текста (кроме первого) побитово складывается по модулю 2 (операция XOR) с предыдущим результатом шифрования
PropagatingCipherBlockChaining (РСВС)
Недостатки режима CBC привели к созданию усовершенстванного режима распространяющегося сцепления блоков шифра . Естественно этот режим похож на CBC за исключением того, что предыдущий блок открытого текста и предыдущий блок шифротекста подвергается операции XOR с текущем блоком открытого текста перед шифрованием или после него.
CipherFeedback (CFB)
Основная статья: Режим обратной связи по шифротексту
Режим обратной связи по шифротексту, режим гаммирования с обратной связью . Для шифрования следующего блока открытого текста он складывается по модулю 2 с перешифрованным (блочным шифром) результатом шифрования предыдущего блока.
OutputFeedback (OFB)
Режим (OFB)[5] обратной связи вывода превращает блочный шифр в синхронный шифрпоток: это генерирует ключевые блоки, которые являются результатом сложения с блоками открытого текста, чтобы получить зашифрованный текст. Так же, как с другими шифрами потока, зеркальное отражение в зашифрованном тексте производит зеркально отраженный бит в открытом тексте в том же самом местоположении. Это свойство позволяет многим кодам с исправлением ошибок функционировать как обычно, даже когда исправление ошибок применено перед кодированием.
CounterMode (CTR)
Режим Счетчика (CounterMode-CTR)[5] предполагает возврат на вход соответствующего алгоритма блочного шифрования значения некоторого счетчика, накопленного с момента старта. Режим делает из блочного шифра потоковый, т.е. генерирует последовательность, к которой применяется операция XOR с текстом сообщения. Исходный текст и блок зашифрованного текста имеют один и тот же размер блока, как и основной шифр (например, DES или AES)
Применения в сети Internet
1. Для алгоритмов шифрования, аутентификации, контроля целостности сообщений и управления ключами в сети Internet приняты стандарты InternetPrivacy-EnhancedMailstandards (PEM). Этипротоколыразработаныврамкахгрупп Internet Resources Task Force (IRTF) и Privacy and Security Research Group (PSRG), затемпереданы Internet Engineering Task Force (IETF) PEM Working Group и, наконец, приняты Internet Architecture Board (IAB). Протоколы опубликованы в серии RequestforComment (RFC). PEM поддерживают протокол X.509 и алгоритм RSA (для ключей длиной до 1024 бит). Существует также военный аналог PEM, разработанный АНБ США в конце 80-х годов (MessageSecurityProtocol - MSP).
2. Созданная в марте 1996 года фирма PrettyGoodPrivacy, Inc. для распространения коммерческих версий, разработанного Филиппом Циммерманом программного продукта PGP, предпринимает активные попытки по введению де-факто в качестве стандарта в Internet своего алгоритма, являющегося, по сути, алгоритмом RSA с длиной ключа - 2047 бит). Сегодня сложно предсказывать дальнейшее развитие ситуации, поскольку PGP, Inc. вынуждена обсуждать проекты внедрения в свои алгоритмы процедур депонирования ключей, что неизбежно подрывает доверие к системе в целом со стороны пользователей.
Алгоритмы асимметричной криптографии (в частности, схема открытого распределения ключей) реализованы в телефонной аппаратуре серии STU (SecureTelephoneUnit): STU-II, STU-III.
В последние несколько лет в США ведется активная политическая борьба вокруг попыток принудительного внедрения в сети связи ClipperChip (также называемого MYK-78T). Основные проблемы здесь связаны с процедурой депонирования ключей. Нам же хотелось лишь упомянуть, что ClipperChip позволяет выполнять и некоторые протоколы асимметричной криптографии.
12. Понятие вычислительно неразрешимой математической задачи. Однонаправленная функция.
Однонаправленная функция.
Однонаправленная функция (onewayfunction)
Вычислительно разрешимаязадача –вычисляемая в полиномиальное время от
некоторого параметра.
Вычислительно неразрешимаязадача –вычисляемая в экспоненциальное время от
некоторого параметра.
Y = f(X) –легко X = f-1(Y) -трудно
13. Алгоритм RSA. Выбор параметров. Атака с помощью квантового компьютера. Алгоритм Шора.
SA-ключи генерируются следующим образом:
1. Выбираются два различных случайных простых числа 
и 
заданного размера (например, 1024 бита каждое).
2. Вычисляется их произведение 
, которое называется модулем.
3. Вычисляется значение функции Эйлера от числа 
:
4. Выбирается целое число 
( 
), взаимно простое со значением функции 
. Обычно в качестве берут простые числа, содержащие небольшое количество единичных бит в двоичной записи, например, простые числа Ферма 17, 257 или 65537.
· Число называется открытой экспонентой (
· Время, необходимое для шифрования с использованием быстрого возведения в степень, пропорционально числу единичных бит в .
· Слишком малые значения , например 3, потенциально могут ослабить безопасность схемы RSA.
5. Вычисляется число 
, мультипликативно обратное к числу по модулю , то есть число, удовлетворяющее условию:
· Число называется секретной экспонентой. Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.
6. Пара 
публикуется в качестве открытого ключа RSA (англ. RSA public key).
7. Пара 
играет роль закрытого ключа RSA (англ. RSA private key) и держится в секрете.