Вопрос «Как работает шифрования RSA»?«может пониматься двумя способами»:
- Каковы расчеты для RSA вер- и расшифрования требуется?
- Почему работают соответствующие формулы?
Ниже я буду только для версии RSA- и расшифровки кратко объяснить необходимые вычисления, а затем задать, Почему эти формулы работают.
1 Расчеты с вер- и расшифровка
Прежде чем вы вер- и расшифровки, должен быть создан первый соответствующей пары ключей (Секция 1.1). В следующем разделе 1.2 использует пару ключей, обычный текст для зашифрования и расшифрования.
1.1 Создайте пару ключей
Для генерации пары ключей, требуется два больших простых чисел, Мы называем их p и q. Эти primes требуются только для генерации пары ключей, более точным, для вычисления в частном от открытого ключа. Если это будет сделано, больше не требуются простые числа.
Является продуктом двух чисел m расчет, Затем, как класс остаточные (по модулю) используется:
(1) m = p * q
Затем вы выбираете случайное число s (кодирование), в (Вместе с m) открытый ключ используется в качестве. Она должна быть Копростые и менее чем Фи(m) быть. На следующем шаге ключ для расшифровки должен этот ключ (d) (расшифровать) рассчитать. Это (d) Поиск, так что следующая формула удовлетворен:
(2) s * d mod фи(m) = 1
Фи() Функция Эйлера. Это настолько дорогостоящей для большого числа для определения, что даже современных компьютеров для этого потребуются десятилетия. Однако существует исключение: Если разложение простое число m Как известно. Как мы m рассчитывается как произведение двух чисел, Мы понимаем, разложение простое число: p и q. В этом случае рассчитывается Фи(m) Кому:
(3) Фи(m)=(p-1)*(q-1)
В настоящее время (2) решены с использованием расширенного алгоритм Евклида.
Тогда у нас:
(s,m) для открытого ключа и
((d),m) как закрытый ключ.
Все остальные значения больше не требуется.
1.2 Вер- и расшифровки
Ряд K (Обычный текст) затем может быть зашифрован следующим с открытым ключом:
(4) 
V Это зашифрованный открытый текст. Это число может быть расшифрован снова с помощью следующей формулы:
(5) V(d) МО m = K
2 Почему работают формулы для вер- и расшифровка?
Должно быть показано, что после применения формулы шифрования (4) на K и затем формула расшифровки (5) Исходный номер снова K выходит.
Прежде всего, это должно быть ограничено легко: Вер- и расшифровки работает только для обычного текста K, Если он модуль m — взаимно простые числа.
Работы системы RSA, потому что
- все m teilerfremden числа по модулю m создать группу (Претензии 1) и
- всегда находится в группе, что число, возведенное в количество элементов в группе власти является одним из результатов всегда количество группы (Претензии 2: Теорема Эйлера-ферма).
Сначала я покажу, Это, Если выполнены эти два условия, на самом деле RSA процедура работает. Затем я покажу, что оба условия.
Вер- и расшифровки подряд применяется результаты:
(6) (Ks)^ d моделирование m = K
Оно должно быть показано здесь, что это K выходит обратно в. В (6) квадратные скобки можно решить:
(7) Ks * d МО m = K
Если он с в количество элементов (т.е.. количество m teilerfremden числа) упомянутые, Затем применяется:
(8) Kв *K = K mod m,
Поскольку согласно претензии 2 применяет: Kв МО m =. 1. Формула (8) может использоваться для
(9) K 1 МО m = K
Поскольку количество элементов возникает ряд в число 1 результаты в, Он делает это для 2*в, 3*в, 4*в…, Общие f *:
(10) K* f 1 МО m = K
D.h. Уравнение (7) удовлетворяется, Если имеет значение true:
(11) * f 1 = d * e
Это соответствует расчету (d) По формуле (2), потому что Фи(m) число m teilerfremden числа в на (Это определение функции Эйлера):
(12) = Фи(m)
В (11) Мы использовали:
(11) Фи(m)*f + 1= d * e
Если вы в (2) по модулю Фи(m) удален, Вам подходящей фактор f Выбор, для получения точных (11).
Таким образом уместно, -Если претензии 1 и 2 true - добавив ряд K в формуле (4) зашифрованный номер V может быть рассчитана, так что, включив этот номер в формуле (5) Исходный номер снова K выходит. В следующих главах претензии, соответственно 1 и 2 доказана.