№10 - Шифрование с открытым ключем. Криптосистема RSA

Пусть функция $f : A \to B$ и выполнены следующие условия:
1. Вычисление значения $b = f(a)$ для любого а из $А$ – выполняется достаточно просто
2. Нахождение значения $а$ при $b = f(a)$ достаточно трудная задача
3. $f$ – биекция

Тогда $f$ называется односторонней функцией

Для системы шифрования с открытым ключом необходимо выполнение ещё одного свойства (условия)

1. Существует такой секрет  при знании которого нахождение a из уравнения $f(a) = b$ становится достаточно простой задачей

Функцию удовлетворяющую условиям 1-4 называют односторонней функцией с секретом

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

Криптосистема RSA

1. Вначале выбирается два достаточно больших простых числа $p$ и $q$ и вычисляется модуль $n = p * q$. Числа $p$ и $q$ сверхсекретно, модуль $n$ – открытое.
2. Далее вычисляется функция Эйлера $f(n) = (p-1)(q-1)$, выбирается число е такое, что $\text{НОД} (е, f(n)) = 1$.

3. Параметр е служит открытым ключом шифрования. Значение  $f(n)$ держится в секрете. Из того что $\text{НОД}(e, f(n)) = 1$, можно однозначно вычислить число $d$, такое, что
   $$e * d = 1 (\text{mod } f(n)) (1 <= d <= f(n))$$
   То есть $d$ – открытый элемент к $е$ в группе $Z*f(n)$ значение $d$ является секретным ключом дешифрования.

4. В качестве платформы для единиц исходного текста выберет $Z_{n}$. Единицами шифрованного текста также будут элементы $Z_{n}$.

Единицы шифротекста (обозначаем обычно $C$) получается из единиц исходного текста m по следующему правилу: 
$С=me(\text{mod } n)$
$C$ записывается стандартным именем, т.е. $0\leq c\leq n-1$

1. Дешифрование производится следующим образом: 
   $m=(me)d(\text{mod } n)$
   Пусть $\text{НОД }(m,n)=1$. Тогда $m\in Z_{n}^{*}$, и $|Z_{n}^{*}|=(n)$. По теореме Эйлера $m^{\phi(n)}=1$. Равенство
   $$ed=1(\text{mod } (\phi(n))) \iff \exists kZ:ed=1+(n)k$$ Вычисляем:
   $$c^{d}=(m^{e})^{d}=m^{ed}=nm^{\phi(n)k}=$$
   $$=m(m^{\phi(n)^k})=m*1^k=m(\text{mod } n)$$

$\text{НОД }(m,n)=1$ является необходимым условием при RSA во многих книгах, но утверждается, что $m=m^{ed}(\text{mod } n) \forall m$