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).