O'quv Markazi / Kriptografiya / Asimmetrik Shifrlash

Asimmetrik Shifrlash: RSA va Diffie-Hellman

Ochiq va yopiq kalitlar, RSA ning matematik asoslari (Euler, mod teskari), Diffie-Hellman kalit almashinuvi, ECC, va raqamli imzolar — zamonaviy internet xavfsizligining poydevori.

RSA Diffie-Hellman ECC / ECDH Raqamli Imzo CTF RSA

1 Asimmetrik Shifrlash Nima?

Kalit muammosi yo'q

Ochiq kalitni xavfsiz kanal talab etmaydi — istalgan joyda tarqatish mumkin.

Raqamli Imzo

Yopiq kalit bilan imzo qo'yiladi, ochiq kalit bilan tekshiriladi.

Sekin

Simmetrik shifrlashdan 1000x sekin. Shuning uchun Hybrid Encryption ishlatiladi.

2 RSA (Rivest–Shamir–Adleman)

RSA — 1977-yilda Rivest, Shamir va Adleman tomonidan ixtiro qilingan. Xavfsizligi katta sonlarni bo'luvchilarga ajratishning qiyinligiga (Integer Factorization Problem) asoslanadi. n=p×q dan p va q ni topish eksponensial vaqt talab etadi.

RSA Shifrlash va Deshifrlash

Shifrlash (ochiq kalit bilan):

C = Mᵉ mod n

M=65 (xabar), e=17, n=3233

C = 65¹⁷ mod 3233 = 2790

Deshifrlash (yopiq kalit bilan):

M = Cᵈ mod n

C=2790, d=2753, n=3233

M = 2790²⁷⁵³ mod 3233 = 65

Nima uchun ishlaydi? (Matematik asosi)

Euler teoremasi:

a^φ(n) ≡ 1 (mod n), GCD(a,n)=1

Deshifrlash isboti:

C^d = (M^e)^d = M^(e·d)

e·d ≡ 1 (mod φ(n))

e·d = 1 + k·φ(n)

M^(e·d) = M·(M^φ(n))^k ≡ M·1^k = M (mod n)

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Signature import pss
from Crypto.Hash import SHA256

# ============================================
# RSA kalit generatsiyasi
# ============================================
key = RSA.generate(2048)  # Minimum 2048-bit
public_key = key.publickey()

# Kalitlarni saqlash
with open('private.pem', 'wb') as f:
    f.write(key.export_key())
with open('public.pem', 'wb') as f:
    f.write(public_key.export_key())

# ============================================
# RSA shifrlash (OAEP padding bilan)
# ============================================
def rsa_encrypt(message: bytes, public_key) -> bytes:
    cipher = PKCS1_OAEP.new(public_key)
    return cipher.encrypt(message)

def rsa_decrypt(ciphertext: bytes, private_key) -> bytes:
    cipher = PKCS1_OAEP.new(private_key)
    return cipher.decrypt(ciphertext)

# ============================================
# Raqamli imzo
# ============================================
def sign_message(message: bytes, private_key) -> bytes:
    h = SHA256.new(message)
    signature = pss.new(private_key).sign(h)
    return signature

def verify_signature(message: bytes, signature: bytes, public_key) -> bool:
    h = SHA256.new(message)
    try:
        pss.new(public_key).verify(h, signature)
        return True
    except:
        return False

# ============================================
# CTF: RSA oddiy misol (kichik n uchun)
# ============================================
def rsa_manual():
    p, q = 61, 53
    n = p * q                        # 3233
    phi = (p - 1) * (q - 1)         # 3120
    e = 17
    d = pow(e, -1, phi)              # Python 3.8+ modular inverse
    print(f"d = {d}")                   # 2753

    M = 65
    C = pow(M, e, n)                  # Shifrlash: 65^17 mod 3233 = 2790
    M2 = pow(C, d, n)                 # Deshifrlash: 2790^2753 mod 3233 = 65
    print(f"Shifr: {C}, Asl: {M2}")

rsa_manual()

3 CTF'da RSA Hujumlari

Small e Attack (e=3, kichik M)

Agar e=3 va M kichik bo'lsa, M³ < n — mod hech qachon ishlatilmagan.

import gmpy2
# C = M^3 (mod n ishlatilmagan)
M = gmpy2.iroot(C, 3)[0]

Common Modulus Attack

Bir xil M ni ikki xil e bilan shifrlagan bo'lsa va GCD(e1,e2)=1:

# Bezout: a*e1 + b*e2 = 1
# M = C1^a * C2^b mod n
a, b, _ = extended_gcd(e1, e2)
M = pow(C1,a,n) * pow(C2,b,n) % n

Small Prime Factor (factordb)

n ni factordb.com da qidirish — agar avval buzilgan bo'lsa.

# n = p * q topilsa:
phi = (p-1) * (q-1)
d = pow(e, -1, phi)
M = pow(C, d, n)

Håstad Broadcast Attack

Bir xil M ni e=3 ta turli n bilan shifrlagan bo'lsa (CRT):

from sympy.ntheory.modular import crt
# C1,C2,C3 → M^3 via CRT → iroot(3)
M3, _ = crt([n1,n2,n3], [C1,C2,C3])
M = gmpy2.iroot(M3, 3)[0]

Wiener Attack (katta d)

d < n^(1/4) bo'lsa, davomiy kasrlar (continued fractions) bilan d topiladi.

# owiener Python library
import owiener
d = owiener.attack(e, n)

CTF RSA checklisti

□ n ni factordb.com da qidirish
□ e=3 va kichik M? → cube root
□ Bir xil n, bir xil M, turli e? → common modulus
□ e=3, 3 ta n? → Håstad broadcast
□ Katta e, kichik d? → Wiener attack
□ p va q yaqin? → Fermat factorization
□ RsaCtfTool GitHub repo ishlatish

4 Diffie-Hellman Kalit Almashinuvi

1976-yilda Whitfield Diffie va Martin Hellman tomonidan ixtiro qilingan. Ikkita tomon umumiy sir kalitni ochiq kanal orqali almashishi mumkin. Xavfsizligi Diskret Logarifm Muammosiga (DLP) asoslanadi.

Nima uchun ishlaydi?

Alice hisoblaydi:

K = B^a = (g^b)^a = g^(ab) mod p

Bob hisoblaydi:

K = A^b = (g^a)^b = g^(ab) mod p

Ikkalasi g^(ab) mod p ga keladi!

Tajovuzkor p, g, A=g^a, B=g^b ni biladi, lekin a yoki b ni bilmaydi. Diskret logarifm muammosi: g^a mod p dan a ni topish — hisoblash jihatdan qiyin.

import secrets

def diffie_hellman():
    # Ochiq parametrlar (haqiqatda 2048+ bit)
    p = 23   # Tub son
    g = 5    # Generator (g < p, primitiv ildiz)

    # Alice
    a = secrets.randbelow(p - 2) + 2
    A = pow(g, a, p)   # Alice ochiq qiymati

    # Bob
    b = secrets.randbelow(p - 2) + 2
    B = pow(g, b, p)   # Bob ochiq qiymati

    # Almashinuv (ochiq kanalda)
    # Alice B ni oladi, Bob A ni oladi

    # Umumiy sir
    K_alice = pow(B, a, p)  # Alice: B^a mod p
    K_bob   = pow(A, b, p)  # Bob: A^b mod p

    assert K_alice == K_bob, "Xato!"
    print(f"Sir kalit: {K_alice}")
    return K_alice

# Real hayotda ECDH (elliptik egri) ishlatiladi:
from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey
private_key = X25519PrivateKey.generate()
public_key = private_key.public_key()
# Partner ochiq kaliti bilan:
# shared = private_key.exchange(partner_public_key)