DSA
DSA - elektron imzo yaratish uchun shaxsiy kalitdan kriptografik algoritm, lekin shifrlash uchun emas . Imzo yashirincha (maxfiy kalit bilan) yaratiladi, lekin uni ommaviy ravishda tekshirish mumkin (ommaviy kalit bilan). Bu shuni anglatadiki, faqat bitta sub'ekt xabar imzosini yaratishi mumkin, ammo har kim uning to'g'riligini tekshirishi mumkin. Algoritm chekli sohalarda logarifmlarni olishning hisoblash murakkabligiga asoslangan. Algoritm 1991-yil avgust oyida Milliy standartlar va texnologiyalar instituti ( AQSh ) tomonidan taklif qilingan va patentlangan , NIST ushbu patentni royaltisiz foydalanish uchun taqdim etgan. DSA <b id="mwGg">DSS</b> ning bir qismidir Raqamli imzo standarti - birinchi marta 1998 yil 15 dekabrda nashr etilgan raqamli imzo standarti. Standart bir necha marta yangilangan , eng oxirgi versiyasi FIPS-186-4 . (2013 yil iyul).
Algoritmning tavsifi
DSA ikkita algoritmni (S, V) o'z ichiga oladi: xabar imzosini yaratish (S) va uni tekshirish uchun (V) iborat. Yana bir qancha qo`shimchalar mavjud. Ikkala algoritm ham birinchi navbatda kriptografik hash funktsiyasidan foydalangan holda xabarning xeshini hisoblab chiqadi. Algoritm S imzo yaratish uchun xesh va shaxsiy kalitdan foydalanadi, V algoritmi imzoni tekshirish uchun xabar xeshi, imzo va ochiq kalitdan foydalanadi. Ya`ni barchasi umumlashgan holda ishlaydi. Shuni ta'kidlash kerakki, aslida imzolangan xabar emas, balki uning xeshi (160 - 256 bit), shuning uchun to'qnashuvlar muqarrar va bitta imzo, umuman olganda, bir xil xeshli bir nechta xabarlar uchun amal qiladi. . Shuning uchun, etarlicha "yaxshi" hash funktsiyasini tanlash butun tizim uchun juda muhimdir. Standartning birinchi versiyasida SHA-1 xesh funktsiyasi ishlatilgan , so'nggi versiyada siz SHA-2 oilasining istalgan algoritmidan ham foydalanishingiz mumkin . 2015 yil avgust oyida yangi SHA-3 xesh funksiyasini tavsiflovchi FIPS-202 nashr etildi. Tizim ishlashi uchun muallifning haqiqiy ma'lumotlari (bu jismoniy shaxs yoki tashkilot bo'lishi mumkin) va ochiq kalitlar, shuningdek elektron raqamli imzo sxemasining barcha kerakli parametrlari .
Raqamli imzo sxemasi imkoniyatlari
Elektron raqamli imzo tizimini yaratish uchun siz quyidagi bosqichlarni bajarishingiz kerak. Albatta ketma ketlikda:
Yuqorida aytib o'tilganidek, raqamli imzo sxemasining birinchi parametri kriptografik xesh funktsiyasidan foydalaniladi, bu xabar matnini imzo hisoblangan raqamga aylantirish uchun zarurdir. DSS standartining birinchi versiyasi SHA-1 funksiyasini tavsiya qildi va shunga mos ravishda imzolangan raqamning bit uzunligi 160 bit . Standart L va N raqamlari uchun quyidagi mumkin bo'lgan qiymat juftlarini belgilaydi:
Ushbu standart SHA-2 xesh funktsiyalari oilasini tavsiya qiladi. AQSh hukumati tashkilotlari dastlabki uchta variantdan birini qo'llashi kerak; CAlar abonentlar ishlatadigan juftlikka teng yoki undan yuqori bo'lgan juftlikdan foydalanishlari kerak . Tizim dizayneri istalgan yaroqli xesh funksiyasini tanlashi mumkin. DSA-ga asoslangan kriptotizimning kuchi ishlatiladigan xesh funktsiyasining kuchidan va juftlikning (L, N) kuchidan oshmaydi, ularning kuchi alohida raqamlarning har birining kuchidan katta emas. Hozirgi vaqtda 2010 yilgacha ( 2030 yilgacha ) chidamli bo'lishi kerak bo'lgan tizimlar uchun tavsiya etilgan uzunlik 2048 (3072) bitni tashkil qiladi.
Umumiy va shaxsiy kalitlar
Umumiy parametrlar raqamlardir (p, q, g, y) . Faqat bitta shaxsiy parametr mavjud - x raqami. Bunday holda, raqamlar (p, q, g) foydalanuvchilar guruhi uchun umumiy bo'lishi mumkin va x va y raqamlari mos ravishda ma'lum bir foydalanuvchining shaxsiy va ochiq kalitlari hisoblanadi. Xabarga imzo qo'yishda x va k maxfiy raqamlari qo'llaniladi. (p, q, g) bir nechta foydalanuvchilar uchun ishlatilishi mumkinligi sababli, ba'zi bir mezonlarga ko'ra bir xil (p, q, g) guruhlarga bo'linadi.
Xabar imzosi
Xabar quyidagi algoritm yordamida imzolanadi :
Hisoblash jihatidan murakkab operatsiyalar ko'rsatkich moduli (hisoblash
g
k
mod
p
{\displaystyle g^{k}{\bmod {p}}}
), ular uchun tezkor algoritmlar mavjud, xeshni hisoblash
H
(
x
)
{\displaystyle H(x)}
, bu erda murakkablik tanlangan xesh algoritmiga va kirish xabarining o'lchamiga va teskari elementni topishga bog'liq.
Imzoni tekshirish
Imzoni tekshirish algoritmga muvofiq amalga oshiriladi :
Hisoblab chiqish jihatidan murakkab funksiyalarni tekshirganda, bu ikkita eksponentatsiya
g
u
1
y
u
2
{\displaystyle g^{u_{1}}y^{u_{2}}}
, xeshni hisoblash
H
(
x
)
{\displaystyle H(x)}
va teskari qismni topish
s
−
1
mod
q
{\displaystyle s^{-1}{\bmod {q}}}
. Bu funksiyalar o`zi muhim.
Sxemaning to'g'riligi
Ushbu elektron raqamli imzo sxemasi shu darajada to'g'ri bo'ladiki, imzoning haqiqiyligini tekshirishni istagan har bir kishi haqiqiylik holatida har doim ijobiy natija oladi. Bunda chiqishi mumkin emas. Chunki bular shaxsiydir. Keling, buni ko'rsatamiz:Birinchidan, agar
g
=
h
(
p
−
1
)
/
q
mod
p
{\displaystyle g=h^{(p-1)/q}\mod p}
,
g
q
=
h
p
−
1
=
1
mod
p
{\displaystyle g^{q}=h^{p-1}=1\mod p}
. g >1 va q tub son ekan, u holda g q moduli p ning ko'paytma tartibida. Xabar imzosi uchun u hisoblanadi
s
=
k
−
1
(
H
(
m
)
+
x
⋅
r
)
mod
q
.
{\displaystyle s=k^{-1}(H(m)+x\cdot r)\mod {q}.}
Shuning uchun
k
=
H
(
m
)
⋅
s
−
1
+
x
⋅
r
⋅
s
−
1
=
H
(
m
)
⋅
w
+
x
⋅
r
⋅
w
mod
q
.
{\displaystyle k=H(m)\cdot s^{-1}+x\cdot r\cdot s^{-1}=H(m)\cdot w+x\cdot r\cdot w\mod {q}.}
g q tartibli bo'lgani uchun biz olamiz
g
k
=
g
H
(
m
)
⋅
w
mod
q
g
x
⋅
r
⋅
w
mod
q
=
g
H
(
m
)
⋅
w
mod
q
y
r
⋅
w
mod
q
=
g
u
1
y
u
2
mod
p
.
{\displaystyle g^{k}=g^{H(m)\cdot w\mod q}g^{x\cdot r\cdot w\mod q}=g^{H(m)\cdot w\mod q}y^{r\cdot w\mod q}=g^{u1}y^{u2}\mod {p}.}
Nihoyat, DSA sxemasining to'g'riligi shundan kelib chiqadi
r
=
(
g
k
mod
p
)
mod
q
=
(
g
u
1
y
u
2
mod
p
)
mod
q
=
v
.
{\displaystyle r=(g^{k}\mod p)\mod q=(g^{u1}y^{u2}\mod p)\mod q=v.}
[4]
Ishga misol
Xesh qiymati bizning xabarimizning funktsiyasi bo'lsin
H
=
9
{\displaystyle H=9}
.
Parametrlarni yaratish
Kalitlarni yaratish
Xabar imzosi
Analoglar
DSA algoritmi diskret logarifmlarni hisoblash qiyinligiga asoslanadi va klassik El-Gamal sxemasining modifikatsiyasi bo'lib, bu erda xabar xeshlash qo'shiladi va barcha logarifmlar quyidagi tarzda hisoblanadi.
m
o
d
q
{\displaystyle mod~q}
, bu sizga analoglarga nisbatan imzoni qisqartirish imkonini beradi . U GOST R 34.10-2012 standarti bilan almashtirildi [13] , bu elliptik egri nuqtalar guruhidan foydalanadi. Shunga o'xshash modifikatsiya, ya'ni. Ko'paytma guruhi modulidan tub sondan elliptik egri chiziqning nuqtalar guruhiga o'tish DSA - ECDSA uchun ham mavjud . U, masalan, bitcoin kriptovalyutasida tranzaktsiyalarni tasdiqlash uchun ishlatiladi. Ushbu tarjima xavfsizlikni buzmasdan kalitlarning hajmini qisqartirish imkonini beradi - bitkoin tizimida shaxsiy kalitning o'lchami 256 bit, mos keladigan ochiq kalit esa 512 bit. Yana bir umumiy ochiq kalit algoritmi, RSA (mualliflar nomi bilan atalgan: Rivest, Shamir, Adleman ) katta raqamlarni faktoring qilish qiyinligiga asoslangan.
Kriptografik kuch
Algoritmga qilingan har qanday hujumni quyidagicha ta'riflash mumkin: buzg`unchi barcha ochiq imzo parametrlarini va ma'lum bir juftlik to'plamini oladi va ushbu to'plamdan foydalanib, yangi imzo yaratishga urinadi. Ushbu hujumlarni ikki guruhga bo'lish mumkin - birinchidan, tajovuzkor maxfiy kalitni tiklashga harakat qilishi mumkin
x
{\displaystyle x}
, va keyin u darhol istalgan xabarni imzolash imkoniyatini qo'lga kiritadi, ikkinchidan, u maxfiy kalitni to'g'ridan-to'g'ri tiklamasdan yangi xabar uchun haqiqiy imzo yaratishga harakat qilishi mumkin. Bu havfsizlik parametrlarini buzadi. Imzonoi buzib kirish imkoni paydo bo`ladi.
Tasodifiy parametrni bashorat qilish
k
{\displaystyle k}
tizim xavfsizligi uchun juda muhim. Agar bir nechta ketma-ket parametr bitlari ma'lum bo'lsa
k
{\displaystyle k}
bir qator imzolar uchun, keyin maxfiy kalit yuqori koeffitsiyent bilan tiklanishi mumkin. Kalit yo`qolgan taqdirda tiklash imkonini beradi. Ikkita xabar uchun parametrni takrorlash tizimni oddiy buzishga olib keladi. Android uchun bitcoin tizimining ba'zi ilovalarida tajovuzkor hamyonga kirish huquqiga ega bo'lishi mumkin. Ikkala misolda ham ECDSA tizimi ishlatilgan. Agar ikkita xabar uchun
m
1
,
m
2
{\displaystyle m_{1},m_{2}}
Xuddi shu parametr ishlatilgan
k
{\displaystyle k}
, keyin ularning imzolari
(
r
,
s
)
{\displaystyle (r,s)}
xuddi shunday bo'ladi
r
{\displaystyle r}
, lekin boshqacha
s
{\displaystyle s}
, keling, ularni chaqiramiz
s
1
,
s
2
{\displaystyle s_{1},s_{2}}
. Algaritmlarda to`g`ri foydalana bilish kerak. Uning s1 , s2 funksidan foydalanish
uchun ifodasidan
s
{\displaystyle s}
umumiy ifodalanishi mumkin
k
{\displaystyle k}
:
k
=
(
H
(
m
)
+
x
r
)
s
−
1
mod
q
{\displaystyle k=(H(m)+xr)s^{-1}\mod q}
.
Va umumiy miqdorni tenglashtiring
k
{\displaystyle k}
turli xabarlar uchun:
(
H
(
m
1
)
+
x
r
)
s
1
−
1
mod
q
=
(
H
(
m
2
)
+
x
r
)
s
2
−
1
mod
q
{\displaystyle (H(m_{1})+xr)s_{1}^{-1}\mod q=(H(m_{2})+xr)s_{2}^{-1}\mod q}
Bu erdan maxfiy kalitni ifodalash oson
x
{\displaystyle x}
:
x
=
H
(
m
1
)
s
1
−
1
−
H
(
m
2
)
s
2
−
1
r
(
s
2
−
1
−
s
1
−
1
)
{\displaystyle x={\frac {H(m_{1})s_{1}^{-1}-H(m_{2})s_{2}^{-1}}{r(s_{2}^{-1}-s_{1}^{-1})}}}
Ekzistensial soxtalashtirish
Ba'zi raqamli imzo algoritmlari mavjud soxtalik bilan hujum qilishi mumkin. Gap shundaki, imzo uchun faqat umumiy parametrlardan foydalangan holda to'g'ri xabarni yaratish mumkin (ammo bu odatda mantiqiy emas). DSA sxemasi imzosi uchun
r
=
g
e
y
mod
p
mod
q
{\displaystyle r=g^{e}y\mod p\mod q}
,
s
=
r
{\displaystyle s=r}
har qanday vaqtda
e
{\displaystyle e}
xash bilan xabar uchun to'g'ri
H
(
m
)
=
e
s
{\displaystyle H(m)=es}
. Mos kelishi mumkin. Agar xesh funktsiyasi to'g'ri tanlangan bo'lsa, DSA algoritmi ushbu hujumdan himoyalangan, chunki kriptografik xesh funktsiyasi teskari
k
{\displaystyle k}
topish
m
{\displaystyle m}
shu kabi
H
(
m
)
=
k
{\displaystyle H(m)=k}
) hisoblash jihatidan murakkab masala.
Kalitni tiklash
Imzoning amal qilish sharti boshqa shaklda qayta yozilishi mumkin
g
k
s
mod
p
mod
q
=
g
H
(
m
)
+
x
r
mod
p
mod
q
{\displaystyle g^{ks}\mod p\mod q=g^{H(m)+xr}\mod p\mod q}
bu tenglama ekvivalent
H
(
m
)
mod
q
=
k
s
−
x
r
mod
q
{\displaystyle H(m)\mod q=ks-xr\mod q}
Bu shuni anglatadiki, kalitni tiklash uchun buzuvchi shakldagi tenglamalar tizimini hal qilishi kerak deb taxmin qilishimiz mumkin.
H
(
m
i
)
mod
q
=
k
i
s
i
−
x
r
i
mod
q
{\displaystyle H(m_{i})\mod q=k_{i}s_{i}-xr_{i}\mod q}
lekin bu tizimda noma'lum
x
{\displaystyle x}
va tamom
k
i
{\displaystyle k_{i}}
, ya'ni noma'lumlar soni tenglamalardan bitta ko'p va har qanday uchun
x
{\displaystyle x}
bo'ladi
k
i
{\displaystyle k_{i}}
, tizimni qondirish. q katta tub son bo'lgani uchun tiklash uchun
x
mod
q
{\displaystyle x\mod q}
eksponensial sonli juftlik (xabar, imzo) talab qilinadi. Juftliklar bo`lmagan taqdirda tizimga kirish uchun qayta tiklash parametrlari mos kelmaydi. Shuning uchun bularga katta e`tibor qaratish kerak.
Imzoni qalbakilashtirish
Siz maxfiy kalitni bilmasdan imzo soxtalashtirishga harakat qilishingiz mumkin.
r
s
mod
p
mod
q
=
g
H
(
m
)
y
r
mod
p
mod
q
{\displaystyle r^{s}\mod p\mod q=g^{H(m)}y^{r}\mod p\mod q}
nisbatan
r
{\displaystyle r}
Va
s
{\displaystyle s}
. Har bir o`zgarmas uchun
r
{\displaystyle r}
tenglama diskret logarifmni hisoblashga teng. Huddi s kabi hisoblash.
Algoritmni amalga oshirishni tekshirish tizimi
Litsenziya shartlari algoritmni dasturiy va apparat vositalarida amalga oshirish imkonini beradi. NIST DSAVS ni yaratdi . DSAVS har bir tizim komponentini boshqalardan mustaqil ravishda tekshiradigan bir nechta muvofiqlik test modullaridan iborat. Sinov qilingan amalga oshirish komponentlari:
Amalga oshirishni tekshirish uchun ishlab chiquvchi CMT laboratoriyasida uning bajarilishini sinab ko'rish uchun ariza topshirishi kerak .
Bosh sonlarni hosil qilish
DSA algoritmi ikkita tub sonni talab qiladi (𝑝 Va 𝑞), shuning uchun tub yoki psevdo tub sonlar generatori kerak.tub sonlarni hosil qilish uchun Shou-Teylor algoritmidan foydalaniladi . Psevdoprimalar xesh funksiyasi yordamida yaratiladi va birlamchilikni tekshirish uchun Miller-Rabin probabilistik testidan foydalaniladi. Kerakli takrorlashlar soni ishlatilgan raqamlarning uzunligiga va tekshirish algoritmiga bog'liq . Ya`ni barcha algoritmlar bir biriga bog`liq:
Tasodifiy raqamlarni yaratish
Algoritm tasodifiy yoki psevdo-tasodifiy raqamlar generatorini ham talab qiladi. Ushbu generator shaxsiy foydalanuvchi kalitini yaratish uchun kerak bo'ladi x va s . Standart blokli shifrlar yoki xesh funksiyalari yordamida psevdor tasodifiy raqamlarni yaratishning turli usullarini taklif qiladi. Har bir usul universal bo`lishi mumkin.
Eslatmalar
Adabiyot
Standartlar va patentlar
Maqolalar
uz.wikipedia.org