Multipel signatur

Multipel (kollektiv) signatur ( engelsk Aggregate signatur ) - en ordning (protokol) til implementering af en elektronisk signatur (EDS), som giver flere brugere mulighed for at underskrive et enkelt dokument.

En kollektiv signatur giver mulighed for samtidig underskrift af et elektronisk dokument, da det er dannet som et resultat af en enkelt udelelig transformation og ikke kan opdeles i individuelle signaturer; derudover kan den ikke udvides, det vil sige, at der kan indlejres en ekstra signatur af en eller flere personer i den [1] .

Introduktion

Udtrykket "kollektiv signatur" er i overensstemmelse med udtrykket " gruppesignatur ", men disse begreber er forskellige. Gruppens digitale signaturprotokol løser problemet med at gøre det muligt for enhver bruger fra en bestemt gruppe at danne en signatur på vegne af hele gruppen. Gruppe EDS-protokollen regulerer også tilstedeværelsen af specifikke personer, som kan bestemme listen over personer, der har dannet en underskrift (således har sidstnævnte en hypotetisk mulighed for at underskrive for et hvilket som helst af medlemmerne af gruppen). Ved kollektivt arbejde med elektroniske dokumenter er det nødvendigt at kunne underskrive dem af mange brugere [2] . Varianten af ordningen med generering af et sæt individuelle EDS af brugere, der underskriver et elektronisk dokument, har flere udtalte ulemper - en lineær stigning i størrelsen af den kollektive EDS (CEDS) med en stigning i antallet af underskrivere, samt behovet for yderligere kontrol af integriteten og fuldstændigheden af den kollektive digitale signatur for at eliminere muligheden for at erstatte antallet og navnesammensætningen på de deltagere, der underskrev dokumentet [1] .

Konceptet med en delt offentlig nøgle

På baggrund af deltagernes offentlige nøgler genereres en kollektiv offentlig nøgle, som gør det muligt at udvikle og verificere ægtheden af en samlet elektronisk digital signatur. Den delte offentlige nøgle er underlagt en række begrænsninger med hensyn til størrelse, integritet, uafhængighed af brugere, samtidig generering af den delte offentlige nøgle og kontinuitet. Med andre ord er det umuligt at beregne en gyldig CECP fra CECP for ethvert andet sæt deltagere fra sættet af nuværende, CECP er ikke bundet til sammensætningen af deltagere - enhver bruger kan danne en gruppe og udvikle deres egen CECP. Den kollektive offentlige nøgle, en funktion af brugernes offentlige nøgler, er det grundlag, som hele den kollektive signaturprotokol er bygget på [3] .

QECP er udviklet i overensstemmelse med ovenstående krav ved hjælp af algoritmer, hvis stabilitet er sikret af følgende beregningsmæssigt vanskelige problemer: diskret logaritme i en multiplikativ gruppe af stor prime orden , ekstraktion af rødder af en stor prime grad modulo en stor primtal, diskret logaritme i gruppe af punkter i en elliptisk kurve af en speciel form [3] .

Implementering af protokoller baseret på EDS-standarder

EDS-standard - GOST R 34.10−94

Ifølge standarden GOST R 34.10−94 [4] pålægges der restriktioner på det anvendte primtal p. Kapaciteten af et primtal p i binær repræsentation: bit eller bit. Tallet skal indeholde en stor primtal divisor , således at for eller for . For at generere og verificere en EDS , bruges et tal således , at hvor er generatoren af en undergruppe af en tilstrækkelig stor prime-ordre . $510\leq |p|\leq 512$ $1022\leq |p|\leq 1024$ $(s-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$

EDS-beregningsalgoritme 1. Et tilfældigt tal genereres .

k,1<k<q

2. Værdien beregnes , som er den første del af signaturen.

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

3. Ifølge GOST R 34.11–94 beregnes en hash-funktion ud fra den meddelelse, der signeres.

H

4. Den anden del af signaturen beregnes: , hvor er den hemmelige nøgle. Hvis , gentages signaturgenereringsproceduren.

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

z

S=0

EDS-godkendelsesalgoritme 1. Opfyldelsen af betingelserne og er verificeret . Hvis betingelserne ikke er opfyldt, er underskriften ikke gyldig.

r<q

s<q

2. Værdien beregnes

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

, hvor er den offentlige nøgle for den bruger, der genererede signaturen, der skal verificeres.

y

3. Værdierne og sammenlignes . Hvis , så er signaturen gyldig

R

R'

R=R'

Implementering af CECP-protokollen

Hver bruger genererer en offentlig nøgle af formen , hvor er en privat (hemmelig) nøgle, = , , … , . $jeg$ $y_{i}=\alpha ^{z_{i}}{\bmod {p}}$ $z_{i}$ $jeg$ $en$ $2$ $m$

Den kollektive offentlige nøgle er produktet

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

Hver bruger vælger en tilfældig hemmelig nøgle , et tal, der kun bruges én gang. $k_i$

Beregnet

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

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

R_i

er tilgængelig for alle teammedlemmer, der udvikler CECP

Derefter beregner hvert af teammedlemmerne, der udvikler KECP, i henhold til værdien og resultatet bestemt af ham $R_i$ $H$

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

S_{i}

- en del af underskriften.

Den kollektive signatur vil være et værdipar , hvor er summen af alle modulo [3] . $(S,R)$ $S$ $S_{i}$ $q$

Verifikation af en kollektiv elektronisk digital signatur

Verifikation af den kollektive underskrift udføres i henhold til formlen

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

Hvis , så er CEC for sættet af brugere ægte, da det kun kunne dannes med deltagelse af hver bruger fra denne gruppe, da dets dannelse kræver brug af den hemmelige nøgle for hver af dem. Bemærk, at værdierne bliver autentificeret automatisk, når den kollektive digitale signatur er autentificeret. Hvis en ubuden gæst forsøger at erstatte nogen af disse værdier eller erstatte dem med tidligere brugte værdier, vil kendsgerningen af interferens med protokollen straks blive opdaget, når den digitale signatur godkendes , dvs. Størrelsen af QECP afhænger naturligvis ikke af [3] . $R=R'$ $m$ $R_i$ $R'\neq R$ $m$

Bevis for rigtigheden af den foreslåede CECP-algoritme

Erstat den opnåede signatur i ligningen - et par (R,S), hvor R er produktet af R i modulo q, S er summen af Si modulo q : ligning , reguleret af standarden 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}^{\ 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}}\ højre]{\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}}$

Mulighed for forfalskning af CECP

For krænkere er kompleksiteten af at forfalske CECP naturligvis bestemt af kompleksiteten i at forfalske den individuelle signatur fra et individuelt medlem af gruppen. Der opstår muligheder for brugere, der kombinerer deres bestræbelser for at danne et CECP relateret til et kollektiv, som udover dem omfatter en eller flere andre brugere, som ikke er underrettet om dette (beviset for begge tilfælde er ens). Lad m-1- brugere ønsker at danne en QEDP, der kan verificeres med en delt offentlig nøgle , hvor , det vil sige, brugere kombinerer deres indsats for at danne et par tal, således at . Det vil sige, de kan forfalske en offentlig nøglesignatur , det vil sige beregne værdierne af og som opfylder ligningen . Dette indebærer muligheden for at forfalske en digital signatur i den grundlæggende EDS-ordning, da den har en tilfældig værdi [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^{*}$

Et angreb på beregningen af den hemmelige nøgle for en anden medejer af CECP

Lad - være den digitale signatur genereret af den -th bruger til dokumentet svarende til hash-funktionen (angrebet udføres af brugere). Så er følgende sandt: Angribere genererer tilfældige værdier og beregner . for . Derefter beregnes de parametre og , der opfylder ligningerne , hvor . Ved at indføre betegnelsen . Vi har , hvor og . Det betyder, at angriberne har opnået den korrekte værdi af den kollektive signatur , som de og en anden bruger, der har den offentlige nøgle, deltager i . Ifølge antagelsen kan angriberne ud fra den modtagne kollektive signatur beregne den hemmelige nøgle . Det er let at få ud fra udtrykket for og formlen : . Angriberne beregnede den hemmelige nøgle for brugeren ved hjælp af hans individuelle EDS, genereret inden for rammerne af den grundlæggende EDS-algoritme. Dette beviser forslaget om, at den foreslåede CECP-protokol ikke reducerer styrken af den underliggende EDS-algoritme. [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$

EDS-standard - GOST R 34.10−2001

Ifølge standarden GOST R 34.10−2001 [5] pålægges der restriktioner på det anvendte primtal , primtal og punkt . Et primtal er modulet af en elliptisk kurve (EC), som er givet i det kartesiske koordinatsystem ved en ligning med koefficienter og : ∈ ( er Galois ordensfelt ) . Et primtal er rækkefølgen af en cyklisk undergruppe af punkter på en elliptisk kurve. Punkt - et punkt på en elliptisk kurve med koordinater , som er forskellig fra oprindelsen, men hvor punktet falder sammen med oprindelsen. Den hemmelige nøgle er et ret stort heltal . Den offentlige nøgle er punkt . $s$ $q$ $G$ $s$ $y^{2}=x^{3}+ax+b{\bmod {p}}$ $-en$ $b$ $a,b$ $GF_{p}$ $GF_{p}$ $s$ $q$ $G$ $(x_{G},y_{G})$ $qG$ $d$ $Q=dG$

Signaturdannelse 1. Et tilfældigt heltal genereres .

k,0<k<q

2. Beregn koordinaterne for EC-punktet og bestem værdien , hvor er koordinaten for punktet .

C=kP

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

x_{C}

C

3. Værdien beregnes , hvor .

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

e=H{\bmod {q))

Signaturen er et par tal . [5]

(R,S)

Signaturbekræftelse

Signaturverifikation består i at beregne koordinaterne for EF-punktet:

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

og også i værdifastsættelse og lighedskontrol . [5] $R'=x_{C}{\bmod {q))$ $R'=R$

Implementering af CECP-protokollen

Hvert medlem af gruppen genererer en offentlig nøgle til formularen

Q=d_{i}G

, hvor er en privat (hemmelig) nøgle, .

d_{i}

i=1,2,...,m

Den kollektive offentlige nøgle er summen

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

Hvert medlem af gruppen genererer et nummer - en engangs tilfældig hemmelig nøgle. Ved at bruge denne tilfældige engangsnøgle beregnes koordinaterne for punktet . Resultatet af beregningen sendes til alle medlemmer af gruppen til fælles brug. Summen er beregnet $k_i$ $C_{i}=k_{i}G$

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

Værdien beregnes ud fra det modtagne beløb . Hvert medlem af gruppen beregner deres del af signaturen: $R$

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

[3] Kontrollerer CECP

Beregn

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

Resultatet er beregnet

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

Hvis , så er QEC for sættet af m brugere ægte, da det kun kunne dannes med deltagelse af hver bruger fra denne gruppe, da dannelsen af QEC kræver den hemmelige nøgle for hver af deltagerne [3] . $R'=R$

Implementering af multiple signatur baseret på RSA

Dobbeltsignaturskema

Den dobbelte digitale signaturordning udvider den konventionelle RSA -ordning . I det dobbelte digitale signaturskema genereres ikke et par nøgler (offentlig / privat nøgle), men en tredobbelt (to private og en offentlig). I analogi med den sædvanlige RSA-ordning vælger deltagerne en beregningsenhed - produktet af to simple lange tal. 2 tilfældige private nøgler er valgt og i området fra 1 til , som vil være coprime med , hvor er Euler - funktionen . Den offentlige nøgle genereres i henhold til formlen . Værdien vil være den offentlige nøgle. For at underskrive værdien beregner den første deltager . Resultatet af beregningen videregives til input fra det andet medlem af gruppen. Den anden deltager har mulighed for at se, hvad han vil skrive under på. For at gøre dette får den værdien fra værdien . Når den anden deltager er klar til at underskrive værdien , skal han beregne . Signaturverifikation udføres ved hjælp af . [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))$

Udvidelse af dobbeltsignaturordningen til medlemmer $n$

Tilfældige private nøgler genereres . Den offentlige nøgle vil blive beregnet ved hjælp af formlen . Hver -te deltager underskriver beskeden M i henhold til formlen . Derefter beregnes værdien . Signaturverifikation udføres i henhold til formlen . [6] $n$ ${\displaystyle k_{1},k_{2},...,k_{n))$ $\left(k_{1}+k_{2}+...+k_{n}\right)*t=1{\bmod {\varphi }}(n)$ $jeg$ $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$

Noter

↑ 1 2 Moldovianske Nikolay Andreevich, Eremeev Mikhail Alekseevich, Galanov Alexey Igorevich. FLERE SIGNATUR: NYE LØSNINGER BASEREDE PÅ KONCEPTET OM EN KOLLEKTIV OFFENTLIG NØGLE (rus.) // Journal "Informations- og kontrolsystemer". - 2008. - Udgave. 1 .
↑ B. Schneier. Anvendt kryptografi (russisk) // John Wiley & Sons. - 1996. - S. 98 . Arkiveret fra originalen den 18. december 2018.
↑ 1 2 3 4 5 6 7 8 9 Nikolay Andreevich Moldovyan, Andrey Alekseevich Kostin, Lidia Vyacheslavovna Gortinskaya, Mikhail Yurievich Ananiev. IMPLEMENTERING AF PROTOKOLLEN FOR KOLLEKTIV SIGNATUR BASEREDE PÅ EDS STANDARDER (rus.) // Journal "Information and Control Systems". - 2005. Arkiveret 21. november 2016.
↑ GOST R 34,10–94. Informationsteknologi. Kryptografisk beskyttelse af information. Processer til dannelse og verifikation af elektronisk digital signatur (russisk) // Gosstandart i Den Russiske Føderation. - 1994. - 25. maj.
↑ 1 2 3 GOST R 34.10–2001. Informationsteknologi. Kryptografisk beskyttelse af information. Processer til dannelse og verifikation af elektronisk digital signatur (russisk) // Gosstandart i Den Russiske Føderation. - 2001. - 12. september.
↑ 1 2 Mihir Bellare, Gregory Neven. Digital Multi Signature Schemes (engelsk) // Springer-Verlag Berlin Heidelberg. - 2007. - S. 145-162 . (utilgængeligt link)

Offentlig nøgle kryptosystemer

Algoritmer

Faktorisering af heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalingsmodtager Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritme	BLS Cramer - Shoup Diffie-Hellman protokol DSA ECDH Kurve25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypteret nøgleudveksling Ordning af ElGamal underskriftsordning MQV Schnorr ordning SPEKE SRP STS
Kryptografi på gitter	NTRUEncrypt NTRUSign Læringsbaseret nøgleudveksling med fejl Signaturbaseret træning med fejl i ringen LYKKELIGHED Nyt håb
Andet	AE CEILIDH EPOC Skjulte feltligninger IES Lamports underskrift McEliece Merkle-Hellman rygsæk kryptosystem Naccache-Stern rygsæk kryptosystem Tre trins protokol XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Post kvantekryptering

Emner

Elektronisk signatur
OAEP
Fingeraftryk
PKI
web af tillid
Nøglestørrelse
Identitetsbaseret kryptografi
Postkvantekryptografi
OpenPGP-kort