автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Сплайн-вэйвлеты и их некоторые применения

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

00346Э216

На правах рукописи

Левина Алла Борисовна СПЛАЙН-ВЭЙВЛЕТЫ И ИХ НЕКОТОРЫЕ ПРИМЕНЕНИЯ

05.13.18 — математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

1 I, 2359

Санкт-Петербург 2009

Работа выполнена на кафедре параллельных алгоритмов математико-механического факультета Санкт-Петербургского государственного университета

Научный руководитель: доктор физико-математических наук,

профессор Демьянович Юрий Казимирович

Официальные оппоненты: доктор физико-математических паук,

профессор Жук Владимир Васильевич (Санкт-Петербургский государственный университет)

доктор физико-математических наук, профессор Ходаковский Валентин Аветикович (Санкт-Петербургский государственный университет путей сообщения)

Ведущая организация: Научно-исследовательский вычислительный центр Московского государственного университета им. М.В. Ломоносова (НИВЦ МГУ)

Н- ■ <, сс Защита диссертации состоится " ьи-слц 2009 г. в часов

на заседании совета Д 212.232.51 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 28, ауд. 405.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан "¿У" Л/ул ^..: е'2009 г.

Ученый секретарь диссертационного совета, доктор физ.-мат. наук,

профессор Даугавет И.К.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы

Сплайны » вэйвлеты широко используются для обработки числовых информационных потоков (см. [1|); эта область исследований относится к численным методам. Использование цепочек вложенных пространств сплайнов позволяет строить вэпвлетные разложения (декомпозицию и реконструкцию) в весьма общих условиях, в том числе, с использованием неравномерной сетки (см. [2]), последняя может рассматриваться как ключ в шифровании исходного числового потока, при котором результаты шифрования представлен вэйвлетным разложением. Поскольку постоянно рассматриваются новые способ шифрования, то построение сплайн - вэйвлетных разложений и разработка на их основе сплайн-вэйвлетных криптосистем представляются актуальными.

Одной из областей математического моделирования традиционно является криптография. Началом современной криптографии можно считать работы Клода Шеннона опубликованные в 1948 году "A Mathematical Theory of Communication"B которой сформулированы основы теории информации, большую ценность представляет другая его работа - "Communication Theory of Secrecy Systems". В основу блочных шифров легли работы Хорста Фейстеля начатые им в 1971 году и опубликованные в журнале Scientific American в 1973. Было введено понятие "сеть Фейстеля", которое легло в основу большинства современных блочных шифров. Развитием криптографии, созданием и исследованием новых алгоритмов занимались многие ученые: У. Фридман, Д. Копперсмит, Й. Дамен и В. Раймен, Р. Ривестом, М. Робшау и Р. Сиднеем, Б. Шнайер, Э. Бихам и А. Шамир, Мапуи и многие другие.

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

Цель диссертационной работы

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

Методы исследования

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

Достоверность и обоснованность

Достоверность результатов подтверждена строгими доказательствами; результаты согласуются с проведенными численными экспериментами.

Результаты, выносимые на защиту

1. Построены новые сплайн-вэйвлетные разложения и изучены их свойства.

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

3. Проведен анализ устойчивости предложенных алгоритмов по отношению к криптоатакам.

4. Проведен анализ стойкости алгоритмов, установлены условия, в которых упомянутые алгоритмы являются абсолютно стойкими.

5. Теоретические результаты апробированы на модельных числовых примерах с использованием комплекса программ, основанных на предложенных алгоритмах.

Научная новизна

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

Теоретическая и практическая полезность

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

Апробация работы

Основные результаты были представлены на следующих конференциях и семинарах:

1. Процессы управления и устойчивость. XXXVII международная научная конференция аспирантов и студентов, С.-Петербург, Россия, 10-13 апреля

2006 г.

2. Процессы управления и устойчивость. XXXVIII международная научная конференция аспирантов и студентов, С.-Петербург, Россия, 9-12 апреля

2007 г.

3. Космос, астрономия и программирование (Лавровские чтения), С.-Петербург, 20-22 мая 2008 г.

4. World Congress on Engineering 2008, London, U.K., 2-4 July, 2008.

5. International School on Mathematical Cryptology, Mathematical Foundations of Cryptology, Barcelona, Spain, 21-27 September 2008.

6. 2>ri Information Security and Cryptology Conference, Ankara, Turkey, 25-27 December.

7. Fast Software Encryption 2009, Leuven, Belgium, February 22-25, 2009.

8. Семинар кафедры параллельных алгоритмов математика-механического факультета Санкт-Петербургского государственного университета.

Публикации

Основные результаты опубликованы в восьми работах [1-8]. Работа [6J опубликована в издании входящем в список рекомендованных Высшей аттестационной комиссией на момент публикации. В работах (3, 6) диссертанту принадлежит реализация идеи использования сплайн-вэйвлетных разложений в криптографии, описание процессов шифрования и дешифрования. В работе [б] диссертантом описан алгоритм, основанный на сплайн-вэйвлетных разложениях первого порядка, данный алгоритм представлен для блочного шифрования.

Структура и объем работы

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

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе приведен краткий обзор классических симметричных шифров (см. [3]), введено понятие блочных и поточных шифров. Рассмотрены пассивные и активные атаки, введено понятие стойкости шифров.

Приведена Теорема Шеннона о стойкости криптоалгоритмов. Далее излагаются наиболее известные симметричные алгоритмы блочного шифрования, шифр Фейстеля, DES и алгоритм Rijndatl. который является стандартом шифрования США с 2002 года. Во второй главе рассматриваются сплайн-вэйнлетные разложения. Для координатных сплайнов строятся системы функционалов {i/'^Jisz биортогопальные системам координатных сплайнов {uj}jez-

Пусть X : ... < < zo < xi < ...- сетка,

а = lim Xj, ß = lim Xj,

3 — -00

положим здесь а и ß могут быть конечными или бесконечными. Для фиксированного к G Z положим

— def ■ ^ 1 1 — dei ■ » def

Xj = Xj при j < к — 1, и Xj = xJ+1 при j > к, £ = хк,

и рассмотрим новую сетку X : ... < < xq < Xi < ____ Таким образом

сетка Хполучается из сетки X выбрасыванием узла

Для сетки X, полученной из сетки X удалением одного узла, строятся сплайны Löj, устанавливаются калибровочные соотношения, выражающие сплайны Gj в виде линейной комбинации сплайнов uij\ üi = Yljd

Теорема 1. Для сплайнов первого порядка коэффициенты d^j, € Z отыскиваются по формулам:

dij = ¿ij при i < k — 3, Vj 6 Z,

dk-2,k-2 = 1, dk-2,k-i = (zjfc+i - Xjfc)(l*+1 - Xk-i)'1,

dk-2,j = 0 npuj ^ {k — 2, k — 1}, <h-i,j = 0 npuj £ {k — 1, k},

1 = (xk - xk-i)(xk+i ~ Xk-irffc-i.fe = 1,

dij = &i,j-i при i > k, Vj e Z.

Для сплайнов второго и третьего порядков устанавливаются аналогичные калибровочные соотношения.

Калибровочные отношения для сплайнов второго порядка представлены в теореме 2.

Теорема 2. Справедливы соотношения

ü?i = J^ijWj, i

где для i,j&"L числа dij отыскиваются по формулам:

dij = &i,j при г < к — 4,

4-з,/с-з = 1, ¿к-з,к-2 - (хк - 0(xk-Xk-2)~l,dk~s,j = 0 при j £ {к - 3,к - 2}, dk-2,k-2 = (i-Xk-2)(Xk-Xk-2)~l,dk-2,k-l = (Zfc+1 ~ -Xfc-l)-1,

rffc-2j=0 при j ${k-2,k-l},

¿к-1,к-1 = (С - Хк-1)(хь+1 - ^-1) \ (1к_ик = 1, = 0 гари з${к- 1, к},

<1,^ = при г > к.

Далее во второй главе строятся сплайн-вэйвлетные разложения и выводятся формулы реконструкции и декомпозиции.

пространство, являющееся линейной оболочкой функций ш,-,

П(Х)1Г{ и | ^ е К1 };

з

пространство П(Л') называется пространством сплайнов на сетке X, а и^ — образующими этого пространства.

В соответствии с этим определением П(Х) является пространством сплайнов на сетке X,

ЩХ) = { и | й"= Уо,- € К1 }.

з

Согласно теореме 1 справедливо включение С

Рассматривается оператор Р проектирования пространства Г2(Х) на подпространство задаваемый формулой

Рий и) щ V« 6 ПрГ).

з

Это проектирование определяет прямое разложение

П(Х) = П(Х)+ИЪ, (1)

где \\гк — пространство взйвлетов.

Пусть и 6 П(Л'); используя соотношение (1), получаем два представления элемента и

j

и = ^ аА + Е 1 ¿

Связь между коэффициентами этих представлений устанавливается в следующем утверждение:

Теорема 3(Формулы декомпозиции). Для сплайп-вэйвлетного разложения (1) пространства (1(Х) сплайнов первого порядка верны формулы:

ai = ^ при г < к — 2, = при г > А; — 1,

Ь= 0 яри j ф к —\ Ьк-1 = С/Ь-1 - - Хк)(хк+1 - Хк-1)'1Ск-2~ ~(хк - Хк-1)(хк+1 - Хк-!)'1^.

Теорема 4( Формулы реконструкции). Для рассматриваемого сплайи-вэйвлетног< разложения (1) пространства П(Х) спла,йгюо первого порядка верны. формулы:

сг = aj при] < к — 2, с] = npuj >

Оп-1 = (Хк+1 ~ Хк){Хк+1 - Хк_1)_1а*_2 + (х*: - Хк~1)(хШ - Хк-1)~1ак^ +

Также выведены формулы реконструкции и декомпозиции для сплайнов второго и третьего порядка.

Теорема 5. Для рассматриваемого сплайн-вэйвлетного разложения (1) пространства 0.{Х) сплайнов второго порядка формулы реконструкции имеют вид

с; = а] + Ь] при ] < к — 3, Ск-2 = ак-3(хк - ()(хк - ж^)-1 + ак-2(£ - хк-2)(хк - хк-2)-1 + Ьк-2, с/с-1 = ак-2{хк+1 - 1 ~ я/с-О-1 + - - + Ьк-и

С] = + Ьу при] > к.

Теорема 6. Для сплайн-вэйвлетпого разложения (1) пространства ЩХ) сплайнов второго порядка формулы декомпозиции имеют вид

а{ = сч при г < к — 3,

«4-2 = -Йь - - ^-гГ'с*-з + (ж* - ж^-гКС - хк-2)~1ск„2, = С>+1 ПР" * > А: — 1, = 0 при ] фк — 1,

"(С - ЯЬ-ОК - Ж|Е_2)С|£| (хМ - Хк-!)-1^ - Хк-2)~\

Для полиномиальных сплайнов первого порядка рассматривается вопрос о восстановление сетки по исходному потоку и по вэйвлетной составляющей и о построение сетки по поступающему потоку. Эти результаты сформулированы в следующих теоремах: Теорема 7. Если

ск-2 Ф ск,

то узел £ определяется однозначно по формуле

i = Хк-1 + (¡к(хк+1 - Хк-1),

где

ск-1 — ск-2 - Ьк^х дк =-•

ск - ск-2

Если же

Ск-2 = Ск, 8

то в качестве Ç можно взять любую точку интервала

Теорема 5. В условиях теоремы. 4 при 2 oj, вэйвлетная составляющая bk-i jxieua пулю тогда и только тогда, когда, выполнено соотношение

Ск - Cfc-l hk Ск~ 1 - ск-2 Л/t-i '

где hkd=xk+i - хк.

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

Ключ К имеет две составляющие: сетку X и порядок выбрасывания узлов ■у: К = (X, 7); здесь X = {xj}j=o,...L-i, где L количество узлов в сетке, Xj— (различные) узлы сетки. 7 = {7n}n=i,...A', К число раундов шифрования, 7„—номер выбрасываемого узла. Сетку X можно считать периодической (имея ввиду, например, сетку на окружности): xJ+i, = Xj для V/ € Z, L— натуральное число Ь>Ъ.

Открытым текстом является последовательность С = J С Z. От-

крытый текст разбивается на I блоков |Cj| одинаковой длины, \Ci\ = M, |Q| — число элементов в блоке, г — 1,2,.../. На к—м раунде число элементов преобразованного блока С~к равно M — к\ при необходимости последовательность C£_fe = =1,...продлевается периодически с периодом M — к.

Все вычисления проводятся в конечных нолях, по модулю N, где N—простое число. N передается вместе с открытым текстом. При шифровании сплайнами первого порядка считаем, что Ç Ф £~*+1(modJV), где г—номер раунда, а узел на г—ом раунде с номером Здесь и в дальнейшем все неравенства относятся к конечным полям классов сравнений по модулю N.

Для сплайнов второго порядка предполагается, что:

= ОД-

Для сплайнов третьего порядка: = 2,3,

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

На каждом раунде из сетки выбрасывается один узел с номером у^, где к—но мер раунда, получается "подключ", используемый на этом раунде. Далее при шифровании по формулам декомпозиции вычисляем последовательность {c~k}içj, после проведения К раундов получается шифротекст. Все раундовые функции обратимы. При дешифровании текст восстанавливается с помощью формул реконструкции.

Представленные алгоритмы могут работать с блоками произвольной длины, в частности, с блоками равными 512 и 1024 бит, что раньше не представлялось возможным для алгоритмов 3DES и Rijndael.

В этой главе представлены численные примеры, демонстрирующие работу предложенных алгоритмов. Также продемонстрирована работа алгоритмов с блоками длиной 128, 256 и 512 бит.

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

Теорема 8. Если для к £ 1, ...,К выполнены соотношения

Чк-1 г Чк+1 >

(^-ЧГ^Ц-^-О"1;

где и х~к элементы сетки X ф X;

• Ж7И-1 Ф Х7к>

то криптосистема, основанная на вэйвлетном разложении сплайнов первого порядка, является абсолютно стойкой.

Теорема 9. При выполнении соотноше?шй, где к £ 1,..., К,

• с;*-+з Ф с^-21;

• {^к - - ^ ~ + - Ф О-((^ - ад - - + (С - о,

. ((*-* - ад - (х-* - + (с - ) / о,

г(?е £ г/звл, выбрасываемый на к—ом раунде из сетки X, при этом, 7 ^ 7,

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

Теорема 10. Если при к £ \,...,К справедливы формулы

• С1к-4, Г С7к-3 .

• С7*-2 Ф с7к~\>

• (?« - <-3) - - +- * о,

■ (ё - + С^З1 • - - (? - # О,

гс?е х~к_3, х~к и элементы сетки X ф Х\

• (s^1 • « - О + с-^з1 ■ « - s-*.,) - (i - ^ О,

Hïl

где £ узел, выб})асываемый на к—ом щунде из сетки X, при этом 7 ф 7,

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

Проведен анализ устойчивости алгоритмов к атаке методом перебора и к атаке с выбором открытого текста.

В заключении перечислены основные результаты исследований.

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

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

Список цитируемой литературы

[1| Демьянович Ю. К. Минимальные сплайны и всплески // Вестн. С.-Петерб. ун-та. Сер. 1. 2008. Вып. 2. С. 8-22.

[2j Малла С. Вэйвлеты в обработке сигналов // Пер. с англ. Я. М. Жилей-кина. М.: Мир, 2005. 671 с.

[3] Смарт Н. Криптография // Москва: ТЕХНОСФЕРА, 2005. 528с.

Список опубликованных работ по теме диссертации

[1| Левина А. Б. Устойчивость алгоритмов шифрования при использовании параллельных систем // Процессы управления и устойчивость: Тр. 37-й междунар. науч. коиф. аспирантов и студентов. СПб., 10-13 апреля 2006г. / Под ред. А. В. Платонова, Н. В. Смирнова. - СПб.: Изд-во С.-Петерб. ун-та, 2006. С. 365-367.

[2[ Левина А. Б. Распараллеливание алгоритма Rijndael // Процессы управления и устойчивость: Тр. 38-й междунар. науч. конф. аспирантов и студентов. СПб., 9-12 апреля 2007г. / Под ред. А. В. Платонова, Н. В. Смирнова. - СПб.: Изд-во С.-Петерб. ун-та, 2007. С. 381-386.

[3] Демьянович Ю. К., Левина А. Б. Вэйвлетные разложения и шифрование// Методы вычислений-2008: Выпуск 22: Изд-во С.-Петерб. ун-та, 2008. С. 41-63.

[4] Demjanovich Yu. К., Levina А. В. Encryption with first order splines // Third Information Security Cryptology Conference, Ankara, Turkey, 25-27 December 2008. p. 169-172.

[5| Levina A. B. Cryptoalgorithm Based on Formulas of Reconstruction and Decomposition on the Non-uniform Grid // Lecture Notes in Engineering and Computer Science, World Congress on Engineering 2008, London, U.K. 2-4 July, 2008. p. 17241727.

[G] Демьянович Ю. К., Левина А. Б. О вэйвлетных разложениях линейных пространств над произвольным нолем и о некоторых приложениях,'/ Журнал Математическое моделирование - 2008: Том 20, номер 11, С. 104-108.

|7] Левина А. Б. Работа криптосистемы, основанной на формулах реконструкции и декомпозиции на неравномерной сетке/,/ Математические модели теория и приложения, сборник научных статей - 2008: Выпуск 9, С. 3-29.

[8| Levina А. В. Block ciphers based on wavelet decomposition of splines// http://fse2009rump.cr.yp.to/5e510e48dlel66b3e7ade715bcab744e.pdf

Подписано к печати 20.04.09. Формат 60 х 84 Vie. Бумага офсетная. Гарнитура Times. Печать цифровая. Печ. л. 1,0. Тираж 100 экз. Заказ 4448.

Отпечатано в Отделе оперативной полиграфии химического факультета СПбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26 Тел.: (812) 428-4043,428-6919

Введение

1 О некоторых алгоритмах шифрования

1.1 Краткий обзор симметричных шифров

1.2 Стойкость шифротекста, ложные ключи, расстояние единственности и энтропия.

1.3 Шифр Фейстеля и DES.

1.4 Алгоритм Rijndael.

1.5 Криптоустойчивость алгоритмов.

2 Сплайн-вэйвлетные разложения

2.1 Предварительные обозначения и биортогональная система функционалов для сплайнов первого порядка.

2.2 Укрупнение сетки и калибровочные соотношения.

2.3 Вэйвлетное разложение.

2.4 Формулы реконструкции

2.5 О восстановлении сетки по числовому потоку

2.6 Реализация биортогональной системы для координатных сплайнов второго порядка.

2.7 Калибровочные соотношения.

2.8 Декомпозиция и реконструкция для сплайнов второго порядка

2.9 Вложенность пространств сплайнов третьего порядка и калибровочные соотношения.

2.10 Вэйвлетное разложение.

3 ШИФРОВАНИЕ С ПОМОЩЬЮ СПЛАЙН-ВЭЙВЛЕТНЫХ

АЛГОРИТМОВ

3.1 Предварительные обозначения.

3.2 Сплайн-вэйвлетное шифрование первого порядка

3.3 Процесс дешифрования.

3.4 Пример шифрования.

3.5 Блочное шифрование первого порядка.

3.6 Процесс дешифрования при использовании алгоритма в качестве блочного шифра.

3.7 Сплайн-вэйвлетное шифрование второго порядка

3.8 Процесс дешифрования.

3.9 Иллюстративный пример шифрования второго порядка

3.10 Блочное структурирование алгоритма.

3.11 Дешифрования при блочном подходе

3.12 Использование сплайн-вэйвлетов третьего порядка.

3.13 Особенности дешифрования третьего порядка.

3.14 Иллюстрация процесса шифрования/дешифрования.

3.15 Сплайн-вэйвлетное шифрование третьего порядка. Блочное шифрование/дешифрование.

4 ЭФФЕКТИВНОСТЬ СПЛАЙН-ВЭЙВЛЕТНОГО ШИФ

РОВАНИЯ

4.1 Теоремы Шеннона.

4.2 Проверка условий теоремы Шеннона для сплайн-вэйвлетного шифрования первого порядка.

4.3 О выполнении условий теоремы Шеннона при шифровании второго порядка

4.4 Об эффективности шифрования третьего порядка.

4.5 Криптоанализ алгоритмов сплайн-вэйвлетного шифрования

Сплайны широко используются при математическом моделировании различных процессов механики и физики. Наряду с классическими сплайнами появились минимальные интерполяционные сплайны, обладающие конструктивной простотой и численной оптимальностью (В.С.Рябенький). Дальнейшие исследования, связанные с вариационно-сеточным методом и методом конечных элементов (С.Г.Михлин), позволили построить и изучить свойства минимальных сплайнов, получаемых из аппроксимацион-ных соотношений и определяемых на существенно неравномерных сетках, в том числе и на сетках с конечными точками сгущения (Ю.К.Демьянович).

Интерес к области всплесковых (вэйвлетных) разложений связан с широким применением этих разложений в теории информации и в задачах обработки больших массивов чисел; основными методами исследования являются методы гармонического анализа. Информационные числовые массивы (называемые также цифровыми сигналами или информационными потоками) столь велики, что в первую очередь создаются средства их экономного компьютерного представления, обработки, хранения и передачи по каналам связи. Для достижения этих целей из информационного потока выделяют основной поток (несущий основную информацию), уточняющий информационный поток (его иногда называют вэйвлетным 5 потоком) и поток с несущественной информацией (который обычно отбрасывают); иногда последний поток вообще не рассматривается: в этом случае исходный поток должен однозначно восстанавливаться по основному и вэйвлетному потокам. Вопрос о том, какая информация является основной, какая уточняющей, а какая несущественной, выходит за рамки математических исследований и решается в каждом отдельном случае специалистом предметной области. Задача математических исследований состоит в том, чтобы предоставить предметному специалисту достаточно широкий набор средств для выделения необходимых информационных потоков.

В простейшем случае исходный сигнал отождествляется с функцией, которая задана на интервале (а, /3) вещественной оси; дальше эту функцию называем первоначальной. Для компьютерной обработки строится дискретный сигнал, представляющий собой сеточную функцию, определяемую как значения первоначальной функции (или результатов ее сглаживания) в узлах некоторой сетки (эту сеточную функцию и сетку назовем исходными). Использование исходной сеточной функции позволяет построить приближение к первоначальной функции с помощью того или иного аппарата аппроксимации или интерполяции. Линейное пространство таких приближений (будем называть его аналогично предыдущему — исходным пространством) затем представляют в виде прямой суммы пространств, одно из которых называют основным, а второе — вэйвлет-ным. Часто основное пространство связывают с сеткой, получающейся выбрасыванием узлов из исходной сетки, а подпространство вэйвлетов определяют операцией проектирования исходного пространства на основное. Таким образом, порождается разложение упомянутого приближения на основную и вэйвлетную составляющие. Центральными здесь оказываются два момента: вложенность основного пространства в исходное и задание операции проектирования исходного пространства на основное. Представления элементов этого разложения в базисах рассматриваемых пространств порождают соответствующие соотношения между коэффициентами этих представлений. Соотношения, позволяющие перейти от коэффициентов базиса исходного пространства к коэффициентам базисов основного и вэйвлетного пространств, называются формулами декомпозиции, а соотношения, дающие обратный переход — формулами реконструкции.

Каждое из упомянутых выше подпространств иногда также разлагают в прямую сумму некоторых подпространств и, возможно, продолжают этот процесс дальше; разложения подобного рода называются вэйвлет-пакетами.

Исследования в области обработки больших числовых массивов информации восходят к трем источникам, возникшим независимо друг от друга: к классической теории сплайнов, к методу конечных элементов и к теории вэйвлетов. В соответствии с этим можно выделить, по крайней мере, три направления развития теории обработки упомянутых массивов. Первое направление берет свое начало от работ Шонберга (Ы.ЗсЬоепЬе^, 1946); здесь исходным моментом является решение какой-либо задачи интерполяции (задачи Лагранжа, Эрмита или Эрмита-Биркгофа) в классе функций с «кусочными» свойствами и с определенной гладкостью в узлах рассматриваемой сетки. Заметим, что если исходный массив числовой информации задан как сеточная функция на мелкой сетке, то замена этой сеточной функции на результат решения интерполяционной задачи для крупной сетки (являющейся подмножеством мелкой сетки) может рассматриваться как сжатие исходного массива числовой информации.

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

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

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

Криптография (от греч. кди-ктоя — скрытый и 7дафш — пишу) — наука о математических методах обеспечения конфиденциальности и аутентичности информации.

Криптография — одна из старейших наук, ее история насчитывает несколько тысяч лет, первый пример передачи скрытого сообщения упоминал Геродот, это была татуировка, сделанная на обритой голове раба, скрытая под отросшими волосами. Развитие академических криптографических исследований началось относительно недавно, примерно с середины 1970х годов с открытой публикации спецификации стандарта шифрования DES от NBS, в статье Диффи - Хеллмана (см. [51]), и открытием алгоритма RSA. После этого, криптография начинает широко использоваться в коммуникациях, компьютерных сетях и для обеспечения компьютерной безопасности.

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

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

• симметричные DES, AES, ГОСТ 28147-89, Camellia, Twofish, Blowfïsh, IDEA, RC4 и др.

• ассиметричные RSA и Elgamal (Эль-Гамаль)

• хэш-функций MD4, MD5, SHA-1, ГОСТ Р 34.11-94

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

Асимметричное шифрование (криптографические системы с открытым ключом) — системы шифрования и электронной цифровой подписи, при которой открытый ключ передаётся по открытому (т.е. незащищённому, доступному для наблюдения) каналу, и используется для шифрования сообщения и проверки ЭЦП. Для генерации ЭЦП и для расшифрования сообщения используется секретный ключ. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах.

Во многих странах приняты национальные стандарты шифрования. В 2001 году в США принят стандарт симметричного шифрования AES па основе алгоритма Rijndael с длиной ключа 128, 192 и 256 бит. Алгоритм AES пришёл на смену прежнему алгоритму DES, который теперь рекомени довано использовать только в режиме Triple DES. В Российской Федерации действует стандарт ГОСТ 28147-89, описывающий алгоритм блочного шифрования с длиной ключа 256 бит, а также алгоритм цифровой подписи ГОСТ Р 34.10-2001.

Если сравнивать симметричные и ассиметричные алгоритмы можно выделить несколько критериев:

Достоинства симметричных шифров

• скорость (по данным Applied Cryptography - на 3 порядка выше, чем у ассиметричных),

• простота реализации (за счёт более простых операций),

• меньшая требуемая длина ключа для сопоставимой стойкости (например, для ассиметричного алгоритма RSA длина ключа в 512 бит уже не обеспечивает хорошей стойкости),

• изученность (за счёт бо'лынего возраста).

Недостатки симметричных шифров

• сложность управления ключами в большой сети; эта сложность заключается в том, что квадратично возрастает число пар ключей, которые надо генерировать, передавать, хранить и уничтожать в сети. Для сети в 10 абонентов требуется 45 ключей, для 100 уже 4950, для 1000 - 499500 и т. д., таким образом, резко возрастает сложность обмена ключами с увеличением числа абонентов;

• для применения симметричных шифров необходимо решить проблему надёжной передачи ключей каждому абоненту: нужен секретный канал для передачи каждого ключа обеим сторонам.

Важным свойством симметричных шифров является невозможность их использования для подтверждения авторства, так как ключ известен каждой стороне.

Современные симметричные шифры блочного шифрования работают с блоками 128, 192 и 256 бит, но в некоторых задачах может возникнуть потребность в блоках бо'льшей длины. Для криптографов актуальна разработка новых алгоритмов, которые используют новые идеи.

В данной работе реализована идея применения сплайн-вэйвлетных разложений для шифрования.

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

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

Актуальность темы. Началом современной криптографии можно считать работы Клода Шеннона опубликованные в 1948 году «А Mathematical Theory of Communication» в которой сформулированы основы теории информации, большую ценность представляет другая его работа — «Communication Theory of Secrecy Systems». В основу блочных шифров легли работы Хорста Фейстеля начатые им в 1971 году и опубликованные в журнале Scientific American в 1973. Было введено понятие «сеть Фейстеля», которое легло в основу большинства современных блочных шифров. Развитием криптографии, созданием и исследованием новых алгоритмов занимались многие ученые: У. Фридман, Д. Копперсмит, Й. Дамен и В. Раймен, Р. Ривестом, М. Робшау и Р. Сиднеем, Б. Шнайер, Э. Бихам и А. Шамир, Мацуи и многие другие.

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

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

Вэйвлеты широко применяются при составлении эффективных алгоритмов обработки больших потоков информации или цифровых сигналов. Роль теории вэйвлетов заключается в предоставлении предметному специалисту достаточно широкого набора средств, из которых он может выбрать именно то средство, которое ему подходит для обработки (для разложения на составляющие) интересующего его потока информации (цифрового сигнала). В теории вэйвлетов упомянутыми средствами являются наборы вложенных пространств функций и их представлений в виде пряJ мой (а иногда и ортогональной) суммы вэйвлетных пространств. Многие типы известных вэйвлетов обеспечивают быстрое, но весьма неточное сжатие. В данной работе используются сплайн-вэйвлетные системы с гарантированно высокой точностью приближения гладких цифровых потоков. Они приводят к эффективному сжатию и к достаточно точному результату. Стимулом к исследованиям в этом направлении стали работы С. Г. Михлина и Ю. К. Демьяновича.

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

Методы исследования.

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

Результаты, выносимые на защиту.

1. Построены новые сплайн-вэйвлетные разложения и изучены их свойства.

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

3. Проведен анализ устойчивости предложенных алгоритмов по отношению к криптоатакам.

4. Проведен анализ стойкости алгоритмов, установлены условия, в которых упомянутые алгоритмы являются абсолютно стойкими.

5. Теоретические результаты апробированы на модельных числовых примерах; разработан комплекс программ, основанный на предложенных алгоритмах.

Научная новизна. Все основные результаты диссертации являются новыми.

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

Апробация работы. Основные результаты были представлены на следующих конференциях и семинарах:

1. Процессы управления и устойчивость. XXXVII международная научная конференция аспирантов и студентов, С.-Петербург, Россия, 10-13 апреля 2006 г.

2. Процессы управления и устойчивость. XXXVIII международная научная конференция аспирантов и студентов, С.-Петербург, Россия, 9-12 апреля 2007 г.

3. Космос, астрономия и программирование (Лавровские чтения), С.Петербург, 20-22 мая 2008 г.

4. World Congress on Engineering 2008, London, U.K., 2-4 July, 2008.

5. International School on Mathematical Cryptology, Mathematical Foundations of Cryptology, Barcelona, Spain, 21-27 September 2008.

6. 3rd Information Security and Cryptology Conference, Ankara, Turkey, 2527 December.

7. Fast Software Encryption 2009, Leuven, Belgium, February 22-25, 2009.

8. Семинар кафедры параллельных алгоритмов математико-механического факультета Санкт-Петербургского государственного университета.

Публикации. Основные результаты опубликованы в 8 работах (см. раздел "Работы автора по теме диссертации11 в конце списка литературы.)

Структура и объем работы. Диссертация объемом 214 страниц состоит из введения, четырех глав, заключения, списка литературы и приложения. Приложение содержит описание комплекса программ, основанного на предложенных алгоритмах и предназначенного для выбора их параметров (ключа, входного потока), шифрования и дешифрования испытуемых потоков.

Заключение

В данной работе были построены сплайн-вэйвлетные разложений для сплайнов первого, второго и третьего порядка, выведены формулы реконструкции и декомпозиции. Установлены критерии для однозначного восстановления сетки по числовому потоку. Были получены новые криптоалгоритмы, основанные на вэйвлетных разложениях сплайнов первого, второго и третьего порядка в конечных полях. Предложенные алгоритмы удовлетворяют следующим критериям: 1) имеют размер блока до 1024 бит, что не предлагалась ранее в блочных алгоритмах, 2) имеют масштабируемые ключи, 3) используют простые операции, которые эффективны на микропроцессорах, 4) алгоритмы имеют простую для понимания разработку, что дает возможность для их анализа.

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

1. Аграновский A.B., Хади P.A. Практическая криптография: Алгоритмы и их программирование. // Москва "COJ1.H-P", 2002.

2. Алберг Дж., Нильсон Э., Уолш Дж. Теория сплайнов и ее приложения. М.: Мир, 1972. 316 с.

3. Астафьева Н. М. Вейвлет-анализ: основы теории и примеры применения // Успехи физических наук. 1998. Т. 166. № 11. С. 1145-1170.

4. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. // Издательство Мир, Москва 1979.

5. Блейхут. Быстрые алгоритмы цифровой обработки сигналов // М. Мир 1989, 448с.

6. Бурова И. Г\.т Демьянович Ю. К. Теория минимальных сплайнов. СПб.: Изд-во С.-Петерб. ун-та, 2000. 316 с.

7. Бурова И. Г., Демьянович Ю. К. О сплайнах максимальной гладкости // Вестн. С.~Петерб. ун-та. Сер. 1. 2005. Вып. 2. С. 5-9.

8. Бухбергер Б., Коллинз Дж., JIooc Р. Компьютерная алгебра символьные и алгебраические вычисления. // Москва, Мир 1986.

9. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. // М.: МЦНМО, 2003.-328 с.

10. Воробьев В. И., Грибунин В. Г. Теория и практика вейвлет-преобразования. СПб.: Изд-во ВУС, 1999. 208 с.

11. Де Бор К. Практическое руководство по сплайнам. М., 1984. 303 с.

12. Демьянович Ю. К. Локальная аппроксимация на многообразии и минимальные сплайны. СПб.: Изд-во С.-Петерб. ун-та, 1994. 356 с.

13. Демьянович Ю. К. О построении пространств локальных функций на неравномерной сетке // Зап. науч. сем. ЛОМИ АН СССР. 1983. Т. 124. С. 140-163.

14. Демьянович Ю. К. О вложенности пространств минимальных сплайнов// Ж. выч. мат. и мат. физ. 2000. Т. 40. № 7. С. 1012-1029.

15. Демьянович Ю. К. Всплесковые разложения в пространствах сплайнов на неравномерной сетке // Докл. РАН. 2002. Т. 382, № 3. С. 313-316.

16. Демьянович Ю. К. Всплески &; минимальные сплайны. СПб.: Изд-во С.-Петерб. ун-та, 2003. 200 с.

17. Демьянович Ю. К. Гладкость пространств сплайнов и всплесковые разложения // Докл. РАН. 2005. Т. 401, № 4. С. 1-4.

18. Демьянович Ю. К. Локальный базис всплесков на неравномерной сетке. // Зап. науч. семинаров ПОМИ. 2006. Т. 334. С. 84 110.

19. Демьянович Ю. К. Всплесковые разложения на неравномерной сетке. // Труды С.-Петерб. матем. о-ва, 2007. Т. 13. С. 27-51.

20. Демьянович Ю. К., Иванцова О. Н. Гладкость пространств сплайнов третьего порядка. // Сб. Математические модели. Теория и приложения. Вып. 7. СПб.: ВВМ, 2006. С. 58-64.

21. Демьянович Ю. К., Михлин С. Г. О сеточной аппроксимации функций соболевских пространств // Зап. науч. семинаров ЛОМИ АН СССР. 1973. Т. 35. С. 6-11.

22. Демьянович Ю. К., Ходаковский В. А. Введение в теорию вэй-влетов // Учебное пособие, Санкт-Петербург 2008. 50 с.

23. Добеши И. Десять лекций по вейвлетам: Пер. с англ. Е. В. Мищенко; под ред. А. П. Петухова. Москва-Ижевск: НИЦ "Регулярная и хаотическая динамика", 2004. 464 с.

24. Желудев В. А. О цифровой обработке сигналов при помощи сплайн-вейвлетов и вейвлет-пакетов // ДАН. 1997. Т. 355. № 5. С. 592-596.

25. Завьялов Ю. С., Квасов В. И., Мирошниченко В. К. Методы сплайн-функций. М. 1980. 352 с.

26. Кирушев В. А., Малоземов В. Н., Певный А. Б. Вейвлет-ное разложение пространства дискретных периодический сплайнов // Матем. заметки. 2000. Т. 67. Вып. 5. С. 712-720.

27. Коробейников А. Г. Математические основы криптографии. Учебное пособие. СПб: СПб ГИТМО (ТУ), 2002. 41 с.

28. Коробейников А. Г., Гатчин Ю. А. Математические основы криптологии. Учебное пособие. СПб: СПб ГУ ИТМО, 2004. 106 с.

29. Кравченко В. Ф., Рвачев В. А., Пустовойт В. И. Алгоритм построения "wavelet"-систем для обработки сигналов // ДАН. 1996. Т. 346. № 1. С. 31-32.

30. Малла С. Вэйвлеты в обработке сигналов: Пер. с англ. Я. М. Жи-лейкина. М.: Мир, 2005. 671 с.

31. Малоземов В. Ы., Машарский С. М. Сравнительное изучение двух вейвлетных базисов // Пробл. передачи инф. 2000. Т. 36. Вып. 2. С. 27-37.

32. Малоземов В. Н., Певный А. Б., Третьяков А. А. Быстрое вейвлетное преобразование дискретных периодических сигналов и изображений // Проблемы передачи инф. 1998. Т. 34. Вып. 2. С. 7785.

33. Малоземов В. Н., Певный А. Б. Полиномиальные сплайны. Л., 1986. 120 с.

34. Максименко И. Е., Скопина М. А. Многомерные периодические всплески // Алгебра и Анализ. 2003. Т. 15. № 2. С. 1-39.

35. Новиков И. Я., Стечкин С. Б. Основы теории всплесков // Успехи матем. наук. 1998. Т. 53, № 6. С. 53-128.

36. Поляков Р. В. Аппроксимационные сплайны и приближенное решение интегральных уравнений // Инстутут физики НАН Украины Украина.

37. Ромичев Дискретная математика и криптология // Москва: Диалог 2003.

38. Смарт Н. Криптография // Москва: ТЕХНОСФЕРА, 2005. 528с.

39. Спельников А.Б. Вычисление редукции по модулю простого числа в системах остаточных классов // Северо-Кавказский государственный технический университет, г.Ставрополь.

40. Стечкин С. Б., Субботин Ю. Н. Сплайны в вычислительной математике. М. 1976. 248 с.

41. Столниц Э., ДеРоуз Т., Салезин Д. Вейвлеты в компьютерной графике: Пер. с англ. Ижевск: НИЦ "Регулярная и хаотическая динамика", 2002. 272с.

42. Терехов А. А. Конспект лекций "Криптографическая защита информации"// Санкт-Петербург 1999.

43. Чуй Ч. К. Введение в вэйвлеты. Пер. с англ. Я. М. Жилейкина. М.: Мир, 2001. 412 с.

44. Щербаков А., Домашев А. Прикладная криптография использование и синтез криптографических интерфейсов // М. Издательско-торговый дом "Русская Редакция"2003, 416 с. D. Stinson. Cryptography Theory and Practice. CRC Press, 1995.

45. Aldroubi A., Sun Q., Tang W.-S. Non-uniform average sampling and reconstruction in multiply generated shift-invariant spaces// Constr. Approx., 20(2004), 173-189.

46. Biham E., Shamir A. Differential Cryptanalysis of DES-like cryptosystems // The Weizmann Institute of Science Department of Applied Mathematics July 19, 1990.

47. Chaum D., Evertse J. H. Cryptanalysis of DES with a reduced number of rounds Sequences of linear factors in block ciphers // Lecture Notes in Computer Science Advances in Cryptology proceedings of CRYPTO'85, pp. 192-211, 1985.

48. Churchhouse R. Codes and Ciphers. Julius Caesar, the Enigma and the Internet // Cambridge University Press, 2001.

49. Daemen J., Rijmen. V. The Design of Rijndael: AES The Advanced Encryption Standard. Springer-Verlag, 2002.

50. Daubechies I., Guskov I., Schroder P., and Sweldens W.

51. Wavelets on irregular point sets, Phil. Trans. Math., Physical, Engng. Sci. 357 (1999), 2397 2413.

52. Daubechies I., Guskov I., and Sweldens W. Commutation for irregular subdivision, Const. Approx. 17 (2001), no. 4, 479 514.

53. Diffie W., Hellman M. New Directions in Cryptography// IEEE Transactions on Information Theory, vol. IT-22, Nov. 1976, pp: 644—654.

54. Goel J. J. Construction of basis functions for numerical utilization of Ritz's method // Numer. Math. 1968. Vol. 12. P. 435-447.

55. Goldwasser S., Bellare M. Lecture Notes on Cryptography // MIT Laboratory of Computer Science, Cambridge.

56. J.C.A. van der Lubbe. Information Theory // Cambridge University Press, 1997.

57. Kahn D. The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet // Scribner, 1996.

58. Lidl R., Neiderreiter H. Introduction to finite field and their applications // Cambridge University Press, 1986.

59. Mantin I. Analysis of the Stream Cipher RC4. MSc. Thesis, Weizmann Institute of Science, 2001.

60. Miihibach G. ECT-B-splines defined by generalized divided differences// Journal of Computational and Applied Mathematics 187 (2006), 96-122.

61. Protasov V. Fractal curves and their applications to wavelets // Proc. of the Int. Workshop on self-similar systems, July 30 August 7, 1998. - Dubna, Russia, 1999. - P. 120-125.

62. Schoenberg I. J. Contributions to the problem of approximation of equidistant date by analytic function // Qaurt. Appl. Math. 1946. Vol. 4. Pt A. P. 45-99; Pt B. P. 112-141.

63. Schaumuller-Bichl I. On the Design and Analysis of New Cipher Systems Related to the DES technical report Linz university

64. Schumacker L. L. Spline Functions. Basic Theory. Waley Interscience. New York. 1981. 548 p.

65. Singh S. The Codebook: The Evolution of Secrecy from Mary, Queen of Scots to Quantum Cryptography. Doubleday, 2000.

66. Skopina M. Multiresolution analysis of periodic functions// East J. Approx. 1997. V. 3, №. P. 203-224.

67. Stinson D. Cryptography: Theory and Practice. CRC Press, 1995.

68. Strang G., Fix G. Fourier analysis of the finite element method in Ritz-Galerkin theory // Stud. Appl. Math. 1969. Vol. 48, №3. P. 265273.

69. Strang G., Strela V. Short wavelets and matrix dilation equations // IEEE Trans. Signal Proc., 1995, v. 3. P. 108-115.

70. Sweldens W. Wavelets and the lifting scheme

71. Welsh D. Codes and Cryptography. Oxford University Press, 1988. Работы автора по теме диссертации:

72. Демьянович Ю. К., Левина А. Б. О вэйвлетных разложениях линейных пространств над произвольным полем и о некоторых приложениях// Журнал Математическое моделирование- 2008: Том 20, номер 11, стр. 104-108.

73. Демьянович Ю. К., Левина А. Б. Вэйвлетное разложение и шифрование // Методы Вычислений выпуск 22, 2008. стр. 41-63.

74. Левина А. Б. Работа криптосистемы, основанной на формулах реконструкции и декомпозиции на неравномерной сетке // Математические модели теория и приложения, сборник научных статей, 2008 г., выпуск 9, стр. 3-29.

75. Levina А. В. Cryptoalgorithm Based on Formulas of Reconstruction and Decomposition on the Non-uniform Grid // Lecture Notes in Engineering and Computer Science, Volume III 2008, pp. 1724- 1727.

76. Demjanovich Yu. K., Levina A. B. Encryption with first order splines // ISCTurkey 2008, pp. 25-27.

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