Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Анализ и синтез криптографических алгоритмов.DOC
Скачиваний:
102
Добавлен:
02.05.2014
Размер:
99.33 Кб
Скачать

Анализ и синтез криптографических алгоритмов Рюкзачная система

Рюкзачный вектор А=(а1,...,аn) упорядоченный набор изn3 различных натуральных чисел аi. Входом задачи о рюкзаке наз-ют пару, состоящую из А и, где А - рюкзачный вектор, а- натуральное число: (А,). Решением для входа (А,) будет такое подмн-во из А, сумма эл-тов которого равно, причем Аiможет в сумме появляться более одного раза. Обычно требуется выяснить обладает данный вход или нет (А,) решением. Если речь идет о криптографии необходимо для заданного входа (А,) построить решение, зная, что такое решение существует.

Алгоритм шифрования

Пусть дано:

  • рюкзачный вектор А;

  • блок С из nдвоичных символов.

Суммируются те компоненты А, для которых соответствующая позиция в С стоит 1. Если эту сумму обозначить через , то расшифрование равносильно нахождению С поили по А и.F.e. n=6, A=(3, 42, 5, 1, 21, 10), C1=(110010), C2=(101101),

Для данного А все криптотексты есть числа не более 81 и не более одного текста соответствует одному криптотексту. Необходима однозначность расшифрования, поэтому рюкзачные векторы А должны обладать следующим свойством: для каждого все входы (А,) обладают не более чем одним решением. Такие рюкзачные векторы называется инъективными.F.e. n=10. A=(14, 28, 56, 82, 90, 132, 197, 284, 341, 455).455=*. =515. Столбиком:(1110010010) (0110100010) (1001111000).Это можно показать если будет читать А справа налево. Можем показать, что элемент * может не входить в решение 515-455=60. Если криптотекст=516, то можно показать, что не имеется соответствующего исходного текста. Для=517 будет единственный исходный текст (1110111000). Рюкзачный вектор А=(а1,...,аn) наз-ся возрастающим (сверхрастущим) если выполняется след-щие условия:aj>aj-1 (соответственноaj>(отi=1 до j-1)ai, гдеj=2,...,n). Для А определимmaxA= max(aj1jn). Пусть х0. Обозначим через[x]целую часть х, т.е. наибольшее целоех. Для целых х иm2 обозначим через (x, modm) неотрицательный остаток от деленияx наm: (x, modm)=x-[x/m]m; x=(x, modm)+[x/m]m. Определим два варианта понятия модульного умножения. Рассмотрим рюкзачный вектор А, целое числоm>maxA и натуральное числоt<m, такое что наибольший общий делительt иmравен 1. Если В=(b1,...,bn) такой вектор, эл-ты которогоbi=(tai, modm), i=1,...,n, то говорят, что В получен из А с помощью модульного умножения отн-но модуляmи множителяt.Условие (t, m)=1 гарантирует существование обратного числаt-1=u, такого чтоtu1(modm)m, 1um - это означает, что также и обратно А получается из В модульным умножением отн-ноm иu. Если условиеm>maxA заменяетсяm>(отi=1 до n)ai, то говорят, что В получается из А сильным модульным умножением отн-ноm иt. При разработки криптосистемы выбираются А,t, m, Bтак, что А явл-ся сверхрастущим, а В получается из А сильным модульным умножением отн-ноm иt. Вектор В раскрывается как ключ зашифрования, а двоичные блоки длиныnпредставляются в виде чисел, полученных с помощью В. Перехватчик сообщения должен решать задачу о рюкзаке для входа (В,). Разработчик же криптосистемы вычисляет, равное (u, modm) и решает задачу о рюкзаке для входа (А,). Лемма: предположим А=(а1,...,аn) сверхрастущий вектор и вектор В получен из А сильным модульным умножением отн-ноm иt. Выполняется условиеut-1(modm),- произвольное натуральное число, а=(u, modm), тогда справедливы след-щие утверждения: 1) задача о рюкзаке (А,) разрешима за минимальное время. Если решение сущ-ет, то оно единственно; 2) задача о рюкзаке (В,) имеет не более одного решения; 3) если сущ-ет решение для входа (В,), то оно совпадает с решением для входа для (А,).F.e. n=10, A=(103, 107, 211, 430, 863, 1718, 3449, 6907, 13807, 27610), m=55207 - больше на две суммы эл-тов А. Выберемtравное 25236, (t, m)=1 - взаимно просты.t-1=u=1061; 106125236 - 1=48555207. В рез-те сильного модульного умножения получается выражениеB=(4579, 50316, 24924, 30908, 27110, 17953, 32732, 16553, 22075, 53620). 25236103= 4579+ 4755207; 10614579= 103+ 8855207; 252301890= 17953+ 78555207; 106117953= 1718+ 34555207; 2523627610= 53620+ 1262055207; 106153620= 27610+ 103055207. Вектор В это открытый ключ к шифрованию, в то время как А,t, u иm явл-ся секретной лазейкой.F.e. применим открытый ключ В=(b1,...bn); n= 10 и зашифруем исходное сообщение (А и В смотри ранее):IN FINLAND CHILDREN USED TO BE BORN IN SAUNA EVEN TODAY IN FANT MORTALITY IS IN FINLAND LOWEST IN THE WORLD. Используя цифровое кодирование: «пробел» - 0, а буквы А-1,...,Z-26. {Далее алфавит и под ним цифры}. Запишем двоичный эквивалент: «пробел» - 00000; А - 00001; В - 00010; С - 00011;D - 00100;...; Y - 11001; Z - 11010. Учитывая, чтоn=10исходный текст разобьем на блоки из двух букв:

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

Двоичный код

Шифр

IN

F

IN

LA

ND

01001 01110

00000 00110

01001 01110

01100 00001

01110 00100

148786

38628

148786

128860

122701

Дешифруем число 148786 и отметим, что 1061148786=285955207+25133. Рассмотрим задачу о рюкзаке: (А, 25133). Решение получается просмотром А справа налево. Как только число в левом столбце становится не меньше текущей просматриваемой компоненты А, записываем 1 и новое число в левом столбце получается вычитанием компоненты из предыдущего числа. В противном случае записываем 0 и число слева не меняется. Результат этих действий может быть представлен след-щим образом:

Число

Компонента А

Символ

25133

25133

11326

4419

970

970

107

107

107

0

27610

13807

6907

3449

1718

863

430

211

107

103

0

1

1

1

0

1

0

0

1

0

Получим 0100101110 IN. Исходный двоичный вектор, из которого получается блокINсчитывается из правой колонки снизу вверх. При дешифровки второго числа 38628 вначале получаем 20717 (остаток) и т.д.F.e. (более сложный).n=20. Выберем модульm=53939986 и сомножительt=54377; t-1=u=17521047; A=(101, 102, 206, 412, 823, 1647, 3292, 6584, 13169, 26337, 52676, 105352, 210703, 421407, 842812, 1685624, 3371249, 6742497, 13484996, 26969992). Сильное модульное умножение дает след-щий открытый вектор В: В=(5492077, 5546454, 11201662, 22403324, 44752271, 35618933, 17189126, 34378252, 14870895, 29687413, 5543594, 11087188, 22119999, 44294375, 34540010, 15140034, 30334445, 6674527, 13457808, 26915616). Текст:IF YOUR FEET CARRY YOU TO SAUNA THEY SUPELY CARRY YOU BACK HOME IN SAUNA ALCOHOL AND TAR DO NOT CURE YOUR DISEASE IT MUST BE FATAL.Т.к.n=20, то 4 буквы текста зашифровываем одновременно.

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

Двоичный код

IFY

OUR

FEET

....

01001 00110 00000 11001

01111 10101 10010 00000

00110 00101 00101 10100

....

Криптотекст получается след-щим: для первой строки: 1344452701, для второй строки: 174686956, для третьей строки: 190623683,... Остаток: 15488011. Легальный получатель сообщения умножает эти числа на u по модулюmи возвращается к сверхрастущему вектору А. Зная А мы можем получить исходное сообщение.