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.

ncat --ssl groups.chal.uiuc.tf 1337

challenge.py

Here’s the Python source:

1
from random import randint
2
from math import gcd, log
3
import time
4
from Crypto.Util.number import *
5

6

7
def check(n, iterations=50):
8
    if isPrime(n):
9
        return False
10

11
    i = 0
12
    while i < iterations:
13
        a = randint(2, n - 1)
14
        if gcd(a, n) == 1:
15
            i += 1
16
            if pow(a, n - 1, n) != 1:
17
                return False
18
    return True
19

20

21
def generate_challenge(c):
22
    a = randint(2, c - 1)
23
    while gcd(a, c) != 1:
24
        a = randint(2, c - 1)
25
    k = randint(2, c - 1)
26
    return (a, pow(a, k, c))
27

28

29
def get_flag():
30
    with open('flag.txt', 'r') as f:
31
        return f.read()
32

33
if __name__ == '__main__':
34
    c = int(input('c = '))
35

36
    if log(c, 2) < 512:
37
        print(f'c must be least 512 bits large.')
38
    elif not check(c):
39
        print(f'No cheating!')
40
    else:
41
        a, b = generate_challenge(c)
42
        print(f'a = {a}')
43
        print(f'a^k = {b} (mod c)')
44

45
        k = int(input('k = '))
46

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

In short, this is simply solving the discrete log problem with the modulus is a Carmichael number. Essentially, Carmichael numbers are composite numbers that have the same property of the primes of Fermat’s Little Theorem, which states that $a^{p-1}=1\;(mod \;p)$ for any prime p, such that a and p are coprime. Essentially, $a^{n-1}=1\;(mod\;n)$, such that a and n are coprime.

Through a bit of research, I found out how to calculate large Carmichael numbers in this post. Basically, you take an integer k, and check if $6k+1$, $12k+1$, and $18k+1$ are all prime. If they are, then $(6k+1)(12k+1)(18k+1)$ is a Carmichael number.

With this, we can write a pretty quick generation script for a Carmichael number:

1
from Crypto.Util.number import isPrime
2
from tqdm import trange
3

4
for k in trange(2**171, 2**171 + 2**20):
5
    if isPrime(6*k+1) and isPrime(12*k+1) and isPrime(18*k+1):
6
        n = (6*k+1)*(12*k+1)*(18*k+1)
7
        print(n)
8
        break

Now, how do we solve the discrete log problem? Well, since our Carmichael number is actually the product of 3 primes that are each ~171 bits, this problem now becomes much easier to do, since our discrete log using a modulus of 512 bits now becomes equivalent to just doing 3 discrete logs using 3 different moduli of 171 bits. I actually kinda failed implementing it by hand, so I just Alperton to just solve the discrete log problem. Plug it in to get k, then send it back to the server to get the flag!

1
uiuctf{c4rm1ch43l_7adb8e2f019bb4e0e8cd54e92bb6e3893}