CEILIDH - CEILIDH

CEILIDH je veřejný klíč kryptosystém založeno na problém diskrétního logaritmu v algebraický torus. Tuto myšlenku poprvé představil Alice Silverberg a Karl Rubin v roce 2003; Silverberg pojmenovala CEILIDH po své kočce.^[1][2] Hlavní výhodou systému je zmenšená velikost klíčů pro stejné zabezpečení oproti základním schématům.^{[který? ]}

Algoritmy

Parametry

• Nechat ${ displaystyle q}$ být hlavní silou.
• An celé číslo ${ displaystyle n}$ je zvolen tak, aby:
  • Torus ${ displaystyle T_ {n}}$ má výslovnou racionální parametrizaci.
  • ${ displaystyle Phi _ {n} (q)}$ je dělitelný velkými prime ${ displaystyle l}$ kde ${ displaystyle Phi _ {n}}$ je ${ displaystyle n ^ {th}}$ Cyklomtomický polynom.
• Nechat ${ displaystyle m = phi (n)}$ kde ${ displaystyle phi}$ je Eulerova funkce.
• Nechat ${ displaystyle rho: T_ {n} ( mathbb {F} _ {q}) rightarrow { mathbb {F} _ {q}} ^ {m}}$ birational mapa a její inverzní ${ displaystyle psi}$.
• Vybrat ${ displaystyle alpha v T_ {n}}$ řádu ${ displaystyle l}$ a nechte ${ displaystyle g = rho ( alpha))}$.

Klíčové schéma dohody

Tento systém je založen na Klíčová dohoda Diffie-Hellman.

• Alice vybere náhodné číslo ${ displaystyle a { pmod { Phi _ {n} (q)}}}$.
• Ona počítá ${ displaystyle P_ {A} = rho ( psi (g) ^ {a}) v mathbb {F} _ {q} ^ {m}}$ a pošle to Bobovi.
• Bob si vybere náhodné číslo ${ displaystyle b { pmod { Phi _ {n} (q)}}}$.
• Vypočítává ${ displaystyle P_ {B} = rho ( psi (g) ^ {b}) v mathbb {F} _ {q} ^ {m}}$ a pošle to Alici.
• Alice počítá ${ displaystyle rho ( psi (P_ {B})) ^ {a}) v mathbb {F} _ {q} ^ {m}}$
• Bob počítá ${ displaystyle rho ( psi (P_ {A})) ^ {b}) v mathbb {F} _ {q} ^ {m}}$

${ displaystyle psi circ rho}$ je identita, tedy máme:${ displaystyle rho ( psi (P_ {B})) ^ {a}) = rho ( psi (P_ {A})) ^ {b}) = rho ( psi (g) ^ {ab })}$ což je sdílené tajemství Alice a Boba.

Šifrovací schéma

Toto schéma je založeno na Šifrování ElGamal.

• Generování klíčů
  • Alice vybere náhodné číslo ${ displaystyle a { pmod { Phi _ {n} (q)}}}$ jako její soukromý klíč.
  • Výsledný veřejný klíč je ${ displaystyle P_ {A} = rho ( psi (g) ^ {a}) v mathbb {F} _ {q} ^ {m}}$.
• Šifrování
  • Zpráva ${ displaystyle M}$ je prvek ${ displaystyle mathbb {F} _ {q} ^ {m}}$.
  • Bob vybere náhodné celé číslo ${ displaystyle k}$ v dosahu ${ displaystyle 1 leq k leq l-1}$.
  • Bob počítá ${ displaystyle gamma = rho ( psi (g) ^ {k}) v mathbb {F} _ {q} ^ {m}}$ a ${ displaystyle delta = rho ( psi (M) psi (P_ {A}) ^ {k}) v mathbb {F} _ {q} ^ {m}}$.
  • Bob pošle šifrovací text ${ displaystyle ( gamma, delta)}$ Alice.
• Dešifrování
  • Alice počítá ${ displaystyle M = rho ( psi ( delta) psi ( gamma) ^ {- a})}$.

Bezpečnostní

Schéma CEILIDH je založeno na schématu ElGamal a má tedy podobné vlastnosti zabezpečení.

Pokud výpočetní Diffie-Hellmanův předpoklad drží podkladovou cyklickou skupinu ${ displaystyle G}$, pak je funkce šifrování jednosměrný.^[3] Pokud rozhodný předpoklad Diffie-Hellman (DDH) drží ${ displaystyle G}$, pak dosáhne CEILIDH sémantická bezpečnost.^[3] Sémantická bezpečnost není implikována samotným výpočetním Diffie-Hellmanovým předpokladem.^[4] Vidět rozhodný předpoklad Diffie-Hellman pro diskusi o skupinách, kde se předpokládá, že předpoklad platí.

Šifrování CEILIDH je bezpodmínečné tvárný, a proto není pod zvolený útok šifrovaného textu. Například dané šifrování ${ displaystyle (c_ {1}, c_ {2})}$ nějaké (možná neznámé) zprávy ${ displaystyle m}$, lze snadno vytvořit platné šifrování ${ displaystyle (c_ {1}, 2c_ {2})}$ zprávy ${ displaystyle 2m}$.

Reference

• Rubin, K .; Silverberg, A. (2003). „Kryptografie založená na torusu“. V Boneh, D. (ed.). Pokroky v kryptologii - CRYPTO 2003. Přednášky z informatiky. 2729. Springer, Berlín, Heidelberg. str. 349–365. doi:10.1007/978-3-540-45146-4_21. ISBN  9783540406747.

externí odkazy

• Kryptografie založená na torusu: příspěvek představující koncept (v PDF z webové stránky univerzity Silverberg).