TSGCTF 2020 rubikrypto

solve.js

const Cube = require('cubejs');
const fs = require('fs');
const {randint, buffer2cubes, cubes2buffer} = require('./utils.js');

// use calculated dlogs to get the flag

const pow = (a, n) => {
  const r = new Cube();
  const x = a.clone();
  while (n !== 0n) {
    if (n % 2n === 1n) {
      r.multiply(x);
    }
    x.multiply(x);
    n /= 2n;
  }
  return r;
};

const str = (cube) => Cube.inverse(cube.solve());

const ORDER = 43_252_003_274_489_856_000n;

Cube.initSolver();

cs = [{g: "L2 R2 U R2 U' R2 B2 D2 L2 U B2 U2 R' B' U2 F2 U L' B2 R D' R'",
h: "L2 R2 D2 B2 L2 U' R2 D B2 D' B2 U' F R' D U' L D' B U R F",
c1: "U2 F2 D L2 B2 D' R2 B2 F2 U L2 U2 F R U L2 R2 U2 B' F2 U",
c2: "U2 L2 R2 U' R2 D2 F2 U B2 U R2 F' U L' B D' U2 R' F2 L' B D",
y: 1181},
{g: "U2 L2 U2 L2 D F2 D' L2 D R2 U' R2 U2 F L B D' L2 D2 R F2 D'",
h: "L2 U L2 D' B2 U R2 U B2 R2 B2 R U2 B D' L2 D' F' R U' B D2",
c1: "L2 D2 F2 U L2 D2 L2 U B2 D' B2 F' L D' B' U' R F U' B2 L' F2",
c2: "L2 F2 D2 F2 D' R2 B2 D B2 L2 U B2 F' L2 F' D F2 L F D R U",
y: 273},
{g: "B2 U F2 D B2 D L2 U R2 D' B F R' D F L R F2 R2 B U2",
h: "L2 F2 U2 R2 F2 R2 U2 R2 F2 L' R' U2 L' R'",
c1: "D F2 U F2 U B2 D' B2 U F2 L2 U2 R' F2 L U2 B' U' L2 R' B2 F'",
c2: "F2 U L2 F2 D L2 U R2 B2 U' B2 R2 U B R' D' U F' L B' R' D'",
y: 33},
{g: "B2 L2 D' B2 R2 U2 L2 U' F2 U R2 F2 R B' D2 R F R' D L U' F",
h: "F2 D' L2 D U2 L2 R2 U' L2 B2 U2 B' F L B2 D' B2 L' U2 F U2 R'",
c1: "D' F2 R2 B2 F2 U2 L2 U' B2 U R2 B2 F2 L' D L2 R B F' L U L2",
c2: "U2 R2 D U2 F2 L2 D' L2 U L2 U2 R' B' D2 U2 L R2 B R D R'",
y: 325},
{g: "B2 U' F2 U' F2 U2 L2 D B2 U' B2 F' L' R2 B' R2 D B F D2 R' U",
h: "F2 R2 B2 L2 F2 R2 U R2 U' L2 R2 D2 L' B L F2 L' U2 F' R2 U' R2",
c1: "R2 U' L2 D2 U' F2 L2 B2 F2 R2 D' B' R' D L' R' U2 B' D' U R'",
c2: "U2 R2 U' L2 U' F2 D B2 D F2 R2 U F' L B R2 F R2 D U F' R",
y: 173},
{g: "F2 D' L2 U2 F2 R2 U2 R2 F2 L2 R' F L2 F2 L' D' R B R2 D' F2",
h: "B2 U F2 R2 D L2 U' F2 U2 F2 R2 F' U R' B2 D' F L' F2 U F U'",
c1: "D R2 D' B2 D' F2 L2 F2 D2 B2 F2 U' L' U2 B F' R B D2 L2 D R2",
c2: "F2 R2 F2 D' L2 D L2 U F2 U L2 U2 F' L R' D' L R2 U' L D'",
y: 75},
{g: "D2 L2 D' F2 L2 R2 U' B2 F2 D2 U' R2 B' L F' L' F' L' D2 U",
h: "B2 U2 L2 D' R2 F2 R2 U' R2 D' L2 D U' F' D' R' D2 F' D' F R'",
c1: "D R2 B2 D L2 U2 R2 B2 U F2 D2 R' B2 D' U2 B R' B2 R' F R2 U",
c2: "D2 L2 R2 B2 D' F2 D L2 D' F2 R2 B' R2 U L R' D B L2 U L' B'",
y: 151},
{g: "D' F2 L2 U' B2 U2 F2 D' F2 U' B' R' U R D2 B R B L' U2 R2",
h: "D2 B2 F2 D B2 D L2 B2 F2 U' L2 U2 L B' F U' F D2 B2 L D2 U'",
c1: "L2 R2 U L2 R2 U2 F2 U' R2 U' B2 D' R D2 F R' D' F U' L2 D' U",
c2: "U2 B2 U' F2 R2 D L2 F2 U B2 D' B U' R2 F2 R B' L' R F D' R'",
y: 245},
{g: "D' R2 D' B2 R2 D L2 U2 R2 B2 L2 B2 L' B U' R' D' R B' F2 L2",
h: "U' R2 B2 D2 B2 U' B2 D' F2 D U2 F R2 U' L' D' B' U2 F' L' U2 R'",
c1: "U L2 R2 F2 R2 U B2 D R2 B2 D' R2 B' D F2 R U2 R B D R F",
c2: "R2 F2 L2 F2 U F2 U2 R2 F2 U' B2 R2 B' R2 U B' R' F' R2 D' R2 F2",
y: 68},
{g: "L2 U B2 U' F2 R2 D' L2 B2 U L2 F' D' R' U R' D2 R' B' L' F R2",
h: "F2 D F2 L2 U2 B2 F2 U' L2 U B2 D2 L B2 R D' B' F2 L2 B2 D2 R",
c1: "R2 B2 U2 R2 B2 D U B2 R2 U2 F2 L' F2 R D U' F' D2 F' U2",
c2: "L2 D F2 D B2 F2 R2 D2 R2 U B2 L2 F2 R B R' B' L R F' R2 F2",
y: 72}]


cubes = []

for (const cube of cs)
{
  console.log("new cube")
  g = new Cube()
  g.move(cube.g)
  h = new Cube()
  h.move(cube.h)
  c2 = new Cube()
  c2.move(cube.c2)
  c1 = new Cube()
  c1.move(cube.c1)

  y = BigInt(cube.y)

  t = pow(g, y)
  console.log(str(t))
  console.log(str(c1))

  k = pow(h, y).solve()
  s = new Cube()
  s.move(k)
  m = c2.clone()
  f = m.multiply(s)
  cubes.push(f)
}
console.log(cubes2buffer(cubes).toString('utf8'))



// const flag = fs.readFileSync('flag.txt');
// const cubes = buffer2cubes(flag);
// console.log(cubes2buffer(cubes))

// for (const cube of cubes) {
//   const g = Cube.random();
//   const x = randint(ORDER)

//   const h = pow(g, x);
//   const y = randint(ORDER)
//   console.log(x);
//   console.log(y);
//   const m = cube.clone();

//   const c1 = pow(g, y);
//   const c2 = m.multiply(pow(h, y));
//   const t = pow(h, y).solve();
//   const test = new Cube();
//   const m2 = c2.clone();
//   const m3 = c2.clone();
//   test.move(t)
//   var test2 = m2.multiply(test)
//   var test3 = m3.move(t)
//   console.log(cubes2buffer([test2]))
//   console.log(cubes2buffer([test3]))

//   console.log({
//     g: str(g),
//     h: str(h),
//     c1: str(c1),
//     c2: str(c2),
//   });
// }

solve.sage

import json
# calculate discrete logarithms in rubik cube group

S48=SymmetricGroup(48)
R=S48("(25,27,32,30)(26,29,31,28)(3,38,43,19)(5,36,45,21)(8,33,48,24)")
L=S48("(9,11,16,14)(10,13,15,12)(1,17,41,40)(4,20,44,37)(6,22,46,35)")
U=S48("(1,3,8,6)(2,5,7,4)(9,33,25,17)(10,34,26,18)(11,35,27,19)")
D=S48("(41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40)")
F=S48("(17,19,24,22)(18,21,23,20)(6,25,43,16)(7,28,42,13)(8,30,41,11)")
B=S48("(33,35,40,38)(34,37,39,36)(3,9,46,32)(2,12,47,29)(1,14,48,27)")
RC3=S48.subgroup([R,L,U,D,F,B])

cs = """
[{
  "g": "L2 R2 U R2 U' R2 B2 D2 L2 U B2 U2 R' B' U2 F2 U L' B2 R D' R'",
  "h": "L2 R2 D2 B2 L2 U' R2 D B2 D' B2 U' F R' D U' L D' B U R F",
  "c1": "U2 F2 D L2 B2 D' R2 B2 F2 U L2 U2 F R U L2 R2 U2 B' F2 U",
  "c2": "U2 L2 R2 U' R2 D2 F2 U B2 U R2 F' U L' B D' U2 R' F2 L' B D"
},
{
  "g": "U2 L2 U2 L2 D F2 D' L2 D R2 U' R2 U2 F L B D' L2 D2 R F2 D'",
  "h": "L2 U L2 D' B2 U R2 U B2 R2 B2 R U2 B D' L2 D' F' R U' B D2",
  "c1": "L2 D2 F2 U L2 D2 L2 U B2 D' B2 F' L D' B' U' R F U' B2 L' F2",
  "c2": "L2 F2 D2 F2 D' R2 B2 D B2 L2 U B2 F' L2 F' D F2 L F D R U"
},
{
  "g": "B2 U F2 D B2 D L2 U R2 D' B F R' D F L R F2 R2 B U2",
  "h": "L2 F2 U2 R2 F2 R2 U2 R2 F2 L' R' U2 L' R'",
  "c1": "D F2 U F2 U B2 D' B2 U F2 L2 U2 R' F2 L U2 B' U' L2 R' B2 F'",
  "c2": "F2 U L2 F2 D L2 U R2 B2 U' B2 R2 U B R' D' U F' L B' R' D'"
},
{
  "g": "B2 L2 D' B2 R2 U2 L2 U' F2 U R2 F2 R B' D2 R F R' D L U' F",
  "h": "F2 D' L2 D U2 L2 R2 U' L2 B2 U2 B' F L B2 D' B2 L' U2 F U2 R'",
  "c1": "D' F2 R2 B2 F2 U2 L2 U' B2 U R2 B2 F2 L' D L2 R B F' L U L2",
  "c2": "U2 R2 D U2 F2 L2 D' L2 U L2 U2 R' B' D2 U2 L R2 B R D R'"
},
{
  "g": "B2 U' F2 U' F2 U2 L2 D B2 U' B2 F' L' R2 B' R2 D B F D2 R' U",
  "h": "F2 R2 B2 L2 F2 R2 U R2 U' L2 R2 D2 L' B L F2 L' U2 F' R2 U' R2",
  "c1": "R2 U' L2 D2 U' F2 L2 B2 F2 R2 D' B' R' D L' R' U2 B' D' U R'",
  "c2": "U2 R2 U' L2 U' F2 D B2 D F2 R2 U F' L B R2 F R2 D U F' R"
},
{
  "g": "F2 D' L2 U2 F2 R2 U2 R2 F2 L2 R' F L2 F2 L' D' R B R2 D' F2",
  "h": "B2 U F2 R2 D L2 U' F2 U2 F2 R2 F' U R' B2 D' F L' F2 U F U'",
  "c1": "D R2 D' B2 D' F2 L2 F2 D2 B2 F2 U' L' U2 B F' R B D2 L2 D R2",
  "c2": "F2 R2 F2 D' L2 D L2 U F2 U L2 U2 F' L R' D' L R2 U' L D'"
},
{
  "g": "D2 L2 D' F2 L2 R2 U' B2 F2 D2 U' R2 B' L F' L' F' L' D2 U",
  "h": "B2 U2 L2 D' R2 F2 R2 U' R2 D' L2 D U' F' D' R' D2 F' D' F R'",
  "c1": "D R2 B2 D L2 U2 R2 B2 U F2 D2 R' B2 D' U2 B R' B2 R' F R2 U",
  "c2": "D2 L2 R2 B2 D' F2 D L2 D' F2 R2 B' R2 U L R' D B L2 U L' B'"
},
{
  "g": "D' F2 L2 U' B2 U2 F2 D' F2 U' B' R' U R D2 B R B L' U2 R2",
  "h": "D2 B2 F2 D B2 D L2 B2 F2 U' L2 U2 L B' F U' F D2 B2 L D2 U'",
  "c1": "L2 R2 U L2 R2 U2 F2 U' R2 U' B2 D' R D2 F R' D' F U' L2 D' U",
  "c2": "U2 B2 U' F2 R2 D L2 F2 U B2 D' B U' R2 F2 R B' L' R F D' R'"
},
{
  "g": "D' R2 D' B2 R2 D L2 U2 R2 B2 L2 B2 L' B U' R' D' R B' F2 L2",
  "h": "U' R2 B2 D2 B2 U' B2 D' F2 D U2 F R2 U' L' D' B' U2 F' L' U2 R'",
  "c1": "U L2 R2 F2 R2 U B2 D R2 B2 D' R2 B' D F2 R U2 R B D R F",
  "c2": "R2 F2 L2 F2 U F2 U2 R2 F2 U' B2 R2 B' R2 U B' R' F' R2 D' R2 F2"
},
{
  "g": "L2 U B2 U' F2 R2 D' L2 B2 U L2 F' D' R' U R' D2 R' B' L' F R2",
  "h": "F2 D F2 L2 U2 B2 F2 U' L2 U B2 D2 L B2 R D' B' F2 L2 B2 D2 R",
  "c1": "R2 B2 U2 R2 B2 D U B2 R2 U2 F2 L' F2 R D U' F' D2 F' U2",
  "c2": "L2 D F2 D B2 F2 R2 D2 R2 U B2 L2 F2 R B R' B' L R F' R2 F2"
}]

"""

cs = json.loads(cs)
for c in cs:
    g = RC3(rubik.parse(c["g"]))
    c1 = RC3(rubik.parse(c["c1"]))
    y = discrete_log(c1, g)
    c["y"] = y

print(cs)