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

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

Название CEILIDH пришло от Гальско-Шотландского слова 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 достигает семантической безопасности.

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

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

• Torus-Based Cryptography — Общее представление о концепции (в PDF)
• http://en.wikipedia.org/wiki/CEILIDH#cite_note-cryptutor-0 - Английская страница в Wikipedia.