Többszörös aláírás

Többszörös (kollektív) aláírás ( angolul Aggregate signature ) - az elektronikus aláírás (EDS) megvalósítására szolgáló séma (protokoll) , amely lehetővé teszi, hogy több felhasználó írjon alá egyetlen dokumentumot.

A kollektív aláírás lehetőséget biztosít egy elektronikus dokumentum egyidejű aláírására, mivel az egyetlen oszthatatlan átalakítás eredményeként jön létre, és nem osztható fel egyedi aláírásokra; emellett nem bővíthető, azaz egy vagy több személy további aláírása ágyazható be [1] .

Bevezetés

A "kollektív aláírás" kifejezés megegyezik a " csoportos aláírás " kifejezéssel, de ezek a fogalmak különböznek egymástól. A csoportos digitális aláírási protokoll megoldja azt a problémát, hogy egy adott csoport bármely felhasználója aláírást hozzon létre a teljes csoport nevében. A csoportos EDS-protokoll szabályozza azon személyek jelenlétét is, akik meghatározhatják az aláírást létrehozó személyek listáját (ez utóbbiaknak feltételezhetően lehetőségük van az aláírásra a csoport bármelyik tagja számára). Az elektronikus dokumentumokkal végzett kollektív munka esetén szükséges, hogy sok felhasználó alá tudja írni azokat [2] . Az egy elektronikus dokumentumot aláíró felhasználók egyéni EDS-készletének generálásával járó rendszerváltozatnak számos kifejezett hátránya van - a kollektív EDS (CEDS) méretének lineáris növekedése az aláírók számának növekedésével, valamint a kollektív digitális aláírás sértetlenségének és hiánytalanságának további ellenőrzésének szükségessége a dokumentumot aláíró résztvevők számának és névösszetételének helyettesítésének kiküszöbölése érdekében [1] .

A megosztott nyilvános kulcs fogalma

A résztvevők nyilvános kulcsai alapján kollektív nyilvános kulcs generálódik, amely lehetővé teszi a kollektív elektronikus aláírás kidolgozását és hitelességének ellenőrzését. A megosztott nyilvános kulcsra számos korlátozás vonatkozik a méretre, az integritásra, a felhasználóktól való függetlenségre, a megosztott nyilvános kulcs egyidejű generálására és a folytonosságra vonatkozóan. Más szóval, a CECP-ből nem lehet érvényes CECP-t kiszámítani bármely más résztvevőcsoport számára a jelenlegiek halmazából, a CECP nincs a résztvevők összetételéhez kötve - bármely felhasználó létrehozhat egy csoportot és kialakíthatja saját CECP-jét. A kollektív nyilvános kulcs, a felhasználók nyilvános kulcsainak függvénye, az egész kollektív aláírási protokoll alapja [3] .

A QECP-t a fenti követelményeknek megfelelően fejlesztették ki olyan algoritmusok felhasználásával, amelyek stabilitását a következő számításilag nehéz problémák biztosítják: diszkrét logaritmus nagy prímrendű multiplikatív csoportban, nagy prímfok gyökeinek kinyerése modulo nagy prím, diszkrét logaritmus speciális alakú elliptikus görbe pontjainak csoportja [3] .

EDS szabványokon alapuló protokollok megvalósítása

EDS szabvány - GOST R 34.10-94

A GOST R 34.10−94 [4] szabvány szerint a használt p prímszámra korlátozások vonatkoznak. Egy p prímszám kapacitása bináris ábrázolásban: bit vagy bit. A számnak tartalmaznia kell egy nagy prímosztót úgy, hogy for vagy for . Az EDS generálásához és ellenőrzéséhez olyan számot használnak , ahol a kellően nagy prímrendű alcsoport generátora . $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$

EDS számítási algoritmus 1. Egy véletlen szám jön létre .

k,1<k<q

2. A rendszer kiszámítja az értéket , amely az aláírás első része.

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

3. A GOST R 34.11–94 szerint a hash függvényt az aláírt üzenetből számítják ki.

H

4. Az aláírás második része kiszámításra kerül: , ahol a titkos kulcs. Ha , az aláírásgenerálási eljárás megismétlődik.

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

z

S=0

EDS hitelesítési algoritmus 1. A feltételek teljesítését és igazoljuk . Ha a feltételek nem teljesülnek, akkor az aláírás érvénytelen.

r<q

s<q

2. Az érték kiszámításra kerül

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

, ahol az ellenőrizendő aláírást létrehozó felhasználó nyilvános kulcsa található.

y

3. A és értékeket összehasonlítjuk . Ha , akkor az aláírás érvényes

R

R'

R=R'

A CECP protokoll megvalósítása

Minden egyes felhasználó létrehoz egy nyilvános kulcsot az alábbi formában , ahol egy privát (titkos) kulcs, = , , … , . $én$ $y_{i}=\alpha ^{z_{i}}{\bmod {p}}$ $z_{i}$ $én$ $egy$ $2$ $m$

A kollektív nyilvános kulcs a termék

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

Minden felhasználó kiválaszt egy véletlenszerű titkos kulcsot , egy számot, amelyet csak egyszer használ fel. $k_i$

Számított

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

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

R_i

elérhető minden csapattag számára, aki fejleszti a CECP-t

Ezután a KECP-t fejlesztő csapattagok mindegyike az általa meghatározott érték és eredmény szerint számol $R_i$ $H$

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

S_{i}

- az aláírás része.

A kollektív aláírás egy értékpár lesz , ahol az összes modulo összege [3] . ${\megjelenítési stílus (S,R)}$ $S$ $S_{i}$ $q$

Kollektív elektronikus digitális aláírás ellenőrzése

A közös aláírás ellenőrzése a képlet szerint történik

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

Ha , akkor a felhasználók halmazának CEC-je valódi, mivel csak az ebből a csoportból származó összes felhasználó részvételével jöhet létre, mivel a létrehozásához mindegyikük titkos kulcsának használata szükséges. Vegye figyelembe, hogy a kollektív digitális aláírás hitelesítésekor az értékek automatikusan hitelesítésre kerülnek. Ha egy behatoló megpróbálja lecserélni ezeket az értékeket, vagy lecseréli azokat korábban használt értékekkel, akkor a digitális aláírás hitelesítésekor azonnal észleli a protokoll zavarásának tényét , azaz . Nyilvánvaló, hogy a QECP mérete nem függ [3] -tól . $R=R'$ $m$ $R_i$ $R'\neq R$ $m$

A javasolt CECP algoritmus helyességének bizonyítása

Helyettesítse be a kapott aláírást az egyenletbe – egy pár (R,S), ahol R az R i modulo q szorzata, S az S i modulo q : egyenlet összege , amelyet az EDS GOST R 34.10-94 szabvány szabályoz. $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}^{\ displaystyle -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}}\ jobbra]{\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}}$

Hamisítás lehetősége CECP

Nyilvánvaló, hogy a szabálysértők számára a CECP-hamisítás bonyolultságát a csoport egy tagjának egyéni aláírásának hamisításának összetettsége határozza meg. Lehetőség nyílik azoknak a felhasználóknak, akik egyesítik erőfeszítéseiket egy olyan kollektívához kapcsolódó CECP létrehozására, amely rajtuk kívül még egy vagy több másik felhasználót is tartalmaz, akiket erről nem értesítenek (a bizonyíték mindkét esetben hasonló). Hagyja , hogy az m-1 felhasználók egy megosztott nyilvános kulccsal ellenőrizhető QEDP-t alkossanak , ahol , azaz a felhasználók egyesítik erőfeszítéseiket , hogy olyan számpárt alkossanak , hogy . Ez azt jelenti, hogy hamisíthatnak egy nyilvános kulcsú aláírást , azaz kiszámíthatják a és az egyenletet kielégítő értékeket . Ez magában foglalja a digitális aláírás hamisításának lehetőségét az alap EDS sémában, mivel annak véletlenszerű értéke van [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^{*}$

Támadás a CECP másik társtulajdonosa titkos kulcsának kiszámítása ellen

Legyen - a -edik felhasználó által a hash függvénynek megfelelő dokumentumhoz generált digitális aláírás (a támadást a felhasználók hajtják végre). Ekkor a következő igaz: A támadók véletlenszerű értékeket generálnak és kiszámítják . számára . Ezután kiszámítjuk azokat a és paramétereket , amelyek kielégítik az egyenleteket , ahol . Az elnevezés bevezetésével . Van , hol és . Ez azt jelenti, hogy a támadók megszerezték annak a kollektív aláírásnak a megfelelő értékét, amelyben ők és egy másik, nyilvános kulccsal rendelkező felhasználó részt vesz . A feltételezés szerint a kapott kollektív aláírásból a támadók ki tudják számítani a titkos kulcsot . Könnyen kiolvasható a for kifejezésből és a képletből : . A támadók az EDS alapalgoritmus keretein belül generált egyéni EDS segítségével számították ki a th felhasználó titkos kulcsát . Ez bizonyítja azt a feltételezést, hogy a javasolt CECP protokoll nem csökkenti az alapul szolgáló EDS algoritmus erejét. [3] $\left(R^{*},S^{*}\right)$ $m$ $H$ $m-1$ $R^{*}=\left(\alpha ^{S^{*}/H}\left(y_{m}\right)^{-R^{*}/H}{\bmod {p }}\jobbra){\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$

EDS szabvány - GOST R 34.10−2001

A GOST R 34.10-2001 [5] szabvány szerint korlátozások vonatkoznak a használt prímszámra , prímszámra és pontra . A prímszám egy elliptikus görbe (EC) modulusa , amelyet a derékszögű koordináta-rendszerben egy egyenlet ad meg együtthatókkal és : ∈ ( a Galois -féle rendű mező ). A prímszám egy elliptikus görbe pontjainak ciklikus részcsoportjának sorrendje. Pont - egy pont az elliptikus görbén koordinátákkal , amely eltér az origótól, de a pont egybeesik az origóval. A titkos kulcs egy meglehetősen nagy egész szám . A nyilvános kulcs pont . $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$

Aláírás kialakítása 1. Egy véletlenszerű egész szám jön létre .

k,0<k<q

2. Számítsa ki az EK pont koordinátáit és határozza meg az értéket , ahol a pont koordinátája .

C=kP

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

x_{C}

C

3. Kiszámítjuk az értéket , ahol .

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

e=H{\bmod {q))

Az aláírás egy számpár . [5]

{\megjelenítési stílus (R,S)}

Aláírás ellenőrzése

Az aláírás ellenőrzése az EK-pont koordinátáinak kiszámításából áll:

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

valamint az értékmeghatározásban és az egyenlőség-ellenőrzésben is . [5] $R'=x_{C}{\bmod {q))$ $R'=R$

A CECP protokoll megvalósítása

A csoport minden tagja létrehozza az űrlap nyilvános kulcsát

Q=d_{i}G

, ahol egy privát (titkos) kulcs, .

d_{i}

i=1,2,...,m

A kollektív nyilvános kulcs az összeg

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

A csoport minden tagja generál egy számot – egy egyszeri véletlenszerű titkos kulcsot. Ennek az egyszeri véletlenszerű kulcsnak a segítségével kiszámítja a pont koordinátáit . A számítás eredményét a csoport minden tagja elküldi közös használatra. Az összeg kiszámításra kerül $k_i$ $C_{i}=k_{i}G$

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

Az érték a kapott összegből kerül kiszámításra . A csoport minden tagja kiszámítja a rájuk eső részt az aláírásból: $R$

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

[3] CECP ellenőrzése

Kiszámítja

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

Az eredmény kiszámításra kerül

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

Ha , akkor az m felhasználóból álló halmaz QEC-je valódi, mivel csak a csoport minden egyes felhasználójának részvételével jöhet létre, mivel a QEC kialakításához minden résztvevő titkos kulcsára van szükség [3] . $R'=R$

Többszörös aláírás megvalósítása RSA alapján

Kettős aláírási séma

A kettős digitális aláírási séma kiterjeszti a hagyományos RSA sémát . A kettős digitális aláírási sémában nem egy kulcspár (nyilvános / privát kulcs), hanem egy hármas (két privát és egy nyilvános) jön létre. A szokásos RSA-sémához hasonlóan a résztvevők választanak egy számítási egységet - két egyszerű hosszú szám szorzatát. 2 véletlenszerű privát kulcs van kiválasztva 1 és tartományban , ami együtt lesz a következővel , ahol az Euler függvény . A nyilvános kulcs a képlet szerint jön létre . Az érték a nyilvános kulcs lesz. Az érték aláírásához az első résztvevő kiszámítja . A számítás eredménye a csoport második tagjának bemenetére kerül. A második résztvevőnek lehetősége van megnézni, mit ír alá. Ehhez az értéket az értékből kapja . Miután a második résztvevő készen áll az érték aláírására , ki kell számítania . Az aláírás ellenőrzése a segítségével történik . [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))$

A kettős aláírási séma kiterjesztése a tagokra $n$

Véletlenszerű privát kulcsok generálódnak . A nyilvános kulcs kiszámítása a képlet segítségével történik . Minden -edik résztvevő aláírja az M üzenetet a képlet szerint . Ezután kiszámítjuk az értéket . Az aláírás ellenőrzése a képlet szerint történik . [6] $n$ ${\displaystyle k_{1},k_{2},...,k_{n))$ $\left(k_{1}+k_{2}+...+k_{n}\right)*t=1{\bmod {\varphi }}(n)$ $én$ $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$

Jegyzetek

↑ 1 2 Moldovyan Nyikolaj Andrejevics, Eremejev Mihail Alekszejevics, Galanov Alekszej Igorevics. TÖBBSZÖRÖS ALÁÍRÁS: ÚJ MEGOLDÁSOK A KOLLEKTÍV NYILVÁNOS KULCS ALAPJÁN (rus.) // "Information and Control Systems" folyóirat. - 2008. - Kiadás. 1 .
↑ B. Schneier. Alkalmazott kriptográfia (orosz) // John Wiley & Sons. - 1996. - S. 98 . Az eredetiből archiválva : 2018. december 18.
↑ 1 2 3 4 5 6 7 8 9 Nyikolaj Andrejevics Moldovyan, Andrej Alekszejevics Kosztin, Lidia Vjacseszlavovna Gortyinszkaja, Mihail Jurijevics Ananijev. AZ EDS-SZABVÁNYOK ALAPJÁN ALAPULÓ KÖZÖSSÉGI ALÁÍRÁS JEGYZŐKÖNYV VÉGREHAJTÁSA (rus.) // "Information and Control Systems" folyóirat. - 2005. Archiválva : 2016. november 21.
↑ GOST R 34.10–94. Információs technológia. Az információk kriptográfiai védelme. Az elektronikus digitális aláírás létrehozásának és ellenőrzésének folyamatai (orosz) // Az Orosz Föderáció Gosstandartja. - 1994. - május 25.
↑ 1 2 3 GOST R 34.10–2001. Információs technológia. Az információk kriptográfiai védelme. Az elektronikus digitális aláírás létrehozásának és ellenőrzésének folyamatai (orosz) // Az Orosz Föderáció Gosstandartja. - 2001. - szeptember 12.
↑ 1 2 Mihir Bellare, Gregory Neven. Digital Multi Signature Schemes (angol) // Springer-Verlag Berlin Heidelberg. - 2007. - S. 145-162 . (nem elérhető link)

Nyilvános kulcsú kriptorendszerek

Algoritmusok

Egész számok faktorizálása	Benalo kriptorendszer Bluma – Goldwasser Cayley Purser Damgorda – Eureka GMR Goldwasser – Micali Nakasha – Stern paye Rabin RSA Okamoto – Uchiyama Schmidt-Szamoa
Diszkrét logaritmus	BLS Cramer – Shoup Diffie-Hellman protokoll DSA ECDH Görbe 25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Titkosított kulcscsere ElGamal séma aláírási séma MQV Schnorr-séma SPEKE SRP STS
Kriptográfia rácsokon	NTRUEncrypt NTRUSign Tanulás alapú kulcscsere hibákkal Aláírás alapú edzés hibákkal a ringben BOLDOGSÁG Új remény
Egyéb	AE CEILIDH EPOC Rejtett mező egyenletek IES Lamport aláírása McEliece Merkle-Hellman háti kriptorendszer Naccache–Stern háti kriptorendszer Három lépéses protokoll XTR

Elmélet

Szabványok

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Posztkvantum kriptográfia

Témák

Elektronikus aláírás
OAEP
Ujjlenyomat
PKI
a bizalom hálója
Kulcsméret
Identitás alapú kriptográfia
Posztkvantum kriptográfia
OpenPGP kártya