Криптосистема Шмидта-Самоа

редактировать

Криптосистема Шмидта-Самоа - это асимметричный криптографический метод, безопасность которого, как и Рабина, зависит от сложности целочисленной факторизации. В отличие от Рабина, этот алгоритм не создает двусмысленности в расшифровке за счет скорости шифрования.

Содержание

1 Генерация ключа
2 Шифрование
3 Расшифровка
4 Безопасность
5 Эффективность
6 Ссылки

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

Выберите два больших разных простых числа p и q и вычислить $N = p 2 q {\ displaystyle N = p ^ {2} q}$ $N = p ^ {2} q$
Compute $d = N - 1 mod lcm (p - 1, q - 1) {\ displaystyle d = N ^ {- 1} \ mod {\ text {lcm}} (p-1, q-1)}$ $d = N ^ {{- 1}} \ mod {\ text {lcm}} (p-1, q-1)$

Теперь N - открытый ключ, а d - закрытый ключ.

Шифрование

Чтобы зашифровать сообщение m, мы вычисляем зашифрованный текст как $c = m N mod N. {\ displaystyle c = m ^ {N} \ mod N.}$ $c = m ^ {N} \ mod N.$

Расшифровка

Чтобы расшифровать зашифрованный текст c, мы вычисляем открытый текст как $m = cd mod pq, {\ displaystyle m = c ^ {d} \ mod pq,}$ $m = c ^ {d} \ mod pq,$ который, как и для Рабина и RSA, может быть вычислен с помощью китайской теоремы об остатках.

Пример:

$p = 7, q = 11, N = p 2 q = 539, d = N - 1 mod lcm (p - 1, q - 1) = 29 {\ displaystyle p = 7, q = 11, N = p ^ {2} q = 539, d = N ^ {- 1} \ mod {\ text {lcm}} (p-1, q-1) = 29}$ $p = 7, q = 11, N = p ^ {2} q = 539, d = N ^ {{- 1}} \ mod {\ text {lcm}} (p-1, q-1) = 29$
$m = 32, c = m N mod N = 373 {\ displaystyle m = 32, c = m ^ {N} \ mod N = 373}$ $m = 32, c = m ^ {N} \ mod N = 373$

Теперь для проверки:

$m = cd mod pq = 373 29 mod pq = 373 29 mod 77 = 32 {\ displaystyle m = c ^ {d} \ mod pq = 373 ^ {29} \ mod pq = 373 ^ {29} \ mod 77 = 32}$ $m = c ^ {d} \ mod pq = 373 ^ {{29}} \ mod pq = 373 ^ {{29}} \ mod 77 = 32$

Безопасность

Алгоритм, как и у Рабина, основан на сложности факторизации модуль N, что является явным преимуществом перед RSA. То есть можно показать, что если существует алгоритм, который может дешифровать произвольные сообщения, то этот алгоритм можно использовать для множителя N.

Эффективность

Алгоритм обрабатывает дешифрование так же быстро, как Рабин. и RSA, однако он имеет гораздо более медленное шифрование, поскольку отправитель должен вычислить полное возведение в степень.

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

Ссылки

Новая перестановка лазейки типа Рабина, эквивалентная факторингу и его приложениям