ایا دا ممکنه ده چې تصادفي شمیرې رامینځته کړو که چیرې موږ په یو بل باور ونه کړو؟ 2 برخه

اې حبره!

В لومړی برخه په دې مقاله کې، موږ بحث وکړ چې ولې دا اړینه ده چې د ګډون کونکو لپاره تصادفي شمیرې رامینځته کړي چې په یو بل باور نلري، د داسې تصادفي شمیرو جنراتورونو لپاره کومې اړتیاوې وړاندې کیږي، او د دوی پلي کولو لپاره دوه لارې په پام کې نیول شوي.

د مقالې په دې برخه کې، موږ به یوې بلې طریقې ته نږدې کتنه وکړو چې د حد لاسلیکونه کاروي.

یو څه کریپټوګرافي

د دې لپاره چې پوه شئ چې د حد لاسلیکونه څنګه کار کوي، تاسو اړتیا لرئ یو څه لومړني کریپټوګرافي پوه شئ. موږ به دوه مفکورې وکاروو: سکالر، یا ساده شمیرې، کوم چې موږ به د کوچنیو تورو په واسطه اشاره وکړو (x، y) او د بیضوي منحني نقطې، کوم چې موږ به د لوی لیکونو په واسطه اشاره وکړو.

د حد د لاسلیکونو په اساساتو پوهیدو لپاره، تاسو اړتیا نلرئ پوه شئ چې څنګه بیضوي منحني کار کوي، د یو څو اساسي شیانو پرته:

1. په بیضوي وکر کې نقطې د سکالر لخوا اضافه او ضرب کیدی شي (موږ به د سکالر لخوا ضرب په توګه وښیو xGکه څه هم یادښت Gx اکثرا په ادبیاتو کې هم کارول کیږي). د سکالر په واسطه د اضافه او ضرب پایله د بیضوي منحني نقطه ده.

2. یوازې په ټکي پوهیدل G او د هغې محصول د سکیلر سره xG محاسبه نشي کیدی x.

موږ به د پولینیم مفهوم هم وکاروو p(x) سند k-1. په ځانګړې توګه، موږ به د پولینیمونو لاندې ملکیت وکاروو: که موږ په ارزښت پوهیږو p(x) د هر چا لپاره k مختلف x (او موږ په اړه نور معلومات نه لرو p(x))، موږ محاسبه کولی شو p(x) د بل چا لپاره x.

په زړه پورې، د هر څو څو اړخیز لپاره p(x) او د منحنی په اړه یو څه ټکی Gپه معنی پوهیدل p(x)G د هر چا لپاره k مختلف معنی x، موږ هم محاسبه کولی شو p(x)G د هر چا لپاره x.

دا کافي معلومات دي چې د توضیحاتو کیندلو لپاره د حد لاسلیکونه څنګه کار کوي او د تصادفي شمیرو رامینځته کولو لپاره څنګه کارول کیږي.

د حد په لاسلیکونو کې تصادفي شمیره جنراتور

راځئ چې ورته ووایو n برخه اخیستونکي غواړي یو تصادفي شمیره رامینځته کړي، او موږ غواړو چې هرڅوک برخه واخلي k د دوی د شمیر د تولید لپاره کافي وو، مګر دا چې برید کونکي کنټرول کړي k-1 یا لږ ګډونوال نشي کولی د تولید شوي شمیرې وړاندوینه وکړي یا اغیزه وکړي.

فرض کړئ چې دا ډول پولینومیل شتون لري p(x) سند k- 1 هغه څه چې لومړی ګډون کوونکی پوهیږي p (1)، دوهم پوهیږي مخ(۲) او همداسی پسی (n- هغه پوهیږي p(n)). موږ دا هم فرض کوو چې د ځینې دمخه ټاکل شوي ټکي لپاره G هرڅوک پوهیږي p(x)G د ټولو ارزښتونو لپاره x. موږ به غږ وکړو p(i) "شخصي برخه" iګډون کونکی (ځکه یوازې iګډون کوونکی هغه پیژني) او p(i)G "عامه برخه" i-م ګډونوال (ځکه چې ټول ګډونوال هغه پیژني). لکه څنګه چې تاسو په یاد ولرئ، پوهه p(i)G د بیا رغونې لپاره کافي ندي p(i).

داسې یو پولینومیل رامینځته کول چې یوازې i-لومړی ګډون کوونکی او بل څوک د هغه شخصي برخه نه پیژني - دا د پروتوکول ترټولو پیچلې او زړه پورې برخه ده، او موږ به یې لاندې تحلیل کړو. د اوس لپاره، راځئ چې فرض کړو چې موږ دا ډول پولیومیلیل لرو او ټول ګډونوال د دوی شخصي برخې پیژني.

موږ څنګه کولی شو د تصادفي شمیرې رامینځته کولو لپاره دا ډول پولینومیل وکاروو؟ د پیل کولو لپاره، موږ یو څه تار ته اړتیا لرو چې مخکې جنراتور ته د ننوتلو په توګه نه و کارول شوي. د بلاکچین په حالت کې، د وروستي بلاک هش h د داسې کرښې لپاره یو ښه نوماند دی. اجازه راکړئ چې ګډونوال وغواړي په کارولو سره تصادفي شمیره جوړه کړي h لکه تخم ګډون کوونکي لومړی بدلوي h د هر مخکیني ټاکل شوي فعالیت په کارولو سره د منحني نقطې ته:

H = scalarToPoint(h)

بیا هر ګډونوال i محاسبه کوي او خپروي سلام = p(i)H دوی څه کولی شي ځکه چې دوی پوهیږي p(i) او H. افشا کول Hزه نورو ګډون کوونکو ته اجازه نه ورکوم چې شخصي برخې بیرته راولي iګډون کونکی، او له همدې امله د شخصي اجزاوو یوه سیټ له بلاک څخه بل بلاک ته کارول کیدی شي. په دې توګه، لاندې تشریح شوي ګران پولینومیل نسل الګوریتم یوازې یو ځل اجرا کولو ته اړتیا لري.

کله چې k د ګډون کوونکو مړینه وشوه سلام = p(i)H هرڅوک محاسبه کولی شي Hx = p(x)H دټولو لپاره x د پولینیومونو ملکیت څخه مننه چې موږ یې په وروستۍ برخه کې بحث وکړ. په دې وخت کې، ټول ګډونوال حساب کوي H0 = p(0)H، او دا د تصادفي نتیجه ده. مهرباني وکړئ په یاد ولرئ چې هیڅوک نه پوهیږي مخ(۲) او له همدې امله د محاسبې یوازینۍ لار ده p(0)H – دا انټرپولیشن دی p(x)H، کوم چې یوازې هغه وخت ممکن وي k ارزښتونه p(i)H پیژندل شوی هر کوچنی مقدار خلاصول p(i)H په اړه هیڅ معلومات نه ورکوي p(0)H.

پورته جنراتور ټول هغه ملکیتونه لري چې موږ یې غواړو: برید کونکي یوازې کنټرولوي k-1 برخه اخیستونکي یا لږ د پایلې په اړه هیڅ معلومات یا اغیزه نلري، پداسې حال کې چې کوم k برخه اخیستونکي کولی شي د پایلې شمیره محاسبه کړي، او د هرې فرعي سیټ k ګډون کوونکي به تل د ورته تخم لپاره ورته پایلې ته ورسیږي.

یوه ستونزه ده چې موږ یې په احتیاط سره پورته مخنیوی کړی. د کار کولو لپاره د انټرپولیشن لپاره، دا مهمه ده چې ارزښت Hi چې د هر ګډون کونکي لخوا خپور شوی و i دا واقعیا همداسې وه p(i)H ځکه چې هیڅوک پرته i- ګډون کوونکی نه پوهیږي p(i) هیڅوک پرته i-ګډون کوونکی نشي کولی دا تصدیق کړي Hi په حقیقت کې په سمه توګه محاسبه شوې، او پرته له کوم کریپټوګرافیک د سموالي ثبوت Hزه یو برید کونکی کولی شي هر ډول ارزښت خپور کړي سلام، او په خپلسري ډول د تصادفي شمیر جنراتور محصول اغیزه کوي:

د لومړي ګډون کونکي لخوا لیږل شوي H_1 مختلف ارزښتونه مختلف پایلې H_0 ته رسوي

د سموالي ثابتولو لپاره لږترلږه دوه لارې شتون لري Hi، موږ به وروسته له دې چې موږ د پولینیم نسل تحلیل کړو دوی به په پام کې ونیسو.

پولی نومی نسل

په وروستۍ برخه کې موږ داسې انګیرل چې موږ دا ډول پولینوم لرو p(x) سند k-1 هغه ګډون کوونکی i پوهيږي p(i)، او هیڅوک د دې ارزښت په اړه هیڅ معلومات نلري. په راتلونکې برخه کې به موږ دې ته د ځینې دمخه ټاکل شوي ټکي لپاره هم اړتیا ولرو G هرڅوک پوهیدل p(x)G دټولو لپاره x.

پدې برخه کې به موږ فرض کړو چې هر ګډونوال په سیمه ایزه توګه ځینې شخصي کیلي لري xi داسې چې هرڅوک ورته عامه کیلي پیژني Xi.

یو احتمالي پولینومیل نسل پروتوکول په لاندې ډول دی:

1. هر ګډونوال i په سیمه ایزه توګه یو خپلسری پولینیمیال رامینځته کوي pi(x) درجې k-1. دوی بیا هر ګډون کوونکی لیږي j معنی pi(j)، د عامه کیلي سره کوډ شوی Xj. په دې توګه یوازې i-د и j-د ګډون کوونکی پوهیږي pi(j). ګډون کوونکی i هم په عامه توګه اعلان کوي pi(j)G دټولو لپاره j от 1 پورې k ټول شموله

2. ټول ګډونوال د انتخاب لپاره ځینې اجماع کاروي k برخه اخیستونکي چې پولینومونه به کارول کیږي. څرنګه چې ځینې ګډونوال ممکن آفلاین وي، موږ نشو کولی تر ټولو پورې انتظار وکړو n ګډون کوونکي به پولي نوميالونه خپاره کړي. د دې ګام پایله یوه جوړه ده Z لږ تر لږه شامل دي k په مرحله کې جوړ شوي پولینومونه (1).

3. برخه اخیستونکي ډاډ ترلاسه کوي چې هغه ارزښتونه چې دوی پوهیږي pi(j) په عامه توګه اعلان شوي سره مطابقت لري pi(j)G د دې ګام وروسته Z یوازې پولینومونه چې په شخصي توګه لیږدول کیږي pi(j) په عامه توګه اعلان شوي سره مطابقت لري pi(j)G

4. هر ګډونوال j خپل شخصي برخه محاسبه کوي p(j) د یوې مجموعې په توګه pi(j) د ټولو لپاره i в Z. هر ګډونوال ټول ارزښتونه هم محاسبه کوي p(x)G د یوې مجموعې په توګه pi(x)G د ټولو i لپاره в Z.

هغه یاداښت کړه p(x) – دا واقعیا یو پولیمومیل دی k-1, ځکه چې دا د فرد مجموعه ده pi(x)، چې هر یو یې د درجې پولی نومیال دی k-1. بیا، په یاد ولرئ پداسې حال کې چې هر ګډونوال j پوهيږي p(j) دوی په اړه هیڅ معلومات نلري p(x) لپاره x ≠ j. په حقیقت کې، د دې ارزښت محاسبه کولو لپاره، دوی باید په هرڅه پوه شي pi(x) او تر هغه چې ګډون کوونکي وي j لږترلږه یو له ټاکل شوي پولینومونو څخه نه پوهیږي، دوی په اړه کافي معلومات نلري p(x).

دا د پولینومیل نسل ټوله پروسه ده چې په وروستۍ برخه کې ورته اړتیا وه. پورته 1، 2 او 4 مرحلې په کافي اندازه څرګند تطبیق لري. مګر دریم ګام دومره کوچنی ندی.

په ځانګړې توګه، موږ اړتیا لرو چې دا ثابت کړو چې کوډ شوی pi(j) واقعیا د خپرو شویو سره مطابقت لري pi(j)G که موږ دا ثابت نه کړو، بریدګر i کیدای شي پرځای یې کثافات ولیږدوي pi(j) ګډون کوونکي ته j، او ګډون کوونکی j د حقیقي ارزښت ترلاسه کولو توان نلري pi(j) او د دې توان ونلري چې خپل شخصي برخه محاسبه کړي.

دلته یو کریپټوګرافیک پروتوکول شتون لري چې تاسو ته اجازه درکوي اضافي پیغام رامینځته کړئ ثبوتi(j)، داسې چې هر ګډونوال، یو څه ارزښت لري e, هم ثبوت (j) и pi(j)G، کولی شي په محلي توګه دا تصدیق کړي e - دا واقعیا ده pi(j) د ګډون کونکي کیلي سره کوډ شوی j. له بده مرغه، د داسې شواهدو اندازه په زړه پورې ده، او د دې لپاره چې دا اړینه ده چې خپور شي O(nk) دا ډول شواهد د دې هدف لپاره نشي کارول کیدی.

د دې پر ځای چې دا ثابت کړي pi(j) د pi(j)G موږ کولی شو د پولینومیال نسل پروتوکول کې خورا اوږده موده تخصیص کړو ، په کوم کې چې ټول ګډون کونکي ترلاسه شوي کوډ شوي چیک کوي pi(j) او که چیرې کوډ شوی پیغام د خلکو سره مطابقت ونلري pi(j)G، دوی یو کریپټوګرافیک ثبوت خپروي چې کوډ شوی پیغام چې دوی ترلاسه کړی غلط دی. دا پیغام ثابت کړئ نه د pi(G) د ثابتولو په پرتله خورا اسانه چې دا سره سمون لري. دا باید په یاد ولرئ چې دا هر ګډونوال ته اړتیا لري چې لږترلږه یو ځل د داسې شواهدو رامینځته کولو لپاره په ټاکل شوي وخت کې آنلاین حاضر شي، او په دې انګیرنې تکیه کوي چې که دوی دا ډول ثبوت خپور کړي، دا به په ورته ټاکل شوي وخت کې نورو ټولو ګډون کونکو ته ورسیږي.

که چیرې یو ګډون کوونکی د دې مودې په اوږدو کې آنلاین نه و حاضر شوی، او هغه لږ تر لږه یوه غلطه برخه درلوده، نو هغه ځانګړی ګډون کوونکی به د نورو شمیرو په تولید کې برخه وانخلي. پروتوکول به بیا هم کار وکړي که چیرې لږترلږه شتون ولري k هغه برخه اخیستونکي چې یا یې سمې برخې ترلاسه کړې یا په ټاکل شوي وخت کې د غلطۍ ثبوت پریږدي.

د H_i د سموالي ثبوت

وروستۍ برخه چې بحث ته پاتې دی دا دی چې څنګه د خپریدو سموالی ثابت کړو Hزه، یعنی دا سلام = p(i)H پرته له پرانیستلو p(i).

راځئ چې دا ارزښتونه په یاد ولرو H, G, p (i) G عامه او ټولو ته پیژندل شوی. عملیات ترلاسه کول p(i) پوهیدل p(i)G и G discrete logarithm په نوم یادیږي، یا dlog او موږ غواړو دا ثابت کړو:

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

پرته له افشاء کولو p(i). د بیلګې په توګه، د داسې شواهدو لپاره جوړښتونه شتون لري د Schnorr پروتوکول.

د دې ډیزاین سره، هر ګډونوال، سره Hi د ډیزاین مطابق د سموالي ثبوت لیږي.

یوځل چې یو تصادفي شمیره رامینځته شي ، دا ډیری وختونه اړتیا لري د ګډون کونکو لخوا کارول کیږي پرته له هغه چا چې دا تولید کړي. دا ډول ګډونوال، د شمیرې سره، باید ټول واستوي Hi او اړوند شواهد.

یو پلټونکی لوستونکی ممکن پوښتنه وکړي: ځکه چې وروستی تصادفي شمیره ده H0، او p(0)G – دا عامه معلومات دي، ولې موږ د هر فرد لپاره ثبوت ته اړتیا لرو Hزه، ولې د دې پرځای ثبوت نه لیږئ

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

ستونزه دا ده چې دا ډول ثبوت د شنور پروتوکول په کارولو سره نشي رامینځته کیدی ځکه چې هیڅ څوک ارزښت نه پوهیږي p (0)، د ثبوت رامینځته کولو لپاره اړین دی ، او نور څه دي ، د تصادفي شمیرې ټول جنریټر د دې حقیقت پراساس دی چې هیڅ څوک پدې ارزښت نه پوهیږي. نو دا اړینه ده چې ټول ارزښتونه ولري Hi او د دوی انفرادي شواهد د سموالي ثابتولو لپاره H0.

په هرصورت، که چیرې د بیضوي منحني نقطو په اړه ځینې عملیات شوي وي چې په معنی توګه د ضرب سره ورته وي، د درستیت ثبوت H0 لږ به وي، موږ به په ساده ډول ډاډ ترلاسه کړو

H0 × G = p(0)G × H

که ټاکل شوی وکر ملاتړ وکړي elliptic curve pairings، دا ثبوت کار کوي. په دې صورت کې H0 نه یوازې د تصادفي شمیرې جنراتور محصول دی ، کوم چې د هر ګډون کونکي لخوا تایید کیدی شي څوک چې پوهیږي ج، ایچ и p(0)G. ه0 په پیغام کې یو لاسلیک هم دی چې د تخم په توګه کارول شوی و، دا تاییدوي k и n ګډونوالو دا پیغام لاسلیک کړ. په دې توګه، که تخم - بیا د بلاکچین پروتوکول کې د بلاک هش دی H0 دواړه په بلاک کې یو څو لاسلیکونه او یو خورا ښه تصادفي شمیره ده.

په پای کې

دا مقاله د تخنیکي بلاګ لړۍ برخه ده نژدې. NEAR د غیر متمرکز غوښتنلیکونو رامینځته کولو لپاره د بلاکچین پروتوکول او پلیټ فارم دی چې د پراختیا په اسانۍ او د پای کاروونکو لپاره د کارولو اسانتیا باندې ټینګار کوي.

د پروتوکول کوډ خلاص دی، زموږ تطبیق په Rust کې لیکل شوی، دا موندل کیدی شي دلته.

تاسو کولی شئ وګورئ چې د NEAR لپاره پرمختګ څه ډول ښکاري او په آنلاین IDE کې تجربه وکړئ دلته.

تاسو کولی شئ ټول خبرونه په روسیه کې تعقیب کړئ د ټیلیګرام ګروپ او په ګروپ په VKontakte کې، او په رسمي کې په انګلیسي ژبه ټویټر.

встреч скорых встреч!

سرچینه: www.habr.com