779 - Wily Hacker's Problem

[brianfry713]

I attempted to solve 779, but the problem statement seems too ambiguous.

Here is one encryption scheme I came up with, which works for both sample inputs. I could probably come up with others.
C[1] = M[1] < K[4] < K[4] + K[3] < K[2] + K[2] ^ K[2] < K[1] ^ K[3] + K[4] ^ K[2] < K[2];
C[2] = M[2] ^ K[2] + K[1] + K[1] < K[1] ^ K[3] < K[3] + K[1] + K[1] + K[1] + K[4] < K[2] ^ K[4];
C[3] = M[3] + K[1] + K[1] < K[4] + K[1] + K[1] + K[4] < K[4] < K[4] ^ K[1] < K[2] ^ K[3];
C[4] = M[4] ^ K[1] + K[1] < K[1] ^ K[1] < K[4] + K[1] + K[1] + K[4] + K[4] < K[2] ^ K[3] < K[1] + K[2];

Where ^ is xor, + is addition modulo (1 << 16), and < is left circular shift.

To decrypt start with C and go right to left in the above formulas. Xor is the same, addition becomes subtraction, and left circular shift becomes right circular shift.

There are probably other ways to approach this problem. Can anyone share their thoughts on how to get AC here?

[bategojko74]

This problem is given in Romania and in South pacific region with differnt crypt scheme and different input but common output(TEACHERS and STUDENTS).
Most of the problem statements are mistaken. They take crypt scheme from australian contest and input data from romanian contest.
You can find the correct problem(with correct input) statement for South Pacific contest at : https://www.cs.auckland.ac.nz/~mjd/prog ... PC1996.pdf

You can't find the encryption scheme for Romanian contest anywhere on the web. But I know it because I have participated in Romanian contest.
The graph of the scheme is the same but there are five differences in the operators(graph nodes).
1) On the first row replace
(<K1) (+K2) (^K3) (<K4)
with
(<K1) (+K2) (+K3) (<K4)

2)In the first ellipse replace
(<(K1 + K2))
with
(<(K1 ^ K2))

3)In the second ellipse replace
(<(K3 + K4))
with
(<(K3 ^ K4))

4) In the middle circle which accepts the output arrows of the both ellipses as an input replace
(^)
with
(+)

5) In the circle on the third position of the last row containing circles over 'C3' replace
(^K2)
with
(+K2)

And that's all. Cheers.

Bate Gojko

[bategojko74]

Infact I dont remember the exact scheme but I remember that the graph of the scheme is the same.
Yesterday I reversed the scheme rotating 18 nested loops for every operator in the scheme and
found the original operators of the Romanian cryptogram.

[bategojko74]

And here is the source code that decrypts Romanian Cryptogram(uncomment the operators in comments and comment the operators right before them to decrypt South Pacific cryptogram):

bool DecryptMessage(unsigned short int * punCrypted, unsigned short int * punKey, char * pchResult)
{
for (unsigned short int unD3 = 0; true; unD3++)
{
unsigned short int unA2 = _rotr16(punCrypted[0], (punKey[3] % 16)) ^ unD3;
unsigned short int unE2 = (punCrypted[2] - /*^*/punKey[1]) ^ unD3;
unsigned short int unC1 = unA2 ^ unE2;
unsigned short int unC2 = _rotl16(unC1, ((unsigned short int )(punKey[0] ^ /*+*/punKey[1])) % 16);
unsigned short int unC3 = unC2 + /*^*/ unD3;
unsigned short int unB2 = unC3 ^ ((unsigned short int )(punCrypted[1] - punKey[2]));
unsigned short int unF2 = unC3 ^ _rotr16(punCrypted[3], (punKey[0] % 16));
unsigned short int unD1 = unF2 ^ unB2;
unsigned short int unD2 = unD1 + unC2;
unsigned short int unNewD3 = _rotl16(unD2, (((unsigned short int )(punKey[2] ^ /*+*/ punKey[3])) % 16));

if (unNewD3 != unD3)
{
if (unD3 == ((unsigned short int)0xffff))
break;
continue;
}

((unsigned short int *)pchResult)[0] = _rotr16(unA2, (punKey[0] % 16));
((unsigned short int *)pchResult)[1] = unB2 - punKey[1];
((unsigned short int *)pchResult)[2] = unE2 - /*^*/punKey[2];
((unsigned short int *)pchResult)[3] = _rotr16(unF2, (punKey[3] % 16));

pchResult[8] = 0;

return true;
}
return false;
}

[bategojko74]

Forgot :

unsigned short int _rotl16(unsigned short int usnArg, int nCount)
{
nCount %= 16;
unsigned int unArg = usnArg;
unArg <<= nCount;
unsigned int unArg1 = unArg >> 16;
return (unArg | unArg1);
}

unsigned short int _rotr16(unsigned short int usnArg, int nCount)
{
return _rotl16(usnArg, 16 - (nCount % 16));
}