TUM CTF 2016 – Tacos (Crypto 400)

def is_prime(n):
    for _ in range(42):
        if pow(random.randrange(1, n), n - 1, n) != 1:
            return False
    return True
 
q, p = int(input(), 0), int(input(), 0)
 
assert 2 ** 1024 < p < q < 2 ** 4096
assert is_prime(q)
assert not (q - 1) % p
assert is_prime(p)
 
g = random.randrange(1, q)
y = pow(g, random.randrange(q - 1), q)
print(hex(g), hex(y))
signal.alarm(60)
 
# good luck!
if pow(g, int(input(), 0), q) == y:
    print(open('flag.txt').read().strip())

from sage.all import *
import operator
 
first_primes = list(primes(10**7))
 
# it is important to find good lambda
# the algorithm highly depends on it
# this one is from some paper
factors = [2**5, 3**2, 5, 7, 11, 13, 17]
lam = reduce(operator.mul, factors)
# lam = /\ = 24504480
 
P = []
for p in primes(min(10000000, lam)):
    # do not include large primes so that Fermat test
    # has higher probability to pass
    if p < 400:
        continue
    if lam % p and lam % (p - 1) == 0:
        P.append(p)
 
print "P size", len(P)
 
prodlam = reduce(lambda a, b: a * b % lam, P)
prod = reduce(lambda a, b: a * b, P)
 
# faster prime checks
proof.arithmetic(False)
 
while 1:
    numlam = 1
    num = 1
    # we are building random subset {p1,...,p20}
    # and checking the subset at each step
    for i in xrange(20):
        p = choice(P)
        numlam = numlam * p % lam
        num = num * p
        if numlam != prodlam or prod % num != 0:
            continue
        q = prod // num
        print "candidate", q
        print factor(q)
        print
        ps = [p for p, e in factor(q)]
        is_carm = ( (q - 1) % lcm([p-1 for p in ps]) == 0 )
        if not is_carm:
            continue
 
        # now check if q - 1 = small primes * large prime p
        # since we need to know such p
        # should happen by chance quite often
        t = q - 1
        for p in first_primes:
            while t % p == 0:
                t //= p
        if is_prime(t):
            print "Good!"
            print "q =", q, "#", len(q.bits()), "bits"
            print "p =", p, "#", len(p.bits()), "bits"
            print
            open("candidates", "a").write("q = %d\n" % q)
            open("candidates", "a").write("p = %d\n\n" % p)
 
# solution:
q = 59857999685097510058704903303340275550835640940514904342609260821117098340506319476802302889863926430165796687108736694628663794024203081690831548926936527743286188479060985861546093711311571900661759884274719541236402441770905441176260283697893506556009435089259190308034118717196693029323272007089714272903225216389846915864612112381878100108428287917605430965442572234711074146363466926780699151173555904751392997928289187479977403795442182731620805949932616667193358004913424246140299423521
p = 62524500763431441748481642690708441489776386892126187254070724779722504054292898512943722029745633023670685560530873804922086432332770562190282869379418979194485569141426416326281184435782910942683630763055432514713734358605440032411156894024431274583468338817956399407807741136790938228633811230955007519469063632837378284757301519562677312080310137628454021752642170957113443979650111115572728879157653822412120689975685302219422272533094042684647476957834486986793341

from sage.all import *
from sock import *
 
q = 59857999685097510058704903303340275550835640940514904342609260821117098340506319476802302889863926430165796687108736694628663794024203081690831548926936527743286188479060985861546093711311571900661759884274719541236402441770905441176260283697893506556009435089259190308034118717196693029323272007089714272903225216389846915864612112381878100108428287917605430965442572234711074146363466926780699151173555904751392997928289187479977403795442182731620805949932616667193358004913424246140299423521
p = 62524500763431441748481642690708441489776386892126187254070724779722504054292898512943722029745633023670685560530873804922086432332770562190282869379418979194485569141426416326281184435782910942683630763055432514713734358605440032411156894024431274583468338817956399407807741136790938228633811230955007519469063632837378284757301519562677312080310137628454021752642170957113443979650111115572728879157653822412120689975685302219422272533094042684647476957834486986793341
 
itr = 0
while 1:
    itr += 1
    print "Try #%d" % itr
    f = Sock("104.198.63.175 1729")
    f.send_line(str(q))
    f.send_line(str(p))
    ans = f.read_line()
    print `ans`
    if "Traceback" in ans:
        print ans
        print f.read_all()
        continue
 
    print "Primes are accepted! Getting discrete log"
    g, y = [int(ss[2:], 16) for ss in ans.split()]
    R = IntegerModRing(q)
    x = discrete_log(R(y), R(g))
    print "x", x
    print "y", y
    print "correct ?", pow(g, x, q) == y
    f.send_line(str(x))
 
    print f.read_all()
    break