Random ramblings on hacking, coding, fighting with infrastructure and general tech
Internetwache CTF 2016 – Prime Time – Coding – 60 Points
Posted: 21 Feb 2016 at 23:02 by Codehead

### Challenge:

It’s Prime Time! (code60)

Description: We all know that prime numbers are quite important in cryptography. Can you help me to find some?

Service: 188.166.133.53:11059

## Solution:

Running netcat against the address gave the following output:

```> nc 188.166.133.53 11059
Hi, you know that prime numbers are important, don't you?
Help me calculating the next prime!
Level 1.: Find the next prime number after 5:
```

I know the answer to that!, Lets see how far we get doing this manually:

```> nc 188.166.133.53 11059
Hi, you know that prime numbers are important, don't you?
Help me calculating the next prime!
Level 1.: Find the next prime number after 5:
7
Yay, that's right!
Level 2.: Find the next prime number after 15:
17
Yay, that's right!
Level 3.: Find the next prime number after 19:
23
Yay, that's right!
Level 4.: Find the next prime number after 37:
39
Nope, that's just wrong. Try again later!
```

OK, this is going to need automation. I’ve seen this type of challenge before. Calculating the primes can get quite slow for large numbers, so let’s use a lookup table of pre-calculated primes.

Google quickly provided a text file of the first 10,000 primes.

This needed a quick bit of bash-fu to transform it into a one entry per line list:

`cat 10000.txt | tr  [:blank:] '\n' | grep -v "^[[:space:]]*\$" > primelist.txt`

Next, a bit of python to talk to the server and pull primes from the list:

``````import sys
from telnetlib import Telnet

def main():

tn = Telnet('188.166.133.53', 11059)

for i in range(0,200):
sys.stdout.write(tn.read_until("the next prime number after ",0.2))
sys.stdout.write(numstr)

numval = numstr.split(':')
nxtpr = nextPrime(int(numval))
sys.stdout.write(nxtpr)
tn.write(nxtpr)

tn.close()

def nextPrime(tp):

with open('primelist.txt') as f:
if (int(ln) > tp):
return ln;

if __name__ == "__main__":
main()
``````

The output is as follows:

```> snip - way too much data before this bit <

Level 95.: Find the next prime number after 584:
587
Yay, that's right!
Level 96.: Find the next prime number after 425:
431
Yay, that's right!
Level 97.: Find the next prime number after 837:
839
Yay, that's right!
Level 98.: Find the next prime number after 44:
47
Yay, that's right!
Level 99.: Find the next prime number after 422:
431
Yay, that's right!
Level 100.: Find the next prime number after 902:
907
Yay, that's right!
IW{Pr1m3s_4r3_!mp0rt4nt}
```

100 primes! Way too many to type by hand. Interestingly, the request value was never higher than 1000, so on-the-fly calculation would have probably been fine. Categories: Hacking CTF