Навигация
Асимметричные алгоритмы шифрования
50231
знак
14
таблиц
1
изображение
2.2 Асимметричные алгоритмы шифрования
В асимметричных алгоритмах шифрования (или криптографии с открытым ключом) для зашифровывания информации используют один ключ (открытый), а для расшифровывания - другой (секретный). Эти ключи различны и не могут быть получены один из другого.
Схема обмена информацией такова:
· получатель вычисляет открытый и секретный ключи, секретный ключ хранит в тайне, открытый же делает доступным (сообщает отправителю, группе пользователей сети, публикует);
· отправитель, используя открытый ключ получателя, зашифровывает сообщение, которое пересылается получателю;
· получатель получает сообщение и расшифровывает его, используя свой секретный ключ.
2.2.1 Алгоритм Диффи-Хелмана
Алгоритм Диффи-Хелмана (Whitfield Diffie и Martin Hellman, 1976 год) использует функцию дискретного возведения в степень и похож на метод Эль-Гамаля.
Сначала генерируются два больших простых числа n и q. Эти два числа не обязательно хранить в секрете. Далее один из партнеров P1 генерирует случайное число x и посылает другому участнику будущих обменов P2 значение A = qx mod n
По получении А партнер P2 генерирует случайное число у и посылает P2 вычисленное значение B = qy mod n
Партнер P1, получив В, вычисляет Kx = Bx mod n, а партнер P2 вычисляет Ky = Ay mod n. Алгоритм гарантирует, что числа Ky и Kxравны и могут быть использованы в качестве секретного ключа для шифрования. Ведь даже перехватив числа А и В, трудно вычислить Kx или Ky.
Алгоритм Диффи-Хелмана, обеспечивая конфиденциальность передачи ключа, не может гарантировать того, что он прислан именно тем партнером, который предполагается. Для решения этой проблемы был предложен протокол STS (station-to-station). Этот протокол для идентификации отправителя использует технику электронной подписи. Подпись шифруется общим секретным ключом, после того как он сформирован. Подпись включает в себя идентификаторы как P1, так и P2.
2.2.2 RSA
Защищен патентом США N 4405829. Разработан в 1977 году в Массачусетском технологическом институте (США). Получил название по первым буквам фамилий авторов (Rivest, Shamir, Adleman). Криптостойкость основана на вычислительной сложности задачи разложения большого числа на простые множители.
Алгоритм RSA предполагает, что посланное закодированное сообщение может быть прочитано адресатом и только им. В этом алгоритме используется два ключа - открытый и секретный. Данный алгоритм привлекателен также в случае, когда большое число субъектов (N) должно общаться по схеме все-со-всеми. В случае симметричной схемы шифрования каждый из субъектов каким-то образом должен доставить свои ключи всем остальным участникам обмена, при этом суммарное число используемых ключей будет достаточно велико при большом значении N. Применение асимметричного алгоритма требует лишь рассылки открытых ключей всеми участниками, суммарное число ключей равно N.
Сообщение представляется в виде числа M. Шифрование осуществляется с помощью общедоступной функции f(M), и только адресату известно, как выполнить операцию f-1. Адресат выбирает два больших простых (prime) числа p и q, которые делает секретными. Он объявляет n=pq и число d, c (d,p-1)=(d,q-1)=1 (один из возможных способов выполнить это условие, выбрать d больше чем p/2 и q/2). Шифрование производится по формуле:
f(M) ≡ Md mod n,
где M и f(M) оба ≤ n-1. Как было показано, может быть вычислено за разумное время, даже если M, d и n содержит весьма большое число знаков. Адресат вычисляет M на основе Md, используя свое знание p и q. В соответствие со следствием , если
dc ≡ (p-1)1, тогда (Md)e ≡ p1.
Исходный текст M получается адресатом из зашифрованного F(M) путем преобразования: M = (F(M))e (mod pq). Здесь как исходный текст, так и зашифрованный рассматриваются как длинные двоичные числа.
Аналогично (Md)e ≡ qM, если dc ≡ (q-1)1. e удовлетворяет этим двум условиям, если cd ≡ (p-1) (q-1)1. Теорема 1 гласит, что мы можем позволить e=x, когда x является решением уравнения dx + (p-1)(q-1)y = 1.
Так как (Md)e - M делимо на p и q, оно делимо и на pq, следовательно, мы можем определить M, зная Md, вычислив его значение в степени e и определив остаток от деления на pq. Для соблюдения секретности важно, чтобы, зная n, было нельзя вычислить p и q. Если n содержит 100 цифр, подбор шифра связан с перебором ~1050 комбинаций. Данная проблема изучается уже около 100 лет. RSA-алгоритм запатентован (20 сентября 1983, действует до 2000 года).
Теоретически можно предположить, что возможно выполнение операции f-1, не вычисляя p и q. Но в любом случае задача эта не проста и разработчики считают ее трудно факторизуемой.
Предположим, что мы имеем зашифрованный текст f(M) и исходный текст M, и мы хотим найти значения p и q. Нетрудно показать, что таких исходных данных для решения задачи недостаточно - надо знать все возможные значения Mi.
Проясним использование алгоритма RSA на конкретном примере. Выбираем два простые числа p=7; q=17 (на практике эти числа во много раз длиннее). В этом случае n = p*q будет равно 119. Теперь необходимо выбрать e, выбираем e=5. Следующий шаг связан с формированием числа d так, чтобы d*e=1 mod [(p-1)(q-1)]. d=77 (использован расширенный алгоритм Эвклида). d - секретный ключ, а e и n характеризуют открытый ключ. Пусть текст, который нам нужно зашифровать представляется M=19. С = Memod n. Получаем зашифрованный текст C=66. Этот “текст” может быть послан соответствующему адресату. Получатель дешифрует полученное сообщение, используя М= Cdmod n и C=66. В результате получается M=19.
На практике общедоступные ключи могут помещаться в специальную базу данных. При необходимости послать партнеру зашифрованное сообщение можно сделать сначала запрос его открытого ключа. Получив его, можно запустить программу шифрации, а результат ее работы послать адресату. На использовании общедоступных ключей базируется и так называемая электронная подпись, которая позволяет однозначно идентифицировать отправителя. Сходные средства могут применяться для предотвращения внесения каких-либо корректив в сообщение на пути от отправителя к получателю. Быстродействующие аппаратные 512-битовые модули могут обеспечить скорость шифрования на уровне 64 кбит в сек. Готовятся ИС, способные выполнять такие операции со скоростью 1 Мбайт/сек. Разумный выбор параметра e позволяет заметно ускорить реализацию алгоритма.
Похожие работы
... для блокировки загрузки с FDD; Интерфейс для блокировки загрузки с CD-ROM; Программное обеспечение формирования списков контролируемых программ; Документация. 2. Система защиты информации "Secret Net 4.0" Рис. 2.1. Назначение: Программно-аппаратный комплекс для обеспечения информационной безопасности в локальной вычислительной сети, рабочие ...
... 6.0. – Microsoft Press, 1998. – 260 c. ISBN 1-57231-961-5 ТУЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ На правах рукописи Карпов Андрей Николаевич ЗАЩИТА ИНФОРМАЦИИ В СИСТЕМАХ ДИСТАНЦИОННОГО ОБУЧЕНИЯ С МОНОПОЛЬНЫМ ДОСТУПОМ Направление 553000 - Системный анализ и управление Программная подготовка 553005 – Системный анализ данных и моделей принятия решений АВТОРЕФЕРАТ диссертации на соискание степени ...
... , в которые преступники хотят вмешаться, так и для планирования методов совершения преступления. Таким образом, осуществляется «оптимизация» способа совершения преступления.[2] 1.3 Методы защиты информации Для решения проблем защиты информации в сетях прежде всего нужно уточнить возможные причины сбоев и нарушений, способные привести к уничтожению или нежелательной модификации данных. К ним ...
... части локальной сети не позволяют останавливаться на известных достигнутых результатах и побуждают на дальнейшее исследование в дипломной работе в направлении разработки локальной сети с беспроводным доступом к ее информационным ресурсам, используя перспективные технологии защиты информации. 2. Выбор оборудования, для перспективных технологий СПД 2.1 Выбор передающей среды Зачастую перед ...
0 комментариев