CEILIDH

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, «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)