This challenge requires solving 100 RSA problems consecutively with maximum 1s for each problem.
There are 6 different types of problems:- Finding n given p and q- Finding q given n and p- Finding d given p, q and e- Finding phi given p and q- Finding pt given p, q (or phi), e and ct- Finding ct given p, q (or phi), e and pt
This is boresome and I only tried at the last minutes. Thereforce I didn't manage to solve it on time.
Anyway, here's the code:
```import socket
# Extended Euclidean Algorithmdef egcd(a, b):    if a == 0:        return (b, 0, 1)    g, y, x = egcd(b % a, a)    return (g, x - (b // a) * y, y)
# application of Extended Euclidean Algorithm to find a modular inversedef modinv(a, m):    g, x, y = egcd(a, m)    if g != 1:        raise Exception('modular inverse does not exist')    return x % m
def find_pt(p, q, e, ct):    n = p * q    phi = (p - 1) * (q - 1)    d = modinv(e, phi)    pt = pow(ct, d, n)    return pt
def find_ct(p, q, e, pt):    n = p * q    phi = (p - 1) * (q - 1)    ct = pow(pt, e, n)    return ct
def find_d(p, q, e):    n = p * q    phi = (p - 1) * (q - 1)    d = modinv(e, phi)    return d
IP = '88.198.219.20'PORT = 23125
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)s.connect((IP, PORT))s.setblocking(0)
buffer = b''
while True:    # Read until a prompt or line break    try:        chunk = s.recv(4096)        buffer += chunk        print(chunk.decode(), end='')    except BlockingIOError:        pass
    if b'\n' not in buffer and not buffer.endswith(b': '):        continue
    # Grab the oldest line    buffer = buffer.split(b'\n', 1)    if len(buffer) == 1:        line, buffer = buffer[0], b''    else:        line, buffer = buffer
    # Llines start with []    if line[:1] != b'[':        continue
    # Use slicing not indexing because indexing bytes returns ints    mode = line[1:2]    vari = line[4:7]    #print(vari)    if mode == b'*':        print('*')    elif mode == b'c':        p,q,e,n,pt,ct,phi = 0,0,0,0,0,0,0        print('c')    elif mode == b':':        if vari == b'p: ':            p = int(line[7:].decode())            #print(p)        elif vari == b'q: ':            q = int(line[7:].decode())            #print('q: ' + str(q))        elif vari == b'e: ':            e = int(line[7:].decode())            #print(e)        elif vari == b'n: ':            n = int(line[7:].decode())            #print(n)        elif vari == b'phi':            phi = int(line[9:].decode())            #print(phi)        elif vari == b'pt:':            pt = int(line[8:].decode())            #print(pt)        elif vari == b'ct:':            ct = int(line[8:].decode())            #print(ct)    elif mode == b'!':        #print('!')        if line == b'[!] A good cryptologist should be faster than that!':            break;        elif line == b'[!] INCORRECT ANSWER!':            break;    elif mode == b'?':        #print('?')        if vari == b'n: ':            n = p * q            #print(n)            s.sendall((str(n) + '\n').encode())        elif vari == b'q: ':            q = n // p            #print(q)            s.sendall((str(q) + '\n').encode())        elif vari == b'd: ':            d = find_d(p, q, e)            #print(d)            s.sendall((str(d) + '\n').encode())        elif vari == b'phi':            phi = (p - 1) * (q - 1)            #print(phi)            s.sendall((str(phi) + '\n').encode())        elif vari == b'pt:':            if q == 0:                q = (phi // (p - 1)) + 1            #print('q: ' + str(q))            pt = find_pt(p, q, e, ct)            #print(pt)            s.sendall((str(pt) + '\n').encode())        elif vari == b'ct:':            if q == 0:                q = (phi // (p - 1)) + 1            #print('q: ' + str(q))            ct = find_ct(p, q, e, pt)            #print(ct)            s.sendall((str(ct) + '\n').encode())    else:        print(line)```
Result:
```[c] Challenge 100:[:] p: 6892503881845816135437970025250733877066829303171701023363747158858557273648035991068180509649935204522542306573221659692941997106933628410204032749970179[:] q: 6892503881845816135437970025250733877066829303171701023363747158858557273648035991068180509649935204522542306573221659692941997106933628410204032749970179[:] e: 65537[?] d: c[!] Correct answer
[F] FLAG: ractf{F45t35tCryp70gr4ph3rAr0und}```