WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

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

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

Левина Алла Борисовна СПЛАЙН-ВЭЙВЛЕТЫ И ИХ НЕКОТОРЫЕ ПРИМЕНЕНИЯ 05.13.18 математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание уч степени еной кандидата физико-математических наук

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

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

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

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

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

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

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

Автореферат разослан " " 2009 г.

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

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Одной из областей математического моделирования традиционно является криптография. Началом современной криптографии можно считать работы Клода Шеннона опубликованные в 1948 году "A Mathematical Theory of Communication"в которой сформулированы основы теории информации, большую ценность представляет другая его работа - "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. 3rd Information Security and Cryptology Conference, Ankara, Turkey, 25-December.

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

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

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

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

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

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

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

Приведена Теорема Шеннона о стойкости криптоалгоритмов.

Далее излагаются наиболее известные симметричные алгоритмы блочного шифрования, шифр Фейстеля, DES и алгоритм Rijndael, который является стандартом шифрования США с 2002 года. Во второй главе рассматриваются сплайн-вэйвлетные разложения. Для координатных сплайнов строятся системы функционалов {g(i)}iZ биортогональные системам координатных сплайнов {j}jZ.

Пусть X :... < x-1 < x0 < x1 <... сетка, = lim xj, = lim xj, j- j+ положим здесь и могут быть конечными или бесконечными.

Для фиксированного k Z положим def def def xj xj при j k - 1, и xj xj+1 при j k, xk, = = = и рассмотрим новую сетку X :... < x-1 < x0 < x1 <.... Таким образом сетка Xполучается из сетки X выбрасыванием узла.

Для сетки X, полученной из сетки X удалением одного узла, строятся сплайны j, устанавливаются калибровочные соотношения, выражающие сплайны j в виде линейной комбинации сплайнов j: i = di,jj, j Теорема 1. Для сплайнов первого порядка коэффициенты di,j, i, j Z отыскиваются по формулам:

di,j = i,j при i k - 3, j Z, dk-2,k-2 = 1, dk-2,k-1 = (xk+1 - xk)(xk+1 - xk-1)-1, dk-2,j = 0 при j {k - 2, k - 1}, dk-1,j = 0 при j {k - 1, k}, / / dk-1,k-1 = (xk - xk-1)(xk+1 - xk-1)-1, dk-1,k = 1, di,j = i,j-1 при i k, j Z.

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

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

Теорема 2. Справедливы соотношения i = di,jj, j где для i, j Z числа di,j отыскиваются по формулам:

di,j = i,j при i k - 4, dk-3,k-3 = 1, dk-3,k-2 = (xk - )(xk - xk-2)-1, dk-3,j = 0 при j {k - 3, k - 2}, / dk-2,k-2 = ( - xk-2)(xk - xk-2)-1, dk-2,k-1 = (xk+1 - )(xk+1 - xk-1)-1, dk-2,j = 0 при j {k - 2, k - 1}, / dk-1,k-1 = ( - xk-1)(xk+1 - xk-1)-1, dk-1,k = 1, dk-1,j = 0 при j {k - 1, k}, / di,j = i+1,j при i k.

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

(X) пространство, являющееся линейной оболочкой функций j, def def (X) { u | u cjj cj R1 };

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

В соответствии с этим определением (X) является пространством сплайнов на сетке X, def (X) = { u | u ajj aj R1 }.

= j Согласно теореме 1 справедливо включение (X) (X).

Рассматривается оператор P проектирования пространства (X) на подпространство (X), задаваемый формулой def P u g(j), u j u (X).

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

(X) = (X)+Wk, (1) где Wk пространство вэйвлетов.

Пусть u (X); используя соотношение (1), получаем два представления элемента u u = cjj, j u = aii + bjj.

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

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

ai = ci при i k - 2, ai = ci+1 при i k - 1, bj = 0 при j = k - bk-1 = ck-1 - (xk+1 - xk)(xk+1 - xk-1)-1ck-2-(xk - xk-1)(xk+1 - xk-1)-1ck.

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

cj = aj при j k - 2, cj = aj-1 при j k, ck-1 = (xk+1 - xk)(xk+1 - xk-1)-1ak-2 + (xk - xk-1)(xk+1 - xk-1)-1ak-1 + bk-1.

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

Теорема 5. Для рассматриваемого сплайн-вэйвлетного разложения (1) пространства (X) сплайнов второго порядка формулы реконструкции имеют вид cj = aj + bj при j k - 3, ck-2 = ak-3(xk - )(xk - xk-2)-1 + ak-2( - xk-2)(xk - xk-2)-1 + bk-2, ck-1 = ak-2(xk+1 - )(xk+1 - xk-1)-1 + ak-1( - xk-1)(xk+1 - xk-1)-1 + bk-1, cj = aj-1 + bj при j k.

Теорема 6. Для сплайн-вэйвлетного разложения (1) пространства (X) сплайнов второго порядка формулы декомпозиции имеют вид ai = ci при i k - 3, ak-2 = -(xk - )( - xk-2)-1ck-3 + (xk - xk-2)( - xk-2)-1ck-2, ai = ci+1 при i k - 1, bj = 0 при j = k - 1, bk-1 = (xk+1-)(xk-)ck-3-(xk+1-)(xk-xk-2)ck-2+(xk+1-xk-1)(-xk-2)ck-1 -( - xk-1)( - xk-2)ck (xk+1 - xk-1)-1( - xk-2)-1, Для полиномиальных сплайнов первого порядка рассматривается вопрос о восстановление сетки по исходному потоку и по вэйвлетной составляющей и о построение сетки по поступающему потоку. Эти результаты сформулированы в следующих теоремах:

Теорема 7. Если ck-2 = ck, то узел определяется однозначно по формуле = xk-1 + qk(xk+1 - xk-1), где ck-1 - ck-2 - bk-qk =.

ck - ck-Если же ck-2 = ck, то в качестве можно взять любую точку интервала (xk-1, xk+1).

Теорема 5. В условиях теоремы 4 при ck-2 = ck, вэйвлетная составляю щая bk-1 равна нулю тогда и только тогда, когда выполнено соотношение ck - ck-1 hk =, ck-1 - ck-2 hk-def где hk xk+1 - xk.

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

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

Ключ K имеет две составляющие: сетку X и порядок выбрасывания узлов : K = (X, ); здесь X = {xj}j=0,...L-1, где L количество узлов в сетке, xj (различные) узлы сетки. = {n}n=1,...K, K число раундов шифрования, n номер выбрасываемого узла. Сетку X можно считать периодической (имея ввиду, например, сетку на окружности): xj+L = xj для j Z, L натуральное число L 5.

Открытым текстом является последовательность C = {ci}iJ, J Z. Открытый текст разбивается на l блоков |Ci| одинаковой длины, |Ci| = M, |Ci| число элементов в блоке, i = 1, 2,...l. На k-м раунде число элементов пре-k образованного блока Ci равно M - k; при необходимости последовательность -k Ci = {c-k}i=1,...,M-k продлевается периодически с периодом M - k.

Pages:     |
|



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.