# WhiteHat GrandPrix 2018: Misc04
## Problem Statement
`nc misc04.grandprix.whitehatvn.com 1337`
__Hint__: After get the message "It's a friendly point", you should send the friendly point value.
Here is the prompt:
```                   Wellcom to Friendly face challengeAccording to experts, the formula for measuring the friendliness of a face is    (lip point**nose point)**(eyes point**forehead point) mod Face_index                              Now play!------------------------------Stage 1--------------------------------------Face_index: 7897184Face           Lip point      Nose point     Eyes point     Forehead point:-)            475020320      847953080      880256045      579217726      (';')          428011459      639570885      173423050      299150823...     (=^..^=)       937474753      344758946      966767343      782968811      So, what is the most friendly face?```
## Solution
The solution that will be discussed would be the "semi-naive" approach in solving this problem. It doesn't necessarily solve the problem well sometimes but it is _good enough_ to get the flag.
### Explanation ("Quick" Approach)
If we try to compute the _friendliness_ of the `:-)` face, we would have to evaluate:```python((475020320**847953080)**(880256045**579217726)) mod 7897184```
So a useful concept here is to use `mod_pow` which is really just [binary exponentiation](https://cp-algorithms.com/algebra/binary-exp.html).
```pythondef mod_pow(n, e, mod):	if e == 0:		return 1	ret = mod_pow(n, e/2, mod)	ret = (ret*ret) % mod	if e % 2 == 1:		ret *= n	return ret % mod```
With `mod_pow`, we can quickly evaluate `(475020320**847953080) mod 7897184` which is `2954392`. Now we are left with:
```python(2954392**(880256045**579217726)) mod 789718```
 It is __incorrect__ to assume that we can simply get `(880256045**579217726) mod 789718` and substitute that value in the equation. Instead we have to find the period of `2954392^r mod 789718`. When we evaluate the following: * `2954392^1 mod 789718` * `2954392^2 mod 789718` * `2954392^3 mod 789718` * `2954392^4 mod 789718` * ...
We will find an exponent `r` such that `2954392^r == 2954392 mod 789718`. The easiest way to do this is to just evaluate `r=1`, `r=2`, ... until we find the period, which is `r-1 = 46452`.
```pythondef mod_find_cycle(n, mod):	curr = (n**2)%mod	count = 2	while curr != n:		curr = (curr*n)%mod		count+=1	return count-1```
Using this period, we can now find `(475020320**847953080) mod (46452))`, which is `5632`. And now we can simply have to evaluate:
```python(2954392**(5632)) mod 789718```
This is `230232`.
So in summary, given the functions defined above:```pythonlip_nose = mod_pow(lip, nose, face_index)cycle_length = mod_find_cycle(lip_nose, face_index)eyes_forehead = mod_pow(eyes, forehead, cycle_length)value = mod_pow(lip_nose, eyes_forehead, face_index)```
### Full Solution```pythonfrom pwn import *
def mod_pow(n, e, mod):	if e == 0:		return 1	ret = mod_pow(n, e/2, mod)	ret = (ret*ret) % mod	if e % 2 == 1:		ret *= n	return ret % mod
def mod_find_cycle(n, mod):	curr = (n**2)%mod	count = 2	while curr != (n%mod):		curr = (curr*n)%mod		count+=1	return count-1
r = remote('misc04.grandprix.whitehatvn.com', 1337)message = r.recvuntil('face?\n')prompt = message.split('\n')[5:]
while True:	face_index = int(prompt[0].split(': ')[1])	faces = []
	for e in prompt[2:]:		if e.startswith('So'):			break		parts = e.split()  		face = parts[0]		lip = int(parts[1])		nose = int(parts[2])		eyes = int(parts[3])		forehead = int(parts[4])
		lip_nose = mod_pow(lip, nose, face_index)		cycle_length = mod_find_cycle(lip_nose, face_index)		eyes_forehead = mod_pow(eyes, forehead, cycle_length)		value = mod_pow(lip_nose, eyes_forehead, face_index)		faces.append((value, face))
	faces.sort()	r.send(faces[-1][1] + '\n')	r.recvline()	r.send('{}\n'.format(faces[-1][0]))	stage = r.recvline()	if 'Stage' not in stage:		print(stage)		break	prompt = r.recvuntil('face?\n').split('\n')
```
Perhaps the hardest part of the problem is that without the _hint_, you'd have to guess that you'd have to send the value after giving the face.