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

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

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

Алгоритмы

Параметры

• Пусть q — простая степень.

• Целое число n выбрано так, что:

• Тор — T _n имеет явную рациональную параметризацию.
• Φ _n (q) делится без остатка на большое простое число , где Φ n — это циклический полином n-й степени.

• Пусть m = Ф(n), где Ф- функция Эйлера .

• Пусть ρ: Tn(F _q ) → F _q ^m — это бирациональное отображение, а ψ — его инверсия.

• Выбираем α є Tn, степени l и задаем q=ρ(α).

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

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

• Алиса выбирает случайное число — a (mod Ф _n (q)).

• Она вычисляет Ρ _А = ρ(ψ(g) ^a ) є F _q ^m и отправляет результат Бобу.

• Боб выбирает случайное число — b (mod Ф _n (q)).

• Он вычисляет Ρ _В = ρ(ψ(g) ^b ) є F _q ^m и отправляет результат Алисе.

• Алиса вычисляет ρ(ψ(Ρ _В ) ^a ) є F _q ^m

• Боб вычисляет ρ(ψ(Ρ _А ) ^b ) є F _q ^m

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

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

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

• Алиса выбирает случайное число — a (mod Ф _n (q)) — как свой секретный ключ.
• В результате вычислений — Ρ _А = ρ(ψ(g) ^a ) є F _q ^m — получаем открытый ключ.

• Шифрование

• Сообщение М — элемент F _q ^m .

• Боб выбирает случайное целое число k в диапазоне 1 ≤ k ≤ l — 1

• Боб вычисляет γ = ρ(ψ(g) ^k ) є F _q ^m и δ = ρ(ψ(M)ψ(Ρ _А ) ^k ) є F _q ^m .

• Боб отправляет зашифрованный текст (γ,δ) Алисе.

• Де шифрование

• Алиса вычисляет М = ρ (ψ(δ) ψ(γ) ^-а )

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

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

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

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

Ссылки

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