Elliptisten käyrien DSA eli ECDSA

ec-spekulantti

Onko kukaan koettanut toteuttaa ECDSA-menetelmän mukaisen digitaalisen allekirjoituksen PHP:llä? Löytyykö valmista PHP-koodia? Mielessä on lähinnä "alkulukukenttä" mutta voi harkita myös "binääristä" toteutusta.

Lähinnä kiinnostaisi tehokas "point multiplication" ja modulaarisen inverssin laskenta. Ja tämä siis pitäisi toimia palvelimella ilman häiritsevän suurta viivettä noin 200-300 bittisenä.

Idea sellainen että nettisaitissa tarkistetaan käyttäjän sisäänkirjautuessa julkista avainta käyttäen lisenssitiedosto jossa on salaisella avaimella tehty digitaalinen allekirjoitus. Jos tiedosto puuttuu tai digitaalinen allekirjoitus ei täsmää selkokielisten tietojen kanssa, niin sitten softan lisenssi ei ole kondiksessa.

ECDSA valittu koska se on moderni ja allekirjoitus menee pienempään tilaan kuin RSA:lla. ECDSA-menetelmän teoreettiset perusteet alkavat olla perustasolla hanskassa, mutta toteutuksen käytännön toimintanopeus on vielä mysteeri.

Turvatasoa voidaan laskea eli bittimäärää pudottaa turvallisena pidetystä pakon edessä, hitauden vähentämiseksi. Jos koodi on asiakkaan koneella niin pääseehän ne sen kuitenkin ohittamaan kommentoimalla koko tarkistuksen pois koodista. Jos on omalla palvelimella niin sinne ei vieras helpolla pääse sisältöä tutkimaan. Mutta hienoa toki olisi jos saisi toimimaan esim. normaalina 256-bittisenä riittävän nopeasti. Eihän sen salamannopea tarvitse olla koska sisäänkirjautuminen kuitenkin kestää jonkin verran.

4

362

    Vastaukset

    Anonyymi (Kirjaudu / Rekisteröidy)
    5000
    • algebrikko

      Eikös ole helpointa implementoida algoritmit ja kokeilla niiden nopeutta? En tunne kovinkaan paljoa kryptografiaa, mutta modulaariset inverssit saa laskettua kätevästi laajennetin Eukleideen algoritmin avulla. Point multiplication ei ole kauhean tuttua minulle, mutta voit kokeilla, josko Montgomeryn algoritmi olisi tarpeeksi nopea. Jos kerran teoreettiset perusteet on hallussa, niin ei kai sen aikavaativuuden laskeminen niin työlästä ole. Itse en ECDSA:ta tunne.

      • ec-spekulantti

        Olen tehnyt yksinkertaisen ECDSA-kokeilukoodin NIST:in 192-bittisellä käyrällä P-192. Turvataso on vain puolet tästä bittimäärästä, eli ei ehkä ihan murtovarma enää nykyisin, mutta minulle tässä vaiheessa riittävä.

        Siinä myös pisteen laskenta on melkoisen yksinkertainen, mutta ei se silti kauhea tehosyöppö ole. Pariksi sekunniksi CPU Usage lyö tappiin eli sataan prossaan kun sen ajaa omalla koneella.

        Fiksummalla laskennalla sitä pystyy vielä oleellisesti keventämään, melko helpostikin. ECDSA:ssa generaattoripiste on vakio sen jälkeen kun käyrä on valittu, joten kaikki tarvittavat tuplapisteet ovat myös vakioita, joten pisteen tuplaukset pystyy laskemaan etukäteen. Tällöin "kalliita" pisteen tuplauksia (point doubling) ei tarvitse laskea digitaalista allekirjoitusta verifioitaessa, vaan voi käyttää etukäteen laskettuja arvoja.

        Kaikkiaan luulenpa että tästä tulee vielä soiva peli.

        Jos joku on ECC-menetelmistä kiinnostunut niin netistä löytää hyvän johdatuksen EC:n perusteisiin googlettamalla "certicom ecc tutorial". Certicom:in sivulla on myös Java-appletteja joilla voi kokeilla pienillä esimerkeillä. Sivusto näyttää ensin pieneltä, mutta siinä on "potkua" yllättävän paljon, joten kannattaa perehtyä huolella. Tämä siis havainnollista periaatteita hyvin pienillä esimerkeillä, jotka eivät ole sellaisenaan kryptografiassa käyttökelpoisia.

        Hyvä kompakti, nykyaikainen kirja ECC:n käytännön toteutuksen yksityiskohtiin on "Guide to Elliptic Curve Cryptography", Hankerson-Menezes-Vanstone. Errata-sivut löytyvät netistä.

        Enkku-Wikipedian kryptografiaa koskevat artikkelit kuten
        http://en.wikipedia.org/wiki/Elliptic_curve_cryptography
        ovat myös hyviä. Tuossa artikkelissa on myös linkit suositeltuihin elliptisiin käyriin jos ei halua generoida omia elliptisiä käyriä.
        Esim. "NIST, Recommended Elliptic Curves for Government Use"


      • ec-spekulantti
        ec-spekulantti kirjoitti:

        Olen tehnyt yksinkertaisen ECDSA-kokeilukoodin NIST:in 192-bittisellä käyrällä P-192. Turvataso on vain puolet tästä bittimäärästä, eli ei ehkä ihan murtovarma enää nykyisin, mutta minulle tässä vaiheessa riittävä.

        Siinä myös pisteen laskenta on melkoisen yksinkertainen, mutta ei se silti kauhea tehosyöppö ole. Pariksi sekunniksi CPU Usage lyö tappiin eli sataan prossaan kun sen ajaa omalla koneella.

        Fiksummalla laskennalla sitä pystyy vielä oleellisesti keventämään, melko helpostikin. ECDSA:ssa generaattoripiste on vakio sen jälkeen kun käyrä on valittu, joten kaikki tarvittavat tuplapisteet ovat myös vakioita, joten pisteen tuplaukset pystyy laskemaan etukäteen. Tällöin "kalliita" pisteen tuplauksia (point doubling) ei tarvitse laskea digitaalista allekirjoitusta verifioitaessa, vaan voi käyttää etukäteen laskettuja arvoja.

        Kaikkiaan luulenpa että tästä tulee vielä soiva peli.

        Jos joku on ECC-menetelmistä kiinnostunut niin netistä löytää hyvän johdatuksen EC:n perusteisiin googlettamalla "certicom ecc tutorial". Certicom:in sivulla on myös Java-appletteja joilla voi kokeilla pienillä esimerkeillä. Sivusto näyttää ensin pieneltä, mutta siinä on "potkua" yllättävän paljon, joten kannattaa perehtyä huolella. Tämä siis havainnollista periaatteita hyvin pienillä esimerkeillä, jotka eivät ole sellaisenaan kryptografiassa käyttökelpoisia.

        Hyvä kompakti, nykyaikainen kirja ECC:n käytännön toteutuksen yksityiskohtiin on "Guide to Elliptic Curve Cryptography", Hankerson-Menezes-Vanstone. Errata-sivut löytyvät netistä.

        Enkku-Wikipedian kryptografiaa koskevat artikkelit kuten
        http://en.wikipedia.org/wiki/Elliptic_curve_cryptography
        ovat myös hyviä. Tuossa artikkelissa on myös linkit suositeltuihin elliptisiin käyriin jos ei halua generoida omia elliptisiä käyriä.
        Esim. "NIST, Recommended Elliptic Curves for Government Use"

        Tarvittavan suurten kokonaislukujen aritmetiikan toteutin ihan vaan PHP:ssä nykyisin vakiona tulevilla BC Math -funktioilla.

        http://fi2.php.net/manual/en/ref.bc.php

        Ei varmaan mikään maailman tehokkain ratkaisu, mutta mielestäni tässä vaiheessa riittävä. GMP voisi olla parempi, mutta vaatisi lisäosan PHP:hen.

        http://fi2.php.net/manual/en/book.gmp.php

        Tarvittavat erikoisfunktiot pystyy tekemään itsekin.


      • ec-spekulantti
        ec-spekulantti kirjoitti:

        Olen tehnyt yksinkertaisen ECDSA-kokeilukoodin NIST:in 192-bittisellä käyrällä P-192. Turvataso on vain puolet tästä bittimäärästä, eli ei ehkä ihan murtovarma enää nykyisin, mutta minulle tässä vaiheessa riittävä.

        Siinä myös pisteen laskenta on melkoisen yksinkertainen, mutta ei se silti kauhea tehosyöppö ole. Pariksi sekunniksi CPU Usage lyö tappiin eli sataan prossaan kun sen ajaa omalla koneella.

        Fiksummalla laskennalla sitä pystyy vielä oleellisesti keventämään, melko helpostikin. ECDSA:ssa generaattoripiste on vakio sen jälkeen kun käyrä on valittu, joten kaikki tarvittavat tuplapisteet ovat myös vakioita, joten pisteen tuplaukset pystyy laskemaan etukäteen. Tällöin "kalliita" pisteen tuplauksia (point doubling) ei tarvitse laskea digitaalista allekirjoitusta verifioitaessa, vaan voi käyttää etukäteen laskettuja arvoja.

        Kaikkiaan luulenpa että tästä tulee vielä soiva peli.

        Jos joku on ECC-menetelmistä kiinnostunut niin netistä löytää hyvän johdatuksen EC:n perusteisiin googlettamalla "certicom ecc tutorial". Certicom:in sivulla on myös Java-appletteja joilla voi kokeilla pienillä esimerkeillä. Sivusto näyttää ensin pieneltä, mutta siinä on "potkua" yllättävän paljon, joten kannattaa perehtyä huolella. Tämä siis havainnollista periaatteita hyvin pienillä esimerkeillä, jotka eivät ole sellaisenaan kryptografiassa käyttökelpoisia.

        Hyvä kompakti, nykyaikainen kirja ECC:n käytännön toteutuksen yksityiskohtiin on "Guide to Elliptic Curve Cryptography", Hankerson-Menezes-Vanstone. Errata-sivut löytyvät netistä.

        Enkku-Wikipedian kryptografiaa koskevat artikkelit kuten
        http://en.wikipedia.org/wiki/Elliptic_curve_cryptography
        ovat myös hyviä. Tuossa artikkelissa on myös linkit suositeltuihin elliptisiin käyriin jos ei halua generoida omia elliptisiä käyriä.
        Esim. "NIST, Recommended Elliptic Curves for Government Use"

        Melko paljon tilaa koodissa tosin vievät esilasketut tuplatut pisteet, koska niitä täytyy olla sama määrä kuin kertojassa on bittejä. Tässä P-192 esimerkissä täytynee laskea valmiiksi 191 tai 192 tuplattua pistettä joista jokaisen koordinaatit voivat olla pari 10-järjestelmässä noin 58-numeroa pitkiä kokonaislukuja. Pisteiden X- ja Y-koordinaatit sisältävästä 2-ulotteisesta taulukosta tulee siis kohtalaisen iso. Tässäpä on puuhaa hetkeksi aikaa :-)


    Ketjusta on poistettu 0 sääntöjenvastaista viestiä.

    Luetuimmat keskustelut

    1. Mitä siellä ABC on tapahtunut

      Tavallista isompi operaatio näkyy olevan kyseessä.
      Alajärvi
      163
      6512
    2. Kuvaile elämäsi naista

      Millainen hän on? Mikä tekee hänestä sinulle erityisen?
      Ikävä
      53
      1903
    3. Klaukkalan onnettomuus 4.4

      Klaukkalassa oli tänään se kolmen nuoren naisen onnettomuus, onko kellään mitään tietoa mitä kävi tai ketä onnettomuudes
      Nurmijärvi
      44
      1630
    4. Kuvaile elämäsi miestä

      Millainen hän on? Mikä tekee hänestä sinulle erityisen?
      Ikävä
      54
      1142
    5. Ukraina ja Zelenskyn ylläpitämä sota tuhoaa Euroopan, ei Venäjä

      Mutta tätä ei YLE eikä Helsingin Sanomat kerto.
      Maailman menoa
      327
      1069
    6. Kolari Klaukkala

      Kaksi teinityttö kuoli. Vastaantulijoille ei käynyt mitenkään. Mikä auto ja malli telineillä oli entä se toinen auto? Se
      Nurmijärvi
      49
      1019
    7. Ooo! Kaija Koo saa kesämökille öky-rempan:jättimäinen terde, poreallas... Katso ennen-jälkeen kuvat!

      Wow, nyt on Kaija Koon mökkipihalla kyllä iso muutos! Miltä näyttää, haluaisitko omalle mökillesi vaikkapa samanlaisen l
      Kesämökki
      13
      980
    8. Kevyt on olo

      Tiedättekö, että olo kevenee kummasti, kun päästää turhista asioista tai ihmisistä irti! Tämä on hyvä näin <3
      Ikävä
      84
      918
    9. Olisinpa jo siellä, otatkohan minut vastaan

      Olisitpa lähelläni ja antaisit minun maalata sinulle kuvaa siitä kaikesta ikävästä, tuskasta, epävarmuudesta ja mieleni
      Ikävä
      79
      908
    10. Toivoisin, että lähentyisit kanssani

      Tänään koin, että välillämme oli enemmän. Kummatkin katsoivat pidempään kuin tavallisesti toista silmiin. En tiedä mistä
      Ikävä
      14
      897
    Aihe