# Baby Shuffle — Solution
We are given a file called `server.py` along with a connection string to theremote server. When we connect to the server, we receive the following data:
![Chall](img/chall.png)
The setup of the challenge is basically laid out in front of us. More precisely,we have the following information:  * The public [RSA](https://en.wikipedia.org/wiki/RSA_(cryptosystem)) key, i.e.    the modulus $N$ and the public exponent $e$.  * The ciphertext produced by encrypting the flag using the above public key.  * The ciphertext produced by encrypting the permuted flag using the above    public key.  * The challenge strongly hints that the "flag shuffling" was not done    partciularly well.
Let's check out the relevant parts of the implementation in `server.py`.
```pythonclass RSA:    BITS = 512
    def __init__(self):        self.p = getPrime(self.BITS)        self.q = getPrime(self.BITS)        self.n = self.p * self.q        self.e = 17
    def pubkey(self):        return (self.n, self.e)
    def encrypt(self, m):        return pow(m, self.e, self.n)```
So far, so good... The `RSA` class seems to be reasonably implemented in thecontext of a CTF. Let's see how is it used.
```pythonflag = open("flag.txt", "r").read().strip()shuffled_flag = flag[-1] + flag[:-1]
assert(len(flag) == 61)
myprint(f"(N, e) = ({cipher.n}, {cipher.e})")
m1 = bytes_to_long(flag.encode("utf-8"))m2 = bytes_to_long(shuffled_flag.encode("utf-8"))
c1 = cipher.encrypt(m1)c2 = cipher.encrypt(m2)
myprint(f"c1 = {c1}")myprint(f"c2 = {c2}")```
Ok, looks like the flag is not shuffled at all. Instead, it has been[circularly shifted](https://en.wikipedia.org/wiki/Circular_shift) to the rightby one character.
If this doesn't immediately give out the attack to you, it is a good idea toresearch some well-known attacks against the RSA cryptosystem. A great resourcefor that purpose is [thispaper](https://crypto.stanford.edu/~dabo/pubs/papers/RSA-survey.pdf) by DanBoneh.
Just by looking at the attack names, the "Franklin-Reiter Related MessageAttack" immediately stands out because the two encrypted messages in our caseare definitely strongly related. Let's see what is this attack all about andwhat conditions need to be satisfied in order to mount it.
The necessary conditions are:  * We need to know the public key with which two messages were encrypted  * The public exponent $e$ needs to be "small"  * Messages $M_1$ and $M_2$ need to satisfy $M_1 = f(M_2) \mod N$, for some    known linear polynomial $f(x) = ax + b \in \mathbb{Z}_N[x]$, where $b \ne 0$.
Given these conditions are met, an attacker should be able to deduce $M_1$ and$M_2$, which is exactly what we want.
The first two conditions obviously hold, what about the third one? Can we findthe linear polynomial $f(x)$ such that $f(M_1) = M_2$?
Of course we can!
To make our lives easier, we will transform $M_2$ (the *shuffled* flag) into$M_1$ using a linear polynomial. Let's see, we need to:  * Add the character `}` as the last element.  * Remove the character `}` from the first element.
To add a character, we need to *make some room for it*. In other words, we willneed to shift $M_2$ to the left by 8 bits in order to append a new character.This is the same as multiplying $M_2$ by $2^8$. Adding the character now boilsdown to incrementing $M_2$ with the ascii value of `}`, which is $125$.
Now to remove the first character, we will simply decrease the value of $M_2$by the shifted ascii value of `}` by the length of the flag. This equals to$2^{61 \cdot 8} \cdot 125$.
In total, we've multiplied $M_2$ by $2^8$, therefore $a = 2^8$. We've alsoadded to it $125$, and subtracted $2^{61 \cdot 8} \cdot 125$, making $b = 125 - 2^{61 \cdot 8} \cdot 125$
Now, all that is left to do is to implement the attack by following thedescription in the paper.
Putting it all together in a solve script:
```sagefrom Crypto.Util.number import *
(N, e) = (112153052251909364783308270590397746531609910104166334595923202016390447976677079867403232057727250231696335160570132850610262158172833494281653230380660063956295425794739260806712635773413785147778859690744295256452049506808129359916021415700901260208117922700040853622956983687979711198405721229154361646579, 17)c1 = 78864742082332223108178230358000266004470931720079683255285292238641115808760648155039121450606113339286686223280031100480222153671600244333633846762469936846532257315775568469791246301540478826458197579990381744555892521144223274010450757999785181053774832962110745144727049687042555070865449787051501053959c2 = 6585395060343147891100039023563439293501539588909846320283080181220377506011006401305950317373682510271235776656043396895585148284029657373536876376820285984022186488664177497404180038601761647270471329724434774733979814363977868741805880498722071147845627397600301632678051748619345144811128191656190996124L = 61 * 8
a = 2^8b = -2^L * ord('}') + ord('}')
def compositeModulusGCD(a, b):  if b == 0:    return a.monic()  return compositeModulusGCD(b, a % b)
P.<x> = PolynomialRing(Zmod(N))f = (a*x + b)^e - c1g = (x)^e - c2m = Integer(N - (compositeModulusGCD(f,g)).coefficients()[0])
shuffled = long_to_bytes(m).decode("utf-8")flag = shuffled[1:] + shuffled[0]print(flag)```
This finally yields the flag: `TBTL{1_5i7_4nd_wa7ch_7h3_ch1ldr3n_pl4y_w17h_r3l4t3d_m3554g35}`.