DSA, Digital Signature Algorithm | |
---|---|
Teremtő | NIST |
Létrehozva | 1991 |
közzétett | 1998 |
Kulcsméret | zárt: 160-256 bit, nyitott: 1024-3072 bit |
Aláírás mérete | két 160-256 bites szám |
DSA ( Digital Signature Algorithm – digitális aláírási algoritmus ) – titkos kulcsot használó titkosítási algoritmus ( egy kulcspárból: <nyilvános; privát>) elektronikus aláírás létrehozására , de nem titkosításra (ellentétben az RSA -val és az ElGamal sémával ). Az aláírás titokban jön létre (privát kulcs), de nyilvánosan ellenőrizhető (nyilvános kulcs). Ez azt jelenti, hogy csak egy alany hozhat létre üzenetaláírást, de bárki ellenőrizheti annak helyességét. Az algoritmus a véges mezők logaritmusának számítási bonyolultságán alapul .
Az algoritmust a National Institute of Standards and Technology ( USA ) javasolta 1991 augusztusában, és szabadalmaztatott [1] (a szabadalom szerzője – David W. Kravitz), a NIST jogdíjmentesen használhatóvá tette ezt a szabadalmat . A DSA a DSS ( Digitális aláírás szabvány) része, amelyet először 1998. december 15-én tettek közzé (FIPS-186 [2] dokumentum ( szövetségi információfeldolgozási szabvány ) . A szabványt többször frissítették [3] [4] , a legújabb verzió a FIPS-186-4 [5] . (2013 július).
A DSA két algoritmust tartalmaz (S, V): üzenetaláírás létrehozására (S) és ellenőrzésére (V).
Mindkét algoritmus először kiszámítja az üzenet kivonatát egy kriptográfiai hash függvény segítségével . Az S algoritmus a hash-t és a titkos kulcsot használja az aláírás létrehozásához, az V algoritmus az üzenetkivonatot, az aláírást és a nyilvános kulcsot használja az aláírás ellenőrzéséhez.
Érdemes hangsúlyozni, hogy valójában nem az üzenet (tetszőleges hosszúságú) van aláírva, hanem annak hash-je (160 - 256 bit), ezért elkerülhetetlenek az ütközések , és egy aláírás általában több azonos hash-es üzenetre érvényes. . Ezért a kellően "jó" hash függvény kiválasztása nagyon fontos az egész rendszer egésze szempontjából. A szabvány első verziója az SHA-1 [6] [2] hash funkciót használta ( Secure Hash Algorithm - safe hashing algorithm ) , a legújabb verzióban az SHA-2 család bármely algoritmusa is használható [6] [5 ] . 2015 augusztusában megjelent a FIPS-202 [7] , amely az új SHA-3 hash függvényt írja le . De ma már nem szerepel a DSS szabványban [5] .
A rendszer megfeleltetési bázist igényel a szerző valós adatai (lehet magánszemély vagy szervezet) és a nyilvános kulcsok , valamint a digitális aláírási séma összes szükséges paramétere (hash függvény, prímszámok ) között. Ilyen alapként például egy tanúsító hatóság szolgálhat .
A digitális aláírási rendszer felépítéséhez a következő lépéseket kell végrehajtania:
Mint fentebb említettük, a digitális aláírási séma elsődleges paramétere a kriptográfiai hash függvény , amelyet az üzenet szövegének olyan számmá alakítására használnak , amelyhez az aláírást számítják. Ennek a függvénynek egy fontos jellemzője a kimeneti sorozat bithossza, amelyet az alábbiakban N jelölünk . A DSS szabvány első változatában az SHA-1 függvény [2] használata javasolt , ennek megfelelően az előjeles szám bithossza 160 bit. Most az SHA-1 már nem elég biztonságos [8] [9] . A szabvány a következő lehetséges értékpárokat határozza meg az L és N számokhoz :
E szabvány szerint az SHA-2 család hash függvényei ajánlottak . Az Egyesült Államok kormányzati szervezeteinek az első három lehetőség valamelyikét kell használniuk, a CA-knak pedig olyan párt kell használniuk, amely egyenlő vagy nagyobb, mint az előfizetők által használt pár [5] . A rendszertervező bármilyen érvényes hash függvényt választhat. Ezért a további figyelem nem egy adott hash függvény használatára összpontosul.
A DSA-alapú kriptorendszer erőssége nem haladja meg a használt hash függvény és a pár erősségét (L,N), amelynek erőssége nem nagyobb, mint az egyes számok erőssége külön-külön. Azt is fontos figyelembe venni, hogy mennyi ideig kell biztonságosnak lennie a rendszernek. Jelenleg a 2010 -ig ( 2030 ) kitartó rendszerekhez 2048 (3072) bites hossz javasolt. [5] [10]
A nyilvános paraméterek számok (p, q, g, y) . Csak egy privát paraméter létezik: az x szám . Ebben az esetben a számok (p, q, g) közösek lehetnek egy felhasználói csoport számára, az x és y számok pedig egy adott felhasználó privát, illetve nyilvános kulcsai. Egy üzenet aláírásakor titkos x és k számokat használunk , és a k számot véletlenszerűen (a gyakorlatban álvéletlenszerűen) kell kiválasztani minden következő üzenet aláírásának számításakor.
Mivel a (p, q, g) több felhasználóra is használható, a gyakorlatban a felhasználókat bizonyos kritériumok alapján gyakran azonos (p, q, g) csoportokra osztják . Ezért ezeket a paramétereket tartományi paramétereknek nevezzük. [5]
Az üzenet aláírása a következő algoritmus szerint [5] történik :
Számításilag összetett műveletek a hatványozás modulo (számítás ), amelyekhez vannak gyors algoritmusok , hash számítás , ahol a bonyolultság függ a választott hash algoritmustól és a bemeneti üzenet méretétől, valamint az inverz elem megtalálása például a kiterjesztett euklideszi segítségével. algoritmus vagy Fermat kis tétele formában .
Az aláírás ellenőrzése a [5] algoritmus szerint történik :
1 Számítás 2 Számítás 3 Számítás 4 Számítás 5 Az aláírás helyes, haHa be van jelölve, a számításilag összetett műveletek két hatványozás , egy hash számítás és az inverz elem megtalálása .
Ez a digitális aláírási séma annyiban helyes, hogy az aláírás valódiságát ellenőrizni kívánó személy hitelesség esetén mindig pozitív eredményt kap. Mutassuk meg:
Először is, ha , akkor Fermat kis tételéből az következik, hogy . Mivel g >1 és q prím, akkor g -nek q modulo p szorzórenddel kell rendelkeznie .
Egy üzenet aláírásához kiszámítja
Ezért
Mivel g q rendű , azt kapjuk
Végül a DSA-séma helyessége abból következik
[5]Nézzünk egy példát arra, hogyan működik az algoritmus kis számok esetén. Legyen üzenetünk hash értéke .
A DSA algoritmus a diszkrét logaritmusok kiszámításának nehézségén alapszik, és a klasszikus ElGamal séma [11] módosítása , ahol hozzáadódik az üzenetkivonat, és az összes logaritmust kiszámítja , ami lehetővé teszi az aláírás rövidebbé tételét az analógokhoz képest. [12] . Az ElGamal séma alapján más algoritmusokat is építettek, például az orosz GOST 34.10-94 , amely mára már elavultnak számít. Ezt a GOST R 34.10-2012 [13] szabvány váltotta fel , amely egy elliptikus görbe pontcsoportját használja .
Egy ilyen módosítás, i.e. az átmenet a multiplikatív csoportból modulo a prímszámból az elliptikus görbe pontjainak csoportjába a DSA- ECDSA [14] ( Elliptic Curve Digital Signature Algorithm – digitális aláírás algoritmus elliptikus görbéken) esetében is létezik . Például a bitcoin kriptovalutában használják tranzakciók megerősítésére. Ez a fordítás lehetővé teszi a kulcsok méretének csökkentését a biztonság feláldozása nélkül - a bitcoin rendszerben a privát kulcs mérete 256 bit, a megfelelő nyilvános kulcs pedig 512 bit.
Egy másik elterjedt nyilvános kulcsú (titkosításra és digitális aláírásra is használt) algoritmus, az RSA (a szerzőkről kapta a nevét: Rivest , Shamir , Adleman ) a nagy számok faktorálásának nehézségén alapszik.
Az algoritmus elleni bármely támadás a következőképpen írható le: a támadó megkapja az összes nyilvános aláírási paramétert és bizonyos párokat (üzenet, aláírás) , és ezzel a készlettel megpróbál érvényes aláírást létrehozni egy olyan új üzenethez, amely nem szerepel a készletben. .
Ezek a támadások feltételesen két csoportra oszthatók - egyrészt a támadó megpróbálhatja visszaszerezni a titkos kulcsot , majd azonnal lehetőséget kap bármilyen üzenet aláírására, másodszor pedig megpróbálhat érvényes aláírást létrehozni egy új üzenethez anélkül, hogy közvetlenül visszaállítja a titkos kulcsot.
A véletlenszerű paraméter egyenletes eloszlása nagyon fontos a rendszer biztonsága szempontjából. Ha több egymást követő paraméterbit ismert egy aláírássorozathoz, akkor a titkos kulcs nagy valószínűséggel visszaállítható. [tizenöt]
A paraméter megismétlése két üzenetnél a rendszer egyszerű feltöréséhez vezet. Ez akkor fordulhat elő, ha rossz pszeudo-véletlenszám-generátort használ . A PlayStation 3 rendszer sérülékenysége lehetővé tette, hogy bármilyen programot aláírjanak a Sony nevében . Az Android bitcoin rendszerének egyes megvalósításaiban a támadó hozzáférhet a pénztárcához. [16] [17] Mindkét példa az ECDSA [14] rendszerét használta .
Ha két üzenethez ugyanazt a paramétert használtuk , akkor az aláírásaik ugyanazt , de eltérőek lesznek , nevezzük őket .
A for kifejezésből kifejezhetjük a teljes összeget :
.
És egyenlő a különböző üzeneteknél:
Innentől könnyen kifejezhető a titkos kulcs :
Egyes digitális aláírási algoritmusokat megtámadhat egy létező hamisítás (egzisztenciális hamisítás) . Ez abban rejlik, hogy egy (egyáltalán véletlenszerű vagy valamilyen szabály szerint létrehozott) aláíráshoz csak nyilvános paraméterek felhasználásával lehet helyes üzenetet készíteni (aminek azonban általában nincs értelme).
A DSA séma esetében az aláírás minden esetben érvényes egy hash-t tartalmazó üzenetre .
Ez az egyik oka a bemeneti üzenet kivonatolásának. Ha a hash függvényt helyesen választjuk meg, a DSA algoritmus védve van ettől a támadástól, mivel a kriptográfiai hash függvény megfordítása (vagyis egy adott lelet esetén , ha ) számításilag nehézkes. [tizennyolc]
az aláírás helyességi feltétele más formában is átírható:
ez az egyenlet ekvivalens (mert a g modulo p szorzási sorrendje egyenlő q-val)
tehát feltételezhetjük, hogy a kulcs visszaállításához a támadónak meg kell oldania egy ilyen alakú egyenletrendszert
de ebben a rendszerben az ismeretlen , és ez minden , ami azt jelenti, hogy az ismeretlenek száma eggyel több, mint az egyenletek, és minden esetben vannak olyanok , amelyek kielégítik a rendszert. Mivel q nagy prímszám, a helyreállításhoz exponenciális számú párra (üzenetre, aláírásra) lesz szükség. [egy]
Megpróbálhat aláírást hamisítani a titkos kulcs ismerete nélkül, vagyis megpróbálhatja megoldani az egyenletet
tekintetében és . Minden rögzített esetén az egyenlet egyenértékű a diszkrét logaritmus kiszámításával. [egy]
A licencfeltételek lehetővé teszik az algoritmus szoftverben és hardverben való megvalósítását. A NIST létrehozta a DSAVS-t [19] ( Eng. The Digital Signature Algorithm Validation System – a digitális aláírási algoritmus ellenőrzésére szolgáló rendszer ). A DSAVS több megfelelőségi tesztmodulból áll, amelyek a rendszer minden egyes összetevőjét a többitől függetlenül tesztelik. Tesztelt megvalósítási összetevők:
A megvalósítás teszteléséhez a fejlesztőnek kérelmet kell benyújtania a megvalósítás tesztelésére a CMT laboratóriumba ( Criptographic Module Testing Laboratory ) . [5]
A DSA-algoritmushoz két prímszám ( és ), ezért prím- vagy pszeudoprímgenerátorra van szükség .
A Shaw-Taylor algoritmust [20] használják prímszámok generálására .
A pszeudoprímeket egy hash függvény segítségével állítják elő, és a Miller-Rabin valószínűségi tesztet használják az elsődlegesség tesztelésére . Egyetlen Luke primalitásteszt hozzáadható hozzá . [5]
A szükséges iterációk száma a felhasznált számok hosszától és az ellenőrző algoritmustól függ [5] :
lehetőségek | csak M-R teszt | M-R teszt + Luke teszt |
---|---|---|
p: 1024 bit
q: 160 bit hiba valószínűsége |
40 | p: 3
q:19 |
p: 2048 bit
q: 224 bit hiba valószínűsége |
56 | p: 3
q:24 |
p: 2048 bit
q: 256 bit hiba valószínűsége |
56 | p: 3
q:27 |
p: 3072 bit
q: 256 bit hiba valószínűsége |
64 | p: 2
q:27 |
Az algoritmushoz véletlen vagy pszeudo-véletlenszám generátor is szükséges. Ez a generátor szükséges egy x privát felhasználói kulcs , valamint egy titkos véletlenszerű paraméter generálásához .
A szabvány különféle módokat kínál pszeudo-véletlen számok generálására blokk titkosítások vagy hash függvények segítségével. [5] [21]