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

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

Генерация ключей [ править ]

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

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

Шифрование [ править ]

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

Расшифровка [ править ]

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

Пример:

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

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

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

Безопасность [ править ]

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

Эффективность [ править ]

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

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

Ссылки [ править ]

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