Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm now studying the block cipher substitution-permutation network construction and realized that it uses several small pseudo-random permutations instead a big one for saving memory (or that is one of the reasons).

Why does the PRP with input/output of $n$ bits utilize $\log(2^n!)$ memory? (When saving a full table of $\mathrm{Domain}\to\mathrm{Range}$)

I thought it should utilize $n\cdot2^n$.

share|improve this question
uses several small PRPs instead a big one I'm not sure what you mean by that. A block cipher iterates over itself a number of times (rounds) to make the output look random. Maybe it's my maths illiteracy but what do you mean by $domain -> range$? – rath Dec 9 '13 at 0:35

Each one of your first two sentences has a mistaken premise: you're starting from some assumptions that aren't actually true.

DES does not use small PRPs for saving memory. It doesn't use small PRPs at all. The DES S-boxes are not PRPs. The DES F-function is not a PRP. A SPN does not use several small PRPs for saving memory. A SPN doesn't use PRPs at all. The S-boxes in a SPN are not PRPs.

A PRP does not necessarily require $\lg(2^n!)$ memory. Actually, most PRPs have short keys that fully determine the encryption mapping, and the short key can be stored in much less memory. That is in some sense the entire point of a PRP.

You might wish to restate your questions in a way that removes those implicit assumptions. Also you might wish to review the definition of a PRP again, and read some more textbook material on PRPs to familiarize yourself with the concept a bit further. Perhaps you are confusing a PRP with a random permutation (one chosen uniformly at random from the set of all permutations on $n$ bits). If so, here's an exercise for you to ponder: how many permutations are there on $n$ bits? Now what happens if the take the logarithm (base 2) of that number?

share|improve this answer
Sorry, I meant block cipher construction like SPN instead of DES. Will edit my question. – Bush Dec 7 '13 at 21:42
@Bush, your question still has the same problems. Have you tried answering the questions in the last paragraph of my question? They are intended to get you thinking along lines that enable you to clear up your confusion on your own. – D.W. Dec 7 '13 at 23:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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