Подробное объяснение алгоритма RSA

внешний интерфейс алгоритм Безопасность
Подробное объяснение алгоритма RSA

предисловие

Обобщить:В этой статье описывается подробное объяснение алгоритма RSA, включая внутренние математические принципы и процесс генерации.

Увлажняйте друг друга. В конце концов нужна любовь легкая, как вода.

текст

Я написал статью раньшеПроцесс шифрования данных протокола SSL, в котором подробно описан процесс шифрования данных и необходимые алгоритмы. Протокол SSL умело использует два алгоритма, симметричное шифрование и асимметричное шифрование, для шифрования данных. Эта статья предназначена в основном для объяснения одного из наиболее распространенных алгоритмов асимметричного шифрования — алгоритма RSA. По сути, это описание того, как генерируются закрытый ключ и открытый ключ. Во-первых, давайте разберемся с историей этого алгоритма:

История алгоритма RSA

RSA была создана в 1977 г.Рональд Левист(Рон Ривест),Ади Саммер(Ади Шамир) иЛеонард Аардман(Леонард Адлеман). Все трое былиМассачусетский технологический институтРабота. RSA — это сочетание первых букв их фамилий.

Но на самом деле в 1973 году математики, работавшие в ГЧККлиффорд Киркус(Клиффорд Кокс) предложил идентичный алгоритм во внутреннем документе, но его выводы были засекречены и не публиковались до 1997 года.

Так кто же изобретатель алгоритма RSA? Трудно сказать, как будто Белл не был первым, кто изобрел телефон, но Белла все помнят, тут нам как сторонним наблюдателям не нужно быть серьезными, главное содержание этого алгоритма:

Процесс алгоритма RSA

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

1. Найдите два простых числа, которые не идентичны

Выбираем по желанию два больших простых числа p и q, p не равно q, и вычисляем N=p*q;

Что такое простое число?Я думаю, некоторые люди, возможно, забыли, определение выглядит следующим образом:

За исключением 1 и самого числа, число, которое не делится на другие натуральные числа (его также можно определить как число, имеющее только 1 и два положительных делителя).

Например, 2, 3, 5 и 7 — простые числа, а 9 — нет, потому что 3*3=9.

2. Получить r по функции Эйлера

r = φ(N) = φ(p)φ(q) = (p-1)(q-1).

Математическая концепция здесь заключается в том, что такое функция Эйлера и что такое функция Эйлера?

Функция ЭйлераОпределение:

Функция Эйлера ф (п)Меньше или равноnположительное целое число иnКоличество взаимно простых чисел.

взаимное превосходствоОпределение:

Два или более целых числа называются, если их наибольший общий делитель равен 1.взаимное превосходство

Например:ф(8) = 4,потому что1,3,5,7Гармония8Копрайм.

Выведите функцию Эйлера:

(1) Еслиn = 1, ф(1) = 1; (Единственное положительное целое число, меньше или равно 1, которое относительно пронзит до 1, составляет 1 сам);

(2) еслиnэто простое число,φ(n) = n - 1; потому что простое число взаимно просто с каждым меньшим числом. Например, 5, меньшие положительные целые числа 1, 2, 3 и 4 взаимно просты с ним;

(3) Еслиnдаaизkсила, тоφ(n) = φ(a^k) = a^k - a^(k-1) = (a-1)a^(k-1);

(4) Еслиm,nвзаимно простое, тогдаφ(mn) = φ(m)φ(n)

**Доказательство:**ПустьA, B, Cэто сm, n, mnМножество взаимно простых чисел согласноКитайская теорема об остатках(Детская обувь, часто читающая математические аллюзии, должна понимать, что теорему об остатках также называют точкой солдат Хань Синя, также называемой теоремой Сунь-Цзы),A*Bа такжеCМожно установить двукратные отношения. (Или может быть дано с точки зрения элементарной алгебраическойЭйлер доказал простую функцию произведения), поэтому значение φ(n) используетОсновная теорема арифметикизнать. (из Википедии)

3. Выберите целое число e, меньшее r и взаимно простое с r.

Выберите целое число e, меньшее r и взаимно простое с r, и найдите элемент, обратный по модулю e относительно r, названный какd(*ed = 1(mod r)* по модулю обратный элемент существует тогда и только тогда, когда e и r взаимно просты),eМы обычно берем 65537.

Модульный обратный элемент:

Если два натуральных числа a и n взаимно просты, то нужно найти это целое числоb, так что ab-1 делится на n, или остаток от деления ab на n равен 1.

Например3а также5взаимное превосходство,3о5Элемент, обратный по модулю, может быть равен 2, потому что3*2-1=5Делится на 5. Таким образом, очевидно, что существует более одного обратного по модулю элемента, и целое число, кратное 2 плюс-минус 5, является элементом, обратным по модулю 3 относительно 5 *{...-3, 2,7,12...} * подставить в формулу3*2 = 1 (mod 5)

Полезность упомянутой выше функции Эйлера на самом деле заключается в теореме Эйлера:

Теорема Эйлера:

Если два положительных целых числаaа такжеnвзаимно простое, тогдаnФункция Эйлераф (п)Можно установить следующее уравнение:

a^φ(n) = 1(mod n)

Следовательно:aизф (п - 1)Сила определенноaоnМодульный элемент.

Теорему Эйлера можно использовать для доказательства того, что обратный по модулю элемент должен существовать.

Из определения по модулю обратных элементов и теоремы Эйлера мы знаем, чтоaизф (п)Th Power Minus One, n может быть делимым. Например, 5 Prime и 3, а также5функция Эйлераф(5)равно 4, поэтому3из4Мощность*(81)минус 1, может быть5* Делимый (80/5=16).

Маленькая теорема Ферма:

Предположим, что натуральное число a взаимно просто с простым числом p, потому что простое число p имеетф(р)равныйp-1, то теорему Эйлера можно записать в виде

a^(p-1) = 1 (mod p)

На самом деле это частный случай теоремы Эйлера.

4. Разрушение p и q

В этот момент наш *(N , e)открытый ключ,(N, d)Для закрытого ключа Алиса поместит открытый ключ(N, e)перешло к Бобу, затем(N, d)* Спрячьтесь сами. Генерируется пара открытого ключа и закрытого ключа, а как потом ее использовать? Пожалуйста, посмотри:Подробное объяснение процесса шифрования данных протокола SSL

Безопасность алгоритма RSA

Мы знаем, что алгоритмы асимметричного шифрования, такие как RSA, очень безопасны, так почему же они безопасны? Давайте посмотрим на несколько чисел, сгенерированных вышеуказанными процессами:

  • p,q: случайным образом выбираем два больших простых числа;
  • N: состоит из двух больших простых чиселpа такжеqполучается умножением.N = p * q;
  • r: получено из функции ЭйлераNзначение ,r = φ(N) = φ(p)φ(q) = (p-1)(q-1).
  • e: случайным образом выберите сумму иrНа практике обычно выбирают взаимно простые числа 65537;
  • d: d - элемент, обратный по модулю e относительно r, полученный на основе теоремы Эйлера,ed = 1 (mod r);

Nа такжеeМы все будем использовать его публично, самое главное — закрытый ключd,dПосле утечки шифрование теряет свое значение. Итак, каков процесс получения d? следующим образом:

  1. Например, мы знаем e и r, потому что d — элемент, обратный по модулю e относительно r, r — значение φ(N)
  2. а такжеφ(N)=(p-1)(q-1), Поэтому мы знаем, что мы можем получить P и Q D;
  3. N = pq, мы только знаем N и E из публичных данных, поэтому ключ к проблеме заключается в том, может ли факторизация N получить P и Q

Итак, я пришел к выводу, упомянутому в предыдущем блоге, принципу асимметричного шифрования:

Легко умножить а и b, чтобы получить произведение с, но чрезвычайно трудно вывести а и b из произведения с. То есть чрезвычайно сложно разложить на множители большое число

В настоящее время количество битов, которые публично расшифрованы, составляет 768 бит, а фактическое использование обычно составляет 1024 или 2048 бит, поэтому теоретически это очень безопасно.

постскриптум

Ядром алгоритма RSA является теорема Эйлера, согласно которой мы можем получить закрытый ключ для обеспечения безопасности всей коммуникации.

Категории