Elliptinen kryptografia

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 23.11.2021 tarkistetusta versiosta . tarkastukset vaativat 37 muokkausta .

Elliptinen kryptografia on kryptografian haara , joka tutkii epäsymmetrisiä kryptosysteemejä , jotka perustuvat elliptisiin käyriin äärellisten kenttien yli . Elliptisen kryptografian tärkein etu on se, että subeksponentiaalisia diskreettejä logaritmialgoritmeja ei tunneta toistaiseksi .

Neil Koblitz ja Victor Miller ehdottivat itsenäisesti elliptisten käyrien käyttöä kryptosysteemien luomiseen vuonna 1985 [1] .

Johdanto

Vuonna 1985 Neil Koblitz ja Victor Miller ehdottivat itsenäisesti elliptisten käyrien algebrallisten ominaisuuksien käyttöä kryptografiassa . Siitä hetkestä lähtien kryptografian uuden suunnan nopea kehitys alkoi, josta käytetään termiä "elliptisten käyrien kryptografia". Pääsalauksen rooli suoritetaan elliptisen käyrän pisteen skalaarikertoinnilla annetulla kokonaisluvulla, joka määräytyy elliptisen käyrän pisteiden yhteen- ja tuplausoperaatioilla. Jälkimmäiset puolestaan suoritetaan summaus-, kerto- ja inversiooperaatioiden perusteella siinä äärellisessä kentässä, jonka yli käyrää tarkastellaan. Erityisen kiinnostava elliptisen käyrän kryptografia johtuu eduista, joita sen käyttö langattomassa viestinnässä tarjoaa - suuri nopeus ja pieni avaimen pituus [2] . Epäsymmetrinen kryptografia perustuu joidenkin matemaattisten ongelmien ratkaisemisen monimutkaisuuteen. Varhaiset julkisen avaimen salausjärjestelmät, kuten RSA-algoritmi , ovat turvallisia, koska yhdistelmälukua on vaikea sisällyttää alkutekijöihin. Käytettäessä algoritmeja elliptisille käyrille oletetaan, että diskreetin logaritmin ongelman ratkaisemiseksi niiden pisteiden ryhmissä ei ole subeksponentiaalisia algoritmeja . Tässä tapauksessa elliptisen käyrän pisteryhmän järjestys määrittää ongelman monimutkaisuuden. Uskotaan, että saman kryptografisen vahvuuden saavuttamiseksi kuin RSA:ssa tarvitaan pienempien tilausten ryhmiä, mikä vähentää tiedon tallennus- ja lähetyskustannuksia. Esimerkiksi RSA 2005 -konferenssissa National Security Agency ilmoitti luovansa "Suite B:n", joka käyttää vain elliptisiä salausalgoritmeja ja vain 384-bittisiä avaimia käytetään suojaamaan "Top Secret" -luokkaan luokiteltuja tietoja.

Elliptiset käyrät äärellisten kenttien yli

Elliptinen käyrä on joukko pisteitä , jotka täyttävät yhtälön: $(x,y)$

y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6

Tätä yhtälöä voidaan tarkastella mielivaltaisten kenttien ja erityisesti äärellisten kenttien yli , jotka ovat erityisen kiinnostavia kryptografian kannalta.

Krypografiassa elliptisiä käyriä tarkastellaan kahdentyyppisten äärellisten kenttien yli : yksinkertaisten parittomien ominaisuuksien kentät ( , missä on alkuluku) ja ominaisuuden 2 ( ) kentät. $\mathbb {Z} _{p}$ $p>3$ $GF(2^{m})$

Elliptiset käyrät parittomien ominaisuuksien kenttien yli

Ominaiskentän yli elliptisen käyrän E yhtälö voidaan pelkistää muotoon: $\mathbb {Z} _{p}$ $p>3$

E:\quad y^2 = x^3 + Ax + B \pmod p,

missä vakiot tyydyttävät . $A, B \in \mathbb{Z}_p$ $4A^3 + 27B^2 \not\equiv 0 \pmod p$

Kentän päällä olevan elliptisen käyrän E pisteryhmä on E : ssä olevien parien joukko yhdistettynä nollaelementtiin : $\mathbb {Z} _{p}$ $(x,y)$ $\mathcal{O}$

E(\mathbb{Z}_p) = \mathcal{O} \cup \left\{ (x, y) \in \mathbb{Z}_p \times \mathbb{Z}_p | y^2 \equiv x^3 + Ax + B \pmod p \right\}.

On huomattava, että jokaisessa nollasta poikkeavassa elementissä on joko kaksi neliöjuurta tai ei yhtään, joten elliptisen käyrän pisteet on jaettu muodon ja -pareihin . $\mathbb {Z} _{p}$ $(x, y)$ $(x, -y)$

Esimerkki

Tarkastellaan elliptistä käyrää kentän päällä . Erityisesti tällä käyrällä on piste , koska . On helppo tarkistaa, että pisteet , , , ovat kaikki annetun käyrän pisteitä. $y^2 = x^3 + 3x + 2$ $\mathbb {Z} _{5}$ $(1.1)$ $1^2 \equiv 1^3 + 3 \cdot 1 + 2 \pmod 5$ $(1,\pm 1)$ $(1,\pm 4)$ $(2,\pm 1)$ $(2,\pm 4)$

Hassen lause

Hassen elliptisen käyrän lauseessa sanotaan, että elliptisen käyrän pisteiden lukumäärä on lähellä äärellisen kentän kokoa:

(\sqrt p - 1)^2 \leqslant |E(\mathbb{Z}_p)| \leqslant (\sqrt p + 1)^2,

mitä tuo:

\left| |E(\mathbb{Z}_p)|-p\right| < 2\sqrt p + 1.

Elliptiset käyrät ominaisuuden 2 kenttien yli

Ominaisuuden 2 kentässä tarkastellaan kahdenlaisia elliptisiä käyriä:

Supersingulaarinen käyrä $y^2+ay=x^3+bx+c$
Ei-supersingulaarinen käyrä $y^2+axy=x^3+bx^2+c$

Supersingulaaristen elliptisten käyrien erityinen mukavuus on, että niiden järjestys on helppo laskea, kun taas ei-supersingulaaristen käyrien järjestyksen laskeminen on vaikeaa. Supersingulaariset käyrät ovat erityisen käteviä kotitekoisen ECC (Elliptic-curve cryptography) -salausjärjestelmän luomiseen. Voit käyttää niitä ilman aikaa vievää tilauksen laskentaprosessia.

Projektiiviset koordinaatit

Pisteparin summan laskemiseksi elliptisellä käyrällä ei vaadita vain useita yhteen- ja kertolaskuoperaatioita , vaan myös inversiooperaatio , eli tietylle löydökselle , joka on yksi tai kaksi suuruusluokkaa hitaampi kuin kertolasku. Onneksi elliptisen käyrän pisteet voidaan esittää erilaisissa koordinaattijärjestelmissä, jotka eivät vaadi inversion käyttöä pisteiden lisäämisessä: $\mathbb {F} _{q}$ $x \in \mathbb{F}_q$ $y \in \mathbb{F}_q$ $xy = 1$

Projektiivisessa koordinaattijärjestelmässä jokaista pistettä edustaa kolme koordinaattia , jotka täyttävät suhteet: $(x,y)$ $(X,Y,Z)$ $x = \frac{X}{Z}$ , . $y = \frac{Y}{Z}$
Jacobin koordinaatistossa pistettä edustaa myös kolme koordinaattia relaatioiden kanssa: , . $(X,Y,Z)$ $x = \frac{X}{Z^2}$ $y = \frac{Y}{Z^3}$
koordinaattijärjestelmässä Lopez-Dahab (kiinaksi 洛佩斯·達哈卜 / Lopez-Dahab lat.) relaatio täyttyy: , . $x = \frac{X}{Z}$ $y = \frac{Y}{Z^2}$
muokattu Jacobin koordinaattijärjestelmä käyttää 4 koordinaattia samoilla suhteilla. $(X,Y,Z,aZ^4)$
Chudnovsky-Jacobi-koordinaattijärjestelmässä käytetään 5 koordinaattia . $(X,Y,Z,Z^2,Z^3)$

On tärkeää huomata, että nimiä voi olla erilaisia - esimerkiksi IEEE P1363-2000 kutsuu projektitiivisia koordinaatteja, joita yleensä kutsutaan Jacobi-koordinaateiksi.

Salaus/salauksen purku elliptisten käyrien avulla

Ensimmäinen tehtävä tarkasteltavassa järjestelmässä on salata viestin pelkkä teksti , joka lähetetään arvona (Kuinka?) [3] pisteelle . Tässä piste edustaa siihen koodattua tekstiä ja se puretaan myöhemmin. Huomaa, että viestiä ei voi koodata pelkällä koordinaatilla tai pisteellä, koska kaikki tällaiset koordinaatit eivät ole käytettävissä . Kuten avaimenvaihtojärjestelmässä, salaus- ja salauksenpurkujärjestelmissä myös piste ja elliptinen ryhmä katsotaan parametreina . Käyttäjä valitsee yksityisen avaimen ja luo julkisen avaimen . Salatakseen ja lähettääkseen viestin käyttäjälle käyttäjä valitsee satunnaisen positiivisen kokonaisluvun ja laskee salatekstin , joka koostuu pisteparista. $m$ $xy$ ${\displaystyle P_{m))$ ${\displaystyle P_{m))$ $x$ $y$ $E_{p}(a,b)$
$G$ $E_{p}(a,b)$ $A$ $n_{A}$ $P_{A}=n_{A}G$ ${\displaystyle P_{m))$ $B$ $A$ $k$ $G_{m}$

G_{m}=(kG,P_{m}+kP_{B})

. Tässä tapauksessa pari kohtaa.

{\displaystyle G_{m}\neq P_{m},G_{m))

Huomaa, että osapuoli käyttää osapuolen julkista avainta : . Pura tämän salatekstin salaus kertomalla parin ensimmäinen piste salaisella avaimella ja vähentämällä tulos toisesta pisteestä: $A$ $B$ $P_{B}$ $B$ $Huom}$
${\näyttötyyli (P_{m}+kP_{B})-n_{B}(kG)=P_{m}+k(n_{B}G)-n_{B}(kG)=P_{m}+ {\cancel {kn_{B}(G)))-{\cancel {kn_{B}(G)}}=P_{m}}$

Käyttäjä peitti viestin lisäämällä . Kukaan muu kuin tämä käyttäjä ei tiedä :n arvoa , joten vaikka se on julkinen avain, kukaan ei voi paljastaa naamiota . Käyttäjä kuitenkin sisällyttää viestiin myös "vihjeen", joka riittää poistamaan maskin henkilöltä, jolla on yksityinen avain . Viestin palauttamiseksi vastustajan on laskettava tiedoista ja , mikä näyttää olevan vaikea tehtävä [4] . $A$ ${\displaystyle P_{m))$ $kP_{B}$ $k$ $P_{B}$ $kP_{B}$ $A$ $Huom}$ $k$ $G$ $kg$

Elliptisen käyrän pisteiden aritmeettiset operaatiot eivät vastaa näitä koordinaattiensa aritmeettisia operaatioita.

Elliptisen käyrän pisteet äärellisen kentän yli edustavat ryhmää [5] . Kertominen pelkistyy toistuvaan tuplaukseen ja summaukseen.

Esimerkiksi G+G ≠ 2G ( nämä ovat eri operaatioita ), 2G + 2^115G = 2^115G + 2G (summaus on kommutatiivista);

2G = 2*G; 4G = 2*2G; 8G = 2*4G; 16G = 2*8G jne. (kahdelle identtiselle pisteelle - vain tuplaustoiminto);

25*G; 25 = 11001 (binäärimuodossa); 25 = 1*2^0 + 0*2^1 + 0*2^2 + 1*2^3 + 1*2^4 = 1 + 8 + 16; 25G = 16G + 8G + G = 1*(2^4)G + 1*(2^3)G + 1*G (summausoperaatio).

24G/3 = 24G* (3^-1 mod P); missä 3^(-1) mod P - modulaarinen kertova käänteinen ,

5G - 3G = 5G + (-3G); missä -3G = nG - 3G = O - 3G - additiivinen käänteispiste, vastakkainen piste .

Esimerkki

Tarkastellaan tapausta , , joka vastaa käyrää $p=751$ $E_{p}(-1 188)$

y^{2}=x^{3}-x+188

ja .

G=(0,376)

Oletetaan, että käyttäjä on lähettämässä käyttäjälle elliptisellä pisteellä koodatun viestin ja että käyttäjä valitsee satunnaisluvun . Julkinen avain on . Meillä on: $A$ $B$ $P_{m}=(562 201)$ $A$ $k=386$ $B$ $P_{B}=(201.5)$

386(0.376)=(676.558)

(562.201)+386(201.5)=(385.328)

Siten käyttäjän on lähetettävä salateksti . $A$ $(676,558),(385,328)$

Salauksen toteutus

Elliptisen käyrän salausalgoritmien erityiset toteutukset kuvataan alla. Tässä tarkastellaan elliptisen kryptografian yleisiä periaatteita.

Parametrijoukko

Elliptisen kryptografian käyttämiseksi kaikkien osallistujien tulee sopia kaikista elliptistä käyrää määrittävistä parametreista, ts. joukko salausprotokollan parametreja. Elliptinen käyrä määritetään vakioilla ja yhtälöstä (2). Abelin pistealaryhmä on syklinen ja sen antaa yksi generoiva piste G . Tässä tapauksessa kofaktorin , jossa n on pisteen G kertaluku , on oltava pieni ( , mieluiten parillinen ). $a$ $b$ $h = \frac{|E|}{n}$ $h\le4$ $h = 1$

Joten ominaisuuden 2 kentällä parametrien joukko: , ja lopullisen kentän , jossa , parametrien joukko: . $(m,f,a,b,G,n,h)$ $\mathbb {Z} _{p}$ $p>3$ $(p,a,b,G,n,h)$

On olemassa useita suositeltuja parametrijoukkoja:

NIST [6]
SECG [7]

Voit luoda oman parametrijoukon seuraavasti.

Valitse joukko vaihtoehtoja.
Etsi elliptinen käyrä, joka täyttää tämän parametrijoukon.

Käyrän etsimiseen tietylle parametrijoukolle käytetään kahta menetelmää.

Valitse satunnainen käyrä ja käytä sitten pisteenlaskenta-algoritmia [8] [9] .
Valitse pisteet ja rakenna sitten käyrä näistä pisteistä kertolaskutekniikalla.

On olemassa useita kryptografisesti "heikkojen" käyrien luokkia, joita tulisi välttää:

Käyrät yli , missä ei ole alkuluku. Näiden käyrien salaus on herkkä Weylin hyökkäyksille . $\mathbb{F}_{2^m}$ $m$
Käyrät ovat alttiina hyökkäykselle, joka kartoittaa tietyn käyrän pisteet additiivinen kenttäryhmään . $|E(\mathbb{F}_q)| = q$ $\mathbb {F} _{q}$

Nopea pienennys (NIST-käyrät)

Jakomoduuli p (joka on välttämätön yhteen- ja kertolaskussa) voidaan suorittaa nopeammin, jos p valitaan alkuluvuksi lähellä 2:n potenssia. Erityisesti p voi olla Mersennen alkuluku . Esimerkiksi tai ovat hyviä valintoja . National Institute of Standards and Technology (NIST) suosittelee käyttämään samanlaisia alkulukuja kuin p . $p=2^{251} - 1$ $p = 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1$

Toinen NIST:n suosittelemien käyrien etu on valinta , joka nopeuttaa Jacobin koordinaattien yhteenlaskutoimintoa. $a = -3$

NIST:n suosittelemat elliptiset käyrät

NIST suosittelee 15 elliptistä käyrää, joista monet on johtanut Jerry Solinas (NSA) Neil Koblitzin työn perusteella [10] . Erityisesti FIPS 186-3 [11] suosittelee 10 päätekenttää. Jotkut heistä:

kentät , joissa alkuluku p on 192, 224, 256, 384 tai 521 [12] bittiä pitkä , $\mathbb {F} _{p}$
kentät , joissa m = 163, 233, 283, 409 tai 571. $\mathbb{F}_{2^m}$

Lisäksi suositellaan yhtä elliptistä käyrää jokaista äärellistä kenttää kohden. Nämä äärelliset kentät ja elliptiset käyrät valitaan usein virheellisesti korkean turvallisuustason vuoksi. NIST:n mukaan heidän valintansa perusteli ohjelmistototeutuksen tehokkuus [13] . Ainakin muutamien turvallisuudesta on epäilyksiä [14] [15] [16] .

Avaimen koko

Nopein algoritmi, joka ratkaisee diskreetin logaritmiongelman elliptisillä käyrillä, kuten Shanksin algoritmi ja Pollardin ρ-menetelmä , tarvitsee operaatioita. Siksi kentän koon on oltava vähintään kaksi kertaa avaimen koko. Esimerkiksi 128-bittiselle avaimelle on suositeltavaa käyttää elliptistä käyrää kentän päällä , jossa p on 256 bittiä pitkä. $O(\sqrt{n})$ $\mathbb {F} _{p}$

Monimutkaisimmat tähän mennessä julkisesti murtetut elliptisen käyrän piirit ovat sisältäneet 112-bittisen avaimen äärelliselle alkukentälle ja 109-bittisen avaimen ominaisuuden 2 äärelliselle kentälle. . Heinäkuussa 2009 yli 200 Sony Playstation 3 : n klusteri löysi 109-bittisen avaimen 3,5 kuukaudessa. Ominaisuuskentän 2 avain löydettiin huhtikuussa 2004 2 600 tietokoneella 17 kuukauden aikana. .

Diffie-Hellman-avaimenvaihdon analogi

Oletetaan, että tilaajat A ja B haluavat sopia avaimesta, jota he käyttävät myöhemmin jossain klassisessa salausjärjestelmässä. Ensinnäkin he valitsevat avoimesti jonkin äärellisen kentän ja jonkin elliptisen käyrän sen päälle. Niiden avain on rakennettu tämän elliptisen käyrän satunnaisesta pisteestä . Jos niillä on satunnainen piste , niin esimerkiksi sen -koordinaatti antaa satunnaisen elementin , joka voidaan sitten muuntaa -bitiksi kokonaisluvuksi -aarilukujärjestelmässä (jossa ), ja tämä luku voi toimia avaimena heidän klassisissa kryptojärjestelmä. Heidän on valittava kohta niin, että kaikki heidän viestinsä toisilleen ovat avoimia ja silti kukaan muu kuin he kaksi eivät tiedä niistä mitään . $F_q$ $E$ $P$ $P$ $x$ $F_q$ $r$ $s$ $rq=p$ $P$ $P$

Tilaajat (käyttäjät) A ja B valitsevat ensin avoimesti pisteen ∈ "kantapaikaksi"; Sillä on sama rooli kuin generaattori Diffie-Hellman-järjestelmässä äärellisille kentille. Emme kuitenkaan vaadi sen olevan generoiva elementti käyrän pisteryhmässä . Tämä ryhmä ei välttämättä ole syklinen. Vaikka se olisi syklistä, älkäämme tuhlaako aikaa generoivan elementin tarkistamiseen (tai edes N pisteen kokonaismäärän löytämiseen, jota emme seuraavassa tarvitse). Haluamme, että B:n generoima alaryhmä on suuri, mieluiten samaa suuruusluokkaa kuin se itse . Tällä hetkellä oletetaan, että se on avoimesti otettu piste erittäin suuressa järjestyksessä (yhtä kuin joko , tai suuri jakaja ). $B$ $E$ $B$ $q$ $B$ $E$ $B$ $E$ $B$ $E$ $N$ $N$

Avaimen muodostamiseksi valitaan ensin satunnaisesti kokonaisluku , joka on verrattavissa arvoon (joka on lähellä ); hän pitää tämän numeron salassa. Se laskee ∈ ja ohittaa tämän pisteen avoimesti. Tilaaja B tekee samoin: hän valitsee satunnaisesti ja lähettää julkisesti ∈ . Silloin heidän käyttämä salainen avain on ∈ . Molemmat käyttäjät voivat laskea tämän avaimen. Se esimerkiksi tietää (piste välitettiin avoimesti) ja oman salaisuutensa . Kuka tahansa kolmas osapuoli tietää kuitenkin vain ja . Lukuun ottamatta diskreetin logaritmin ongelman ratkaisemista - lähteen ja (tai lähteen ja :n löytäminen ) ei näytä olevan mitään keinoa löytää , tietäen vain ja [17] . $A$ $a$ $q$ $N$ $aB$ $E$ $b$ $bB$ $E$ $P=abB$ $E$ $A$ $bB$ $a$ $aB$ $bB$ $B$ $aB$ $b$ $B$ $bB$ $abB$ $aB$ $bB$

Esimerkki Diffie-Hellman-avaintenvaihdosta

Esimerkkinä otetaan

p=211

. _

E_{p}(0,-4)

joka vastaa käyrää

y^{2}=x^{3}-4

ja .

G=(2,2)

Voidaan laskea, että . Käyttäjän A yksityinen avain on , joten A:n julkinen avain on $241G=$ $\mathcal{O}$ $n_{A}=121$

P_{A}=121(2,2)=(115,48)

Käyttäjän B yksityinen avain on , joten B:n julkinen avain on $n_{B}=203$

203(2,2)=(130,203)

Jaettu salaisuus on

121(130.203)=203(115.48)=(161.69)

Salauksen suojaus elliptisten käyrien avulla

Elliptisen käyrän kryptografisen lähestymistavan tarjoama turvallisuus riippuu siitä, kuinka vaikeaa on ratkaista datasta ja . Tätä ongelmaa kutsutaan yleensä diskreetiksi logaritmiongelmaksi elliptisellä käyrällä. Nopein nykyään tunnettu menetelmä logaritmien ottamiseen elliptisellä käyrällä on ns. Pollard-menetelmä. Taulukossa (katso alla) verrataan tämän menetelmän tehokkuutta seula-alkutekijälaskentamenetelmään yleisessä lukukentässä. Siitä voidaan nähdä, että RSA:han verrattuna elliptisten käyrien kryptografiamenetelmiä käytettäessä saavutetaan suunnilleen sama suojaustaso huomattavasti pienemmillä avaimen pituuksilla. $k$ $kP$ $P$ $s$

Samoilla avainten pituuksilla RSA:n ja elliptisen käyrän salaustekniikan vaatima laskenta ei myöskään eroa paljon. Siten verrattuna RSA:han samalla suojaustasolla selkeä laskennallinen etu kuuluu elliptisiin käyriin perustuvalle kryptografialle, jonka avaimen pituus on lyhyempi [18] .

Taulukko: Elliptisiä käyriä ja RSA:ta käyttävän krypta-analyysin vaatima laskentateho

Logaritmi elliptisellä käyrällä Pollardin -menetelmällä. $s$

Avaimen koko	MIPS vuotta
150	3,8*10^10
205	7,1*10^18
234	1,6*10^28

Kokonaislukujen faktorointi seulamenetelmällä yleisen muodon lukukentässä.

Avaimen koko	MIPS vuotta
512	3*10^4
768	3*10^7
1024	3*10^11
1280	3*10^14
1536	3*10^16
2048	3*10^20

Sähköisen digitaalisen allekirjoituksen rakentaminen elliptisiä käyriä käyttäen

ECDSA ( Elliptic Curve Digital Signature Algorithm) -algoritmi on hyväksytty ANSI X9F1- ja IEEE P1363 -standardeiksi .

Avainten luominen

Elliptinen käyrä on valittu . Siinä olevien pisteiden lukumäärän tulee olla jaollinen suurella alkuluvulla n. $E_{p}(a,b)$
Tilauksen peruspiste valitaan . $G\in E_{p}(a,b)$ $n,n\cdot G=\infty$
Satunnaisluku valitaan . $d\in(1,n)$
Laskettu . $Q=d \cdot G$
Yksityinen avain on d, julkinen avain on monikko <a, b, G, n, Q>.

Allekirjoituksen luominen

Satunnaisluku valitaan . $k\in(1,n)$
ja lasketaan . $k\cdot G=(x_{1},y_{1})$ $r=x_{1}(\operaattorin nimi {mod} n)$
Ehto tarkistetaan , koska muuten allekirjoitus ei riipu yksityisestä avaimesta. Jos r = 0, valitaan toinen satunnaisluku k. $r\neq 0$
Laskettu . $k^{-1}(\operaattorinimi {mod} n)$
Laskettu . $s=k^{-1}\cdot (H(M)+dr)(\operaattorin nimi {mod} n)$
Ehto tarkistetaan , koska tässä tapauksessa allekirjoituksen vahvistamiseen tarvittavaa numeroa ei ole olemassa. Jos s = 0, valitaan toinen satunnaisluku k. $s\neq 0$ $s^{-1}(\operaattorin nimi {mod} n)$

Viestin M allekirjoitus on numeropari (r, s).

Allekirjoituksen vahvistus

Tarkistetaan, että luvut r ja s kuuluvat lukualueeseen (1, n). Muussa tapauksessa varmennustulos on negatiivinen ja allekirjoitus hylätään.
Laske ja H(M). $w=s^{-1}(\operaattorin nimi {mod} n)$
Laske ja . $u_{1}=H(M)w(\operaattorinimi {mod} n)$ $u_{2}=rw(\operaattorinimi {mod} n)$
Laske . $u_{1}G+u_{2}Q=(x_{0},y_{0}),v=x_{0}(\operaattorin nimi {mod} n)$
Allekirjoitus on tosi, jos ja vain jos v = r [19] .

Sovellukset

Suurin osa nykyaikaisen kryptografian kryptosysteemeistä voidaan luonnollisesti "siirtää" elliptisiin käyriin. Perusajatuksena on, että tietyille äärellisille ryhmille käytetty tunnettu algoritmi kirjoitetaan uudelleen käyttämään elliptisten käyrien rationaalisten pisteiden ryhmiä:

ECDSA - algoritmi , joka perustuu EDS :ään ,
Diffie-Hellman- algoritmiin perustuva ECDH -algoritmi ,
ECMQV- algoritmi , joka perustuu MQV :hen , Menezes-Q-Wenstone-avaimen jakeluprotokollaan,
GOST R 34.10-2012 ,
Lenstran kertoimet elliptisten käyrien avulla
kaksois EY DRBG .

On huomattava, että tällaisten digitaalisten allekirjoitusjärjestelmien turvallisuus ei riipu ainoastaan salausalgoritmien kryptografisesta vahvuudesta, vaan myös käytettyjen kryptografisten hajautusfunktioiden ja satunnaislukugeneraattoreiden kryptografisesta vahvuudesta .

Vuoden 2013 katsauksen mukaan yleisimmin käytetyt käyrät ovat nistp256, nistp384, nistp521, secp256k1, secp384r1, secp521r1 [20] .

Muistiinpanot

↑ Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. Johdatus matemaattiseen kryptografiaan . - Springer, 2008. - 524 s. - (Matematiikan perustutkintotekstit). — ISBN 9780387779942 .
↑ Bolotov A. A., Gashkov S. B., Frolov A. B., Chasovskikh A. A. . Johdatus elliptiseen kryptografiaan. 11 s.
↑ Numeroiden koodaus pisteiksi elliptisellä käyrällä äärellisessä kentässä ja niiden salaus ja salauksen purkaminen. . Haettu 29.10.2019.
↑ Zhdanov O.N., Zolotarev V.V. Tietojen kryptografisen suojauksen menetelmät ja keinot. 167 s.
↑ Elliptinen kryptografia: teoria . Haettu 13. lokakuuta 2016.
↑ Suositellut elliptiset käyrät valtion käyttöön
↑ SEC 2: Suositellut elliptisen käyrän verkkoalueen parametrit
↑ Schoofin algoritmi (downlink)
↑ Schoof–Elkies–Atkin-algoritmi
↑ Neal Koblitz. Satunnaiset käyrät: Matemaatikko matkat . - Springer, 2009. - S. 312-313. — 402 s. — ISBN 9783540740780 .
↑ FIPS 186-3 Arkistoitu 7. lokakuuta 2013. // NIST, 2009; poistui käytöstä vuonna 2013 FIPS 186-4:n julkaisun myötä
↑ Tämä järjestys saattaa vaikuttaa virheeltä. Viimeinen arvo on kuitenkin täsmälleen 521, ei 512 bittiä.
↑ Daniel J. Bernstein , Tanja Lange, NIST-käyrien turvallisuusvaarat // 2013.09.16: "Miksi NIST valitsi nämä käyrät? * Useimmat olemme kysyneet: turvallisuus * Todellinen NIST-suunnitteludokumentti: tehokkuus" ( [1] )
↑ Daniel J. Bernstein ja Tanja Lange. SafeCurves: turvallisten käyrien valinta elliptisen käyrän kryptografiaan. (englanniksi) . safecurves.cr.yp.to (18. marraskuuta 2013). Haettu: 20. joulukuuta 2013.
↑ Jevgeni Zolotov . Snowden ja elliptinen krypto: Bitcoinia ja TOR:ta ei epäillä, mutta entä muut projektit? , Computerra (16. syyskuuta 2013). Haettu 20. joulukuuta 2013.
↑ Tohtori Michael Scott, NIST-elliptisten käyrien takaovet Arkistoitu 20. joulukuuta 2013 Wayback Machinessa 24. lokakuuta 2013: "NSA:ssa työskennellyt Jerry Solinas ehdotti itse käyrät."
↑ Chalkin T.A. Zhdanov O.N. Elliptisten käyrien käyttö kryptografiassa.
↑ Zhdanov O.N., Zolotarev V.V. Tietojen kryptografisen suojauksen menetelmät ja keinot. 186 s.
↑ Ishmukhametov Sh.T. Faktorisointimenetelmät luonnollisille lukuille.99 p.
↑ Bos et al, Elliptic Curve Cryptography in Practice // MSR-TR-2013-119, marraskuu 2013

Linkit

Bolotov A.A., Gashkov S.B., Frolov A.B., Chasovskikh A.A. Elliptisen kryptografian algoritmiset perusteet . - Moskova: MEI, 2000. - 100 s.
Bolotov A.A., Gashkov S.B., Frolov A.B., Chasovskikh A.A. Johdatus elliptiseen kryptografiaan. Algebralliset ja algoritmiset perusteet - Moskova: KomKniga, 2006. - 328 s.
Zhdanov O.N., Zolotarev V.V. Tietojen kryptografisen suojauksen menetelmät ja keinot. - Krasnojarsk: "Kaupunki", 2007. - 217 s.
Ishmukhametov Sh.T. Faktorisointimenetelmät luonnollisille lukuille. - Kazan: KFU, 2011. - 190 s.
Koblitz NA Lukuteorian ja kryptografian kurssi - USA: Springer-Verlag, 1994. - 235 s.

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