Оптимальное асимметричное шифрование с дополнением

1. Сообщению ${\displaystyle m}$ дописывается ${\displaystyle k_{1}}$ нулей, благодаря чему оно достигает ${\displaystyle n-k_{0}}$ бит в длину.
2. Генерируется случайная ${\displaystyle k_{0}}$-битная строка ${\displaystyle r}$.
3. ${\displaystyle G}$ расширяет ${\displaystyle k_{0}}$ бит строки ${\displaystyle r}$ до ${\displaystyle n-k_{0}}$ бит.
4. ${\displaystyle X=m00..0\bigoplus G(r)}$.
5. ${\displaystyle H}$ ужимает ${\displaystyle n-k_{0}}$ бит ${\displaystyle X}$ до ${\displaystyle k_{0}}$ бит.
6. ${\displaystyle Y=r\bigoplus H(X)}$.
7. Зашифрованный текст ${\displaystyle X||Y}$.

1. Восстанавливается случайная строка ${\displaystyle r=Y\bigoplus H(X)}$
2. Восстанавливается исходное сообщение как ${\displaystyle m00..0=X\bigoplus G(r)}$
3. Последние ${\displaystyle k_{1}}$ символов расшифрованного сообщения проверяются на равенство нулю. Если имеются ненулевые символы, то сообщение подделано злоумышленником.

Виктор Шоуп предложил свой вариант схемы дополнения на основе OAEP (называемый OAEP+), который является устойчивым к атакам с адаптивно подобранным шифротекстом в случае комбинирования с любой односторонней функцией с потайным входом[2].

• ${\displaystyle n}$ — число бит в подготавливаемом для асимметричного шифрования блоке.
• ${\displaystyle k_{0}}$ и ${\displaystyle k_{1}}$ — фиксированные протоколом целые числа.
• ${\displaystyle m}$ открытый текст сообщения, ${\displaystyle n-k_{0}-k_{1}}$-битная строка.
• ${\displaystyle G}$, ${\displaystyle H}$ и ${\displaystyle H'}$ — криптографические хеш-функции, заданные протоколом.

1. Генерируется случайная ${\displaystyle k_{0}}$-битная строка ${\displaystyle r}$.
2. ${\displaystyle H'}$ преобразует ${\displaystyle r||m}$ в строку длины ${\displaystyle k_{1}}$.
3. ${\displaystyle G}$ преобразует ${\displaystyle r}$ в строку длины ${\displaystyle n-k_{0}-k_{1}}$.
4. Составляется левая часть сообщения ${\displaystyle X=(G(r)\bigoplus m)||H'(r||m)}$.
5. ${\displaystyle H}$ преобразует ${\displaystyle X}$ в строку длины ${\displaystyle k_{0}}$.
6. Составляется правая часть сообщения ${\displaystyle Y=H(X)\bigoplus r}$.
7. Зашифрованный текст ${\displaystyle X||Y}$.

1. Восстанавливается случайная строка ${\displaystyle r=Y\bigoplus H(X)}$.
2. ${\displaystyle X}$ разбивается на две части ${\displaystyle X_{1}}$ и ${\displaystyle X_{2}}$, размерами ${\displaystyle n-k_{1}-k_{0}}$ и ${\displaystyle k_{1}}$ бит соответственно.
3. Восстанавливается исходное сообщение как ${\displaystyle m=G(r)\bigoplus X_{1}}$.
4. Если не выполняется ${\displaystyle H'(r||m)=X_{2}}$, то сообщение подделано.

Дэн Боне предложил две упрощённые реализации OAEP, названные SAEP и SAEP+ соответственно. Основная идея упрощения шифрования заключается в отсутствии последнего шага — сообщение «склеивалось» с изначально сгенерированной случайной строкой ${\displaystyle r}$. Таким образом, схемы состоят только из одной ячейки Фейстеля, благодаря чему достигается прирост к скорости работы[7]. Отличием алгоритмов друг от друга выражается в записи проверяющих битов. В случае SAEP это нули, в то время как для SAEP+ — это хеш от ${\displaystyle m||r}$ (соответственно как у OAEP и OAEP+)[5]. Недостатком алгоритмов является сильное уменьшение длины сообщения. Надёжность схем в случае использования функции Рабина и RSA была доказана только при следующем ограничении на длину передаваемого текста: ${\displaystyle m\leqslant n/2+k_{0}}$ для SAEP+ и дополнительно ${\displaystyle m\leqslant n/4}$ для SAEP[8]. Стоит отметить, что при примерно одинаковой скорости работы, SAEP+ имеет меньше ограничений на длину сообщения чем SAEP[8], благодаря чему признан более предпочтительным[8].

В схеме используются следующие обозначения:

• ${\displaystyle n}$ — число бит в блоке RSA или криптосистемы Рабина.
• ${\displaystyle k_{0}}$ и ${\displaystyle k_{1}}$ — фиксированные протоколом целые числа.
• ${\displaystyle m}$ открытый текст сообщения, ${\displaystyle n-k_{0}-k_{1}}$-битная строка.
• ${\displaystyle G}$ и ${\displaystyle H}$ — криптографические хеш-функции, заданные протоколом.

1. Генерируется случайная ${\displaystyle k_{0}}$-битная строка ${\displaystyle r}$.
2. ${\displaystyle G}$ преобразует ${\displaystyle m||r}$ в строку длины ${\displaystyle k_{1}}$.
3. ${\displaystyle H}$ преобразует ${\displaystyle r}$ в строку длины ${\displaystyle n-k_{0}}$.
4. Вычисляется ${\displaystyle X=(m||G(m||r))\bigoplus H(r)}$.
5. Зашифрованный текст ${\displaystyle X||r}$.

1. Вычисляется ${\displaystyle X_{1}||X_{2}=X\bigoplus H(r)}$, где ${\displaystyle X_{1}}$ и ${\displaystyle X_{2}}$ — строки размерами ${\displaystyle n-k_{0}-k_{1}}$ и ${\displaystyle k_{0}}$ соответственно.
2. Проверяется равенство ${\displaystyle X_{2}=G(X_{1}||r)}$. Если равенство выполняется, то исходное сообщение ${\displaystyle X_{1}}$, если нет — то сообщение подделано злоумышленником.