Rating:

# Rubikcrypto Writeup En

This is just an Elgamal Cryptosystem on Rubik's Cube Group.

## Solution 1

As you can see in elgamal.js, the order of Rubik's Cube Group is `p = 43252003274489856000`. By the way,

```

p = 43252003274489856000 = 2^27 * 3^14 * 5^3 * 7^2 * 11

```

and,

```

φ(p) = 8987429251842048000 = 2^31 * 3^14 * 5^3 * 7

```

Then the maximum of prime power factor of `φ(p)` is `2^31`, so we can use Pohlig–Hellman algorithm to break the cypher.

## Solution 2

No, no, no! It doesn't have to be that difficult!

As stated in [Rubik's Cube group - Wikipedia](https://en.wikipedia.org/wiki/Rubik%27s_Cube_group#Group_structure), the order of an element of Rubik's Cube group is only **1260** at most, so if you multiply `g` by 1260 times, there will always be `h` somewhere. Therefore, we get `x` and decrypt it immediately.

Solver can be found [here](https://github.com/tsg-ut/tsgctf2020/blob/master/crypto/rubikrypto/solver/solve.js).

Original writeup (https://github.com/tsg-ut/tsgctf2020/blob/master/crypto/rubikrypto/writeup.en.md).