Creating Good Passwords

September 11 2022
Home | Blog | Prev | Next
Public Domain · vim(1) No Babies

If you simply want a good way to generate passwords, jump to "List of 7,776 Common Words". Otherwise, here's the table of contents:

What Makes a Good Password?

Good passwords are hard for hackers to guess. They have three properties:

Good Passwords Are Random

Passwords must be random; otherwise hackers could easily guess them. Don't use any personal information (your name, government ID, birthday, family members' names, pets' names, business's name, etc.) as part of your passwords because it's probably publicly available or easy to guess. Don't try to make up passwords in your head, either: People are terrible at creating randomness. Use physical processes (coins, dice, or playing cards) instead.

Good Passwords Are Long

Even if passwords are random, they must be long, or else hackers might accidentally guess them.

Good Passwords Contain Lots of Entropy

Entropy is a measure of randomness. The more entropy a password has, the more difficult it is for hackers to guess it. Entropy is usually measured in bits — the same bits that computers use, each of which is 0 or 1. One bit of entropy contains the same amount of randomness as a single coin flip. N bits of entropy contain the same amount of randomness as N coin flips.

Information Entropy

Technically speaking, entropy as discussed above is known as information entropy and describes systems people use to generate passwords, not passwords themselves. When people say that a particular password has "100 bits of entropy", they mean that the process the password's creator used generates 100 bits of entropy.

For example, tossing a coin 100 times to generate passwords containing 1's and 0's is a 100-bit password-generating system. The passwords this system creates technically don't contain any information entropy.

Algorithmic Entropy

Although individual passwords don't contain information entropy per se, they do contain algorithmic entropy, also known as kolmogorov complexity and descriptive complexity. A password's algorithmic entropy is a measure of how long it would take someone to tell someone else the password. For example, someone can only communicate the password:

RqHxPtNah73zHJUy

to another person by saying each letter (including its case) and number: there are no recognizable words, codes, or other ways to shorten the password for communication. (In other words, this password is incompressible.)

Compare that to:

AAAAAAAAAAAAAAAA

which someone could communicate by saying "sixteen uppercase A's" — much easier! Its algorithmic complexity is much lower than the complicated, random-looking password.

How Both Kinds of Entropy Fit into Password Generation

The ways you create passwords should have high information entropy. The more bits of entropy they have, the harder hackers will probably have to work to guess your passwords. Passwords would ideally also have high algorithmic entropy.

Why should passwords have high algorithmic entropy? Most people, especially those who know nothing about computer security, tend to choose passwords that are easy to describe (low algorithmic entropy) and thus easy to remember, like "abcd12345" ("'a' through 'd', '1' through '5'"). Hackers exploit this tendency by trying passwords with low algorithmic entropy first.

Unfortunately, even password schemes with high information entropy, such as flipping a coin 256 times to generate strings of 256 1's and 0's, may create passwords with low algorithmic entropy, such as a string of 256 0's. This is extremely unlikely if you create random passwords, so this is rarely problematic in practice. The rest of this document focuses exclusively on information entropy.

Password Strength and Quantum Computers

How much information entropy do your passwords need? That depends on how important the information your passwords protect is. For data that must remain absolutely secret — bank accounts, government records, etc. — at least 128 bits is recommended. For less important accounts, fewer bits will do, though you should use at least 80 bits. Most security experts think 100 bits is effectively unguessable.

Quantum computers are poised to revolutionize computing. Mathematicians have devised several clever algorithms (Shor's algorithm and Grover's algorithm) that make sufficiently large quantum computers capable of breaking most of today's information security systems. Although large quantum computers haven't been built yet, they're just over the horizon.

To guard against quantum computers, double the number of bits of entropy in your passwords. For example, if you want a password that is effectively 100-bits-strong against quantum computers, make it 200 bits. You have to double the number of bits because hackers can use Grover's algorithm to greatly reduce the number of guesses they need to make. Specifically, if a hacker needs to guess at most N times to figure out your password, Grover's algorithm reduces the number of guesses to the square root of N, which halves the password's bits of entropy.

Thus the recommended number of bits depends on how sensitive the information they guard is and whether you want to consider quantum computers (QC):

Information Sensitivity Examples Bits (No QC) Bits (QC)
Throwaway: I don't care if someone steals it. Accounts lacking personal info or photos/recordings 80 160
Sensitive: It wouldn't be the end of the world if someone steals it Online news subscriptions, dating profiles, Twitter 100 200
Critical: Theft would mean the end of my life/world Financial accounts, government records, some social media — anything with info that someone could use to impersonate, attack, stalk, or rob you 128 256

Entropy Sources

This document assumes you're using physical processes — coins, dice, cards, etc. — to generate passwords. You can use digital sources, such as /dev/random and websites like random.org, but only if you trust that their results are truly random and that no one else can see or bias their results. If you're paranoid about security, create passwords using physical processes you can control, not computers. The results will be truly random and you won't have to trust third parties.

Flipping Coins

Coins are ubiquitous. Flipping one generates a single bit of entropy. They're most useful when your alphabet's size is a power of two (2, 4, 8, 16, 32, 64, 128, 256, etc.).

When you flip a coin:

  1. Toss it high up as you flip it. Short flips reduce the coin's randomness.
  2. Make sure you flick it well so that it rotates quickly. Faster rotation improves randomness.
  3. Catch it in your hand. Letting it hit a surface and roll flat will bias the results slightly (make it less random).

Rolling Dice

Dice are cheap and easy to find, but they're not as common as coins. They come in a variety of sizes and shapes. 6-sided dice are common. Role-playing game (RPG) dice are also easy to find. A complete RPG dice set has a 4-sided die, an ordinary 6-sided die, an 8-sided die, two 10-sided dice (one marked with multiples of 10), a 12-sided die, and a 20-sided die.

When rolling dice:

  1. Don't just drop them an inch or two above a hard surface as most game players do. The results won't be very random. Instead, toss them a long distance across the surface so that they tumble and roll a lot.
  2. Rolling them onto a hard backdrop (similar to a craps table's rubber bumper) can improve randomness.

Poker and Bridge Cards

Poker and bridge cards (standard 52-card decks with French suits) are also a handy way to generate randomness. You can remove cards to match your alphabet's size.

When using cards:

  1. Riffle shuffle the deck at least seven times to randomize it. Don't use an overhand shuffle, which many card players use to speed up shuffling or protect decks. Overhand shuffling requires at least 10,000 shuffles to produce random results. Watch a mathematician explain randomness in card shuffling.
  2. You'll need to reshuffle the entire deck every time you draw a card. If you don't, subsequent draws will make some results more probable than others. Using multiple decks or splitting a deck into smaller ones (if your alphabet has 26 or fewer symbols) and shuffling and drawing from them separately can hasten random number generation.

Some password generation schemes don't require you to reshuffle the deck every time you draw a card ((2) above), but their passwords will have less entropy.

Alphabets

Passwords are sequences of random symbols. Therefore, you have to decide which set of symbols — which alphabet — you'll use. Each symbol contributes log2 N bits of entropy, where N is the size of the alphabet and log2 is the base-2 logarithm function, if you choose each symbol independently and randomly.

Here are some alphabets and the number of bits of entropy each of their symbols contributes:

Alphabet Symbols Bits/Symbol
Decimal digits (0-9) 10 3.3
Hexadecimal 16 4.0
Lowercase English alphabet 26 4.7
Lowercase English alphabet plus decimal digits 36 5.1
Full English alphabet (both cases) 52 5.7
Base64 alphabet 64 6.0
List of 1,296 common words 1,296 10.3
List of 7,776 common words 7,776 12.9

Unless otherwise specified, tables in future sections list how many bits of entropy each symbol contributes if each symbol is chosen independently and randomly. Entropy decreases if some symbols aren't chosen independently or randomly.

Decimal Digits

There are 10 decimal digits (hence the name "decimal"):

0 1 2 3 4 5 6 7 8 9

Entropy

Assuming you generate each digit independently and randomly:

Digits Bits Digits Bits
413.2944146.16
826.5848159.45
1239.8652172.74
1653.1556186.03
2066.4460199.32
2479.7364212.60
2893.0168225.89
32106.3072239.18
36119.5976252.47
*40132.8880265.75
*: Highly secure against classical computers
: Highly secure against quantum computers

Generating with Ten-Sided Dice

Ten-sided dice are the easiest way to generate random decimal digits. Throw multiple dice at the same time to generate them faster. Ten-sided dice are cheap and easy to find online and in board game stores.

Generating with Six-Sided Dice

Suppose you throw two 6-sided dice, one red and one black. Use this table to figure out which decimal digit each throw generates:

Red
1 2 3 4 5 6
Black 1123456
2789012
3345678
4901234
5567890
6------

If the black die shows a 6, throw the dice again.

Probability of generating a digit: 5/6

Generating with Coins

The slowest way to generate decimal digits is with a coin. Flip a coin five times. Use this to figure out which decimal digit the five flips generate ('H' is heads, 't' is tails):

FlipsSymbolFlipsSymbolFlipsSymbol
ttttt0tHtHt0HtHtt0
ttttH1tHtHH1HtHtH1
tttHt2tHHtt2HtHHt2
tttHH3tHHtH3HtHHH3
ttHtt4tHHHt4HHttt4
ttHtH5tHHHH5HHttH5
ttHHt6Htttt6HHtHt6
ttHHH7HtttH7HHtHH7
tHttt8HttHt8HHHtt8
tHttH9HttHH9HHHtH9

If the first four flips are heads, ignore them and flip five times again.

You're essentially creating a five-digit binary number (where tails represents 0 and heads represents 1), converting it to decimal, and keeping the units digit.

Probability of generating a digit: 15/16

Generating with Poker Cards

You can also generate random digits with poker cards. Take a 52-card deck and remove the face cards and jokers, but keep the aces and 10's. There should be 40 cards left.

Shuffle the cards and draw them one at a time. Keep the first card of each suit you encounter and discard the rest. Stop once you keep one card of each suit. The ranks of the four cards you keep correspond to decimal digits:

CardDigit
Ace1
22
33
44
55
66
77
88
99
100

Reshuffle the cards after generating digits. If you don't, subsequent draws will make some digits more probable than others, reducing the password's entropy.

Example: Suppose you shuffle and draw the following cards:

Ace of spaces 3 of clubs 8 of clubs 8 of spades 5 of diamonds 4 of clubs 3 of hearts

You'd keep the four cards with yellow borders (the ace of spades, 3 of clubs, 5 of diamonds, and 3 of hearts) and generate the digits 1, 3, 5, and 3. Then you'd reshuffle the entire deck and repeat until you get all the digits you need.

Hexadecimal

Hexadecimal is commonly used in computer programming. It combines the decimal digits with the first 6 letters of the English alphabet, providing 16 symbols:

0 1 2 3 4 5 6 7 8 9 a b c d e f

Entropy

Assuming you generate each symbol independently and randomly:

Symbols Bits Symbols Bits
41636144
83240160
124844176
166448192
208052208
249656224
2811260240
*3212864256
*: Highly secure against classical computers
: Highly secure against quantum computers

Generating with Coins

Flip a coin four times. Convert the four flips into a hexadecimal symbol with this table ('H' is heads, 't' is tails):

FlipsSymbolFlipsSymbol
tttt0Httt8
tttH1HttH9
ttHt2HtHta
ttHH3HtHHb
tHtt4HHttc
tHtH5HHtHd
tHHt6HHHte
tHHH7HHHHf

Lowercase English Alphabet

There are 26 letters in the English alphabet:

a b c d e f g h i j k l m n o p q r s t u v w x y z

Entropy

Assuming you generate each letter independently and randomly:

LettersBitsLettersBitsLettersBits
523.5022103.4139183.32
628.2023108.1140188.02
732.9024112.8141192.72
837.6025117.5142197.42
942.3026122.2143202.12
1047.0027126.9144206.82
1151.70*28131.6145211.52
1256.4129136.3146216.22
1361.1130141.0147220.92
1465.8131145.7148225.62
1570.5132150.4149230.32
1675.2133155.1150235.02
1779.9134159.8151239.72
1884.6135164.5252244.42
1989.3136169.2253249.12
2094.0137173.9254253.82
2198.7138178.6255258.52
*: Highly secure against classical computers
: Highly secure against quantum computers

Generating with Six-Sided Dice

Suppose you throw two 6-sided dice, one red and one black. Use this table to figure out which English letter each throw generates:

Red
1 2 3 4 5 6
Black 1abcdef
2ghijkl
3mnopqr
4stuvwx
5yz----
6------

'-' means that you should roll the dice again.

Probability of generating a letter: 11/18

Generating with Coins

The slowest way to generate English letters is with a coin. Flip a coin five times. Use this to figure out which letter the five flips generate ('H' is heads, 't' is tails):

FlipsSymbolFlipsSymbolFlipsSymbolFlipsSymbol
tttttatHtttiHttttqHHttty
ttttHbtHttHjHtttHrHHttHz
tttHtctHtHtkHttHtsHHtHt-
tttHHdtHtHHlHttHHtHHtHH-
ttHttetHHttmHtHttuHHHtt-
ttHtHftHHtHnHtHtHvHHHtH-
ttHHtgtHHHtoHtHHtwHHHHt-
ttHHHhtHHHHpHtHHHxHHHHH-

'-' means that you should ignore the result and flip five times again.

Probability of generating a letter: 13/16

Generating with Poker Cards

You can also generate random letters with poker cards. Shuffle a deck and flip the top card. Ignore its suit. The card's color and rank correspond to a letter:

BlackRed
AceaAcen
2b2o
3c3p
4d4q
5e5r
6f6s
7g7t
8h8u
9i9v
10j10w
JackkJackx
QueenlQueeny
KingmKingz

Reshuffle the cards after generating a letter. If you don't, subsequent draws will make some letters more probable than others, reducing the password's entropy.

Another technique is to divide the 52 cards into two decks, each containing a red suit and a black suit (so 26 cards per deck), and to shuffle and draw from each deck separately. This might be faster than using a single deck.

Lowercase English Alphabet Plus Decimal Digits

Combining lowercase English letters and decimal digits gives 36 symbols.

Entropy

Assuming you generate each symbol independently and randomly:

SymbolsBitsSymbolsBitsSymbolsBits
525.8521108.5737191.29
631.0222113.7438196.46
736.1923118.9139201.63
841.3624124.0840206.80
946.53*25129.2541211.97
1051.7026134.4242217.14
1156.8727139.5943222.31
1262.0428144.7644227.48
1367.2129149.9345232.65
1472.3830155.1046237.82
1577.5531160.2747242.99
1682.7232165.4448248.16
1787.8933170.6149253.33
1893.0634175.7850258.50
1998.2335180.9551263.67
20103.4036186.1252268.84
*: Highly secure against classical computers
: Highly secure against quantum computers

Generating with Six-Sided Dice

Generating symbols with two 6-sided dice is easy. Suppose one is red and the other is black:

Red
1 2 3 4 5 6
Black 1abcdef
2ghijkl
3mnopqr
4stuvwx
5yz0123
6456789

Full English Alphabet

Combining uppercase (majuscule) and lowercase (miniscule) English letters gives 52 symbols.

Entropy

Assuming you generate each letter independently and randomly:

LettersBitsLettersBitsLettersBits
1057.0022125.4134193.81
1162.70*23131.1135199.52
1268.4124136.8136205.22
1374.1125142.5137210.92
1479.8126148.2138216.62
1585.5127153.9139222.32
1691.2128159.6140228.02
1796.9129165.3141233.72
18102.6130171.0142239.42
19108.3131176.7143245.12
20114.0132182.4144250.82
21119.7133188.1145256.52
*: Highly secure against classical computers
: Highly secure against quantum computers

Generating with Poker Cards

You can generate random English letters with poker cards. Shuffle a deck and flip the top card. Its suit and rank correspond to a letter:

CardSymbolCardSymbolCardSymbolCardSymbol
Aof clubsaAof diamondsAAof spadesnAof heartsN
2of clubsb2of diamondsB2of spadeso2of heartsO
3of clubsc3of diamondsC3of spadesp3of heartsP
4of clubsd4of diamondsD4of spadesq4of heartsQ
5of clubse5of diamondsE5of spadesr5of heartsR
6of clubsf6of diamondsF6of spadess6of heartsS
7of clubsg7of diamondsG7of spadest7of heartsT
8of clubsh8of diamondsH8of spadesu8of heartsU
9of clubsi9of diamondsI9of spadesv9of heartsV
10of clubsj10of diamondsJ10of spadesw10of heartsW
Jof clubskJof diamondsKJof spadesxJof heartsX
Qof clubslQof diamondsLQof spadesyQof heartsY
Kof clubsmKof diamondsMKof spadeszKof heartsZ

You can, of course, arrange the suits in any order you please in the above diagram.

If you reshuffle the entire deck after flipping a single card (generating one letter), each letter will supply 5.7 bits of entropy to your password. If you don't, subsequent draws will make some letters more probable than others, reducing the password's overall entropy. (See a similar scheme that trades entropy for fewer shuffles.)

Base64 Alphabet

Base64 is a 64-symbol alphabet:

ABCDEFGH
IJKLMNOP
QRSTUVWX
YZabcdef
ghijklmn
opqrstuv
wxyz0123
456789+/

Entropy

Assuming you generate each symbol independently and randomly:

SymbolsBitsSymbolsBitsSymbolsBits
5301911433198
6362012034204
7422112635210
848*2213236216
9542313837222
10602414438228
11662515039234
12722615640240
13782716241246
14842816842252
15902917443258
16963018044264
171023118645270
181083219246276
*: Highly secure against classical computers
: Highly secure against quantum computers

Generating with Eight-Sided Dice

The easiest to generate Base64 symbols is with two 8-sided dice. Suppose one is red and the other is black:

Red
1 2 3 4 5 6 7 8
Black 1ABCDEFGH
2IJKLMNOP
3QRSTUVWX
4YZabccef
5ghijklmn
6opqrstuv
7wxyz0123
8456789+/

Generating with Coins

The slowest way to generate Base64 symbols is with a coin. Flip a coin six times. Convert the first three flips and the last three flips into two numbers using this table ('H' is heads, 't' is tails):

ttt0
ttH1
tHt2
tHH3
Htt4
HtH5
HHt6
HHH7

Then convert those two numbers to Base64 as follows:

First Number
(First 3 Flips)
0 1 2 3 4 5 6 7
Second
Number
(Last
3
Flips)
0ABCDEFGH
1IJKLMNOP
2QRSTUVWX
3YZabccef
4ghijklmn
5opqrstuv
6wxyz0123
7456789+/

List of 1,296 Common Words

This "alphabet" is a set of 1,296 common English words (or words of any human language). Each word is counted as a symbol. Any list of words will do as long as there are no duplicates.

Passwords constructed from common words are easier to remember than long strings of random letters and numbers. They're also longer and thus slightly harder for hackers to guess.

Diceware is a password generation scheme that uses lists of 1,296 common words. The Electronic Frontier Foundation (EFF) published two such word lists. (copy of the EFF's first short list (13KiB))

Entropy

Assuming you generate each word independently and randomly:

WordsBitsWordsBits
441.3615155.10
551.7016165.44
662.0417175.78
772.3818186.12
882.7219196.46
993.0620206.80
10103.4021217.14
11113.7422227.48
12124.0823237.82
*13134.4224248.16
14144.7625258.50
*: Highly secure against classical computers
: Highly secure against quantum computers

Generating with Six-Sided Dice

Number each word in base six. The first word is 1111, the second is 1112, the sixth is 1116, the seventh is 1121, the eigth is 1122, and the last (1,296th) word is 6666.

To randomly pick a word, roll four 6-sided dice. Pick the word with the resulting number. For example, if your dice show "2545", pick word 2545.

List of 7,776 Common Words

This "alphabet" is a set of 7,776 common English words (or words of any human language). Each word is counted as a symbol. Any list of words will do as long as there are no duplicates.

Passwords constructed from common words are easier to remember than long strings of random letters and numbers. They're also longer and thus slightly harder for hackers to guess.

Diceware is a password generation scheme that uses lists of 7,776 common words. Both the author of Diceware (Arnold G. Reinhold) and the Electronic Frontier Foundation (EFF) published word lists. (copy of the EFF's long list (106KiB))

Entropy

Assuming you generate each word independently and randomly:

WordsBitsWordsBits
338.7712155.10
451.7013168.02
564.6214180.95
677.5515193.87
790.4716206.80
8103.4017219.72
9116.3218232.65
*10129.2519245.57
11142.1720258.50
*: Highly secure against classical computers
: Highly secure against quantum computers

Generating with Six-Sided Dice

Number each word in base six. The first word is 11111, the second is 11112, the sixth is 11116, the seventh is 11121, the is eigth 11122, and the last (7,776th) word is 66666.

To randomly pick a word, roll five 6-sided dice. Pick the word with the resulting number. For example, if your dice show "32545", pick word 32545.

Alternative Password Generation Schemes

These ways to generate passwords have less entropy than the systems outlined in earlier sections because the resulting passwords' symbols aren't generated independently.

Generate English Letters with Poker Cards Shuffled Once

Thoroughly shuffle a deck of 52 cards (excluding jokers). Draw cards one at a time. Each card's suit and rank correspond to an English letter, which can be lowercase (miniscule) or uppercase (majuscule):

CardSymbolCardSymbolCardSymbolCardSymbol
Aof clubsaAof diamondsAAof spadesnAof heartsN
2of clubsb2of diamondsB2of spadeso2of heartsO
3of clubsc3of diamondsC3of spadesp3of heartsP
4of clubsd4of diamondsD4of spadesq4of heartsQ
5of clubse5of diamondsE5of spadesr5of heartsR
6of clubsf6of diamondsF6of spadess6of heartsS
7of clubsg7of diamondsG7of spadest7of heartsT
8of clubsh8of diamondsH8of spadesu8of heartsU
9of clubsi9of diamondsI9of spadesv9of heartsV
10of clubsj10of diamondsJ10of spadesw10of heartsW
Jof clubskJof diamondsKJof spadesxJof heartsX
Qof clubslQof diamondsLQof spadesyQof heartsY
Kof clubsmKof diamondsMKof spadeszKof heartsZ

The password's randomness (entropy) will be less than if you were to shuffle the entire deck every time you draw a card, but you'll only have to randomize the deck once.

Here's how much entropy your password will have based on this scheme:

Cards Drawn
(Password Length)
Entropy
(Bits)
Cards Drawn
(Password Length)
Entropy
(Bits)
15.727141.9
211.428146.5
317.029151.1
422.630155.7
528.231160.1
633.832164.5
739.333168.8
844.834173.1
950.235177.2
1055.736181.3
1161.137185.3
1266.438189.2
1371.739193.0
1477.040196.7
1582.341200.3
1687.542203.8
1792.743207.1
1897.844210.3
19102.945213.3
20107.946216.1
21112.947218.7
22117.948221.0
23122.849223.0
24127.650224.6
*25132.451225.6
26137.252225.6
*: Highly secure against classical computers
: Secure against quantum computers
: Highly secure against quantum computers

If you reshuffle after drawing some cards, you'll increase the entropy, reducing the number of letters you'll need to generate a password with specific amount of entropy. You'll achieve maximum entropy — 5.7 bits per letter — if you reshuffle every time you draw a card; this is the English alphabet scheme described further above.

How Many Passwords Should I Create?

Ideally, each of your accounts would have a different password. That way a hacker who breaks into one account or service you use can only access that account with the stolen password.

But most of us have at least a dozen accounts; some have several dozen. That's a lot of passwords to remember!

Some people compromise by distinguishing between critical, sensitive, and throwaway accounts and services. They give each critical account or service its own highly-secure password, each moderately sensitive account its own moderately-secure password, and all throwaway accounts the same moderately-secure password. What "sensitive", "moderately sensitive", and "throwaway" mean are up to the user. This is the solution I use.

Other people create a few highly-secure password prefixes. For each account, they combine one of the prefixes with a memorable (not necessarily random) suffix to get a password. This makes it much easier to remember one's passwords, but if an attacker can guess that you're using this scheme, he'll have a much easier time breaking into your other accounts after learning one of your passwords.


The Mathematics of Password Generation

Fortunately, password generation doesn't rely on complicated mathematics. You can calculate a system's entropy using grade school and middle school math.

Information Entropy

The amount of entropy each symbol contributes to a password (if chosen randomly and independently) is

log2 N

where "log2" is logarithm base 2 and N is the size of the password's alphabet.

Why is this so? Imagine how you could randomly pick one symbol out of an alphabet of N symbols. One very general way to do so is to assign each symbol a number from 0 to N-1. For example, if your alphabet is the lowercase English letters (N=26), you could do this:

LetterNumberLetterNumber
a0n13
b1o14
c2p15
d3q16
e4r17
f5s18
g6t19
h7u20
i8v21
j9w22
k10x23
l11y24
m12z25

Then you could flip a coin multiple times, convert the flips into a binary number (1's and 0's), convert the binary number to a base ten number (our everyday counting system), and pick the letter associated with that number. For example, if you were to use the table above and flip tails, heads, heads, tails, and tails, you'd convert the five flips into the binary number "01100", which is "12" in base ten, which corresponds to the digit "m" in the table. If the generated number isn't assigned to any symbols in your alphabet, keep generating numbers until you pick a symbol. It's easy to see that this scheme makes choosing each symbol equally likely.

Assuming you only have to generate one binary number to pick a symbol, how many times would you have to flip a coin to pick a symbol? (In other words, how many digits would the binary number have to have?) The answer is the symbol's contribution to the password's entropy. Remember, a coin flip has 1 bit of entropy. If it takes 5 coin flips to randomly pick a symbol out of an alphabet, the symbol's entropy contribution is 5 bits. Therefore, given that

2^x = N

which states that it takes x coin flips to randomly pick one of N symbols,

x = log2 N

x is each symbol's entropy.

Note that x will be fractional unless N is a power of 2. There are 26 lowercase English letters, so each letter contributes

x = log2 N = log2 26 = 3.26

bits if chosen independently and randomly.

Another way to measure a password generation system's entropy is to look at how many different passwords it can generate. Assuming the system can generate M different passwords and each one is equally likely (that is, each password is chosen independently and randomly), ask, "How many coin flips would it take to randomly select one of the M passwords?" The answer is the system's information entropy in bits. If there are M possibilities, the password generator's entropy is

log2 M

Note that if you choose one of N symbols independently and randomly m times (so that M = Nm; see "The Rule of Product" below), the resulting entropy will be

log2 M = log2 (N^m) = m log2 N

which is the same as saying that the system's entropy is m times the entropy contribution of each randomly-selected symbol.

The Rule of Product

The mathematical foundations of password systems and password strength come from combinatorics, the study of arrangements. It rests on a few simple counting principles. One that's particularly important for passwords is the rule of product.

Suppose you can choose one of A things followed by one of B things. How many combinations of one A thing and one B thing are there?

For example, if A is the letters {X, Y} and B is the numbers {1, 2, 3, 4}, then there are two choices for A and four for B. The AB combinations are:

X1 X2 X3 X4
Y1 Y2 Y3 Y4

There are eight combinations. Notice that this is the size of A times the size of B: 2 x 4.

This observation generalizes to all sets A and B:

The total number of combinations of one A thing followed by one B thing is |A| x |B|.

Here "|A|" means "the number of things in A" or "the size of A".

What if you choose one from each of three sets A, B, and C? The total number of combinations is |A| x |B| x |C|. Why does this work? If we define a fourth set D as the set of combinations of one B thing followed by one C thing, then D has |B| x |C| things. Now, how many combinations of one A thing and one D thing are there? The answer is:

|A| x |D| = |A| x (|B| x |C|)
	  = |A| x  |B| x |C|

To see how this applies to password generation, suppose you make the lowercase English letters your password alphabet. Let's call this alphabet A. The alphabet has 26 letters, so |A| = 26. If you were to generate a single-letter password, there would only be 26 possible passwords. But if you randomly choose two letters, there would be

|A| x |A| = 26 x 26 = 262 = 676 possible passwords

The possibilities grow exponentially as you add more letters:

Number of LettersNumber of Possible Passwords
1261 = 26
226 x 26 = 262 = 676
326 x 26 x 26 = 263 = 17,576
......
n|A|n

So if you randomly and independently choose n letters, there would be |A|n possible passwords.

Permutations

Suppose you have a set of things. We'll call the set A. Each thing in A is unique. How many arrangements of those A things are there? In other words, if you had to arrange everything in A into a line, how many possible lines would there be?

Each of these arrangements is called a permutation. Counting permutations relies on the rule of product.

Let's use poker cards as an example. There are 52 cards in a standard poker deck (excluding jokers). If we line all the cards up (to form a permutation), we'd have to start by deciding which card comes first. There are 52 choices. Once we choose the first card, we'll have 51 choices for the second. And once we choose the second card, we'll have 50 choices for the third. This continues until we have only one card left, which becomes the final card.

Each position in this line acts like a set of choices. The first position has 52 card choices; the second, 51; the third, 50; and so on. What's the total number of choice combinations? Using the rule of product, there are

  |1st| x |2nd| x |3rd| x ... x |51st| x |52nd|
=   52   x  51   x  50  x ... x    2   x    1   permutations

Mathematicians write "52!", read "52 factorial", to signify these multiplications. So the number of permutations of a standard 52-card poker deck is 52!, which is

80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000

There are more permutations of poker cards than there are atoms in the observable Universe! This number is so huge that it's unlikely that any two games of poker (or any other game using poker cards) were ever played with exactly the same deck of well-shuffled cards.

We generalize this by saying:

The number of permutations of a set of X distinct things is "|X|!", or

|X| x (|X|-1) x (|X|-2) x ... x 1

Mathematicians say that 0! = 1. This makes some calculations more convenient.

What if you need to form a permutation with fewer than X things? Let's use the poker cards again. If you need to form a permutation of five cards, there would be

  |1st| x |2nd| x |3rd| x |4th| x |5th|
=   52  x   51  x   50  x   49  x   48  permutations

This is like forming a permutation with all 52 cards but ignoring the last 47. How can we express this mathematically? Well, looking back on grade school and middle school, you might remember that dividing a number by itself effectively "cancels" it. For example:

(2x6)/6 = (2x1)/1 = 2

Notice that the sixes "cancel" each other, leaving the 2.

For our permutation of five poker cards, we want to form a permutation of all 52 cards and "cancel" the permutation of the last 47 cards. There are 47! permutations of 47 cards, so the number of permutations of five cards is

52!/47!

We generalize this result by saying:

The number of permutations of n of x distinct things is

xPn = x!/(x-n)!

xPn is a convenient shorthand for this number.

Let's apply this to password generation. Recall the alternative poker card password system in which you assign each of 52 poker cards a different English letter (uppercase or lowercase), shuffle the deck, draw n cards, and use the resulting arrangement of n letters as your password. This is a permutation of n of 52 cards, so there are 52Pn possible passwords. The system's entropy is thus

log2 52Pn

(Recall the "Information Entropy" section for this formula.) Clearly, the more cards you choose after shuffling, the more entropy the system will have.