 |
|
Системы, основанные на задаче о рюкзаке.
Простые числа специального вида.
Для чисел n = 2^m – 1 будут простыми только при простом m.
Построение больших простых чисел с использованием полного разложением на простые множители.
n-1 = П(i-1, m) Pj ^aj
Пусть n нечетное натуральное число, n>1 и известно разложение на простые множители Pj. Если для каждого j=1,…,m существует натуральное число aj такое что, aj ^ (n-1) = 1 (mod n), aj^((n-1)/Pj)=1 (mod n).
На этой теореме основан следующий метод Миллера для построения больших чисел: для некоторого набора известных простых чисел P1=2, P2=…, Pm и показателей a1, a2,….am вычисляем n как произведение P1^a1 * P2^a2*…*Pm*am. С помощью некоторого вероятностного теста проверяем является ли n составным числом. Если нет, т.е. n вероятно простое, то генерируется случайная последовательность натуральных чисел из интервала (1,n) и определяются степени aj.
Системы, основанные на задаче о рюкзаке.
Меркли и Хелман предложили криптосистему с публичными ключами, основанную на сложности решения задачи о рюкзаке. Наиболее устойчивую систему предложили Кор-Рейгест, однако потом появились публикации, говорящие об ее изъянах.
Пусть a1, a2, … an последовательность из n натуральных чисел. S тоже некоторое натуральное большое число. Имеет ли место следующее уравнение:
x1a1 + x2a2 + … + xnan = S? Уравнение 1.
Такое решение в котором все xi @ {0,1} называется задачей об укладке о рюкзака, или просто задачей о рюкзаке.
Определить что оставить, а что выбросить задача нетривиальная. При больших n задача о рюкзаке трудна для решения. Эта задача NP (эн полна). Для некоторых последовательностей a1,a2,…,an {ai}(i=1, n) нетрудно найти последовательность 01 для уравнения 1 или показать, что такого решения не существует. Например, для последовательности ai=2^(i-1) будет иметь решение тогда и только тогда 0<=S<=2^n - 1. В этом случае решение находится легко.
Есть более общий класс последовательностей ai для которых уравнение 1 легко решается. Это класс так называемых сверхвозрастающих последовательностей.
Последовательность {ai)(i=1, n) называется сверхвозрастающей если для всех k
СУММА(i=1, k-1) ai < ak.
Алгоритм 1 решает задачу о рюкзаке для сверхвозрастающих последовательностей. Он находит решения последовательностей {xi}(i=1, n) для каждой правой части S для которой есть решение. Идея алгоритма очень простая, из идеи, что сумма СУММА(i=1, n-1) ai < an.
Рассмотрим сверхвозрастающую последовательность {ai}(i=1, 6) = {22,89,345,987, 4567, 45678,} S=5665.
Рассмотрим формирование рюкзачной системы . Рюкзачная система, предложенная Меркли основана на том, что задача о рюкзаке решается сложно, а та же задача для сверхвозрастающих последовательностей допускает легкое решение.
Каждый пользователь создает сверхвозрастающую последовательность длины nu {ui}(i=1, n). Затем выбирает число …. Такие что Nu>SUM(i=1, nu) ui (3). НОД(Wu, Nu) = 1 (4)
Далее пользователь находит такие числа u’I = (Wu * ui) mod Nu. 1<=i<=nu (5) и объявляет последовательность {u’i}(i=1, nu) открытым ключом. Далее пользователь вычисляет значение (Wu)^-1 mod Nu, которое окажется ему полезным при дешифровании. Это число можно получить при помощи расширенного алгоритма Евклида. Действительно, поскольку НОД(Wu, Nu)=1, этот алгоритм дает такие X,Y что 1 = X*Wu + Y* Nu, X*Wu =1 (mod Nu). Каждый пользователь хранит секретик сверхвозрастающей последовательности {ui}(i=1, nu), а также числа Wu, (Wu)^-1 и Nu.
Шифрование.
Предположим, что пользователь Алиса желает послать сообщение Бобу (bi’)(i=1, nB), затем она представляет свое сообщение в виде двоичного вектора m1,m2,…mnB. Затем Алиса посылает криптотекст
С = (i=1,nB)СУММА (mi bi’ ) (6)
Пример.
Публичный ключ Боба имеет следующий вид
{bi’}(i=1, 6) = {44434, 19714, 56639, 31669, 44927,36929}
Пусть {mi}(i=1,6)={1,1,0,0,0,1}. Просуммировав, получим 101077.
Дешифрование.
CxWB^(-1) (mod NB)
WB^(-1) x C = WB^(-1) (i=1, nB) СУММА (mi*bi’) = (i=1, nB) СУММА (mi*bi) (mod NB)
(i=1, nB) СУММА (mi*bi) < NB
(i=1, nB) СУММА (mi*bi’) = (WB^(-1) * C) mod NB (7)
Поскольку последовательность сверхвозрастающая для нахождения сообщения mi можно применить первый алгоритм, в котором правая часть будет выражение CxWB^(-1) (mod NB).
Пример.
Допустим, Боб получил сообщение С = 101077.
WB^(-1) = 39750, NB = 56785.
При этом выполняется условие 3.
Дополнительно пользователю U рекомендуется перед публикованием ключа переставить его элементы, чтобы скрыть их порядок в исходной сверхвозрастающей последовательности. Тем самым криптоаналитик лишается информации о том, какой например элемент Ui’ в публичном ключе получит из минимального элемента секретного ключа U1.
Умножение сверхвозрастающей последовательности на константу W по модулю Nu выполняется для того, чтобы получившаяся задача о рюкзаке выглядела как случайная. Чтобы увеличить этот эффект и тем самым увеличить безопасность криптосистемы, некоторые советуют повторить такое же умножение. Это означает, что пользователь U дополнительно выбирает такие числа Wu’ и Nu’ так чтобы 
, 
, затем он вычисляет 
и объявляет публичный ключ в таком 
, 
(публичный ключ) виде вместо 
, вместо 
. Т.е. мы делаем дополнительные усложнения, чтобы …
Пример при n=3
, умножаем на 17 по модулю 47
умножаем на 3 по модулю 89
Невозможно найти такие целые числа W и N, чтобы непосредственно перевести из ui в ui’’. Это показывает, что 2 модульных умножения не всегда сводятся к одному. Второе преобразование переводит несверхвозрастающую последовательности в сверх возрастающую(после сортировки). Становится понятно, что криптоаналитику Еве жить становится сложнее, поскольку общая задача о рюкзаке является NP (полной) задачей и неизвестен алгоритм, решающий ее за полиномиальное время.
14.03.2013
Сравним 2 стандарта шифрования – Американский и Российский.
Стандарт шифрования DES был опубликован в 1977 году. Он предназначен для защиты от НСД важной, но несекретной информации в государственных и коммерческих организациях США. В 1980 году этот алгоритм был принят в качестве стандарта.
Основные достоинства алгоритма DES:
1) Используется только 1 ключ длиной 56 бит
2) Зашифровав сообщение с помощью одного пакета программ, для расшифровки можно использовать любой другой пакет программ, реализующий DES
3) Относительная простота алгоритма DES обеспечивает высокую скорость его работы
4) Достаточно высокая стойкость алгоритма
Первоначальная идея алгоритма DES была реализована компанией IBM в системе Lucifer. Эта система была основана на комбинировании методов подстановки и перестановки, которые между собой чередовались. В этой системе использовался ключ длиной 128 бит, который управлял состоянием блоков перестановки и подстановки. Но система Lucifer была сложна для практической реализации из-за относительно малой скорости преобразования. DES осуществляет шифрование 64-битовых блоков с помощью 64-битового ключа, в котором значимыми являются всего 56 бит. 8 бит отложены для служебной информации.
Исходный текст - Начальная перестановка – Шифрование ключом 16 раз - Конечная перестановка – Шифротекст.
Все перестановки и коды в таблицах являются стандартными и должны включаться в реализацию алгоритма DES в неизменном виде.
РИСУНОК ПЕРЕРИСОВАТЬ.
Пусть из файла исходного текста считан 64-битный блок T. T преобразуется с помощью матрицы начальной перестановки IP.
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
Биты исходного текста переставляются в соответствии с матрицей IP. 58 бит блока T становится первым битом, бит 50 – вторым. T0 = IP(T). Полученная последовательность битов T0 разбивается на 2 подпоследовательности: L0 и R0 – старишие и младшие биты.
Затем выполняется итеративный процесс шифрования, состоящий из 16 циклов.
Пусть Ti = Li Ri, где Li = t1, t2, …t32 (первые 32 бита), Ri = t33… t64 (последние 32 бита).
Li = R(i-1), i=1,2…16
Ri = L(i-1) (+) f(R(i-1), Ki), i=1,2…16
f – функция шифрования. Ее аргументами являются R(i-1) и 48-битовый ключ Ki, который является результатом преобразования 64-битового ключа шифра K.
Матрица обратной перестановки IP^(-1)
40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30
37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28
35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26
33 1 41 09 49 17 57 25
Связь элементов матриц
IP^(-1) IP
40 01
8 02
48 03
16 04
56 05
Процесс расшифрования является инверсным шифрованию – все действия выполняются в обратном порядке и может быть описан следующим образом:
R(i-1) = Li, i=1,2…16
L(i-1) = Ri (+)
Таким образом, процесс расшифрования с переставленным входным блоком L16 R16, на первой итерации используется ключ К16, на второй – К15 и на последней – К1. На последнем шаге операции будут получены последовательности L0 R0, которые соединяются (контентинируются) в 64-битную последовательность, которая в соответствии с таблицей IP переставляется.
Функция шифрования имеет следующий вид:
1) Расширяем ключ из 32 бит в 48
2) Суммируем по модулю 2 с ключом
Функции S1 – S8 и перестановка битов P 32-битовой последовательности.
Функция расширения E(таблица 4)
32 01 02 03 04 05
04 05 06 07 08 09
08 09 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 01
Модуль.
Полученный результат E(R(i-1)) в соответствии с таблицей 4 складывается по модулю 2 с текущим значения ключа Ki, а затем разбивается на восемь 6-битовых блоков B1, B2, … B8.
E(R(i-1)) (+) Ki = B1 B2 … B8
Каждый из этих блоков используется как номер элемента в функциях матрицы S1, S2,…S8, которые содержат четырехбитовые значения таблицы 5. Выбор элемента в матрице Si осуществляется достаточно оригинальным образом: пусть на вход матрицы Si поступает 6-битовый блок Bi = b1, b2,..b6, тогда 2-битовое число b1b6 указывает номер строки, а 4-битовое число b2b3b4b5 указывает на номер столбца.
Пример.
Пусть на вход матрицы S1 поступает 6-битовый блок B1=100110, тогда b1b6=10=2, а b2b3b4b5=0011=3. Таким образом берется элемент 8. Совокупность B1 B2 … B8 обеспечивает выбор четырехбитового элемента в каждой из матриц S1, S2, …, S8.
В результате получаем S1(B1), S2(B2), … , S8(B8), т.е. 32-битовый блок. Таким образом функция шифрования f(R K)=P() ((1)).
Схема вычисления ключей(Взять фотку у Игоря)
Результат преобразования G(K) разбивается на 2 половинки C0 и D0 по 28 бит каждая. Первые 4 строки матрицы G определяют как будет формироваться C0: первым будет бит 57 ключа шифра, затем 49 и т.д. Следующие 4 строки определяют выбор последовательности D0. После определения C0 и D0 мы начинаем определять каждый раундовый ключ. В зависимости от номера шага итерации идет сдвиг влево на 1 или 2 бита.