Chunk Norris (easy)

Code given

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#!/usr/bin/python3 -u

import random
from Crypto.Util.number import *
import gmpy2

a = 0xe64a5f84e2762be5
chunk_size = 64

def gen_prime(bits):
  s = random.getrandbits(chunk_size)

  while True:
    s |= 0xc000000000000001
    p = 0
    for _ in range(bits // chunk_size):
      p = (p << chunk_size) + s
      s = a * s % 2**chunk_size
    if gmpy2.is_prime(p):
      return p

n = gen_prime(1024) * gen_prime(1024)
e = 65537
flag = open("flag.txt", "rb").read()
print('n =', hex(n))
print('e =', hex(e))
print('c =', hex(pow(bytes_to_long(flag), e, n)))

n = 0xab802dca026b18251449baece42ba2162bf1f8f5dda60da5f8baef3e5dd49d155c1701a21c2bd5dfee142fd3a240f429878c8d4402f5c4c7f4bc630c74a4d263db3674669a18c9a7f5018c2f32cb4732acf448c95de86fcd6f312287cebff378125f12458932722ca2f1a891f319ec672da65ea03d0e74e7b601a04435598e2994423362ec605ef5968456970cb367f6b6e55f9d713d82f89aca0b633e7643ddb0ec263dc29f0946cfc28ccbf8e65c2da1b67b18a3fbc8cee3305a25841dfa31990f9aab219c85a2149e51dff2ab7e0989a50d988ca9ccdce34892eb27686fa985f96061620e6902e42bdd00d2768b14a9eb39b3feee51e80273d3d4255f6b19
e = 0x10001
c = 0x6a12d56e26e460f456102c83c68b5cf355b2e57d5b176b32658d07619ce8e542d927bbea12fb8f90d7a1922fe68077af0f3794bfd26e7d560031c7c9238198685ad9ef1ac1966da39936b33c7bb00bdb13bec27b23f87028e99fdea0fbee4df721fd487d491e9d3087e986a79106f9d6f5431522270200c5d545d19df446dee6baa3051be6332ad7e4e6f44260b1594ec8a588c0450bcc8f23abb0121bcabf7551fd0ec11cd61c55ea89ae5d9bcc91f46b39d84f808562a42bb87a8854373b234e71fe6688021672c271c22aad0887304f7dd2b5f77136271a571591c48f438e6f1c08ed65d0088da562e0d8ae2dadd1234e72a40141429f5746d2d41452d916

RSA algorithm (reminder)

where:

• p and q are large prime numbers
• e is the public key
• m is the message
• c is the cipher text

The RSA algorithm is based around the idea of asymeytric keys or in this case, the fact that for large primes, it is hard to computer a number d such that:

Large Prime number generation

1
2
3
4
5
6
7
8
9
10
11
12
13
14

a = 0xe64a5f84e2762be5
chunk_size = 64

def gen_prime(bits):
  s = random.getrandbits(chunk_size)

  while True:
    s |= 0xc000000000000001
    p = 0
    for _ in range(bits // chunk_size):
      p = (p << chunk_size) + s
      s = a * s % 2**chunk_size
    if gmpy2.is_prime(p):
      return p

When we look at the above function, we can see the way the challenge generates primes. It can be resumed by the following equation:

where s is the random number that was used to generate the prime.

NB: as we can see in the function, the number s might be different than the one picked by the system originaly. For our purposes, this has no incidence as we only care about the number that generated the prime and we can consider it to be random.

Reversing the primes

Now we know that n=pq thus we have:

where $s_i$ and $s’_i$ are the two random numbers that generate the primes

Now the trick to this challenge was to not try and factor n directly but rather factor the random numbers. Here let’s first try and find their product

Getting the product of random numbers

We know:

Howver $a = 16 594 180 801 339 730 917$ and is an odd number thus it has an inverse $mod\ 2^{64}$

Thus we have:

Now we can simplify $n$:

Since $(2^{65}*a^{-1}+1)$ is an odd number it must have an inverse $mod\ 2^{128}$. Thus we get:

Now once we calculate and factor this we get the following factors:

13, 167541865434116759, 11, 109, 223, 1290533, 4608287

Now we just need to find two numbers out of this set that have more or less the same length bit wise which are

s1 = 13 * 167541865434116759
t1 = 11 * 109 * 223 * 1290533 * 4608287

Back to decrypting RSA

Now that we have the two random numbers we can get to getting the d value that we need to decrypt:

1
2
3
4
5
6
7
8

b = inverse(a, pow(2, 64))

def remverse_primes(s):
    p = s
    for i in range(1,16):
        s = b * s % 2^64
        p += s * 2^(64*i)
    return p

Now with both prime we calculate the inverse of e modulo phi of n which is equal to $\phi = (p-1)(q-1)$. Once we have d we just need to raise the cipher text to that power and we have the clear flag

FULL CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

from Crypto.Util.number import long_to_bytes
from euclid import inverse # custom inverse fucntion nothing fancy

a = 0xe64a5f84e2762be5

n = 0xab802dca026b18251449baece42ba2162bf1f8f5dda60da5f8baef3e5dd49d155c1701a21c2bd5dfee142fd3a240f429878c8d4402f5c4c7f4bc630c74a4d263db3674669a18c9a7f5018c2f32cb4732acf448c95de86fcd6f312287cebff378125f12458932722ca2f1a891f319ec672da65ea03d0e74e7b601a04435598e2994423362ec605ef5968456970cb367f6b6e55f9d713d82f89aca0b633e7643ddb0ec263dc29f0946cfc28ccbf8e65c2da1b67b18a3fbc8cee3305a25841dfa31990f9aab219c85a2149e51dff2ab7e0989a50d988ca9ccdce34892eb27686fa985f96061620e6902e42bdd00d2768b14a9eb39b3feee51e80273d3d4255f6b19
e = 0x10001
c = 0x6a12d56e26e460f456102c83c68b5cf355b2e57d5b176b32658d07619ce8e542d927bbea12fb8f90d7a1922fe68077af0f3794bfd26e7d560031c7c9238198685ad9ef1ac1966da39936b33c7bb00bdb13bec27b23f87028e99fdea0fbee4df721fd487d491e9d3087e986a79106f9d6f5431522270200c5d545d19df446dee6baa3051be6332ad7e4e6f44260b1594ec8a588c0450bcc8f23abb0121bcabf7551fd0ec11cd61c55ea89ae5d9bcc91f46b39d84f808562a42bb87a8854373b234e71fe6688021672c271c22aad0887304f7dd2b5f77136271a571591c48f438e6f1c08ed65d0088da562e0d8ae2dadd1234e72a40141429f5746d2d41452d916

ss = n * inverse(pow(2,65) * inverse(a, pow(2,64)) + 1, pow(2,128)) % pow(2,128)
print(ss)

#Use factordb or anything to get the factors of the product
s1 = 13 * 167541865434116759
s2 = 11 * 109 * 223 * 1290533 * 4608287

b = inverse(a, pow(2,64))

def reverse_prime(s):
    p = s
    for i in range(1,16):
        s = b * s % pow(2,64)
        p += s * 2^(64*i)
    return p

p = reverse_prime(s1)
q = reverse_prime(s2)
phi = (p-1)*(q-1)
d = inverse(e, phi)
print(long_to_bytes(pow(c,d,n)).decode())

FLAG

CTF{donald_knuths_lcg_would_be_better_well_i_dont_think_s0}