Password Cracker
You’re a hacker (an ethical one, of course) who’s trying to figure out someone’s password. You decide on a brute-force approach and write some code that produces every possible string of a given length. Here’s the code you whipped up:
| | from string import ascii_lowercase |
| | import itertools |
| | |
| | |
| | def every_password(length): |
| | for s in itertools.product(ascii_lowercase, repeat=length): |
| | print("".join(s)) |
In our code, we’ve imported the entire alphabet using ascii_lowercase from Python’s string module so we don’t have to actually type out the entire alphabet. We’ve also used Python’s itertools module to allow us to run an arbitrary number of nested loops with minimum code.
In truth, we’re not going to focus on how this code works, but rather what this code does.
When we call the every_password function, we pass in an integer, which becomes the variable length.
If length is 3, the code will return all possible strings within the range of "aaa" and "zzz". Running this code will print the following:
| | aaa |
| | aab |
| | aac |
| | aad |
| | aae |
| | |
| | ... |
| | |
| | zzx |
| | zzy |
| | zzz |
If length is 4, your code will print all possible strings of length 4:
| | aaaa |
| | aaab |
| | aaac |
| | aaad |
| | aaae |
| | |
| | ... |
| | |
| | zzzx |
| | zzzy |
| | zzzz |
If you try running this code even for a mere length of 5, you may be waiting some time for it to finish. This is a slow algorithm! But how do we express it in terms of Big O?
Let’s break it down.
If we simply print each letter from the alphabet once, it would take 26 steps.
When we print every two-character combination, we end up with 26 characters multiplied by 26 characters.
When printing every three-character combination, we end up with 26 * 26 * 26 combinations.
Do you see the pattern?
Length | Combinations |
|---|---|
1 | 26 |
2 | 262 |
3 | 263 |
4 | 264 |
If we look at this in terms of N, it emerges that if N is the length of each string, the number of combinations is 26N.
Therefore, in Big O notation, we express this as O(26N). This is an utterly glacial algorithm! The truth is that even an algorithm that is a “mere” O(2N) is incredibly slow. Let’s see how it looks on a graph, shown, compared to some of the other algorithms we’ve seen so far.
As you can see, O(2N) gets even slower than O(N3) at a point.
In a certain sense, O(2N) is the opposite of O(log N). With an algorithm of O(log N) (like binary search), each time the data is doubled, the algorithm takes one additional step. With an algorithm of O(2N), each time we add one element of data, the algorithm doubles in steps!
In our password cracker, each time we increase N by one, the number of steps get multiplied by 26. This takes an incredible amount of time, which is why brute force is such an inefficient way to crack a password.
