2
$\begingroup$

In a substitution cipher, I recieve 3 bits and than I return another 3 bits. The key of this cipher could be a matrix represented as:

(0) 0 0 0 => 0 1 1

(1) 0 0 1 => 1 0 1

(2) 0 1 0 => 1 1 1

(3) 0 1 1 => 0 1 0

(4) 1 0 0 => 0 0 1

(5) 1 0 1 => 1 0 0

(6) 1 1 0 => 0 0 0

(7) 1 1 1 => 1 1 0

So, when we receive 000, the cipher will return 011.

When we receive 101, the cipher will return 100.

The key itself can be represented as a stream of 24 bits like this:

0 1 1 1 0 1 1 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 1 0

Is there a way to reduce the key to 15 bits?

I other words, can that matrix representation of 24 bits, could be represented with 15 bits?

$\endgroup$
  • 1
    $\begingroup$ That's not a key, that's a permutation from ${\{0,1}\}^3$ to ${\{0,1\}}^3$. And it is identical to performing XOR with 1 for each bit, also known as a bit complement. $\endgroup$ – Maarten Bodewes May 24 '15 at 20:09
  • $\begingroup$ Maarten Bodewes, my key example was unfortunate... I changed there to a random mapping $\endgroup$ – user24664 May 24 '15 at 20:18
  • $\begingroup$ OK, now it is a random permutation from ${\{0,1\}}^3$ to ${\{0,1\}}^3$, helped you a bit with the edit. I presume any random permutation is allowed. $\endgroup$ – Maarten Bodewes May 24 '15 at 20:25
2
$\begingroup$

Not quite, if all possible permutations are allowed.

There are $8! = 40320$ permutations over 3 bits; 15 bits of key allows you to specify $2^{15} = 32768$ of them; hence any mapping of 15 bits will necessarily $40320-32768 = 7552$ of permutations unexpressable.

It is doable if you don't allow every single permutation (e.g. allow only even permutations), or if you allow 16 bits of keying data.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.