Криптография с использованием шифров Виженера.

Вопрос 1. Основные понятия криптографии. Криптография с использованием шифров Виженера.

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

Конфиденциальность - обеспечениеневозможности доступа к информации несанкционированному пользователю при передаче сообщений по контролируемому противником каналу связи.

Целостность— неизменности ее в процессе передачи или хранении.

Аутентификация — установление подлинности.

Цифровая подпись—уникальная запись, которая формируется при каждом обращении на основе индивидуального цифрового ключа и одного из алгоритмов шифрования. Назначение – подтверждение личности.

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

Протокол — это распределенный алгоритм, определяющий последовательность действий каждой из сторон.

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

Криптография с использованием шифров Виженера.

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

Таблица Виженера

Для русского алфавита

Первая строка служит алфавитом открытого текста, а первый столбец — алфавитом ключа. Для зашифрования открытого сообщения (Тп ) Виженер предлагал в качестве ключевой последовательности (Г) использовать само сообщение (Т0) с добавленной к нему в качестве первой буквы (70), известной отправителю и получателю (этим идея Виженера отличалась от идеи Кардано, у которого не было начальной буквы и система которого не обеспечивала однозначности расшифрования). Последовательности букв подписывались друг под другом:

При этом пара букв, стоящих друг под другом в Г и Т0, указывала, соответственно, номера строк и столбцов таблицы, на пресечении которых находится знак sl шифрованного текста(Тш ).

Пример.

Шифр Виженера. Ключевое слово: Понедельник.

Шифруемое сообщение : Абракадабра

Шифрование: находим в первой строке первый символ сообщения- А,на пересечении с первым символом ключа – П находим первый символ шифрограммы – П. И т.д.

Ответ ППЯЕОЕПЬОЪК

Шифрование

Выберем Криптография с использованием шифров Виженера. - student2.ru

y1 = Ш = 26 + 5 = 31 = Э,

y2 = Н = 10 + 5 = 15 = Н и т.д.

y10 = Я = 33 + 5 = 38 -5 = 5

Получим криптограмму:

- в цифровом эквиваленте – 31,15,27,23,29,11,14,06,23,05

- в буквенном эквиваленте - ЭНЩХЫЙМЕХД

Дешифрование

Согласноx = Dk(y) = (y1 + (33 – k),…, yi + (33 – k)),расшифруем побуквенно криптограмму :

x1 = Э = 31 = 31 + (33 – 5) = 31 + 28 = 59 -33 = 26 = И

x2 = Н = 15 = 15 + 28 = 43 – 33 = 10 = И …

x5 = Ы = 29 = 29 + 28 = 57 -33 = 24 = Ц …

x10 = Д = 5 = 5 + 28 = 33 = Я

Расшифрованный текст «Шифр Цезаря».

2. Аффинный шифр для русского алфавита

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

Криптография с использованием шифров Виженера. - student2.ru

где модульm — размер алфавита, а пара a и b — ключ шифра. Значение a должно быть выбрано таким, что a и m — взаимно простые числа.

Функция расшифрования

Криптография с использованием шифров Виженера. - student2.ru

где Криптография с использованием шифров Виженера. - student2.ru — обратное к a число по модулю m. То есть оно удовлетворяет уравнению

Криптография с использованием шифров Виженера. - student2.ru

Обратное к a число существует только в том случае, когда a и m — взаимно простые. Значит, при отсутствии ограничений на выбор числа a расшифрование может оказаться невозможным. Покажем, что функция расшифрования является обратной к функции шифрования

Количество возможных ключей для аффинного шифра можно записать через функцию Эйлера как Криптография с использованием шифров Виженера. - student2.ru .

Таблица 1.2 Для русского алфавита

Буква	А	Б	В	Г	Д	Е	Ё
Цифра
Буква	Ж	З	И	Й	К	Л	М
Цифра
Буква	Н	О	П	Р	С	Т	У
Цифра
Буква	Ф	Х	Ц	Ч	Ш	Щ	Ъ
Цифра
Буква	Ы	Ь	Э	Ю	Я
Цифра

В качестве примера возьмем исходный текст: «Аффинный шифр «

Шифрование

Выберем К = (2,4) Данный ключ индуцирует следующую подстановку на Z в соответствии с таблицей 6.2. Согласно Криптография с использованием шифров Виженера. - student2.ru

вычислим

Если декодировать числа в буквы, то получим следующее соответствие для букв:

Д	Ё	З	Й	Л	Н	П
С	У	Х	Ч	Щ	Ы	Э
Я	Б	Г	Е	Ж	И	К
М	О	Р	Т	Ф	Ц	Ш
Ъ	Ь	Ю	А	В

Исходному тексту: «Аффинный шифр «соответствует числовая последовательность x=(0,21,21, 9,14, 14,28,10,25,9,21,17).

При первом способе шифрования буквы исходного текста заменяются на буквы нижнего ряда трансформированной таблицы Y

= ЙВВЦЫЫИЧПЦВЮ.

При втором методе шифрования Yвычисляется по формуле Криптография с использованием шифров Виженера. - student2.ru

Y =(0*2+4, 21*2+4, 21*2+4, 9*2+4,14*2+4, 14*2+4, 28*2+4, 10*2+4, 25*2+4, 9*2+4, 21*2+4, 17*2+4)= ( 4,13,13,22,32,32,27,24,21,22,13,5)

Для расшифрованияу следует вычислить 2^-1 в группе Криптография с использованием шифров Виженера. - student2.ru . Очевидно, что 2^-1= 17. Теперь расшифруем у в соответствии с определением правила расшифрования:

x= Dk(х)=((4+29)*17,(13+29)*17,(13+29)*17,(22+29)*17),(32+29)*17,(32+29)*17,(27+29)*17,(24+29)*17,(21+29)*17,(22+29)*17,(13+29)*17,(5+29)*17) = (0,21,21,9,14,14,28,10,25,9,21,17).

Подстановка букв из таблицы 6.2 даёт буквенный исходный текст: «Аффинный шифр».

Биты Сложение

000 100 100

010 101 111

000 100 100

000 101 101

011 100 111

Посмотрите внимательно на среднюю колонку - "налагаемые" битовые наборы циклически повторяются: их меньше, чем блоков.

Наборы из правой колонки объединяем. Поскольку символы алфавита кодируются 5 битами, группируем по 5 бит: ШИФР(БАГ) = 100111100101111 = {19, 25, 15}, то есть нам нужно найти в алфавите символы номер 19, 25, 15 (нумерация ведётся с нуля).

АБВГДЕЖЗИЙ

КЛМНОПРСТУ

ФХЦЧШЩЪЫЬЭ

ЮЯ

Итог - пресловутое УЩП. То естьБАГ изменился до неузнаваемости.

Режим простой замены

Функция f(A_i, K_i), используемая в сети Фейстеля

Для зашифровывания в этом режиме 64-битный блок открытого текста сначала разбивается на две половины (младшие биты — A, старшие биты — B^[3]). На i-ом цикле используется подключ K_i:

Криптография с использованием шифров Виженера. - student2.ru ( = двоичное «исключающее или»)

Криптография с использованием шифров Виженера. - student2.ru

Гаммирование

При работе ГОСТ 28147-89 в режиме гаммирования описанным ниже образом формируется криптографическая гамма, которая затем побитно складывается по модулю 2 с исходным открытым текстом для получения шифротекста.

Схема работы в режиме гаммирования с обратной связью

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

Вопрос 15. Шифрсистема RSA.

Система RSA (Rivest-Shamir-Adleman) была предложена в 1978 г. и в настоящее время является наиболее распространенной системой шифрования с открытым ключом.

Пусть n = p*q — целое число, представимое в виде произведения двух больших простых чисел р, q . Выберем числа е и d из условия

e∙d=1(modφ(n)), (1)

где φ(n)=(p-1)∙(q-1)- значение функции Эйлера от числа n. Пусть k = (n,p,q,e,d) — выбранный ключ, состоящий из открытого ключа kз = (n,е) и секретного ключа kр = (n,p,q,d). Пусть М — блок открытого текста и С — соответствующий блок шифрованного текста. Тогда правила зашифрования и расшифрования определяются формулами:

C=E_k (M)=M^c (modn),D_k (M)=C^d (modn)

(2)

Заметим, что в соответствии с (2) Dk (С) = М. Это вытекает из следующих рассуждений. Для любого целого числа М и любого простого р справедливо сравнение

M^p=M(modp) (3)

В самом деле, (3) равносильно сравнению M^p-M=0(modp) или сравнению

〖M(M〗^(p-1)-M)=0(modp) (4)

Если НОД(М,/>) = р, то р делит М , и поэтому M=0(modp), откуда следует (4). Если же НОД(М, р) = 1, то, согласно малой теореме Ферма M^(p-1)≡1(modp) , откуда также следует (4).

Согласно (1), существует целое число r, такое, что e∙d=r∙φ(n)+1. Отсюда и из (3) получаем следующую цепочку равенств и сравнений:

C^d=〖(M^c)〗^d=M^cd=M^(rφ(n)+1)=M^(r(p-1)(q-1)+1)=M^(rp(q-1))∙M^(-rq+r+1)=(M^p )^r(q-1) ∙M^(-rq+r+1)≡M^r(q-1) ∙M^(-rq+r+1)≡M(modp) (5)

Аналогично можно показать, что

C^d=M(modp) (6)

Поскольку р и q — разные простые числа, то на основании известных свойств сравнений из (5), (6) получаем: C^d=M(modp)

Отсюда и следует корректность определения (2).

Примеры шифрсистемы RSA.

Пример 1

Установим p=3, q=7. Тогда n=p*q=21. Выбираем d как 5. Из формулы (e*5) mod 12=1 вычисляем e=17. Открытый ключ 17, 21, секретный — 5, 21.

Зашифруем последовательность «12345»:

C(1)= 117 mod 21= 1

C(2)= 217 mod 21 =11

C(3)= 317 mod 21= 12

C(4)= 417 mod 21= 16

C(5)= 517 mod 21= 17

Криптотекст — 1 11 12 16 17.

Проверим расшифровкой:

M(1)= 15 mod 21= 1

M(2)= 115 mod 21= 2

M(3)= 125 mod 21= 3

M(4)= 165 mod 21= 4

M(5)= 175 mod 21= 5

Как видим, результат совпал.

Пример 1

Рассмотрим тривиальный пример. Боб выбирает 11 в качестве p. Затем он выбирает e₁ = 2. Обратите внимание, что 2 — первообразный корень в Z_11*. Затем Боб выбирает d= 3 и вычисляет

e₂ = e₁^d = 8.

Получены открытые ключи доступа — (2, 8, 11) и секретный ключ — 3. Алиса выбирает r = 4 и вычисляет C₁ и C₂ для исходного текста 7.

Исходный текст: 7

C₁ = e₁^rmod 11 = 16 mod 11= 5 mod 11

C₂ = (P x e₂^r) mod 11 = (7 x 4096) mod 11 = 6 mod 111

Зашифрованный текст: (5, 6)

Боб получает зашифрованные тексты ( 5 и 6 ) и вычисляет исходный текст.

Зашифрованный текст:

[C₁x (C₂^d)^-1] mod 11 = 6 x (5³)^-1mod 11 = 6 x 3 mod 11 = 7 mod 11

Исходный текст: 7

Пример 2

Вместо того чтобы использовать Криптография с использованием шифров Виженера. - student2.ru длядешифрования, мы можем избежать вычисления мультипликативной инверсии и применить (см. малую теорему Ферма). В Примере 1 мы можем вычислить Криптография с использованием шифров Виженера. - student2.ru .

Правила составления паролей

Типичным требованием, предъявляемым при составлении паролей, является ограничение на минимальную длину паролей. Примером может служить требование, чтобы пароль имел длину не менее 9 букв или цифр. Другими требованиями могут быть наличие в пароле хотя бы одного символа из каждого регистра(верхнего, числового, не алфавитно-цифрового и т. д.), а также требование, чтобы пароль не мог быть словом из имеющегося словаря или частью идентификационной информации доказывающего.

Тотальный перебор паролей

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

Атаки с помощью словаря

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

Одноразовые пароли

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

Существуют три схемы использования одноразовых паролей:

1. пользователи системы имеют общий список одноразовых паролей, который доставляется по защищенному от перехвата каналу связи;

2. первоначально пользователь и система имеют один общий секретный пароль. Во время идентификации, использующей пароль t, пользователь создает и передает в систему новый пароль (t + 1), зашифрованный на ключе, полученном из пароля t;

3. пользователи системы используют одноразовые пароли на основе однонаправленной функции.

Вопрос 21.«Запрос-ответ». (сильная идентификация)

Идея построения криптографических протоколов идентификации типа “запрос-ответ” состоит в том, что доказывающий убеждает проверяющего в своей аутентичности путем демонстрации своего знания некоторого секрета без предъявления самого секрета. Знание секрета подтверждается выдачей ответов на меняющиеся с течением времени запросы проверяющего. Обычно запрос — это число, выбираемое проверяющим при каждой реализации протокола.

Стороны следуют заранее определенной политике. Сообщение принимается только тогда, когда его число (метка сообщения) не было использовано ранее (или в определенный предшествующий период времени) и удовлетворяет согласованной политике. Простейшей политикой является такая:последовательность начинается с нуля и каждое следующее число увеличивается на единицу. Менее жесткая политика состоит в том, что принятые числа должны только монотонно возрастать. Это позволяет работать с учетом возможности потери сообщений из- за ошибок в каналах связи.

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

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

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

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

“Запрос-ответ” с использованием симметричных алгоритмов шифрования

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

Для описания алгоритмов введем следующие обозначения:

z_A - случайное число, вырабатываемое A;

t_A - временная метка А;

E_k - алгоритм шифрования на ключе k;

id(B) - идентификатор В.

Этап

- Ввыбирает один из этих вопросов и Адает на него ответ, который затем проверяетсяВ.

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

В основе протоколов с нулевым разглашением лежит комбинация идей протоколов типа “режь и выбирай” (этот термин происходит от стандартного метода, которым дети делят кусок пирога: один режет, а другой выбирает) и протоколов типа “запрос-ответ”.

Вопрос 24.Хэш-функции

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

В криптографии хэш-функции применяются для решения следующих задач:

· построения систем контроля целостности данных при их передаче или хранении,

· аутентификации источника данных.

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

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

Имитовставки, формируемые с помощью ключевых хэш-функций, не должны позволять противнику создавать поддельные (сфабрикованные) сообщения (fabrication) при атаках типа имитация (impersonation) и модифицировать передаваемые сообщения (modification) при атаках типа “подмена” (substitution).

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

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

Хэш-функцией называется всякая функция h: X -> Y, легко вычислимая и такая, что для любого сообщения Мзначение h(M) = Н (свертка) имеет фиксированную битовую длину.

Как правило, хэш-функции строят на основе так называемых одношаговых сжимающих функций у = f(x_l,x₂) двух переменных, где х₁ и у — двоичные векторы длины m и nсоответственно, причем n — длина свертки. Для получения значения h(M)сообщение М сначала разбиваетсяна блоки длины m (при этом если длина сообщения не кратна m, то последний блок неким специальным образом дополняется до полного), а затем к полученным блокам М₁, М₂,.., М_N применяют следующую последовательную процедуру вычисления свертки:

Криптография с использованием шифров Виженера. - student2.ru

(1)

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

При таком подходе свойства хэш-функции hполностью определяются свойствами одношаговой сжимающей функции f.

Жизненный цикл ключей

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

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