Advent of Code 2016 Day14: One-Time Pad

This is a series of programming challenges for beginners and experienced Caché programmers.

For an introduction : go to article https://community.intersystems.com/post/advent-code-2016-day1-no-time-ta...

The challenge today is about some basic cryptography : you will have to generate data for a one-time pad (OTP) (see https://en.wikipedia.org/wiki/One-time_pad for more info).

You need to generate keys by taking the MD5 of a pre-arranged salt (your puzzle input), and an increasing integer index starting with 0.

Only those keys are valid which have :

- three the same characters in a row (consider only the first triplet), e.g. 8b16a3fff478a85de22947a1686a0e1d
- one of the next 1000 hashes has that same character 5 times in a row

For more in depth instructions and examples, go to http://adventofcode.com/2016/day/14, it will also include your puzzle input.

The code I wrote  to solve this challenge is pretty much straightforward : 

• loop from index 0 onwards:
  • calculate a MD5 hash with the salt and the index
  • if you can locate a triplet
    •  calculate MD5 hash for the next 1000 indexes until:
      •  if such a new hash has the character five times, consider the original hash as a good key
  •   stop and output the index when you reached the 64th valid key

Class AOC2016.Day14
{

ClassMethod Part(part As %Integer = 1)
{
  #Dim salt as %String = "cuanljph"  //my input
  #Dim index, nextIndex as %Integer
  #Dim hash, hash2, hashes, triplet, fivelet as %String
  #Dim countKey as %Integer = 0
  #Dim okKey as %Boolean
  Set hashes = $Select(part=1:1, 1:2017)  //part2 of the challenge : key stretch index 2017 times
  Kill %hash  //store calculated hashes in a public var, so we don't have to pass them to all methods as param
  Try {
    For index = 0:1 {
      Set hash = ..GetMD5(salt_index,hashes)
      If $Locate(hash,"(.)\1\1",,,triplet) {  //regex: 3 the same characters
        Set okKey = 0
        Set fivelet=$E(triplet_triplet,1,5)
        For nextIndex=1:1:1000 {
          Set hash2 = ..GetMD5(salt_(index+nextIndex),hashes)
          If $Find(hash2,fivelet) {
            Set okKey = 1
            Quit
          }
        }
        If okKey {
          Set countKey=countKey+1
          write countKey," ",index," : ",hash,!
          If countKey = 64 Quit
        }
      }
    }
    Write "Index = ",index,!
  } Catch {
    Write "Error : ",$ZError,!
  }
}

ClassMethod GetMD5(s, hashes) As %String
{
  #Dim hash as %String
  #Dim iHash as %Integer

  If $data(%hash(s)) quit %hash(s)
  Set hash = s
  For iHash=1:1:hashes {  //if hashes>1 : strech key (for part2)
    set hash = ..StrToHex($system.Encryption.MD5Hash(hash))
  }
  set %hash(s)=hash
  quit hash
}

ClassMethod StrToHex(str As %String) As %String
{
  #Dim hex as %String = ""
  #Dim hex1 as %String
  #Dim iStr as %Integer
  For iStr=1:1:$Length(str) {
    Set hex1 = $ZHex($Ascii(str,iStr))
    If $Length(hex1)=1 set hex1="0"_hex1
    Set hex = hex _ hex1
  }
  Quit $ZConvert(hex,"l")
}

}

After unlocking, the second challenge is stretching the cryptography a bit further by asking for key stretching the MD5 key  (see https://en.wikipedia.org/wiki/Key_stretching for more info).

You will have to generate a MD5 hash 2017 times (first calculate md5 hash on salt+index, than take the MD5 of that result, and so on)

If you only change your code to calculate your hash in a 2017 times loop, your machine will be steaming after a while. Since the same salt_index has to be hashed different times, I store each calculated hash so we only have to calculate each hash once. 

Actually, the code above did all that already, so here is the code that Bert wrote for this challenge :

Start2() PUBLIC {
  s input="qzyelonm"
  s i=1
  s found=0
  s isBusy=1
  while isBusy {
    s hash=$ZCONVERT($$getMD5Hash(input_i),"L")
    for j=1:1:2016 {
      s hash=$ZCONVERT($$getMD5Hash(hash),"L")
    }
    s search=$ORDER(toFind(""),1,quintet)
    while search'="" {
      if ((search+1000)>=i) {
        if hash[quintet {
          s found=found+1
          s found(search)=""
        }
      } else {
        k toFind(search)
      }
      s search=$ORDER(toFind(search),1,quintet)
    }
    s x = $$getFirstTriple(hash)
    if x'="" {
      s toFind(i)=x_$EXTRACT(x)_$EXTRACT(x)
    }
    if found>=70 {
      s isBusy=0
    } else {
      s i=i+1
    }
  }
  s count=1
  s struct=$ORDER(found(""))
  while struct'="" {
    if count=64 {
      w !,"nr 64 = ",struct
    }
    s count=count+1
    s struct=$ORDER(found(struct))
  }
}

getMD5Hash(String) {
  s result=""
  s hash=##class(%SYSTEM.Encryption).MD5Hash(String)
  f i=1:1:$LENGTH(hash) {
    s add=$ZHEX($ASCII($EXTRACT(hash,i)))
    if $LENGTH(add)=1 {
      s add="0"_add
    }
    s result=result_add
  }
  q result
}

getFirstTriple(Hash) {
  s result=""
  s i=1
  while (result="") && (i<($LENGTH(Hash)-1)) {
    if ($EXTRACT(Hash,i)=$EXTRACT(Hash,i+1)) && ($EXTRACT(Hash,i)=$EXTRACT(Hash,i+2)) {
      s result=$EXTRACT(Hash,i,i+2)
    }
    s i=i+1
  }
  q result
}

 

Look here for all our solutions so far : https://bitbucket.org/bertsarens/advent2016 and https://github.com/DannyWijnschenk/AdventOfCode2016

 

Here is the list of all Advent of Code 2016 articles  :

1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25