Crypto nonsense



  • This is only sort of moderately serious, since I'm just doing this for fun pretty much, but I was trying these crypto challenges, and one of the rules was to work with the raw bytes, so I thought I'd just roll my own everything.

    The first challenge was to take a hex string, and convert it to base64. I'm probably doing like 5 things wrong here, since a character in C# is specifically not ascii, but:

    	static void Main(string[] args)
    	{
    		var beginning = "49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d";
    		var bytes = beginning.Select(CharToByte);
    		var bits = bytes.SelectMany(ExtractBits);
    		int i = 0;
    		var chars = bits.GroupBy(x => i++/6).Select(group => group.ToArray());
    		var finalCharacters = chars.Select(GetChar);
    		var actual = new string(finalCharacters.ToArray());
    		var expected = "SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t";
    		if (actual != expected)
    			throw new Exception();
    	}
    
    	private static bool[] ExtractBits(byte arg)
    	{
    		var bits = new bool[8];
    		for (int i = 7; arg != 0; i--)
    		{
    			var max = Convert.ToByte(Math.Pow(2, i));
    			if (arg >= max)
    			{
    				arg -= max;
    				bits[i] = true;
    			}
    		}
    		return bits;
    	}
    
    	private static byte CharToByte(char arg)
    	{
    		switch (arg)
    		{
    			case '0':
    				return 0;
    			case '1':
    				return 1;
    			case '2':
    				return 2;
    			case '3':
    				return 3;
    			case '4':
    				return 4;
    			case '5':
    				return 5;
    			case '6':
    				return 6;
    			case '7':
    				return 7;
    			case '8':
    				return 8;
    			case '9':
    				return 9;
    			case 'a':
    			case 'A':
    				return 10;
    			case 'b':
    			case 'B':
    				return 11;
    			case 'c':
    			case 'C':
    				return 12;
    			case 'd':
    			case 'D':
    				return 13;
    			case 'e':
    			case 'E':
    				return 14;
    			case 'f':
    			case 'F':
    				return 15;
    			default:
    				throw new ArgumentException("The provided character is not within the range of hexidecimal values.");
    		}
    	}
    
    	private static char GetChar(bool[] bits)
    	{
    		var value = bits.Select((bit, i) => bit ? (byte)Math.Pow(2, i) : 0).Sum();
    		return (char)value;
    	}
    }
    

    I always get random bells and things rather than the expected, and I iz noob. What obvious things did I miss? Is it all just the groupby?

    EDIT: Fixed a dumb bug.
    EDIT: And another.



  • @Magus said:

    The first challenge was to take a hex string, and convert it to base64.

    var ba = BigInteger.Parse(str, NumberStyles.HexNumber).ToByteArray();
    ba.Reverse(); //little endian
    var result = Convert.ToBase64String(ba);
    

    Or something like that, haven't tested it, but WTF you're doing here can probably be summed up in three lines or less.



  • No, I know full well that that's the correct way. That isn't the challenge. This isn't production code. I'm following the rules.



  • Which Base64? I'm assuming RFC 4648, which is the current version AFAICT, so I would start by skimming through that.



  • Here's what I know about base64: You take a thing, you put it in binary, and you convert each six bits to a character. Or so Wikipedia told me. This is what I've tried to do, but I'm sure I have something horribly wrong.



  • Maybe if I use the table wikipedia provides... That seems a bit messed up, though...



  • Well, yeah, that's pretty much the thing to do, for that part anyway. I recommend using an array as a lookup table.



  • So, I made an awful switch, and it gives me something that looks sufficiently insane. It just isn't the right thing.

    EkgAHYQDCAgBLYQCGwgBMYQCG4gBHIAAHkgBPcQBHIgAAYgAHIgBBYQCG4gAAYADGkgBLYQBCAgBBIAAHAgBPYQCHMgBPYgDG8wBFcwACAgBNcQBHMgBIcgAG8gBPYQD

    It's also longer than the expected, which is somehow shorter than the original, despite being a character every 6 bits instead of every 8. I don't get it.



  • FAIL. Right, so: A hex character is half a byte. I was making each one a byte. No wonder it's all messed up.


  • Winner of the 2016 Presidential Election

    @Magus said:

    It's also longer than the expected, which is somehow shorter than the original

    Which one do you mean by "original"? Because if you mean beginning, and I've understood enough of what you said right, than I think you forgot that hex is a character every four bits, not eight.

    EDIT: got :hanzo:d by @Magus and :hanzo:d @ScholRLEA at the same time. Any chance there's a :badger: for that?



  • A byte requires a 2-character representation in hex. You're conversion is wrong anyway, for the same reason,



  • Sorry, hit reply too early, twice in a row, which makes me feel like an idiot.

    Anyway. as I was about to say, you need to convert the whole hex value (both characters) to get the whole value you need. Fortunately, there's a general algorithm for converting base representations, a Python implementation of which can be found here (the function named value_to_base()).

    EDIT: Ack, that's not the algorithm I had in mind! Give me a minute...



  • Here is a working, but not especially efficient, algorithm for the conversion; if you need any explanations, just ask.

    def str2int(s, base):
        """ 
        A simple function for converting a string in any base 2..16 to an integer representation 
        """
    
        # Define a mapping of the characters to the values.
        # You can use a Dictionary<string, byte> in C# for a direct translation.
        # There are simpler ways to do this, but this approach works 
        # for all encodings of the Latin alphabet and Arabic numerals.
        digits = {
                  '0':0, '1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, 
                  '9':9, 'A':0xA, 'B':0xB, 'C':0xC, 'D':0xD, 'E':0xE, 'F':0xF
                 }
    
        # check for the end of the string, or a null string
        if s is None or len(s) == 0:
           return 0
    
        charValue = s[0].upper()   # convert any alphas to uppercase
    
        # lookup the values for the character in the mapping's keys
        if charValue in digits.keys():
            # digitValue is the value of the current significant digit in the base,
            # shift is the current significant digit (column place) in the number
            # partialValue is the digit put into the correct significant digit,
            # the return value is partialValue plus the value of the remaining 
            # substring, computed recursively
            # For example, for s = '1234', base = 10, the first significant digit 
            # (digitValue * the base raised to the total string length minus 1) 
            # is the thousandths place, so partialValue = 1000. This is added
            # successively as 1000 + 200 + 30 + 4 to get 1234.
            digitValue = digits[charValue]
            shift =  base ** (len(s) - 1)
            partialValue = digitValue * shift
            return  partialValue + str2int(s[1:], base) 
        else:
            # if the string finds a character not in the map, assume it is the end of the value
            return 0
    


  • See, again, what I'm looking for isn't really the algorithm itself. I'm trying to complete a challenge. I'm looking for bugs in what I'm doing.

    I redid some things, and ended up with this, which is much closer:

    static void Main(string[] args)
    {
    	var beginning = "49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d";
    	var bits = beginning.SelectMany(ExtractBits);
    	int i = 0;
    	var chars = bits.GroupBy(x => i++/6).Select(group => group.ToArray());
    	var finalCharacters = chars.Select(GetChar);
    	var actual = new string(finalCharacters.ToArray());
    	var expected = "SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t";
    	if (actual != expected)
    		throw new Exception();
    }
    
    private static bool[] ExtractBits(char arg)
    {
    	switch (arg)
    	{
    		case '0':
    			return new[] { false, false, false, false };
    		case '1':
    			return new[] { false, false, false, true };
    		case '2':
    			return new[] { false, false, true, false };
    		case '3':
    			return new[] { false, false, true, true };
    		case '4':
    			return new[] { false, true, false, false };
    		case '5':
    			return new[] { false, true, false, true };
    		case '6':
    			return new[] { false, true, true, false };
    		case '7':
    			return new[] { false, true, true, true };
    		case '8':
    			return new[] { true, false, false, false };
    		case '9':
    			return new[] { true, false, false, true };
    		case 'a':
    		case 'A':
    			return new[] { true, false, true, false };
    		case 'b':
    		case 'B':
    			return new[] { true, false, true, true };
    		case 'c':
    		case 'C':
    			return new[] { true, true, false, false };
    		case 'd':
    		case 'D':
    			return new[] { true, true, false, true };
    		case 'e':
    		case 'E':
    			return new[] { true, true, true, false };
    		case 'f':
    		case 'F':
    			return new[] { true, true, true, true };
    		default:
    			throw new ArgumentException("The provided character is not within the range of hexidecimal values.");
    	}
    }
    
    private static char GetChar(bool[] bits)
    {
    	var value = bits.Select((bit, i) => bit ? (byte)Math.Pow(2, i) : 0).Sum();
    	//return (char)value;
    	switch (value)
    	{
    		case 0:
    			return 'A';
    		case 1:
    			return 'B';
    		case 2:
    			return 'C';
    		case 3:
    			return 'D';
    		case 4:
    			return 'E';
    		case 5:
    			return 'F';
    		case 6:
    			return 'G';
    		case 7:
    			return 'H';
    		case 8:
    			return 'I';
    		case 9:
    			return 'J';
    		case 10:
    			return 'K';
    		case 11:
    			return 'L';
    		case 12:
    			return 'M';
    		case 13:
    			return 'N';
    		case 14:
    			return 'O';
    		case 15:
    			return 'P';
    		case 16:
    			return 'Q';
    		case 17:
    			return 'R';
    		case 18:
    			return 'S';
    		case 19:
    			return 'T';
    		case 20:
    			return 'U';
    		case 21:
    			return 'V';
    		case 22:
    			return 'W';
    		case 23:
    			return 'X';
    		case 24:
    			return 'Y';
    		case 25:
    			return 'Z';
    		case 26:
    			return 'a';
    		case 27:
    			return 'b';
    		case 28:
    			return 'c';
    		case 29:
    			return 'd';
    		case 30:
    			return 'e';
    		case 31:
    			return 'f';
    		case 32:
    			return 'g';
    		case 33:
    			return 'h';
    		case 34:
    			return 'i';
    		case 35:
    			return 'j';
    		case 36:
    			return 'k';
    		case 37:
    			return 'l';
    		case 38:
    			return 'm';
    		case 39:
    			return 'n';
    		case 40:
    			return 'o';
    		case 41:
    			return 'p';
    		case 42:
    			return 'q';
    		case 43:
    			return 'r';
    		case 44:
    			return 's';
    		case 45:
    			return 't';
    		case 46:
    			return 'u';
    		case 47:
    			return 'v';
    		case 48:
    			return 'w';
    		case 49:
    			return 'x';
    		case 50:
    			return 'y';
    		case 51:
    			return 'z';
    		case 52:
    			return '0';
    		case 53:
    			return '1';
    		case 54:
    			return '2';
    		case 55:
    			return '3';
    		case 56:
    			return '4';
    		case 57:
    			return '5';
    		case 58:
    			return '6';
    		case 59:
    			return '7';
    		case 60:
    			return '8';
    		case 61:
    			return '9';
    		case 62:
    			return '+';
    		case 63:
    			return '/';
    		default:
    			return '=';
    	}
    }
    

    Even so, my actual result is:

    SSutEYtl2Yjl2ZOBeavrORgROZol2RgNWatpEYIBOYvlObvd27qzEYrrObhT2bvt // Actual
    SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t // Expected
    

    The length is right, and some of the characters are too. I probably have some minor mistake somewhere.



  • It looks like it's the bit order. Looking at the beginning of your two strings, S and t match, which are 18 and 45, and their binary representations are palindromes (010010 and 101101 respectively). Lowercase u (46, 101110) is the reverse of lowercase d (29 = 011101). I'd be surprised if this doesn't hold for the rest.



  • Ah! Sweet! I'll see if that does it.

    Thanks!

    EDIT: It worked!

    static void Main(string[] args)
    {
    	var beginning = "49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d";
    	var bits = beginning.SelectMany(ExtractBits);
    	int i = 0;
    	var chars = bits.GroupBy(x => i++/6).Select(group => group.ToArray());
    	var finalCharacters = chars.Select(GetChar);
    	var actual = new string(finalCharacters.ToArray());
    	var expected = "SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t";
    	if (actual != expected)
    		throw new Exception();
    }
    
    private static bool[] ExtractBits(char arg)
    {
    	switch (arg)
    	{
    		case '0':
    			return new[] { false, false, false, false };
    		case '1':
    			return new[] { false, false, false, true };
    		case '2':
    			return new[] { false, false, true, false };
    		case '3':
    			return new[] { false, false, true, true };
    		case '4':
    			return new[] { false, true, false, false };
    		case '5':
    			return new[] { false, true, false, true };
    		case '6':
    			return new[] { false, true, true, false };
    		case '7':
    			return new[] { false, true, true, true };
    		case '8':
    			return new[] { true, false, false, false };
    		case '9':
    			return new[] { true, false, false, true };
    		case 'a':
    		case 'A':
    			return new[] { true, false, true, false };
    		case 'b':
    		case 'B':
    			return new[] { true, false, true, true };
    		case 'c':
    		case 'C':
    			return new[] { true, true, false, false };
    		case 'd':
    		case 'D':
    			return new[] { true, true, false, true };
    		case 'e':
    		case 'E':
    			return new[] { true, true, true, false };
    		case 'f':
    		case 'F':
    			return new[] { true, true, true, true };
    		default:
    			throw new ArgumentException("The provided character is not within the range of hexidecimal values.");
    	}
    }
    
    private static char GetChar(bool[] bits)
    {
    	var rev = bits.Reverse();
    	var value = rev.Select((bit, i) => bit ? (byte)Math.Pow(2, i) : 0).Sum();
    	//return (char)value;
    	switch (value)
    	{
    		case 0:
    			return 'A';
    		case 1:
    			return 'B';
    		case 2:
    			return 'C';
    		case 3:
    			return 'D';
    		case 4:
    			return 'E';
    		case 5:
    			return 'F';
    		case 6:
    			return 'G';
    		case 7:
    			return 'H';
    		case 8:
    			return 'I';
    		case 9:
    			return 'J';
    		case 10:
    			return 'K';
    		case 11:
    			return 'L';
    		case 12:
    			return 'M';
    		case 13:
    			return 'N';
    		case 14:
    			return 'O';
    		case 15:
    			return 'P';
    		case 16:
    			return 'Q';
    		case 17:
    			return 'R';
    		case 18:
    			return 'S';
    		case 19:
    			return 'T';
    		case 20:
    			return 'U';
    		case 21:
    			return 'V';
    		case 22:
    			return 'W';
    		case 23:
    			return 'X';
    		case 24:
    			return 'Y';
    		case 25:
    			return 'Z';
    		case 26:
    			return 'a';
    		case 27:
    			return 'b';
    		case 28:
    			return 'c';
    		case 29:
    			return 'd';
    		case 30:
    			return 'e';
    		case 31:
    			return 'f';
    		case 32:
    			return 'g';
    		case 33:
    			return 'h';
    		case 34:
    			return 'i';
    		case 35:
    			return 'j';
    		case 36:
    			return 'k';
    		case 37:
    			return 'l';
    		case 38:
    			return 'm';
    		case 39:
    			return 'n';
    		case 40:
    			return 'o';
    		case 41:
    			return 'p';
    		case 42:
    			return 'q';
    		case 43:
    			return 'r';
    		case 44:
    			return 's';
    		case 45:
    			return 't';
    		case 46:
    			return 'u';
    		case 47:
    			return 'v';
    		case 48:
    			return 'w';
    		case 49:
    			return 'x';
    		case 50:
    			return 'y';
    		case 51:
    			return 'z';
    		case 52:
    			return '0';
    		case 53:
    			return '1';
    		case 54:
    			return '2';
    		case 55:
    			return '3';
    		case 56:
    			return '4';
    		case 57:
    			return '5';
    		case 58:
    			return '6';
    		case 59:
    			return '7';
    		case 60:
    			return '8';
    		case 61:
    			return '9';
    		case 62:
    			return '+';
    		case 63:
    			return '/';
    		default:
    			return '=';
    	}
    }


  • Glad I could help.

    Have we always had the Solution feature? I don't think I've seen it before.



  • Nah, we got it a week or two ago, and it only applies to help sections.


Log in to reply