Алгоритм Blowfish

Алгоритм Blowfish разработал американец Б. Шнайер. Данный алгоритм базируется на сети Фейстелл, не запатентован. Многораундовый (18 раундов) алгоритм обрабатывает 32-разрядные числа.

Основная функция – операция сложения.

k_c<448 бит>

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

Предварительно формируется массив ключей 448*18.

18 32-разрядных слов (подключей) p₁,p₂,…,p₁₈. Каждый p_i – четыре 32-разрядных вектора. Используется табличное преобразование (нелинейное), применение 32х s-блоков. Каждый s-блок – 256 элементов.

s₁₀, s_11,...,s_1,255

s₂₀, s_21,...,s_2,255

s₃₀, s_31,…,s_3,255

s₄₀, s_41,…,s_4,255

Блок-схема

<64 To>

Перестановка и

Функция F

Алгоритм расширения ключа

1. Исходный ключ получается с помощью ПЧС.

2. Выполняется XOR p₁ c первыми 32-разрядными битами ключа; XOR p₂ – со вторыми 32-разрядными битами и т.д. до p₁₈.

3. Шифрование алгоритмом Blowfish

4. p₁ и p₂ заменяются результатом шага 3.

5. Результат этапа 3 шифруется с помощью алгоритма Blowfish и измененных подключей.

6. p₃ и p₄ заменяются результатом этапа 5.

7. Все элементы p-массива заменяются выходом, постоянно меняющимся.

В алгоритмах DES и ГОСТ таблицы фиксированы, а в Blowfish заключается в том, что ключи формируются в зависимости от исходных данных.

ГОСТ 28147 – 89

Структура алгоритма состоит из трех частей. Предназначен для реализации блочного шифрования. Каждый блок – 64 бита. 64 бита открытого текста преобразуется в 64 биташифрованного текста. М разбивается в двоичном представлении.

М→ М₁, М₂ …, М_к

С₁, С₂ …, С_к

М_i

OT <64>

C_i

ШТ <64>

Степень стойкости зависит от режима.

Все три части используют три основные операции:

· Поразрядное сложение по mod 2

· Сложение двух чисел a, b (32 разряда каждое) (a+b) mod 2³²

· Сложение (a+b) mod (2³²-1)

Часть1 – базовый блок.

Режим работает следующим образом. В часть заносится 64 бита, которые делятся попалам. Далее над ними выполняются операции. Всего проводится 32 раунда. После 32 раундов получаем из М₁→ С₁. такой режим называется заменой.

Структура Ч1 при реализации алгоритма замены

В регистры N₁ и N₂ заносятся числа a, b. Регистры связаны между собой. Исходные 64 бита представляются в виде a₁…a₃₂, b₁…b₃₂. Память с ключом – 256 бит. Память состоит из 8 ячеек по 32 разряда. CM₁ – сумматор, реализующий операцию . Далее следует блок памяти, реализующий нелинейную операцию. Регистр сдвига осуществляет сдвиг на 11 разрядов (своего рода перемешивание). CM₁ – сумматор, реализующий сложение по mod 2. Из N₁ значения выталкиваются в N₂. Таким образом осуществляется один раунд. Также происходят следующие раунды, но во втором раунде в качестве ключа берется х₁, в третьем – х₂ и т.д. Так происходит каждые 8 раундов. Но на последнем раунде использование ключей меняется ключи берутся в обратном порядке.

Цикл	Исходное состояние а(0), b(0)
j = 1 – 24     j = 25 – 31	a(1) = φ(a(0) k0) b(0) b(1) = a(0)   a(j) = φ(a(j-1) kj-1(mod 8)) b(j-1) b(j) = a(j-1)   a(j) = φ(a(j-1) k32-1) b(j-1) b(j) = a(j-1)

После 32 раунда a(32) = a(31), b(32) = φ(a(31) + k₀) b(31)

Базовая часть служит для режима гаммирования.

Часть 1 предназначена для формирования данных.

N_5, N₆ – 32-разрядные регистры

С₁, С₂ – константы

Для получения гаммы используется СМ₄(С_1,N₄)

Хэш-функция базируется на этом алгоритме

Отечественный стандарт предполагает 4 режима:

1. Режим замены (r1);

2. Режим гаммирования (r1, r2,r3);

3. Режим гаммирования с обратной связью (r1,r3);

4. Имитовставка

Режим гаммирования с обратной связью.

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

Открытые данные, разбитые на 64-разрядные блоки Т0⁽¹⁾,Т0⁽²⁾, зашифровываются путем поразрядного сложения по модулю 2 с гаммой шифра Г_ш, которая вырабатывается блоками по 64 бита.

Число двоичных разрядов в блоке Т0⁽ⁱ⁾ может быть менее 64, при этом неиспользованная дел шифрования часть гаммы шифра из блока Гш⁽ⁱ⁾ отбрасывается.

Имитовставка.

Имитовсатавка – это блок из Р бит, который вырабатывают по определенному правилу из открытых данных с использованием ключа и затем добавляют к зашифрованным данным для обеспечения их имитозащиты.

Имитозащита – это защита системы шифрованной связи от навязывания ложных данных.

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

< М₁,…, М_m>

< С₁, …, С_m>

Берется несколько блоков С′_к …С′_m – зашифрованных. Блоки подвергают преобразованию, соответствующему первым 16 циклам алгоритма зашифрования в режиме простой замены.

p = < С′_к …С′_m > - имитовставка

Получателю пересылается < С₁, …, С_{m, р}>. Поступившие к получателю зашифрованные данные расшифровываются, и из полученных блоков открытых данных вырабатывается имтовставка. Эта имитовставка сравнивается с имитовставкой, полученной вместе с зашифрованными данными. В случае несовпадения имитовставок полученные при расшифровании блоки открытых данныхт считают ложными.

С помощью имитовставок проверяются:

1. целостность исходного текста;

2. аутентификация;

3. юридическая подпись.

Американский стандарт шифрования DES.

Стандарт шифрования данных DES(Data Encryption Standart) опубликован в 1977г. Национальным бюро стандартов США.

Основные достоинства алгоритма DES:

1. используется только один ключ длиной 56 бит;

2. зашифровав сообщение с помощью одного пакета программ, для расшифровки можно использовать любой другой пакет программ, соответствующий стандарту DES;

3. относительная простота алгоритма обеспечивает высокую скорость обработки;

4. достаточно высокая стойкость алгоритма.

Алгоритм DES использует комбинацию подстановок и перестановок. DES осуществляет шифрование 64-битовых блоков данных с помощью 64-битового ключа, в котором значащими являются 56 бит (остальные 8 бит – проверочные биты для контроля на честность).

Обобщенная схема процесса шифрования в алгоритме DES.

1. начальная перестановка

2. шифрование

3. конечная перестановка

4. шифротекст

64-битовый блок Т образуется с помощью матрицы начальной перестановки IP.

Биты входного блока Т(64 бита) переставляются в соответствии с матрицей IP: бит 58 входного блока Т становится битом 1, битом 2 и т.д. Полученная последовательность битов Т₀ разделяется на две последовательности: L₀ – левые или старшие биты, R₀ – правые или младшие биты, каждая из которых содержит 32 бита.

По окончании шифрования осуществляется восстановление позиций битов с помощью матрицы обратной перестановки IP^-1.

Реализация шифрования.

R₁ = L₀ f(R₀,k₁)

…………………..

R₁₆= L₁₅ f(R₁₅,k₁₆)

f – функция шифрования

Достигаются принципы Шеннона: перемешивания и рассеивания.

Рассеивание – изменение хотя бы одного бита в открытом тексте в раунде влечет изменение на выходе до пяти бит. После 16 раундов рассеивание полное, влияние на все 64 бита.

В 70-е гг. 1 раунд – сеть Фейстеля.

Принципы Шеннона достигаются благодаря тому, что:

1. преобразования представляются в виде сети Фейстеля;

2. чередование процедур;

3. итеративный процесс реализуется 16 раундов.

Главное требование – обратимость преобразования. Обратимость основана на использовании операций подстановки, перестановки, замены они по определению обратимы.

Алгоритм Эль- Гамаля.

1985 г. Алгоритм Эль- Гамаля основан на проблеме дискретного логарифма. Для вскрытия перебором необходимо 10²⁶ логических операций.

Q, P

А	В к0 кCB
M, Q, P, e	Q, P, e d
1. подготавливает секретное число для шифрования 1<кСА<p-1 (кСА,p-1) = 1	e = y = Q^к^CB mod р d = кCB 1<кСB<p-1
2. С1 = Q^кСА mod р
3. С2 = (y^кСА · M) mod р

4. (C1, C2)

Открытыми являются два вспомогательных числа Q и P

1<Q<p-1

C1, C2 → M = (C2/C1^кCB) mod p

(y^кСА · M/Q^{кСА· кСB}) mod p = (Q^{кСА· кСB} · M/Q^{кСА· кСB}) mod p = M mod p

Пример:

P = 11, Q = 2, M= 5

А: кСА = 9	В: кCB = 8
С1 = 2^9 mod 11 = 6	e = y = 2^8 mod 11 = 3
С2 = (3^9 · 5) mod 11 = 9
(6,9)	(9·(6^8)^-1) mod p = 5

Электронно-цифровая подпись (ЭЦП)

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

Функции:

1. Авторство;

2. Целостность;

3. Аутентификация.

	Ф1
	Ф2

Ф1 – некий документ

Ф2 – приложение к Ф1

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

Ф2 = у = (М, к_с), где с – некие секретные данные

Алгоритм постановки подписи выполняет сторона А. Реализует алгоритм проверки подписи сторона В.

ЦП на основе алгоритма RSA

Используется функция хэширования Н(М) = m << M

B:

e, n, M, C

m′ = C^e mod n

m = H(M)

Проверяет m = m′

(этап хэширования)

C = m^d mod n =

(C, M)

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

ЦП на основе алгоритма Эль-Гамаля

А: Q, P, M	В: Q, P, y
1. 1<kСА<p-1	(M, С1, С2)
2. e = y = Q^kCB mod р 3. m = H(M) 4. 1<k<p-1, (k, p-1) = 1 5. С1 = Q^к mod р 6. m = (kСА·C1 + k·C2) mod (p-1) Находим С2 (С1, С2)	1. m = H(M) 2. A = (y^С^1·C1^С2) mod p 3. A = Q^m mod p 4. A = A′

Дополнение к RSA.

1. Почему работает RSA

Х – ОТ

Y – ШТ

A: y = (ax + b) mod m,

m – число букв в алфавите

а,b – некоторые числа

k = (a,b) – ключ

B: x = E_k(y) = [(y + (m-b))·a^-1] mod m

a→ a^-1

Если m – простое число, то a^-1 есть у каждого элемента из 1…(m-1).

Если (a,m) = 1, то не будет совпадений в значениях зашифрованного текста.

Чтобы однозначно поставить в соответствие С и М, требуется k₁ k₂

e · d ≡ 1 mod φ(m)

Ek₁(M) = C

Dk₂(C) = M

С = M^e mod m; m = p·q

a ≡ b mod m; a·b = m·k + r

M<m; (M,m) = 1;

С^d mod m = M = M^e·d mod m = M^(1+φ(m)k) mod m = M · M^φ(m)k mod m = M mod m,

так как e·d ≡ 1 mod φ(m)

e·d = 1 + φ(m)·k,

a^φ(m)k ≡ 1^k mod m, (a,m) = 1

Необходимо доказать, что p·q | M^ed - M для любых М

M^ed mod p = M mod p

M^ed mod q = M mod q

p| M^ed - M

q| M^ed - M

(M · M^φ(m)k) mod p = M · M^(p-1)(q-1)k mod p = M mod p

(M · M^φ(m)k) mod q = M · M^(p-1)(q-1)k mod q = M mod q

M · M^(p-1)(q-1)k mod p = 1

M · M^(p-1)(q-1)k mod q = 1

Следовательно, p·q| M^ed – M. По теории сравнимости: если одно Ито же число делится на p и на q, то оно делится и на их произведение.

2. Выбор p и q

p = 2^p - 1 – нельзя брать такое р

Получение простых чисел для алгоритма RSA

r, s, t – простые числа

Число р называется простым устойчивым, если оно удовлетворяет следующим условиям:

1. р ≡ 1 mod r

2. p ≡ (s-1) mod s

3. r ≡ 1 mod t

Числа r, s, t должны удовлетворять следующим критериям:

1. r ≡ (u-1) mod u

2. s ≡ 1 mod w

3. s ≡ (v-1) mod v, где u, v, w – простые числа

Пример:

р = 19819 = 2·3·3·17·653 + 1 = 2·2·5·97·103-1

р – устойчивое простое число

Процедура получения устойчивых простых чисел

1. Генерируются простые числа s,t

2. Получаем простое число r такое что, (r-1) делит t без остатка: r-1|t

На основе этих двух операций получаем простое число р по следующей формуле:

P = U(r,s) + krs, где k – подборное натуральноге число

Число р должно удовлетворять следующим свойствам:

· p ≡ 1 mod r

· p ≡ (s-1) mod s

· U(r,s) = (s^r-1 – r^s-1) mod rs

Цифровая подпись DSA (Digital Standart Alhoritm)

Появилась в 1991 г. Основана на базе подписи Эль – Гамаля.

Исходные числа – три простые числа G, P(512-1024 бит), Q(160 бит).

q|p-1

А:	В:
1. Формирует случайное число х 1<x<q	1. Вычисляет w = 1s mod q
2. Вычисляет y (открытый ключ) y = G^x mod р 3. Хэширование m = h(M) 1<m<q 4. Формирует случайное число kA 1< kA <q 5. Вычисляет число r r = (G^kA mod р) mod q 6. Вычисляет число s s = (m+rx/ kA) mod q ЭЦП – (r,s) 7. (r, s, m)	2. m = h(M) 3. U1 = (m·w) mod q U2 = (r·w) mod q 4. v = ((G^U1·y^U2) mod p) mod q 5. Проверка равенства v = r

Дата добавления: 2014-01-15