Автор: Пользователь скрыл имя, 17 Декабря 2012 в 22:36, курсовая работа
Предметом работы являются методы и алгоритмы выполнения арифметических операций которые являются основой различных криптосистем.
Целью работы является повышение качества работы криптосистем путем создания нового алгоритма.
ВВЕДЕНИЕ 4
1 АНАЛИЗ ЗАДАЧ ДЕЛЕНИЯ ЧИСЕЛ В КРИПТОГРАФИЧЕСКИХ ПРИЛОЖЕНИЯХ 6
1.1 Цели поддержки безопасности 6
1.2 Типы атак угрожающих конфиденциальности информации 7
1.3 Механизмы обеспечения информационной безопасности 11
1.4 Методы реализации информационной безопасности 12
1.5 Выводы по главе 14
2 АНАЛИЗ СУЩЕСТВУЮЩИХ АЛГОРИТМОВ ДЕЛЕНИЯ ЧИСЕЛ 16
2.1 Арифметика целых чисел 16
2.2 Бинарные операции 16
2.3 Деление целых чисел 18
2.4 Теория делимости 20
2.4.2 Все делители 21
2.4.3 Наибольший общий делитель 21
2.5 Алгоритм Евклида 22
2.6 Расширенный алгоритм Евклида 23
2.7 Линейные диофантовы уравнения 25
2.8 Модульная арифметика 26
2.9 Бинарные операции в Zn 27
2.10 Виды Инверсий 28
2.10.1 Аддитивная инверсия 28
2.10.2 Мультипликативная инверсия 28
2.11 Вывод по главе 29
3 РАЗРАБОТКА АЛГОРИТМА ДЕЛЕНИЯ ЧИСЕЛ 30
3.1 Алгоритм матричного деления полиномов 30
3.2 Выводы по главе 3 32
ЗАКЛЮЧЕНИЕ 34
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 35
- Частное решение: X0 = (c/d)s и y0 = (c/d)t
- Общие решения: x = x0 + k(b/d) и y = y0 – k(a/d), где k — целое число.
2.8 Модульная арифметика
Уравнение деления ( ), рассмотренное в предыдущей секции, имеет два входа ( a и n ) и два выхода ( q и r ). В модульной арифметике мы интересуемся только одним из выходов — остатком r. Мы не заботимся о частном q. Другими словами, когда мы делим a на n, мы интересуемся только тем, что значение остатка равно r. Это подразумевает, что мы можем представить изображение вышеупомянутого уравнения как бинарный оператор с двумя входами a и n и одним выходом r.
Операции по модулю
Вышеупомянутый бинарный оператор назван оператором по модулю и обозначается как mod. Второй вход ( n ) назван модулем. Вывод r назван вычетом. Рисунок 9 показывает отношение деления по сравнению с оператором по модулю.
Рисунок 9 - Соотношение уравнения деления и оператора по модулю
Как показано на рис. 2.9, оператор по модулю ( mod ) выбирает целое число ( a ) из множества Z и положительный модуль ( n ). Оператор определяет неотрицательный остаток ( r ).
Можно сказать, что a mod n = r
2.9 Бинарные операции в Zn
Три бинарных операции ( сложение, вычитание и умножение ), которые мы обсуждали для Z, могут также быть определены для набора Zn. Результат, возможно, должен быть отображен в Zn с использованием операции по модулю, как это показано на рисунке 10.
Рисунок 10 - Бинарные операции в Zn
Фактически применяются два набора операторов: первый набор — один из бинарных операторов ; второй — операторы по модулю. Мы должны использовать круглые скобки, чтобы подчеркнуть порядок работ. Как показано на рис. 2.13, входы ( a и b ) могут быть членами Z или Zn.
2.10 Виды Инверсий
Когда мы работаем в модульной арифметике, нам часто нужно найти операцию, которая позволяет вычислить величину, обратную заданному числу. Мы обычно ищем аддитивную инверсию (оператор, обратный сложению) или мультипликативную инверсию (оператор, обратный умножению).
2.10.1 Аддитивная инверсия
В Z2 два числа a и b аддитивно инверсны друг другу, если b = n – a. Например, в Zn аддитивная инверсия числу a может быть вычислена как b = n – a. Например, аддитивная инверсия 4 в Z10 равна 10 – 4 = 6.
В модульной арифметике каждое целое число имеет аддитивную инверсию. Сумма целого числа и его аддитивной инверсии сравнима с 0 по модулю n .
Обратите внимание, что в модульной арифметике каждое число имеет аддитивную инверсию, и эта инверсия уникальна; каждое число имеет одну и только одну аддитивную инверсию. Однако инверсия числа может быть непосредственно тем же самым числом
2.10.2 Мультипликативная инверсия
В модульной арифметике
целое число может или не может
иметь мультипликативную
2.11 Вывод по главе
Были рассмотрены и проанализированы существующие алгоритмы деления, теория делимости и инверсии, рассмотрены свойства теории делимости и виды инверсий. Все рассмотренное в этой главе активно используется и применяется при создании и эксплуатации криптографических систем. Для более углубленного исследования главы, были показаны примеры решения элементарных задач.
3 РАЗРАБОТКА АЛГОРИТМА ДЕЛЕНИЯ ЧИСЕЛ
3.1 Алгоритм матричного деления полиномов
Необходимы две матрицы Z и Y. Матрица Z определяется рисунком 1.
Рисунок 1 – Матрица Z
А матрица Y – рисунком 2.
Рисунок 2 – Матрица Y
Воспользуемся алгоритмом представленным на рисунке 3.
Для математического обоснования матричного алгоритма сформулирована
и доказана теорема - Если Z – специальным образом сформированная матрица от B(x), то остаток от деления A(x) на B(x) будет равен результату, показанному на рисунке 4.
Рисунок 4 – Результат остатка от деления A(x) на B(x)
Для быстрого формирования матриц Z и Y , получены и доказаны
методом математической индукции рекуррентные формулы представленные на рисунке 5.
Рисунок 5 – Рекуррентные формулы
Результаты исследования эффективности алгоритмов деления полиномов показали большее быстродействие оригинального матричного алгоритма деления полиномов по сравнению с остальными алгоритмами. На рис. 3 в виде гистограмм приведена в качестве примера часть результатов исследования эффективности алгоритмов деления полиномов для соотношений разрядностей делимого к делителю, равных 30/5, 30/15 и 30/25. Показано во сколько раз по быстродействию матричный и двусторонний алгоритмы деления полиномов превосходят классический алгоритм. Эти результаты получены с относительной ошибкой в пределах 3-4% при доверительной вероятности 95%. С целью выбора алгоритма функционирования кодека, проведены исследования позволившие разработать алгоритмы функционирования кодера и декодера. Эти алгоритмы положены в основу шаблона проектируемого кодека, созданного на языке описания аппаратуры Verilog. Предложены методы уменьшения требуемого объѐма энергонезависимой памяти при аппаратной реализации кодеков помехоустойчивых полиномиальных кодов с синдромным декодированием. При этом предложены метод составления словаря и метод выборки исправляющей комбинации по принципу организации частично-ассоциативной кэш-памяти. Показано, что использование метода составления словаря более предпочтительно из-за его простоты реализации, в отличие от метода выборки исправляющей комбинации по принципу организации частично-ассоциативной кэш-памяти.
3.2 Выводы по главе
Разработан быстродействующий алгоритм матричного деления полиномов в арифметике по модулю два. Результаты компьютерного эксперимента подтвердили теоретические предположения о егоэффективности по быстродействию. Матричный алгоритм позволяет создаватьбыстродействующие кодеки помехоустойчивых полиномиальных кодов. Предложены методы уменьшения требуемого объѐма энергонезависимой памяти при аппаратной реализации кодека с синдромным декодированием, которые позволяют создавать кодеки в условиях нехватки объѐма такой памяти.
ЗАКЛЮЧЕНИЕ
В ходе работы были рассмотрены главные цели информационной безопасности, виды атак угрожающих информации, методы защиты информации – такие как криптография и стеганография.
Были рассмотрены и проанализированы существующие алгоритмы деления, теория делимости и инверсии, рассмотрены свойства теории делимости и виды инверсий. Все рассмотренное в этой главе активно используется и применяется при создании и эксплуатации криптографических систем. Для более углубленного исследования главы, были показаны примеры решения элементарных задач. И представлен алгоритм матричного деления полиномов.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
Абзац Отступ слева – 0, справа -0, первая строка – 1,3 (и для всех абзацев так сделай, кроме подписей рисунков)
Информация о работе Разработка алгоритмов деления для криптосистем