Kriptografiya 1 fanidan Loyiha ishi Guruh: cry002 Bajardi

O`ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI



kriptografiya 1 fanidan
Loyiha ishi
Guruh: CRY002


Bajardi: Boltayev Ravshanbek Jumaboyev Faxriyor
Matyoqubov Yusufboy Muhammadiyev Komil
Normengliyev Boymurod Sayidov Firdavs
Tekshirdi: Mardiyev Ulug’bek.
Toshkent-2023


7. 𝑃 = 2²⁵⁶ − 2²²⁴ + 2¹⁹² + 2⁹⁶ − 1 va 𝑔 = 2 asosini hisobga olgan holda, 𝑚𝑜𝑑 𝑝 da 123456789 ning diskret logarifmini toping.

Z^*_p chekli siklik guruh berilgan bo’lsin va α , β € Z^*_p. Tenglikdan x noma’lum butun sonni toppish lozim va 1 ≤ x ≤ p – 1

α^x ≡ β mod p
Bu yerda, 𝑥 butun son 𝛼 asosga ko’ra 𝛽 ning diskret logarifmi asosida hisoblanadi va u quyidagiga teng bo’ladi:

x = log_α β mod p

Chekli gruppada diskret logarifmni hisoblash
Biz shu paytgacha chegirmalar nazariyasi bo’yicha tanishganimizda
a^x mod p;
ifoda qiymatini topish bilan tanishgan edik.
Quyidagi masala esa oldingi masaladan ko’ra murakkabrok hisoblanadi, yani shunday x- butun son topilsinki :
a^x  b (mod p) (1)
o’rinli bo’lsin. Bu yerda r-tub son va (1) tenglama (Z /pZ) gruppada qaralayapti.

(1) tenglamaning yechimi x =log a b - ni quyidagi formula orqali topish mumkin:

Biroq bu formula bilan yechimni topish masalasi bevosita «mumkin bo’lgan barcha xolatlarni ko’rib chiqish» kabi usulga o’xshash bo’lgani uchun ham amalda bu formula qo’llanilmaydi. Quyida keltiriladigan algoritm esa hisoblashlar sonini qisqartirib yechimni topishning samarali usulini beradi.

Diskret logarifmlash algoritmi:
1- qadam. Quyidagi son hisoblansin.
H:= [ p^1/2 ] + 1
2- qadam. Quyidagi son hisoblansin.
C  a^H (mod p)
3- qadam. u, 1  u  H sonli qiymatlari uchun C u (mod p) jadval tuzing. Bu qiymatlarni tartiblab chiqing.
4 – qadam. Keyingi jadval esa b*a v (mod p) , 0  v  H qiymatlar uchun tuzilib tartiblansin.
5- qadam. Birinchi va ikkinchi jadvalda teng chiqqan u, v elementlar olinsin.
6- qadam. Javob sifatida
x  H*u – v (mod p-1)
olinsin.


2- algoritm
Polig-Xelman algoritmi(Pohlig-Hellman)
Eyler teoremasi: Agar, a, m o'zaro tub sonlar bo'lsa u holda a ^(m)  1 (mod m) bo'ladi, bu yerda  (m) - Eyler funksiyasi.

 N = pq teng bo'lsin, EKUB p, q = 1. a^x = b (mod p) ni yechish uchun Polig-Xelman algoritmi quyidagi yondashuvga asoslanadi. x = a₀ +a₁ p teng bo'lsin.

Bundan
a^x  b
a^qx  b^q
a^q(a0+a1*p)  b^q
(a^q)^a0(a^a1)^pq  b^q
a^q va b^q topulguncha, a_o ni tanlash yo'li bilan topamiz va x = a₀ +a₁p topulguncha, keyin x  a₀mod p.
Xuddi shu yo'l oqali x  b_o mod q ni ham topamiz. Shundan so'ng qoldiqlar haqidagi Xitoy teoramasidan foydalanib x ni topamiz.

C = 24222668243131884808741022100933642382729471088349810791616108529809929000908

H = 15592102382884305881604928301670257973546352220110352770757634434092538409771
u = 5743223920373611369593700761855384903808286661154983405249305239434567869668537681399469472106319544960888335839732582885404937797481214952244160323066742
v = 5743223920373611369593700761855384903808286661154983405249305239434567869668537681399469472106319544960888335839732582885404937797481214952244160323066742
x = H * u - v ( mod p - 1 ) = 10385224669612839384368647610889220844774431758635855015193981267163114676926

Dastur natijasi:

Java dasturida:
import java.math.BigInteger;

public class Main {

public static void main(String[] args) {
System.out.println("C = a^N (mod p)");

BigInteger a = BigInteger.valueOf(2);

BigInteger b = BigInteger.valueOf(123456789);

BigInteger p = BigInteger.valueOf(2).pow(256)

.subtract(BigInteger.valueOf(2).pow(224))
.add(BigInteger.valueOf(2).pow(192))
.add(BigInteger.valueOf(2).pow(96))
.subtract(BigInteger.ONE);

BigInteger H = p.sqrt().add(BigInteger.ONE);

BigInteger C = a.modPow(H, p);
System.out.println("C = " + C + " H = " + H);

int hLength = H.intValue();

for (int i = 0; i < hLength; i++) {

BigInteger u = C.modPow(BigInteger.valueOf(i), p);

for (int j = 0; j <= hLength; j++) {

BigInteger v = b.multiply(a.modPow(BigInteger.valueOf(i), p)).mod(p);

if (u.equals(v)) {
BigInteger x = H.multiply(u).subtract(v).mod(p.subtract(BigInteger.ONE));
System.out.println("u = " + u + " v = " + v);
System.out.print("x = H * u - v ( mod p - 1 ) = ");
System.out.println(x);
}
}
}
}
}