CEILIDH — криптосистема с открытым ключом, в основе которой лежат задачи дискретного логарифмирования и алгебраические группы. Впервые эта идея была предложена Алисой Силверберг и Карлом Рубин в 2003 году.
Главное преимущество схемы — уменьшенный размер ключей для обеспечения защиты.
В шотландском гэльском языке слово ceilidh (читается кейли) означает праздник, вечеринку, традиционные парные и групповые шотландские («пабные») танцы и музыку для этих танцев.
Алгоритмы
Параметры Пусть q — простая степень. Целое число n выбрано так, что:
Тор — T n имеет явную рациональную параметризацию. Φn(q) делится без остатка на большое простое число, где Φn — это циклический полином n-й степени.
Пусть m = Ф(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)
Категория:Криптография с открытым ключом