Schéma IBE kohoutů - Cocks IBE scheme

Schéma IBE kohoutů je šifrování založené na identitě systém navržený Clifford Cocks v roce 2001.^[1] Zabezpečení systému je založeno na tvrdosti systému kvadratický problém reziduaity.

Protokol

Založit

PKG volí:

1. veřejný modul RSA ${displaystyle extstyle n = pq}$, kde ${displaystyle extstyle p, q ,, pequiv qequiv 3 {mod {4}}}$ jsou hlavní a drženi v tajnosti,
2. zprávy a šifrovacího prostoru ${displaystyle extstyle {mathcal {M}} = vlevo {-1,1ight}, {mathcal {C}} = mathbb {Z} _ {n}}$ a
3. zabezpečená veřejná hash funkce ${displaystyle extstyle f: left {0,1ight} ^ {*} ightarrow mathbb {Z} _ {n}}$.

Výpis

Když uživatel ${displaystyle extstyle ID}$ chce získat svůj soukromý klíč, kontaktuje PKG prostřednictvím zabezpečeného kanálu. PKG

1. odvozuje se ${displaystyle extstyle a}$ s ${displaystyle extstyle left ({frac {a} {n}} ight) = 1}$ deterministickým procesem z ${displaystyle extstyle ID}$ (např. vícenásobné použití ${displaystyle extstyle f}$),
2. počítá ${displaystyle extstyle r = a ^ {(n + 5-p-q) / 8} {pmod {n}}}$ (který splňuje buď ${displaystyle extstyle r ^ {2} = a {pmod {n}}}$ nebo ${displaystyle extstyle r ^ {2} = - a {pmod {n}}}$, viz níže) a
3. vysílá ${displaystyle extstyle r}$ uživateli.

Šifrovat

Trochu zašifrovat (kódováno jako ${displaystyle extstyle 1}$/${displaystyle extstyle -1}$) ${displaystyle extstyle min {mathcal {M}}}$ pro ${displaystyle extstyle ID}$, uživatel

1. vybere náhodně ${displaystyle extstyle t_ {1}}$ s ${displaystyle extstyle m = left ({frac {t_ {1}} {n}} ight)}$,
2. vybere náhodně ${displaystyle extstyle t_ {2}}$ s ${displaystyle extstyle m = left ({frac {t_ {2}} {n}} vpravo)}$, odlišný od ${displaystyle extstyle t_ {1}}$,
3. počítá ${displaystyle extstyle c_ {1} = t_ {1} + at_ {1} ^ {- 1} {pmod {n}}}$ a ${displaystyle c_ {2} = t_ {2} -at_ {2} ^ {- 1} {pmod {n}}}$ a
4. posílá ${displaystyle extstyle s = (c_ {1}, c_ {2})}$ uživateli.

Dešifrovat

K dešifrování šifrovacího textu ${displaystyle s = (c_ {1}, c_ {2})}$ pro uživatele ${displaystyle ID}$, on

1. počítá ${displaystyle alpha = c_ {1} + 2r}$ -li ${displaystyle r ^ {2} = a}$ nebo ${displaystyle alpha = c_ {2} + 2r}$ jinak a
2. počítá ${displaystyle m = left ({frac {alpha} {n}} vpravo)}$.

Všimněte si, že zde předpokládáme, že šifrovací entita neví, zda ${displaystyle ID}$ má odmocnina ${displaystyle r}$ z ${displaystyle a}$ nebo ${displaystyle -a}$. V tomto případě musíme poslat šifrovací text pro oba případy. Jakmile jsou tyto informace šifrovací entitě známy, je třeba odeslat pouze jeden prvek.

Správnost

Nejprve si povšimněte, že od té doby ${displaystyle extstyle pequiv qequiv 3 {pmod {4}}}$ (tj. ${displaystyle left ({frac {-1} {p}} ight) = left ({frac {-1} {q}} ight) = - 1}$) a ${displaystyle extstyle left ({frac {a} {n}} ight) Rightarrow left ({frac {a} {p}} ight) = left ({frac {a} {q}} ight)}$, buď ${displaystyle extstyle a}$ nebo ${displaystyle extstyle -a}$ je kvadratický zbytek modulo ${displaystyle extstyle n}$.

Proto, ${displaystyle extstyle r}$ je druhá odmocnina z ${displaystyle extstyle a}$ nebo ${displaystyle extstyle -a}$:

${displaystyle {egin {aligned} r ^ {2} & = left (a ^ {(n + 5-pq) / 8} ight) ^ {2} & = left (a ^ {(n + 5-pq- Phi (n)) / 8} ight) ^ {2} & = left (a ^ {(n + 5-pq- (p-1) (q-1)) / 8} ight) ^ {2} & = left (a ^ {(n + 5-pq-n + p + q-1) / 8} ight) ^ {2} & = left (a ^ {4/8} ight) ^ {2} & = pm aend {zarovnáno}}}$

Navíc (pro případ, že ${displaystyle extstyle a}$ je kvadratický zbytek, platí stejná myšlenka ${displaystyle extstyle -a}$):

${displaystyle {egin {aligned} left ({frac {s + 2r} {n}} ight) & = left ({frac {t + at ^ {- 1} + 2r} {n}} ight) = left ({ frac {tleft (1 + at ^ {- 2} + 2rt ^ {- 1} ight)} {n}} ight) & = left ({frac {tleft (1 + r ^ {2} t ^ {- 2 } + 2rt ^ {- 1} ight)} {n}} ight) = left ({frac {tleft (1 + rt ^ {- 1} ight) ^ {2}} {n}} ight) & = left ({frac {t} {n}} ight) left ({frac {1 + rt ^ {- 1}} {n}} ight) ^ {2} = left ({frac {t} {n}} ight) (pm 1) ^ {2} = vlevo ({frac {t} {n}} vpravo) konec {zarovnáno}}}$

Bezpečnostní

Lze prokázat, že prolomení schématu je ekvivalentní řešení problému kvadratické reziduozity, o kterém se předpokládá, že je velmi tvrdý. Společná pravidla pro výběr a Modul RSA blokování: Použijte zabezpečený ${displaystyle extstyle n}$, vybrat si z ${displaystyle extstyle t}$ jednotné a náhodné a navíc obsahují některé kontroly pravosti ${displaystyle extstyle t}$ (jinak an adaptivně zvolený útok šifrovaného textu lze připojit změnou paketů, které přenášejí jeden bit, a použitím věštec sledovat účinek na dešifrovaný bit).

Problémy

Hlavní nevýhodou tohoto schématu je, že může šifrovat zprávy pouze bit na bit - proto je vhodný pouze pro malé datové pakety, jako je klíč relace. Pro ilustraci zvažte 128bitový klíč, který se přenáší pomocí 1024bitového modulu. Poté je třeba odeslat 2 × 128 × 1024 bitů = 32 kByte (pokud není známo, zda ${displaystyle r}$ je čtverec A nebo -A), což je přijatelné pouze pro prostředí, ve kterých se klíče relace mění jen zřídka.

Toto schéma nezachovává soukromí klíčů, tj. Pasivní protivník může získat smysluplné informace o totožnosti příjemce při sledování šifrovacího textu.

Reference