Научные проблемы Интернета
УО «БГУИР» кафедра информационных технологий автоматизированных систем РЕФЕРАТ на тему: «Научные проблемы Интернета» МИНСК, 2008 Научные проблемы Интернета группируются вокруг следующих задач: · Защита информации · Сжатие информации · Поиск информации · Распознавание информационных объектов (текста и образов) · Прогнозирование временных рядов · Классификация документов · Выбор и оценка многокритериальных альтернатив · Принятие решений и логический вывод и др. Рассмотрение всех этих задач выходит за рамки настоящего труда. Рассмотрим только некоторые задачи. 1 Защита информации Современные способы защиты информации используют в первую очередь различные методы шифрования. Мы рассмотрим здесь два криптографических метода: RSA и DES. Основные принципы криптографии можно сформулировать следующим образом. 1. В шифровании основную роль играет не алгоритм, а ключ. 2. Алгоритм шифрования должен быть таким, чтобы шифрование выполнялось легко и эффективно с вычислительной точки зрения; наоборот, дешифрование должно представлять собой сложнейшую математическую задачу (например, переборного типа). Алгоритм RSA. Пусть необходимо передать по линии связи числа x (рассмотрим здесь только целые положительные числа). Вместо числа x передают число y, вычисляемое по формуле где e и m являются открытыми числами (известны всем абонентам сети). Требуем, чтобы e и m были взаимно простыми числами (т.е. не числами общих делителей, кроме 1, причем ). Оказывается, что зная y, e и m, найти x - сложнейшая математическая задача. Пока же продемонстрируем, как найти y по x, e, m. Операция находит целочисленный остаток 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, удовлетворяющее условию где - значение функции Эйлера от числа m. Функция Эйлера вычисляется сравнительно просто. Так, Если p простое число и r - целое, то Формул (1.4) и (1.5) достаточно для того, чтобы найти функцию Эйлера для любого целого положительного числа. В нашем случае получаем: . Для любознательных читателей отметим, что значение равно числу целых чисел на отрезке 1..m, взаимно простых с m. Отыскание значения функции Эйлера для больших целых чисел является вычислительной задачей очень большой сложности. Пример. . Все четыре числа: 1, 2, 3, 4 взаимно просты с m. Теперь обратимся к уравнению (3.3). В этом уравнении d играет роль секретного ключа. Решить уравнение (3.3) путем перебора значений d можно, но если в числе m, например, 100 цифр, то на вычисление d уйдет достаточно много времени. Для небольших значений, таких как в нашем примере, можно воспользоваться алгоритмом решения уравнений в целых числах, который мы и приведем. Итак, в нашем примере уравнение такое: Уравнение (1.6) можно переписать следующим известным образом: В (1.7) r и d неизвестные целые числа. Представим (1.7) в виде системы двух линейных неравенств. , , или, что эквивалентно: В неравенстве с положительной правой частью выделим член с минимальным по модулю коэффициентом и разрешим неравенство относительно этого члена: , . Отсюда легко получить отсекающее неравенство: Здесь z - новая целочисленная переменная. Заметим, что переход от (a) к (b) в (1.9) правомерен, так как r , d, z - целочисленны. Выполним подстановку (3.9) в систему (1.8). Получим новую систему: Обратим внимание на следующее принципиальное обстоятельство. В сравнении с (1.8) значение минимального коэффициента понизилось. Этот факт можно строго обосновать. Следовательно, весь процесс должен закончиться рано или поздно одним из двух результатов: 1) минимальный коэффициент по модулю станет равным 1 (как в (1.10)); будет получена система вида , , где a и b - взаимно просты (в этом случае нет решения в целых числах). В первом случае процесс решения завершен. Получаем из (1.10) подстановку для d: Тогда из (1.9) найдем: Итак, формулы (1.11) и (1.12) и дают нам итоговые подстановки для d и r из (1.7). Например, пусть . Тогда , . Возьмем именно это значение для минимального d. Итак, мы подошли к решающему моменту: наш секретный ключ . Получили число , , .Восстанавливаем x по формуле: Итак, . Все сошлось. Возьмем, например, . Тогда , : (ответ тот же). Таким образом, не имеет значения, какое z брать для получения d. Метод RSA мы завершим следующим замечанием. Метод RSA вообще говоря требует, чтобы m было большим простым числом. Для установления факта, что m - простое, можно использовать малую теорему Ферма: В (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 и вычисляет . Таким образом, оба абонента находят одно и то же число, которое они и используют в качестве ключа для обмена сообщениями. При этом секретные ключи абонентов остаются известными только им одним. Алгоритм DES. Алгоритм DES (description encryption system) состоит в последовательности чередующихся операций подстановки и перемешивания. Алгоритм DES использует секретный ключ K. Пусть, например, блок данных есть , а ключ . Подстановка есть сложение по модулю 2: Таким образом, операция подстановки непредсказуемым образом искажает исходные данные. Для восстановления исходных данных достаточно выполнить подстановку вторично: Операция перемешивания заключается в обмене местами двух блоков в соответствии с заранее составленными таблицами. Длина обмениваемых блоков одинакова, но варьирует от одного прохода к другому. Операция подстановки выполняется не над целым ключом, а над случайно выбираемой его частью. Эта случайно выбираемая часть сама определяется значением ключа. Одним из способов получения псевдослучайных чисел является следующий: Здесь - псевдослучайное число, порожденное на шаге i. первоначально полагают, например, . В качестве константы C примем где K - секретный ключ. Величина M как правило равна ; величина n равна числу разрядов генерируемого псевдослучайного числа. Например, пусть , , , , :
Страницы: 1, 2, 3
|