Crypto-Groups

My friend told me that cryptography is unbreakable if moduli are Carmichael numbers instead of primes. I decided to use this CTF to test out this theory. - Nikhil

Full Implementation

Challenge

def check(n, iterations=50):
    if isPrime(n):
        return False

    i = 0
    while i < iterations:
        a = randint(2, n - 1)
        if gcd(a, n) == 1:
            i += 1
            if pow(a, n - 1, n) != 1:
                return False
    return True

def generate_challenge(c):
    a = randint(2, c - 1)
    while gcd(a, c) != 1:
        a = randint(2, c - 1)
    k = randint(2, c - 1)
    return (a, pow(a, k, c))
    
if __name__ == '__main__':
    c = int(input('c = '))

    if log(c, 2) < 512:
        print(f'c must be least 512 bits large.')
    elif not check(c):
        print(f'No cheating!')
    else:
        a, b = generate_challenge(c)
        print(f'a = {a}')
        print(f'a^k = {b} (mod c)')
        
        k = int(input('k = '))

        if pow(a, k, c) == b:
            print(get_flag())
        else:
            print('Wrong k')

The server first checks if the number we give is a Carmichael number having a bit length greater than 512. Then it asks us to compute the discrete log of a random number modulo the number we provide.

After extensive searching, I found this excellent repo which has a large collection of Carmichael numbers along with their prime factors.

We choose a number which is atleast 512 bits long and has many small prime factors, which allows sage to directly calculate the discrete log.

from pwn import *
from math import prod
s =[17, 23, 29, 31, 43, 53, 61, 67, 71, 79, 89, 97, 113, 211, 241, 313,331, 337, 353, 421, 463, 521, 547, 617, 661, 673, 859, 881, 911, 1093,1249, 1321, 2003, 2081, 2311, 2731, 2861, 3121, 3361, 3433, 3697, 4621,5281, 6007, 7393, 8737, 9241, 13729, 14561, 18481, 21841, 48049, 96097,120121]
t1= prod(s)
cmd = "ncat --ssl groups.chal.uiuc.tf 1337"
r = process(cmd,shell=True,stdin=PTY)
r.recv()
r.sendline(str(t1))
l1=int(r.recvuntil("a^k").decode()[3:-4])
l2= int(r.recvuntil("(mod c)").decode()[2:-7])
R= Zmod(t1)
g = R(l1)
h = R(l2)
ans=discrete_log(h,g)
r.recv()
r.sendline(str(ans))
print(r.recv())
b'uiuctf{c4rm1ch43l_7adb8e2f019bb4e0e8cd54e92bb6e3893}'