Научные проблемы Интернета (стр. 1 из 5)
УО «БГУИР»
кафедраинформационных технологий автоматизированных систем
РЕФЕРАТ
на тему:
«Научные проблемы Интернета»
МИНСК, 2008
Научные проблемы Интернета группируются вокруг следующих задач:
· Защита информации
· Сжатие информации
· Поиск информации
· Распознавание информационных объектов (текста и образов)
· Прогнозирование временных рядов
· Классификация документов
· Выбор и оценка многокритериальных альтернатив
· Принятие решений и логический вывод и др.
Рассмотрение всех этих задач выходит за рамки настоящего труда. Рассмотрим только некоторые задачи.
Современные способы защиты информации используют в первую очередь различные методы шифрования. Мы рассмотрим здесь два криптографических метода: 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, равный
. Но 
, 
. Поэтому 
.Теперь нетрудно это правило применить, скажем, к
713mod 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 по формуле: