Научные проблемы Интернета

Научные проблемы Интернета группируются вокруг следующих задач:
· Защита информации
· Сжатие информации
· Поиск информации
· Распознавание информационных объектов (текста и образов)
· Прогнозирование временных рядов
· Классификация документов
· Выбор и оценка многокритериальных альтернатив
· Принятие решений и логический вывод и др.
Рассмотрение всех этих задач выходит за рамки настоящего труда. Рассмотрим только некоторые задачи.
1 Защита информации
Современные способы защиты информации используют в первую очередь различные методы шифрования. Мы рассмотрим здесь два криптографических метода: RSA и DES. Основные принципы криптографии можно сформулировать следующим образом.
1. В шифровании основную роль играет не алгоритм, а ключ.
2. Алгоритм шифрования должен быть таким, чтобы шифрование выполнялось легко и эффективно с вычислительной точки зрения; наоборот, дешифрование должно представлять собой сложнейшую математическую задачу (например, переборного типа).
Алгоритм RSA. Пусть необходимо передать по линии связи числа x (рассмотрим здесь только целые положительные числа). Вместо числа x передают число y , вычисляемое по формуле
, (1.1)
где e и m являются открытыми числами (известны всем абонентам сети).
Требуем, чтобы e и m были взаимно простыми числами (т.е. не числами общих делителей, кроме 1, причем ).
Оказывается, что зная y , e и m , найти x – сложнейшая математическая задача. Пока же продемонстрируем, как найти y по x , e , m .
Операция
(1.2)
находит целочисленный остаток a от деления b на m . Например,
2 = 17 mod 5
или
1 = 41 mod 8.
Но пусть требуется найти
630 mod 18 = ?
Это сделать посложнее. Мно записать
630 = 2*315 = 2*5*63 = 2*5*7*9 = 63*10.
Теперь можно использовать правило разложения на множители
.
В самом деле, пусть
,
,
.
Тогда
.
Последняя сумма дает остаток от деления на m , равный . Но , . Поэтому
.
Теперь нетрудно это правило применить, скажем, к
713 mod 8 = ?
Запишем
.
Имеем . Поэтому .
Обратимся теперь к формуле (6.16).
Пусть , , .
Найдем
.
Итак, . Это значение и будет передано по сети вместо x .
Теперь рассмотрим, как восстановить x по y , m , e . Для этой цели нужно найти число d , удовлетворяющее условию
, (1.3)
где – значение функции Эйлера от числа m . Функция Эйлера вычисляется сравнительно просто. Так,
. (1.4)
Если p простое число и r – целое, то
. (1.5)
Формул (1.4) и (1.5) достаточно для того, чтобы найти функцию Эйлера для любого целого положительного числа. В нашем случае получаем:
.
Для любознательных читателей отметим, что значение равно числу целых чисел на отрезке 1..m , взаимно простых с m . Отыскание значения функции Эйлера для больших целых чисел является вычислительной задачей очень большой сложности.
Пример . . Все четыре числа: 1, 2, 3, 4 взаимно просты с m .
Теперь обратимся к уравнению (3.3). В этом уравнении d играет роль секретного ключа. Решить уравнение (3.3) путем перебора значений d можно, но если в числе m , например, 100 цифр, то на вычисление d уйдет достаточно много времени. Для небольших значений, таких как в нашем примере, можно воспользоваться алгоритмом решения уравнений в целых числах, который мы и приведем.
Итак, в нашем примере уравнение такое:
. (1.6)
Уравнение (1.6) можно переписать следующим известным образом:
. (1.7)
В (1.7) r и d неизвестные целые числа. Представим (1.7) в виде системы двух линейных неравенств.
,
,
или, что эквивалентно:
,
.
(1.8)
В неравенстве с положительной правой частью выделим член с минимальным по модулю коэффициентом и разрешим неравенство относительно этого члена:
, .
Отсюда легко получить отсекающее неравенство:
(a) ,
(b) ,
(c) .
(1.9)
Здесь z – новая целочисленная переменная. Заметим, что переход от (a) к (b) в (1.9) правомерен, так как r , d , z – целочисленны.
Выполним подстановку (3.9) в систему (1.8). Получим новую систему:
,
.
(1.10)
Обратим внимание на следующее принципиальное обстоятельство. В сравнении с (1.8) значение минимального коэффициента понизилось. Этот факт можно строго обосновать. Следовательно, весь процесс должен закончиться рано или поздно одним из двух результатов:
1) минимальный коэффициент по модулю станет равным 1 (как в (1.10)); будет получена система вида
,
,
где a и b – взаимно просты (в этом случае нет решения в целых числах).
В первом случае процесс решения завершен. Получаем из (1.10) подстановку для d :
. (1.11)
Тогда из (1.9) найдем:
. (1.12)
Итак, формулы (1.11) и (1.12) и дают нам итоговые подстановки для d и r из (1.7). Например, пусть . Тогда , . Возьмем именно это значение для минимального d .
Итак, мы подошли к решающему моменту: наш секретный ключ . Получили число , , .Восстанавливаем x по формуле:
. (1.13)
Итак, .
Все сошлось. Возьмем, например, . Тогда , :
(ответ тот же).
Таким образом, не имеет значения, какое z брать для получения d .
Метод RSA мы завершим следующим замечанием.
Метод RSA вообще говоря требует, чтобы m было большим простым числом. Для установления факта, что m – простое, можно использовать малую теорему Ферма:
. (1.14)
В (1.14) a и p должны быть взаимно просты, а p – простое число.
Пример .
, :
.
,:.
К сожалению, формула (1.14) справедлива также для некоторых составных чисел. Поэтому чтобы применить ее на практике, нудно выполнить проверку для некоторых различных a (идея алгоритма Рабина).
Электронная подпись . Принцип электронной подписи легко выводится из алгоритма RSA. Пусть нужно подписать текст T . Этот текст нудно «свернуть» в некое число y . Для свертки используют алгоритм хэширования. Теперь из уравнения (1.13) на основании секретного ключа получают подпись X . Число X и возвращается вместе с T и y в качестве подписи в документу Т . Не зная секретного ключа d (заменяющего фамилию), нельзя найти X . Проверяющий легко проверит (1.1), чтобы удостовериться, что X и y соответствуют друг другу. Заметим, что кто-либо может перехватить документ и подписать его своей подписью, если ему известно преобразование (1.13). Поэтому принятый «подделанный» документ должен быть «застрахован».
Для этого используется число e – открытый ключ подписавшего документ. Теперь очень легко проверить соотношение:
.
Подобрать секретный ключ d к открытому ключу e практически невозможно.
Метод Диффи-Хеллмана .
Метод Диффи и Хеллмана является двухключевым. Каждый абонент в сети имеет два ключа: один секретный – , второй открытый, вычисляемый по формуле
,
где p – большое простое число (взаимно простое с ); .
Число выбирается так, чтобы числа , , …, по модулю p давали некоторую перестановку чисел {1, 2, …, p -1}. Число называется первообразным корнем p . Все абоненты публикуют свои открытые ключи . Допустим, абоненты A и B хотят передать друг другу информацию. Тогда первый из них, например A , берет открытый ключ абонента B и вычисляет.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию