# Tokyo Western 2018: scs7## Solution
If you want to know the gist of the solution, just look at the quick explanation. The rest of the writeup would simply be my approach in solving this problem. If you need code snippets for some of the parts, it'll be in the github repository. 
### Quick Explanation
 The encryption used is a mix of a special encoding and substitution cipher using the following steps: 1. m1 = base59encode(m) 2. m2 = substitution_encryption(m1, secret_mapping)
 So to decrypt you first have to figure out the mapping used for the substitution cipher and then just reverse the process.
 1. m1 = substitution_decrypt(m2, secret_mapping) 2. flag = base59decode(m1)
### Full Explanation
Based on some trial and errors, we can see gain insight from the input and output.```message: aaaaciphertext: vyCU1bmessage: aaabciphertext: vyCU1Hmessage: aciphertext: 4Rmessage:```
#### It's an encoding
Observe the differences between `aaaa` and `aaab`.
```aaaa => vyCU1baaab => vyCU1H```
This is a clue that this is either a shift cipher, substitution cipher, or simply some encoding. One clue that can it is an encoding if that _"close"_ characters result to _"close"_ output. Here is an example below, where we see `a`, `b`, and `c` result to ciphertexts all starting with `g`.
```message: aciphertext: gAmessage: bciphertext: gXmessage: cciphertext: g1```
#### It's base59
We enumerate all printable ASCII characters to see if this behavior holds true or if this is a coincidence.
```message: 0ciphertext: mmessage: 1ciphertext: z2message:ciphertext: 13message:ciphertext: qmessage: 4ciphertext: F
...
message: 9ciphertext: Zmessage: :ciphertext: 3message: ;ciphertext: uGmessage: <ciphertext: uu
...
message: Aciphertext: uNmessage: Bciphertext: uRmessage: Cciphertext: u7message: Dciphertext: uS
```
So here it is clear that it is indeed some encoding. And we observe that it is notable that __starting `;`, the ciphertext is 2 digits__.
```| character | value || --------- | ----- || `:`       | 58    || `;`       | 59    || `<`       | 60    |```
Since `;` is 59, then this is a clue that this is in base59, since this would be `10` in base59. This is further supported by `<`, value 60, which should be `11` in base59.
We see the mapping
```| character | value | base59 | ciphertext || --------- | ----- | ------ | ---------- || `;`       | 59    | 10     | uG         || `<`       | 60    | 11     | uu         |```
So this leads us to believe that this is __base59 encoding + substitution cipher__.  
#### Finding out the substitution
However, we see that in each run, the substitution is different.```message: 9ciphertext: kmessage: :ciphertext: zmessage: ;ciphertext: AUmessage: <ciphertext: AA```
To do this, we generate a lot of ciphertext and since we know what the plaintext _(base59 of our message)_ should be, we can figure out what the mapping is.
```encrypted flag: ZwkbWBK6s1Juy2PPamHctPBy4hCDe5aKKEg2boyQ0UXdXz453nwcnkRd0SQaXnFP
You can encrypt up to 100 messages.message:OMPrEcUtniP3tKswwMLLnhCRYbIAMkS7vxycrccgciphertext: sjyzwT6TUwUVUZ8Xs0e7jerDy8QQR3jRdcPVedAf5dxrUMqWXkfKq8Emessage: vdBPbo7JqcrsQzU8ZzwvdvKOCxFK6wh9LL6ezeYXciphertext: xEeEDmYjuLUobQiTnP2NkoV3m8cTJWdKsh4EDd4EgkQNuyWqfWFZYKimessage: Q09UcgkIzd9Nt0BWXrX6wFc1kTrVhJACY0EmJeXcciphertext: s1WeVJdKJvGpVvQWZqExHJn61LTj3KiKuDAMP0eKdRpZuQwwJm2nJcWmessage: 3QFMcEPpXitmaL05OcTrE0dIBajyAtujbccupUJlciphertext: sqnbSkc8K3L50UDGDrHiQsCMpCpPnAgFBbrTmxYX1p8kasngcYJ7VGEmessage: NXY3IDTj6eKWvUVTMBLnE0XyjTnh70BtwSK8rXeCciphertext: sWfLryrSXGxo3MTBMTqzA3PmmtyR8GvzRTsH7ZBxKYwM6E09mFoer5x```
And from this information, we know enough to get the flag.
`TWCTF{67ced5346146c105075443add26fd7efd72763dd}`