[Cryptography] Kerckhoffs's principle ==? Turing Machine universality

Henry Baker hbaker1 at pipeline.com
Thu Feb 25 19:04:01 EST 2016


Either Kerckhoffs preceded Turing by a half century, or
Turing rediscovered Kerckhoffs's Principle in the form of
Turing Machine universality.

Kerckhoffs suggested that an entire crypto machine could
be considered a mathematical abstraction, where the only
thing missing for decryption was a "key", which Shannon
interpreted as a number of bits of information.

But with the advent of the (universal) Turing Machine,
the entire crypto machine could also be reduced to a
("small" constant-size) bit string, independent of the
amount of key & plaintext material to be processed.

Inverting this logic, every crypto machine is a
universal Turing Machine with a "key" which consists
of a particular crypto TM description, plus an initial
input tape with a fixed-size number of tape squares
containing the key, and another input tape consisting
of either the plaintext to be encrypted, or the
ciphertext to be decrypted.

In modern virtual machine terminology, you have a
computer with a hypervisor that boots up a particular
crypto program which you then feed with a key located
in a file system which the virtual machine has access
to.

Thus, Turing's universal TM is a very mild extension of
Kerckoffs's Principle.

https://en.wikipedia.org/wiki/Kerckhoffs%27s_principle



More information about the cryptography mailing list