Что такое шифр RSA ?

Что такое шифр RSA ?

Ты уже знаешь

Асимметричное шифрование использует два ключа: открытый для шифрования сообщений и закрытый для расшифровки.

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

Шифр RSA представляет собой асимметричный криптографический алгоритм. У него есть пара ключей — открытый (e, n) и закрытый (d, n).

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

Любой человек, который хочет получить зашифрованное сообщение, «выставляет» свой открытый ключ.

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

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

Как обозначить закрытый и открытый ключ?

Выберем любые два простых числа и обозначим их как pи q. Эти числа должны быть как можно больше.

Рассчитываем стоимость n = p • q. Значение n является частью открытого и закрытого ключа, оно также определяет максимально возможный числовой размер отправляемого нами сообщения.

Мы вычисляем значение функции Эйлера для n и выбираем любое число , eудовлетворяющее условию , которое будет взаимно простым со значением . Номер является частью открытого ключа.(1

e

Мы вычисляем обратное значение по модулю числа и получаем число , которое является элементом закрытого ключа.φphi(n)ed

После выполнения всех четырех шагов мы можем шифровать и расшифровывать сообщения в соответствии со следующими функциями:

и:

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

Важный!

Если вы заботитесь о конфиденциальности, никому не говорите даже одно из простых чисел p или q значение функции Эйлера . Открытый показатель степени широко известен, поэтому, когда кто-то также знает значение , он может узнать закрытый ключ и взломать шифр.φphi(n)

Почему p и q должны быть простыми числами?

Безопасность шифрования RSA основана на сложности факторизации чисел . Разложить на множители числа, являющиеся произведением простых чисел , сложнее, чем разложить на множители числа, являющиеся произведением составных чисел. Следовательно, они должны быть первыми.pq

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

Функция Эйлера — это функция, которая сопоставляет каждому натуральному числу количество чисел, взаимно простых с ним и не превосходящих его.φphi(n)

Вторая причина этого заключается в том, что для простых чисел функция Эйлера принимает следующий вид:

фффф

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

Если x оно простое, то:

ф

– где p i q простые числа с показателем степени, равным 1.

Если бы p i q не были простыми числами, функция Эйлера приняла бы гораздо более сложный вид, что объективно усложнило бы ее вычисление, что было бы невыгодно в практических приложениях. Однако это второстепенная причина.

Предположим, мы хотим узнать чей-то закрытый ключ. Открытый ключ этого лица известен и принимает, например, следующие значения: e = 3и n = 33. Благодаря тому, что он n небольшой, мы можем легко - с помощью т.н. метод грубой силы - установить, что p = 11и q = 3. Здесь следует отметить, что не существует другой комбинации цифр, кроме 11 и 3, которая при умножении дала бы 33.

Предположим, что n = 2501. Существует только одна комбинация чисел, произведение которых точно такое, потому что переменные p и q являются простыми числами. Попытка найти простые множители методом грубой силы в случае n = 2501 более сложна в вычислительном отношении. Используя его, нам пришлось бы делить 40 раз, прежде чем мы нашли бы первый простой множитель, который в данном случае равен p 41. В этом примере q это 61.

Важный!

Нахождение значений p i q должно быть максимально затруднено, поэтому они должны быть одного порядка, потому что даже если n=11485методом грубой силы мы получим первый множитель очень быстро p=5, а затем вычислить второй множитель не составит труда. больше проблема, потому что достаточно разделить число n на 5 .

Для сравнения предположим теперь, что это n =6840. Мы можем получить число 6840, умножив, например, 3420 на 2, 1710 на 4 или 684 на 10. Существует много комбинаций составных чисел, которые дадут значение n.

Подводя итог: если p и q не простые, то мы можем разбить число n на множество простых множителей. Тогда, несмотря на то, что вычисление функции Эйлера становится потенциально гораздо более вычислительно сложным, нахождение всех простых множителей упрощается, а безопасность самого шифрования основана на сложности разложения числа n на простые множители . когда p и q не являются простыми, мы можем использовать другую формулу для вычисления функции Эйлера , а именно:

- где , , ... простые множители без повторений. Например, для числа 32 единственным простым делителем будет 2, как и для числа 1024 или 8192. Тогда:pIndeks dolny 11pIndeks dolny 22pIndeks dolny kk

Если бы мы методом грубой силы нашли все простые множители числа 8192, мы бы нашли их очень быстро, потому что, хотя это число больше 2501, его гораздо проще разложить на множители.

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

Если мы получим простые множители, мы сможем вычислить функцию Эйлера, а затем вычислить обратное значение по модулю этого e числа , и тогда наш ключ будет сломан.φphi(n).

Важный!

Безопасность RSA основана на сложности факторизации чисел. Следовательно, как объяснялось, p и q должны быть простые числа аналогичного (и как можно большего) порядка, чтобы эта сложность была максимально возможной.

Для вычисления оптимального обратного модуля также следует использовать простые числа.

Обратный модуль

Определение: модульная инверсия

Модульная обратная операция - это операция поиска для любой пары

такой x, что

В качестве альтернативы мы можем записать это как:

Вычисление обратного по модулю можно выполнить многими способами, но ни один из них не имеет полиномиальной сложности. Самый простой метод — это наивный метод подстановки x последовательных значений, пока вы не получите правильный результат.

Оптимальным методом является использование расширенного алгоритма Евклида.

Важный!

Расширенная версия алгоритма Евклида позволяет найти линейную комбинацию чисел по следующей формуле:

- где число x обратно по модулю b числа aпри условии, что числа a и b являются простыми. Это соотношение, упомянутое ранее, заключается в том, что для оптимального вычисления обратного модуля вы должны оперировать простыми числами.

Предположим, мы хотим вычислить обратное значение по модулю 5 от 2. Итак, для этого нам нужно решить следующее:

Тогда найди x.

Сделаем это методом грубой силы:

2 ∙ 1, что равно 2 по модулю 5 = 2

2 ∙ 2, что равно 4 по модулю 5 = 4

2 ∙ 3, что равно 6 по модулю 5 = 1

Таким образом x , мы можем поставить 3 под.

Однако это не единственное решение - пробуя дальше, мы найдем еще возможные значения x:

2 ∙ 4, т.е. 8 по модулю 5 = 3

2 ∙ 5, т.е. 10 по модулю 5 = 0

2 ∙ 6, т.е. 12 по модулю 5 = 2

2 ∙ 7, то есть 14 по модулю 5 = 4

2 ∙ 8, поэтому 16 по модулю 5 = 1

Так x что 8 тоже можно заменить.

Имеет ли значение выбор компонента d в ​​закрытом ключе?

Мы доказали, что модуль 5 от 2 имеет по крайней мере два решения, но правда в том, что решений бесконечно много. Однако существует ли оптимальный выбор результата для закрытого ключа?

Представленное выше шифрование имеет следующий вид:

и расшифровка будет выглядеть так:

Пример 1

Возьмем следующие два простых числа:

p = 3

q = 5

Итак:

n = 3 • 5 = 15

ффф

Мы выбираем относительно простое число из диапазона (1, 8).

Это может быть даже число 3, так что давайте предположим e = 3.

Затем мы вычисляем обратное значение по модулю числа , что, в свою очередь, после подстановки числового значения дает нам: 8 • x mod 3 = 1.φphi(n)e

φphi(n) • x mod e = 1

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

(3 • 1) mod 8 = 3

(3 • 2) mod 8 = 6

( 3 • 3) mod 8 = 1

(3 • 4) mod 8 = 4

(3 • 5) mod 8 = 7

(3 • 6) mod 8 = 2

(3 • 7) mod 8 = 5

(3 • 8) mod 8 = 0

(3 • 9) mod 8 = 3

(3 • 10 ) мод 8 = 6

(3 • 11) мод 8 = 1

Обратный модуль 8 из 3 будет, среди прочего, 3 и 11.

Значение 3 или 11 также является d значением нашего закрытого ключа.

Число, которое мы хотим зашифровать, должно быть меньше n, что в нашем случае равно 15. Итак, давайте выберем число 13.

Теперь давайте расшифруем сообщение, используя по очереди 3 и 11 в качестве значений d.

Пример, представленный выше, показывает, что для корректности алгоритма не имеет значения, какое число мы выберем в качестве d, лишь бы оно было обратным по модулю числа . С вычислительной точки зрения оптимальное решение — выбрать меньшее , однако оно не должно быть равным . Следует избегать ситуаций, когда закрытый ключ и открытый ключ имеют одинаковые значения, так как это будет слабостью, которой может воспользоваться наш потенциальный противник. В этом случае оптимальным выбором из соображений безопасности будет выбор 11.φphi(n)edded

Почему шифрование и дешифрование работают?

Следующая функция:

и обратная функция:

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

Нажмите, чтобы начать предварительный просмотрГрафика циферблата. Часы отмечены на часах: 12, 3, 6 и 9. Часы показывают 3 часа.

Источник: Contentplus.pl sp.z o.o. , лицензия: CC BY-SA 3.0.

Часы показывают 3 часа — например, предположим, что нас интересует только поведение часовой стрелки. Проходит 12 часов - часы снова показывают три часа. Время остановилось? Это те же 3 часа, что и 12 часов назад? Конечно нет.

Таким образом, утверждение, что 3 + 12 = 3, неверно, потому что часы не равны, а конгруэнтны . В математике мы запишем операцию сравнения как:

Мы также можем записать это отношение следующим образом:

Определение: конгруэнтность

Конгруэнтность (другими словами: конгруэнтность) по модулю n — это ситуация, в которой остатки от деленияи кравны (тогда выполняется равенство: a % n = b % n, которое также можно записать как ).[a]Indeks dolny nn = [b]Indeks dolny nn

Ранее представленное правило с часами математически выглядело бы так:

Операция шифрования и дешифрования основана на следующем принципе:

Следовательно, сообщение, которое мы отправляем в числовом виде, должно быть меньше n, потому что тогда даже для e = 1i d = 1сообщение, которое мы хотим отправить, будет отличаться от того, которое мы в итоге получим.

Для заинтересованных

Если вас интересует необычная арифметика, в которой 12 + 3 может равняться 3, стоит познакомиться с понятием алгебраической структуры, особенно группы и кольца.

Теория и практика

Чем больше простые числа p и q, тем сложнее угадать хотя бы одно из них. Здесь можно задать резонный вопрос: если злоумышленник знает, что мы используем только простые числа, почему бы не найти все простые числа и просто проверить все комбинации?

Основная проблема с такой стратегией заключается в том, что существует бесконечно много простых чисел, поэтому, чтобы противостоять методу грубой силы, мы должны p использовать q как можно больше простых чисел, которые имеют одинаковые порядки. Вот почему в практических приложениях используются ключи с несколькими сотнями бит (напомню: 64-битное число может иметь максимальное значение 18 446 744 073 709 551 615).

Как мы уже говорили, простых чисел бесконечно много. Самое большое известное и подтвержденное простое число по состоянию на 21 июня 2020 года — это число, состоящее из 22 338 618 цифр .

Формула для оценки количества простых чисел от 0 x до:

Ошибка для x = 50000составляет всего 0,6% и уменьшается только для больших значений.

Таким образом, существует около 4621 +/- 0,6% простых чисел до 50 000.

Словарь

простое число

натуральное число больше 1, имеющее только два делителя: 1 и само себя (например: 2, 3, 5, 7, 11)

составное число

Составные числа — это натуральные числа, имеющие более двух делителей. (пример: 6, 9, 12, 14)

криптограмма

зашифрованное сообщение

факторизация чисел

в противном случае простая факторизация