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 достигает семантической безопасности.

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

Ссылки

  • CRYPTUTOR, «Elgamal encryption scheme»
  • 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
  • Torus-Based Cryptography — Общее представление о концепции (в PDF)