Java – problem converting Base64 string to hexadecimal string
TLDR:
I recently decided to try Matasano crypto challenges, but for whatever reason, I decided to try to write the first challenge instead of using the library to convert hex and Base64 strings
I have tried to make the hex to Base64 conversion work, but from the output, I can see that there will be a slight exception when I try to convert Base64 back to hex (for example, compare the last four values of Base64 with the hex output)
I use https://conv.darkbyte.ru/ To check some of my values and assume that the code on the site is correct. It seems that my problem is to get the base10 representation from Base64, not from base10 to hex:
It seems that all values with errors are clustered between 40-60 and 100-120, but I'm not sure where to go from there I guess there are some marginal situations I will pay attention to, but I'm not sure what it will be
Relevant codes:
private static final Character[] base64Order = new Character[] { 'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','0','1','2','3','4','5','6','7','8','9','+','/',}; private static final Character[] hexOrder = new Character[] { '0','f' }; public static String base64ToHex(String base64) throws Exception { if (base64.length() % 4 != 0 || base64.contains("[^a-zA-Z0-9\\+/]")) throw new Exception("InputNotBase64"); else { int charValue = 0; int index = 0; String hex = ""; BitSet bits = new BitSet(); for (int i = 0; i < base64.length(); i++) { charValue = base64.charAt(i); // get actual value from ASCII table if (charValue > 64 && charValue < 91) charValue -= 65; if (charValue > 96 && charValue < 123) charValue -= 71; /// loop that adds to the BitSet reads right-to-left,so reverse // the bits and then shift charValue = Integer.reverse(charValue << 24) & 0xff; charValue >>= 2; // append binary values to the BitSet while (charValue != 0L) { if (charValue % 2 != 0) { bits.set(index); } index++; charValue >>= 1; } // account for trailing 0s while (index % 6 != 0) { index++; } } // read 8-bit integer value for hex-value lookup String temp; int remainder; for (int i = 0; i < index; i++) { charValue = (charValue | (bits.get(i) ? 1 : 0)); if ((i + 1) % 8 == 0) { temp = ""; while (charValue != 0L) { remainder = charValue % 16; temp = hexOrder[remainder] + temp; charValue /= 16; } hex += temp; } charValue <<= 1; } return hex; } }
Solution
You forgot to process the following characters in your code: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '2', '3', '/'
if (charValue > 64 && charValue < 91) charValue -= 65; if (charValue > 96 && charValue < 123) charValue -= 71;
adopt
charValue = getPositionInBase64(charValue);
where?
public static int getPositionInBase64(int n) { for (int p = 0; p < base64Order.length; p++) { if (n == base64Order[p]) { return p; } } return -1; }
business as usual
In addition, the code is easier to read when you use characters instead of magic numbers
if (charValue >= 'A' && charValue <= 'Z') charValue -= 'A'; ...
In this case, it is easier to find problems
Because you asked me, I'm proposing possible improvements to speed up the calculation
Prepare the following table and initialize it once
// index = character,value = index of character from base64Order private static final int[] base64ToInt = new int[128]; public static void initBase64ToIntTable() { for (int i = 0; i < base64Order.length; i++) { base64ToInt[base64Order[i]] = i; } }
Now you can replace your if / else chain with a simple operation
charValue = base64ToInt[base64.charAt(i)];
Using this, my method is several times faster than yours
private static String intToHex(int n) { return String.valueOf(new char[] { hexOrder[n/16],hexOrder[n%16] }); } public static String base64ToHexVer2(String base64) throws Exception { StringBuilder hex = new StringBuilder(base64.length()*3/4); //capacity Could be 3/4 of base64 string length if (base64.length() % 4 != 0 || base64.contains("[^a-zA-Z0-9\\+/]")) { throw new Exception("InputNotBase64"); } else { for (int i = 0; i < base64.length(); i += 4) { int n0 = base64ToInt[base64.charAt(i)]; int n1 = base64ToInt[base64.charAt(i+1)]; int n2 = base64ToInt[base64.charAt(i+2)]; int n3 = base64ToInt[base64.charAt(i+3)]; // in descriptions I treat all 64 base chars as 6 bit // all 6 bites from 0 and 1st 2 from 1st (00000011 ........ ........) hex.append(intToHex(n0*4 + n1/16)); // last 4 bites from 1st and first 4 from 2nd (........ 11112222 ........) hex.append(intToHex((n1%16)*16 + n2/4)); // last 2 bites from 2nd and all from 3rd (........ ........ 22333333) hex.append(intToHex((n2%4)*64 + n3)); } } return hex.toString(); }
I think this code is faster, mainly because it is simply converted to hexadecimal If you want and need it, you can test it
To test speed, you can use the following constructs
String b64 = "SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t"; try { Base64ToHex.initBase64ToIntTable(); System.out.println(Base64ToHex.base64ToHex(b64)); System.out.println(Base64ToHex.base64ToHexVer2(b64)); int howManyIterations = 100000; Date start,stop; long period; start = new Date(); for (int i = 0; i < howManyIterations; i++) { Base64ToHex.base64ToHexVer2(b64); } stop = new Date(); period = stop.getTime() - start.getTime(); System.out.println("Ver2 taken " + period + " ms"); start = new Date(); for (int i = 0; i < howManyIterations; i++) { Base64ToHex.base64ToHex(b64); } stop = new Date(); period = stop.getTime() - start.getTime(); System.out.println("Ver1 taken " + period + " ms"); } catch (Exception ex) { }
The example result is
49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d 49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d Ver2 taken 300 ms Ver1 taken 2080 ms
But it is only an approximation When you check ver1 first and ver2 second, the result may be slightly different In addition, the results may be different for different Javas (sections 6, 7, 8) and different settings for starting Java