Криптосистема Шмидт-Самоа является асимметричной криптографической техникой, безопасность которых, как Рабин , зависит от сложности целочисленной факторизации . В отличие от Рабина, этот алгоритм не создает двусмысленности в расшифровке за счет скорости шифрования.
Генерация ключей
- Выберите два больших различных простых числа p и q и вычислите
- Вычислить
Теперь N - открытый ключ, а d - закрытый ключ.
Шифрование
Чтобы зашифровать сообщение m, мы вычисляем зашифрованный текст как
Расшифровка
Чтобы расшифровать зашифрованный текст c, мы вычисляем открытый текст каккоторые, как и для Рабина и RSA, могут быть вычислены с помощью китайской теоремы об остатках .
Пример:
Теперь для проверки:
Безопасность
Алгоритм, как и у Рабина, основан на сложности факторизации модуля N , что является явным преимуществом перед RSA. То есть, можно показать , что если существует алгоритм , который может расшифровать произвольные сообщения, то этот алгоритм может быть использован для коэффициента N .
Эффективность
Алгоритм обрабатывает дешифрование так же быстро, как Rabin и RSA, однако он имеет гораздо более медленное шифрование, поскольку отправитель должен вычислить полное возведение в степень.
Поскольку в шифровании используется фиксированный известный показатель степени, для оптимизации процесса шифрования можно использовать цепочку сложения . Стоимость создания оптимальной цепочки сложения может быть амортизирована в течение срока действия открытого ключа, то есть ее нужно вычислить только один раз и кэшировать.