|
||||||||||||||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Описание алгоритмаАлгоритм, разработанный Ривестом, Шамиром и Адлеманом, использует выражения с экспонентами. Данные шифруются блоками, каждый блок рассматривается как число, меньшее некоторого числа n. Шифрование и дешифрование имеют следующий вид для некоторого незашифрованного блока М и зашифрованного блока С. С = Ме (mod n)M = Cd (mod n) = (Me)d (mod n) = Med (mod n)Как отправитель, так и получатель должны знать значение n. Отправитель знает значение е, получатель знает значение d. Таким образом, открытый ключ есть KU = {e, n} и закрытый ключ есть KR = {d, n}. При этом должны выполняться следующие условия:
Сначала рассмотрим первое условие. Нам необходимо выполнение равенства: Med = М (mod n)Рассмотрим некоторые математические понятия, свойства и теоремы, которые позволят нам определить e, d и n.
Тогда w Zp z: w · z 1 mod p Доказательство этого следует из того, что т.к. w и p взаимнопростые, то при умножении всех элементов Zp на w остатками будут все элементы Zp, возможно, переставленные. Таким образом, хотя бы один остаток будет равен 1.
Если p и q - простые, то Φ(p · q) = (p-1) · (q-1). В этом случае Zp · q ={0, 1, ј, (p · q - 1)}. Перечислим остатки, которые не являются взаимнопростыми с p · q: {p, 2 · p, ј, (q-1) · p}{q, 2 · q, ј, (p-1) · q}0Таким образом Φ(p · q) = p · q - [(q-1) + (p-1) + 1] = p · q - (p+q) + 1 = (p-1) · (q-1).
an-1 1 mod n, если n - простое. Если все элементы Zn умножить на а по модулю n, то в результате получим все элементы Zn, быть может, в другом порядке. Рассмотрим следующие числа: {a mod n, 2 · a mod n, ј, (n-1) · a mod n} являются числами {1, 2, ј, (n-1)}, быть может, в некотором другом порядке. Теперь перемножим по модулю n числа из этих двух множеств. [(a mod n) · (2a mod n) ·... · (n-1)a mod n] mod n (n-1)! mod n(n-1)! an-1 (n-1)! mod nn и (n-1)! являются взаимнопростыми, если n - простое, следовательно, an-1 1 mod n.
aΦ(n) 1 mod n для всех взаимнопростых a и n. Это верно, если n - простое, т.к. в этом случае Φ(n) = n-1. Рассмотрим множество R = {x1, x2, ј, xΦ(n)}. Теперь умножим по модулю n каждый элемент этого множества на a. Получим множество S = {a · x1 mod n, a · x2 mod n, ј, a · xΦ(n) mod n}. Это множество является перестановкой множества R по следующим причинам. Так как а является взаимнопростым с n и xi являются взаимнопростыми с n, то a · xi также являются взаимнопростыми с n. Таким образом, S - это множество целых, меньших n и взаимнопростых с n. В S нет дублей, т.к. если a · xi mod n = a · xj mod n xi = xj. Следовательно, перемножив элементы множеств S и R, получим: Φ(n) Φ(n) ∏ (a · xi mod n) ∏ xi mod ni=1 i=1 Φ(n) Φ(n)(∏ a · xi ∏ xi) mod n i=1 i=1 Φ(n) Φ(n)(aΦ(n) · ∏ xi ∏ xi) mod n i=1 i=1(aΦ(n) 1) mod nТеперь рассмотрим сам алгоритм RSA. Пусть p и q - простые. n = p · q.Надо доказать, что M < n: MΦ(n) = M(p-1) · (q-1) 1 mod n Если gcd (M, n) = 1, то соотношение выполняется. Теперь предположим, что gcd (M, n) 1, т.е. gcd (M, p · q) 1. Пусть gcd (M, p) 1, т.е. M = c · p gcd (M, q) = 1, так как в противном случае M = c · p и M = l · q, но по условию M < p · q. Следовательно, MΦ(q) 1 mod q(MΦ(q))(p) 1 mod qMΦ(n) 1 mod qПо определению модуля это означает, что MΦ(n) = 1 + k · q. Умножим обе части равенства на M = c · p. Получим MΦ(n)+1 = c · p + k · q · c · p.MΦ(n) 1 mod nИли MΦ(n)+1 M mod nТаким образом, следует выбрать e и d такие, что е · d 1 mod (n) Или e d-1 mod Φ(n) e и d являются взаимнообратными по умножению по модулю Φ(n). Заметим, что в соответствии с правилами модульной арифметики, это верно только в том случае, если d (и следовательно, е) являются взаимнопростыми с Φ(n). Таким образом, gcd (Φ(n), d) = 1. Теперь рассмотрим все элементы алгоритма RSA.
Закрытый ключ состоит из {d, n}, открытый ключ состоит из {e, n}. Предположим, что пользователь А опубликовал свой открытый ключ, и что пользователь В хочет послать пользователю А сообщение М. Тогда В вычисляет С = Ме (mod n) и передает С. При получении этого зашифрованного текста пользователь А дешифрует вычислением М = С d (mod n). Суммируем алгоритм RSA: Создание ключей
Шифрование
Дешифрование
Рассмотрим конкретный пример: Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.) |