Предмет криптографии. Определения. Задачи. Исторические примеры

1. Предмет криптографии. Определения. Задачи. Исторические примеры.

 

Криптология – это наука, состоящая из двух ветвей, цели которых прямо противоположны:

• Криптография – наука о способах преобразования (шифрования) информации с целью обеспечения ее секретности, аутентичности и неотслеживаемости.

• Криптоанализ – о методах и способах оценки надежности, анализа стойкости и разработки способов вскрытия шифров.

 

Основные задачи:

• Обеспечение конфиденциальности.

• Обеспечение целостности.

• Обеспечение аутентификации.

• Обеспечение невозможности отказа от авторства

 

Шифр – семейство обратимых преобразований, каждое из которых определяется некоторым параметром, называемым ключом, а также порядком применения данного преобразования, называемого режимом шифрования.

Ключ представляет собой буквенную или числовую последовательность.

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

• Пару алгоритмов зашифрования и расшифрования называют криптосистемой (шифросистемой), а реализующие их устройства – шифротехникой.

• Обозначим:

M – открытое сообщение, С – шифрованное сообщение.

Зашифрование алгоритмом E с ключом k1 означает, что

Ek1(M) = C

Расшифрование алгоритмом D с ключом k2

Dk2(C) = M

Алгоритмы должны удовлетворять равенству

Dk2(Ek1(M)) = M

• Зашифровка– процесс преобразования множества открытого сообщения в множество закрытое сообщение.

• Дешифрование – процесс нахождения открытого сообщения, соответствующему заданному закрытому сообщению при неизвестном криптопреобразовании.

Абстрактно систему можно описать как множество открытых сообщений в множество закрытых. Выбор конкретного типа преобразования определяется ключом расшифрования.

Отображения должны быть взаимно однозначные.

Ключи зашифрования и расшифрования могут быть различны.

Множество, из которых выбираются ключи, называется ключевым пространством.

Совокупность процессов зашифрования, множества открытых сообщений, множества возможных закрытых сообщений и ключ пространства называется алгоритмом зашифрования.

 

Исторические примеры.
Около 4000 лет назад египтяне заменяли иероглифы в важных местах на другие.Но их было не трудно расшифровать,видимо цель была не в этом.
Скиталы – кожаная полоска наматывается на цилиндр определенной толщины.
Диск Энея( 4 век до н.э.) на диске просверливаются дырки, соотв.буквам, через них продевается в нужном порядке нить. Расшифровка тривиальна, но сообщение можно мгновенно уничтожить. Он же книжный шифр: незаметные пометки над буквами книги ( первая стеганография)

Квадрат Полибия: в квадрат вписываются буквы, каждая буква заменяется на ту, что под ней. Шифр – порядок букв в этом квадрате.
Геродот упоминает, как сообшение о планирующейся атаке персов было записано на основе восковых табличек,которые потом опять покрыли воском.
Шифр Цезаря – простой шифр подстановки. Буквы сдвигаются на фиксированное число позиций. A-D, B-E....
Талмуд – атбаш: первая буква заменяется на последнюю. Вторая на предпоследнюю…
Шифр Цезаря и атбаш – частные случаи моноалфавитных шифров (в них в каждой букве становится в соответствие другая бука алфавита).
Полиалфавитные шифры : первый такой шифр: диск. Внутри код. Снаружи сообщение. Время от времени сдвигаем внутренний диск, изменяя тем самым код.
Иоганн Трисемус, 1508 «Полиграфия» - первый труд по криптографии. Шифр Трисемуса – квадрат, tabula recta, в котором записан алфавит со смещением. Первая буква кодируется по первой строке и т.д.

Блез де Виженер, 1586 – предложил кодировать сообщение им самим: первая расшифрованная буква используется для декодирования второй и т.д.
Многое изменилось после изобретения телеграфа. Нужно было кодировать большие объемы сообщений. Прежние шифры были слишком трудоемки. Перешли на простые коды, секретность достигалась частой сменой кодовых слов. Были и новые шифры.
Цилиндр Джеферсона: чтобы зашифровать, нужно повернуть цилиндры так, чтобы получилось сообщение и записать какую-нибудь другую строчку, чтобы дешифровать нужно повернуть цилиндры так, чтобы получился код и поискать ту строчку, которая имеет смысл как сообщение.
Во время мировых войн на криптографию сильно повлияло радио. Теперь перехватывали большое количество вражеских сообщений.

В 1910-е годы Гильберт Вернам :
улучшил шифр Виженера;
разработал шифр, который невозможно взломать. Одноразовый блокнот: используем одноразовый секретный ключ k, который просто побитово складывался с сообщением:
Без знаний о ключе и сообщении враг, перехвативший сообщение, получил ровно ноль информации.
Whitfield Diffie, Martin Hellman, 1976, “New directions in cryptography” – протокол согласования ключа Диффи-хелмана.
Ron Rivers, Adi Shamir,Leonard Adleman, 1978 – RSA, первая криптосистема с открытым ключом.

 

1. Виды атак на криптографические алгоритмы. Понятие стойкости.

 

• Криптоатака с использованием только шифрованных текстов.

• Криптоатака с использованием открытых текстов и соответствующих им шифрованных текстов.

• Криптоатака с использованием выбираемых криптоаналитиком открытых текстов и соответствующих им шифрованных.

• Криптоатака с использованием активного аппарата воздействия на систему

 

Стойкость алгоритмов шифрования

Под раскрытием понимаем:

• Полное – нашел ключ.

• Нахождение эквивалентного алгоритма – не имея представления о ключе.

• Раскрытие открытого сообщения – вычислил 1, соответствующее 1 из зашифрованных.

• Частичное раскрытие – частичные сведения о ключе.

Факторы, влияющие на раскрытие шифра:

• объем сообщений;

• время для вычислений;

• вычислительные ресурсы.

Стойким считается алгоритм, который для своего раскрытия требует практически недостижимых вычислений ресурсов, или недостаток времени, или недостаток объема.

!!Любой алгоритм может быть вскрыт прямым перебором.

 

1. Классификация алгоритмов шифрования. Примеры простейших шифров.

 

Или другой вариант:

ШИФРЫ

 

Шифры перестановки

Шифр, преобразования из которого изменяют только порядок следования символов исходного текста, но не изменяют их самих, называется шифром перестановки.

Рассмотрим, предназначенное для зашифрования сообщения длиной n символов. Его можно представить с помощью таблицы

 

 

где i1 - номер места шифртекста, на которое попадает первая буква исходного сообщения при выбранном преобразовании, i2 - номер места для второй буквы и т.д.

В верхней строке таблицы выписаны по порядку числа от 1 до , а в нижней - те же числа, но в произвольном порядке. Такая таблица называется подстановкой степени n. Зная подстановку, задающую преобразование, можно осуществить как зашифрование, так и расшифрование текста.

 

Маршрутная перестановка

Например, можно вписывать исходное сообщение в прямоугольную таблицу, выбрав такой маршрут: по горизонтали, начиная с левого верхнего угла… Выписывать сообщение будем по другому маршруту: по вертикали, начиная с… При расшифровании надо определить число длинных столбцов, т.е. число букв в последней строке прямоугольника. Для этого…

Формирование группы

При построении алгоритма учитывают формирование группы, в которой элементами являются множество блоков шифротекста при всех ключах, а групповой операцией — композиция раундов шифрования. Если данный шифр образует практически полную группу, не имеет смысла применять кратное шифрование.

1. Алгоритм симметричного шифрования DES.

Ый раунд DES

1. Алгоритм симметричного шифрования ГОСТ 28147-99.

• Длина блока 64 бит

• Длина ключа 256 бит.

• Сеть Фейстеля, количество раундов равно 32.

 

Функция F

• Сначала правая половина и i-ый подключ складываются по модулю 232.

• Затем результат разбивается на восемь 4-битовых значений, каждое из которых подается на вход S-box.

• ГОСТ 28147 использует восемь различных S-boxes, каждый из которых имеет 4-битовый вход и 4-битовый выход.

• Выходы всех S-boxes объединяются в 32-битное слово, которое затем циклически сдвигается на 11 битов влево.

• Наконец, с помощью XOR результат объединяется с левой половиной, в результате чего получается новая правая половина.

 

1-й раунд ГОСТ

Генерация ключей ГОСТ

Алгоритм имеет 32 раунда, поэтому каждый подключ используется в четырех раундах по следующей схеме: Раунд …  

S-boxes

• Тогда порядковый номер числа будет являться входным значением S-box, а само число - выходным значением S-box 1-ый S-box 4 10 9 2 13 8 0 14

Добавление ключа.

        =   … Эта операция является обратной к самой себе. Алгоритмы симметричного…

Blowfish

• Сеть Фейстеля, 16 итераций. • Каждая итерация состоит из перестановки, зависящей от ключа, и подстановки,… • Операциями являются XOR и сложение 32-битных слов.

Генерация подключей Blowfish

Для создания всех подключей требуется 521 итерация. IDEAХарактеристики: • Сеть Фейстеля, 16 итераций.

Создание подключей

• Пятьдесят два 16-битных подключа создаются из 128-битного ключа шифрования следующим образом.

• Первые восемь подключей, которые обозначим как Z1, Z2, ..., Z8, получаются непосредственно из ключа, при этом Z1 равен первым 16 битам, Z2 равен следующим 16 битам и т.д.

• Циклический сдвиг ключа влево на 25 битов, создаются следующие 8 подключей.

• Повторяется до тех пор, пока не будут созданы все 52 подключа.

• Заметим, что каждый первый подключ раунда получен из своего подмножества битов ключа. Если весь ключ обозначить как Z [1..128], то первыми ключами в восьми раундах будут:

Z1 = Z [1..16] Z25 = Z [76..91] Z7 = Z [97..112]

Z31 = Z [44..59] Z13 = Z [90..105] Z37 = Z [37..52]

Z19 = Z [83..98] Z43 = Z [30..45]

Расшифрование IDEA

• Первые четыре подключа i-ого раунда дешифрования получаются из первых четырех подключей (10-i)-го раунда шифрования, где стадия заключительного… • Для первых восьми раундов последние два подключа i раунда дешифрования… (9 - i) раунда шифрования.

Режим ECB

• ECB-режим идеален для небольшого количества данных, например, для шифрования ключа сессии. • Существенным недостатком ECB является то, что один и тот же блок…

Режим CFB

• Одним из преимуществ такого режима блочного алгоритма шифрования является то, что зашифрованный текст будет той же длины, что и исходный. • Будем считать, что блок данных, используемый для передачи, состоит из J… • Рассмотрим шифрование. Входом функции шифрования является регистр сдвига, который первоначально устанавливается в…

Режим OFB

• Основное преимущество режима OFB состоит в том, что если при передаче произошла ошибка, то она не распространяется на следующие зашифрованные… • Недостаток OFB в том, что он более уязвим к атакам модификации потока… Поточные криптосистемы. Принципы построения. Классификация. Проблема синхронизации. …

Примеры потоковых шифров Mush

• представляет собой взаимно прореживающий генератор.

Пусть A, B - аддитивные генераторы.

• Если бит переноса А установлен тактируется B.

• Если бит переноса B установлен тактируется A.

• Тактируем A и при переполнении устанавливаем бит переноса.

• Тактируем B и при переполнении устанавливаем бит переноса.

• Окончательным выходом является XOR выходов A и B.

• Можно использовать следующие генераторы:

A(i)=(A(i-55)+ A(i-24)) mod 232 ;

B(i)=(B(i-52)+ B(i-19)) mod 232.

• В среднем, для генерации одного выходного слова нужно три итерации генератора.

Gifford

b0, b1,...., b7. • Ключом является начальное состояние регистра. • Открытый текст не влияет на работу алгоритма. Для генерации байта ключа k объединим b0 и b1, а также объединим b4 и…

PKZIP

• Использует три 32-битовых переменных:

• К0 = 305419896; К1 = 591751049; К2 = 878082192.

• Используется 8-битовый ключ К3, полученный из К2.

Алгоритм (в стандартной нотации С):

Сi=Рi^K3;

K0=сrc32 (K0,Pi);

K1=K1+ (K0 & 0х000000ff);

K1= K1*134775813 + 1;

K2 = сrc32 (K2, K1 >> 24);

K3 = ((K2|2)*((K2 | 2)^1))>>8.

Функция crc32 берёт своё предыдущее значение и байт, выполняет их XOR и вычисляет следующее значение с помощью многочлена CRC, определённого 0xcdb88320.

На практике 256-элементная таблица может быть рассчитана заранее, и вычисление crc32 превращается в

crc32(a,b)=(a<<8)^ table [(a& 0xff) xor b].

Для шифрования потока открытого текста сначала для обновления ключей зациклим байты ключа в алгоритме шифрования.

Полученный шифротекст на этом этапе игнорируется.

Затем побайтно зашифруем открытый текст. Открытому тексту предшествуют 12 случайных байт, но это не важно.

Безопасность этого алгоритма не слишком велика. Для вскрытия нужно от 40 до 2000 байтов известного открытого текста.Если в сжатом файле используются стандартные заголовки, то вскрытие становится ещё прощё.

 

1. Примеры поточных шифров на основе FCSR.

 

• Сдвиговый регистр с обратной связью по переносу, или FCSR (feedback with carry shift register), похож на LFSR

• В обоих есть сдвиговый регистр и функция обратной связи, разница в том, что в FCSR есть также регистр переноса.

• Вместо выполнения XOR над всеми битами отводной последовательности эти биты складываются друг с другом и с содержимым регистра переноса.

• Результат mod 2 и становится новым битом.

• Результат, деленный на 2, становится новым содержимым регистра переноса.

• Регистр переноса не бит, а число.

• Максимальный период FCSR выше, чем LFSR. Любое начальное состояние приводит к одной из четырёх ситуаций. Во-первых, оно может быть частью максимального периода. Во вторых, оно может перейти в последовательность максимального периода после начальной задержки. В третьих, после начальной задержки оно может породить бесконечную последовательность нулей. В четвёртых, после начальной задержки оно может породить бесконечную последовательность единиц. Для определения, чем закончится конкретное начальное состояние, существует математическая формула, но намного проще проверить это опытным путём. Если выходной поток вырождается в бесконечную последовательность нулей или единиц за n битов , где n - длина FCSR, не используйте это начальное состояние. FCSR можно использовать в потоковых шифрах вместо LFSR, а можно комбинировать FCSR и LFSR ,например:

• Каскад FCSR. Каскад Голлманна с FCSR вместо LFSR;

• Каскад LFSR/ FCSR. Каскад Голлманна с генераторами, меняющими LFSR на FCSR и наоборот;

• Генератор "стоп - пошёл " FCSR. Все регистры - CSR; объединяющая функция XOR.

• Генератор "стоп - пошёл " FCSR/LFSR.Регистр-1 - CSR, а Регистр-2 и Регистр-3 - LFSR. Объединяющая функция - сложение с переносом

 

RC4

• Поток ключей в этом алгоритме не зависит от открытого текста.

• Используется S-блок размером 8*8: S(0),....,S(255)

• Элементы представляют собой перестановку чисел от 0 до 255, а перестановка является функцией ключа переменной длины.

• В алгоритме применяются два счётчика (i и j) с нулевыми начальными значениями.

• Для генерации случайного байта выполняется следующее:

• i = (i+1) mod 256 ; j = (i+ S(i))) mod 256;

• меняем местами S(i) и S(j);

• t = (S(i) + S(j)) mod 256; K = S(t).

• Байт K используется в операции XOR с открытым текстом для получения шифротекста.

• Шифрование выполняется примерно в 10 раз быстрее , чем DES.

Инициализация S блока.

• Сначала заполним его линейно: S(0)=0;....;S(255)=255.

• Затем заполним ключом другой 256-байтовый массив, при необходимости для заполнения всего массива повторяя ключ: K(0),...,K(255).

• Установим j=0.

• for(i=0;i<256;i++)

{

j=(j+S(i)+K(i)) mod 256 ;

меняем местами S(i) и S(j);

}

Утверждается, что алгоритм устойчив к дифференциальному и линейному криптоанализу, что в нём нет никаких коротких циклов, и что он в высокой степени нелинеен.

RC4 может находиться в 21700 возможных состояниях.

S-блок медленно изменяется при использовании: i обеспечивает изменение каждого элемента, а j - что элементы изменяются случайным образом.

Идею можно обобщить на S-блоки и слова больших размеров.

 

WAKE

• Алгоритм WAKE(Word Auto Key Encryption) выдаёт поток 32-битных слов,которые с помощью XOR могут быть использованы для получения шифротекста.

• Для генерации следующего слова ключа используется предыдущее слово шифротекста.

• Это быстрый алгоритм.

• Алгоритм также использует S блок из 256 32-битовых значений. Этот S-блок обладает одним особым свойством: старший байт всех элементов представляет собой перестановку всех возможных байтов, а 3 младших байта случайны.

• Сначала по ключу сгенерируем элементы S-блока.

• Затем проинициализируем четыре регистра с использованием того же или иного ключа: A(0),B(0),C(0) и D(0).

• Для генерации слова потока ключей K(i): K(i)=D(i).

• Слово шифротекста С(i) представляет собой XOR слова открытого текста P(i) c K(i).

• Затем обновим четыре регистра:

A(i+1) = M(A(i),D(i)) ;

B(i+1) = M(B(i),A(i+1)) ;

C(i+1) = M(C(i),B(i+1)) ;

• D(i+1) = M(D(i),C(i+1)), где M(x,y)= (x+y) >> 8 xor S((x+y)^255).

• Самым ценным качеством WAKE является его скорость. Однако он чувствителен к вскрытию с выбранным открытым текстом или выбранным шифротекстом.

 

1. Математические методы криптоанализа: метод опробывания, методы на основе теории статистических решений.

Криптоанализ включает определение используемого языка, типа криптосистемы, ключа и исходного текста; обычно именно в этом порядке

Попытку раскрытия конкретного шифра с применением методов криптоанализа называют криптографической атакой на этот шифр. Криптографическую атаку, в ходе которой раскрыть шифр удалось, называют взломом или вскрытием.

Метод «опробывания» (полного перебора, brute force).

V –алфавит

N –его мощность(кол-во букв)

X = (x₁, x₂, …, x_n) ϵ V_n

k^o = (k₁^o, …, k_l^o) ϵ K c V^l_n –ключ данного сеанса шифрования

f(●) –функция зашифрования

y = (y₁, …, y_n) ϵ Vⁿ_N -шифр текст (С)

y = f(X, k^o)

x = f^-1(y, k) -расшифровка

 

1. Линейный криптоанализ.

Линейный криптоанализ изначально разрабатывался для атак на блочные шифры, но применим и к потоковым. Самим разработчиком было подробно изучено его применение к DES.

Криптоанализ происходит в два шага. Первый — построение соотношений между открытым текстом, шифротекстом и ключом, которые справедливы с высокой вероятностью. Второй — использование этих соотношений вместе с известными парами открытый текст — шифротекст для получения битов ключа.

Смысл алгоритма состоит в получении соотношений следующего вида:

где P_n, C_n, K_n — n-ые биты текста, шифротекста и ключа.

 

Данные соотношения называются линейными аппроксимациями. Для произвольно выбранных бит открытого текста, шифротекста и ключа вероятность справедливости такого соотношения P примерно равна 1/2. Такими соотношениями, вероятность которых заметно отличается от 1/2 можно пользоваться для вскрытия алгоритма.

Как и в дифференциальном криптоанализе, сначала криптоаналитик находит некое однораундовое соотношение, затем пытается распространить его на весь алгоритм. В отличие от дифференциального криптоанализа существуют алгоритмы поиска полезных соотношений. Два алгоритма были описаны Мицуру Мацуи, другие появились позже.

В блочных шифрах анализ преимущественно концентрируется на S-боксах, так как они являются нелинейной частью шифра. Наиболее эффективное однораундовое соотношение для алгоритма DES использует свойство таблицы S5. Второй входной бит таблицы равен результату операции XOR над всеми выходными битами с вероятностью 3/16 (смещение в 5/16 относительно 1/2). А для полнораундового DES известно соотношение, выполняющееся с вероятностью 1/2 + 2⁻²⁴.

Линейный криптоанализ имеет одно очень полезное свойство — при определённых условиях можно свести соотношение (1) к уравнению вида:

Здесь отсутствуют биты открытого текста, то есть можно построить атаку на основе только шифротекста. Такая атака является наиболее практичной.

Разностный криптоанализ.

На схеме представлено прохождение одного из этапов DES. Пусть X и X' - пара входов, различающихся на ΔX. Соответствующие им выходы известны и… Таким образом, определенные отличия пар открытых текстов с высокой… Пара открытых текстов, которая соответствует характеристике называется правильной парой, а пара, не соответствующая…

Основные принципы построения асимметричных криптосистем. Стойкость.

Шифросистема RSA. Стойкость.

Шифросистема Эль-Гамаля. Стойкость.

25. Шифросистема на основе принципа «рюкзака».

Шифросистема Рабина. Стойкость.

Алгоритм обмена ключами Диффи-Хеллмана.

Хэш-функции. Требования. Типы функций хэширования.

Хеш-функция- преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины.

 

Требования:

- хеш-функция должна быть чувствительна к всевозможным изменениям в тексте M(вставка, выбросы, перестановки);
- хеш-функция должна обладать свойством необратимости, то есть задача подбора документа M', который обладал бы требуемым значением хеш-функции, должна быть вычислительно неразрешима;
- вероятность того, что значения хеш-функций двух различных документов (вне зависимости от их длин) совпадут, должна быть ничтожно мала

Типы функций хэширования:

• на основе какой-либо трудно вычисляемой математической задачи;

• на основе алгоритмов блочного шифрования (многие из существующих алгоритмов являются стойкими)

• разработанные с нуля(эффективная программная реализация);

Атаки на функции хэширования.

• 2,Атака методом “дня рождения” -для нахождения двух различных сооб- • щений с одинаковыми хэш-значениями. Эта атака основана на парадоксе “дня… • этими множествами.

Функция хеширования MD5.

  После некоторой первоначальной обработки MD5 обрабатывает входной текст… Сообщение дополняется так, чтобы его длина была на 64 бита короче числа, кратного 512. Этим дополнением является 1, за…

Функция хеширования SHA-1.

• SHA-1 реализует хеш-функцию, построенную на идее функции сжатия. Входами функции сжатия являются блок сообщения длиной 512 бит и выход… • Инициализация .Исходное сообщение разбивается на блоки по 512 бит в каждом.… • Определяются четыре нелинейные операции и четыре константы. • • = 0x5A827999 • …

Функция хеширования ГОСТ 3411-94.

Входное сообщение разделяется на блоки по 256 бит. В случае если размер последнего блока меньше 256 бит, то к нему приписываются слева нули для… Каждый блок сообщения, начиная с первого, подаётся на шаговую функцию для… После вычисления конечное значение хеш-функции получают следующим образом:

Алгоритм

1. — Начальное значение хеш-функции. То есть — 256 битовый IV вектор, определяется пользователем. 2. — Контрольная сумма 3. — Длина сообщения

Функция хеширования СТБ 1176.1-99.

Общие положения электронной цифровой подписи. Задачи. Требования.

1. Осуществить аутентификацию источника сообщения. 2. Установить целостность сообщения 3. Обеспечить невозможность отказа от подписи конкретного сообщения.

Прямая и арбитражная цифровая подписи. Примеры.

Прямая ЦП:

При использовании прямой цифровой подписи взаимодействуют только сами участники (отправитель и получатель).

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

Проблемы прямой ЦП:

1. Все зависит от безопасности закрытого ключа отправителя. Если отправитель впоследствии не захочет признать факт отправки сообщения, он может утверждать, что закрытый ключ был потерян или украден, и в результате кто-то подделал его подпись. Можно применить административное управление, обеспечивающее безопасность закрытых ключей, для того чтобы, по крайней мере, хоть в какой-то степени ослабить эти угрозы. Один из возможных способов состоит в требовании в каждую подпись сообщения включать отметку времени (дату и время) и сообщать о скомпрометированных ключах в специальный центр.

2. Другая угроза состоит в том, что закрытый ключ может быть действительно украден у Х в момент времени Т. Нарушитель может затем послать сообщение, подписанное подписью Х и помеченное временной меткой, которая меньше или равна Т.

Арбитражная ЦП:

Каждое подписанное сообщение от отправителя Х к получателю Y первым делом поступает к арбитру А, который проверяет подпись для данного сообщения. После этого сообщение датируется и посылается к Y с указанием того, что оно было проверено арбитром. Присутствие А решает проблему схем прямой цифровой подписи, при которых Х может отказаться от сообщения.

Все участники должны доверять арбитру.

Примеры

Симметричное шифрование, арбитр видит сообщение:

Х→A: M || E_KXA [ ID_X || H(M)]

Предполагается, что отправитель Х и арбитр А разделяют секретный ключ K_ХА и что А и Y разделяют секретный ключ K_АY. Х создает сообщение М и вычисляет его хэш-значение Н(М). Затем Х передает сообщение и подпись А. Подпись состоит из идентификатора Хи хэш-значения, все зашифровано с использованием ключа K_ХА. А дешифрует подпись и проверяет хэш-значение.

A→Y: Е_КAY [ ID_X || M || E_KXA [ID_X || H (M)], T ]

Затем А передает сообщение к Y, шифруя его K_AY. Сообщение включает IDX, первоначальное сообщение от Х, подпись и отметку времени. Y может дешифровать его для получения сообщения и подписи. Отметка времени информирует Y о том, что данное сообщение не устарело и не является повтором. Y может сохранить М и подпись к нему.

В случае спора Y, который утверждает, что получил сообщение М от Х, посылает следующее сообщение к А:

Е_КAY [ ID_X || M || E_KXA [ID_X || H (M)]]

Арбитр использует KAY для получения IDХ, М и подписи, а затем, используя KХА, может дешифровать подпись и проверить хэш-код. По этой схеме Y не может прямо проверить подпись Х; подпись используется исключительно для разрешения споров. Y считает сообщение от Х аутентифицированным, потому что оно прошло через А.

Обе стороны должны иметь высокую степень доверия к А:

1. Х должен доверять А в том, что тот не будет раскрывать K_ХА и создавать фальшивые подписи в форме E_KXA [ID_X || H (M)].

2. Y должен доверять А в том, что он будет посылать Е_КAY [ ID_X || M || E_KXA [ID_X || H (M)]] только в том случае, если хэш-значение является корректным и подпись была создана Х.

3. Обе стороны должны доверять А в решении спорных вопросов.

 

Симметричное шифрование, арбитр не видит сообщение:

Если арбитр не является доверенной стороной, то Х должен добиться того, чтобы никто не мог подделать его подпись, а Y должен добиться того, чтобы Х не мог отвергнуть свою подпись.

Рассмотрим сценарий, который, как и прежде, использует арбитраж, но при этом еще обеспечивает конфиденциальность. В таком случае также предполагается, что Х и Y разделяют секретный ключ K_XY.

X→A: ID_X || E_KXY[M] || E_KXA [ID_X || H(E_KXY[M]) ]

Х передает А свой идентификатор, сообщение, зашифрованное K_XY, и подпись. Подпись состоит из идентификатора и хэш-значения зашифрованного сообщения, которые зашифрованы с использованием ключа KХА. А дешифрует подпись и проверяет хэш-значение. В данном случае А работает только с зашифрованной версией сообщения, что предотвращает его чтение.

A→Y:Е_КAY[ID_X ||E_KXY[M] ||E_KXA[ID_X ||H(E_KXY[M])],T]

А передает Y все, что он получил от Х плюс отметку времени, все шифруя с использованием ключа K_AY.

Хотя арбитр и не может прочитать сообщение, он в состоянии предотвратить подделку любого из участников, Х или Y. Остается проблема, как и в первом сценарии, что арбитр может сговориться с отправителем, отрицающим подписанное сообщение, или с получателем, для подделки подписи отправителя.

Шифрование открытым ключом, арбитр не видит сообщение:

X→A: ID_X || E_KRX[ID_X || E_KUY[E_KRX[M]]]

Х осуществляет двойное шифрование сообщения М, сначала своим закрытым ключом KR_X, а затем открытым ключом Y KU_Y.

Получается подписанная секретная версия сообщения. Теперь это подписанное сообщение вместе с идентификатором Х шифруется KR_X и вместе с ID_X посылается А. Внутреннее, дважды зашифрованное, сообщение недоступно арбитру (и всем, исключая Y). Однако А может дешифровать внешнюю шифрацию, чтобы убедиться, что сообщение пришло от Х (так как только Х имеет KRX). Проверка дает гарантию, что пара закрытый/открытый ключ законна, и тем самым верифицирует сообщение.

A →Y: E_KRA [ID_X || E_KUY[E_KRX[M]] || T]

Затем А передает сообщение Y, шифруя его KR_A. Сообщение включает ID_X, дважды зашифрованное сообщение и отметку времени.

Преимущества шифрования открытым ключом:

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

Некорректные данные не могут быть посланы, даже если KR_X скомпрометирован, при условии, что не скомпрометирован KR_А.

Содержимое сообщения от Х к Y неизвестно ни А, ни кому бы то ни было еще.

Стандарт электронной цифровой подписи DSS.

Национальный институт стандартов и технологии США (NIST) разработал федеральный стандарт цифровой подписи DSS.

Для создания цифровой подписи используется алгоритм DSA (Digital Signature Algorithm).

В качестве хэш-алгоритма стандарт предусматривает использование алгоритма SHA-1 (Secure Hash Algorithm).

DSS первоначально был предложен в 1991 году и пересмотрен в 1993 году в ответ на публикации, касающиеся безопасности его схемы.

DSS использует алгоритм, который разрабатывался для использования только в качестве цифровой подписи (его нельзя использовать для шифрования или обмена ключами). Тем не менее, это технология открытого ключа.

Создание и проверка подписи с помощью алгоритма RSA

Создание и проверка подписи с помощью стандарта DSS

Цифровая подпись на основе алгоритмов с открытыми ключами. Схема Фиата-Шамира.

Пусть h – некоторая хэш-функция, преобразующая исходное сообщение в битовую строку длины m.

Выберем различные простые числа p и q, положим n = pq.

В качестве секретного ключа каждый абонент должен сгенерировать m различных случайных чисел a₁,a₂,…a_mÎZ_n.

Открытым ключом объявляется набор чисел b₁,b₂,…b_mÎZ_n, где b_i=(a_i^-1)² mod n.

Алгоритм вычисления цифровой подписи

1. Выбрать случайное число , .

2. Вычислить .

3. Вычислить .

4. Вычислить

5. Подписью для сообщения М положить пару

Достоинства: возможность выработки цифровых подписей для нескольких различных сообщений с использованием одного секретного ключа, сравнительная простота алгоритмов вычисления и проверки подписей.

Недостатки: большая длина ключа (определяется числом m).

 

Алгоритм проверки

1. По открытому ключу и значению вычислить

.

2. Вычислить .

3. Проверить равенство

Цифровая подпись Эль-Гамаля. Схема RSA.

Пусть – простое число, – примитивный элемент поля .

Выберем случайное число в интервале и вычислим

значение .

Число является секретным ключом,

набор – открытым ключом.

 

Подпись для сообщения М вычисляется по алгоритму:

1. Выбрать случайное целое число , .

2. Вычислить .

3. Для вычислить .

4. Подписью для сообщения М положить пару .

 

Проверка подписи заключается в проверке сравнения

Замечания.

Число r должно уничтожаться сразу после выработки подписи. Оно должно быть действительно случайным и не должно повторяться для различных подписей при одном значении секретного ключа.

В качестве x целесообразнее использовать x=h(M), а не само М. Это защищает схему подписи от возможности подбора сообщений с известным значением подписи

Стандарт электронной цифровой подписи DSS.

DSS основан на трудности вычисления дискретных логарифмов и базируется на схеме, первоначально представленной ElGamal и Schnorr.

Общие компоненты группы пользователей

Существует три параметра, которые являются открытыми и могут быть общими для большой группы пользователей.

1. 160-битное простое число q, т.е. 2¹⁵⁹ < q < 2¹⁶⁰.
2. Простое число р длиной между 512 и 1024 битами должно быть таким, чтобы q было делителем (р - 1), т.е. 2^L-1 < p < 2^L, где 512 < L < 1024 и (p-1)/q является целым.
3. g = h^(p-1)/q mod p,

где h является целым между 1 и (р-1) и g должно быть больше, чем 1,10.

Зная эти числа, каждый пользователь выбирает закрытый ключ и создает открытый ключ.

Закрытый ключ отправителя

должен быть числом между 1 и q -1 и должен быть выбран случайно или псевдослучайно.

x - случайное или псевдослучайное целое, 0<x<q.

Открытый ключ отправителя

вычисляется из закрытого ключа

у = g^x mod p.

Вычислить у по известному х довольно просто. Однако, имея открытый ключ у, вычислительно невозможно определить х, который является дискретным логарифмом у по основанию g.

Случайное число, уникальное для каждой подписи

k - случайное или псевдослучайное целое,

0 < k < q, уникальное для каждого подписывания.

Подписывание

Для создания подписи отправитель вычисляет две величины, r и s, которые являются функцией от компонент открытого ключа (p, q, g), закрытого ключа пользователя х, хэш-кода сообщения Н(М) и целого k, которое должно быть создано случайно или псевдослучайно и должно быть уникальным при каждом подписывании.

r = (g^k mod p) mod q

s = [ k^-1 (H(M) + xr)] mod q

• Подпись = (r, s)

Проверка подписи

Получатель выполняет проверку подписи с использованием следующих формул. Он создает величину v, которая является функцией от компонент общего открытого ключа, открытого ключа отправителя и хэш-кода полученного сообщения.

Если эта величина равна компоненте r в подписи, то подпись считается действительной.

w = s - 1 mod q

u1 = [H(M)w ] mod q

u2 = r w mod q

v = [(g^u1 y^u2) mod p] mod q

Подпись корректна, если v = r

 

 

Стандарт электронной цифровой подписи ГОСТ-Р 34.10-94.

В стандарте ГОСТ 3410 используется хэш-функция ГОСТ 3411, которая создает хэш-код длиной 256 бит. Это во многом обуславливает требования к выбираемым простым числам p и q: р должно быть простым числом в диапазоне

Проверка подписи

Получатель вычисляет

w = H(M)^-1 mod q

u1 = ws mod q

u2 = (q-r)w mod q

v = [(g^u1y^u2) mod p] mod q

Подпись корректна, если v = r.

Для справки Отличия DSS и ГОСТ 3410-94.

Используются разные хэш-функции: в ГОСТ 3410 применяется отечественный стандарт на хэш-функции ГОСТ 3411, в DSS используется SHA-1, которые имеют разную длину хэш-кода. Отсюда и разные требования на длину простого числа q: в ГОСТ 3410 длина q должна быть от 254 бит до 256 бит, а в DSS длина q должна быть от 159 бит до 160 бит.

По-разному вычисляется компонента s подписи. Последнее отличие приводит к соответствующим отличиям в формулах для проверки подписи.

Стандарт электронной цифровой подписи СТБ 1176.2-99.

1999г. Стандарт РБ «Информационная технология. Защита информации. Процедуры выработки и проверки электронной цифровой подписи». Базируется на схеме ЭЦП Шнорра, которая является модификацией схемы Эль-Гамаля.

Параметры.

Допустимые значения параметров и . Уровень стойкости …   Часть преобразований стандарта выполняется в группе , определяемой множеством и операцией : , где . Использование…

Входные данные.

Всякое сообщение , подпись к которому вырабатывается или проверяется, задается последовательностью байтов. Если – -разрядное число по основанию , т.е.

то есть сообщение, полученное вставкой байтов в начало .

Выработка подписи.

1. Выработать случайное секретное число , . 2. . 3. . Если , то вернуться к шагу 1.

Проверка подписи.

1. . 2. . 3. Проверить условия , . Если хотя бы одно из условий нарушается, то подпись признается недействительной и выполнение…

Применение эллиптических кривых в криптографии. Алгоритм шифрования на основе эллиптических кривых.

• Задача состоит в том, чтобы зашифровать сообщение М, которое может быть представлено в виде точки на эллиптической кривой Pm (x,y). • В качестве параметров рассматривается эллиптическая кривая Ep(a,b) и точка… • Участник B выбирает закрытый ключ nB и вычисляет открытый ключ PB = nB × G.

Алгоритмы обмена ключами и электронной цифровой подписи на основе эллиптических кривых.

Создание ключей: Выбирается эллиптическая кривая Ep(a,b). Число точек на ней должно делиться на большое целое n. Выбирается точка Р на… Создание подписи: Выбирается случайное число k из отрезка [1,n-1]. … Проверка подписи: Проверить, что целые числа r и s принадлежат диапазону чисел [0, n-1]. В противном случае…

Стеганографические методы защиты информации. Основные понятия и определения. Области применения.

• В 1983 году Симмонс предложил т. н. «проблему заключенных». Её суть состоит в том, что есть человек на свободе (Алиса), в заключении (Боб) и охранник Вилли. Алиса хочет передавать сообщения Бобу без вмешательства охранника. В этой модели сделаны некоторые допущения: предполагается, что перед заключением Алиса и Боб договариваются о кодовом символе, который отделит одну часть текста письма от другой, в которой скрыто сообщение. Вилли же имеет право читать и изменять сообщения.

• В 1996 году на конференции Information Hiding: First Information Workshop была принята единая терминология:

• Стеганографическая система (стегосистема) — объединение методов и средств используемых для создания скрытого канала для передачи информации.

• При построении такой системы условились о том, что:

• 1) враг представляет работу стеганографической системы. Неизвестным для противника является ключ с помощью которого можно узнать о факте существования и содержания тайного сообщения.

• 2) При обнаружении противником наличия скрытого сообщения он не должен смочь извлечь сообщение до тех пор пока он не будет владеть ключом.

• 3) Противник не имеет технических и прочих преимуществ.

• Сообщение – скрываемая секретная информация

• Контейнер – несекретная информация, используемая для сокрытия сообщения.

• Пустой контейнер (контейнер-оригинал) и заполненный контейнер (контейнер-результат) визуально не должны отличаться.

Алгоритм встраивания информации:

1. Встраивание в стеганокодере секретного сообщения в контейнер-оригинал.

2. Обнаружение в стеганодетекторе скрытого защифрованного сообщения из контейнера-результата.

Стеганогорафическая система (стеганосистема) – это совокупность средств и методов, которые используются для создания скрытого (незаметного) канала передачи информации.

Цель не ограничивать или регламентировать доступ к контейнеру, а гарантировать, что содержащиеся в нем данные останутся неповрежденными (неизмененными) и подлежащими восстановлению.

Требования на построение стегостистемы:

• Должна иметь приемлемую вычислительную сложность реализации.

• Должна обеспечиваться необходимая пропускная способность.

• Методы скрытия должны обеспечивать аутентичность и целостность секретной информации для авторизованного лица.

• Потенциальный нарушитель имеет полное представление о стегосистеме и детали ее реализации (кроме ключа).

• Если факт содержания сообщения становится известным нарушителю, это не должно позволить ему извлечь данные, не зная ключа.

• Нарушитель должен быть лишен технических и других преимуществ в распознании.

Направления:

• Встраивание информации с целью ее скрытой передачи

• Встраивание цифровых водяных знаков

• Встраивание идентификационых номеров

• Встраивание заголовков.

• Защита информации от НСД

• Защита авторского права на интеллектуальную собственность.

• Камуфлирование ПО

• Создание скрытых от законного пользователя каналов утечки информации

Области применения:

• Защита от копирования (электронная коммерция, контроль за тиражированием дисков, распространение мультимедийной информации, камуфлирование ПО).

• Аутентификация (системы видеонаблюдения, электронной коммерции, голосовой почты, электронное делопроизводство).

• Скрытая аннотация документов (медицинские снимки, картография, мультимедийные БД).

Скрытая связь (военные, разведка).

Общая модель стеганосистемы. Проблема устойчивости. Стегоанализ.

• Прекодер обеспечивает предварительную обработку сигнала, например, преобразованием Фурье или вейвлет-преобразованием. Тогда данные можно скрывать… • Упаковка сообщения в контейнер выполняется с помощью стеганокодера. Например, модификация младших значащих бит контейнера.

Методы сокрытия информации в неподвижных изображениях.

• Относительно большой размер файла. • Фиксированный контейнер. • Наличие в большинстве реальных изображений участков с шумовой структурой.

Методы сокрытия информации в текстовых данных.

Методы: • Метод произвольного интервала • Синтаксические методы

Протоколы аутентификации. Двусторонняя аутентификация.

Аутентификация - подтверждение того, что информация получена из законного источника, и получатель действительно является тем, за кого себя выдает. … Взаимная: Применяются для взаимной аутентификации участников и для обмена ключом сессии.

Протоколы аутентификации. Односторонняя аутентификация.

Аутентификация- подтверждение того, что информация получена из законного источника, и получатель действительно является тем, за кого себя выдает. … Односторонняя аутентификация: Применение - электронная почта, для которого шифрование также имеет большое значение.