Useita allekirjoituksia

Monikertainen (kollektiivinen) allekirjoitus ( englanniksi Aggregate signature ) - järjestelmä (protokolla) sähköisen allekirjoituksen (EDS) toteuttamiseksi, jonka avulla useat käyttäjät voivat allekirjoittaa yhden asiakirjan.

Yhteinen allekirjoitus tarjoaa mahdollisuuden sähköisen asiakirjan samanaikaiseen allekirjoittamiseen, koska se muodostuu yhden jakamattoman muunnoksen seurauksena eikä sitä voida jakaa yksittäisiin allekirjoituksiin; Lisäksi sitä ei voi laajentaa, eli siihen voidaan upottaa yhden tai useamman henkilön lisäallekirjoitus [1] .

Johdanto

Termi "kollektiivinen allekirjoitus" on sopusoinnussa termin " ryhmäallekirjoitus " kanssa, mutta nämä käsitteet ovat erilaisia. Ryhmän digitaalinen allekirjoitusprotokolla ratkaisee sen ongelman, että kuka tahansa tietyn ryhmän käyttäjä voi muodostaa allekirjoituksen koko ryhmän puolesta. Ryhmä-EDS-protokolla säätelee myös tiettyjen henkilöiden läsnäoloa, jotka voivat määrittää allekirjoituksen muodostaneiden henkilöiden luettelon (jälkimmäisillä on siis hypoteettinen mahdollisuus allekirjoittaa minkä tahansa ryhmän jäsenen puolesta). Sähköisten asiakirjojen kollektiivisessa työssä on välttämätöntä, että monet käyttäjät voivat allekirjoittaa ne [2] . Järjestelmän versiolla, jossa luodaan joukko yksittäisiä EDS-tiedostoja yhden sähköisen asiakirjan allekirjoittaneista käyttäjistä, on useita ilmeisiä haittoja - kollektiivisen EDS:n (CEDS) koon lineaarinen kasvu allekirjoittajien määrän kasvaessa sekä yhteisen digitaalisen allekirjoituksen eheyden ja täydellisyyden lisätarkastuksia, jotta voidaan poistaa mahdollisuus korvata asiakirjan allekirjoittaneiden osallistujien lukumäärä ja nimikokoonpano [1] .

Jaetun julkisen avaimen käsite

Osallistujien julkisten avainten perusteella muodostetaan kollektiivinen julkinen avain, jonka avulla voidaan kehittää ja varmistaa kollektiivisen sähköisen allekirjoituksen aitous. Jaettuun julkiseen avaimeen liittyy useita kokoa, eheyttä, käyttäjistä riippumattomuutta, jaetun julkisen avaimen samanaikaista luomista ja jatkuvuutta koskevia rajoituksia. Toisin sanoen on mahdotonta laskea kelvollista CECP:tä CECP:stä millekään muulle osallistujajoukolle nykyisten joukosta, CECP ei ole sidottu osallistujien kokoonpanoon - kuka tahansa käyttäjä voi muodostaa ryhmän ja kehittää oman CECP:n. Kollektiivinen julkinen avain, käyttäjien julkisten avainten toiminto, on perusta, jolle koko kollektiivinen allekirjoitusprotokolla rakennetaan [3] .

QECP on kehitetty yllä olevien vaatimusten mukaisesti käyttämällä algoritmeja, joiden stabiiliuden takaavat seuraavat laskennallisesti vaikeat ongelmat: diskreetti logaritmi suuren alkuluvun kertovassa ryhmässä, suuren alkuasteen juurien erottaminen modulo suuresta alkuluvusta, diskreetti logaritmi erikoismuotoisen elliptisen käyrän pisteiden ryhmä [3] .

EDS-standardeihin perustuvien protokollien käyttöönotto

EDS-standardi - GOST R 34.10-94

Standardin GOST R 34.10−94 [4] mukaan käytettävälle alkuluvulle p on asetettu rajoituksia. Alkuluvun p kapasiteetti binäärimuodossa: bitti tai bitti. Numeron on sisällettävä suuri alkulukujakaja siten, että for tai for . EDS :n luomiseen ja varmentamiseen käytetään lukua siten, että missä on riittävän suuren alkuluvun aliryhmän generaattori . $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-laskentaalgoritmi 1. Luodaan satunnaisluku .

k,1<k<q

2. Arvo lasketaan , joka on allekirjoituksen ensimmäinen osa.

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

3. GOST R 34.11–94:n mukaan hajautusfunktio lasketaan allekirjoitetusta viestistä.

H

4. Allekirjoituksen toinen osa lasketaan: , jossa on salainen avain. Jos , allekirjoituksen luontimenettely toistetaan.

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

z

S=0

EDS-todennusalgoritmi 1. Ehtojen täyttyminen ja varmistetaan . Jos ehdot eivät täyty, allekirjoitus ei ole kelvollinen.

r<q

s<q

2. Arvo lasketaan

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

, jossa on tarkistettavan allekirjoituksen luoneen käyttäjän julkinen avain.

y

3. Arvoja ja verrataan . Jos , niin allekirjoitus on voimassa

R

R'

R=R'

CECP-protokollan käyttöönotto

Jokainen käyttäjä luo julkisen avaimen muodossa , jossa on yksityinen (salainen) avain = , , … , . $i$ $y_{i}=\alpha ^{z_{i}}{\bmod {p}}$ $z_{i}$ $i$ $yksi$ $2$ $m$

Kollektiivinen julkinen avain on tuote

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

Jokainen käyttäjä valitsee satunnaisen salaisen avaimen , numeron, jota käytetään vain kerran. $k_i$

Laskettu

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

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

R_i

on kaikkien CECP:tä kehittävien tiimin jäsenten käytettävissä

Sitten jokainen KECP:tä kehittävä tiimin jäsen laskee määrittämänsä arvon ja tuloksen mukaan $R_i$ $H$

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

Si}

- osa allekirjoitusta.

Yhteinen allekirjoitus on arvojen pari , jossa on kaikkien modulo -arvojen summa [3] . ${\näyttötyyli (S,R)}$ $S$ $Si}$ $q$

Yhteisen sähköisen digitaalisen allekirjoituksen todentaminen

Yhteisen allekirjoituksen varmennus suoritetaan kaavan mukaan

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

Jos , niin käyttäjäjoukon CEC on aito, koska se voitiin muodostaa vain jokaisen tämän ryhmän käyttäjän osallistuessa, koska sen muodostaminen edellyttää jokaisen salaisen avaimen käyttöä. Huomaa, että arvot todennetaan automaattisesti, kun kollektiivinen digitaalinen allekirjoitus todennetaan. Jos tunkeilija yrittää korvata jonkin näistä arvoista tai korvata ne aiemmin käytetyillä arvoilla, protokollan häiriö havaitaan välittömästi digitaalista allekirjoitusta todettaessa , eli . On selvää, että QECP:n koko ei riipu [3] . $R=R'$ $m$ $R_i$ $R'\neq R$ $m$

Todiste ehdotetun CECP-algoritmin oikeellisuudesta

Korvaa saatu allekirjoitus yhtälöön — pariin (R,S), jossa R on R i modulo q:n tulo, S on yhtälön S i modulo q : yhtälön summa , jota säätelee standardi 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}\oikea)^{-R/H}{\bmod {p}}\oikea]{\bmod {q}}=$ $\left(\prod _{i=1}^{m}\alpha ^{\displaystyle S_{i}/H}\prod _{i=1}^{m}y_{i}^{\ näyttötyyli -R/H}{\bmod {p}}\oikea){\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}}\ oikea]{\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}}$

CECP:n väärentämisen mahdollisuus

Ilmeisesti rikkojien kannalta CECP:n väärentämisen monimutkaisuus määräytyy ryhmän yksittäisen jäsenen henkilökohtaisen allekirjoituksen väärentämisen monimutkaisuuden perusteella. Mahdollisuuksia syntyy käyttäjille, jotka yhdistävät voimansa muodostaakseen kollektiiviin liittyvän CECP:n, johon kuuluu heidän lisäksi yksi tai useampi muu käyttäjä, joille ei ole ilmoitettu tästä (todiste molemmissa tapauksissa on samanlainen). Haluavatko m-1- käyttäjät muodostaa QEDP:n, joka voidaan todentaa jaetulla julkisella avaimella , jolloin käyttäjät yhdistävät ponnistelunsa muodostaakseen numeroparin siten, että . Toisin sanoen he voivat väärentää julkisen avaimen allekirjoituksen , eli laskea arvot ja jotka täyttävät yhtälön . Tämä tarkoittaa mahdollisuutta väärentää digitaalinen allekirjoitus EDS-perusmallissa, koska sillä on satunnainen arvo [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}}\oikea){\bmod {q }}$ $y^{*}=y'y_{m}{\bmod {p))$ $R$ $S$ $R=\left(\alpha ^{S/H}\left(y^{*}\right)^{-R/H}{\bmod {p}}\oikea){\bmod {q} }$ $y^{*}$

Hyökkäys CECP:n toisen osaomistajan salaisen avaimen laskentaan

Olkoon - digitaalinen allekirjoitus , jonka -: nnet käyttäjä on luonut hajautustoimintoa vastaavaan dokumenttiin (hyökkäyksen suorittavat käyttäjät). Sitten seuraava on totta: Hyökkääjät luovat satunnaisia arvoja ja laskevat . varten . Sitten lasketaan parametrit ja jotka täyttävät yhtälöt , jossa . Esittelemällä nimityksen . Meillä on , missä ja . Tämä tarkoittaa, että hyökkääjät ovat saaneet oikean arvon kollektiiviselle allekirjoitukselle , johon he ja toinen käyttäjä, jolla on julkinen avain, osallistuvat . Oletuksen mukaan hyökkääjät voivat laskea salaisen avaimen vastaanotetusta kollektiivisesta allekirjoituksesta . Se on helppo saada lausekkeesta for ja kaavasta : . Hyökkääjät laskivat käyttäjän salaisen avaimen käyttämällä hänen yksilöllistä EDS:ään, joka on luotu EDS-perusalgoritmin puitteissa. Tämä todistaa ehdotuksen, että ehdotettu CECP-protokolla ei vähennä taustalla olevan EDS-algoritmin vahvuutta. [3] $\left(R^{*},S^{*}\oikea)$ $m$ $H$ $m-1$ $R^{*}=\left(\alpha ^{S^{*}/H}\left(y_{m}\right)^{-R^{*}/H}{\bmod {p }}\oikea){\bmod {q}}$ $t_{i}$ $R_{i}=\left(\alpha ^{t_{i}}{\bmod {p}}\oikea){\bmod {q}}$ $i=1,2,...,m-1$ $R=\left(R^{*}\prod _{i=1}^{m-1}R_{i}{\bmod {p}}\oikea){\bmod {q}}$ $Si}$ $R_{i}=\left(\alpha ^{S_{i}/H}y_{i}^{-R/H}{\bmod {p}}\oikea){\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}}\oikea){\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-standardi - GOST R 34.10−2001

Standardin GOST R 34.10−2001 [5] mukaan rajoituksia on asetettu käytettävälle alkuluvulle , alkuluvulle ja pisteelle . Alkuluku on elliptisen käyrän (EC) moduuli , joka on annettu karteesisessa koordinaatistossa yhtälöllä , jossa on kertoimet ja : ∈ ( on Galois'n järjestyskenttä ). Alkuluku on elliptisen käyrän pisteiden syklisen alaryhmän järjestys. Piste - piste elliptisellä käyrällä, jonka koordinaatit on eri kuin origo, mutta jonka piste on sama kuin origo. Salainen avain on melko suuri kokonaisluku . Julkinen avain on piste . $s$ $q$ $G$ $s$ $y^{2}=x^{3}+ax+b{\bmod {p))$ $a$ $b$ $a,b$ $GF_{p}$ $GF_{p}$ $s$ $q$ $G$ ${\näyttötyyli (x_{G},y_{G})}$ $qG$ $d$ $Q=dG$

Allekirjoituksen muodostus 1. Luodaan satunnainen kokonaisluku .

k,0<k<q

2. Laske EC-pisteen koordinaatit ja määritä arvo , jossa on pisteen koordinaatti .

C=kP

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

x_{C}

C

3. Lasketaan arvo , jossa .

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

e=H{\bmod {q))

Allekirjoitus on numeropari . [5]

{\näyttötyyli (R,S)}

Allekirjoituksen vahvistus

Allekirjoituksen todentaminen koostuu EY-pisteen koordinaattien laskemisesta:

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

sekä arvonmäärittelyssä ja tasa-arvon tarkastuksessa . [5] $R'=x_{C}{\bmod {q))$ $R'=R$

CECP-protokollan käyttöönotto

Jokainen ryhmän jäsen luo lomakkeen julkisen avaimen

Q=d_{i}G

, missä on yksityinen (salainen) avain, .

d_{i}

i=1,2,...,m

Kollektiivinen julkinen avain on summa

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

Jokainen ryhmän jäsen luo numeron - kertaluonteisen satunnaisen salaisen avaimen. Tämän kertaluonteisen satunnaisavaimen avulla lasketaan pisteen koordinaatit . Laskennan tulos lähetetään kaikille ryhmän jäsenille yhteiskäyttöön. Summa lasketaan $k_i$ $C_{i}=k_{i}G$

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

Arvo lasketaan saadusta summasta . Jokainen ryhmän jäsen laskee oman osuutensa allekirjoituksesta: $R$

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

[3] Tarkistetaan CECP

Laskea

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

Tulos lasketaan

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

Jos , niin m käyttäjän joukon QEC on aito, koska se voidaan muodostaa vain jokaisen tämän ryhmän käyttäjän osallistuessa, koska QEC:n muodostaminen vaatii jokaisen osallistujan salaisen avaimen [3] . $R'=R$

RSA-pohjaisen usean allekirjoituksen käyttöönotto

Kaksoisallekirjoitusmalli

Kaksinkertainen digitaalinen allekirjoitus laajentaa perinteistä RSA - mallia . Kaksinkertaisessa digitaalisessa allekirjoituksessa ei luoda avainparia (julkinen / yksityinen avain), vaan kolminkertainen (kaksi yksityistä ja yksi julkinen). Analogisesti tavallisen RSA-järjestelmän kanssa osallistujat valitsevat laskentayksikön - kahden yksinkertaisen pitkän luvun tulon. Valitaan 2 satunnaista yksityistä avainta välillä 1 - , joka on koprime kanssa , missä on Euler - funktio . Julkinen avain generoidaan kaavan mukaan . Arvo on julkinen avain. Allekirjoittaakseen arvon ensimmäinen osallistuja laskee . Laskennan tulos välitetään ryhmän toisen jäsenen syötteeseen. Toisella osallistujalla on mahdollisuus nähdä, mitä hän allekirjoittaa. Tätä varten se saa arvon arvosta . Kun toinen osallistuja on valmis allekirjoittamaan arvon , hänen on laskettava . Allekirjoituksen tarkistus suoritetaan käyttämällä . [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))$

Kaksoisallekirjoitusjärjestelmän laajentaminen jäseniin $n$

Satunnaisia yksityisiä avaimia luodaan . Julkinen avain lasketaan kaavalla . Jokainen -. osallistuja allekirjoittaa viestin M kaavan mukaan . Sitten lasketaan arvo . Allekirjoituksen tarkistus suoritetaan kaavan mukaan . [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$

Muistiinpanot

↑ 1 2 Moldovyan Nikolay Andreevich, Eremeev Mihail Alekseevich, Galanov Aleksei Igorevitš. MONIA ALLEKIRJOITUS: UUSIA RATKAISIA PERUSTUVAT KOLLEKTIIVIN JULKINEN AVAIN (rus.) // Journal "Information and Control Systems". - 2008. - Ongelma. 1 .
↑ B. Schneier. Sovellettu kryptografia (venäjä) // John Wiley & Sons. - 1996. - S. 98 . Arkistoitu alkuperäisestä 18. joulukuuta 2018.
↑ 1 2 3 4 5 6 7 8 9 Nikolay Andreevich Moldovyan, Andrey Alekseevich Kostin, Lidia Vyacheslavovna Gortinskaya, Mihail Jurievich Ananiev. EDS-STANDARDEISIIN PERUSTUVA YHTEISKOHTAINEN ALLEKIRJOITUSPROTOKOLLA TÄYTÄNTÖÖNPANO (rus.) // Journal "Information and Control Systems". - 2005. Arkistoitu 21. marraskuuta 2016.
↑ GOST R 34.10-94. Tietotekniikka. Tietojen kryptografinen suojaus. Sähköisen digitaalisen allekirjoituksen (venäläinen) muodostus- ja varmennusprosessit // Venäjän federaation Gosstandart. - 1994 - 25. toukokuuta.
↑ 1 2 3 GOST R 34.10–2001. Tietotekniikka. Tietojen kryptografinen suojaus. Sähköisen digitaalisen allekirjoituksen (venäläinen) muodostus- ja varmennusprosessit // Venäjän federaation Gosstandart. - 2001 - 12. syyskuuta.
↑ 1 2 Mihir Bellare, Gregory Neven. Digital Multi Signature Schemes (englanniksi) // Springer-Verlag Berlin Heidelberg. - 2007. - S. 145-162 . (linkki ei saatavilla)

Julkisen avaimen salausjärjestelmät

Algoritmit

Kokonaislukujen faktorointi	Benalon kryptojärjestelmä Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern paye Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskreetti logaritmi	BLS Cramer - Shoup Diffie-Hellman-protokolla DSA ECDH Käyrä 25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Salatun avaimen vaihto ElGamalin kaava allekirjoitusmalli MQV Schnorrin kaava SPEKE SRP STS
Kryptografia ristikoilla	NTRUEncrypt NTRUSign Oppimiseen perustuva avainten vaihto virheineen Allekirjoituspohjainen koulutus, jossa virheitä kehässä AUTUUS Uusi toivo
Muut	AE CEILIDH EPOC Piilotettu kenttäyhtälöt IES Lamportin allekirjoitus McEliece Merkle-Hellmanin selkärepun salausjärjestelmä Naccache-Stern selkäreppujen salausjärjestelmä Kolmivaiheinen protokolla XTR

Teoria

Diskreetti logaritmi elliptisellä käyrällä
Elliptinen kryptografia
Hash-pohjainen kryptografia
Ei-kommutatiivinen kryptografia
RSA ongelma
Yksisuuntainen toiminto salaisella sisäänkäynnillä

Standardit

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Postkvanttisalaus

Aiheet

Sähköinen allekirjoitus
OAEP
Sormenjälki
PKI
luottamuksen verkko
Avaimen koko
Identiteettiin perustuva kryptografia
Postkvanttisalaus
OpenPGP-kortti