Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Алгоритм шифрования RSA

Модульная экспонента

Целочисленное умножение

Однонаправленные функции

 

Реализация асимметричных криптосистем основана на использовании однонаправленных функций.

Пусть X и Y – некоторые произвольные множества. Функция называется однонаправленной функцией, если для любого элемента можно легко вычислить его образ, однако, зная элемент, достаточно сложно получить его прообраз, хотя такой элемент x однозначно существует, хотя бы один.

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

Рассмотрим несколько примеров однонаправленных функций, имеющих большое значение для криптографии.

 

Вычисление произведения двух очень больших целых чисел P и Q (N = P * Q) является несложной задачей для ЭВМ. Однако, решение обратной задачи, заключающейся в нахождении делителей P и Q большого числа N (в особенности, когда P и Q – большие простые числа), является практически неразрешимой задачей. Если N»264 и P» Q, то задача факторизации не разрешима за приемлемое время на современных ЭВМ. Поэтому целочисленное умножение является однонаправленной функцией.

Возведение очень большого числа A в очень большую степень x (), то есть вычисление, где модуль M тоже большое число, является несложной задачей для ЭВМ. Однако решение обратной задачи – нахождения степени x по известным у, A, M такой, что (задача дискретного логарифмирования,), практически не разрешима за приемлемое время на современных ЭВМ (эффективного алгоритма вычисления дискретного логарифма пока не найдено). Поэтому модульная экспонента является однонаправленной функцией.

Рассмотрим простую интерпретацию сказанного. Пусть задано: А=2, х=2, М=4. Тогда = 0. Пусть А=2, х=3, М=4. Тогда = 0. Отсюда видно, что по у вычислить х можно только полным перебором всех вариантов даже, если известны А и М.

Кроме однонаправленных функций важное значение для криптографии с открытым ключом имеют однонаправленные функции с «потайным входом», эффективное обращение которых возможно, если известен секретный «потайной ход» (секретное число или другая информация, ассоциируемая с функцией).

 

 

Алгоритм RSA был предложен в 1978 году Р.Райвестом, А. Шамиром, А. Адлеманом и был назван по первым буквам фамилий его авторов. Данный алгоритм стал первым алгоритмом шифрования с открытым ключом. Надежность данного алгоритма основывается на трудности факторизации больших чисел и вычисления дискретных логарифмов [14,2].

В криптосистеме RSA открытый ключ ОК, секретный ключ СК, исходное сообщение М и шифротекст С являются целыми числами от 0 до N -1, где N – модуль.

Пусть пользователь А является получателем сообщения, которое ему должен переслать отправитель B.

Пользователь A должен вначале сгенерировать ключевую пару RSA, это он делает следующим образом.

 

<== предыдущая лекция | следующая лекция ==>
Принципы асимметричного шифрования | Действия получателя А
Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 527; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.008 сек.