Разработка алгоритмов деления для криптосистем

1.4 Методы реализации информационной безопасности

Теперь, следует рассмотреть  методы реализации информационной безопасности. Их два:

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

1. Шифрование симметричными ключами иногда называют шифрованием c секретным ключом или криптографией с секретным ключом. Например, объект, назовем его Алиса, может передать сообщение другому объекту, который называется Боб, по опасному каналу, для того, чтобы ее противник, который называется Ева, не смог понять содержание сообщения, просто подслушав его по каналу. Алиса зашифровала сообщение, используя алгоритм шифрования; Боб расшифровывает сообщение, используя алгоритм расшифровки. В шифровании симметричными ключами применяется единственный ключ засекречивания и для шифрования, и для расшифровки. Шифрование/дешифрование можно представить как электронный замок. При шифровании симметричным ключом Алиса помещает сообщение в блок и закрывает блок, используя совместный ключ засекречивания; Боб отпирает замок другим экземпляром того же ключа и извлекает сообщение.
2. Шифрование асимметричными ключами. При шифровании асимметричными ключами (иногда называемом шифрованием с открытыми ключами или криптографией с открытыми ключами) мы имеем ту же самую ситуацию, что и при шифровании симметричными ключами, но с небольшой разницей. Во-первых, мы имеем два ключа вместо одного: из них один открытый ключ (public key), другой — индивидуальный или секретный (private key). Для того чтобы передать защищенное сообщение Бобу, Алиса сначала зашифровала сообщение, используя открытый ключ Боба. Чтобы расшифровывать сообщение, Боб использует свой собственный секретный ключ.
3. Хэширование. При хэшировании из сообщения переменной длины может быть создан дайджест фиксированной длины, обычно намного меньшего размера, чем исходное сообщение. Сообщение и дайджест нужно передать Бобу. Дайджест используется, чтобы обеспечить проверку целостности данных, которая обсуждалась раньше.

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

1.5 Выводы по главе

Для информационной безопасности было определено три главные цели: конфиденциальность, целостность и готовность. Также, было отмечено , что конфиденциальности информации угрожают два типа атак: вмешательство — и наблюдение за трафиком и его анализ. Четыре типа атак могут угрожать целостности информации: модификация, имитация источника, повторная передача информации и отказ от сообщения. Атака "прекращение обслуживания запроса" угрожает готовности информации.

Есть два метода —  криптография и стеганография, которые  могут реализовать некоторые  или все механизмы. Криптография или "тайное письмо" включает скремблирование  сообщения или создание дайджеста сообщения. Стеганография, или "закрытая запись", означает, что сообщение скрывается и закрывается другой информацией.

2 анализ существующих алгоритмов деления чисел

2.1 Арифметика целых чисел

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

Множество целых чисел

Множество целых чисел, обозначенных Z, содержит все числа (без дробей) от минус бесконечности до плюс бесконечности в соответствии с рисунком 1.

 

Рисунок 1 – Множество  чисел Z

 

2.2 Бинарные операции

В криптографии необходимо рассмотреть три бинарных операции в приложении к множеству целых чисел. Бинарные операции имеют два входа и один выход. Для целых чисел определены три общих бинарных операции — сложение, вычитание и умножение. Каждая из этих операций имеет два входа ( a и b ) и выход ( c ), как это показано на рисунке 2. Два входа принимают числа из множества целых чисел; выход выводит результат операции — число из множества целых чисел.

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

Рисунок 2 - Три бинарных операции для множества целых чисел

 

Пример 1.

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

 

Рисунок 3 – Бинарные операции на множестве двух целых чисел

 

2.3 Деление целых чисел

В арифметике целых чисел, если мы a делим на n, мы можем получить q и r. Отношения между этими четырьмя целыми числами можно показать как 

 

a=q*x+r (1)

 

В равенстве (1) a это делимое ; q это частное ; n это делитель и r это остаток. Необходимо отметить, что это не операция, поскольку результат деления a на n — это два целых числа, q и r. Следует называть это уравнением деления.

Пример 2.

Предположим, что a = 255, а n = 23. Можно найти q = 11 и r = 2, используя алгоритм деления, из элементарной арифметики известно, что оно определяется, как показано на рисунке 3.

 

Рисунок 3 – Нахождение частного и остатка

 

Большинство компьютерных языков может найти частное и  остаток, используя заданные языком операторы. Например, на языке C оператор "/" может найти частное, а оператор "%" — остаток.

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

1) Первое требование: чтобы делитель был положительным целым числом ( n > 0 ).

2) Второе требование: чтобы остаток был неотрицательным целым числом ( r > 0 ). Рисунок 4 показывает эти требования с двумя указанными ограничениями.

 

Рисунок 4 - Алгоритм деления целых чисел

 

Пример 3

Используется калькулятор, а r и q отрицательны, при отрицательном a. Как можно сделать, чтобы выполнялось ограничение, что число r должно быть положительным? Решение простое: мы уменьшаем значение q на 1 и добавляем значение n к r, чтобы r стало положительным.

 

 (2)

 

Уменьшая ( –23 ), получим ( –24 ) и добавим 11 к ( –2 ), чтобы получить + 9. Полученное равенство эквивалентно исходному.

Граф уравнения деления

 

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

Рисунок 5 - Граф алгоритма деления

 

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

2.4 Теория делимости

Теперь, необходимо рассмотреть теорию делимости. Если a не равно нулю, а r = 0, в равенстве деления мы имеем  a = q x n

Тогда известно, что a делится на n (или n — делитель a ). Можно также сказать, что a делится без остатка на n. Когда мы не интересуемся значением q, мы можем записать вышеупомянутые отношения как n|a. Если остаток не является нулевым, то n не делится, и мы можем записать отношения как n†a.

2.4.1 Свойства теории делимости

Следующие несколько свойств теории делимости которые необходимо рассмотреть:

1) Свойство 1: если a|1, то a=±1.

2) Свойство 2: если a|b и b|a, то a=±b

3) Свойство 3: если a|b и b|c, то a|c

4) Свойство 4: если a|b и a|c, то a|(m x b + n x c), где m и n — произвольные целые числа.

2.4.2 Все делители

Положительное целое  число может иметь больше чем  один делитель. Например, целое число 32 имеет шесть делителей: 1, 2, 4, 8, 16 и 32. Необходимо упомянуть два свойства делителей положительных целых чисел:

1) Свойство 1: целое число 1 имеет только один делитель — само себя.

2) Свойство 2: любое положительное целое число имеет по крайней мере два делителя — 1 и само себя (но может иметь больше).

2.4.3 Наибольший общий делитель

Одно целое число, часто необходимое в криптографии, — наибольший общий делитель двух положительных целых чисел. Например, общие делители чисел 12 и 140 есть 1, 2 и 4. Однако наибольший общий делитель — 4 это показано на рисунке 6.

 

Рисунок 6 - Общие делители двух целых чисел

 

Наибольший общий делитель двух положительных целых чисел  — наибольшее целое число, которое  делит оба целых числа.

2.5 Алгоритм Евклида

Нахождение наибольшего  общего делителя (НОД) двух положительных  целых чисел путем составления  списка всех общих делителей непригодно для достаточно больших чисел.

Алгоритм Евклида основан  на следующих двух фактах:

1) Факт 1: НОД (a, 0) = a

2) Факт 2: НОД (a, b) = НОД (b, r), где r — остаток от деления a на b

Первый факт говорит, что если второе целое число — 0, наибольший общий делитель равен первому числу. Второй факт позволяет нам изменять значение a на b, пока b не станет 0. Например, вычисляя НОД (36, 10), мы можем использовать второй факт несколько раз и один раз первый факт, как показано ниже. НОД(36,10) = НОД(10,6) = НОД(6,4) = НОД(4,2) = НОД(2,0)

Другими словами, НОД (36, 10) = 2, НОД (10, 6) = 2, и так далее. Это  означает, что вместо вычисления НОД (36, 10) мы можем найти НОД (2, 0). Рисунок 7 показывает, как мы используем вышеупомянутые два факта, чтобы вычислить НОД (a, b).

 

Рисунок 7 - Алгоритм Евклида

 

Для определения НОД  мы используем две переменные, r1 и r2, чтобы запоминать изменяющиеся значения в течение всего процесса. Они  имеют начальное значение a и b. На каждом шаге мы вычисляем остаток от деления r1 на r2 и храним результат в виде переменной r. Потом заменяем r1, на r2 и r2 на r и продолжаем шаги, пока r не станет равным 0. В этот момент процесс останавливается и НОД (a, b) равен r1.

2.6 Расширенный алгоритм Евклида

Даны два целых числа a и b. Нам зачастую надо найти другие два целых числа, s и t, такие, которые s x a + t x b = НОД(a,b). Расширенный алгоритм Евклида может вычислить НОД (a, b) и в то же самое время вычислить значения s и t. Алгоритм и процесс такого вычисления показан на рисунке 8.

Здесь расширенный алгоритм Евклида использует те же самые шаги, что и простой алгоритм Евклида. Однако в каждом шаге мы применяем  три группы вычислений вместо одной. Алгоритм использует три набора переменных: r,s и t.

 

Рисунок 8 - Расширенный алгоритм Евклида

 

На каждом шаге переменные r1, r2 и r используются так же, как в  алгоритме Евклида. Переменным r1 и r2 присваиваются начальные значения a и b соответственно. Переменным s1 и s2 присваиваются  начальные значения 1 и 0 соответственно. Переменным t1 и t2 присваиваются начальные значения 0 и 1, соответственно. Вычисления r, s и t одинаковы, но с одним отличием. Хотя r — остаток от деления r1 на r2, такого соответствия в других двух группах вычислений нет. Есть только одно частное, q, которое вычисляется как r1/r2 и используется для других двух вычислений.

2.7 Линейные диофантовы уравнения

Хотя очень важное приложение расширенного алгоритма  Евклида будет рассмотрено далее, здесь необходимо рассмотреть "нахождение решения линейных диофантовых уравнений двух переменных", а именно, уравнения ax + by = c. Необходимо найти значения целых чисел для x и y, которые удовлетворяют этому уравнению. Этот тип уравнения либо не имеет решений, либо имеет бесконечное число решений. Пусть d = НОД (a, b). Если d†c, то уравнение не имеет решения. Если d|c, то мы имеем бесконечное число решений. Одно из них называется частным, остальные — общими.

Линейное диофантово уравнение — это уравнение двух переменных

ax + by =c .

Если d|c, то можно найти  частное решение вышеупомянутого уравнения, используя следующие шаги. Преобразуем уравнение к a1x + b1y = c1, разделив обе части уравнения на d. Это возможно, потому, что d делит a, b, и c в соответствии с предположением. Найти s и t в равенстве a1s + b1t = 1, используя расширенный алгоритм Евклида. Получим: