Криптографическая система RSА

Продолжение серии "О математике и математиках"


Криптографическая система RSА   отнесена к классу асимметрично-ключевой криптографии.  Симметричная - и асимметрично ключевые криптографии существуют параллельно, и будут продолжать обслуживать общество. Они - дополняют друг друга; преимущества одной компенсируют недостатки другой.
Концептуальные отличия между этими двумя системами базируются на том, как эти системы сохраняют секретность. В криптографии с симметричными ключами,  задача секретности должна быть разделена между двумя людьми.
1. В асимметрично-ключевой криптографии, секретность персональная  задача (не разделяется между источником и получателем); человек-источник создает и сохраняет свою собственную тайну.
2. В сообществе n людей, при криптографии с симметричными ключами для сохранения секретности требуется n (n - 1)/2 общедоступных ключей. В криптографии с асимметричными ключами необходимы только n персональных ключей.  Общество с населением 1 миллион при криптографии с симметричными ключами требовало бы пятисот миллионов общедоступных ключей; асимметрично-ключевая криптография требовала бы 1 миллион персональных ключей.
3. Всякий раз, когда приложение базируется на персональной тайне, мы должны использовать асимметрично-ключевую криптографию.
4. Криптография с симметричными ключами базируется на подстановке и перестановке символов (символов или бит), асимметрично-ключевая криптография базируется на применении математических функций к числам.

5. В криптографии с симметричными ключами, исходный текст и зашифрованный текст представляют комбинацию символов. Шифрование и дешифрование представляет перестановку этих символов или замену одного символа другим. В асимметрично-ключевой криптографии, исходный текст и зашифрованный текст - числа; шифрование и дешифрование – это математические функции, которые применяются к числам, чтобы создать другие числа.

6. Асимметричная ключевая криптография использует два отдельных ключа: один частный (закрытый) и один публичный (открытый),  шифрование и дешифрование можно представить как процесс запирания и отпирания замков  ключами. В этом случае замок, запертый  открытым ключом доступа, можно отпереть только  соответствующим секретным ключом.
7. В отличие от в криптографии с симметричными ключами в асимметрично-ключевой криптографии, исходный текст и зашифрованный текст обрабатываются как целые числа. Сообщение должно перед шифрованием кодироваться как целое число  (или множество целых чисел). Сообщение после дешифрования должно быть расшифровано как целое число (или множество целых чисел). Асимметрично-ключевая криптография - обычно зашифровывает или расшифровывает маленькие части информации, определяемые длиной ключа шифра для асимметрично-ключевой криптографии.

RSА использует  два типа ключей – e и d, где e открытый, a  d – закрытый (секретный). Предположим, что P - исходный текст, и C - зашифрованный текст. чтобы создать зашифрованный текст C из исходного текста P используется
C =P^e mod n. Чтобы  извлечь (файл) переданный исходный текст,  используется P = C^d mod n,. Модулей n создается очень большое количество с помощью процесса генерации ключей, который мы обсудим позже.
При шифровании и дешифровании используют возведение в степень по модулю n. При использовании быстрого алгоритма возведения в степень по модулю n выполнимо в полиномиальное время. Так алгоритмов много и они доступны в сети Интернет. Однако, нахождения модульного логарифма, также сложно, как и  разложение  числа по модулю. Для него нет алгоритма с полиномиальным временем. Это означает, что можно зашифровать сообщение общедоступным ключом (e) в полиномиальное время.  Можно расшифровать зашифрованное сообщение в полиномиальное время (потому что он знает d). Но посторонний человек не может расшифровать это сообщение, потому что он должна была бы вычислить корень e - той степени из C  с использованием модульной арифметики.
Если когда-нибудь найдут, полиномиальный алгоритм для модуля вычисления корня e той степени из n, то возведение в степень по модулю n – не будет больше односторонней функцией.

Генерация ключей

Для того чтобы создать  открытый и секретный ключ, надо выполнить следующие действия. 
1. Выбрать два больших простых  p and q  таких, что  p   q.
2. Вычислить n=p x q.
3. Вычислить функцию Эйлера фи (n).
4. Выбрать число e, удовлетворяющее условиям 1<е<фи(n) и взаимно простое с фи(n).
5. Найти d=e^-1 mod фи(n) – (e в степени "-1" по моудулю m)инверсию e по модулю фи(n)

 После генерации ключей, владелец системы криптографии объявляет пару (e, n) как открытый ключ доступа: он сохраняет d  как свой секретный ключ.  Для  безопасности рекомендуется размер, для каждого простого p или q , 512 бит (почти 154 десятичные цифры). Это  определяет   размер модуля, n 1024 бита (309 цифр).

Шифрование

 Передать сообщение владельцу системы криптографии может любой, используя его открытый ключ доступа. Шифрование в  RSA может быть выполнено с использованием алгоритма с полиномиальной сложностью  по времени.
Для этого передаваемый текст должен быть представлен в числовой форме. И это число надо возвести в степень e. P^e mod n
Быстрых алгоритмов возведения в степень по модулю много  (алгоритмы быстрого возведения в степень по модулю приводятся в Интернет). Размер исходного текста должен быть меньше чем n, это означает,  что если размер исходного текста – больше, то он должен быть разделен на блоки. Дешифрование
Чтобы расшифровать сообщение зашифрованного текста, которое владелец секретного ключа получил в RSA, надо применить один из алгоритмов быстрого возведения в степень с полиномиальной сложностью  по времени,
P=C^d mod n
 Это определяется основными положениями  теоремы Эйлера, которая  обсуждалась выше. Процедура выбора ключей сделана так, что  шифрование, и дешифрование - инверсны друг другу
Если n = p х q, <n, и k - целое число, тогда a^k х фи(n)   a (modn).

Предположим, что исходный текст, восстановленный получателем текст, есть P1,
эквивалентен P .
Докажем это:
P1 =C^d mod n=(P^e mod n) mod n=P^ed mod n
ed= фи(n) +1
P1 = P^ed mod n
P^ed mod n =  P^фи(n) mod n= P mod n (e и d  инверсны по mod фи (n)).
Таким образом, при возведении зашифрованного текста  C в степень d мы получили исходный текст P.
Это одно из практических применений малой теоремы Ферма.

Продлжение следует