Лекция №17. Алгоритм Solitaire (Пасьянс)

Лекция №16

Потоковые шифры.

Алгоритм Solitaire (Пасьянс).

Идея состоим в раскладывании карт по определенному закону.

52! – число перестановок карт.

Автор – Шнайер.

Текст предстает в виде последовательности букв.

Р = р₁, р₂, …, р_m

i = 1,m, m – мощность алфавита

m=25 для английского алфавита

Р = р₁, р₂, …, р_m

J = j₁, j₂,..., j_m

C = c₁, c₂,..., c_m – шифрограмма

Колода состоит из 52 карт и двух джокеров А и В.

54! = 2,3 *10⁷¹ – число двоичных перестановок

Джокерам А и В соответствует цифра 53.

52 карты делятся на подмножества:

«трефы» - 1-13;

«бубны» - 14-26;

«червы» - 27–39;

«пики» - 40-52.

На основе игры Пасьянс создали алгоритм шифрования.

к_с=< начальное расположение карт>.

Джокер, который расположен левее относительно другого джокера, называется первым джокером, второй джокер – вторым.

Алгоритм.

I. Находим джокер А и перемещаем его циклически вправо через 1 карту. Если джокер А является последней картой, то перемещаем его за первую карту.

Имеем начальную расстановку карт

6 1 5 В 2 3 4 А 8 5 7

Шаг 1.

6 1 5 В 2 3 4 8 А 5 7

II. Находим джокер В и перемещаем его циклически вправо через 2 карты. Если джокер В является последней картой, то перемещаем его за вторую карту. Если джокер В - предпоследняя карта, то помещаем его за первую карту.

Шаг 2.

6 1 5 2 3 В 4 8 А 5 7

III. Меняем местами карты, расположенные левее первого джокера, с картами, расположенными правее второго джокера.

Шаг 3.

5 7 В 4 8 А 6 1 5 2 3

IV. Последнюю правую карту преобразуем в число n. Меняем местами первые n карт со следующими (53-n) картами. Последняя карта остается на месте.

Шаг 4.

4 8 А 6 1 5 2 5 7 В 3

V. Первую левую карту преобразуем в число n. Если (n+1) карта от начала колоды является джокером, то возвращаемся к этапу I.

Шаг 5.

4 8 А 6 1 5 2 5 7 В 3

VI. Фиксируем число с (n+1) номером. Элемент гаммы вычисляется как j= N mod 26.

Далее результат этапа VI является начальным состоянием для вычисления следующих элементов гаммы (m операций).

Пример.

52 карты + 2 джокера

1 2 3 … 52 А В

Шаг 1. 1 2 3 … 52 В А

Шаг 2. 1 В 2 … 52 А

Шаг 3. В 2 3 … 52 А 1

Шаг 4. 2 3… 52 А В 1

Шаг 5. 2 3 … А В 1

J₁=4

2 3 … А В 1

Шаг 1. 2 3 …52 В А 1

Шаг 2. 2 3 … 52 А 1 В

Шаг 3. А 1 В 2 3 … 51 52

Шаг 4. 51 А В 2 3 … 50 52

Шаг 5. 51 А 1 В 2 3 … 49 50 52

J₂=23

И т.д. j₃=10, j₄ = 24.

Генераторы гаммы (ПС последовательностей).

Генератор на основе линейного RG сдвига

2m бит

1

2

………

m

Криптографический анализ линейного RG сдвига.

2m бит, m – длина регистра. Необходимо определить связи. Они определяются матрицей, порождающей последовательность.

X_t+1 = AX_t

Размерность матрицы А mxm.

1. 1, 2, 3, …, m, m+1, …., 2m – разряды

построим группу разрядов S(1) – первые m разрядов

S(2) – вторая группа

…….

S(m+1) групп

2. образуем из групп две матрицы

X(1) 1столбец – 1группа

Х(2) 1столбец – группа S(2)

1234

Х(1)= 2345

2345

Х(2)= 3456

3. на основе матриц выводим соотношение:

Х(2) = АХ(1); А = Х(2)Х(1)^-1

Х(r) → Х(1)^-1

Генераторы на основе необратимых функций.

y = a^x mod m

Генератор BBS (Бюм, Блюм, Шуба)

Х- целые числа, P,Q- большие простые числа.

n = PQ

X принадлежат 0,1,…, (pQ-1)

1. X_i+1 = X_i² mod n

2. представление числа в двоичном коде. От каждого числа берется один разряд. Результат – m-разрядное число. На этом этапе тратится дополнительное время, но повышается криптографическая стойкость.

Генератор RSA.

В основе лежит необратимая функция y = a^x mod m

n = pQ

1. X_i+1 = X_i^e mod n

Для получения диапазона 0,1…, (pq-1), x₀ берется из этого же диапазона и e‹(pq-1)

(e, (p-1)(Q-1)) = 1

2. Аналогично как и в генераторе на основе необратимых функций(BBS) служит для большей криптостойкости.

Второй этап необязателен.

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

X_i+1 › n/2 → “1”

X_i+1 ≤ n/2 → “0”

Генератор RSA требует больше времени, чем алгоритм BBS.

Генератор ПСЧ.

X_i+1 = (aX_i + b) mod n

N = 2^k - разрядная сетка машины. Например к = 32.

Диапазон 0,1,…2^k

Теорема n= 2^k, x₀, a, b

X₀ – целое нечетное число.

Требования к числам a,b

1. (b,n) = 1

2. (a-1) должно быть кратно р, котрое является делителем n.

(a-1) должно быть кратно 4, если n кратно 4.

X_i+1 = ax_i mod n – мультипликативный

(a,n) = 1 – полный период

n – простое

n = L = 2^p-1

Кроме криптографических свойств важны статические.

Примеры тестов статического анализа:

Графические тесты. Построение поля по плоскости по 2 текущим числам из формируемого диапазона. Чем больше точек, тем лучше. Закономерности не должны проявляться.

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

I. особенности реализации:

1. применение нестойких криптографических алгоритмов:

- низкое быстродействие стойких криптографических алгоритмов

- экспортное ограничение

- использование собственных алгоритмов

2. неправильное применение криптографических алгоритмов:

- недостаточная длина ключа или недостаточный объем ключевого пространства

- некачественные процедуры генерации, передачи и хранения ключей

- некачественная процедура инициализации генератора ключей

- некачественные генераторы гамм

- применение криптоалгоритмов не по значению

3. ошибки при реализации криптографических алгоритмов:

- программные ошибки

- зависимость от времени работы

- наличие «дыр»

- неправильная обработка нестандартных ситуаций

- некачественная процедура оперативного обнаружения несанкционированных действий и восстановление работоспособности системы защиты после обнаружения этих действий

II. человеческий фактор:

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