DSA

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2016. szeptember 12-én felülvizsgált verziótól ; az ellenőrzések 76 szerkesztést igényelnek .
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).  

Az algoritmus leírása

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 .

Digitális aláírási séma opciók

A digitális aláírási rendszer felépítéséhez a következő lépéseket kell végrehajtania:

  1. A H(x) kriptográfiai hash függvény kiválasztása .
  2. Olyan q prímszám kiválasztása, amelynek N dimenziója bitben megegyezik a H(x) hash értékek bitben mért dimenziójával .
  3. Olyan p prímszám kiválasztása , hogy (p-1) osztható q -val . A p bithosszt L jelöli .
  4. Egy g ( ) szám kiválasztása úgy, hogy a modulo p szorzórendje egyenlő q -val . Kiszámításához használhatja a képletet , ahol h  egy tetszőleges szám , így . A legtöbb esetben a h = 2 érték kielégíti ezt a követelményt. [5]

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 :

  1. L = 1024, N = 160
  2. L = 2048, N = 224
  3. L = 2048, N = 256
  4. L = 3072, N = 256

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]

Nyilvános és privát kulcsok

  1. A titkos kulcs egy szám
  2. A nyilvános kulcs kiszámítása a képlet segítségével történik

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]

Üzenet aláírása

Az üzenet aláírása a következő algoritmus szerint [5] történik :

  1. Véletlen szám kiválasztása
  2. számítás
  3. Másik k választása ha
  4. számítás
  5. Másik k választása ha
  6. Az aláírás egy teljes hosszúságú pár

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 .

Aláírás ellenőrzése

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, ha

Ha 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 .

A séma helyessége

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]

Munka példa

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 .

Paraméter generálás

  1. hash hossza , így választhat
  2. választani , mert
  3. választ

Kulcsok létrehozása

  1. válasszon titkos kulcsként
  2. majd a nyilvános kulcsot

Üzenet aláírása

  1. választ
  2. akkor
  3. , lépj tovább
  4. , ahol figyelembe veszik, hogy
  5. , lépj tovább
  6. az aláírás egy számpár

Aláírás ellenőrzése

  1. megkapta, ami azt jelenti, hogy az aláírás helyes.

Analógok

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: RivestShamir , Adleman ) a nagy számok faktorálásának nehézségén alapszik.

Kriptográfiai erősség

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.

Véletlenszerű paraméter kiszámíthatósága

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 :

Egzisztenciális hamisítás

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]

Kulcs-helyreállítás

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]

Aláírás-hamisítás

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]

Algoritmusmegvalósítás-ellenőrző rendszer

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:

  1. Domain paraméterek generálása
  2. Domainbeállítások ellenőrzése
  3. Nyilvános-privát kulcspár generálása
  4. Hozzon létre egy aláírást
  5. Aláírás ellenőrzése

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]

Prímszám generálás

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

Véletlenszám generálás

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]

Jegyzetek

  1. 123 US 5231668 A szabadalom .
  2. 123 FIPS 186-1 . _
  3. FIPS 186-2 .
  4. FIPS 186-3 .
  5. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 FIPS 186-4 .
  6. 12 FIPS 180-4 .
  7. FIPS 202 .
  8. Ütközések keresése a teljes SHA-1-ben .
  9. Szabadindítású ütközés a teljes SHA-1-hez .
  10. NIST speciális kiadvány 800-57 .
  11. Elgamal, 1985 .
  12. C. P. Schnorr. Hatékony azonosítás és aláírások intelligens kártyákhoz  //  Advances in Cryptology - CRYPTO' 89 Proceedings / Gilles Brassard. – New York, NY: Springer, 1990. – P. 239–252 . - ISBN 978-0-387-34805-6 . - doi : 10.1007/0-387-34805-0_22 . Az eredetiből archiválva : 2022. április 12.
  13. GOST R 34.11-2012
  14. 1 2 Az elliptikus görbe digitális aláírási algoritmusa (ECDSA) .
  15. A digitális aláírás algoritmusának bizonytalansága részlegesen ismert hiányosságokkal .
  16. ECDSA – Alkalmazási és megvalósítási hibák .
  17. Elliptikus görbe kriptográfia a gyakorlatban .
  18. Biztonsági érvek a digitális aláírásokhoz és a vak aláírásokhoz .
  19. A digitális aláírás algoritmus-ellenőrző rendszere .
  20. Erős prímszámok generálása .
  21. Véletlenszám generálás .

Irodalom

Szabványok és szabadalmak

Cikkek