[Cryptography] Random permutation model for encryption as a teaching tool?

Peter Fairbrother 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 mailing list