Counting a Structured Password Generator with Combinatorics
Most password generators are judged by intuition: they look random, so they must be strong. A better approach is to count the exact number of possible outputs. Once we can count the space precisely, we can measure the generator’s entropy instead of guessing.
Password Series
Count the exact number of valid passwords this structured generator can produce.
Use combinatorics: count each independent choice, then multiply them together.
This generator produces about 5.50 × 10²⁰ passwords, or roughly 69 bits of entropy.
Our Password Structure
We will analyze a generator that produces passwords in this shape:
segment-segment-segmentEach segment follows these rules:
- Each segment contains 3–5 lowercase letters
- The three segments must all have different lengths
- A single digit appears in exactly one segment
- A single symbol appears in exactly one segment
- The digit and symbol cannot appear in the same segment
- Digits and symbols can appear as prefixes or suffixes
This is a good example of a structured generator: it is readable, constrained, and still large enough to analyze mathematically.
Choose the Segment Lengths
The allowed lengths are:
\[ \{3,4,5\} \]
Since all three segments must have different lengths, we are not choosing freely with repetition. We are choosing a permutation of the three values.
\[ 3! = 6 \]
The possible orders are:
(3,4,5)
(3,5,4)
(4,3,5)
(4,5,3)
(5,3,4)
(5,4,3)Count the Letter Combinations
Each letter comes from the lowercase alphabet:
\[ |A| = 26 \]
Across the three segments, the total number of letters is always:
\[ 3 + 4 + 5 = 12 \]
That means the number of possible letter strings is:
\[ 26^{12} \]
The order of segment lengths matters, but the total number of letters stays the same.
Place the Digit and Symbol
Digit placement
The digit involves three independent choices:
- Choose which segment gets the digit: \(\;3\)
- Choose the digit itself: \(\;10\)
- Choose prefix or suffix position: \(\;2\)
So digit placement contributes:
\[ 3 \cdot 10 \cdot 2 \]
Symbol placement
The symbol must go in a different segment than the digit, so after the digit segment is chosen, only two segments remain.
- Choose which remaining segment gets the symbol: \(\;2\)
- Choose the symbol itself: \(\;8\)
- Choose prefix or suffix position: \(\;2\)
So symbol placement contributes:
\[ 2 \cdot 8 \cdot 2 \]
Total Password Space
Now we multiply the independent choices:
\[ 6 \cdot 26^{12} \cdot 3 \cdot 10 \cdot 2 \cdot 2 \cdot 8 \cdot 2 \]
This simplifies to:
\[ 5760 \cdot 26^{12} \]
Since:
\[ 26^{12} = 95{,}428{,}956{,}661{,}682{,}176 \]
the total number of valid passwords is:
\[ 5760 \cdot 26^{12} = 549{,}670{,}790{,}371{,}289{,}333{,}760 \]
or approximately:
\[ 5.50 \times 10^{20} \]
Convert Password Space into Entropy
Password strength is often measured in bits of entropy:
\[ H = \log_2(N) \]
Substituting our value gives:
\[ \log_2(5.50 \times 10^{20}) \approx 68.9 \]
So this generator provides roughly 69 bits of entropy.
Why Summation Helps Analysis but Not Generation
Mathematics helps us count the space. For example, we could summarize part of the counting idea using notation like:
\[ \sum_{p \in P(3,4,5)} 26^{\sum p_i} \]
But that formula does not generate passwords. It only measures the space.
Generation still requires random sampling. The math tells us how big the world is. Randomness picks a single point inside it.
Frequently Asked Questions
These are the practical questions that usually come up when counting a structured password generator with combinatorics.
Why count the password space instead of just saying the generator looks strong?
Because visual complexity is not the same as measured security. Counting the exact number of valid outputs gives you a concrete search space and an entropy value instead of a guess.
Why do we multiply the choices instead of add them?
Because these are independent decisions: segment order, letters, digit placement, symbol placement, and position choice. Independent choices multiply in combinatorics.
Why is the segment-length count equal to 6?
The generator must use all three lengths 3, 4, and 5 exactly once, so the question is just how many orders those three values can appear in. That is \(3! = 6\).
Does a structured password format automatically make a generator weaker?
Not necessarily. Structure reduces freedom, but the remaining space can still be very large. The only reliable way to judge it is to count the actual output space.
What does 69 bits of entropy mean in practice?
It means the generator produces a search space equivalent to about \(2^{69}\) possibilities. That is a much more useful measurement than simply calling the passwords “complex.”
Why does the summation notation help analysis but not generation?
Because counting formulas describe the size of the space, not how to randomly choose one password from it. Generation still needs a sampling process that picks a valid output.
Conclusion
A structured password generator can be analyzed exactly. That is the first important lesson.
Once a generator’s rules are clear, combinatorics lets us count the total number of valid outputs, and entropy turns that count into a security measurement.
That raises the next question: can we design generators so exact entropy is built into the format from the start?
Raell Dottin
Comments
Post a Comment