Pattern Cracking Question
-
NOTE: Please let me know if another section/forum on the site is more appropriate for this question. I'm trying to solve an algorithm puzzle and I was hoping to get some help. Its not for any formal study, just a mind exercise/ puzzle but I've hit a road block: The goal is to figure out what algorithm or formula can be used to decrypt and encrypted string of characters where you know the characters being encrypted and what their encrypted value is but not how the encrypted value is determined. Obviously this would be like looking for a needle in a haystack except that there are some parameters to this that help (I think) narrow the process down. I can't help but think there's got to be a pattermn or method for figuring out something like this when you know the values of both the unencrypted character and what it encrypts to. The parameters of the puzzle are: 1) The encrypted characters are limited to the printiable set of characters within the standard 256 character ASCII set of characters (basically what's on a standard US keyboard). I suppose the thing woiuld work with non-visible charactres but I believe the intent is to use any of the keyboard characters a user could use and so that would include numbers, letters and some of the special characters too. 2) the string of characters to encrypt is limited to 12. 3) Each single character is encrypted to a 2 character value (I think it's always a number but I'm not certain ) so that a string of 12 characters will be encrypted to a 24 character long value. 4) Each character is encrypted to the exact same value based on its position in the string of characters to be encrypted. For example if the text to encrypt is abcdefga1234 then the lower case a is encrypted to the value 57 for position 01 in this string of 12 characters and in the 8th position the lower case a is encrypted to a value of 0A. No matter what combination of characters are in positions 1 thru 7, the lowercase a will always been encrypted as 0A when it is in the 8th position in the string of characters. 5) Each combination of characters plus position has a unique encrypted value and that value is constant when the position of the character is the same. I hope the last 2 above make sense; it's hard to convey these in words. I know that a large lookup table of characters along with their decrypted values and position could be sued to decrypt an encrypted string but unfortunately that’s not the answer to the puzzle. The goal is to decipher wh
-
NOTE: Please let me know if another section/forum on the site is more appropriate for this question. I'm trying to solve an algorithm puzzle and I was hoping to get some help. Its not for any formal study, just a mind exercise/ puzzle but I've hit a road block: The goal is to figure out what algorithm or formula can be used to decrypt and encrypted string of characters where you know the characters being encrypted and what their encrypted value is but not how the encrypted value is determined. Obviously this would be like looking for a needle in a haystack except that there are some parameters to this that help (I think) narrow the process down. I can't help but think there's got to be a pattermn or method for figuring out something like this when you know the values of both the unencrypted character and what it encrypts to. The parameters of the puzzle are: 1) The encrypted characters are limited to the printiable set of characters within the standard 256 character ASCII set of characters (basically what's on a standard US keyboard). I suppose the thing woiuld work with non-visible charactres but I believe the intent is to use any of the keyboard characters a user could use and so that would include numbers, letters and some of the special characters too. 2) the string of characters to encrypt is limited to 12. 3) Each single character is encrypted to a 2 character value (I think it's always a number but I'm not certain ) so that a string of 12 characters will be encrypted to a 24 character long value. 4) Each character is encrypted to the exact same value based on its position in the string of characters to be encrypted. For example if the text to encrypt is abcdefga1234 then the lower case a is encrypted to the value 57 for position 01 in this string of 12 characters and in the 8th position the lower case a is encrypted to a value of 0A. No matter what combination of characters are in positions 1 thru 7, the lowercase a will always been encrypted as 0A when it is in the 8th position in the string of characters. 5) Each combination of characters plus position has a unique encrypted value and that value is constant when the position of the character is the same. I hope the last 2 above make sense; it's hard to convey these in words. I know that a large lookup table of characters along with their decrypted values and position could be sued to decrypt an encrypted string but unfortunately that’s not the answer to the puzzle. The goal is to decipher wh
Ok let's see if I can come up with something, sounds fun! :) The hints we can gather from the given puzzle parameters are: 1) It seems we're talking ASCII characters, one byte per character and a well-known codification. 2) A maximum length of 12 chars, ok. 3) Putting together this with what I see in point 4, it seems the encrypted 2-character data seems to represent a byte value in hex (examples are "57" an "0A", both valid hex byte values). 4) So, the character position in the input string is the second variable to take into account (the first is the character ASCII code itself, see point 1). 5) This confirms what I said for points 1, 3 and 4. So, we want to find an operation "op" which, applied to the two variables (character code and position) gives us the resulting hex code. Now let's have a look at the examples we find in point 4. We know that the ASCII code for "a" is decimal 97, hex 61h, so: 61h op 01h = 57h 61h op 08h = 0Ah (where 01h and 08h are the character positions in the example, of course) Let's have it in binary and decimal too, it will be useful: 0110 0001 op 0000 0001 = 0101 0111 0110 0001 op 0000 1000 = 0000 1010 97 op 1 = 87 97 op 8 = 10 Now, one interesting thing we can see is there seems to be a symmetrical relation between the three values: 97 - 10 = 87 This hints at a relation where the only variable is the character position (1 or 8). So, let't try to find an operation which transforms our equation system in: 97 - 10 = 87 97 - 87 = 10 Looking at the binary representation of 87 and 10, I can seen that if I shift 87 three digits to the right I obtain 10 (0101 0111 shr 3 = 0000 1010). So, one possibile solution for the puzzle is: 1) Take the charater's ASCII code ("a" = 97) 2) Subtract 10 (97 - 10 = 87) 3) Shift the resulting byte to the right by a number of digits equal to the character's position plus 2, where the first position in the input string is 1, but if the number of digits to shift is 10 or more, subtract 10. (so, 1 + 2 = 3 -> shr 3 ; 8 + 2 = 10 -> 10 - 10 = 0 -> shr 0). 3) Subtract the resulting byte from the character's ASCII code (so, 97 - 10 = 87 ; 97 - 87 = 10). While this works for the two given examples, it's a very weak explanation. For example, what I say in point 3 can work in other ways too, and still give the correct results. Maybe someone who is more experienced in cryptography than me will come up with a better solution. Hope this can somehow help you, it sure was fun for me! ;)
-
NOTE: Please let me know if another section/forum on the site is more appropriate for this question. I'm trying to solve an algorithm puzzle and I was hoping to get some help. Its not for any formal study, just a mind exercise/ puzzle but I've hit a road block: The goal is to figure out what algorithm or formula can be used to decrypt and encrypted string of characters where you know the characters being encrypted and what their encrypted value is but not how the encrypted value is determined. Obviously this would be like looking for a needle in a haystack except that there are some parameters to this that help (I think) narrow the process down. I can't help but think there's got to be a pattermn or method for figuring out something like this when you know the values of both the unencrypted character and what it encrypts to. The parameters of the puzzle are: 1) The encrypted characters are limited to the printiable set of characters within the standard 256 character ASCII set of characters (basically what's on a standard US keyboard). I suppose the thing woiuld work with non-visible charactres but I believe the intent is to use any of the keyboard characters a user could use and so that would include numbers, letters and some of the special characters too. 2) the string of characters to encrypt is limited to 12. 3) Each single character is encrypted to a 2 character value (I think it's always a number but I'm not certain ) so that a string of 12 characters will be encrypted to a 24 character long value. 4) Each character is encrypted to the exact same value based on its position in the string of characters to be encrypted. For example if the text to encrypt is abcdefga1234 then the lower case a is encrypted to the value 57 for position 01 in this string of 12 characters and in the 8th position the lower case a is encrypted to a value of 0A. No matter what combination of characters are in positions 1 thru 7, the lowercase a will always been encrypted as 0A when it is in the 8th position in the string of characters. 5) Each combination of characters plus position has a unique encrypted value and that value is constant when the position of the character is the same. I hope the last 2 above make sense; it's hard to convey these in words. I know that a large lookup table of characters along with their decrypted values and position could be sued to decrypt an encrypted string but unfortunately that’s not the answer to the puzzle. The goal is to decipher wh
In general, it is not doable: consider what happens when "a large lookup table" that you describe in your post is filled with randomly generated unique entries. Your target alphabet easily accommodates this, so the result satisfies each of your criteria 1 though 5. Yet the only way to "crack" this "pattern" would be to record the entire lookup table.
-
NOTE: Please let me know if another section/forum on the site is more appropriate for this question. I'm trying to solve an algorithm puzzle and I was hoping to get some help. Its not for any formal study, just a mind exercise/ puzzle but I've hit a road block: The goal is to figure out what algorithm or formula can be used to decrypt and encrypted string of characters where you know the characters being encrypted and what their encrypted value is but not how the encrypted value is determined. Obviously this would be like looking for a needle in a haystack except that there are some parameters to this that help (I think) narrow the process down. I can't help but think there's got to be a pattermn or method for figuring out something like this when you know the values of both the unencrypted character and what it encrypts to. The parameters of the puzzle are: 1) The encrypted characters are limited to the printiable set of characters within the standard 256 character ASCII set of characters (basically what's on a standard US keyboard). I suppose the thing woiuld work with non-visible charactres but I believe the intent is to use any of the keyboard characters a user could use and so that would include numbers, letters and some of the special characters too. 2) the string of characters to encrypt is limited to 12. 3) Each single character is encrypted to a 2 character value (I think it's always a number but I'm not certain ) so that a string of 12 characters will be encrypted to a 24 character long value. 4) Each character is encrypted to the exact same value based on its position in the string of characters to be encrypted. For example if the text to encrypt is abcdefga1234 then the lower case a is encrypted to the value 57 for position 01 in this string of 12 characters and in the 8th position the lower case a is encrypted to a value of 0A. No matter what combination of characters are in positions 1 thru 7, the lowercase a will always been encrypted as 0A when it is in the 8th position in the string of characters. 5) Each combination of characters plus position has a unique encrypted value and that value is constant when the position of the character is the same. I hope the last 2 above make sense; it's hard to convey these in words. I know that a large lookup table of characters along with their decrypted values and position could be sued to decrypt an encrypted string but unfortunately that’s not the answer to the puzzle. The goal is to decipher wh
Clearly a very basic algorithm if each character is changed individually. I would say it is just a shift cipher of some sort. First convert the characters to hex
a b c d e f g a 1 2 3 4 =
61 62 63 64 65 66 67 61 31 32 33 34now find out what values you need to add to those to get your resulting encryption. As I only have two values to use, here is a sample
61 62 63 64 65 66 67 61 31 32 33 34
- -10 -57
57 0A
fill in the rest and look for a pattern. Could be a repeating key, e.g. -10 +5 +23 - 57 interestingly (and maybe a coincidence) is that the second "a" is a reduction of the previously calculated "a" So the algorithm could be... 1. start with a byte array of size [256] that contains all -10 values 2. loop each character 3. convert character to hex (iHex) 4. convert iHex to decimal (iDec) 5. encrypted hex (eHex) equals: iHex - bytearray[iDec] 6. set new bytearray value: bytearray[iDec] = eHex (ready for next use) 7. output eHex to result string 8. process next character ...of course that is just one possible to match the results you have given
I may or may not be responsible for my own actions
-
Clearly a very basic algorithm if each character is changed individually. I would say it is just a shift cipher of some sort. First convert the characters to hex
a b c d e f g a 1 2 3 4 =
61 62 63 64 65 66 67 61 31 32 33 34now find out what values you need to add to those to get your resulting encryption. As I only have two values to use, here is a sample
61 62 63 64 65 66 67 61 31 32 33 34
- -10 -57
57 0A
fill in the rest and look for a pattern. Could be a repeating key, e.g. -10 +5 +23 - 57 interestingly (and maybe a coincidence) is that the second "a" is a reduction of the previously calculated "a" So the algorithm could be... 1. start with a byte array of size [256] that contains all -10 values 2. loop each character 3. convert character to hex (iHex) 4. convert iHex to decimal (iDec) 5. encrypted hex (eHex) equals: iHex - bytearray[iDec] 6. set new bytearray value: bytearray[iDec] = eHex (ready for next use) 7. output eHex to result string 8. process next character ...of course that is just one possible to match the results you have given
I may or may not be responsible for my own actions
First off thanks to both Moreno Airoldi and musefan for providing such detailed and well thoughout replies, this is the kind of help internet forums/boards are all about. I didn't realize how beenficial it would be to prvide additional sample values esle I would have given more then just the few I did. I am going to check out both your recomendations but it will be a day or so before I can get to them (thats why my own reply to each of you has been so slow coming) and so in the mean time here are more examples that might actually scream a pattern to you 2 who are clearly more versed in patterns. I tried to provide a sampleing without going over board. The belwo restroicted to a,b & c (in upper & lower case) is for just the first 3 positions and the resulting number of rows is 18. To show all 12 positions for just a few characters is a lot. Anyway, if anything about the pattern in teh eblow jumps out at you please let me know else I'll let you know what comes of testing your suggestions. Thanks Position, unencrypted character, encrytped value 1 a 57 2 a 24 3 a 2A 1 A 77 2 A 04 3 A 0A 1 b 54 2 b 27 3 b 29 1 B 74 2 B 07 3 B 09 1 c 55 2 c 26 3 c 28 1 C 75 2 C 06 3 C 08
-
First off thanks to both Moreno Airoldi and musefan for providing such detailed and well thoughout replies, this is the kind of help internet forums/boards are all about. I didn't realize how beenficial it would be to prvide additional sample values esle I would have given more then just the few I did. I am going to check out both your recomendations but it will be a day or so before I can get to them (thats why my own reply to each of you has been so slow coming) and so in the mean time here are more examples that might actually scream a pattern to you 2 who are clearly more versed in patterns. I tried to provide a sampleing without going over board. The belwo restroicted to a,b & c (in upper & lower case) is for just the first 3 positions and the resulting number of rows is 18. To show all 12 positions for just a few characters is a lot. Anyway, if anything about the pattern in teh eblow jumps out at you please let me know else I'll let you know what comes of testing your suggestions. Thanks Position, unencrypted character, encrytped value 1 a 57 2 a 24 3 a 2A 1 A 77 2 A 04 3 A 0A 1 b 54 2 b 27 3 b 29 1 B 74 2 B 07 3 B 09 1 c 55 2 c 26 3 c 28 1 C 75 2 C 06 3 C 08
Well obviously the same character in upper and lower case in the same position differs by (hex) 20. This strongly implies that the ANSI value of the character is being used in a relatively unsophisticated way (upper and lower case are separated by hex 20 in ANSI). The difference can be either way; to me this suggests an xor. However, it is not totally trivial as a->b->c is not just +1 each time: (ASCII value a 61 b 62 c 63) Slot 1 a 57 b 54 c 55 Slot 2 a 24 b 27 c 26 Slot 3 a 2A b 29 c 28 All numbers posted here are in the range 06-77. I would guess that it is a 7 bit algorithm (working on 00-7F) and operating with XORing the input character with some function of the input. Let's look at the XOR values for those slots: Slot 1 a 36 b 36 c 36 Slot 2 a 45 b 45 c 45 Slot 3 a 4B b 4B c 4B Looks like I'm onto something there. All that remains is to determine what the XOR parameter which is a function of position is. There isn't enough information in 3 slots and the pattern 36->45->4B does not immediately jump out at me as being meaningful. The encrypted value of 'aaaaaaaaaaaa' should provide all the XOR keys and hopefully that is enough to identify how they are calculated.
-
Well obviously the same character in upper and lower case in the same position differs by (hex) 20. This strongly implies that the ANSI value of the character is being used in a relatively unsophisticated way (upper and lower case are separated by hex 20 in ANSI). The difference can be either way; to me this suggests an xor. However, it is not totally trivial as a->b->c is not just +1 each time: (ASCII value a 61 b 62 c 63) Slot 1 a 57 b 54 c 55 Slot 2 a 24 b 27 c 26 Slot 3 a 2A b 29 c 28 All numbers posted here are in the range 06-77. I would guess that it is a 7 bit algorithm (working on 00-7F) and operating with XORing the input character with some function of the input. Let's look at the XOR values for those slots: Slot 1 a 36 b 36 c 36 Slot 2 a 45 b 45 c 45 Slot 3 a 4B b 4B c 4B Looks like I'm onto something there. All that remains is to determine what the XOR parameter which is a function of position is. There isn't enough information in 3 slots and the pattern 36->45->4B does not immediately jump out at me as being meaningful. The encrypted value of 'aaaaaaaaaaaa' should provide all the XOR keys and hopefully that is enough to identify how they are calculated.
You beat me to it :( Your suggestion of encrypting "aaaaaaaaaaaa" should be enough to solve this you are right. I think there is no pattern as it is just a random set of chars used to provide the XOR values, which should start with "6EK........." I think the OP has been lucky that such a simple algorithm was decided on
If my jokes make me laugh, then I have already succeeded with 100% of my target audience
-
You beat me to it :( Your suggestion of encrypting "aaaaaaaaaaaa" should be enough to solve this you are right. I think there is no pattern as it is just a random set of chars used to provide the XOR values, which should start with "6EK........." I think the OP has been lucky that such a simple algorithm was decided on
If my jokes make me laugh, then I have already succeeded with 100% of my target audience
Well he said it was a mind exercise/puzzle, so I guess it's supposed to be solvable by a person in a reasonable time. You may well be right that the XOR key is simply a 12 character pass code/encryption key. Encrypting 'aaaaaaaaaaa' (or the equivalent with byte zeroes) is often useful for key analysis in simple encryption schemes. I had to modify the first version of my stream encryptor because by throwing a stream of zeroes at it, it would dispense the key. (Real life binary messages, particularly if you're using my socket library as well, often have quite a few zeroes in known places – for example if you request an EXE or DLL download you can rely on 16 or more consecutive zeroes in places in the header; and 4 byte length encoded messages will generally be possible to generate with three zeroes in known positions.)