ECDSA

էլիպտիկ կորի թվային ստորագրության ալգորիթմ (ECDSA), Թվային ստորագրության ալգորիթմի (DSA) տարբերակ, որն օգտագործել է էլիպտիկ կորերի գաղտնագրություն։

Բանալու և ստորագրության չափեր

Ինչպես ընդհանուր առմամբ էլիպտիկ կորերի գաղտնագրության դեպքում, ECDSA-ի համար անհրաժեշտ համարվող մասնավոր բանալիի բիթային չափը մոտավորապես երկու անգամ մեծ է եղել անվտանգության մակարդակից՝ բիթերով արտահայտված։ Օրինակ՝ 80 բիթ անվտանգության մակարդակի դեպքում, ինչը նշանակել է, որ հարձակվողին մասնավոր բանալին գտնելու համար առավելագույնը մոտ $2^{80}$ գործողություն է պահանջվել, ECDSA մասնավոր բանալու չափը պետք է լիներ 160 բիթ։ Մյուս կողմից՝ ստորագրության չափը նույնն է եղել ինչպես DSA-ի, այնպես էլ ECDSA-ի համար՝ մոտավորապես $4t$ բիթ, որտեղ $t$-ն $2^{t}$ բանաձևի ցուցիչն է, այսինքն՝ մոտ 320 բիթ՝ 80 բիթ անվտանգության մակարդակի համար, որը համարժեք է $2^{80}$ գործողության։

Ստորագրության ստեղծման ալգորիթմ

Ենթադրենք՝ Ալիսը ցանկացել է ստորագրված հաղորդագրություն ուղարկել Բոբին։ Սկզբում նրանք պետք է համաձայնեցնեն կորի պարամետրերը՝ $({\textrm {CURVE}},G,n)$։ Բացի կորի դաշտից և հավասարումից, անհրաժեշտ է եղել $G$-ն՝ պարզ կարգ ունեցող բազային կետը կորի վրա։ $n$-ը $G$ կետի ադիտիվ կարգն է։

Պարամետր	Նկարագրություն
CURVE	օգտագործված էլիպտիկ կորի դաշտը և հավասարումը
G	էլիպտիկ կորի բազային կետը՝ կորի վրա գտնվող կետ, որը առաջացրել է մեծ պարզ կարգ ունեցող ենթախումբ
n	G-ի ամբողջ կարգը, ինչը նշանակում է, որ $n\times G=O$, որտեղ $O$-ն նույնականության տարրն է
$d_{A}$	մասնավոր բանալին, որը ընտրվել է պատահականորեն
$Q_{A}$	հանրային բանալին՝ $d_{A}\times G$, որը հաշվարկվել է էլիպտիկ կորի միջոցով
m	ուղարկվող հաղորդագրությունը

Բազային $G$ կետի $n$ կարգը պետք է լինի պարզ։ Իրականում ենթադրվել է, որ $\mathbb {Z} /n\mathbb {Z}$ օղակի յուրաքանչյուր ոչ զրոյական տարր շրջելի է, ուստի $\mathbb {Z} /n\mathbb {Z}$-ը պետք է լինի դաշտ։ Դրանից հետևել է, որ $n$-ը պետք է լինի պարզ թիվ՝ տես նաև Բեզուի նույնություն։

Ալիսը ստեղծել է բանալիների զույգ, որը կազմված է եղել $[1,n-1]$ միջակայքից պատահականորեն ընտրված $d_{A}$ մասնավոր բանալի ամբողջ թվից և $Q_{A}=d_{A}\times G$ հանրային բանալի կետից։ Այստեղ $\times$-ը նշանակել է էլիպտիկ կորի կետի բազմապատկում սկալյարով։

$m$ հաղորդագրությունը ստորագրելու համար Ալիսը հետևել է այս քայլերին.

1. Հաշվել $e={\textrm {HASH}}(m)$։ Այստեղ HASH-ը գաղտնագրական հեշ ֆունկցիա է, օրինակ՝ SHA-2, որի ելքը փոխակերպվել է ամբողջ թվի։
2. Թող $z$-ը լինի $e$-ի ձախից վերցված $L_{n}$ բիթերը, որտեղ $L_{n}$-ը $n$ խմբի կարգի բիթային երկարությունն է։ Պետք է նշել, որ $z$-ը կարող է լինել մեծ $n$-ից, բայց ոչ ավելի երկար։
3. Ընտրել գաղտնագրորեն անվտանգ պատահական $k$ ամբողջ թիվ $[1,n-1]$ միջակայքից։
4. Հաշվել կորի կետը՝ $(x_{1},y_{1})=k\times G$։
5. Հաշվել $r=x_{1}\,{\bmod {\,}}n$։ Եթե $r=0$, վերադառնալ 3-րդ քայլին։
6. Հաշվել $s=k^{-1}(z+rd_{A})\,{\bmod {\,}}n$։ Եթե $s=0$, վերադառնալ 3-րդ քայլին։
7. Ստորագրությունը $(r,s)$ զույգն է։ Ընդ որում՝ $(r,-s\,{\bmod {\,}}n)$-ը նույնպես վավեր ստորագրություն է։

Ինչպես նշել է ստանդարտը, $k$-ն ոչ միայն պետք է գաղտնի լինի, այլ նաև շատ կարևոր է տարբեր ստորագրությունների համար ընտրել տարբեր $k$։ Հակառակ դեպքում 6-րդ քայլի հավասարումը կարող է լուծվել $d_{A}$ մասնավոր բանալու նկատմամբ։ Եթե տրված են երկու ստորագրություններ՝ $(r,s)$ և $(r,s')$, որոնք օգտագործել են նույն անհայտ $k$-ն տարբեր հայտնի հաղորդագրությունների՝ $m$-ի և $m'$-ի համար, հարձակվողը կարող է հաշվարկել $z$-ը և $z'$-ը։ Քանի որ $s-s'=k^{-1}(z-z')$, որտեղ այս պարբերության բոլոր գործողությունները կատարվել են ըստ մոդուլ $n$-ի, հարձակվողը կարող է գտնել $k={\frac {z-z'}{s-s'}}$։ Քանի որ $s=k^{-1}(z+rd_{A})$, հարձակվողը արդեն կարող է հաշվարկել մասնավոր բանալին՝ $d_{A}={\frac {sk-z}{r}}$։

Այս իրականացման սխալը, օրինակ, օգտագործվել է PlayStation 3 խաղային վահանակի ստորագրման բանալին ստանալու համար։

ECDSA ստորագրությունը կարող է մասնավոր բանալիներ արտահոսել նաև այն դեպքում, երբ $k$-ն ստեղծվել է սխալ պատահական թվերի գեներատորով։ Պատահական թվերի գեներացման այդպիսի ձախողումը 2013 թվականի օգոստոսին պատճառ է դարձել, որ Android Bitcoin Wallet-ի օգտատերերը կորցնեն իրենց միջոցները։

Ապահովելու համար, որ $k$-ն յուրաքանչյուր հաղորդագրության համար եզակի լինի, հնարավոր է ամբողջությամբ շրջանցել պատահական թվերի գեներացումը և ստեղծել դետերմինիստական ստորագրություններ՝ $k$-ն ստանալով ինչպես հաղորդագրությունից, այնպես էլ մասնավոր բանալուց։

Ստորագրության ստուգման ալգորիթմ

Որպեսզի Բոբը կարողանա վավերացնել Ալիսի $r,s$ ստորագրությունը $m$ հաղորդագրության վրա, նա պետք է ունենա նրա հանրային բանալիի կորային կետի՝ $Q_{A}$-ի պատճենը։ Բոբը կարող է ստուգել, որ $Q_{A}$-ն վավեր կորային կետ է, հետևյալ կերպ.

1. Ստուգել, որ $Q_{A}$-ն հավասար չէ նույնականության տարրին՝ O-ին, և դրա կոորդինատները վավեր են։
2. Ստուգել, որ $Q_{A}$-ն գտնվում է կորի վրա։
3. Ստուգել, որ $n\times Q_{A}=O$։

Դրանից հետո Բոբը հետևել է այս քայլերին.

1. Ստուգել, որ r-ը և s-ը $[1,n-1]$ միջակայքի ամբողջ թվեր են։ Եթե ոչ, ստորագրությունն անվավեր է։
2. Հաշվել $e={\textrm {HASH}}(m)$, որտեղ HASH-ը նույն ֆունկցիան է, որն օգտագործվել է ստորագրության ստեղծման ժամանակ։
3. Թող $z$-ը լինի e-ի ձախից վերցված $L_{n}$ բիթերը։
4. Հաշվել $u_{1}=zs^{-1}\,{\bmod {\,}}n$ և $u_{2}=rs^{-1}\,{\bmod {\,}}n$։
5. Հաշվել կորի կետը՝ $(x_{1},y_{1})=u_{1}\times G+u_{2}\times Q_{A}$։ Եթե $(x_{1},y_{1})=O$, ստորագրությունն անվավեր է։
6. Ստորագրությունը վավեր է, եթե $r\equiv x_{1}{\pmod {n}}$, հակառակ դեպքում՝ անվավեր։

Պետք է նշել, որ արդյունավետ իրականացումը $s^{-1}\,{\bmod {\,}}n$ հակադարձը կհաշվեր միայն մեկ անգամ։ Բացի այդ, Շամիրի հնարքի օգտագործմամբ երկու սկալյար բազմապատկումների գումարը՝ $u_{1}\times G+u_{2}\times Q_{A}$, կարող է հաշվարկվել ավելի արագ, քան երկու սկալյար բազմապատկումները առանձին կատարելու դեպքում։

Ալգորիթմի ճշտություն

Առաջին հայացքից անմիջապես ակնհայտ չէ, թե ինչու է ստուգումը ճիշտ աշխատել։ Դա տեսնելու համար C-ով նշանակենք ստուգման 5-րդ քայլում հաշվարկված կորի կետը.

$C=u_{1}\times G+u_{2}\times Q_{A}$

Հանրային բանալու սահմանումից՝ $Q_{A}=d_{A}\times G$, ստացվել է.

$C=u_{1}\times G+u_{2}d_{A}\times G$

Քանի որ էլիպտիկ կորի սկալյար բազմապատկումը բաշխական է գումարման նկատմամբ, ստացվել է.

$C=(u_{1}+u_{2}d_{A})\times G$

Ստուգման 4-րդ քայլում տրված $u_{1}$-ի և $u_{2}$-ի սահմանումները բացելով՝ ստացվել է.

$C=(zs^{-1}+rd_{A}s^{-1})\times G$

Ընդհանուր $s^{-1}$ անդամը դուրս բերելով՝ ստացվել է.

$C=(z+rd_{A})s^{-1}\times G$

Ստորագրության 6-րդ քայլի s-ի սահմանումը բացելով՝ ստացվել է.

$C=(z+rd_{A})(z+rd_{A})^{-1}(k^{-1})^{-1}\times G$

Քանի որ հակադարձի հակադարձը նույն սկզբնական տարրն է, իսկ տարրի և իր հակադարձի արտադրյալը նույնականությունն է, ստացվել է.

$C=k\times G$

r-ի սահմանումից սա ստուգման 6-րդ քայլն է։

Սա ցույց է տվել միայն, որ ճիշտ ստորագրված հաղորդագրությունը ճիշտ կստուգվի։ Անվտանգ ստորագրության ալգորիթմի համար պահանջվել են նաև այլ հատկություններ, օրինակ՝ սխալ ստորագրված հաղորդագրությունների չվավերացվելը և կրիպտանալիզային հարձակումների նկատմամբ դիմադրությունը։

Հանրային բանալու վերականգնում

Տրված լինելով m հաղորդագրությունը և այդ հաղորդագրության վրա Ալիսի $r,s$ ստորագրությունը՝ Բոբը կարող է, որոշ դեպքերում, վերականգնել Ալիսի հանրային բանալին.

1. Ստուգել, որ r-ը և s-ը $[1,n-1]$ միջակայքի ամբողջ թվեր են։ Եթե ոչ, ստորագրությունն անվավեր է։
2. Հաշվել կորի $R=(x_{1},y_{1})$ կետ, որտեղ $x_{1}$-ը $r$, $r+n$, $r+2n$ և այլն արժեքներից մեկն է, պայմանով, որ $x_{1}$-ը չափազանց մեծ չէ կորի դաշտի համար, իսկ $y_{1}$-ը այնպիսի արժեք է, որի դեպքում կորի հավասարումը բավարարվում է։ Պետք է նշել, որ կարող են լինել այս պայմաններին համապատասխանող մի քանի կորային կետեր, և յուրաքանչյուր տարբեր R արժեք հանգեցնում է տարբեր վերականգնված բանալու։
3. Հաշվել $e={\textrm {HASH}}(m)$, որտեղ HASH-ը նույն ֆունկցիան է, որն օգտագործվել է ստորագրության ստեղծման ժամանակ։
4. Թող z-ը լինի e-ի ձախից վերցված $L_{n}$ բիթերը։
5. Հաշվել $u_{1}=-zr^{-1}\,{\bmod {\,}}n$ և $u_{2}=sr^{-1}\,{\bmod {\,}}n$։
6. Հաշվել կորի կետը՝ $Q_{A}=(x_{A},y_{A})=u_{1}\times G+u_{2}\times R$։
7. Ստորագրությունը վավեր է, եթե $Q_{A}$-ն համընկնում է Ալիսի հանրային բանալու հետ։
8. Ստորագրությունն անվավեր է, եթե բոլոր հնարավոր R կետերը փորձարկվել են, և դրանցից ոչ մեկը չի համընկել Ալիսի հանրային բանալու հետ։

Պետք է նշել, որ անվավեր ստորագրությունը կամ այլ հաղորդագրության ստորագրությունը կհանգեցնի սխալ հանրային բանալու վերականգնման։ Վերականգնման ալգորիթմը կարող է օգտագործվել ստորագրության վավերությունը ստուգելու համար միայն այն դեպքում, երբ ստորագրողի հանրային բանալին կամ դրա հեշը նախապես հայտնի է։

Վերականգնման ալգորիթմի ճշտություն

Սկսենք վերականգնման 6-րդ քայլում տրված $Q_{A}$-ի սահմանումից.

$Q_{A}=(x_{A},y_{A})=u_{1}\times G+u_{2}\times R$

Ստորագրման 4-րդ քայլում տրված $R=(x_{1},y_{1})=k\times G$ սահմանումից ստացվել է.

$Q_{A}=u_{1}\times G+u_{2}k\times G$

Քանի որ էլիպտիկ կորի սկալյար բազմապատկումը բաշխական է գումարման նկատմամբ, ստացվել է.

$Q_{A}=(u_{1}+u_{2}k)\times G$

Վերականգնման 5-րդ քայլում տրված $u_{1}$-ի և $u_{2}$-ի սահմանումները բացելով՝ ստացվել է.

$Q_{A}=(-zr^{-1}+skr^{-1})\times G$

Ստորագրության 6-րդ քայլի s-ի սահմանումը բացելով՝ ստացվել է.

$Q_{A}=(-zr^{-1}+k^{-1}(z+rd_{A})kr^{-1})\times G$

Քանի որ տարրի և իր հակադարձի արտադրյալը նույնականությունն է, ստացվել է.

$Q_{A}=(-zr^{-1}+(zr^{-1}+d_{A}))\times G$

Առաջին և երկրորդ անդամները չեղարկվել են.

$Q_{A}=d_{A}\times G$

$Q_{A}=d_{A}\times G$ սահմանումից սա Ալիսի հանրային բանալին է։

Սա ցույց է տվել, որ ճիշտ ստորագրված հաղորդագրությունը կվերականգնի ճիշտ հանրային բանալին, եթե լրացուցիչ տեղեկությունը փոխանցվել է այնպես, որ հնարավոր լինի ստորագրության r արժեքից միարժեքորեն հաշվարկել $R=(x_{1},y_{1})$ կորի կետը։

Անվտանգություն

2010 թվականի դեկտեմբերին fail0verflow անունով հանդես եկող խումբը հայտարարել է Sony-ի կողմից PlayStation 3 խաղային վահանակի ծրագրերը ստորագրելու համար օգտագործված ECDSA մասնավոր բանալու վերականգնման մասին։ Սակայն այս հարձակումը աշխատել է միայն այն պատճառով, որ Sony-ն պատշաճորեն չի իրականացրել ալգորիթմը, քանի որ $k$-ն եղել է ստատիկ, ոչ թե պատահական։ Ինչպես նշվել է վերևում՝ ստորագրության ստեղծման ալգորիթմի բաժնում, սա $d_{A}$-ն դարձրել է լուծելի՝ ամբողջ ալգորիթմը դարձնելով անօգուտ։

2011 թվականի մարտի 29-ին երկու հետազոտող հրապարակել է IACR հոդված, որը ցույց է տվել, որ հնարավոր է ստանալ OpenSSL օգտագործող սերվերի TLS մասնավոր բանալին, եթե այն վավերացում է կատարում երկուական դաշտի վրա Էլիպտիկ կորերի DSA-ի միջոցով՝ ժամանակային հարձակման օգնությամբ։ Խոցելիությունը շտկվել է OpenSSL 1.0.0e-ում։

2013 թվականի օգոստոսին բացահայտվել է, որ Java-ի SecureRandom դասի որոշ իրականացումների սխալները երբեմն ստեղծել են $k$ արժեքի համընկնումներ։ Սա հաքերներին թույլ է տվել վերականգնել մասնավոր բանալիները՝ նրանց տալով նույն վերահսկողությունը բիթքոյն գործարքների նկատմամբ, ինչ ունեցել են օրինական բանալիների սեփականատերերը։ Օգտագործվել է նույն խոցելիությունը, որը բացահայտել է PS3-ի ստորագրման բանալին Android-ի որոշ հավելվածների իրականացումներում, որոնք օգտագործել են Java և հիմնվել են ECDSA-ի վրա՝ գործարքները վավերացնելու համար։

Այս խնդիրը կարող է կանխվել $k$-ի դետերմինիստական գեներացմամբ, ինչպես նկարագրվել է RFC 6979-ում։

Մտահոգություններ

ECDSA-ի վերաբերյալ արտահայտվել են որոշ մտահոգություններ.

1. Քաղաքական մտահոգություններ. NIST-ի ստեղծած կորերի վստահելիությունը կասկածի տակ է դրվել այն բացահայտումներից հետո, ըստ որոնց NSA-ն կամավոր կերպով հետնամուտքեր է ներառել ծրագրային ապահովման, սարքաշարային բաղադրիչների և հրապարակված ստանդարտների մեջ։ Հայտնի գաղտնագրագետները կասկածներ են հայտնել NIST կորերի նախագծման եղանակի վերաբերյալ, իսկ կամավոր աղտոտման դեպք արդեն ապացուցվել է անցյալում։ Տե՛ս նաև libssh curve25519 introduction։ Այնուամենայնիվ, դեռևս չկա ապացույց, որ անվանված NIST կորերը շահագործել են հազվադեպ թույլ կողմ։
2. Տեխնիկական մտահոգություններ. ստանդարտը ճիշտ իրականացնելու դժվարությունը, դրա դանդաղությունը և նախագծային թերությունները, որոնք նվազեցրել են անվտանգությունը ոչ բավարար պաշտպանական իրականացումներում։

Իրականացումներ

Ստորև ներկայացված է գաղտնագրական գրադարանների ցանկ, որոնք ապահովում են ECDSA-ի աջակցություն.

• Botan
• Bouncy Castle
• cryptlib
• Crypto++
• Crypto API (Linux)
• GnuTLS
• libgcrypt
• LibreSSL
• mbed TLS
• Microsoft CryptoAPI
• OpenSSL
• wolfCrypt

Գրականություն

• Accredited Standards Committee X9, ASC X9 Issues New Standard for Public Key Cryptography/ECDSA, Oct. 6, 2020. Source
• Accredited Standards Committee X9, American National Standard X9.62-2005, Public Key Cryptography for the Financial Services Industry, The Elliptic Curve Digital Signature Algorithm (ECDSA), November 16, 2005.
• Certicom Research, Standards for efficient cryptography, SEC 1: Elliptic Curve Cryptography, Version 2.0, May 21, 2009.
• López, J. and Dahab, R. An Overview of Elliptic Curve Cryptography, Technical Report IC-00-10, State University of Campinas, 2000.
• Daniel R. L. Brown, Generic Groups, Collision Resistance, and ECDSA, Designs, Codes and Cryptography, 35, 119–152, 2005. ePrint version
• Ian F. Blake, Gadiel Seroussi editors, Advances in Elliptic Curve Cryptography, London Mathematical Society Lecture Note Series 317, Cambridge University Press, 2005.
• Hankerson, D.; Vanstone, S.; Menezes, A. (2004). Guide to Elliptic Curve Cryptography. Springer Professional Computing. New York: Springer. doi:10.1007/b97644. ISBN 0-387-95273-X. S2CID 720546.

Արտաքին հղումներ

• Digital Signature Standard; includes info on ECDSA
• The Elliptic Curve Digital Signature Algorithm (ECDSA); provides an in-depth guide on ECDSA. Wayback link