Vícenásobný podpis

Vícenásobný (kolektivní) podpis ( anglicky Aggregate signature ) - schéma (protokol) pro implementaci elektronického podpisu (EDS), který umožňuje více uživatelům podepsat jeden dokument.

Hromadný podpis poskytuje možnost současného podepisování elektronického dokumentu, protože je vytvořen jako výsledek jediné nedělitelné transformace a nelze jej rozdělit na jednotlivé podpisy; navíc jej nelze rozšířit, to znamená, že do něj lze vložit dodatečný podpis jedné nebo více osob [1] .

Úvod

Pojem "kolektivní podpis" je v souladu s pojmem " skupinový podpis ", ale tyto pojmy se liší. Protokol digitálního podpisu skupiny řeší problém umožňující libovolnému uživateli z určité skupiny vytvořit podpis jménem celé skupiny. Skupinový protokol EDS také upravuje přítomnost konkrétních osob, které mohou určit seznam osob, které vytvořily podpis (tyto mají tedy hypotetickou možnost podepsat se za některého z členů skupiny). V případě hromadné práce s elektronickými dokumenty je nutné, aby je mohlo podepsat mnoho uživatelů [2] . Varianta schématu s generováním sady individuálních EDS uživatelů podepisujících jeden elektronický dokument má několik výrazných nevýhod - lineární nárůst velikosti kolektivního EDS (CEDS) s nárůstem počtu podepisujících, stejně jako nutnost dodatečných kontrol neporušenosti a úplnosti hromadného digitálního podpisu, aby se vyloučila možnost nahrazování číselného a jmenného složení účastníků, kteří dokument podepsali [1] .

Koncept sdíleného veřejného klíče

Na základě veřejných klíčů účastníků je generován hromadný veřejný klíč, který umožňuje vyvinout a ověřit pravost hromadného elektronického digitálního podpisu. Sdílený veřejný klíč podléhá řadě omezení velikosti, integrity, nezávislosti na uživatelích, současného generování sdíleného veřejného klíče a kontinuity. Jinými slovy, nelze z CECP vypočítat platný CECP pro jakoukoli jinou množinu účastníků z množiny aktuálních, CECP není vázán na složení účastníků - libovolní uživatelé mohou vytvořit skupinu a vyvinout si vlastní CECP. Kolektivní veřejný klíč, funkce veřejných klíčů uživatelů, je základem, na kterém je postaven celý protokol kolektivního podpisu [3] .

QECP je vyvíjen v souladu s výše uvedenými požadavky pomocí algoritmů, jejichž stabilita je zajištěna následujícími výpočetně náročnými problémy: diskrétní logaritmus v multiplikativní skupině velkého prvočíselného řádu , extrakce kořenů velkého prvočísla modulo a velké prvočíslo, diskrétní logaritmus v skupina bodů eliptické křivky zvláštního tvaru [3] .

Implementace protokolů založených na standardech EDS

Norma EDS - GOST R 34.10−94

Podle normy GOST R 34.10−94 [4] se na použité prvočíslo p vztahují omezení. Kapacita prvočísla p v binární reprezentaci: bit nebo bit. Číslo musí obsahovat velkého prvočísla , například pro nebo pro . Pro generování a ověřování EDS se používá takové číslo, že kde je generátor podskupiny dostatečně velkého prvočísla . $510\leq |p|\leq 512$ $1022\leq |p|\leq 1024$ $(p-1)$ $q$ $2^{255}\leq q\leq 2^{256}$ $510\leq |p|\leq 512$ $2^{511}\leq q\leq 2^{512}$ $1022\leq |p|\leq 1024$ $\alpha \neq 1$ $\alpha ^{q}{\bmod {p}}=1$ $\alpha$ $q$

Výpočtový algoritmus EDS 1. Vygeneruje se náhodné číslo .

k,1<k<q

2. Vypočítá se hodnota , což je první část podpisu.

R=(\alpha ^{k}{\bmod {p}}){\bmod {q}}

3. Podle GOST R 34.11–94 se hashovací funkce vypočítává z podepisované zprávy.

H

4. Vypočítá se druhá část podpisu: , kde je tajný klíč. Pokud , postup generování podpisu se opakuje.

S=kH+zR{\bmod {q))

z

S=0

Autentizační algoritmus EDS 1. Ověřuje se splnění podmínek a . Pokud podmínky nejsou splněny, pak podpis není platný.

r<q

s<q

2. Hodnota se vypočítá

R'=(\alpha ^{S/H}y^{-R/H}{\bmod {p))){\bmod {q}}

, kde je veřejný klíč uživatele, který vygeneroval podpis, který má být ověřen.

y

3. Hodnoty a jsou porovnány . Pokud , pak je podpis platný

R

R'

R=R'

Implementace protokolu CECP

Každý uživatel vygeneruje veřejný klíč ve tvaru , kde je soukromý (tajný) klíč, = , , … , . $i$ $y_{i}=\alpha ^{z_{i}}{\bmod {p}}$ $z_{i}$ $i$ $jeden$ $2$ $m$

Společný veřejný klíč je produktem

y=y_{1}y_{2}y_{3}...y_{m}{\bmod {p)).

Každý uživatel si vybere náhodný tajný klíč , číslo, které se použije pouze jednou. $k_i$

Vypočteno

R_{i}=\left(\alpha ^{k_{i}}{\bmod {p}}\right){\bmod {q}}

R=R_{1}R_{2}R_{3}...R_{m}{\bmod {q))

R_i

je k dispozici všem členům týmu, kteří vyvíjejí CECP

Poté každý z členů týmu, který vyvíjí KECP, podle jím určené hodnoty a výsledku počítá $R_i$ $H$

S_{i}=k_{i}H+z_{i}R{\bmod {q))

S_{i}

- část podpisu.

Kolektivní podpis bude dvojice hodnot , kde je součet všech modulo [3] . $(S,R)$ $S$ $S_{i}$ $q$

Ověření hromadného elektronického digitálního podpisu

Ověření kolektivního podpisu se provádí podle vzorce

R'=\left(\alpha ^{S/H}y^{-R/H}{\bmod {p}}\right){\bmod {q}}

Pokud , pak je CEC množiny uživatelů pravý, protože mohl být vytvořen pouze za účasti každého uživatele z této skupiny, protože jeho vytvoření vyžaduje použití tajného klíče každého z nich. Všimněte si, že hodnoty se ověřují automaticky při ověřování kolektivního digitálního podpisu. Pokud se narušitel pokusí nahradit kteroukoli z těchto hodnot nebo je nahradit dříve používanými hodnotami, pak bude při ověřování digitálního podpisu okamžitě zjištěna skutečnost narušení protokolu , tj . Je zřejmé, že velikost QECP nezávisí na [3] . $R=R'$ $m$ $R_i$ $R'\neq R$ $m$

Důkaz správnosti navrženého algoritmu CECP

Získanou signaturu dosaďte do rovnice — dvojice (R,S), kde R je součin R i modulo q, S je součet S i modulo q : rovnice , regulované normou EDS GOST R 34.10-94. $R=\left(\alpha ^{S/H}y^{-R/H}{\bmod {p}}\right){\bmod {q}}$ $R=\left[\alpha ^{\displaystyle \sum _{i=1}^{m}S_{i}/H}\left(\prod _{i=1}^{m}y_{ i}\right)^{-R/H}{\bmod {p}}\right]{\bmod {q}}=$ $\left(\prod _{i=1}^{m}\alpha ^{\displaystyle S_{i}/H}\prod _{i=1}^{m}y_{i}^{\ styl zobrazení -R/H}{\bmod {p}}\right){\bmod {q}}=$ $\left[\prod _{i=1}^{m}\left(\alpha ^{\displaystyle S_{i}/H}\alpha ^{\displaystyle -z_{i}R/H}{ \bmod {p}}\right)\right]{\bmod {q}}=$ $\left[\prod _{i=1}^{m}\left(\alpha ^{\displaystyle (k_{i}-z_{i}R)/H}\alpha ^{\displaystyle z_{ i}R/H}{\bmod {p}}\right)\right]{\bmod {q}}=$ $\left(\prod _{i=1}^{m}\alpha ^{\displaystyle k_{i}}{\bmod {p}}\right){\bmod {q}}=$ $\left[\prod _{i=1}^{m}\left(\alpha ^{\displaystyle k_{i}}{\bmod {p}}\right){\bmod {q}}\ vpravo]{\bmod {q}}=$ $\left(\prod _{i=1}^{m}{\displaystyle R_{i}}\right){\bmod {q}}$ $R=\left(\alpha ^{S/H}y^{-R/H}{\bmod {p}}\right){\bmod {q}}$

Možnost padělání CECP

Je zřejmé, že pro narušitele je složitost padělání CECP určena složitostí padělání individuálního podpisu jednotlivého člena skupiny. Příležitosti se otevírají uživatelům, kteří spojí své úsilí a vytvoří CECP související s kolektivem, který kromě nich zahrnuje jednoho nebo více dalších uživatelů, kteří o tom nejsou informováni (důkaz pro oba případy je podobný). Nechť uživatelé m-1 chtějí vytvořit QEDP ověřitelný sdíleným veřejným klíčem , kde uživatelé spojí své úsilí k vytvoření dvojice čísel tak, aby . To znamená, že mohou zfalšovat podpis veřejného klíče , to znamená vypočítat hodnoty, které splňují rovnici . To implikuje možnost padělání digitálního podpisu v základním schématu EDS, protože má náhodnou hodnotu [3] . $y=y'y_{m}{\bmod {p))$ $y'=\prod _{i=1}^{m-1}y_{i}{\bmod {p}}$ $m-1$ $\left(R,S\right)$ $R=\left(\alpha ^{S/H}\left(y'y_{m}\right)^{-R/H}{\bmod {p}}\right){\bmod {q }}$ $y^{*}=y'y_{m}{\bmod {p))$ $R$ $S$ $R=\left(\alpha ^{S/H}\left(y^{*}\right)^{-R/H}{\bmod {p}}\right){\bmod {q} }$ $y^{*}$

Útok na výpočet tajného klíče dalšího spoluvlastníka CECP

Nechť - je digitální podpis generovaný -tým uživatelem k dokumentu odpovídajícímu hashovací funkci (útok provádějí uživatelé). Pak platí následující: Útočníci generují náhodné hodnoty a počítají . pro . Poté se vypočítají parametry a splňující rovnice , kde . Zavedením označení . Máme , kde a . To znamená, že útočníci získali správnou hodnotu kolektivního podpisu , kterého se účastní oni a další uživatel, který má veřejný klíč . Podle předpokladu mohou útočníci z obdrženého kolektivního podpisu vypočítat tajný klíč . Je snadné získat z výrazu pro a vzorce : . Útočníci vypočítali tajný klíč daného uživatele pomocí jeho individuálního EDS, vygenerovaného v rámci základního algoritmu EDS. To dokazuje návrh, že navrhovaný protokol CECP nesnižuje sílu základního algoritmu EDS. [3] $\left(R^{*},S^{*}\right)$ $m$ $H$ $m-1$ $R^{*}=\left(\alpha ^{S^{*}/H}\left(y_{m}\right)^{-R^{*}/H}{\bmod {p }}\right){\bmod {q}}$ $t_{i}$ $R_{i}=\left(\alpha ^{t_{i}}{\bmod {p}}\right){\bmod {q}}$ $i=1,2,...,m-1$ $R=\left(R^{*}\prod _{i=1}^{m-1}R_{i}{\bmod {p}}\right){\bmod {q}}$ $S_{i}$ $R_{i}=\left(\alpha ^{S_{i}/H}y_{i}^{-R/H}{\bmod {p}}\right){\bmod {q}}$ $i=1,2,...,m-1$ $y^{*}=y_{m}^{R^{*}/R}{\bmod {p))$ $R=\left(\alpha ^{S/H}\left(Y\right)^{-R/H}{\bmod {p}}\right){\bmod {q}}$ $S=\left(S^{*}+\displaystyle \sum _{i=1}^{m-1}S_{i}\right){\bmod {p))$ $Y=\left(y^{*}\displaystyle \prod _{i=1}^{m-1}y_{i}\right){\bmod {p))$ $\left(R,S\right)$ $y^{*}=a^{k^{*}}{\bmod {p}}$ $k^{*}$ $y^{*}$ $y=\alpha ^{k}{\bmod {p))$ $k=RK^{*}/R^{*}{\bmod {q))$ $m$

Norma EDS - GOST R 34.10−2001

Podle normy GOST R 34.10−2001 [5] platí omezení na použité prvočíslo , prvočíslo a bod . Prvočíslo je modul eliptické křivky (EC), který je dán v kartézském souřadnicovém systému rovnicí s koeficienty a : ∈ ( je Galoisovo pole řádu ). Prvočíslo je řád cyklické podskupiny bodů na eliptické křivce. Bod - bod na eliptické křivce se souřadnicemi , který se liší od počátku, ale pro který se bod shoduje s počátkem. Tajný klíč je poměrně velké celé číslo . Veřejný klíč je bod . $p$ $q$ $G$ $p$ $y^{2}=x^{3}+ax+b{\bmod {p}}$ $A$ $b$ $a,b$ $GF_{p}$ $GF_{p}$ $p$ $q$ $G$ $(x_{G},y_{G})$ $qG$ $d$ $Q=dG$

Tvorba podpisu 1. Vygeneruje se náhodné celé číslo .

k,0<k<q

2. Vypočítejte souřadnice bodu EC a určete hodnotu , kde je souřadnice bodu .

C=kP

R=x_{C}{\bmod {q))

x_{C}

C

3. Hodnota se vypočítá , kde .

S=(Rd+ke){\bmod {q))

e=H{\bmod {q))

Podpis je dvojice čísel . [5]

(R,S)

Ověření podpisu

Ověření podpisu spočívá ve výpočtu souřadnic ES bodu:

C=\left(\left(Se^{-1}\right){\bmod {q}}\right)G+\left(\left(qR\right)e^{-1}{\bmod {q}}\right)Q

a také při určování hodnoty a kontrole rovnosti . [5] $R'=x_{C}{\bmod {q))$ $R'=R$

Implementace protokolu CECP

Každý člen skupiny vygeneruje veřejný klíč formuláře

Q=d_{i}G

, kde je soukromý (tajný) klíč, .

d_{i}

i=1,2,...,m

Společný veřejný klíč je součet

{\displaystyle Q=Q_{1}+Q_{2}+...+Q_{m))

Každý člen skupiny si vygeneruje číslo – jednorázový náhodný tajný klíč. Pomocí tohoto jednorázového náhodného klíče se vypočítají souřadnice bodu . Výsledek výpočtu je zaslán všem členům skupiny ke společnému použití. Součet je vypočítán $k_i$ $C_{i}=k_{i}G$

{\displaystyle C=C_{1}+C_{2}+...+C_{m))

Hodnota se počítá z přijaté částky . Každý člen skupiny vypočítá svou část podpisu: $R$

S_{i}=\left(Rd_{i}+k_{i}e\right){\bmod {q))

[3] Kontrola CECP

Vypočítat

C'=\left(\left(Se^{-1}\right){\bmod {q))\right)G+\left(\left(qR\right)e^{-1}{\ bmod {q}}\right)Q

Výsledek se vypočítá

R'=x_{C'}{\bmod {q}}

Jestliže , pak je QEC množiny m uživatelů pravé, protože by mohlo být vytvořeno pouze za účasti každého uživatele z této skupiny, protože vytvoření QEC vyžaduje tajný klíč každého z účastníků [3] . $R'=R$

Implementace vícenásobného podpisu založeného na RSA

Schéma dvojitého podpisu

Schéma dvojitého digitálního podpisu rozšiřuje konvenční schéma RSA . Ve schématu dvojitého digitálního podpisu se negeneruje pár klíčů (veřejný / soukromý klíč), ale trojitý (dva soukromé a jeden veřejný). Analogicky k obvyklému schématu RSA si účastníci vyberou výpočetní jednotku - součin dvou jednoduchých dlouhých čísel. Jsou vybrány 2 náhodné soukromé klíče a v rozsahu od 1 do , které budou shodné s , kde je funkce Euler . Veřejný klíč je generován podle vzorce . Hodnota bude veřejný klíč. Pro podepsání hodnoty první účastník vypočítá . Výsledek výpočtu je předán na vstup druhého člena skupiny. Druhý účastník má možnost vidět, co bude podepisovat. K tomu získá hodnotu z hodnoty . Poté, co bude druhý účastník připraven podepsat hodnotu , bude muset vypočítat . Ověření podpisu se provádí pomocí . [6] $n$ $r$ $s$ $n$ $\varphi (n)$ $\varphi (n)$ $r*s*t=1{\bmod {\varphi }}(n)$ $t$ $C$ $S_{1}=C^{r}{\bmod {n))$ $C$ $S_{1}$ $C$ $S_{2}=S_{1}^{s}{\bmod {n))$ $C=S_{2}^{t}{\bmod {n))$

Rozšíření schématu dvojího podpisu na členy $n$

Generují se náhodné soukromé klíče . Veřejný klíč bude vypočítán pomocí vzorce . Každý -tý účastník podepíše zprávu M podle vzorce . Poté se vypočítá hodnota . Ověření podpisu se provádí podle vzorce . [6] $n$ ${\displaystyle k_{1},k_{2},...,k_{n))$ $\left(k_{1}+k_{2}+...+k_{n}\right)*t=1{\bmod {\varphi }}(n)$ $i$ $S_{i}=M_{k}i{\bmod {n))$ $S=S_{1}*S_{2}*S_{3}*...*S_{n}{\bmod {n))$ $S^{t}{\bmod {n}}=\left(S_{1}*S_{2}*S_{3}*...*S_{n}\right)^{t}{ \bmod {n}}$ $=M^{\left(k_{1}+k_{2}+k_{3}+...+k_{n}\right)*t}{\bmod {n))=M$

Poznámky

↑ 1 2 Moldavčan Nikolaj Andrejevič, Eremejev Michail Aleksejevič, Galanov Alexej Igorevič. VÍCE PODPISŮ: NOVÁ ŘEŠENÍ ZALOŽENÁ NA KONCEPCI KOLEKTIVNÍHO VEŘEJNÉHO KLÍČE (rus.) // Journal "Information and Control Systems". - 2008. - Vydání. 1 .
↑ B. Schneier. Aplikovaná kryptografie (ruština) // John Wiley & Sons. - 1996. - S. 98 . Archivováno z originálu 18. prosince 2018.
↑ 1 2 3 4 5 6 7 8 9 Nikolaj Andrejevič Moldovjan, Andrej Alekseevič Kostin, Lidia Vjačeslavovna Gortinskaja, Michail Jurijevič Ananiev. IMPLEMENTACE PROTOKOLU KOLEKTIVNÍHO PODPISU NA ZÁKLADĚ EDS STANDARDŮ (rus.) // Journal "Information and Control Systems". - 2005. Archivováno 21. listopadu 2016.
↑ GOST R 34.10–94. Informační technologie. Kryptografická ochrana informací. Procesy vytváření a ověřování elektronického digitálního podpisu (ruština) // Gosstandart Ruské federace. - 1994. - 25. května.
↑ 1 2 3 GOST R 34.10–2001. Informační technologie. Kryptografická ochrana informací. Procesy vytváření a ověřování elektronického digitálního podpisu (ruština) // Gosstandart Ruské federace. - 2001. - 12. září.
↑ 1 2 Mihir Bellare, Gregory Neven. Digital Multi Signature Schemes (anglicky) // Springer-Verlag Berlin Heidelberg. - 2007. - S. 145-162 . (nedostupný odkaz)

Kryptosystémy s veřejným klíčem

Algoritmy

Faktorizace celých čísel	kryptosystém Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern zaplatit Rabin RSA Okamoto – Uchijama Schmidt-Samoa
Diskrétní logaritmus	BLS Cramer - Shoup protokol Diffie-Hellman DSA ECDH Křivka25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Výměna šifrovaných klíčů Schéma ElGamal podpisové schéma MQV Schnorrovo schéma SPEKE SRP STS
Kryptografie na mřížkách	NTRUEncrypt NTRUSsign Výměna klíčů založená na učení s chybami Trénink založený na podpisu s chybami v kruhu BLAHO Nová naděje
jiný	AE CEILIDH EPOC Rovnice skrytého pole IES Lamportův podpis McEliece Zádový kryptosystém Merkle-Hellman Zádový kryptosystém Naccache–Stern Tříkrokový protokol XTR

Teorie

Diskrétní logaritmus na eliptické křivce
Eliptická kryptografie
Kryptografie založená na hash
Nekomutativní kryptografie
Problém RSA
Jednosměrná funkce s tajným vstupem

Normy

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Post kvantová kryptografie

Témata

Elektronický podpis
OAEP
Otisk prstu
PKI
síť důvěry
Velikost klíče
Kryptografie založená na identitě
Postkvantová kryptografie
OpenPGP karta