# 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
```pythonimport base64num = 0count = 0cipher_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:
```pythonfor 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 python3import base64from math import sqrt
num = 0count = 0cipher_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
```plaintextflag{pR1m3s_4re_co0ler_Wh3n_pal1nDr0miC}```