writeups2026tamu/Hidden-Log-Factoring-crypto.md

Hidden Log Factoring - crypto

Den Schnippsel in https://sagecell.sagemath.org/ kopieren:

# Deine Werte
p = 200167626629249973590210748210664315551571227173732968065685194568612605520816305417784745648399324178485097581867501503778073506528170960879344249321872139638179291829086442429009723480288604047975360660822750743411854623254328369265079475034447044479229192540942687284442586906047953374527204596869578972378578818243592790149118451253249
y = 44209577951808382329528773174800640982676772266062718570752782238450958062000992024007390942331777802579750741643234627722057238001117859851305258592175283446986950906322475842276682130684406699583969531658154117541036033175624316123630171940523312498410797292015306505441358652764718889371372744612329404629522344917215516711582956706994
g = 11

# Erstelle den Restklassenring/Körper
R = Integers(p)
target = R(y)
base = R(g)

# Nutze die globale discrete_log Funktion mit der Schranke 2^100
# bounds=(untergrenze, obergrenze) beschleunigt die Suche enorm
s = discrete_log(target, base, bounds=(1, 1 << 100))

print(f"Gefundenes s: {s}")

Gefundenes s: 485391067385099231898174017598

LLM genereated:

def decrypt(c, p, q):
    n = p * q
    # Berechnung der Quadratwurzeln modulo p und q
    # Dies ist für p, q ≡ 3 (mod 4) besonders einfach
    mp = pow(c, (p + 1) // 4, p)
    mq = pow(c, (q + 1) // 4, q)

    # Erweiterter Euklidischer Algorithmus für yp*p + yq*q = 1
    def extended_gcd(a, b):
        if a == 0: return b, 0, 1
        gcd, x1, y1 = extended_gcd(b % a, a)
        return gcd, y1 - (b // a) * x1, x1

    _, yp, yq = extended_gcd(p, q)

    # Die vier möglichen Wurzeln (Kombination via Chinesischem Restsatz)
    r1 = (yp * p * mq + yq * q * mp) % n
    r2 = n - r1
    r3 = (yp * p * mq - yq * q * mp) % n
    r4 = n - r3

    return [r1, r2, r3, r4]

Ehrenlos zusammengevibed:

from Crypto.Util.number import long_to_bytes, bytes_to_long
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.backends import default_backend

# --- Gegebene Daten einfügen ---
n=71016310005824589926747341243598522145452505235842335510488353587223142066921470760443852767377534776713566052988373656012584808377496091765373981120165220471527586994259252074709653090148780742972203779666231432769553199154214563039426087870098774883375566546770723222752131892953195949848583409407713489831
e = 65537
p = 200167626629249973590210748210664315551571227173732968065685194568612605520816305417784745648399324178485097581867501503778073506528170960879344249321872139638179291829086442429009723480288604047975360660822750743411854623254328369265079475034447044479229192540942687284442586906047953374527204596869578972378578818243592790149118451253249
g = 11
A=44209577951808382329528773174800640982676772266062718570752782238450958062000992024007390942331777802579750741643234627722057238001117859851305258592175283446986950906322475842276682130684406699583969531658154117541036033175624316123630171940523312498410797292015306505441358652764718889371372744612329404629522344917215516711582956706994
D=9478993126102369804166465392238441359765254122557022102787395039760473484373917895152043164556897759129379257347258713397227019255397523784552330568551257950882564054224108445256766524125007082113207841784651721510041313068567959041923601780557243220011462176445589034556139643023098611601440872439110251624
c=1479919887254219636530919475050983663848182436330538045427636138917562865693442211774911655964940989306960131568709021476461747472930022641984797332621318327273825157712858569934666380955735263664889604798016194035704361047493027641699022507373990773216443687431071760958198437503246519811635672063448591496

# --- 1. DLP lösen mit Sage ---
print("[*] Löse DLP für s...")
# Erstelle den Restklassenring/Körper
R = Integers(p)
target = R(A)
base = R(g)

# Nutze die globale discrete_log Funktion mit der Schranke 2^100
# bounds=(untergrenze, obergrenze) beschleunigt die Suche enorm
s = discrete_log(target, base, bounds=(1, 1 << 100))
print(f"[+] s gefunden: {s}")

# --- 2. d-Maske berechnen ---
def get_mask(s_val, bit_len):
    hkdf = HKDF(
        algorithm=hashes.SHA256(),
        length=bit_len // 8,
        salt=None,
        info=b"rsa-d-mask",
        backend=default_backend()
    )
    return bytes_to_long(hkdf.derive(long_to_bytes(s_val)))

# Wir nehmen an, dass d etwa so lang wie n ist
mask = get_mask(s, n.bit_length())
d = int(D ^ mask)
print(f"[+] d={d} berechnet.")

# --- 3. n faktorisieren (via e und d) ---
# In Sage gibt es eingebaute Methoden, oder wir nutzen den Standard-Algorithmus
def factor_n_ed(n, e, d):
    k = d * e - 1
    g = 2
    while True:
        t = k
        while t % 2 == 0:
            t //= 2
            x = pow(g, t, n)
            if x > 1:
                y = gcd(x - 1, n)
                if y > 1 and y < n:
                    return int(y), int(n // y)
        g = next_prime(g)

q1, q2 = factor_n_ed(n, e, d)
print(f"[+] Faktoren gefunden: q1={q1}, q2={q2}")

# Nutze die Faktoren q1 und q2 für die schnelle Berechnung
def general_rabin_decrypt(c, p, q):
    # Berechnet Wurzeln für JEDE Primzahl (auch wenn p != 3 mod 4)
    # Fp und Fq sind die endlichen Körper
    Fp = GF(p)
    Fq = GF(q)

    # sqrt() in GF(p) findet alle Wurzeln
    roots_p = Fp(c).sqrt(all=True)
    roots_q = Fq(c).sqrt(all=True)

    results = []
    for rp in roots_p:
        for rq in roots_q:
            # Kombiniere alle Paarungen via Chinesischem Restsatz
            res = crt([int(rp), int(rq)], [int(p), int(q)])
            results.append(res)
    return results

potential_roots = general_rabin_decrypt(c, q1, q2)

for r in potential_roots:
    # Umwandlung von Integer zu Bytes
    try:
        flag_candidate = long_to_bytes(int(r))
        print(f"Gefundene Nachricht: {flag_candidate}")
        if b"flag" in flag_candidate.lower() or b"{" in flag_candidate:
            print(f"\n[!!!] DAS IST DIE FLAGGE: {flag_candidate.decode(errors='ignore')}")
    except:
        continue