Yordamida hal qilish uchun 55 modul 569 indeksini topishimiz kerak

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA
KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI


Loyha ishi


Guruh: 715-20


Bajardi:Ergashev Tursunmurod
Tekshirdi: Mardiyev Ulug’bek

Diskret lograifmlash muammosi (to‘rt kishi uchun)

Indeks hisoblash usuli yordamida 𝑥 ni toping:
a) 55𝑥 ≡ 444 (𝑚𝑜𝑑 569)
b) 7 𝑥 ≡ 92 (𝑚𝑜𝑑 1433)


Ko’di:
Ushbu tenglamani indeksni hisoblash usuli yordamida hal qilish uchun 55 modul 569 indeksini topishimiz kerak. Keling, bu indeksni 𝑛 deb ataymiz, shuning uchun bizda:
55^𝑛 ≡ 1 (mod 569)
𝑛 ni topish uchun Fermaning kichik teoremasidan foydalanishimiz mumkin, unda aytilishicha, agar 𝑝 tub son boʻlsa va 𝑎 𝑝 ga boʻlinmasa, u holda:
𝑎^(𝑝-1) ≡ 1 (mod 𝑝)
569 tub son va 55 soni 569 ga bo'linmasligi sababli bizda:
55^(568) ≡ 1 (mod 569)
Shuning uchun 𝑛 indeksi 568 ning boʻluvchisi boʻlishi kerak. 568 sonining tub faktorizatsiyasi 2^3 * 71 ekanligini tekshirishimiz mumkin. Demak, 568 sonining 16 ta boʻluvchisi bor, ular 𝑛 ning 16 ta mumkin boʻlgan qiymatiga mos keladi.
𝑛 ning to'g'ri qiymatini topish uchun biz ushbu mumkin bo'lgan qiymatlarning har birini hisoblash orqali sinab ko'rishimiz kerak:
55^(568/𝑛) (mod 569)
Agar biz ushbu tenglamani qanoatlantiradigan 𝑛 qiymatini topsak, u holda 𝑥 ni hal qilish uchun indeksni hisoblash usulidan foydalanishimiz mumkin.

function gcd(a, b) {
if (b === 0) return a;
return gcd(b, a % b);
}
function modExp(base, exponent, modulus) {
if (exponent === 0) return 1;
let result = 1;
base = base % modulus;
while (exponent > 0) {
if (exponent % 2 === 1) result = (result * base) % modulus;
exponent = exponent >> 1;
base = (base * base) % modulus;
}
return result;
}
function findPrimitiveRoot(p) {
let factors = [];
let phi = p - 1;
for (let i = 2; i * i <= phi; ++i) {
if (phi % i === 0) {
factors.push(i);
while (phi % i === 0) phi /= i;
}
}
if (phi > 1) factors.push(phi);
for (let r = 2; r <= p; ++r) {
let isRoot = true;
for (let i = 0; i < factors.length; ++i) {
if (modExp(r, (p - 1) / factors[i], p) === 1) {
isRoot = false;
break;
}
}
if (isRoot) return r;
}
return -1;
}
function indexMethod(a, b, p) {
let primitiveRoot = findPrimitiveRoot(p);
let aInd = -1;
let bInd = -1;
for (let i = 0; i < p - 1; ++i) {
if (modExp(primitiveRoot, i, p) === a) aInd = i;
if (modExp(primitiveRoot, i, p) === b) bInd = i;
if (aInd !== -1 && bInd !== -1) break;
}
let x = (bInd * modExp(aInd, p - 2, p - 1)) % (p - 1);
return x;
}
let a = 7;
let b = 92;
let p = 1433;
let x = indexMethod(a, b, p);
console.log(x);

a)

b )

ffie-Hellman muammosi (DHP) va El Gamal muammosi
(ELGAMAL) hisoblash ekvivalen

Diffie-Hellman muammosi (DHP) va El Gamal muammosi
(ELGAMAL) hisoblash nuqtai nazaridan ekvivalent ekanligini
ko'rsating.
Diffie-Hellman muammosi (DHP) va El Gamal muammosi (ELGAMAL) hisoblash nuqtai nazaridan ekvivalent ekanligini ko'rsatadigan misol :
Berilgan:
p = 23
g = 5
a = 6 (so g^a mod p = 5^6 mod 23 = 9)
b = 3 (shuning uchun g^b mod p = 5^3 mod 23 = 10)
Diffie-Hellman muammosi (DHP):
Hisoblash: g^ab mod p = 5^(6*3) mod 23 = ?
DHP hal qiluvchi yordamida yechim :
5^(6*3) mod 23
= 5^18 mod 23
= 15
Shuning uchun g^ab mod p = 15
El Gamal muammosi (ELGAMAL):
Berilgan:
m = 7
g = 5
g^a mod p = 9
m * g^b mod p = 7 * 10 = 70 mod 23 = 4
Hisoblash: m * g^ab mod p = ?
ELGAMAL hal qiluvchi yordamida yechim:
m * g^ab mod p
= 7 * 15
= 105 mod 23
= 13
Shuning uchun m * g^ab mod p = 13
Shunday qilib, biz buni ko'rsatdik:

• 
  DHP uchun hal qiluvchi ELGAMALni hal qilish uchun ishlatilishi mumkin
  
• 
  ELGAMAL uchun hal qiluvchi DHP ni hal qilish uchun ishlatilishi mumkin
  

Shuning uchun, ikkala muammo hisoblash jihatidan teng - hal qilish bir xil darajada qiyin.
Umid qilamanki, bu aniq misol DHP va ELGAMAL o'rtasidagi hisoblash ekvivalentligini aniqlashga yordam berdi! Boshqa savollaringiz bo'lsa, menga xabar bering.

Diffie-Hellman muammosi (DHP) va El Gamal muammosi (ELGAMAL) hisoblash jihatidan ekvivalentdir, ya'ni ularni hal qilish bir xil darajada qiyin. Buni quyidagicha ko'rsatish mumkin:
Diffie-Hellman muammosi (DHP):
berilgan g, g^a mod p va g^b mod p, g^ab mod p hisoblang.
El Gamal muammosi (ELGAMAL):
berilgan g, g^a mod p va m * g^b mod p , hisoblash m * g^ab mod p.
Biz ushbu muammolardan birini hal qila olsak, boshqasini ham hal qilishimiz mumkinligini ko'rsatmoqchimiz.
DHP dan ELGAMAL ga:
Agar g^a mod p va g^b mod p berilgan g^ab mod p ni topish uchun DHP ni yecha olsak, u holda ELGAMALni quyidagi yoʻl bilan ham hal qilishimiz mumkin:

1. 
   m * g^b mod p ni m ga bo‘lish, g^b mod p ni olish
   
2. 
   G^ab mod p topish uchun DHP hal qiluvchimizdan foydalaning
   
3. 
   g^ab mod p ni m ga ko'paytirish orqali m * g^ab mod p olinadi
   

ELGAMAL dan DHP ga:
Agar m * g^ab mod p berilgan g, g^a mod p va m * g^b mod p ni topish uchun ELGAMALni yecha olsak, u holda DHP ni quyidagi yo‘l bilan ham yecha olamiz:

1. 
   ELGAMAL muammosida m = 1 ni belgilash
   
2. 
   Yechim m * g^ab mod p keyin g^ab mod p ga aylanadi, DHP ni hal qiladi.
   

Xulosa qilib aytganda, biz ushbu muammolardan birini hal qilish algoritmidan boshqasini hal qilish uchun foydalanish mumkinligini ko'rsatdik. Shuning uchun, Diffie-Hellman muammosi va El Gamal muammosi hisoblash jihatidan ekvivalentdir - ularni hal qilish bir xil darajada qiyin.
Umid qilamanki, bu tushuntirish yordam berdi! Boshqa savollaringiz bo'lsa, menga xabar bering.

Aytaylik, Elis El Gamal ochiq kalit kriptotizimida foydalanish uchun kalitni (1237, 34, 383) nashr etdi.
o Siz Elisga m = 14 xabarini yubormoqchisiz. Siz aslida nimani uzatasiz?
Yechimmi
Elisning ElGamal ochiq kaliti yordamida m = 14 xabarini shifrlash uchun biz quyidagi amallarni bajarishimiz kerak:

1. 
   1 < k < p-1 bo'ladigan tasodifiy butun k sonni tanlang , bu erda p = 1237 ElGamal tizimining moduli.
   
2. 
   g ^ k mod p qiymatini hisoblang, bu erda g = 34 ElGama tizimining generatoridir.
   
3. 
   Elisning ochiq kalitining k-chi quvvat rejimiga ko'tarilgan m marta qiymatini hisoblang. Elisning ochiq kaliti (g^a, p, g), bu erda a = 383 uning shaxsiy kalitidir.
   
4. 
   Shifrlangan matnni (c1, c2) Elisga yuboring, bu erda c1 = g^k mod p va c2 = m * (g^a)^k mod p.
   

function modPow(base, exp, mod) {
if (exp == 0) {
return 1;
}
if (exp % 2 == 0) {
let temp = modPow(base, exp/2, mod);
return (temp * temp) % mod;
}
else {
return (base * modPow(base, exp-1, mod)) % mod;
}
}
let p = 1237;
let g = 34;
let a = 383;
let m = 14;
let k = Math.floor(Math.random() * (p - 2)) + 1; // choose a random k
let c1 = modPow(g, k, p);
let c2 = m * modPow(modPow(g, a, p), k, p) % p;
console.log( "Biz kutayotgan shifrmatn" ,[ c1,c2]