Semnătură multiplă

Semnătură multiplă (colectivă) ( English Aggregate signature ) - o schemă (protocol) pentru implementarea unei semnături electronice (EDS), care permite mai multor utilizatori să semneze un singur document.

O semnătură colectivă oferă posibilitatea semnării simultane a unui document electronic, deoarece se formează ca urmare a unei transformări unice indivizibile și nu poate fi împărțită în semnături individuale; în plus, nu poate fi extinsă, adică poate fi încorporată în ea o semnătură suplimentară a uneia sau mai multor persoane [1] .

Introducere

Termenul „semnătură colectivă” este în consonanță cu termenul „ semnătură de grup ”, dar aceste concepte sunt diferite. Protocolul de semnătură digitală de grup rezolvă problema de a permite oricărui utilizator dintr-un anumit grup să formeze o semnătură în numele întregului grup. Protocolul EDS de grup reglementează și prezența unor persoane specifice care pot stabili lista persoanelor care au format o semnătură (astfel, acestea din urmă au o ipotetică oportunitate de a semna pentru oricare dintre membrii grupului). În cazul lucrului colectiv cu documente electronice, este necesar să le poată semna de către mulți utilizatori [2] . Varianta schemei cu generarea unui set de EDS individuale de utilizatori care semnează un document electronic are mai multe dezavantaje pronunțate - o creștere liniară a dimensiunii EDS colectiv (CEDS) cu o creștere a numărului de semnatari, precum și necesitatea unor verificări suplimentare ale integrității și completității semnăturii digitale colective pentru a elimina posibilitatea înlocuirii numărului și componenței numelui participanților care au semnat documentul [1] .

Conceptul unei chei publice partajate

Pe baza cheilor publice ale participanților, se generează o cheie publică colectivă, care face posibilă dezvoltarea și verificarea autenticității unei semnături digitale electronice colective. Cheia publică partajată este supusă unui număr de restricții privind dimensiunea, integritatea, independența față de utilizatori, generarea simultană a cheii publice partajate și continuitate. Cu alte cuvinte, este imposibil să se calculeze un CECP valid din CECP pentru orice alt set de participanți din setul celor actuali, CECP nu este legat de componența participanților - orice utilizator poate forma un grup și își poate dezvolta propriul CECP. Cheia publică colectivă, o funcție a cheilor publice ale utilizatorilor, este baza pe care este construit întregul protocol de semnătură colectivă [3] .

QECP este dezvoltat în conformitate cu cerințele de mai sus folosind algoritmi a căror stabilitate este asigurată de următoarele probleme dificile din punct de vedere computațional: logaritm discret într-un grup multiplicativ de ordin prim mare , extragerea rădăcinilor de grad prim mare modulo un prim mare, logaritm discret în grup de puncte ale unei curbe eliptice de formă specială [3] .

Implementarea protocoalelor bazate pe standardele EDS

Standard EDS - GOST R 34.10−94

Conform standardului GOST R 34.10−94 [4] , sunt impuse restricții asupra numărului prim p utilizat. Capacitatea unui număr prim p în reprezentare binară: bit sau bit. Numărul trebuie să conțină un divizor prim mare, astfel încât pentru sau pentru . Pentru a genera și verifica un EDS , se folosește un număr astfel încât , unde este generatorul unui subgrup de ordin prim suficient de mare . $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$ $\alfa$ $q$

Algoritm de calcul EDS 1. Se generează un număr aleatoriu .

k,1<k<q

2. Se calculează valoarea , care este prima parte a semnăturii.

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

3. Conform GOST R 34.11–94, o funcție hash este calculată din mesajul care este semnat.

H

4. Se calculează a doua parte a semnăturii: , unde este cheia secretă. Dacă , procedura de generare a semnăturii se repetă.

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

z

S=0

Algoritm de autentificare EDS 1. Îndeplinirea condițiilor și se verifică . Dacă nu sunt îndeplinite condițiile, semnătura nu este valabilă.

r<q

s<q

2. Se calculează valoarea

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

, unde este cheia publică a utilizatorului care a generat semnătura pentru a fi verificată.

y

3. Valorile și sunt comparate . Dacă , atunci semnătura este valabilă

R

R'

R=R'

Implementarea protocolului CECP

Fiecare utilizator generează o cheie publică de forma , unde este o cheie privată (secretă), = , , … , . $i$ $y_{i}=\alpha ^{z_{i}}{\bmod {p}}$ $z_{i}$ $i$ $unu$ $2$ $m$

Cheia publică colectivă este produsul

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

Fiecare utilizator alege o cheie secretă aleatorie , un număr care este folosit o singură dată. $k_i$

Calculat

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

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

R_i

este disponibil tuturor membrilor echipei care dezvoltă CECP

Apoi, fiecare dintre membrii echipei care dezvoltă KECP, în funcție de valoarea și rezultatul determinat de acesta, calculează $R_i$ $H$

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

Si}

- parte a semnăturii.

Semnătura colectivă va fi o pereche de valori , unde este suma tuturor modulo [3] . $(S,R)$ $S$ $Si}$ $q$

Verificarea unei semnături digitale electronice colective

Verificarea semnăturii colective se realizează conform formulei

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

Dacă , atunci CEC-ul setului de utilizatori este autentic, deoarece ar putea fi format numai cu participarea fiecărui utilizator din acest grup, deoarece formarea sa necesită utilizarea cheii secrete a fiecăruia dintre ei. Rețineți că valorile sunt autentificate automat atunci când semnătura digitală colectivă este autentificată. Dacă un intrus încearcă să înlocuiască oricare dintre aceste valori sau să le înlocuiască cu valori utilizate anterior, atunci faptul de interferență cu protocolul va fi detectat imediat la autentificarea semnăturii digitale , adică . Evident, dimensiunea QECP nu depinde de [3] . $R=R'$ $m$ $R_i$ $R'\neq R$ $m$

Dovada corectitudinii algoritmului CECP propus

Înlocuiți semnătura obținută în ecuație — o pereche (R,S), unde R este produsul lui R i modulo q, S este suma lui S i modulo q : ecuație , reglementată de standardul 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}^{\ stil de afișare -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}}\dreapta)\dreapta]{\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}}\ dreapta]{\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}}$

Posibilitatea contrafacerii CECP

Evident, pentru contravenienți, complexitatea falsificării CECP este determinată de complexitatea falsificării semnăturii individuale a unui membru individual al grupului. Oportunitățile apar utilizatorilor care își unesc eforturile pentru a forma un CECP aferent unui colectiv, care, pe lângă aceștia, include unul sau mai mulți utilizatori care nu sunt anunțați despre acest lucru (dovada pentru ambele cazuri este similară). Utilizatorii m-1 doresc să formeze un QEDP verificabil printr-o cheie publică partajată , unde , adică utilizatorii își combină eforturile pentru a forma o pereche de numere astfel încât . Adică, pot falsifica o semnătură a cheii publice , adică pot calcula valorile și care satisfac ecuația . Aceasta implică posibilitatea de a falsifica o semnătură digitală în schema EDS de bază, deoarece are o valoare aleatorie [3] . $y=y'y_{m}{\bmod {p)}$ $y'=\prod _{i=1}^{m-1}y_{i}{\bmod {p))$ $m-1$ $\stanga(R,S\dreapta)$ $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^{*}$

Un atac la calculul cheii secrete a altui coproprietar al CECP

Fie - semnătura digitală generată de utilizatorul --lea documentului corespunzător funcției hash (atacul este efectuat de utilizatori). Atunci următorul lucru este adevărat: Atacatorii generează valori aleatorii și calculează . pentru . Apoi se calculează parametrii și care satisfac ecuațiile , unde . Prin introducerea denumirii . Avem , unde și . Aceasta înseamnă că atacatorii au obținut valoarea corectă a semnăturii colective la care participă ei și un alt utilizator care deține cheia publică . Conform ipotezei, din semnătura colectivă primită, atacatorii pot calcula cheia secretă . Este ușor de obținut din expresia pentru și formula : . Atacatorii au calculat cheia secretă a celui de-al- lea utilizator folosind EDS-ul său individual, generat în cadrul algoritmului EDS de bază. Aceasta dovedește sugestia că protocolul CECP propus nu reduce puterea algoritmului EDS de bază. [3] $\left(R^{*},S^{*}\right)$ $m$ $H$ $m-1$ $R^{*}=\left(\alpha ^{S^{*}/H}\left(y_{m}\right)^{-R^{*}/H}{\bmod {p }}\dreapta){\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}}$ $Si}$ $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))$ $\stanga(R,S\dreapta)$ $y^{*}=a^{k^{*}}{\bmod {p}}$ $k^{*}$ $y^{*}$ $y=\alpha ^{k}{\bmod {p)}$ $k=RK^{*}/R^{*}{\bmod {q))$ $m$

Standard EDS - GOST R 34.10−2001

Conform standardului GOST R 34.10−2001 [5] , sunt impuse restricții asupra numărului prim, numărului prim și punctului utilizat . Un număr prim este modulul unei curbe eliptice (EC), care este dat în sistemul de coordonate carteziene printr-o ecuație cu coeficienți și : ∈ ( este câmpul de ordin al lui Galois ). Un număr prim este de ordinea unui subgrup ciclic de puncte de pe o curbă eliptică. Punct - un punct pe o curbă eliptică cu coordonate , care este diferit de origine, dar pentru care punctul coincide cu originea. Cheia secretă este un număr întreg destul de mare . Cheia publică este punctul . $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$

Formarea semnăturii 1. Se generează un număr întreg aleatoriu .

k,0<k<q

2. Calculați coordonatele punctului EC și determinați valoarea , unde este coordonata punctului .

C=kP

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

x_{C}

C

3. Se calculează valoarea , unde .

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

e=H{\bmod {q)}

Semnătura este o pereche de numere . [5]

(R,S)

Verificarea semnăturii

Verificarea semnăturii constă în calcularea coordonatelor punctului CE:

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

și, de asemenea, în determinarea valorii și verificarea egalității . [5] $R'=x_{C}{\bmod {q)}$ $R'=R$

Implementarea protocolului CECP

Fiecare membru al grupului generează o cheie publică a formularului

Q=d_{i}G

, unde este o cheie privată (secretă), .

d_{i}

i=1,2,...,m

Cheia publică colectivă este suma

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

Fiecare membru al grupului generează un număr - o cheie secretă aleatorie unică. Folosind această cheie aleatorie unică, se calculează coordonatele punctului . Rezultatul calculului este trimis tuturor membrilor grupului pentru utilizare colectivă. Se calculează suma $k_i$ $C_{i}=k_{i}G$

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

Valoarea se calculează din suma primită . Fiecare membru al grupului calculează partea sa din semnătură: $R$

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

[3] Verificarea CECP

calculati

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

Rezultatul este calculat

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

Dacă , atunci QEC-ul setului de m utilizatori este autentic, deoarece ar putea fi format numai cu participarea fiecărui utilizator din acest grup, deoarece formarea QEC necesită cheia secretă a fiecăruia dintre participanți [3] . $R'=R$

Implementarea semnăturii multiple pe baza RSA

Schema de semnătură dublă

Schema de semnătură digitală dublă extinde schema convențională RSA . În schema de semnătură digitală dublă, nu se generează o pereche de chei (cheie publică/privată), ci o triplă (două privată și una publică). Prin analogie cu schema obișnuită RSA, participanții aleg o unitate de calcul - produsul a două numere lungi simple. Sunt selectate 2 chei private aleatorii și în intervalul de la 1 la , care vor fi coprime cu , unde este funcția Euler . Cheia publică este generată conform formulei . Valoarea va fi cheia publică. Pentru a semna valoarea , primul participant calculează . Rezultatul calculului este trecut la intrarea celui de-al doilea membru al grupului. Al doilea participant are ocazia să vadă ce va semna. Pentru a face acest lucru, primește valoarea din valoarea . După ce al doilea participant este gata să semneze valoarea , va trebui să calculeze . Verificarea semnăturii se realizează folosind . [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)}$

Extinderea schemei de semnătură dublă la membri $n$

Chei private aleatorii sunt generate . Cheia publică va fi calculată folosind formula . Fiecare participant semnează mesajul M conform formulei . Apoi se calculează valoarea . Verificarea semnăturii se efectuează conform formulei . [6] $n$ $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$

Note

↑ 1 2 Moldovian Nikolay Andreevici, Eremeev Mihail Alekseevici, Galanov Alexey Igorevici. SEMNATURĂ MULTIPLĂ: NOI SOLUȚII BAZATE PE CONCEPTUL DE CHEIE PUBLICĂ COLECTIVĂ (rus.) // Jurnal „Sisteme de informare și control”. - 2008. - Emisiune. 1 .
↑ B. Schneier. Criptografia aplicată (rusă) // John Wiley & Sons. - 1996. - S. 98 . Arhivat din original pe 18 decembrie 2018.
↑ 1 2 3 4 5 6 7 8 9 Nikolai Andreevici Moldovyan, Andrei Alekseevici Kostin, Lidia Viaceslavovna Gortinskaya, Mihail Iurievici Ananiev. IMPLEMENTAREA PROTOCOLULUI DE SEMNATURĂ COLECTIVĂ PE BAZĂ DE STANDARDE EDS (rus.) // Jurnalul „Sisteme de informare și control”. - 2005. Arhivat la 21 noiembrie 2016.
↑ GOST R 34,10–94. Tehnologia de informație. Protecția criptografică a informațiilor. Procese de formare și verificare a semnăturii digitale electronice (rusă) // Gosstandart al Federației Ruse. - 1994. - 25 mai.
↑ 1 2 3 GOST R 34.10–2001. Tehnologia de informație. Protecția criptografică a informațiilor. Procese de formare și verificare a semnăturii digitale electronice (rusă) // Gosstandart al Federației Ruse. - 2001. - 12 septembrie.
↑ 1 2 Mihir Bellare, Gregory Neven. Scheme digitale cu semnături multiple (engleză) // Springer-Verlag Berlin Heidelberg. - 2007. - S. 145-162 . (link indisponibil)

Criptosisteme cu cheie publică

Algoritmi

Factorizarea numerelor întregi	Criptosistemul Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Pupa paye Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Logaritm discret	BLS Cramer - Shoup Protocolul Diffie-Hellman DSA ECDH Curba25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Schimb de chei criptate Schema lui ElGamal schema de semnătură MQV Schema Schnorr VORBIȚI SRP STS
Criptografia pe zăbrele	NTRUEncrypt NTRUSign Schimb de chei bazat pe învățare cu erori Antrenament bazat pe semnătură cu erori în ring FERICIRE Speranța nouă
Alte	AE CEILIDH EPOC Ecuații de câmp ascunse IES Semnătura lui Lampport McEliece Criptosistem de rucsac Merkle-Hellman Criptosistem de rucsac Naccache–Stern Protocol în trei etape XTR

Teorie

Logaritm discret pe o curbă eliptică
Criptografia eliptică
Criptografia bazată pe hash
Criptografia necomutativă
Problema RSA
Funcție unidirecțională cu intrare secretă

Standarde

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Criptografie post cuantică

Subiecte

Semnatura electronica
OAEP
Amprenta
PKI
rețea de încredere
Dimensiunea cheii
Criptografia bazată pe identitate
Criptografia post-cuantică
Card OpenPGP