779 - Wily Hacker's Problem

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

779 - Wily Hacker's Problem

Post by brianfry713 » Wed Jul 30, 2014 12:18 am

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?
Check input and AC output for thousands of problems on uDebug!

bategojko74
New poster
Posts: 4
Joined: Wed Feb 25, 2015 2:47 pm

Re: 779 - Wily Hacker's Problem

Post by bategojko74 » Wed Feb 25, 2015 3:19 pm

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
New poster
Posts: 4
Joined: Wed Feb 25, 2015 2:47 pm

Re: 779 - Wily Hacker's Problem

Post by bategojko74 » Wed Feb 25, 2015 6:37 pm

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
New poster
Posts: 4
Joined: Wed Feb 25, 2015 2:47 pm

Re: 779 - Wily Hacker's Problem

Post by bategojko74 » Thu Feb 26, 2015 3:50 pm

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
New poster
Posts: 4
Joined: Wed Feb 25, 2015 2:47 pm

Re: 779 - Wily Hacker's Problem

Post by bategojko74 » Thu Feb 26, 2015 3:53 pm

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));
}

Post Reply

Return to “Volume 7 (700-799)”