ElGamal shifrlash ehtimoliy, ya'ni bitta Oddiy matn ko'pgina mumkin bo'lgan shifrlangan matnlarga shifrlanishi mumkin, natijada umumiy ElGamal shifrlash hajmi oddiy matndan shifrlangan matngacha 1: 2 kengayishini hosil qiladi.
ElGamal ostida shifrlash ikkitani talab qiladi ko'rsatkichlar; ammo, bu ko'rsatkichlar xabarga bog'liq emas va agar kerak bo'lsa, ularni oldindan hisoblash mumkin. Shifrni echish uchun bitta eksponentatsiya va bitta teskari guruhni hisoblash talab qilinadi, ammo uni shunchaki bitta ko'rsatkichga birlashtirish mumkin.
ElGamal imzo sxemasi - bu diskret logarifma masalasi bilan birga modulli darajali ko'rsatkichning algebraik xususiyatlariga asoslangan raqamli imzo sxemasi. Algoritmda a kalit jufti dan iborat ochiq kalit va a shaxsiy kalit. Shaxsiy kalit a yaratish uchun ishlatiladi elektron raqamli imzo xabar uchun va bunday imzo bo'lishi mumkin tasdiqlangan imzo chekuvchining tegishli ochiq kalitidan foydalanish orqali. Elektron raqamli imzo xabarlarning autentifikatsiyasini (qabul qiluvchi xabarning kelib chiqishini tasdiqlashi mumkin), yaxlitlikni (qabul qiluvchining xabar imzolanganidan beri o'zgartirilmaganligini tasdiqlashi mumkin) va rad etilmasligini (jo'natuvchi yolg'on xabar berib, ular buni qilmaganligini da'vo qila olmaydi) beradi. xabarga imzo chekdi).
Muallif (El Gamal) tomonidan taklif qilingan assimetrik El Gamal sxemasi tub son moduli ko'rsatkichi operatsiyasidan foydalanadi. Shu bilan birga, tajovuzkor uchun hal qilib bo'lmaydigan vazifa - bu kuchga ko'tarilgan raqamni emas, balki ma'lum raqamni ko'taradigan kuchni topishdir. Bu masala diskret logarifm masalasi deb ataladi.
Asosiy avlod bosqichida:
1. Ixtiyoriy (lekin ancha katta) tub p tanlanadi.
2. Ushbu tub son uchun har qanday hosil qiluvchi element (ing. ibtidoiy ildiz) aniqlanadi - ya'ni, bunday a soni qayta-qayta p quvvat moduliga ko'tarilganda (a1mod p, a2modp, ...) tartiblashtiriladi. (ixtiyoriy tartibda, lekin har doim bir marta) 1 dan (p-1) gacha bo'lgan barcha raqamlar.
3. Ixtiyoriy tasodifiy son x (0
shaxsiy kalit.
4. b=axmodp qiymati hisoblanadi – kombinatsiya (a, p, b) qabul qiluvchining ochiq kalitidir.
Shifrlash bosqichida:
1. Yuboruvchi ixtiyoriy tasodifiy son y (02. Shifrlangan matnning boshiga raqam (aymodp) qo‘yadi.
3. k = (mod p) = ((ax mod p)y mod p) qiymatini hisoblaydi.
4. Ilgari ushbu amalga oshirishda ko'rsatilgan ba'zilaridan foydalanib, k qismi har qanday blokli shifr uchun simmetrik kalit sifatida yuborilayotgan xabarni shifrlaydi.
5. y va k raqamlarini operativ xotiradan va ular tasodifan kirib qolishi mumkin bo'lgan boshqa joylardan xavfsiz tarzda o'chiradi.
Shifrni ochish bosqichida:
Shifrlangan xabar kelgandan so‘ng, qabul qiluvchi qiymatni (aymodp) paketdan ajratadi va uning asosida ((ay modp)xmodp) hisoblaydi – matematika shuni isbotlaydiki, natijada olingan raqam jo‘natuvchi hisoblagan k ga teng bo‘ladi. , chunki bu formulada x va y operandlari joylarini o'zgartirish mumkin.
Diskret logarifmning muammosi shundan iboratki, darajaning asosini va modulni tub songa ko'tarishdan keyin olingan natijani bilib, mumkin emas.
poydevor qay darajada ko'tarilganligini aniqlash uchun taxminiy vaqt. ElGamal sxemasida potentsial tajovuzkor a, p, (axmod p) va (aymod p) qiymatlarini olishi mumkin. Biroq, x va y raqamlarini "sof shaklda" aniqlashning murakkabligi tufayli u shifrlashni o'qish uchun juda zarur bo'lgan k = (axymod p) qiymatini hisoblash imkoniyatiga ega emas.
ElGamal sxemasi bilan kriptografik quvvat nuqtai nazaridan 512 bitli p soni 56 bitli simmetrik kalitga teng bo'lib, uning o'lchami hozirda ishonchli shifrlash uchun etarli emas. Shuning uchun amalda 768, 1024 va 1536 bitli p uzunliklari qo'llaniladi.
3-misol. Tsiklik guruhni yaratuvchi tub son sifatida biz p \u003d 11 ni tanlaymiz, hosil qiluvchi element uchun a \u003d 7 raqamini olamiz (7 ni 1, 2, 3 va hokazo quvvatga ko'tarishda modul, modul 11, barcha 10 ta qiymatlar ketma-ket o'tadi [ 7, 5, 2, 3, 10, 4, 6, 9, 8, 1]). Maxfiy kalit sifatida 6 ni tanlaymiz, b parametr b = (axmodp) = (76mod11) = 4 qiymatini oladi. Umuman olganda, kalit (a = 7, p = 11, b = 4) ko'rinishni oladi.
Aytaylik, abonent xabar yubormoqchi. U p dan oshmaydigan tasodifiy sonni tanladi, masalan, y = 9. Raqam (aymodp) = 79mod11) = 8 shifrlashning boshida joylashtiriladi.Bundan tashqari, y va ochiq kalitga asoslanib, jo'natuvchi k = bymodp= 49 mod11 = 3 ni hisoblaydi. Simmetrik kalit sifatida 3-qiymatni yoki uning biron bir bitini tanlash orqali jo‘natuvchi uzatilgan ma’lumotlarni shifrlaydi va drayvlardan 9 va 3 qiymatlarini o‘chiradi.
Paket kelgandan so'ng, qabul qiluvchi k = (aymodp)xmodp ni hisoblash uchun shifrlash sarlavhasidan maxfiy kalitning kuchiga 8 raqamini ko'taradi va k = 86mod11 = 3 ni oladi - jo'natuvchi ma'lumotlarni shifrlashda ishlatgan qiymatni oladi. o'zi.
Ochiq kalitli kriptografiya. Ochiq kalitli kriptografiyada (yoki assimetrik kriptografiya deb ham ataladi) ma’lumotni shifrlash qabul qiluvchining ochiq kaliti bilan amalga oshirilsa, uni deshifrlash qabul qiluvchining shaxsiy kaliti bilan amalga oshiriladi. Shuning uchun ham ochiq kalitli kriptotizimlarni ikki kalitli kriptotizimlar deb ham yuritishadi. Ochiq kalitli kriptografiyaning umumiy ko’rinishi 2.3-rasm “a”da keltirilgan. Ochiq kalitli kriptografik algoritmlar asosida ma’lumot almashinish uchun dastlab, jo’natuvchi qabul qiluvchining ochiq kalitiga ega bo’lishi kerak. Qabul qiluvchining ochiq kalitidan faqat ma’lumotni shifrlash uchun foydalaniladi va u bilan shifrmatnni deshifrlashning imkoni mavjud emas. Xuddi shuningdek, shaxsiy kalit bilan ma’lumotni shifrlash imkoni ham mavjud emas. Shifrmatnni deshifrlash esa faqat shaxsiy kalit egasiga joiz. Demak, shaxsiy kalit egasi tomonidan xavfsiz saqlanishi va o’zidan boshqa hyech kimga ma’lum bo’lmasligi kerak. Xesh funksiyalar. Ma’lumotni xeshlash uning yaxlitligini kafolatlash maqsadida amalga oshirilib, agar ma’lumot uzatilishi davomida o’zgarishga uchrasa, uni aniqlash imkoni mavjud bo’ladi. Xesh-funksiyalarda odatda kiruvchi ma’lumotning uzunligi o’zgaruvchan, chiqishda esa o’zgarmas uzunlikdagi qiymatni qaytaradi. Zamonaviy xesh funksiyalarga MD5, SHA1, SHA256, O‘z DSt 1106:2009 larni misol keltirish mumkin. Quyida “ℎ𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒” xabarini turli xesh funksiyalardagi qiymatlari keltirilgan:
− 𝑀𝑀𝑀𝑀5(ℎ𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒) = 5𝑑𝑑41402𝑎𝑎𝑎𝑎𝑎𝑎4𝑏𝑏2𝑎𝑎76𝑏𝑏9719𝑑𝑑911017𝑐𝑐592
𝑆𝑆𝑆𝑆𝑆𝑆1(ℎ𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒)=𝑎𝑎𝑎𝑎𝑎𝑎4𝑐𝑐61𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑5𝑒𝑒8𝑎𝑎2𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑0𝑓𝑓3𝑏𝑏482𝑐𝑐𝑐𝑐9𝑎𝑎𝑎𝑎𝑎𝑎9434𝑑𝑑 − 𝑆𝑆𝑆𝑆𝑆𝑆256(ℎ𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒) = 2𝑐𝑐𝑓𝑓24𝑑𝑑𝑑𝑑𝑑𝑑5𝑓𝑓𝑓𝑓0𝑎𝑎30𝑒𝑒26𝑒𝑒83𝑏𝑏2𝑎𝑎𝑎𝑎5𝑏𝑏9𝑒𝑒29𝑒𝑒1𝑏𝑏161𝑒𝑒5𝑐𝑐1𝑓𝑓𝑓𝑓7425𝑒𝑒7304336 − 2938𝑏𝑏9824
Xesh funksiyalar quyidagi xususiyatlarga ega [13]: 1. Ixtiyoriy uzunlikdagi matnga qo’llash mumkin. 22 2. Chiqishda tayinlangan uzunlikdagi qiymat shakllanadi. 3. Berilgan ixtiyoriy 𝑥𝑥 bo’yicha ℎ(𝑥𝑥) oson hisoblanadi. 4. Berilgan ixtiyoriy 𝐻𝐻 bo’yicha ℎ (𝑥𝑥) = N tenglikdan 𝑥𝑥 ni hisoblab topib bo’lmaydi (bir tomonlilik xossasi). 5. Olingan 𝑥𝑥 va 𝑦𝑦 ≠ 𝑥𝑥 matnlar uchun ℎ(𝑥𝑥) ≠ ℎ(𝑦𝑦) bo’ladi (kolliziyaga bardoshlilik xossasi). Xesh funksiya yordamida uzatilayotgan ma’lumot yaxlitligini tekshirishning sodda ko’rinishi 8-rasmda keltirilgan. Jo’natuvchi xabarning xesh qiymatini hisoblaydi va uni qabul qiluvchiga xabar bilan birgalikda yuboradi. Qabul qiluvchi dastlab xabarning xesh qiymatini hisoblaydi va qabul qilingan xesh qiymat bilan solishtiradi. Agar har ikkala xesh qiymat teng bo’lsa, u holda ma’lumotning yaxlitligi o’zgarmagan, aks holda o’zgargan deb topiladi. Odatda xesh funksiyalar kirishda ma’lumotdan tashqari xech qanday qiymatni talab etmagani bois, kalitsiz kriptografik funksiyalar deb ham ataladi (kalit talab qiluvchi ma’lumotni yaxlitligini ta’minlash usullari ham mavjud, ular bilan keyingi qismlarda tanishib chiqiladi). Hello ! Hello ! Xesh qiymat Hello ! Xesh qiymat Xesh funksiya Hello ! Xesh funksiya Xesh qiymat Xesh qiymat Yaxlitlikni tekshirish Haqiqiy xabar Jo’natilgan xabar Qabul qilingan xabar 8-rasm. Xesh funksiya asosida ma’lumot yaxlitligini tekshirish Simmetrik va ochiq kalitli kriptotizimlardan ma’lumotlarning maxfiyligini ta’minlashda, xesh funksiyalardan esa ma’lumotlarni yaxlitligini tekshirishda foydalaniladi. Kriptografiyada ElGamal sxemasi: Kriptografiya xavfsizlik usullari haqidagi fandir
maxfiylik, ma'lumotlar yaxlitligi, autentifikatsiya va rad etmaslik.
Kriptografiyaning asosiy vazifasi ma'lumotlarni shifrlashning eng ishonchli algoritmini yaratishdir.
Kriptografiyaning fan sifatida boshlanishi to'rt ming yil oldin, ibtidoiy davrda paydo bo'lgan
xabarlar, harflar va boshqa narsalarni shifrlash. Yigirmanchi asrning boshidan shifrlash ishtirok eta boshladi
kompyuterlar, 70-yillarning oʻrtalaridan boshlab esa ochiq kodli kriptografiyaga oʻtish boshlandi.
kalit.
ElGamal sxemasi. Hisoblash qiyinligiga asoslangan ochiq kalit kriptotizimi
cheklangan maydondagi diskret logarifmlar. Shifrlash algoritmi va raqamli algoritmni o'z ichiga oladi
imzolar.
Sxema 1985 yilda Taher El-Gamal tomonidan taklif qilingan. U Diffie Hellman tizimini takomillashtirish va shifrlash va ta'minlash uchun ishlatiladigan ikkita algoritmni qo'lga kiritdi.
autentifikatsiya. RSA dan farqli o'laroq, ElGamal algoritmi patentlanmagan va shuning uchun ko'proq bo'ldi
RSA ga arzon muqobil, chunki litsenziya to'lovlari talab qilinmaydi.
Shifrlashning ehtimollik tabiati ElGamal sxemasi uchun afzallikdir, chunki sxemalarda
ehtimollik shifrlash, ma'lum bir sxemaga nisbatan ko'proq qarshilik mavjud
shifrlash jarayoni .
Ushbu turdagi shifrlashning afzalliklari shundaki, bu algoritmdan farqli o'laroq, erkin foydalanish mumkin
RSA dan. Shuningdek, u ko'plab o'zgarishlarga ega, chunki u turli guruhlardan foydalanishi mumkin,
buning uchun diskret logarifm muammosi hal etilmaydi. Elektron raqamli imzo (ERI) - bu hujjatning haqiqiyligini tasdiqlovchi rekvizit;
maxfiy kalit yordamida kriptografik o'zgartirish orqali olingan va
yuridik va jismoniy shaxslar tomonidan qo'llaniladi.
Umuman olganda, bu uni berish uchun elektron raqamli hujjatda qo'lda yozilgan imzoning analogidir yuridik kuch.
Birinchi marta ERIga ehtiyoj 1970 yilda muhokama qilingan, ammo uni amalga oshirish qiyin edi, chunki
kriptografik jihatdan kuchli algoritm talab qilinganidek. Faqat 7 yildan keyin Ronald Rivest, Adi Shamir va Leonard
Adleman RSA kriptografik algoritmini ishlab chiqdi, algoritmning ishonchliligi quyidagilarga asoslanadi.
katta sonlarni faktorizatsiya qilishdagi qiyinchiliklar. 1984 yilga kelib ElGamal sxemasi taqdim etildi .
Rossiyada elektron raqamli imzo tarixi birinchi marta 1994 yilda boshlangan
standart - GOST R34.10 - 94 "Axborot texnologiyalari. Axborotni kriptografik himoya qilish.
Assimetrik bo'lgan elektron raqamli imzoni ishlab chiqish va tekshirish tartiblari
kriptografik algoritm. xema 1984 yilda Taher El-Gamal tomonidan taklif qilingan. El-Gamal Diffie-Hellman algoritmining variantlaridan birini ishlab chiqqan. U Diffie-Hellman tizimini takomillashtirdi va shifrlash va autentifikatsiya qilish uchun ishlatiladigan ikkita algoritm oldi. RSA dan farqli o'laroq, ElGamal algoritmi patentlanmagan va shuning uchun litsenziya to'lovlari talab qilinmagani uchun arzonroq alternativaga aylandi. Algoritm Diffie-Hellman patenti bilan qoplangan deb ishoniladi.
Hech qanday xavfsiz aloqa kanallariga ega bo'lmagan holda bir-biriga shifrlangan xabarlarni yuborishni xohlaydigan A, B, C, ... obunachilar bo'lsin. Aslida, bu erda bir-biriga xabar uzatuvchi ikki abonent uchun umumiy maxfiy kalitni yaratish uchun Diffie-Hellman sxemasidan foydalaniladi, so'ngra xabar uni ushbu kalitga ko'paytirish orqali shifrlanadi. Har bir keyingi xabar uchun maxfiy kalit qayta hisoblab chiqiladi.
Keling, usulning aniq tavsifiga o'tamiz. Butun abonentlar guruhi uchun ba'zi bir katta tub son p va g soni shunday tanlanadiki, g ning turli darajalari modulli p har xil sonlar bo'ladi. ElGamal shifrining xususiyatlari:
B abonenti xabarni oldi, ya'ni. m'=m;
raqib p, g, dB, r va e ni bilgan holda, m ni hisoblay olmaydi.
Misol. A dan B ga m=15 xabarini yuboramiz.Parametrlarni tanlang: p=23, g=5. B abonenti o'zi uchun cB=13 maxfiy raqamni tanlasin va (1) dan hisoblab chiqsin.
Biz B uzatilgan xabarning shifrini ochishga muvaffaq bo'lganini ko'ramiz.
Do'stlaringiz bilan baham: |
