Rubikrypto writeup

Rubikrypto.md

Rubikrypto

This is only ElGamal cryptosystem on Rubik Cube.

The order of Rubik Cube Group is 43_252_003_274_489_856_000n and this is small enough to use Pohlig-Hellman.

So the algorithm is simple:

1. get g, h, c1, c2.
2. calculate y = log_g(c1) using Pohlig-Hellman.
3. get message cube m = c2.multiply(invert(pow(h,y))).
4. from all cubes, recover flag.

But these are on Rubik Cube and cubejs is available on JavaScript, so the implementation is harder than usual...

solve.js

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

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 inv = (a) => {
  return (new Cube()).move(a.solve());
};

const str = '['+(fs.readFileSync('./output.txt')+'').split('g').join('"g"').split('h').join('"h"').split('c1').join('"c1"').split('c2').join('"c2"').split('}').join('},')+']';
const json = JSON.parse(str.split('},\n]').join('}]'));
const ORDER = 43_252_003_274_489_856_000n;
const ords = [134217728, 4782969, 125, 49, 11];

const extgcd = (a,b)=>{
  let [x0,y0,x1,y1] = [1n,0n,0n,1n];
  while(b != 0){
    [q,a,b] = [a/b, b, a%b];
    [x0,x1] = [x1, x0-q*x1];
    [y0,y1] = [y1, y0-q*y1];
  }
  return [a, x0, y0];
};
const modinv = (a, n) => {
  let [g,x,y] = extgcd(a,n);
  return (x + n) % n;
};

const dlogBG = (g, gx, ord)=>{
  const m = Math.ceil(Math.sqrt(ord));
  const hash = {};
  for(let j=0; j<m; j++){
    const gj = pow(g, BigInt(j));
    const gstr = cube2number(gj);
    if(gstr in hash)continue;
    hash[gstr] = j;
  }
  const ginv = inv(g);
  const ginvm = pow(ginv, BigInt(m));
  let gamma = gx;
  for(let i=0; i<m; i++){
    const gstr = cube2number(gamma);
    if(gstr in hash){
      // console.log(gstr);
      // console.log(hash[gstr]);
      const ans = i*m + hash[gstr];
      // console.log(pow(g,BigInt(ans)).solve());
      // console.log(gx.solve());
      return ans;
    }
    gamma = gamma.multiply(ginvm);
  }
  console.log('error');
};

const dlogPH = (g, gx)=>{
  const anses = [0,0,0,0,0];
  for(let i=0; i<5; i++){
    const ord = ords[i];
    const gg = pow(g, ORDER / BigInt(ord));
    const gxx = pow(gx, ORDER / BigInt(ord));
    anses[i] = BigInt(dlogBG(gg, gxx, ord));
  }
  // garner
  res = 0n
  for(let i=0; i<5; i++){
    [d,x,y] = extgcd(BigInt(ords[i]), ORDER/BigInt(ords[i]));
    res += y * (ORDER / BigInt(ords[i])) * anses[i];
  }
  res = (res % ORDER + ORDER) % ORDER;
  console.log(anses);
  console.log(res);
  return res;
};

const cubes = [];
for(const dat of json){
  let {g,h,c1,c2} = dat;
  g = (new Cube()).move(g);
  h = (new Cube()).move(h);
  c1 = (new Cube()).move(c1);
  c2 = (new Cube()).move(c2);
  // h = g^x
  // c1 = g^y
  // c2 = m * h^y
  // h^y = (g^x)^y
  // given g^x, g, find x
  const y = dlogPH(g, c1);
  const gy = pow(g, BigInt(y));
  console.log(cube2number(c1) === cube2number(gy));
  const hy = pow(h, BigInt(y));
  const m = c2.multiply(inv(hy));
  cubes.push(m);
}
const buf = cubes2buffer(cubes);
console.log(buf);
console.log((new TextDecoder).decode(buf));