Kriptografiyaning matematik asoslari

Ochiq kalitli kriptografiya — sonlar nazariyasining amaliy mo'jizasi. Bu mavzuda RSA, ElGamal, Diffi–Xellman va imzolarni tushunish uchun zarur bo'lgan barcha matematik vositalarni noldan o'rganamiz.

Bo'linish, EKUB va o'zaro tub sonlar

a ≠ 0 va b butun sonlar bo'lsin. Agar b = a·c tenglikni qanoatlantiruvchi butun c mavjud bo'lsa, b soni a ga bo'linadi. Ikki sonni bo'luvchi sonlar ularning umumiy bo'luvchisi, eng kattasi — eng katta umumiy bo'luvchi, EKUB (a, b). Agar (a, b) = 1 bo'lsa, a va b o'zaro tub deyiladi.

Evklid algoritmi

Evklid bu usulni mil. av. 300-yilda «Negizlar» kitobida keltirgan — bu hozirgacha ishlatiladigan eng qadimgi algoritmlardan biri. G'oya: EKUB(a, b) = EKUB(b, a mod b).

1. a = b bo'lsa, EKUB = a.
2. a > b bo'lsa, a = b·q + r (0 ≤ r < b). r = 0 bo'lsa, EKUB = b.
3. Aks holda b = r·q₁ + r₁ va hokazo — qoldiq 0 bo'lguncha. Oxirgi noldan farqli qoldiq — EKUB.

Modul arifmetikasi

a sonini n ga qoldiq bilan bo'lish: a = q·n + r, 0 ≤ r < n. Qoldiq r = a mod n. Agar ikki son n ga bo'linganda bir xil qoldiq bersa, ular n modul bo'yicha taqqoslanadi: a ≡ b (mod n). {0, 1, …, n−1} to'plam — n modul bo'yicha to'liq chegirmalar tizimi.

Bu xossalar tufayli katta sonlar bilan ishlaganda har bir qadamda mod olib, sonlarni kichik saqlash mumkin.

Teskari element

Agar (a, n) = 1 bo'lsa, (a·b) mod n = 1 ni qanoatlantiruvchi yagona b mavjud — u a ning n modul bo'yicha teskarisi: b = a⁻¹ mod n. a va n o'zaro tub bo'lmasa, teskari mavjud emas. a va b o'zaro tub bo'lishi uchun a·u + b·v = 1 ni qanoatlantiruvchi butun u, v mavjud bo'lishi zarur va yetarli (Bezu ayniyati) — kengaytirilgan Evklid algoritmi aynan shu u ni topadi.

Eyler funksiyasi va teoremalar

Eyler funksiyasi φ(n) — 1 dan n gacha bo'lgan, n bilan o'zaro tub sonlar soni:

Kitobdagi misol: 21⁻¹ mod 41. 41 tub → φ(41) = 40 → 21⁻¹ = 21³⁹ mod 41 = 2. Tekshiruv: 21·2 = 42 ≡ 1 (mod 41) ✓.

Tub sonlar va faktorlash

p > 1 natural son o'zi va 1 dan boshqa songa bo'linmasa — tub: 2, 3, 5, 7, 11, 13, … Ularning soni cheksiz (Evklid isboti). Sonni tub ko'paytuvchilarga ajratish (faktorlash) — sonlar nazariyasining eng qadimgi masalalaridan biri. Kichik sonlar uchun oson, lekin raqamlar soni oshgani sari vaqt keskin ortadi. Ma'lum algoritmlar:

1. Sonli maydon umumiy g'alviri — 110 va undan ko'p xonali sonlar uchun eng samarali;
2. Kvadratik g'alvir — 110 xonagacha bo'lgan sonlar uchun eng samarali;
3. Elliptik egri chiziq usuli — tub ko'paytuvchilari 43 xonagacha bo'lgan sonlar uchun;
4. Pollardning Monte-Karlo (ρ) usuli;
5. Uzluksiz kasrlar usuli;
6. Tanlab bo'lish — √n gacha bo'lgan har bir tub son bilan bo'lib ko'rish (eng sodda).

Tub sonlar generatsiyasi: katta sonning tubligini tekshirish uni faktorlashdan ancha oson. Buning uchun ehtimollik testlari (Ferma, Miller–Rabin) ishlatiladi — ular sonning tubligini berilgan ishonch darajasi bilan aniqlaydi.

Diskret logarifm, kvadratik chegirmalar, yasovchilar

Diskret logarifm. y = a^x mod n ni x bo'yicha hisoblash oson, lekin y ma'lum bo'lsa x ni topish — murakkab masala. Bu ElGamal, Diffi–Xellman, DSA va GOST imzosining asosi. Kriptografiyada GF(p), GF(2ⁿ) maydonlarida va elliptik egri chiziqlar ustida diskret logarifmlash qo'llaniladi.

Yasovchi (primitiv ildiz). p tub son, g < p. Agar 1 dan p−1 gacha bo'lgan har bir b uchun g^a mod p = b ni qanoatlantiruvchi a topilsa, g — p modul bo'yicha yasovchi. Masalan, 5 — 23 modul bo'yicha yasovchi.

Kvadratik chegirma. p tub, 0 < a < p. Agar x² ≡ a (mod p) yechimga ega bo'lsa, a — kvadratik chegirma. U holda ikkita kvadrat ildiz bor (x va p − x). Rabin algoritmi va Feige–Fiat–Shamir sxemasi shunga asoslangan.

Algoritmlar murakkabligi

Algoritm murakkabligi — uni bajarish uchun zarur amallar soni: vaqt bo'yicha T va xotira bo'yicha S, kirish o'lchami n ga bog'liq funksiyalar. «O katta» belgisi eng tez o'suvchi hadni ko'rsatadi: T = 5n² + 6n + 11 bo'lsa, T = O(n²).

Nazorat savollari