CUSTOMMediumCrypto

Hidden Log Factoring

XESXOR9/2/20266 min read

#crypto#custom#medium#baby_step_giant_step#crt_square_root#factoring_from_d#pohlig_hellman_dlp#tonelli_shanks

Hidden Log Factoring

Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: N/A | **Author: XESXOR Techniques: baby_step_giant_step, crt_square_root, factoring_from_d, pohlig_hellman_dlp, tonelli_shanks

Summary

Walkthrough of the CUSTOM Crypto Hidden Log Factoring. Task: Combined RSA + DLP scheme with masked private key and Rabin encryption. Solution: Pohlig-Hellman for 100-bit DLP, recover d via HKDF, factor n from d, Tonelli-Shanks for modular square root.

Description

Where are the logs? I got the raw data in data.txt but can't find the logs.

English summary: A combined RSA + DLP cryptosystem. The RSA private key d is XORed with an HKDF-derived mask from a DLP secret s. The ciphertext is c = flag^2 mod n (Rabin-style encryption). The DLP secret s is only 100 bits, and the DLP prime p has a smooth p-1, making Pohlig-Hellman attack feasible.

Analysis

The challenge combines three cryptographic primitives: ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Discrete Logarithm Problem (DLP): A = g^s mod p where s is only 100 bits
RSA key masking: D = d XOR HKDF(s) - the private key is hidden using HKDF-derived mask
Rabin encryption: c = flag^2 mod n - NOT standard RSA with exponent e!

Key observations:

The DLP prime p is specially chosen so that p-1 has many small factors (smooth)
p-1 = 2^101 * 3 * 29 * 317 * 593 * 480661 * (large prime)
The product of small factors exceeds 2^100, allowing full recovery of the 100-bit secret s
The title "Hidden Log Factoring" hints at DLP + RSA factoring ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Solution

Step 1: Solve DLP using Pohlig-Hellman

Factor p-1 and use Pohlig-Hellman algorithm with Baby-Step Giant-Step (BSGS) for each subgroup:

 python read-only • copy allowed
def pohlig_hellman(g, h, p, factors, target_bits=100):
    """Solve g^x = h mod p using factorization of p-1"""
    remainders = []
    moduli = []
    order = p - 1
    
    for prime, exp in factors:
        pe = prime**exp
        cofactor = order // pe
        gi = pow(g, cofactor, p)
        hi = pow(h, cofactor, p)
        
        # Solve DLP in subgroup using BSGS
        xi = solve_subgroup_dlp(gi, hi, p, prime, exp)
        remainders.append(xi)
        moduli.append(pe)
    
    # Combine using CRT
    return crt(remainders, moduli)

‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Found: s = 485391067385099231898174017598 (99 bits)

Step 2: Recover RSA private key d

With s known, compute the HKDF mask and XOR to recover d:

 python read-only • copy allowed
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes

def hkdf_mask(secret: bytes, length: int) -> bytes:
    hkdf = HKDF(
        algorithm=hashes.SHA256(),
        length=length,
        salt=None,
        info=b"rsa-d-mask",
    )
    return hkdf.derive(secret)

mask_len = 127  # d has ~1020 bits
mask = hkdf_mask(long_to_bytes(s), mask_len)
d = D ^ bytes_to_long(mask)

‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Step 3: Factor n using d

Use the standard algorithm that factors n from knowledge of (e, d, n):

 python read-only • copy allowed
def factor_from_d(n, e, d):
    """Factor n given (e, d) where e*d = 1 (mod phi(n))"""
    k = e * d - 1
    # k = 2^t * r where r is odd
    t, r = 0, k
    while r % 2 == 0:
        t += 1
        r //= 2
    
    # Try random bases
    for _ in range(5000):
        g = random.randint(2, n - 2)
        x = pow(g, r, n)
        for j in range(t):
            y = pow(x, 2, n)
            if y == 1:
                p = gcd(x - 1, n)
                if 1 < p < n:
                    return p, n // p
            x = y
    return None, None

‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Step 4: Compute modular square root (Rabin decryption)

Since c = flag^2 mod n, use Tonelli-Shanks for each prime factor and combine with CRT:

 python read-only • copy allowed
def sqrt_mod_n(c, p, q):
    """Compute all 4 square roots of c mod n = p*q"""
    rp = tonelli_shanks(c % p, p)
    rq = tonelli_shanks(c % q, q)
    
    roots = []
    for sp in [rp, p - rp]:
        for sq in [rq, q - rq]:
            x = crt([sp, sq], [p, q])
            roots.append(x)
    return roots

roots = sqrt_mod_n(c, q1, q2)
for root in roots:
    plaintext = long_to_bytes(root)
    if b"gigem{" in plaintext:
        print(plaintext.decode())

‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Full Solution Script

 python read-only • copy allowed
#!/usr/bin/env python3
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.backends import default_backend
from Crypto.Util.number import long_to_bytes, bytes_to_long
from math import gcd, isqrt
import random

# Given data
n = 71016310005824589926747341243598522145452505235842335510488353587223142066921470760443852767377534776713566052988373656012584808377496091765373981120165220471527586994259252074709653090148780742972203779666231432769553199154214563039426087870098774883375566546770723222752131892953195949848583409407713489831
e = 65537
p = 200167626629249973590210748210664315551571227173732968065685194568612605520816305417784745648399324178485097581867501503778073506528170960879344249321872139638179291829086442429009723480288604047975360660822750743411854623254328369265079475034447044479229192540942687284442586906047953374527204596869578972378578818243592790149118451253249
g = 11
A = 44209577951808382329528773174800640982676772266062718570752782238450958062000992024007390942331777802579750741643234627722057238001117859851305258592175283446986950906322475842276682130684406699583969531658154117541036033175624316123630171940523312498410797292015306505441358652764718889371372744612329404629522344917215516711582956706994
D = 9478993126102369804166465392238441359765254122557022102787395039760473484373917895152043164556897759129379257347258713397227019255397523784552330568551257950882564054224108445256766524125007082113207841784651721510041313068567959041923601780557243220011462176445589034556139643023098611601440872439110251624
c = 1479919887254219636530919475050983663848182436330538045427636138917562865693442211774911655964940989306960131568709021476461747472930022641984797332621318327273825157712858569934666380955735263664889604798016194035704361047493027641699022507373990773216443687431071760958198437503246519811635672063448591496
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

def hkdf_mask(secret: bytes, length: int) -> bytes:
    hkdf = HKDF(algorithm=hashes.SHA256(), length=length, salt=None,
                info=b"rsa-d-mask", backend=default_backend())
    return hkdf.derive(secret)

def bsgs(g, h, p, n):
    """Baby-step Giant-step for DLP"""
    m = isqrt(n) + 1
    table = {}
    val = 1
    for j in range(m):
        table[val] = j
        val = (val * g) % p
    factor = pow(g, -m, p)
    gamma = h
    for i in range(m):
        if gamma in table:
            return i * m + table[gamma]
        gamma = (gamma * factor) % p
    return None
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

def pohlig_hellman(g, h, p, factors):
    """Pohlig-Hellman algorithm for DLP"""
    remainders, moduli = [], []
    order = p - 1
    for prime, exp in factors:
        pe = prime**exp
        if prime > 2**25:
            continue
        cofactor = order // pe
        gi, hi = pow(g, cofactor, p), pow(h, cofactor, p)
        if gi == 1:
            continue
        xi = 0
        gamma = hi
        base_g = pow(gi, pe // prime, p)
        for k in range(exp):
            hk = pow(gamma, pe // (prime ** (k + 1)), p)
            dk = bsgs(base_g, hk, p, prime)
            xi += dk * (prime**k)
            gamma = (gamma * pow(gi, -dk * (prime**k), p)) % p
        remainders.append(xi)
        moduli.append(pe)
    return crt(remainders, moduli)
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

def crt(remainders, moduli):
    from functools import reduce
    M = reduce(lambda x, y: x * y, moduli)
    result = sum(ri * (M // mi) * pow(M // mi, -1, mi) 
                 for ri, mi in zip(remainders, moduli))
    return result % M

def factor_from_d(n, e, d):
    k = e * d - 1
    t, r = 0, k
    while r % 2 == 0:
        t += 1
        r //= 2
    for _ in range(5000):
        g = random.randint(2, n - 2)
        x = pow(g, r, n)
        for j in range(t):
            y = pow(x, 2, n)
            if y == 1:
                p = gcd(x - 1, n)
                if 1 < p < n:
                    return p, n // p
            x = y
    return None, None
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

def tonelli_shanks(n, p):
    if pow(n, (p - 1) // 2, p) != 1:
        return None
    q, s = p - 1, 0
    while q % 2 == 0:
        q //= 2
        s += 1
    z = 2
    while pow(z, (p - 1) // 2, p) != p - 1:
        z += 1
    m, c, t, r = s, pow(z, q, p), pow(n, q, p), pow(n, (q + 1) // 2, p)
    while t != 1:
        i, temp = 1, (t * t) % p
        while temp != 1:
            temp = (temp * temp) % p
            i += 1
        b = pow(c, 1 << (m - i - 1), p)
        m, c, t, r = i, (b * b) % p, (t * b * b) % p, (r * b) % p
    return r
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

# Main solve
factors = [(2, 101), (3, 1), (29, 1), (317, 1), (593, 1), (480661, 1)]
s = pohlig_hellman(g, A, p, factors)
mask = hkdf_mask(long_to_bytes(s), 127)
d = D ^ bytes_to_long(mask)
q1, q2 = factor_from_d(n, e, d)

rp, rq = tonelli_shanks(c % q1, q1), tonelli_shanks(c % q2, q2)
for sp in [rp, q1 - rp]:
    for sq in [rq, q2 - rq]:
        x = crt([sp, sq], [q1, q2])
        try:
            pt = long_to_bytes(x)
            if b"gigem{" in pt:
                print(pt.decode())
        except:
            pass

‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Key Takeaways / Lessons

Mastering baby_step_giant_step, crt_square_root, factoring_from_d, pohlig_hellman_dlp, tonelli_shanks was key to this challenge.
Always check for common misconfigurations and verify assumptions.

Crafted by XESXOR Research • 2026-03-21 • CUSTOM • Hidden Log Factoring • Difficulty: Medium