PROFILPELAJAR.COM

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)