[Cryptography] Random permutation model for encryption as a teaching tool?
peter at tsto.co.uk
Mon Oct 15 13:58:54 EDT 2018
On 15/10/18 15:38, Stephan Neuhaus wrote:
> Dear list,
> I'm teaching a class on IT security generally, and crypto plays not a
> small part in it. The original lecture had a lot of historical context
> and explained monalphabetic ciphers, simple polyalphabetic ciphers and
> transposition ciphers in great detail, and then went rather abruptly to
> AES, which could not be explained on that level any more.
> Since the students only need to understand the *properties* of modern
> ciphers but not the details of their *construction*, and also since the
> detailed treatment of historical ciphers and their cryptanalysis had
> some students derive wrong ideas (e.g., being able to break AES by
> frequency analysis), I was looking for another way to explain modern
> ciphers to students in a way that would give them a useful mental model.
> I came upon the random permutation model of ciphers. In this model,
> given a set P of possible plaintexts, and a set C of possible
> ciphertexts, a key selects a random permutation from P to C (and
> therefore |P| = |C|). This model is of course not an invention of mine;
> it's present in the Wikipedia page on block ciphers for example.
> However, the set of possible n-bit keys contains only 2^n elements,
> whereas there are (2^b)! possible permutations of b-bit blocks, which is
> obviously vastly more if b is of the same order as n. Furthermore, not
> all permutations are good for block ciphers; e.g. those that have many
> fixed points (and most random permutations will have at least one) are
> evidently not well suited.
> So the question is, is this a good model *for teaching*? It doesn't have
> to lead to theorems, and it may even be slightly inaccurate, as long as
> it prevents students from getting entirely wrong ideas à la breaking AES
> with frequency analysis. I personally find it useful, but I have no idea
> what the students will think. Do you use other models?
The bit about 2^n keys and (2^b)! permutations is a lightbulb moment for
I'd avoid talking about permutations which are not good for block
ciphers, as I believe you are wrong there anyway - if they are randomly
chosen, they are good.
Afaict the only way in which it is inaccurate is that in a real cipher
the permutations are pseudorandomly chosen, rather than real-randomly.
-- Peter Fairbrother
More information about the cryptography