[Lua] CryptoPals 1st attempt

matasano.lua

-- Matasano Crypto Challenge 
-- 
-- Jacob Gardner 2014 



-- Challenge 1 (Convert hex to base64) 
test1 = "49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d" 
real1 = "SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t" 

-- character table string 
local b ='ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/' 

-- encoding 
function toBase64(data) 
            return ((data:gsub('.', function(x) 
            local r,b='',x:byte() 
            for i=8,1,-1 do r=r..(b%2^i-b%2^(i-1)>0 and '1' or '0') end 
            return r; 
        end)..'0000'):gsub('%d%d%d?%d?%d?%d?', function(x) 
            if (#x < 6) then return '' end 
            local c=0 
            for i=1,6 do c=c+(x:sub(i,i)=='1' and 2^(6-i) or 0) end 
            return b:sub(c+1,c+1) 
        end)..({ '', '==', '=' })[#data%3+1]) 
end 

-- decoding 
function fromBase64(data) 
        data = string.gsub(data, '[^'..b..'=]', '') 
        return (data:gsub('.', function(x) 
            if (x == '=') then return '' end 
            local r,f='',(b:find(x)-1) 
            for i=6,1,-1 do r=r..(f%2^i-f%2^(i-1)>0 and '1' or '0') end 
            return r; 
        end):gsub('%d%d%d?%d?%d?%d?%d?%d?', function(x) 
            if (#x ~= 8) then return '' end 
            local c=0 
            for i=1,8 do c=c+(x:sub(i,i)=='1' and 2^(8-i) or 0) end 
            return string.char(c) 
        end)) 
end 

function toHex(str,spacer) 
   return ( 
   string.gsub(str,"(.)", 
   function (c) 
   return string.format("%02X%s",string.byte(c), spacer or "") 
   end) 
   ) 
end 

function fromHex(str) 
    return (str:gsub('..', function (cc) 
        return string.char(tonumber(cc, 16)) 
    end)) 
end 

function num2hex(num) 
   local hexstr = '0123456789abcdef' 
   local s = '' 
   while num > 0 do 
      local mod = math.fmod(num, 16) 
      s = string.sub(hexstr, mod+1, mod+1) .. s 
      num = math.floor(num / 16) 
   end 
   if s == '' then s = '0' end 
   return s 
end 

function toBin(num) 
   local t={} 
   num = tonumber(num) 
   while num>0 do 
      rest=num%2 
      table.insert(t,1,rest) 
      num=(num-rest)/2 
   end 
   return table.concat(t) 
end 

function fromBin(str) 
   return tonumber(str, 2) 
end 

-- Challenge 2 (Fixed XOR) 
test2a = "1c0111001f010100061a024b53535009181c" 
test2b = "686974207468652062756c6c277320657965" 
real2 = "746865206b696420646f6e277420706c6179" 

function fixedXor(a, b) 
   local out = "" 
   for i = 1, #a-1,2 do 
      a1 = string.sub(a,i,i+1) 
      b1 = string.sub(b,i,i+1) 
      a2 = string.byte(fromHex(a1)) 
      b2 = string.byte(fromHex(b1)) 
      --print(a,b,a2,b2,string.char(bxor(a2,b2))) 
      out = out .. string.char(bxor(a2,b2)) 
   end 
   return out 
end 

function bxor (a,b) 
   local r = 0 
   --for i = 0, 31 do 
   for i = 0, 7 do 
      local x = a / 2 + b / 2 
      if x ~= math.floor (x) then 
         r = r + 2^i 
      end 
      a = math.floor (a / 2) 
      b = math.floor (b / 2) 
   end 
   return r 
end 

-- Challenge 3 (Single Byte XOR Cipher) 
test3 = "1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736" 

function breakByteXor(str) 
   local table3 = {}                                 --store all results 
   local longest = 0                                 --length of longest result 
   local longestid = 0                              --id of longest result 
   local count = 0 

for i = 0, 255 do                        --try each key 
   count = 0 
   table3[i]=byteXor(str,i)      --save the results 
   --print(table3[i]) 
--if(str:match("%W")) then 
   --Improper characters detected. 
--else 
   for j = 1,#table3[i] do            --find longest one 
      --if string.byte(string.sub(table3[i],j,j)) > 47 then      --check for numbers 
      --   if string.byte(string.sub(table3[i],j,j)) < 58 then 
      --      count = count + 1 
      --   end 
      --end 
      if string.byte(string.sub(table3[i],j,j)) > 64 then      --check for uppercase letters 
         if string.byte(string.sub(table3[i],j,j)) < 91 then 
            count = count + 1 
         end 
      end 
       if string.byte(string.sub(table3[i],j,j)) > 96 then      --check for lowercase letters 
         if string.byte(string.sub(table3[i],j,j)) < 123 then 
            count = count + 2 
         end 
      end 
      if count > longest then 
         longest = count 
         longestid = i 
      end 
   end 
end 

return longestid, table3[longestid] 
end 

function byteXor(str,byte)      --loop through and xor test string by every possible byte 
   local out = "" 
   local temp = "" 
   for i = 1, #str,2 do 
      temp = temp .. string.char(byte) 
   end 
   --print(fixedXor(str,temp)) 
   --print(str,#str,toHex(temp),#toHex(temp)) 
   return(fixedXor(str,toHex(temp))) 
end 

-- Challenge 4 (Detect Single Byte XOR Cipher) 
file4 = io.input("/storage/emulated/0/Download/matasanoTest4.txt","r") 
test4 = file4:read("*all") 

-- find and break the 60 character string 
function detectByteXor(str) 
   local table4 = {} 
   local i = 0 
   local j = 0 
   local nextByte = 0 
   local chunk = "" 
   local key = 0 
   local plaintext = "" 
   local count = 0 
   local longest = 0 
   local longestid = 0 
   local second = 0 
   local third = 0 

   print('Brute Forcing. Please wait...') 

   repeat                  --step through each byte 
      i = i + 1 
      nextByte = string.sub(str,i,i) 
      --if nextByte == " " then 
      if(nextByte:match("%W")) then 
         --chunk = chunk .. nextByte 
         j=j+1 
         key, plaintext = breakByteXor(chunk) 
         table4[j] = plaintext 
         chunk = "" 
      else 
         chunk = chunk .. nextByte 
      end 
   until i == #str 
   --print(chunk) 
   print("number of possibilies: " .. j * 256) 
   for i = 1, j do 
      count = 0 
    for k = 1,#table4[i] do            --find longest one 

if string.byte(string.sub(table4[i],k,k)) > 47 then      --check for numbers 
         if string.byte(string.sub(table4[i],k,k)) < 58 then 
             count = count - 5 
         end 
      end 
      if string.byte(string.sub(table4[i],k,k)) > 64 then      --check for uppercase letters 
         if string.byte(string.sub(table4[i],k,k)) < 91 then 
            count = count + 5 
         end 
      end 
       if string.byte(string.sub(table4[i],k,k)) > 96 then      --check for lowercase letters 
         if string.byte(string.sub(table4[i],k,k)) < 123 then 
            count = count + 10 
         end 
      end 
      if string.byte(string.sub(table4[i],k,k)) < 48 then 
         if string.byte(string.sub(table4[i],k,k)) == 20 then   --check for space 
            count = count + 10 
         elseif string.byte(string.sub(table4[i],k,k)) == 10 then      --check for enter 
            count = count + 5 
         elseif string.byte(string.sub(table4[i],k,k)) == 13 then      --check for enter 
            count = count + 5 
         else 
            count = count - 5 
         end 
      end 
      if string.byte(string.sub(table4[i],k,k)) > 123 then 
         count = count - 5 
      end 
      if count > longest then 
         --debug 
         --print("               123456789012345678901234567890") 
         --print("New Candidate: " .. table4[i], #table4[i]) 
         longest = count 
         third = second 
         second = longestid 
         longestid = i 
      end 
   end 
   --print(table4[i]) 
   end 
   print("Probable Plaintext:  " .. table4[longestid]) 
   return table4[longestid] 
end 

--Challenge 5 (Repeating Key XOR Cipher) 
test5 = "Burning 'em, if you ain't quick and nimble\nI go crazy when I hear a cymbal" 

real5 = "0b3637272a2b2e63622c2e69692a23693a2a3c6324202d623d63343c2a26226324272765272a282b2f20430a652e2c652a3124333a653e2b2027630c692b20283165286326302e27282f " 

function repeatKey(str, len) 
   local temp = string.rep(str,(len / #str)+1) 
   return string.sub(toHex(temp),1,len*2) 
end 

--Challenge 6 (Break Repeating Key XOR) 
test6 = "HUIfTQsPAh9PE048GmllH0kcDk4TAQsHThsBFkU2AB4BSWQgVB0dQzNTTmVSBgBHVBwNRU0HBAxTEjwMHghJGgkRTxRMIRpHKwAFHUdZEQQJAGQmB1MANxYGDBoXQR0BUlQwXwAgEwoFR08SSAhFTmU+Fgk4RQYFCBpGB08fWXh+amI2DB0PQQ1IBlUaGwAdQnQEHgFJGgkRAlJ6f0kASDoAGhNJGk9FSA8dDVMEOgFSGQELQRMGAEwxX1NiFQYHCQdUCxdBFBZJeTM1CxsBBQ9GB08dTnhOSCdSBAcMRVhICEEATyBUCHQLHRlJAgAOFlwAUjBpZR9JAgJUAAELB04CEFMBJhAVTQIHAh9PG054MGk2UgoBCVQGBwlTTgIQUwg7EAYFSQ8PEE87ADpfRyscSWQzT1QCEFMaTwUWEXQMBk0PAg4DQ1JMPU4ALwtJDQhOFw0VVB1PDhxFXigLTRkBEgcKVVN4Tk9iBgELR1MdDAAAFwoFHww6Ql5NLgFBIg4cSTRWQWI1Bk9HKn47CE8BGwFTQjcEBx4MThUcDgYHKxpUKhdJGQZZVCFFVwcDBVMHMUV4LAcKQR0JUlk3TwAmHQdJEwATARNFTg5JFwQ5C15NHQYEGk94dzBDADsdHE4UVBUaDE5JTwgHRTkAUmc6AUETCgYAN1xGYlUKDxJTEUgsAA0ABwcXOwlSGQELQQcbE0c9GioWGgwcAgcHSAtPTgsAABY9C1VNCAINGxgXRHgwaWUfSQcJABkRRU8ZAUkDDTUWF01jOgkRTxVJKlZJJwFJHQYADUgRSAsWSR8KIgBSAAxOABoLUlQwW1RiGxpOCEtUYiROCk8gUwY1C1IJCAACEU8QRSxORTBSHQYGTlQJC1lOBAAXRTpCUh0FDxhUZXhzLFtHJ1JbTkoNVDEAQU4bARZFOwsXTRAPRlQYE042WwAuGxoaAk5UHAoAZCYdVBZ0ChQLSQMYVAcXQTwaUy1SBQsTAAAAAAAMCggHRSQJExRJGgkGAAdHMBoqER1JJ0dDFQZFRhsBAlMMIEUHHUkPDxBPH0EzXwArBkkdCFUaDEVHAQANU29lSEBAWk44G09fDXhxTi0RAk4ITlQbCk0LTx4cCjBFeCsGHEETAB1EeFZVIRlFTi4AGAEORU4CEFMXPBwfCBpOAAAdHUMxVVUxUmM9ElARGgZBAg4PAQQzDB4EGhoIFwoKUDFbTCsWBg0OTwEbRSonSARTBDpFFwsPCwIATxNOPBpUKhMdTh5PAUgGQQBPCxYRdG87TQoPD1QbE0s9GkFiFAUXR0cdGgkADwENUwg1DhdNAQsTVBgXVHYaKkg7TgNHTB0DAAA9DgQACjpFX0BJPQAZHB1OeE5PYjYMAg5MFQBFKjoHDAEAcxZSAwZOBREBC0k2HQxiKwYbR0MVBkVUHBZJBwp0DRMDDk5rNhoGACFVVWUeBU4MRREYRVQcFgAdQnQRHU0OCxVUAgsAK05ZLhdJZChWERpFQQALSRwTMRdeTRkcABcbG0M9Gk0jGQwdR1ARGgNFDRtJeSchEVIDBhpBHQlSWTdPBzAXSQ9HTBsJA0UcQUl5bw0KB0oFAkETCgYANlVXKhcbC0sAGgdFUAIOChZJdAsdTR0HDBFDUk43GkcrAAUdRyonBwpOTkJEUyo8RR8USSkOEENSSDdXRSAdDRdLAA0HEAAeHQYRBDYJC00MDxVUZSFQOV1IJwYdB0dXHRwNAA9PGgMKOwtTTSoBDBFPHU54W04mUhoPHgAdHEQAZGU/OjV6RSQMBwcNGA5SaTtfADsXGUJHWREYSQAnSARTBjsIGwNOTgkVHRYANFNLJ1IIThVIHQYKAGQmBwcKLAwRDB0HDxNPAU94Q083UhoaBkcTDRcAAgYCFkU1RQUEBwFBfjwdAChPTikBSR0TTwRIEVIXBgcURTULFk0OBxMYTwFUN0oAIQAQBwkHVGIzQQAGBR8EdCwRCEkHElQcF0w0U05lUggAAwANBxAAHgoGAwkxRRMfDE4DARYbTn8aKmUxCBsURVQfDVlOGwEWRTIXFwwCHUEVHRcAMlVDKRsHSUdMHQMAAC0dCAkcdCIeGAxOazkABEk2HQAjHA1OAFIbBxNJAEhJBxctDBwKSRoOVBwbTj8aQS4dBwlHKjUECQAaBxscEDMNUhkBC0ETBxdULFUAJQAGARFJGk9FVAYGGlMNMRcXTRoBDxNPeG43TQA7HRxJFUVUCQhBFAoNUwctRQYFDE43PT9SUDdJUydcSWRtcwANFVAHAU5TFjtFGgwbCkEYBhlFeFsABRcbAwZOVCYEWgdPYyARNRcGAQwKQRYWUlQwXwAgExoLFAAcARFUBwFOUwImCgcDDU5rIAcXUj0dU2IcBk4TUh0YFUkASEkcC3QIGwMMQkE9SB8AMk9TNlIOCxNUHQZCAAoAHh1FXjYCDBsFABkOBkk7FgALVQROD0EaDwxOSU8dGgI8EVIBAAUEVA5SRjlUQTYbCk5teRsdRVQcDhkDADBFHwhJAQ8XClJBNl4AC1IdBghVEwARABoHCAdFXjwdGEkDCBMHBgAwW1YnUgAaRyonB0VTGgoZUwE7EhxNCAAFVAMXTjwaTSdSEAESUlQNBFJOZU5LXHQMHE0EF0EABh9FeRp5LQdFTkAZREgMU04CEFMcMQQAQ0lkay0ABwcqXwA1FwgFAk4dBkIACA4aB0l0PD1MSQ8PEE87ADtbTmIGDAILAB0cRSo3ABwBRTYKFhROHUETCgZUMVQHYhoGGksABwdJAB0ASTpFNwQcTRoDBBgDUkksGioRHUkKCE5THEVCC08EEgF0BBwJSQoOGkgGADpfADETDU5tBzcJEFMLTx0bAHQJCx8ADRJUDRdMN1RHYgYGTi5jMURFeQEaSRAEOkURDAUCQRkKUmQ5XgBIKwYbQFIRSBVJGgwBGgtzRRNNDwcVWE8BT3hJVCcCSQwGQx9IBE4KTwwdASEXF01jIgQATwZIPRpXKwYKBkdEGwsRTxxDSToGMUlSCQZOFRwKUkQ5VEMnUh0BR0MBGgAAZDwGUwY7CBdNHB5BFwMdUz0aQSwWSQoITlMcRUILTxoCEDUXF01jNw4BTwVBNlRBYhAIGhNMEUgIRU5CRFMkOhwGBAQLTVQOHFkvUkUwF0lkbXkbHUVUBgAcFA0gRQYFCBpBPU8FQSsaVycTAkJHYhsRSQAXABxUFzFFFggICkEDHR1OPxoqER1JDQhNEUgKTkJPDAUAJhwQAg0XQRUBFgArU04lUh0GDlNUGwpOCU9jeTY1HFJARE4xGA4LACxSQTZSDxsJSw1ICFUdBgpTNjUcXk0OAUEDBxtUPRpCLQtFTgBPVB8NSRoKSREKLUUVAklkERgOCwAsUkE2Ug8bCUsNSAhVHQYKUyI7RQUFABoEVA0dWXQaRy1SHgYOVBFIB08XQ0kUCnRvPgwQTgUbGBwAOVREYhAGAQBJEUgETgpPGR8ELUUGBQgaQRIaHEshGk03AQANR1QdBAkAFwAcUwE9AFxNY2QxGA4LACxSQTZSDxsJSw1ICFUdBgpTJjsIF00GAE1ULB1NPRpPLF5JAgJUVAUAAAYKCAFFXjUeDBBOFRwOBgA+T04pC0kDElMdC0VXBgYdFkU2CgtNEAEUVBwTWXhTVG5SGg8eAB0cRSo+AwgKRSANExlJCBQaBAsANU9TKxFJL0dMHRwRTAtPBRwQMAAATQcBFlRlIkw5QwA2GggaR0YBBg5ZTgIcAAw3SVIaAQcVEU8QTyEaYy0fDE4ITlhIJk8DCkkcC3hFMQIEC0EbAVIqCFZBO1IdBgZUVA4QTgUWSR4QJwwRTWM=" 

function hamming(str1,str2) 
   local distance = 0 
   local a 
   local b 
   -- cannot calculate Hamming distance if strings have different sizes 
   if #str1 ~= #str2 then 
      --return false 
   end 
   for i = 1, #str1 do 
      if str1:sub(i,i) ~= str2:sub(i,i) then 
         --distance = distance + 1 
         a = str1:sub(i,i) 
         b = str2:sub(i,i) 
         --print(a,b) 
         distance = hamming2(toBin(string.byte(a)),toBin(string.byte(b)),distance) 
      end 
   end 
   return distance 
end 

function hamming2(str1,str2,distance) 
   --local distance = 0 
   local a 
   local b 
   -- cannot calculate Hamming distance if strings have different sizes 
   if #str1 ~= #str2 then 
      --return false 
   end 
   for i = 1, #str1 do 
      if str1:sub(i,i) ~= str2:sub(i,i) then 
         distance = distance + 1 
         --a = str1:sub(i,i) 
         --b = str2:sub(i,i) 
      end 
   end 
   return distance 
end 

function getKeySize(str) 
   local a,b 
   local smallest = 666 
   local id = 0 
   local max = #str/2 
   if max > 40 then 
      max = 40 
   end 
   for keysize = 2, max do 
      a = string.sub(str,1,keysize) 
      b = string.sub(str,keysize+1,keysize*2) 
      --print(a,b) 
      --print(keysize, hamming(a,b)/keysize) 
      if hamming(a,b)/keysize < smallest then 
         smallest = hamming(a,b)/keysize 
         id = keysize 
      end 
   end 
   return id 
end 

print(" Matasano Crypto Challenge") 

function wait() 
   print("\nPress Any Key to Continue\n") 
   sleep(5) 
end 

print("---------------------------\n") 
print("Test 1: Hex & Base64 Codecs") 
print("---------------------------") 
print("Hex input:      " .. test1) 
print("Hex Decoded:    " .. fromHex(test1)) 
print("Base64 Encoded: " .. toBase64(fromHex(test1))) 
--print("Expected:       " .. real1) 
wait() 

print("\nTest 2: Fixed XOR") 
print("---------------------------") 
print("A:        " .. test2a) 
print("B:        " .. test2b) 
print("A xor B = " .. toHex(fixedXor(test2a,test2b))) 
print("A xor B = " .. fixedXor(test2a,test2b)) 
--print("Expected: " .. fromHex(real2)) 
--print("Expected: " .. real2) 
wait() 

print("\nTest 3: Single Byte XOR Cipher") 
print("---------------------------") 
print("CipherText (HEX): " .. test3) 
--print("CipherText:       " .. fromHex(test3)) 
local key3, plain3 = breakByteXor(test3) 
print("Key:              " .. string.rep(key3,#test3/2) .. "\nPlainText:        " .. plain3) 
wait() 

print("\nTest 4: Break Single Byte XOR") 
print("---------------------------") 
print("Test input size:       " .. #test4) 
print("Test input:            " .. test4) 
print("Brute Forced:          " .. detectByteXor(test4)) 
wait() 

print("\nTest 5: Repeating-Key (Vignere) Cipher") 
print("---------------------------") 
print("Test input:  " .. test5) 
print("Hex Encoded: " .. toHex(test5)) 
key = repeatKey("ICE",#test5) 
print("Key:         " .. key) 
encrypted = toHex(fixedXor(toHex(test5),key)) 
print("Encrypted:   " .. encrypted) 
decrypted = toHex(fixedXor(encrypted,key)) 
print("Decrypted:   " .. decrypted) 
--print("Expected:    " .. string.upper(real5)) 
wait() 

print("\nTest 6: Break Vignere Cipher") 
print("--------------------------") 
print("Test input:       " .. test6) 
print("\nProbable Keysize: " .. getKeySize(fromBase64(test6))) 
key6= repeatKey("badass!",#fromBase64(test6)) 
decrypted = fixedXor(toHex(fromBase64(test6)),key6) 
print("Decrypted: " .. decrypted)