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 subyekt 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 DSS 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ʻllanadi. "(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 formula_14), ular uchun tezkor algoritmlar mavjud, xeshni hisoblash formula_15, bu yerda murakkablik tanlangan xesh algoritmiga va kirish xabarining oʻlchamiga va teskari elementni topishga bogʻliq. Imzoni tekshirish. "Imzoni tekshirish algoritmga muvofiq amalga oshiriladi" ":" 1 Funksiyani hisoblashda formula_16 formulada 2 Funksiyani Hisoblashda formula_17 formulada 3 Funksiyani Hisoblashda formula_18 formulada 4 Funksiyani Hisoblash formula_19 formuladan ko`pincha foydalaniladi. 5 Imzo to'g'ri bo'lsa formula_20 Hisoblab chiqish jihatidan murakkab funksiyalarni tekshirganda, bu ikkita eksponentatsiya formula_21, xeshni hisoblash formula_15 va teskari qismni topish formula_23 . 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 formula_24, formula_25 . "g" >1 va "q" tub son ekan, u holda "g" "q" moduli "p" ning koʻpaytma tartibida. Xabar imzosi uchun u hisoblanadi Shuning uchun "g" "q" tartibli boʻlgani uchun biz olamiz Nihoyat, DSA sxemasining toʻgʻriligi shundan kelib chiqadi Ishga misol. Xesh qiymati bizning xabarimizning funktsiyasi boʻlsin formula_30 . Analoglar. DSA algoritmi diskret logarifmlarni hisoblash qiyinligiga asoslanadi va klassik El-Gamal sxemasining modifikatsiyasi boʻlib, bu yerda xabar xeshlash qoʻshiladi va barcha logarifmlar quyidagi tarzda hisoblanadi. formula_51, 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 formula_52, 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. formula_53 tizim xavfsizligi uchun juda muhim. Agar bir nechta ketma-ket parametr bitlari maʼlum boʻlsa formula_53 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 formula_55 Xuddi shu parametr ishlatilgan formula_53, keyin ularning imzolari formula_12 xuddi shunday boʻladi formula_58, lekin boshqacha formula_59, keling, ularni chaqiramiz formula_60 . Algaritmlarda toʻgʻri foydalana bilish kerak. Uning s1 , s2 funksidan foydalanish uchun ifodasidan formula_59 umumiy ifodalanishi mumkin formula_53 : formula_63 . Va umumiy miqdorni tenglashtiring formula_53 turli xabarlar uchun: formula_65 Bu yerdan maxfiy kalitni ifodalash oson formula_52 : formula_67 Ekzistensial soxtalashtirish. Baʼzi raqamli imzo algoritmlari mavjud 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 formula_68, formula_69 har qanday vaqtda formula_70 xash bilan xabar uchun toʻgʻri formula_71 . Mos kelishi mumkin. Agar xesh funktsiyasi toʻgʻri tanlangan boʻlsa, DSA algoritmi ushbu hujumdan himoyalangan, chunki kriptografik xesh funktsiyasi teskari formula_53 topish formula_73 shu kabi formula_74) hisoblash jihatidan murakkab masala. Kalitni tiklash. Imzoning amal qilish sharti boshqa shaklda qayta yozilishi mumkinformula_75 bu tenglama ekvivalent formula_76 Bu shuni anglatadiki, kalitni tiklash uchun buzuvchi shakldagi tenglamalar tizimini hal qilishi kerak deb taxmin qilishimiz mumkin. formula_77 lekin bu tizimda nomaʼlum formula_52 va tamom formula_79, yaʼni nomaʼlumlar soni tenglamalardan bitta koʻp va har qanday uchun formula_52 boʻladi formula_79, tizimni qondirish. q katta tub son boʻlgani uchun tiklash uchun formula_82 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.formula_83 nisbatan formula_58 Va formula_59 . Har bir oʻzgarmas uchun formula_58 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. Adabiyot. Maqolalar.