CEILIDH

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

Главное преимущество схемы - уменьшенный размер ключей для обеспечения защиты.

В шотландском гэльском языке слово ceilidh (читается кейли) означает праздник, вечеринку, традиционные парные и групповые шотландские ("пабные") танцы и музыку для этих танцев.


Алгоритмы

Параметры

  • Пусть q - простая степень.
  • Тор - T n имеет явную рациональную параметризацию.
  • Φn(q) делится без остатка на большое простое число, где Φn - это циклический полином n-й степени.
  • Пусть ρ: Tn(Fq) → Fqm - это бирациональное отображение, а ψ - его инверсия.
  • Выбираем α є Tn, степени l и задаем q=ρ(α).

Схемы согласования ключей

Эта схема основывается на алгоритме Диффи-Хелмана.

  • Алиса выбирает случайное число - a (mod Фn(q)).
  • Она вычисляет ΡА = ρ( ψ(g)a ) є Fqm и отправляет результат Бобу.
  • Боб выбирает случайное число - b (mod Фn(q)).
  • Он вычисляет ΡВ = ρ( ψ(g)b ) є Fqm и отправляет результат Алисе.
  • Алиса вычисляет ρ( ψ( ΡВ )a ) є Fqm
  • Боб вычисляет ρ( ψ( ΡА )b ) є Fqm

Схемы шифрования

В основе данной лежит схема шифрования Эль Гамаля.

  • Генерация ключа
  • Алиса выбирает случайное число - a (mod Фn(q)) - как свой секретный ключ.
  • В результате вычислений - ΡА = ρ(ψ(g)a) є Fqm - получаем открытый ключ.
  • Шифрование
  • Сообщение М - элемент Fqm.
  • Боб выбирает случайное целое число k в диапазоне 1 ≤ k ≤ l - 1
  • Боб вычисляет γ = ρ(ψ(g)k) є Fqm и δ = ρ(ψ(M)ψ(ΡА)k) є Fqm .
  • Боб отправляет зашифрованный текст (γ,δ) Алисе.
  • Де шифрование
  • Алиса вычисляет М = ρ ( ψ(δ) ψ(γ) )

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

Схема CEILIDH основывается на схеме Эль - Гамаля и, как следствие, обладает схожими свойствами.

Если вычислительное предположение Диффи - Хеллмана включает в себя базисную циклическую группу - G, то функция шифрования является односторонней. Если вычислительное предположение Диффи - Хеллмана не включает G, тогда криптосистема CEILIDH достигает семантической безопасности.

Шифрование CILIDH - обладает предрасположенностью к выборочным атакам на зашифрованный текст. Это значит, что существует возможность для постороннего лица, например, преобразовать зашифрованный текст (с1,с2) сообщения m в иной текст - (с1, 2с2) сообщения 2m.

Ссылки

  1. CRYPTUTOR, "Elgamal encryption scheme"
  2. M. Abdalla, M. Bellare, P. Rogaway, "DHAES, An encryption scheme based on the Diffie-Hellman Problem" (Appendix A)
  • Karl Rubin, Alice Silverberg: Torus-Based Cryptography. CRYPTO 2003: 349–365

Внешние ссылки