Rating: 5.0
# ASISCTF 2021: Crypto Warm up
In this challenge you are given a cipher text and an encryption algorithm.
## Cipher Analysis
First it generates a random n bit prime p and pads the plaintext with random ascii characters until len(msg) == p. In our case p is a 19489 (a 15 bit prime).
```python
def encrypt(msg, nbit):
l, p = len(msg), getPrime(nbit)
rstr = random_str(p - l)
msg += rstr
```
The random\_str function isnt anything special, it just creates a random string using all printable non-whitespace characters.
Then it selects a random 1024 bit number which passes the `is_valid` requirement.
```python
while True:
s = getRandomNBitInteger(1024)
if is_valid(s, p):
break
```
Then it computes the ciphertext, it is a permutation of the padded plaintex. For this to be decryptable s would need to be coprime to p.
```python
enc = msg[0]
for i in range(p-1):
enc += msg[pow(s, i, p)]
return enc
```
## Reducing s
Due to s only being used in  s can be reduced modulo p. That means that this can be easily brute forced as there are only p - 1 (19488) possible values for s.
However we can create a solution which is faster than bruteforce and works for p way larger than 19489 using a known plaintext attack.
## Reducing the search space
We know that msg starts with 'ASIS{'. The first characters dont give any meaningful information sinec they also appear as the first two characters of the ciphertext. This leaves us with 'I' at index 2, 'S' as index 3 and '{' at index 4
Then, for each character we find all occurences of that character in the ciphertext and their indicies and solve for  where k is the index of the known char and add the roots to set s\_i
```sage
with open('output.txt') as f:
output = f.read()
def findIdx(ch):
return [enum for enum, x in enumerate(output) if x == ch and enum != 0]
known = [('I', 2), ('S', 3), ('{', 4)]
S = set()
for char in known:
possibilities = findIdx(char[0])
s = []
for poss in possibilities:
roots = Mod(char[1], p).nth_root(poss - 1, all = True)
s.extend(roots)
```
Next we define S as the intersection of all sets s\_i. S should contain drastically fewer possibilities for s (in our case 2).
## Inverting the permutation
Then we can try inverting the permutation for all s in S and see which one looks like the flag. (Here we assume that the flag is less than 100 characters
```sage
for s in S:
flag = 'AS'
for x in range(2, 100):
exponent = discrete_log(Mod(x, p), Mod(s, p))
flag += output[exponent + 1]
print(flag)
```
## Flag o'clock
After running `sage solve.sage` the program spits out
```text
possible S: {8562, 10927}
ASIS{_how_dFC.YptZTh1S?h0mx_m4d;_lGD_w;dr\_CUYpI0_5J2T3+?k!!!*Z}j4M?rTU{|MEyI5cnOa6h3+P2Dbv=b,$|R|_)
ASIS{_how_d3CrYpt_Th1S_h0m3_m4dE_anD_wEird_CrYp70_5yST3M?!!!!!!}j-3?cTU&|MEy&*+nOa9F3_P2SbvHb!,aR|_" ```
