A policy changes the sample space
Suppose a system allows lowercase letters, uppercase letters and digits in an eight-character password. How many strings are possible? What changes when characters cannot repeat? What if at least one character from every selected category is required? These are different counting problems and cannot share one careless formula.
The analyzer builds a mathematical search space from category sizes, length, repetition rules and category requirements. It then expresses the size in bits and estimates exhaustive-search time under an explicitly assumed guessing rate.
Product rule
Multiply independent choices at successive positions.
Inclusion–exclusion
Count strings that use every required category.
Logarithms
Convert a large count into an information measure.
Repetition decides between powers and permutations
Characters may repeat
N choices per position, length L ⇒ N^L strings
With 10 digits and length 4, each of four positions has 10 choices: 10×10×10×10 = 10,000. This includes strings such as 0000 and 1221.
Characters may not repeat
P(N,L) = N! / (N−L)! for L ≤ N
The first position has N choices, the next has N−1, and so on. For four distinct digits, the count is 10×9×8×7 = 5,040. When L>N, the count is zero because distinct selection is impossible.
Adding alphabets changes N; requirements change the rule
| Example category | Illustrative size | Symbol |
|---|---|---|
| Lowercase English letters | 26 | a |
| Uppercase English letters | 26 | b |
| Digits | 10 | c |
| Selected special symbols | 10 | d |
If all four sets are available with repetition, N=72 and the unrestricted count is 72^L. But “available” is not the same as “must appear”. Requiring every category removes all strings that omit at least one category.
Length feasibility
If four non-empty categories are required, length must be at least four. This simple lower bound is an excellent pre-calculation check. Without repetition, the total length also cannot exceed the combined alphabet size.
Subtract missing categories without double-subtracting
For lowercase L, uppercase U and digits D, begin with all strings from the combined alphabet. Subtract strings with no lowercase, no uppercase and no digits. A string missing both lowercase and uppercase was subtracted twice, so add such intersections back. Finally subtract the strings missing all three.
valid = T − (missing L + missing U + missing D) + (missing L∩U + missing L∩D + missing U∩D) − missing L∩U∩D
Each term uses available^length when repetition is allowed or P(available,length) otherwise. The alternating sign depends on how many categories are omitted.
Small verification
Using one lowercase symbol {a}, one digit {1}, length 2 and requiring both gives two valid strings: a1 and 1a. Formula: 2² − 1² − 1² = 2. A good implementation must reproduce this enumerable case before being trusted with enormous counts.
Log base two answers repeated yes/no decisions
information measure H = log₂(S), where S is search-space size
If S=256, then H=8 because 2⁸=256. This is often called entropy only under a uniform random-choice assumption. Human-chosen passwords are not uniformly sampled: names, keyboard patterns and reused phrases can be much more likely than arbitrary strings.
Exhaustive-work estimates
worst-case guesses = S average position under random ordering ≈ S/2 time = guesses / guesses_per_second
A guessing rate is not universal. Online authentication may be rate-limited; offline attacks depend on the stored hash, hardware and configuration. The program therefore labels the rate as an input assumption rather than presenting one dramatic number as fact.
Complete Python implementation
The analyzer supports four selectable category sizes, exact length, repetition/no repetition, an optional “use every selected category” rule and a chosen guesses-per-second assumption. Python integers grow automatically, so even very large spaces remain exact.
Loading source…Trace two tiny required categories
- Choose an enumerable model.
- Count aa, a1, 1a, 11.
- Subtract first invalid set.
- Subtract second invalid set.
- Add intersection back; its contribution is zero.
- Apply inclusion–exclusion.
- Verify by direct enumeration.
- Convert count to information.
- Apply an explicit rate assumption.
Press Next to begin.
Use cases small enough to enumerate
One category with repetition
No repetition
Two singleton categories
Impossible category requirement
Policy monotonicity
Combinatorial size is not observed security
| Mathematics captures | Mathematics alone misses |
|---|---|
| Number of policy-valid strings | Human choice bias and reuse |
| Uniform information measure | Common-password dictionaries |
| Assumed exhaustive time | Hash algorithm and rate limiting |
| Effect of length/category rules | Phishing, malware and credential leaks |
For fixed category count, unrestricted counting is O(1) arithmetic conceptually. Required-category counting uses O(2ᶜ) terms. Large-integer arithmetic cost grows with the number of digits, so real runtime is not literally constant for arbitrarily huge numbers.
Check the model choice
Which formula counts length L strings from N symbols when repetition is allowed?
Why add pairwise missing-category intersections back?
Extensions
- Count all permitted lengths from a minimum to maximum.
- Require at least two digits using complementary counting or generating functions.
- Compare uniform random generation with a deliberately biased toy generator.
- Plot log₂(search space) as length increases.
- Add exact custom category sizes while preventing overlapping symbols.
State the counting assumptions
When do you use N^L?
When there are N choices at every one of L ordered positions and reuse is allowed.
When do you use permutations?
When positions are ordered but a selected symbol cannot be used again, producing N(N−1)… choices.
Why is inclusion–exclusion necessary?
Invalid sets such as “missing lowercase” overlap. Simple subtraction removes their intersections multiple times.
Does log₂(S) prove password entropy?
Only under a uniform choice model. A generation process with predictable preferences has lower effective uncertainty.
Why use arbitrary-precision integers?
Search spaces grow exponentially and quickly exceed fixed 64-bit ranges; exact big integers avoid overflow.
Correct counting begins with precise rules
Powers, permutations and inclusion–exclusion answer different models. The strongest result is not the largest number—it is a count whose alphabet, length, repetition, requirements and interpretation are all explicit.