⊕

Modulli Arifmetika

Kriptografiyaning matematika asosi — mod, GCD, Euler, Fermat

Modulli arifmetika — raqamlar ma'lum chegarada "aylanib" hisob-kitob qilinadigan tizim. Soat 12 dan keyin 1 bo'lishi kabi, 17 mod 12 = 5. Bu oddiy tushuncha RSA, Diffie-Hellman, ECC va barcha zamonaviy kriptografiyaning poydevori hisoblanadi. Bu darsni yaxshi tushunmasdan asimmetrik kriptografiyani o'rganib bo'lmaydi.

Mod (%) Operatori

Amaliy misollar:

>>> 17 % 12
5
>>> 100 % 7
2
>>> -7 % 3
2          # Python manfiy sonlarda ijobiy qaytaradi
>>> 2**10 % 1000
24         # 1024 % 1000 = 24

# Katta sonlarda ham tez ishlaydi:
>>> pow(2, 1000, 997)  # 2^1000 mod 997
# Python ichki optimizatsiya bilan hisoblaydi!

Modulli arifmetika qoidalari:

(a+b) mod n = ((a mod n) + (b mod n)) mod n

(a×b) mod n = ((a mod n) × (b mod n)) mod n

(aᵏ) mod n — pow(a, k, n) bilan tez hisob

a ≡ b (mod n) → n | (a - b), ya'ni n bo'ladi

GCD — Eng Katta Umumiy Bo'luvchi (Evklid Algoritmi)

GCD(a, b) — ikki sonning eng katta umumiy bo'luvchisi. Kriptografiyada RSA kalitlarini tekshirishda, teskari element topishda asosiy ahamiyat kasb etadi. Evklid algoritmi miloddan avvalgi ~300-yil kashf qilingan, lekin bugungi kunda ham eng samarali usul!

Evklid Algoritmi:

GCD(a, b) qoida:

GCD(a, 0) = a

GCD(a, b) = GCD(b, a mod b)

Misol: GCD(48, 18) hisoblash:

GCD(48, 18)= GCD(18, 48 mod 18)

GCD(18, 12)= GCD(12, 18 mod 12)

GCD(12, 6)= GCD(6, 12 mod 6)

GCD(6, 0)= 6 Javob!

Python implementatsiyasi:

# Oddiy GCD (rekursiv)
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

print(gcd(48, 18))   # 6
print(gcd(100, 75))  # 25

# Python da tayyor funksiya:
from math import gcd
print(gcd(48, 18))   # 6

# Nisbiy tub sonlar (coprime):
# GCD(a, b) = 1 bo'lsa, a va b coprime
print(gcd(15, 28))   # 1 → coprime!
print(gcd(12, 18))   # 6 → NOT coprime

Kengaytirilgan Evklid Algoritmi (Extended GCD)

GCD(a, b) = ax + by shaklida yozish imkonini beradi. Bu kriptografiyada teskari element (modular inverse) topish uchun ishlatiladi. RSA da bu juda muhim!

Misol: GCD(30, 11) va x, y topish:

30 = 2×11 + 8 → 8 = 30 - 2×11

11 = 1×8 + 3 → 3 = 11 - 1×8

8 = 2×3 + 2 → 2 = 8 - 2×3

3 = 1×2 + 1 → 1 = 3 - 1×2

1 = 4×30 - 11×11

Demak x=4, y=-11

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = extended_gcd(b, a % b)
    return g, y, x - (a // b) * y

# Teskari element: a * x ≡ 1 (mod n)
def mod_inverse(a, n):
    g, x, _ = extended_gcd(a % n, n)
    if g != 1:
        raise ValueError("Teskari yo'q!")
    return x % n

print(mod_inverse(3, 11))   # 4 → 3×4=12≡1(mod 11)
print(mod_inverse(7, 26))   # 15 → 7×15=105≡1(mod 26)

φ Euler's Totient Funksiyasi — φ(n)

φ(n) — 1 dan n gacha bo'lgan, n bilan nisbiy tub (coprime) sonlar soni. RSA algoritmida kalit generatsiyasining markaziy qismi.

Formulalar:

p tub son bo'lsa:

φ(p) = p - 1

p, q tub sonlar bo'lsa:

φ(p×q) = (p-1)(q-1)

Umumiy holda:

φ(pᵏ) = pᵏ - pᵏ⁻¹

φ(7) = 6 (1,2,3,4,5,6 — barchasi coprime 7 bilan)

φ(8) = 4 (1,3,5,7 — toq sonlar)

φ(12) = 4 (1,5,7,11)

φ(15) = 8 = (3-1)(5-1) = 2×4

from math import gcd

def euler_totient(n):
    count = 0
    for i in range(1, n):
        if gcd(i, n) == 1:
            count += 1
    return count

# Tub son uchun tez usul:
def phi(n):
    # Tub bo'luvchilar bilan hisoblash
    result = n
    p = 2
    temp = n
    while p * p <= temp:
        if temp % p == 0:
            while temp % p == 0:
                temp //= p
            result -= result // p
        p += 1
    if temp > 1:
        result -= result // temp
    return result

print(phi(7))    # 6
print(phi(15))   # 8
print(phi(100))  # 40

# RSA uchun: p=61, q=53 (tub sonlar)
p, q = 61, 53
n = p * q            # 3233
phi_n = (p-1)*(q-1)  # 3120
print(f"n={n}, φ(n)={phi_n}")

Fermat va Euler Teoremalari

Fermat'ning Kichik Teoremasi

aᵖ⁻¹ ≡ 1 (mod p)

p tub, a ni p ga bo'lmasa

aᵖ ≡ a (mod p)

p tub, har qanday a uchun

Misol: a=2, p=7
2⁶ mod 7 = 64 mod 7 = 1

Euler Teoremasi (kengaytma)

a^φ(n) ≡ 1 (mod n)

GCD(a, n) = 1 bo'lsa

n tub bo'lsa φ(n)=n-1, shuning uchun Fermat maxsus holat!

Amaliy ishlatilishi:

# Fermat teoremasi bilan teskari element
# a * a^(p-2) ≡ 1 (mod p)
# Demak: a^(-1) ≡ a^(p-2) (mod p)

def fermat_inverse(a, p):
    """p tub son bo'lsa teskari element"""
    return pow(a, p - 2, p)

print(fermat_inverse(3, 7))  # 5 → 3×5=15≡1(mod7)

# RSA da Euler teoremasi:
# m^(e*d) ≡ m (mod n)
# Chunki e*d ≡ 1 (mod φ(n))
# va m^φ(n) ≡ 1 (mod n)

# Katta darajalar tez hisoblash:
# pow(base, exp, mod) — O(log exp)
print(pow(2, 10**18, 10**9 + 7))  # tezkor!

Nima uchun kriptografiyada muhim?

• RSA: m^(ed) ≡ m (mod n) — shifrlash/ochish
• Teskari element hisoblash
• Miller-Rabin tub son testi
• Diffie-Hellman xavfsizligi

Xitoy Qoldiq Teoremasi (CRT)

Bir nechta modulli tenglamalar sistemasini birlashtirib yechish usuli. CTF da RSA hujumlarida (Håstad's broadcast attack) va RSA tezlashtirish uchun ishlatiladi.

Teorema:

Agar n₁, n₂, ..., nₖ — juft tub bo'lsa,

x ≡ a₁ (mod n₁)

x ≡ a₂ (mod n₂)

...

sistemasining yechimi yagona (mod n₁×n₂×...).

Misol:

x ≡ 2 (mod 3)

x ≡ 3 (mod 5)

x ≡ 2 (mod 7)

x = 23 (mod 105) ← yagona yechim

def crt(remainders, moduli):
    """Chinese Remainder Theorem"""
    from functools import reduce

    N = reduce(lambda a, b: a * b, moduli)
    result = 0

    for ai, ni in zip(remainders, moduli):
        Ni = N // ni
        # Ni ning ni ga nisbatan teskari
        yi = pow(Ni, -1, ni)  # Python 3.8+
        result += ai * Ni * yi

    return result % N

# Misol:
r = [2, 3, 2]   # qoldiqlar
m = [3, 5, 7]   # modullar
x = crt(r, m)
print(x)  # 23

# Tekshirish
for ai, ni in zip(r, m):
    print(f"{x} mod {ni} = {x % ni}")
# 23 mod 3 = 2 ✓
# 23 mod 5 = 3 ✓
# 23 mod 7 = 2 ✓

CTF da CRT ishlatilishi — Håstad Attack:

Agar bir xil m xabar e=3 bilan uchta turli RSA kalitida shifrlangan bo'lsa (c₁, c₂, c₃), CRT orqali m³ topiladi va oddiy kub ildiz m ni beradi! m = ∛(CRT(c₁,c₂,c₃))