Slepý podpis

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 14. září 2021; kontroly vyžadují 3 úpravy .

Slepý podpis ( anglicky blind signature ) je typ digitálního podpisu , jehož zvláštností je, že podepisující strana nemůže přesně znát obsah podepsaného dokumentu. Koncept slepého podpisu vynalezl David Chaum [1] v roce 1982 a také navrhl první implementaci pomocí algoritmu RSA . Bezpečnost schématu slepého podpisu byla založena na obtížnosti faktorizace velkých složených čísel . Od té doby bylo navrženo velké množství dalších schémat [2] [3] .

Popis

Základní myšlenka slepých podpisů je následující:

Odesílatel A zašifruje dokument a odešle jej straně B.
Strana B, která nevidí obsah dokumentu, jej podepíše a vrátí zpět straně A.
Strana A odstraní svou šifru a na dokumentu ponechá pouze podpis strany B.

Na konci tohoto protokolu strana B neví nic o zprávě t, ani o podpisu pod touto zprávou.

Toto schéma lze přirovnat k obálce, ve které je umístěn dokument a list kopie. Pokud obálku podepíšete, podpis se otiskne na dokument a při otevření obálky bude dokument již podepsán.

Účelem slepého podpisu je zabránit podepisujícímu B, aby viděl zprávu A, kterou podepisuje, a odpovídající podpis pod touto zprávou. Proto nelze podepsanou zprávu dále přidružit k straně A.

Bezpečné schéma slepého podpisu musí splňovat 3 vlastnosti, a to:

Nulové znalosti . Tato vlastnost pomáhá uživateli získat podpis na dané zprávě, aniž by byla samotná zpráva vystavena podepisujícímu.
Sledovatelnost . Podepisovatel nemůže vysledovat pár podpis-zpráva poté, co uživatel zveřejnil podpis na své zprávě.
Nemožnost . Pouze podepisující osoba může vygenerovat platný podpis. Tato vlastnost je nejdůležitější a musí být splněna pro všechna podpisová schémata.

Vzhledem k vlastnostem nulové znalosti a nesledovatelnosti může být schéma slepého podpisu široce používáno v aplikacích, kde je vyžadována důvěrnost, například v systémech elektronického hlasování [4] [5] [6] [7] .

Algoritmy slepého podpisu

Zcela slepý podpis

Vzhledem k situaci: Bob je notář . Alice potřebuje, aby podepsal dokument, aniž by měl tušení o jeho obsahu. Bob pouze potvrzuje, že dokument je notářsky ověřen v určený čas. Potom jednají podle následujícího algoritmu:

V tomto schématu Alice chce, aby Bob slepě podepsal zprávu . Pro tohle: $m$

Alice zašifruje zprávu pomocí funkce a přijme zašifrovanou zprávu . $m$ $F$ $c=f(m)$
Alice pošle zašifrovanou zprávu Bobovi.
Bob naslepo (protože neví, co je uvnitř) podepíše zprávu funkcí , příjem . $C$ $G$ $c^{{'}}=g(c)=g(f(m))$
Bob posílá zpět Alici. $c^{{'}}$
Alice přijme a odstraní její šifrování a získá: . $c^{{'}}$ $c^{{''}}=g(f(m))*f^{{-1}}=g(m)$

Tento protokol funguje pouze tehdy, jsou-li funkce podepisování a šifrování komutativní .

Slepý podpis

Bob připraví n dokumentů, z nichž každý obsahuje nějaké jedinečné slovo (čím více n, tím menší šance, že Bob bude podvádět).
Bob zamaskuje každý dokument jedinečným maskovacím faktorem a pošle ho Alici.
Alice obdrží všechny dokumenty a náhodně vybere n-1 z nich.
Alice požádá Boba, aby poslal maskovací faktory pro vybrané dokumenty.
Bob to dělá.
Alice otevře n-1 dokumentů a ujistí se, že jsou správné.
Alice podepíše zbývající dokument a pošle ho Bobovi.
Bob má nyní dokument podepsaný Alicí jedinečným slovem, které Alice nezná.

Protokol RSA

První implementaci slepých podpisů provedl Chaum pomocí kryptosystému RSA:

Předpokládejme, že Bob má zpočátku veřejný klíč , kde je modul a veřejný exponent klíče. $(p,e)$ $p$ $E$

Alice vybere náhodný maskovací faktor relativně prvočíslo a vypočítá . $r$ $p$ $m^{{'}}\equiv mr^{{e}}{\bmod p}$
Alice pošle Bobovi otevřený kanál. $m^{{'}}$
Bob počítá pomocí svého soukromého klíče . $s^{{'}}\equiv (m^{{'}})^{{d}}{\bmod p}$ $(p, d)$
Bob posílá zpět Alici. $s^{{'}}$
Alice si sundá svůj původní převlek a obdrží původní zprávu podepsanou Bobem takto: . $m$ $s\equiv s^{{'}}*r^{{-1}}{\bmod p}\equiv m^{{d}}{\bmod p}$

Chaum přišel s celou rodinou složitějších algoritmů slepých podpisů, souhrnně nazývaných neočekávané slepé podpisy . Jejich schémata jsou ještě složitější, ale dávají více možností [1] .

Slepý podpis založený na Schnorr EDS

Nechť Alice chce podepsat zprávu od Boba tak, aby se Bob za prvé se zprávou při podepisování nemohl seznámit, a zadruhé, aby Bob následně po obdržení zprávy a odpovídajícího podpisu nemohl, identifikovat uživatele, který inicioval protokol slepého podpisu pro tuto konkrétní zprávu (Alice). Tento protokol je implementován následovně: $m$ $m$

Alice zahájí interakci s Bobem.
Bob pošle hodnotu Alici . $R=a^{k}\mod p$
Alice vypočítá hodnoty (w a t jsou náhodná čísla nepřesahující ) a poté odešle hodnotu Bobovi . $R^{{'}}=Ra^{{-w}}y^{{-t}}\mod y$ $y$ $E^{{'}}=H(m||R^{{'}})$ $E=E^{{'}}+t\mod y$ $E$
Bob vypočítá hodnotu takovou, že , a odešle ji Alici. $S$ $R=a^{S}y^{{E}}\mod p$ $S$
Alice vypočítá podpis , kde a , který je autentický vzhledem ke zprávě [8] . $(E^{{'}},S^{{'}})$ $E^{{'}}=E^{{-t}}\mod y$ $S^{{'}}=Sw\mod y$ $m$

Důkaz

Pravost podpisu se prokazuje následovně. Vyplývá to z a . V tomto případě je problém anonymity vyřešen, protože jakoukoli trojici z množiny takových trojic, které vytvořil Bob, lze porovnat s podpisem na tomto dokumentu . Skutečně máme: a , tj. s ekvipravděpodobným náhodným výběrem termínů a podpis byl generován se stejnou pravděpodobností z jakékoli trojice obsažené v množině trojic tvořených signatářem. Podotýkáme také, že Bob ani nemá možnost prokázat, že v době, kdy vznikal podpis tohoto dokumentu , s ním nebyl obeznámen. $R=a^{S}y^{{E}}\mod p$ $Ra^{{-w}}y^{{-t}}=a^{{Sw}}y^{{Et}}modp$ $R^{{'}}=a^{{S^{{'}}}}y^{{E^{{'}}}}\mod p$ $(R,S,E)$ $(E^{{'}},S^{{'}})$ $m$ $R=a^{S}y^{{E}}\mod p$ $R^{{'}}=a^{{S^{{'}}}}y^{{E^{{'}}}}\mod p$ $\Šipka doprava$ $R^{{'}}/R\equiv a^{{S^{{'}}-S}}y^{{E^{{'}}-E}}\mod p\equiv a^{{ -w}}y^{{-t}}\mod p$ $w$ $t$ $(E^{{'}},S^{{'}})$ $m$

Slepý podpis založený na GOST R 34.10-94 Možnosti

p je prvočíslo , 510 ≤ | p | ≤ 512 (nebo 1022 ≤ | p | ≤ 1024), kde |p| je kapacita binární reprezentace čísla p.

q je velký prvočíselník p-1, 255 ≤ | q | ≤ 256 (nebo 511 ≤ | q | ≤ 512)

α ≠ 1, α < p , mod p = 1. ${\displaystyle \alpha ^{q))$

Výpočet

Potřeba generovat náhodné k , 1 < k < q ;
R = ( mod p ) mod q je první část podpisu; ${\displaystyle \alpha ^{k))$
H = Hash(m) , kde Hash je hashovací funkce popsaná v normě GOST R 34.11-94 , m je zpráva, která má být podepsána;
S = kH + zR mod q , kde z je soukromý klíč .
Pokud S=0, opakujte operace 1-4.

Kontrola

0 < R < q nebo 0 < S < q. Pokud není splněna alespoň jedna z těchto dvou podmínek, pak je podpis neplatný. V opačném případě:
R' = ( mod p ) mod q , kde y je veřejný klíč ; $\alpha ^{R/H}y^{S/H}$
Pokud R = R' , pak je podpis platný [9] .

Slepý podpis založený na STB 1176.2-99

Běloruský standard poskytuje následující protokol pro generování slepého podpisu k dokumentu M :

Je nutné vygenerovat náhodné k takové, že 1 < k < q a vypočítat . Tyto akce provádí podepisující osoba. Poté předá číslo R uživateli; ${\displaystyle R=a^{k))$
Uživatel generuje náhodná čísla ε a τ taková, že 1 < ε, τ < q a poté vypočítá , a E = E' - τ mod q ; E - první prvek podpisu - je zaslán podepisujícímu; ${\displaystyle R'=R*y^{\tau }*a^{\epsilon ))$ $E'=F_{H}(R'||M)$
Signatář vypočítá druhý prvek podpisu S = (k - xE) mod q a pošle S uživateli;
Uživatel vypočítá S' = S + ε mod q .

V tomto popisu jsou použity následující parametry: q je modul použitý pro výpočty, jednoduchý; a je nadřazený prvek; x - soukromý klíč; y je veřejný klíč [9] .

Hromadný nevidomý podpis

Nechť jsou veřejné klíče vlastněné uživateli s . Nechť je zpráva M , kterou chce podepsat m z nich. V tomto případě lze všechny podpisy sloučit do jednoho, jehož délka se rovná délce podpisu jednoho uživatele a nezávisí na m . To se provádí podle pravidel následujícího 1 protokolu: ${\displaystyle {\overline {y_{1},y_{s))))$

Každý z m uživatelů vygeneruje náhodné číslo < p , kde j = , p je velké prvočíslo. Potom každý z m uživatelů vypočítá mod p ( k je velká prvočísla) a pošle toto číslo všem ostatním uživatelům z této skupiny. $t_{\alpha _{j))$ ${\overline {1,m))$ $R_{\alpha _{j}}=(t_{\alpha _{j}})^{k}$
Každý uživatel vypočítá mod p . Dále se vypočte e = f(R,M) = RH mod q , kde q je velké prvočíslo odlišné od p , H = Hash(M) je hašovací funkce. Číslo e bude prvním prvkem kolektivního podpisu. $R=\prod _{j=1}^{m}R_{\alpha _{j))$
$S_{\alpha _{j}}=x_{\alpha _{j}}^{e}t_{\alpha _{j}}$ mod p je podíl uživatele. Každý uživatel vypočítá tento podíl a poskytne jej ostatním.
Každý uživatel pak vypočítá mod p . Toto je druhý prvek kolektivního podpisu. $S=\prod _{j=1}^{m}S_{\alpha _{j))$

Ověření kolektivního slepého podpisu

$y=\prod _{j=1}^{m}y_{\alpha _{j))$ mod p je sdílený veřejný klíč. Na jeho základě se hromadný slepý podpis ověřuje podle následujícího algoritmu:

Mod p se vypočítá . ${\displaystyle R=S^{k}y^{-e))$
Vypočítejte e' = f(R,M) = RH mod q
Pokud e' = e , pak je podpis platný [9] .

Aplikace

Bankovní systémy

Protokol slepých podpisů našel nejširší uplatnění v oblasti digitálních peněz . Aby například vkladatel banku nepodvedl, lze použít následující protokol: vkladatel napíše stejnou nominální hodnotu bankovek na sto dokumentů s různými čísly a uloží je v zašifrované podobě do banky. Banka vybírá náhodně a požaduje otevření 99 (nebo n-1) obálek, ujišťuje se, že je všude napsáno 10 USD, a ne 1000 USD, a zbývající obálku naslepo podepíše, nevidí číslo účtu.

Může být poskytnuta jednodušší možnost: banka má svůj vlastní pár veřejných klíčů přiřazený ke každé nominální hodnotě směnky. Pod podpisem se pak posílá pouze číslo bankovky a není potřeba před podpisem kontrolovat nominální hodnotu [1] .

Tajné hlasování

Při tajném hlasování se používají slepé podpisy . V protokolu Fujioky, Okamota a Oty volič připraví hlasovací lístek se svou volbou, zašifruje jej tajným klíčem a zamaskuje. Dále volič podepíše hlasovací lístek a zašle jej validátorovi. Validátor ověří, že podpis patří registrovanému voliči, který ještě nehlasoval.

Pokud je hlasovací lístek platný, validátor lístek podepíše a vrátí jej voliči. Volič sejme převlek, čímž odhalí zašifrovaný hlasovací lístek podepsaný validátorem. Následně volič takto získaný podepsaný a zašifrovaný hlasovací lístek zašle přepážce, která zkontroluje podpis na zašifrovaném hlasovacím lístku.

Je-li hlasovací lístek platný, skrutátor jej zařadí na seznam, který se po skončení celého hlasování zveřejní. Po zveřejnění seznamu voliči zkontrolují, zda jsou jejich hlasovací lístky na seznamu, a zašlou sčítacímu komisaři dešifrovací klíče potřebné k otevření jejich hlasovacích lístků. Skrutátor používá tyto klíče k dešifrování hlasovacích lístků a přidává hlas k celkovému počtu. Po volbách skrutátor vydá dešifrovací klíče spolu se zašifrovanými hlasovacími lístky, aby si voliči mohli nezávisle ověřit volby [10] .

Zranitelnosti slepých podpisů

Algoritmus RSA může být objektem útoku, díky kterému je možné dešifrovat dříve naslepo podepsanou zprávu a vydávat ji za zprávu, která ještě nebyla podepsána. Na základě skutečnosti, že proces podepisování je ekvivalentní dešifrování podepisujícím (pomocí jeho soukromého klíče), může útočník podepsat již slepě podepsanou verzi zprávy zašifrovanou veřejným klíčem podepisujícího, tedy podepsat zprávu . $m$ $m'$

{\begin{aligned}m''&=m'r^{e}{\pmod n}\\&=(m^{e}{\pmod n}\cdot r^{e}){\pmod n }\\&=(pan)^{e}{\pmod n}\\\end{aligned}}

kde je zašifrovaná verze zprávy. Jakmile je zpráva podepsána, lze prostý text snadno získat: $m'$ $m$

{\begin{aligned}s'&=m''^{d}{\pmod n}\\&=((mr)^{e}{\pmod n})^{d}{\pmod n}\ \&=(mr)^{{ed}}{\pmod n}\\&=m\cdot r{\pmod n}{\mbox{, protože }}ed\equiv 1{\pmod {\phi (n )}}\\\end{aligned}}

kde je Eulerova funkce . Nyní lze zprávu snadno přijmout. $\phi(n)$

{\begin{aligned}m=s'\cdot r^{{-1}}{\pmod {n}}\end{aligned}}

Útok funguje, protože v tomto schématu podepisující přímo podepisuje samotnou zprávu. Naproti tomu v konvenčních podpisových schématech podepisující osoba typicky podepisuje například kryptografickou hashovací funkci . Kvůli této multiplikativní vlastnosti RSA by proto nikdy neměl být použit stejný klíč jak pro šifrování, tak pro slepé podepisování [8] .

Viz také

Poznámky

↑ 1 2 3 Bruce Schneier, Aplikovaná kryptografie. 2. vydání. Protokoly, algoritmy a zdrojové texty v jazyce C, nakladatelství Triumph, 2002
↑ Jean Kamenich, Jean-Marc Piveto, Markus Stadler, „Slepé podpisy založené na problému diskrétního logaritmu“, Eurocrypt, strany 428-432, Springer-Verlag, 1995.
↑ Qalian Chakrabortu, Jean Mehta, „Schéma razítkového slepého podpisu založené na problému diskrétního logaritmu eliptické křivky“, International Journal of Network Security, číslo 14, strany 316-319, 2012.
↑ Lung-Chang Lin, Ming-Shiang Hang, Chin-Chen Chang „Zlepšení zabezpečení pro anonymní elektronické hlasování přes web“, počítačové standardy a rozhraní, vydání 25, strany 131-139, 2003.
↑ Tatsuaki Okamoto, „Efektivní slepé a částečně slepé podpisy bez náhodných předpovědí“, Sbírka příspěvků „Teorie kryptografie“, strany 80-99, Springer-Verlag, 2006.
↑ Markus Ruckert, „Blind signature based on lattices“, sborník příspěvků z konference Asiacrypt, strany 413-430, Springer-Verlag, 2010.
↑ Daniel Ortiz-Arroyo, Claudia Garcia-Zamora, „Další vylepšení protokolu elektronického hlasování Mu-Varadarajan“, počítačové standardy a rozhraní, vydání 29, strany 471-480, 2007.
↑ 1 2 Moldovyan N.A. Workshop o kryptosystémech s veřejným klíčem. - 2007. - 304 s. — ISBN 5-9775-0024-6 .
↑ 1 2 3 N.A. moldavský. Teoretické minimum a algoritmy digitálního podpisu. - BVH-Petersburg, 2010. - 304 s. - ISBN 978-5-9775-0585-7 .
↑ Anisimov V.V. Protokoly dvou agentur Fujioka-Okamoto-Ohta a Sensus . Kryptografické metody ochrany informací . (neurčitý)

Literatura

Schneier, B. Aplikovaná kryptografie. 2. vydání. Protokoly, algoritmy a zdrojové texty v jazyce C - "Triumph", 2002
Klyuzhev A. Elektronické hlasování, 2003
Shangin, V. F. , Sokolov, A. V. Informační bezpečnost v distribuovaných podnikových sítích a systémech - "DMK", 2002
Chaum, D. Slepé podpisy pro nevysledovatelné platby - Springer-Verlnag, 1998
Moldovyan N. A. Workshop o kryptosystémech s veřejným klíčem, 2007
Moldovyan N. A. Teoretické minimum a základy digitálního podpisu, 2010