Tags: crypto prime

Rating:

# Homecooked

## Topics

- prime generation

## Challenge

## 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}