# Homecooked

## Topics

- prime generation

## Challenge

[decrypt.py](https://github.com/ret2basic/ret2basic.github.io/blob/master/challs/NahamCon_CTF_2020/Crypto/Homecooked/decrypt.py)

## Source Code

```python
import base64
num = 0
count = 0
cipher_b64 = b"MTAwLDExMSwxMDAsOTYsMTEyLDIxLDIwOSwxNjYsMjE2LDE0MCwzMzAsMzE4LDMyMSw3MDIyMSw3MDQxNCw3MDU0NCw3MTQxNCw3MTgxMCw3MjIxMSw3MjgyNyw3MzAwMCw3MzMxOSw3MzcyMiw3NDA4OCw3NDY0Myw3NTU0MiwxMDAyOTAzLDEwMDgwOTQsMTAyMjA4OSwxMDI4MTA0LDEwMzUzMzcsMTA0MzQ0OCwxMDU1NTg3LDEwNjI1NDEsMTA2NTcxNSwxMDc0NzQ5LDEwODI4NDQsMTA4NTY5NiwxMDkyOTY2LDEwOTQwMDA="

def a(num):
if (num > 1):
for i in range(2,num):
if (num % i) == 0:
return False
break
return True
else:
return False

def b(num):
my_str = str(num)
rev_str = reversed(my_str)
if list(my_str) == list(rev_str):
return True
else:
return False

cipher = base64.b64decode(cipher_b64).decode().split(",")

while(count < len(cipher)):
if (a(num)):
if (b(num)):
print(chr(int(cipher[count]) ^ num), end='', flush=True)
count += 1
if (count == 13):
num = 50000
if (count == 26):
num = 500000
else:
pass
num+=1

print()
```

## Analysis

This decrypt script isn't working properly because the implementation of function `a()` is bad. So this function is essentially the naive implementation of `isprime()`. When `num` gets large, the for loop would run forever. A trick to optimize this function is to run the for loop in the range of `(2, int(sqrt(num)) + 1)`, since no factor of `num` would exceed its square root:

```python
for i in range(2, int(sqrt(num)) + 1):
```

There is a nice explanation [here on stackoverflow](https://stackoverflow.com/questions/5811151/why-do-we-check-up-to-the-square-root-of-a-prime-number-to-determine-if-it-is-pr).

## Script

```python
#!/usr/bin/env python3
import base64
from math import sqrt

num = 0
count = 0
cipher_b64 = b"MTAwLDExMSwxMDAsOTYsMTEyLDIxLDIwOSwxNjYsMjE2LDE0MCwzMzAsMzE4LDMyMSw3MDIyMSw3MDQxNCw3MDU0NCw3MTQxNCw3MTgxMCw3MjIxMSw3MjgyNyw3MzAwMCw3MzMxOSw3MzcyMiw3NDA4OCw3NDY0Myw3NTU0MiwxMDAyOTAzLDEwMDgwOTQsMTAyMjA4OSwxMDI4MTA0LDEwMzUzMzcsMTA0MzQ0OCwxMDU1NTg3LDEwNjI1NDEsMTA2NTcxNSwxMDc0NzQ5LDEwODI4NDQsMTA4NTY5NiwxMDkyOTY2LDEwOTQwMDA="

def a(num):
if (num > 1):
# only this for loop is modified
for i in range(2, int(sqrt(num)) + 1):
if (num % i) == 0:
return False
break
return True
else:
return False

def b(num):
my_str = str(num)
rev_str = reversed(my_str)
if list(my_str) == list(rev_str):
return True
else:
return False

cipher = base64.b64decode(cipher_b64).decode().split(",")

while(count < len(cipher)):
if (a(num)):
if (b(num)):
print(chr(int(cipher[count]) ^ num), end='', flush=True)
count += 1
if (count == 13):
num = 50000
if (count == 26):
num = 500000
else:
pass
num+=1

print()
```

## Flag

```plaintext
flag{pR1m3s_4re_co0ler_Wh3n_pal1nDr0miC}
```