RSA Kriptografiyasi

RSA nima?

RSA (Rivest-Shamir-Adleman, 1977) — eng mashhur asimmetrik kriptosistema. Katta sonlarni faktorizatsiya qilishning qiyinligiga asoslangan.

Kalit yaratish (step-by-step)

Shifrlash va deshifrlash

from sympy import isprime, mod_inverse
import random

def rsa_keygen(bits: int = 512):
    # RSA kalit juft yaratish
    # 1. Ikkita katta tub son
    # (Sodda misol uchun kichik sonlar)
    p = 61
    q = 53
    
    # 2. n
    n = p * q  # 3233
    
    # 3. phi
    phi = (p - 1) * (q - 1)  # 3120
    
    # 4. e
    e = 17  # gcd(17, 3120) = 1
    
    # 5. d (modular teskari)
    d = mod_inverse(e, phi)  # 2753
    
    return (n, e), (n, d)

def rsa_encrypt(m: int, n: int, e: int) -> int:
    # Shifrlash: c = m^e mod n
    return pow(m, e, n)

def rsa_decrypt(c: int, n: int, d: int) -> int:
    # Deshifrlash: m = c^d mod n
    return pow(c, d, n)

# Misol
public_key, private_key = rsa_keygen()
n, e = public_key
_, d = private_key

print(f"Ochiq kalit: n={n}, e={e}")
print(f"Maxfiy kalit: d={d}")

message = 65  # Shifrlash uchun son
ciphertext = rsa_encrypt(message, n, e)
print(f"Shifrlangan: {ciphertext}")  # 2790

decrypted = rsa_decrypt(ciphertext, n, d)
print(f"Deshifrlangan: {decrypted}")  # 65

CTF da RSA hujumlari

from sympy import integer_nthroot
from math import isqrt

# e=3 Cube Root hujumi
def cube_root_attack(c: int, n: int) -> int:
    "m^3 < n bolsa ishlaydi"
    m, perfect = integer_nthroot(c, 3)
    if perfect:
        return m
    return None

# Fermat faktorizatsiya
def fermat_factor(n: int):
    "p va q bir biriga yaqin bolsa"
    a = isqrt(n) + 1
    while True:
        b2 = a * a - n
        b = isqrt(b2)
        if b * b == b2:
            return (a - b, a + b)
        a += 1

# n = 100000007
p, q = fermat_factor(100000007)
print(f"p={p}, q={q}")  # p=9999, q=10001