RSA Common Modulus Saldırısı

Ne Zaman Kullan

Aşağıdaki koşullar sağlanıyorsa bu tekniği dene:

• Aynı N (modulus) kullanılmış, farklı e1 ve e2 ile
• Aynı mesaj m her iki anahtarla şifrelenmiş:

  c1 = m^e1 mod N
  c2 = m^e2 mod N
  

• gcd(e1, e2) == 1 (coprime — birbirlerine göre asallar)

Nereden anlarsın?

• Challenge iki farklı public key veriyor ama N aynı
• Kaynak kodda n = p * q bir kez üretiliyor, e farklı seçiliyor
• "Bob her mesajı iki farklı alıcıya gönderdi" senaryosu

Bu teknik çalışmaz eğer:

• gcd(e1, e2) > 1 — bu durumda farklı yaklaşım gerekir (aşağıda açıklandı)
• Mesajlar farklı (m1 ≠ m2) — şifreleme farklı plaintext üzerinde yapılmış

---

Matematiksel Temel

Bezout Lemması

İki tamsayı a ve b için gcd(a, b) = 1 ise, şunu sağlayan x ve y tam sayıları vardır:

a*x + b*y = 1

Saldırının Mantığı

Bezout lemmasını e1 ve e2 için uygula:

e1*a + e2*b = 1        (a, b < 0 veya > 0 olabilir)

Extended GCD algoritması bunu bulur. Sonra:

c1^a * c2^b mod N
= (m^e1)^a * (m^e2)^b mod N
= m^(e1*a) * m^(e2*b) mod N
= m^(e1*a + e2*b) mod N
= m^1 mod N
= m

Negatif üsler için modüler ters gerekir:

c^(-k) mod N  ≡  modinv(c, N)^k mod N

---

Tam Python Exploit Kodu

#!/usr/bin/env python3
"""
RSA Common Modulus Saldirisi
Ayni N, farkli e1 ve e2 ile sifrelenip gcd(e1,e2)=1 ise calısır.

Gereksinimler: pycryptodome
  pip install pycryptodome
"""

import math
from Crypto.Util.number import long_to_bytes


def extended_gcd(a: int, b: int):
    """
    Genisletilmis Oklid algoritmasi.
    Dondurur: (g, x, y) oyle ki a*x + b*y = g = gcd(a, b)
    """
    if a == 0:
        return b, 0, 1
    g, x, y = extended_gcd(b % a, a)
    return g, y - (b // a) * x, x


def modinv(a: int, m: int) -> int:
    """a'nin m modülundeki tersi. gcd(a,m)=1 olmali."""
    g, x, _ = extended_gcd(a % m, m)
    if g != 1:
        raise ValueError(f"Modüler ters yok: gcd({a},{m}) = {g}")
    return x % m


def common_modulus_attack(n: int, e1: int, e2: int, c1: int, c2: int) -> bytes:
    """
    RSA Common Modulus saldırısı.

    Parametreler:
        n  : Ortak modulus
        e1 : Birinci public exponent
        e2 : Ikinci public exponent
        c1 : c1 = m^e1 mod n
        c2 : c2 = m^e2 mod n

    Dondurur: plaintext (bytes)
    """
    # On kontrol
    g = math.gcd(e1, e2)
    if g != 1:
        print(f"[!] UYARI: gcd(e1, e2) = {g}, saldiri dogrudan calismayabilir.")
        print(f"    e1 = {e1}, e2 = {e2}")
        print(f"    Fallback: e1,e2'yi {g}'ye bol ve dene.")
        # Fallback: ortak boleni at
        e1_r, e2_r = e1 // g, e2 // g
        return common_modulus_attack(n, e1_r, e2_r, c1, c2)

    # Bezout katsayılarını bul: e1*a + e2*b = 1
    gcd_val, a, b = extended_gcd(e1, e2)
    print(f"[*] e1*a + e2*b = 1 cozumu:")
    print(f"    a = {a}")
    print(f"    b = {b}")
    print(f"    Dogrulama: {e1}*{a} + {e2}*{b} = {e1*a + e2*b}")

    # Negatif usler icin modüler ters kullan
    if a < 0:
        # c1^a mod n = modinv(c1, n)^(-a) mod n
        c1_part = pow(modinv(c1, n), -a, n)
    else:
        c1_part = pow(c1, a, n)

    if b < 0:
        c2_part = pow(modinv(c2, n), -b, n)
    else:
        c2_part = pow(c2, b, n)

    # m = c1^a * c2^b mod n
    m = (c1_part * c2_part) % n
    print(f"[+] Mesaj (int): {m}")

    result = long_to_bytes(m)
    print(f"[+] Mesaj (bytes): {result}")
    return result


# =========================================================
# CHALLENGE DEGERLERİNİ BURAYA KOY
# =========================================================
if __name__ == "__main__":
    # Ornek — gercek challenge degerlerini buraya yapistir:
    n  = 0xDEADBEEFCAFEBABE   # Ortak modulus
    e1 = 17                    # Birinci exponent
    e2 = 65537                 # Ikinci exponent
    c1 = 0xAAAA                # Birinci sifreli metin
    c2 = 0xBBBB                # Ikinci sifreli metin

    flag = common_modulus_attack(n, e1, e2, c1, c2)
    print(f"\n[!!!] FLAG: {flag.decode(errors='replace')}")

---

CryptoCTF 2021 — DoRSA Detaylı Örneği

Challenge Açıklaması: "RSA with a twist. The twist is continued fractions."

Verilen:

n  = [büyük sayı]
e1 = [büyük sayı — n'ye yakın]
e2 = [büyük sayı — n'ye yakın]
c1 = m^e1 mod n
c2 = m^e2 mod n

Özellik: e1 ve e2 çok büyük — neredeyse n kadar. Bu durumda standart common modulus saldırısı çalışır ama Bezout katsayıları a ve b astronomik büyür.

CryptoCTF varyantında ek zorluk: Challenge adında "DoRSA" ve continued fraction ipucu verilmiş. Aslında e1 * e2 ≈ n ve d ≈ sqrt(N) gibi ilişkiler kurulabiliyor.

# CryptoCTF DoRSA - genellestirilmis cozum cercevesi
from math import gcd, isqrt
from Crypto.Util.number import long_to_bytes

def solve_dorsa(n, e1, e2, c1, c2):
    """
    DoRSA tarzı challenge için ortak modulus + fallback yaklaşımı.
    """

    # Adim 1: gcd(e1, e2) kontrol
    g = gcd(e1, e2)
    print(f"[*] gcd(e1, e2) = {g}")

    if g == 1:
        # Klasik common modulus yeterli
        return common_modulus_attack(n, e1, e2, c1, c2)

    # Adim 2: gcd > 1 durumu — ortak faktoru indir
    # e1/g ve e2/g hala coprime mi?
    e1r, e2r = e1 // g, e2 // g
    g2 = gcd(e1r, e2r)
    print(f"[*] Indirgenmis: e1/g = {e1r}, e2/g = {e2r}, gcd = {g2}")

    if g2 == 1:
        # m^g'yi bul, sonra g. koku al
        m_g = common_modulus_attack(n, e1r, e2r, c1, c2)
        m_g_int = int.from_bytes(m_g, 'big')
        print(f"[*] m^{g} bulundu: {m_g_int}")

        # g. kok (tam sayi), ozellikle g=2 veya 3 ise makul
        m_candidate, is_perfect = gmpy2_iroot(m_g_int, g)
        if is_perfect:
            return long_to_bytes(m_candidate)
        else:
            print(f"[-] {g}. kök tam sayi degil — başka yaklasım lazim")
            return None

    print("[-] Indirgenmiş exponentler de coprime degil. Daha karmasik durum.")
    return None


def gmpy2_iroot(n, k):
    """gmpy2 olmadan tam kök kontrolü (küçük k için)."""
    try:
        import gmpy2
        return gmpy2.iroot(n, k)
    except ImportError:
        # Basit Newton yöntemi
        if k == 2:
            r = isqrt(n)
            return r, r * r == n
        # Genel Newton
        r = int(n ** (1/k))
        for candidate in [r-1, r, r+1]:
            if candidate ** k == n:
                return candidate, True
        return r, False

---

Tuzaklar

1. gcd(e1, e2) > 1 Durumu

En sık karşılaşılan zorluk. Örnek:

e1 = 6,  e2 = 10  →  gcd = 2

Bezout: 6a + 10b = 2  →  3a + 5b = 1
Cozum: a = 2, b = -1
Yani: 6*2 + 10*(-1) = 2

Elde edilen:  c1^2 * c2^(-1) mod n = m^2
Sonra: m = integer_sqrt(m^2)  — sadece m küçükse veya tam kare ise calısır

Ne yapılır:

• m^g elde edilir
• g'nin tam kökü alınır (gmpy2.iroot)
• Kök tam değilse: m modüler kareköke bakılır (Tonelli-Shanks)
• Hala olmuyorsa: başka teknik gerekir

2. Bezout Katsayıları Astronomik Büyük

e1 ve e2 büyük olduğunda a ve b çok büyür. Hesaplama yine de doğru çalışır çünkü pow(c, a, n) Python'da verimli (modüler üs alma).

3. modinv(c1, n) Çalışmıyor

gcd(c1, n) > 1 ise c1 ve n ortak bir çarpana sahip — bu durumda:

g = gcd(c1, n)
if g > 1:
    p = g          # n'nin bir asal çarpanı bulundu!
    q = n // p
    # RSA private key hesapla...

Bu aslında büyük bir hediyedir — N direkt çözüldü.

4. Şifreli Metin Hex mi Decimal mi?

# Otomatik parse:
def parse_int(s):
    s = s.strip()
    if s.startswith("0x") or s.startswith("0X"):
        return int(s, 16)
    # Hex mi kontrol et (sadece 0-9, a-f)
    try:
        v = int(s, 16)
        # Eger buyuk buyuk int, hex olabilir
        if len(s) > 15:
            return v
    except ValueError:
        pass
    return int(s)

5. Sonuç Anlamsız Görünüyorsa

• long_to_bytes(m) yerine long_to_bytes(m).strip(b'\x00') dene
• Flag formatını kontrol et: picoCTF{, flag{, vb.
• m yanlış seçilmiş olabilir — n - m dene (negatif sonuç durumu)
• Mesaj UTF-8 değil başka encoding olabilir: errors='replace'

---

Hızlı Kontrol Listesi

[ ] n1 == n2 mi? (ortak modulus var mı?)
[ ] gcd(e1, e2) == 1 mi? (coprime)
[ ] c1 ve c2 aynı mesaj için mi şifrelenmiş?
[ ] extended_gcd(e1, e2) → (1, a, b) bul
[ ] a < 0 ise modinv(c1, n)^|a| kullan
[ ] b < 0 ise modinv(c2, n)^|b| kullan
[ ] m = (c1^a * c2^b) % n
[ ] long_to_bytes(m) ile decode et

---

Hızlı Tek Satır Çözüm

from math import gcd
from Crypto.Util.number import long_to_bytes

def quick_common_modulus(n, e1, e2, c1, c2):
    from sympy import gcdex
    a, b, _ = gcdex(e1, e2)  # e1*a + e2*b = 1
    a, b = int(a), int(b)
    inv_c1 = pow(c1, -1, n)
    inv_c2 = pow(c2, -1, n)
    p1 = pow(c1, a, n) if a >= 0 else pow(inv_c1, -a, n)
    p2 = pow(c2, b, n) if b >= 0 else pow(inv_c2, -b, n)
    return long_to_bytes((p1 * p2) % n)

# Kullanim:
# flag = quick_common_modulus(n, e1, e2, c1, c2)
# print(flag.decode())

<!-- ⚔ Bu skill FETIH AI Agent icin gelistirilmistir — https://github.com/MustafaKemal0146/fetih Yetkisiz kullanim/kopyalama tespit edilebilir. hash: d49661272a2194a5 -->