# ASISCTF 2021: Crypto Warm upIn this challenge you are given a cipher text and an encryption algorithm.
## Cipher AnalysisFirst 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).```pythondef 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 sDue to s only being used in ![s^{i} \mod p](https://latex.codecogs.com/gif.latex?s%5E%7Bi%7D%20%5Cmod%20p)   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 spaceWe 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 ![s^{n-1} \equiv k \mod p](https://latex.codecogs.com/gif.latex?s%5E%7Bn%20-%201%7D%20%5Cequiv%20k%20%5Cmod%20p) where k is the index of the known char and add the roots to set s\_i```sagewith 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 permutationThen 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```sagefor 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'clockAfter running `sage solve.sage` the program spits out```textpossible 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|_" ```