I. Kirish II. Asosiy qism Ochiq kalitli kriptotizmlarda kalitlarni generatsiyalash usullari

Download 385,21 Kb.
bet	7/12
Sana	05.12.2023
Hajmi	385,21 Kb.
	#111359

1 2 3 4 5 6 7 8 9 ... 12

Chiqish:
Kompozit, n to'liq kompozitsiyani bildiradi;
• ehtimol bosh, n ning ehtimol bosh ekanligini anglatadi. for i = 1, 2, ..., k :
a = tasodifiy butun son 2 dan n - 1 gacha, shu jumladan; agar NOD (a, n)> 1 bo'lsa, unda:
n kompozit ekanligini va to'xtashini aniqlaymiz.
Agar a ^ {(n-1) / 2} \ not \ equiv \ left ({a \ over n} \ right) \ pmod {n} bo'lsa: n kompozit
ekanligini va to'xtashini aniqlaymiz.
• textstyle 1 - 2 ^ {- k} ehtimollik bilan n ning tub ekanligini aniqlaymiz va to'xtatamiz.
Solovey-Shtrassenning katta sonlarni tublikka sinash algoritmiga misol p=19 ni Solovey-Shtrassen algoritmi bilan tublikka sinaymiz:
• k=1, 2 ≤ a ≤ p − 1 oraliqdan tasodifiy a=11 tanlaymiz.
• EKUB(a,r)= EKUB(11,19)=1
• Demak,
a^{( p−1)/2} ≡ (a/p)modp shartni bajarilishini tekshiramiz.
• s= a/p =11/19= 1
• a^{( p−1)/2} = 11^(19−1)/2(mod19) = 1
• Taqqoslasak, demak, a^{( p−1)/2} ≡ (a/p)
• Bundan quyidagicha xulosaga kelish mumkin: 19 son 1-2^-2 ehtimollik bilan tub son bo‘ladi.
Solovey-Shtrassenning sonlarni tublikka tekshirish algoritmini dasturiy moduli
public
static boolean isPrimeAccordingToSoloveiShtrassen(int number, int accuracy){
//number > 2, toq natural son for (int i = 0; i < accuracy; i++)
{ int >randomInt = randomIntInRange(2, number - 1);
if (gcd(randomInt, number) > 1)
{
return false;
}
int checkNumberW = pow(randomInt, (number - 1) / 2, number);
int jacobySignum = (jacobySign(randomInt, number) + number) % number;
if (checkNumberW != jacobySignum)
{
return false;
}
}
return true;
}
2.3 Rabin Millerning katta sonlarni tublikka sinash algoritmi
Rabin Miller- testi ehtimoliy polinom soddaligi testi eyiladi. Miller - Rabin testi, Ferma testi va Solovey Shtrassen testi bilan bir qatorda berilgan sonning kompozit ekanligini samarali aniqlashi mumkin. Biroq, bu raqamning asosiy ekanligini qat'iy isbotlash uchun ishlatilishi mumkin emas. Shunga qaramay, Miller-Rabin testi ko'pincha katta tasodifiy sonlarni olish
uchun kriptografiyada qo'llaniladi. Rabin-Miller algoritmi - bu Gari Miller tomonidan 1976-
yilda ishlab chiqilgan Miller algoritmining modifikatsiyasi hisoblanadi. Millerning algoritmi
deterministik, ammo uning to'g'riligi isbotlanmagan kengaytirilgan Riman gipotezasiga
asoslangan. Maykl Rabin uni 1980-yilda o'zgartirgan . Miller - Rabin algoritmi gipotezaning asosliligiga bog'liq emas, lekin bu ehtimollikdir. Ko'plab shifrlash algoritmlarining
kriptografik kuchi maxfiy kalitlarga asoslanganligi sababli, ularni yaratish uchun asosiy
raqamlar kerak (masalan, RSA shifrining ishlashi shunday), bunday tugmachalarni
yaratishda katta raqamlarni tezda oddiylikda tekshirib ko'rish kerak.Rabin- Miller testi va
Solovey-Shtrassen testi kabi probabilistik soddalik testlari deterministic testlarga nisbatan
katta samaradorlik va ifoda qulayligini ko'rsatadi. Miller-Rabin algoritmi jarayonni qisqa
vaqt ichida amalga oshirishga imkon beradi va shu bilan birga raqamning aslida kompozit
bo'lish ehtimoli juda kichik bo’ladi. Fermat va Solovey Strassen testlari singari,
Rabin- Miller testi ham asosiy sonlar uchun tenglik qatoriga tayanadi. Agar hech bo'lmaganda bunday tenglik qondirilmasa, bu raqamning birlashtirilganligini tasdiqlaydi.
Rabin – Millerning katta sonlarni tublikka sinash testi hozirgi kunda nosimmetrik
kriptotizimlarda modul hosil qilishda keng qo‘llaniladi. Bu algoritm kuchli psevdotub
sonlarni sinash algoritmi sifatida tan olingan. U n -1 ni, ya'ni modulni bitta kamaytirilgan
qiymatini 2^s*r ko‘rinishda ifodalashga asoslangan. Bunda s ─ n -1 ni ikkiga bo‘linishlar
soni, r – toq son. “n - soni tubmi?” degan savolga, “tub” yoki “murakkab” degan javob olishga qaratilgan bo‘ladi.
• n -1 = 2^s*r ko‘rinishda yozib olinadi, bunda r - toq son;
• 2≤ a ≤ n− 1 shartni qanoatlantiruvchi a son tasodifiy tanlanadi.
• y=a^rmodn ni hisoblanadi;
• Agar (y=1 yoki y=n -1) bo‘lsa, u holda keyingi iteratsiyaga o‘tish.
• a^{2^t*r}≡ −1 ( modn ) hisoblanadi;
• t < s marta, y=y²modn;
• Agar (y=1) bo‘lsa, u holda “murakkab son” qaytariladi;
• Agar (y≠n – 1) bo‘lsa, u holda “murakkab son” qaytariladi;
• Aks holda “Tub son” qaytariladi.
Rabin-Millerning katta sonlarni tublikka sinash algoritmiga misol
4033-murakkab sonini Rabin-Miller algoritmidan foydalanib tublikka sinaymiz.
• 4033-1=63∙2⁶
• 2 asosga ko‘ra Rabin-Miller algoritmini qo‘llaymiz
• y=2⁶³ (mod 4033)≡3521(mod 4033)
• s=1 y=y²=3521²(mod 4033)=-1(mod 4033)
• Test tugadi, endi 3 asos bilan tekshirib ko‘ramiz.
• y=3⁶³(mod 4033)≡3551(mod 4033)
• s=1 y=y²=3551²(mod 4033)=2443(mod 4033)
• s=2 y=y²=2443² (mod 4033)=3442(mod 4033)

• s=3 y=y²=3442² (mod 4033)=2443(mod 4033)
• s=4 y=y²=2443² (mod 4033)=3442(mod 4033)
• s=5 y=y²=3442² (mod 4033)=2443(mod 4033)
• Demak, berilgan son murakkab.
Ko'paytirish vaqtini logaritmik deb hisoblasak, tezkor modulli ko'paytma yordamida
algoritmning murakkabligi O (klog3 n), bu erda k turlar soni ...
Shunday qilib, algoritmning ishlash vaqti polinom hisoblanadi. Biroq, FFT yordamida algoritmning ishlash vaqtini O(klog2 (n)log (log (n))log (log (log (n)))) ga qisqartirish
mumkin. Bunday holda, biz k = log2(n) ni olsak, bu yerda n - tekshirilishi kerak bo'lgan
raqam, u holda algoritmning murakkabligi O(log3n) ga teng. Rabin-Millerning sonlarni
tublikka tekshirish algoritmini dasturiy moduli
public static
boolean isPrimeAccordingToMillerRabin(int number, int roundCount){
int numberMinus1 = number - 1;
int t = numberMinus1;
int s = 0;
while (t % 2 == 0)
{ t /= 2; s++; }
for (int i = 0; i < roundCount; i++)
{ int randomInt = randomIntInRange(2, number - 2);
int x = pow(randomInt, t, number);
if (x == 1 || x == numberMinus1) continue;
boolean flagToStop = true;
for (int j = 0; j < s - 1; j++)
{ >x = pow(x, 2, number);
if (x == 1){ return false;
}
if (x == numberMinus1)
{ flagToStop = false;

Download 385,21 Kb.

1 2 3 4 5 6 7 8 9 ... 12

Download 385,21 Kb.