Solution to my April 2016 Puzzle

It's been three years now, and although I've had many people complain about it giving them a headache, to my knowledge no-one has solved the puzzle I posted in April 2016. My other puzzles and crypto trails have all fallen in significantly less time, but I've watched people really struggle with this one, so I think it's fair to say that I made it just a little too hard.

It only seems fair, therefore, to explain the solution (while I can still remember it).

This post will do just that (there's a video of solving it below for those who don't want to read)

 

The Puzzle

The puzzle presents you with the command used to encrypt a file, a number grid, and the ascii armoured encrypted file.

Screenshot of 201604 puzzle

The challenge is to solve the grid in order to calculate the encryption key.

 

Solving the puzzle

The first step, as with any number grid is to look for patterns. The eagle eyed will quite quickly spot a fibonacci sequence running down the right hand side

This sequence itself isn't actually used, but hopefully this and the reference to a Lucas prime (Lucas also being a fibonnacci like sequence) should alert you to the possibility there may be other fibonacci like sequences. In fact, you'll find one right next to a Lucas prime

 So we've got a fibonacci style sequence adjacent to a prime. This also occurs elsewhere in the grid, and the sequences don't always run forwards

 It's more than possible to sit and identify the sequences manually, but it's far easier to write some code to find them for you. Ultimately you'll end up with some code which solves the entire puzzle (see the bottom of this post for python and javascript solutions).

The next thing to do is to work out what to do with the identified sequences. The adjacent prime obviously has some relevance as the actual fibonacci sequence doesn't have one.

A bit of trial and error should reveal that if you subtract the prime from the number it's next to (e.g. 246-199) you'll always get a number in the range 0-127. This, conveniently is also the ASCII number range, so 246-199=47 which is the character /.

So, reading left to right, we can now assemble a 10 character string, at which point we've got our decryption passphrase.

It's then simply a case of dumping the ciphertext into a file, and then running

openssl enc -aes-256-cbc -a -d -salt -in [file]

Providing the decryption passphrase when prompted.

 

Demonstration

 

Solution Code

Javascript

As shown in the video above, it's sufficient to open developer tools and paste into the console. It'll also colour the relevant cells to show how it reached the solution

var css=document.createElement('style');
css.type='text/css';
css.innerHTML='.detectedPrime {background-color: red;} .sequenceMember {background-color: blue} .selected {background-color: yellow}';
document.getElementsByTagName('head')[0].appendChild(css);
var ele,eles,pele,ref,prime,sno, nums = {},ks =[],primes=[],neighbours=[],selecs=[],neighbours=[],identifiedPairs=[];


// Check whether a number is a prime
function checkNumPrime(n){

      // Check whether the number is 1,2 or 3
      if (n<4){
	  return true;
      }

      // Check the number isn't directly divisible by 2 or 3
      if (n%2 == 0 || n%3 == 0){
	  return false;
      }

      var di=2;
      var i = 5;

      // Don't calculcate higher than the square root (rounded down if needed)
      var lim = Math.floor(Math.sqrt(n));

      while (i < lim){

	if (n%i == 0){
	    return false;
	}
	i=i+di;
	di=6-di;
      }

      // If we haven't already returned, n is prime
      return true;

}


function decodeReference(id){
      // Remove the r
      id=id.substr(1);
      return id.split('c');
  
}


// Calculate the DOM ID of all adjacent cells
function calculateNeighbours(id){

      if (!id){
	  return [];
      }
  
      // Break the cell ID into a reference array
      var reference = decodeReference(id);

      // Calculate all adjacent neighbours by subtracting and adding to the reference
      var neighbours=[];

      // Calculate the permutations
      var incr = parseInt(reference[0])+1;
      var incc = parseInt(reference[1])+1;

      var decr = parseInt(reference[0])-1;
      var decc = parseInt(reference[1])-1;
      
      // Don't use negative numbers
      if (decr >= 0){
	    neighbours.push("r"+decr+"c"+reference[1]); // r-1,c
      }else{
	    neighbours.push(false);
      }
      
      // And don't fall off the edge of the grid
      if (incr <20){
	    neighbours.push("r"+incr+"c"+reference[1]); // r+1,c
      }else{
	    neighbours.push(false);
      }
      
      if (decc >=0){
	    neighbours.push("r"+reference[0]+"c"+decc); // r,c-1
      }else{
	    neighbours.push(false);
      }
      
      if (incc <20){
	  neighbours.push("r"+reference[0]+"c"+incc); // r,c+1
      }else{
	    neighbours.push(false);
      }
      
      return neighbours
}

// dir should be either c (column) or r (row)
function getDirectionalNeighbours(id,dir){
  
  var neighbours = calculateNeighbours(id);
  var dirneighbours = []
  
  if (dir == 'c'){
    dirneighbours.push(neighbours[0]);
    dirneighbours.push(neighbours[1]);
	
  }else{
    dirneighbours.push(neighbours[2]);
    dirneighbours.push(neighbours[3]);
  }
  
  return dirneighbours;
}


// Check Cells and identify whether they're part of a sequence
function isPartOfSequence(c1,c2,c3){
  
  if (!c1 || !c3){
      // don't fall off the end of the grid
    
      // Array is - isSequence, checked, sequenceorder, [cell references]
      return [false,false,false, [c1,c2,c3]];
  }
  
  n1 = parseInt(document.getElementById(c1).innerHTML);
  n2 = parseInt(document.getElementById(c2).innerHTML);
  n3 = parseInt(document.getElementById(c3).innerHTML);  
  
  var seq = false;
  var order = false;
  var cells = [c1,c2,c3];
  // Sequences can be ascending or descending, so we need to test both
  if (n1 + n2 == n3){
      seq = true;
      order = 'asc';
  }

  if (n1 - n2 == n3){
      seq = true;
      order = 'desc';
  }
  
  return [seq,true,order,cells];  
}


function colourSequenceMembers(ids){
  
  for (var i=0; i<ids.length;i++){
      document.getElementById(ids[i]).className = 'sequenceMember';
  }
  
}


function enforceFourWay(cells,direction){
      var dnb = getDirectionalNeighbours(cells[0],direction);
      var dseq = isPartOfSequence(dnb[0],cells[0],dnb[1]);
      var match = false;

      if (dseq[0] == true){
	  colourSequenceMembers(dseq[3]);
	  match=true;
      }

      var unb = getDirectionalNeighbours(cells[2],direction);
      var useq = isPartOfSequence(unb[0],cells[2],unb[1]);
      if (useq[0] == true){
	  colourSequenceMembers(useq[3]);
	  match=true;
      }		
      return match;
}

// Becaues Javascript is a dick when it comes to sorting numbers
function sortNumber(a,b) {
    return a - b;
}


// Cycle through cells and colour the primes as a starting point
eles = document.getElementsByTagName('td');


for (var i=0; i<eles.length; i++){
      if (checkNumPrime(eles[i].innerHTML)){
	primes.push(eles[i].id);
      }
}


// Work over each prime and identify it's neighbours, then look for sequences
for (var i=0; i<primes.length; i++){
      neighbours=calculateNeighbours(primes[i]);

      // Check for sequences in neighbours
      for (var r=0; r<neighbours.length; r++){
	      if (! neighbours[r]){
		    // Don't check anything that returned false
		    continue;
	      }
	      
	      var direction = 'r';
	      
	      if (r>1){
		  direction = 'c';
	      }
	      

	      // Get the cell's directional neighbours
	      cnumbers=getDirectionalNeighbours(neighbours[r],direction);
	      
	      // Test if it's part of a sequence (passing cell references in the order they appear in the table
	      seq = isPartOfSequence(cnumbers[0],neighbours[r],cnumbers[1]);
	      
	      if (seq[0] == true){
		  // We found a Fibonnaci like sequence!
		  // But, the rules (now) say each sequence must be > 3 cells, so we need to check for that
		  if (enforceFourWay(seq[3],direction)){
			colourSequenceMembers(seq[3]);
			selecs.push([neighbours[r],primes[i]]);
		  }
		  
		  
	      }else{
		  // Check the neighbours neighbours - just in case the prime is sat at the end of a sequence
		  nnumbers=getDirectionalNeighbours(cnumbers[0],direction);
		  seq = isPartOfSequence(nnumbers[0],cnumbers[0],nnumbers[1]);

		  if (seq[0] == true){
		      // We found a Fibonnaci like sequence!
		    
		      // Apply the 4 cell rule
		      if (enforceFourWay(seq[3],direction)){		    
			    colourSequenceMembers(seq[3]);
			    selecs.push([neighbours[r],primes[i]]);
		      }
		  }
		  
		  // And the other direction
		  nnumbers=getDirectionalNeighbours(cnumbers[1],direction);
		  seq = isPartOfSequence(nnumbers[0],cnumbers[1],nnumbers[1]);

		  if (seq[0] == true){
		      // We found a Fibonnaci like sequence!
		    
		      // Apply the 4 cell rule
		      if (enforceFourWay(seq[3],direction)){
			  colourSequenceMembers(seq[3]);
			  selecs.push([neighbours[r],primes[i]]);
		      }
		      
		  }
	      }
	      
	      
      
      }
      
}

// Work through and start calculating char codes
for (i=0; i<selecs.length; i++){
      ele = document.getElementById(selecs[i][0]);
      pele = document.getElementById(selecs[i][1]);
      ele.className='selected'; 
      pele.className = 'detectedPrime';
      
      prime=parseInt(pele.innerHTML);
      sno=parseInt(ele.innerHTML);
      computedchar = sno - prime;
      // Discard anything not resulting in a printable asci char
      if (computedchar > 127 || computedchar < 32){
	  continue;
      }

      // Numbers should be read left to right, so we need to get column number ready for sorting later
      ref = decodeReference(selecs[i][0]);
      
      ks.push(ref[1]);
      nums["c"+ref[1]] = computedchar;
}


// Sort the columns into Left -> Right order
ks.sort(sortNumber);

// Work through and print the characters in order
s='';

for (var i=0; i<ks.length; i++){
    s += String.fromCharCode(nums['c'+ks[i]]);
}


alert("Passphrase is: " +s);

 

Python


#!/usr/bin/env python
#
# Automatically solve puzzle-201604 and recover the password
#
# Pass the script any argument on the commandline to have it automatically decrypt the bounty
#
# (c) 2016 B Tasker
#

import requests, math,sys
from lxml import etree

primes = []
selecs = []
ks = {}
passphrase = []
pagecontent = False
column = 0

def fetchPage():
	''' Get the page contents
	'''
	global pagecontent
	if not pagecontent:
		r = requests.get("https://www.bentasker.co.uk/puzzles/puzzle-201604.html")
		Page = etree.HTML(r.content)
	return Page

def fetchPuzzle():
	''' Extract the puzzle table from the DOM
	'''
	tree = fetchPage()
	return tree.xpath('//table//tr')


def fetchFile():
	''' Get the bounty file from the DOM
	'''
	tree = fetchPage()
	return tree.xpath('//pre[@id="filecontents"]//text()')


def checkNumPrime(n):
	''' Check whether n is a prime number
	'''

	# Numbers less than 4 are all prime
	if n < 4:
		return True

	# Numbers divisible by 2 or 3 aren't prime
	if n%2 == 0 or n%3 == 0:
		return False

	# Create the seeds
	di=2
	i=5

	# Work out the square root of n (no need to check anything higher)
	lim = math.floor(math.sqrt(n))

	while i < lim:
		if n%i == 0:
			return False

		i=i+di
		di=6-di

	# If we got this far, didn't find a whole number. Number is prime
	return True



def getCellValueById(cellid):
	''' The equivalent of doing document.getElementById(cellid).innerHTML in JS
	'''
	global puzzletable
	return puzzletable[0].xpath('//tr//td[@id="'+cellid+'"]//text()')[0];


def decodeReference(cell):
	''' Break a cell ID into a dict containing row and column
	'''
	cell = cell[1:]
	return cell.split('c')


def calculateNeighbours(cell):
	''' Calculate the IDs of neighbouring cells
	'''
	if not cell:
		return False

	reference = decodeReference(cell)
	neighbours = []

	incr = int(reference[0]) +1
	incc = int(reference[1]) +1
	decr = int(reference[0]) - 1
	decc = int(reference[1]) - 1

	
	# Prevent negatives - we don't want to fall off the grid
	if decr >= 0:
		neighbours.append("r"+str(decr)+"c"+reference[1])
	else:
		neighbours.append(False)

	if incr < 20:
		neighbours.append("r"+str(incr)+"c"+reference[1])
	else:
		neighbours.append(False)

	if decc >= 0:
		neighbours.append("r"+reference[0]+"c"+str(decc))
	else:
		neighbours.append(False)

	if incc < 20:
		neighbours.append("r"+reference[0]+"c"+str(incc))
	else:
		neighbours.append(False)

	return neighbours


def getDirectionalNeighbours(cellid,direction):
	''' Get neighbours moving either longitudinally (c) or latidudally (r)
	'''

	# Shouldn't actually happen, but be safe
	if not cellid:
		return [False,False,False,False]

	neighbours = calculateNeighbours(cellid)
	dirneighbours = []
	if direction == "c":
		dirneighbours.append(neighbours[0])
		dirneighbours.append(neighbours[1])
	else:
		dirneighbours.append(neighbours[2])
		dirneighbours.append(neighbours[3])

	return dirneighbours


def isPartOfSequence(c1,c2,c3):
	''' Check whether cells form part of a sequence - Fn = Fn-1 + Fn-2
	'''
	if not c1 or not c3:
		return [False,False,False,[c1,c2,c3]]

	n1 = int(getCellValueById(c1))
	n2 = int(getCellValueById(c2))
	n3 = int(getCellValueById(c3))

	seq = False
	order = False
	cells = [c1,c2,c3]

	# Sequences can be asc or desc, test both

	if n1 + n2 == n3:
		seq = True
		order = 'asc'
	elif n1 - n2 == n3:
		seq = True
		order = 'desc'

	return [seq,True,order,cells]


def enforceFourWay(cells,direction):
	''' Enforce the four cell rule
	'''
	dnb = getDirectionalNeighbours(cells[0],direction)
	dseq = isPartOfSequence(dnb[0],cells[0],dnb[1])
	if not dseq[0]:
		# Check the other end of the sequence we found
		unb = getDirectionalNeighbours(cells[2],direction)
		return isPartOfSequence(unb[0],cells[2],unb[1])[0]

	# dseq found an additional
	return True
	

def asint(s):
	''' Stackoverflow poach - helps sort a dictionary numerically
	'''
	try: return int(s), ''
	except ValueError: return sys.maxint, s


def DecryptFile(pw):
	''' Take the recovered password and decrypt the bounty
	'''
	import tempfile,os
	from pipes import quote
	from subprocess import check_output

	filecontent=fetchFile()[0]
	tmphandle,tmpfile = tempfile.mkstemp()
	f = open(tmpfile,'w')
	f.write(filecontent)
	f.close()
	os.close(tmphandle)
	cmd = "openssl enc -aes-256-cbc -a -d -salt -k "+quote(pw)+" -in "+tmpfile
	output = check_output(cmd,shell=True)
	os.remove(tmpfile)
	return output



if __name__ == '__main__':
	try:
		if sys.argv[1]:
			decrypt=True
	except:
		decrypt=False


	puzzletable = fetchPuzzle()
	# Pick the primes out of the table by iterating over the cells
	while column < 20:
		row = 0
		while row < 20:
			cellref='r'+str(row)+'c'+str(column)
			if checkNumPrime(int(getCellValueById(cellref))):
				primes.append(cellref)
			row = row +1
		column = column + 1



	# Work over each prime and identify it's neighbour
	for prime in primes:
		neighbours = calculateNeighbours(prime)
		# Check neighbours for sequences
		for r,neighbour in enumerate(neighbours):
			if not neighbour:
				continue

			direction = "r"

			if r > 1:
				direction = "c"

			# Get the cells directional neighbours
			cnumbers = getDirectionalNeighbours(neighbour,direction)

			# Check for a sequence in those neighbours
			seq = isPartOfSequence(cnumbers[0],neighbour,cnumbers[1])
			if seq[0]:
				# We found a matching sequence, need to make sure there's >= 4 cells in the sequence
				if enforceFourWay(seq[3],direction):
					selecs.append([neighbour,prime])
			else:
				# Check the neighbour's neighbours - the prime might be sat on the last in a sequence
				nnumbers=getDirectionalNeighbours(cnumbers[0],direction)
				seq = isPartOfSequence(nnumbers[0],cnumbers[0],nnumbers[1])
				if seq[0]:
					# Fourway
					if enforceFourWay(seq[3],direction):
						selecs.append([neighbour,prime])

				# Now check in the other direction
				nnumbers=getDirectionalNeighbours(cnumbers[1],direction)
				seq = isPartOfSequence(nnumbers[0],cnumbers[1],nnumbers[1])
				if seq[0]:
					# Fourway
					if enforceFourWay(seq[3],direction):
						selecs.append([neighbour,prime])


	# Start calculating the char codes
	for select in selecs:
		ele = int(getCellValueById(select[0]))
		pele = int(getCellValueById(select[1]))

		computed = ele - pele
		# Skip non printable ASCII Char codes
		if computed > 127 or computed < 32:
			continue

		# Numbers need to be decoded left to right, so we still care about cell ids
		ref = decodeReference(select[0])
		ks[str(ref[1])] = computed


	# Sort into column order
	for key in sorted(ks,key=asint):
		passphrase.append(chr(ks[key]))


	pw = ''.join(passphrase)
	print "Password: "+pw

	if decrypt:
		print DecryptFile(pw)

 

 

 
 Share