How to determine which encryption system is being used?

Question

I came across this question in a local contest. I was not able to solve it at that time. Also, no solution was provided. I was wondering if someone can help me to understand how to tackle this kind of questions?

Thanks,

Answer 1

Technically, there's infinitely many possible encryption schemes that do this. But here's what I figured out for what I suspect "they" want, and how. I considered that the "encrypted" number looks as though it's "Hexadecimal", by noting the 0-9 digits and "F" (since I know this well from programming), and then decided to convert it from hexadecimal to binary to examine the bit pattern. And this is what I got:

$$0030700F01FF0_{16} = 0000000000110000011100000000111100000001111111110000_{2}$$ (incl. leading zeroes)

Note that in the plaintext, there are 2 1's, then 3 1's, then 4 1's, then 9 1's. "11" and "111", presumably corresponding to 2 and 3, are separated by 5 zeroes. "1111" and "111111111", presumably corresponding to 4 and 9, are separated by 7 zeroes. So there it seems the scheme must use zeroes to separate the ones corresponding to nonzero digits of the plaintext. Zero digits must also be encoded, apparently, using zeroes, somehow. We also note that all the strings of 1s are right-aligned to nybble boundaries (1 nybble = 4 bits, or 1 hex digit). This is easily seen by breaking it up as so:

$$0000|0000|0011|0000|0111|0000|0000|1111|0000|0001|1111|1111|0000$$

Note that if we look back at the original hex, we can break it up now as

$$00(3)0(7)00(F)0(1FF)0$$,

So every smallest set of nybbles corresponding to a sequence of 1s is separated by 1 or 2 zero-nybbles. If we write a 2 below the (3), a 3 below the (7), a 4 below the (F), and a 9 below the (1FF), we see that the double-zeroes appear when there is a 0 digit. This suggests that single nybbles of zeroes -- that is, single "0" hex digits, are used to separate out individual digits of the plaintext, and 0 itself maps to a zero-nybble, i.e. hex digit "0". So I'll bet the ciphering method they want you to use is:

1. To encrypt a "0", use a nybble of 0 bits, i.e. use a hex digit 0.
2. To encrypt 1-9, write out a number of 1 bits corresponding to that digit, and convert that to hex.
3. Separate the encipherings of each digit by a "0" hex digit.

This makes an easy table:

$$0 \rightarrow 00$$ $$1 \rightarrow 10$$ $$2 \rightarrow 30$$ $$3 \rightarrow 70$$ $$4 \rightarrow F0$$ $$5 \rightarrow 1F0$$ $$6 \rightarrow 3F0$$ $$7 \rightarrow 7F0$$ $$8 \rightarrow FF0$$

So the encryption of your string is

00F01F00070301FF0FF03F0F01FF0F07030F03F0107F0FF03F01F0000000F01FF0FF03F07F0F0001F0703010FF0FF01FF01F0

(provided I didn't make any mistakes)