Agar biz bir-birimizga ishonmasak, tasodifiy raqamlarni yaratish mumkinmi? 2-qism

Hey Xabr!

В birinchi qism Ushbu maqolada biz bir-biriga ishonmaydigan ishtirokchilar uchun nima uchun tasodifiy sonlarni yaratish kerak bo'lishi mumkinligini, bunday tasodifiy sonlar generatorlariga qanday talablar qo'yilishini muhokama qildik va ularni amalga oshirishning ikkita yondashuvini ko'rib chiqdik.

Maqolaning ushbu qismida biz chegara imzolaridan foydalanadigan boshqa yondashuvni batafsil ko'rib chiqamiz.

Bir oz kriptografiya

Chegara imzolari qanday ishlashini tushunish uchun siz biroz asosiy kriptografiyani tushunishingiz kerak. Biz ikkita tushunchadan foydalanamiz: skalerlar yoki oddiygina raqamlar, biz ularni kichik harflar bilan belgilaymiz (x, y) va elliptik egri chiziqdagi nuqtalar, biz ularni bosh harflar bilan belgilaymiz.

Chegara imzolarining asoslarini tushunish uchun bir nechta asosiy narsalardan tashqari elliptik egri chiziqlar qanday ishlashini tushunishingiz shart emas:

1. Elliptik egri chiziqdagi nuqtalarni skalerga qo'shish va ko'paytirish mumkin (biz skaler bilan ko'paytirishni quyidagicha ifodalaymiz. xG, yozuv bo'lsa-da Gx adabiyotda ham tez-tez ishlatiladi). Skayar bilan qo'shish va ko'paytirish natijasi elliptik egri chiziqdagi nuqtadir.

2. Faqat fikrni bilish G va uning mahsuloti skaler bilan xG hisoblash mumkin emas x.

Biz ko'phad tushunchasidan ham foydalanamiz p(x) daraja k-1. Xususan, ko'phadning quyidagi xossasidan foydalanamiz: qiymatini bilsak p(x) har qanday uchun k turli x (va bizda bu haqda boshqa ma'lumot yo'q p(x)), hisoblashimiz mumkin p(x) boshqa hech kim uchun x.

Har qanday polinom uchun bu qiziq p(x) va egri chiziqdagi ba'zi nuqta Gma'nosini bilish p(x) G har qanday uchun k turli ma'nolar x, biz ham hisoblashimiz mumkin p(x) G har qanday uchun x.

Bu chegara imzolari qanday ishlashi va ulardan tasodifiy raqamlarni yaratish uchun qanday foydalanish haqida tafsilotlarni o'rganish uchun etarli ma'lumot.

Eshik imzolarida tasodifiy raqamlar generatori

Buni aytaylik n ishtirokchilar tasodifiy raqamni yaratmoqchi va biz har kim ishtirok etishini xohlaymiz k raqam yaratish uchun ularning soni etarli edi, lekin shunday qilib, nazorat qiluvchi hujumchilar k-1 yoki undan kam ishtirokchi ishlab chiqarilgan raqamni bashorat qila olmadi yoki ta'sir qila olmadi.

Faraz qilaylik, shunday polinom bor p(x) daraja k-1 birinchi ishtirokchi nimani biladi p (1), ikkinchisi biladi p(2), va hokazo (n- biladi p(n)). Biz, shuningdek, oldindan belgilangan nuqta uchun, deb taxmin qilamiz G Hamma biladi p(x) G barcha qadriyatlar uchun x. Biz qo'ng'iroq qilamiz p(i) "shaxsiy komponent" ith ishtirokchisi (chunki faqat iishtirokchi uni taniydi) va p(i)G "ommaviy komponent" i-chi ishtirokchi (chunki barcha ishtirokchilar uni bilishadi). Esingizda bo'lsa, bilim p(i)G qayta tiklash uchun etarli emas p(i).

Bunday polinom yaratish faqat shunday i-Birinchi ishtirokchi va boshqa hech kim uning shaxsiy komponentini bilmagan - bu protokolning eng murakkab va qiziqarli qismi va biz uni quyida tahlil qilamiz. Hozircha, bizda shunday polinom bor va barcha ishtirokchilar o'zlarining shaxsiy komponentlarini bilishadi deb faraz qilaylik.

Tasodifiy son hosil qilish uchun bunday polinomdan qanday foydalanishimiz mumkin? Boshlash uchun bizga generatorga kirish sifatida ilgari ishlatilmagan bir qator kerak. Blockchain bo'lsa, oxirgi blokning xeshi h bunday chiziq uchun yaxshi nomzod. Ishtirokchilar tasodifiy raqam yaratishga ruxsat bering h urug' kabi. Ishtirokchilar birinchi navbatda aylanadilar h har qanday oldindan belgilangan funksiya yordamida egri chiziqdagi nuqtaga:

H = skalarToPoint(h)

Keyin har bir ishtirokchi i hisoblab chiqadi va nashr etadi Salom = p(i)H, ular nima qilishlari mumkin, chunki ular bilishadi p (i) va H. Oshkora qilish Hboshqa ishtirokchilarga shaxsiy komponentni tiklashga ruxsat bermayman ith ishtirokchisi va shuning uchun bitta shaxsiy komponentlar to'plami blokdan blokga ishlatilishi mumkin. Shunday qilib, quyida tavsiflangan qimmat polinom yaratish algoritmi faqat bir marta bajarilishi kerak.

qachon k ishtirokchilar otopsiya qilindi Salom = p(i)H, hamma hisoblay oladi Hx = p(x)H hamma uchun x Oxirgi bo'limda muhokama qilgan polinomlarning xususiyati tufayli. Ayni paytda barcha ishtirokchilar hisoblashadi H0 = p(0)H, va bu tasodifiy sondir. E'tibor bering, hech kim bilmaydi p(0), va shuning uchun hisoblashning yagona usuli p(0)H - bu interpolyatsiya p(x)H, bu faqat qachon mumkin k qiymatlar p(i)H ma'lum. Har qanday kichikroq miqdorni ochish p(i)H haqida hech qanday ma'lumot bermaydi p(0)H.

Yuqoridagi generator biz xohlagan barcha xususiyatlarga ega: faqat tajovuzkorlar nazorat qiladi k-1 yoki undan kam ishtirokchi xulosaga hech qanday ma'lumot yoki ta'sir ko'rsatmaydi k ishtirokchilar natijada olingan sonni va har qanday kichik to'plamini hisoblashlari mumkin k ishtirokchilar har doim bir xil urug' uchun bir xil natijaga keladi.

Yuqorida biz ehtiyotkorlik bilan chetlab o'tadigan bitta muammo bor. Interpolatsiya ishlashi uchun qiymat muhim ahamiyatga ega Hi har bir ishtirokchi tomonidan nashr etilgan i haqiqatan ham xuddi shunday edi p(i)H. Chunki boshqa hech kim i- ishtirokchi bilmaydi p(i), boshqa hech kim i-ishtirokchi buni tasdiqlay olmaydi Hi aslida to'g'ri hisoblangan va to'g'riligini hech qanday kriptografik isbotisiz Hi tajovuzkor har qanday qiymatni nashr qilishi mumkin , Hi va tasodifiy sonlar generatorining chiqishiga o'zboshimchalik bilan ta'sir qiladi:

Birinchi ishtirokchi tomonidan yuborilgan H_1 ning turli qiymatlari har xil natijadagi H_0 ga olib keladi

To'g'riligini isbotlashning kamida ikkita usuli mavjud Hi, biz ko'phadning avlodini tahlil qilgandan keyin ularni ko'rib chiqamiz.

Polinom avlodi

Oxirgi bo'limda bizda shunday polinom bor deb taxmin qildik p(x) daraja k-1 ishtirokchi i biladi p(i), va boshqa hech kim bu qiymat haqida hech qanday ma'lumotga ega emas. Keyingi bo'limda bizga oldindan belgilangan nuqta uchun ham kerak bo'ladi G hamma bilardi p(x) G hamma uchun x.

Ushbu bo'limda biz har bir ishtirokchi mahalliy miqyosda qandaydir shaxsiy kalitga ega deb hisoblaymiz xi, Shunday qilib, hamma tegishli ochiq kalitni biladi Xi.

Mumkin bo'lgan bir polinom yaratish protokoli quyidagicha:

1. Har bir ishtirokchi i lokal ravishda ixtiyoriy polinom hosil qiladi pi(x) daraja k-1. Keyin ular har bir ishtirokchini yuborishadi j ma'no pi(j), ochiq kalit bilan shifrlangan Xj. Faqat shunday i-th и j-th ishtirokchi biladi pi(j). Ishtirokchi i ham ommaga e'lon qiladi pi(j)G hamma uchun j от 1 uchun k jumladan.

2. Tanlash uchun barcha ishtirokchilar konsensusdan foydalanadilar k polinomlari ishlatiladigan ishtirokchilar. Ba'zi ishtirokchilar oflayn bo'lishi mumkinligi sababli, biz hammani kuta olmaymiz n ishtirokchilar polinomlarni nashr etadilar. Ushbu bosqichning natijasi to'plamdir Z kamida iborat k (1) bosqichda yaratilgan polinomlar.

3. Ishtirokchilar o'zlari bilishgan qadriyatlarga ishonch hosil qilishadi pi (j) ommaviy ravishda e'lon qilinganiga mos keladi pi(j)G. Ushbu qadamdan keyin Z faqat xususiy ravishda uzatiladigan polinomlar pi (j) ommaviy ravishda e'lon qilinganiga mos keladi pi(j)G.

4. Har bir ishtirokchi j uning shaxsiy komponentini hisoblaydi p(j) summa sifatida pi(j) hamma uchun i в Z. Har bir ishtirokchi barcha qiymatlarni ham hisoblab chiqadi p(x) G summa sifatida Barcha i uchun pi(x)G в Z.

E'tibor bering p(x) - bu haqiqatan ham polinom k-1, chunki u individning yig'indisidir pi(x), ularning har biri darajali ko‘phaddir k-1. Keyin, e'tibor bering, har bir ishtirokchi j biladi p(j), haqida hech qanday ma'lumotga ega emaslar p(x) uchun x ≠ j. Haqiqatan ham, bu qiymatni hisoblash uchun ular hamma narsani bilishlari kerak pi(x), va ishtirokchi ekan j tanlangan ko'phadlardan kamida bittasini bilmaydi, ular haqida yetarli ma'lumotga ega emas p(x).

Bu oxirgi bo'limda zarur bo'lgan polinomni yaratish jarayoni. Yuqoridagi 1, 2 va 4-bosqichlar juda aniq amalga oshirilgan. Ammo 3-bosqich unchalik ahamiyatsiz emas.

Xususan, biz shifrlanganligini isbotlay olishimiz kerak pi (j) haqiqatan ham nashr etilganlarga mos keladi pi(j)G. Agar buni isbotlay olmasak, hujumchi i o'rniga axlat yuborishi mumkin pi(j) ishtirokchiga j, va ishtirokchi j asl ma’noga erisha olmaydi pi(j), va uning shaxsiy komponentini hisoblay olmaydi.

Qo'shimcha xabar yaratish imkonini beruvchi kriptografik protokol mavjud isboti (j), shunday qilib, har qanday ishtirokchi, qandaydir qiymatga ega e, a takje isbot (j) и pi(j)G, buni mahalliy tekshirishi mumkin e - haqiqatan ham pi(j), ishtirokchi kaliti bilan shifrlangan j. Afsuski, bunday dalillarning hajmi nihoyatda katta va e'lon qilish zarurligini hisobga olsak. O(nk) Bunday dalillardan bu maqsadda foydalanish mumkin emas.

Buni isbotlash o'rniga pi(j) mos keladi pi(j)G biz polinom yaratish protokolida juda katta vaqtni ajratishimiz mumkin, bunda barcha ishtirokchilar qabul qilingan shifrlangan ma'lumotlarni tekshiradilar. pi(j), va agar shifrlangan xabar ommaga mos kelmasa pi(j)G, ular qabul qilgan shifrlangan xabar noto'g'ri ekanligini kriptografik isbotini nashr etadilar. Xabar ekanligini isbotlang yo'q mos keladi pi(G) mos kelishini isbotlashdan ko'ra osonroqdir. Shuni ta'kidlash kerakki, bu har bir ishtirokchidan bunday dalillarni yaratish uchun ajratilgan vaqt ichida kamida bir marta onlayn bo'lishini talab qiladi va agar ular bunday dalilni e'lon qilsalar, u xuddi shu ajratilgan vaqt ichida barcha boshqa ishtirokchilarga etib boradi degan taxminga tayanadi.

Agar ishtirokchi ushbu vaqt ichida onlayn ko'rinmasa va unda kamida bitta noto'g'ri komponent bo'lsa, u holda o'sha ishtirokchi keyingi raqamlarni yaratishda ishtirok eta olmaydi. Biroq, agar hech bo'lmaganda bo'lsa, protokol hali ham ishlaydi k faqat to'g'ri komponentlarni olgan yoki belgilangan vaqt ichida noto'g'riligini tasdiqlovchi hujjatni qoldirishga muvaffaq bo'lgan ishtirokchilar.

H_i ning to'g'riligini isbotlash

Muhokama qilinadigan oxirgi qism - nashr etilganlarning to'g'riligini qanday isbotlash Hmen, ya'ni bu Salom = p(i)H, ochmasdan p(i).

Qadriyatlar ekanligini eslaylik H, G, p(i)G ommaviy va hammaga ma'lum. Operatsiyani qabul qilish p(i) bilish p(i)G и G diskret logarifm deb ataladi yoki dlog, va biz buni isbotlamoqchimiz:

dlog(p(i)G, G) = dlog(Hi, H)

oshkor qilmasdan p(i). Masalan, bunday dalillar uchun konstruktsiyalar mavjud Schnorr protokoli.

Ushbu dizayn bilan, har bir ishtirokchi, bilan birga Hi dizaynga muvofiq to'g'riligini tasdiqlovchi hujjatni yuboradi.

Tasodifiy raqam yaratilgandan so'ng, uni ko'pincha uni yaratganlardan tashqari boshqa ishtirokchilar ham ishlatishlari kerak. Bunday ishtirokchilar raqam bilan birga hammasini yuborishlari kerak Hi va tegishli dalillar.

Qiziquvchan o'quvchi so'rashi mumkin: chunki oxirgi tasodifiy raqam H0, va p(0)G - Bu ommaviy axborot, nega bizga har bir shaxs uchun dalil kerak Hi, nega buning o'rniga dalil yubormaysiz

dlog (p(0)G, G) = dlog (H0, H)

Muammo shundaki, bunday dalilni Schnorr protokoli yordamida yaratib bo'lmaydi, chunki hech kim qiymatni bilmaydi p (0), dalil yaratish uchun zarur va bundan tashqari, butun tasodifiy sonlar generatori bu qiymatni hech kim bilmasligiga asoslanadi. Shuning uchun barcha qadriyatlarga ega bo'lish kerak Hi to'g'riligini isbotlash uchun ularning shaxsiy dalillari H0.

Biroq, elliptik egri chiziqlardagi nuqtalar ustida semantik jihatdan ko'paytirishga o'xshash operatsiya bo'lsa, to'g'riligi isboti H0 arzimas bo'lardi, biz shunchaki ishonch hosil qilamiz

H0 × G = p(0)G × H

Agar tanlangan egri chiziq qo'llab-quvvatlasa elliptik egri juftliklari, bu dalil ishlaydi. Ushbu holatda H0 faqat tasodifiy sonlar generatorining chiqishi emas, uni biladigan har qanday ishtirokchi tekshirishi mumkin G, H и p(0)G. H0, shuningdek, urug' sifatida ishlatilgan xabardagi imzo, buni tasdiqlaydi k и n ishtirokchilar ushbu xabarni imzoladilar. Shunday qilib, agar urug' - blokcheyn protokolidagi blokning xeshi hisoblanadi, keyin H0 blokdagi ko'p imzo va juda yaxshi tasodifiy raqam hamdir.

Xulosa

Ushbu maqola texnik bloglar seriyasining bir qismidir NEAR. NEAR - bu blokcheyn protokoli va markazlashtirilmagan ilovalarni ishlab chiqish uchun platforma bo'lib, ishlab chiqish qulayligi va oxirgi foydalanuvchilar uchun foydalanish qulayligiga urg'u beradi.

Protokol kodi ochiq, bizning dasturimiz Rustda yozilgan, uni topish mumkin shu yerda.

Onlayn IDE-da NEAR uchun ishlanma qanday ko'rinishini ko'rishingiz va tajriba qilishingiz mumkin shu yerda.

Barcha yangiliklarni rus tilida kuzatib borishingiz mumkin telegram guruhi va VKontakte-dagi guruh, va ingliz tilida rasmiy twitter.

Do skoryx vstrech!

Manba: www.habr.com