Suppose I have a Java string of length 32, e.g.
String s = "Y7yEdfjQ2qmpGZbPYswKIdxYVo6KnR9M";
I'm looking for the string t with the following property: If the following loop is performed on t, the resulting string is s:
char[] tArr = t.toCharArray();
for (int i = 1; i < 32; i++) {
tArr[i] = (char) (tArr[i] ^ tArr[i * 123456 % 31] & 31);
}
Note that in Java the array operator [] has highest precedence and bitwise AND is evaluated before bitwise XOR.
In order to obtain t the reverse operation must be applied to s. The inverse operation of XOR is XOR, however the logical AND obviously has no inverse operation.
Can the string t be recovered short of bruteforcing?
Your loop takes in each iteration two chars, and xors the first char with the lowest 5 bits of the other char. That means that the top 3 bits remain unchanged. They don't get lost. In fact the top 3 bits of t[i] are equal to the top 3 bits of s[i], and we only have to find the lowest 5 bits of the characters in the original string t.
Now, lets calculate i * 123456 % 31, and see what the loop actually does in each iteration :
t[1] = t[1] ^ (t[14]&31)
t[2] = t[2] ^ (t[28]&31)
t[3] = t[3] ^ (t[11]&31)
t[4] = t[4] ^ (t[25]&31)
t[5] = t[5] ^ (t[8]&31)
t[6] = t[6] ^ (t[22]&31)
t[7] = t[7] ^ (t[5]&31)
t[8] = t[8] ^ (t[19]&31)
t[9] = t[9] ^ (t[2]&31)
t[10] = t[10] ^ (t[16]&31)
t[11] = t[11] ^ (t[30]&31)
t[12] = t[12] ^ (t[13]&31)
t[13] = t[13] ^ (t[27]&31)
t[14] = t[14] ^ (t[10]&31)
t[15] = t[15] ^ (t[24]&31)
t[16] = t[16] ^ (t[7]&31)
t[17] = t[17] ^ (t[21]&31)
t[18] = t[18] ^ (t[4]&31)
t[19] = t[19] ^ (t[18]&31)
t[20] = t[20] ^ (t[1]&31)
t[21] = t[21] ^ (t[15]&31)
t[22] = t[22] ^ (t[29]&31)
t[23] = t[23] ^ (t[12]&31)
t[24] = t[24] ^ (t[26]&31)
t[25] = t[25] ^ (t[9]&31)
t[26] = t[26] ^ (t[23]&31)
t[27] = t[27] ^ (t[6]&31)
t[28] = t[28] ^ (t[20]&31)
t[29] = t[29] ^ (t[3]&31)
t[30] = t[30] ^ (t[17]&31)
t[31] = t[31] ^ (t[0]&31)
We know that after the final iteration, the array has been transformed from t (which we don't know) to s (which we know - "Y7yEdfjQ2qmpGZbPYswKIdxYVo6KnR9M").
Now, since t[0] is never modified, we know that s[0]=t[0]='Y' (or 01011001 in binary).
This gives us t[31] easily :
t[0]&31 = 00011001
s[31] = 'M' = 01001101 = t[31] ^ 00011001
xor both sides, and get :
t[31] = 01001101 ^ 00011001 = 01010100
The other characters are less easy.
The iterations of the loop form two cycles :
1->14->10->16->7->5->8->19->18->4->25->9->2->28->20->1
3->11->30->17->21->15->24->26->23->12->13->27->6->22->29->3
Now, lets try finding other characters of t :
t[30] = t[30] ^ (t[17]&31)
after this assignment, t[30] becomes s[30], i.e. '9' or 00111001.
We know that 001 11001 = 001 ????? ^ 000 xxxxx
Where ????? are the lowest 5 bits of t[30] and xxxxx are the lowest 5 bits of t[17]. But actually, it's not the original t[17]. By the time we assign t[30], t[17] has already been updated to its final value, which we know (it's s[17] - 's' or 01110011).
Therefore 001 11001 = 001 ????? ^ 000 10011.
And if we xor both sides, 001 11001 ^ 000 10011 = 001 01010
so the original t[30] is 00101010.
So far I found t[0],t[30] and t[31].
I believe (though I haven't actually checked), that I can go on and find all the other characters of t this way.
The important thing to pay attention to when we calculate t[i] is that if t[i] depends on t[j] such that i<j, it depends on the original value of t[j] (the unknown), while if i>j, it depends on the final value of t[j] (which is s[j] - which we know).