1

Recently I have seen many people using a pattern on a ten digit keypad to unlock their mobile device. This got me thinking about the effectiveness of such a security measure. My first instinct was that this is less secure than an equal length PIN. Since for a pattern you must move to an adjacent number, whereas with a PIN you can move to any of ten numbers, the number of possible combinations decreases.

This site is full of brilliant mathematical minds and I would love to see a proof of the difference in possibilities between a PIN and pattern of length X. A little bit of combinatorical magic perhaps.

Dan
  • 143

1 Answers1

3

The number of possible PINs of length $x$ is $10^x$, as we have ten choices for each digit, and none of these choices depend on the other choices.

The total number of patterns is more difficult to calculate. I do not see an easy way to find a closed form for the total number of patterns of length $x$. However, I can easily compute the number of patterns of length $x$ for a specific $x$.

We start by representing the keypad as a graph, where the vertices are the keys, and there is an edge between any two vertices if and only if the keys they represent are adjacent. This is what I believe the graph of a keypad would look like:

http://sagenb.org/home/khalasz23/95/cells/33/sage0.png?6738636834295600943

The number of patterns of length $x$ is then the total number of paths of length $x-1$ on this graph, where we take the order of the vertices of a path into account. It is very easy to count the total number of paths of any given length in a graph using its adjacency matrix. The adjacency matrix of a graph is a (0,1)-matrix $M$, where given a labeling of the graph, $M_{i,j}$ is $1$ if there is an edge between vertex $i$ and vertex $j$ and is $0$ if there is not. The adjacency matrix of our graph is:

$\left(\begin{array}{rrrrrrrrrr} 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \end{array}\right)$.

If we square this matrix, we see that $M^2_{i,j}$ counts the number of paths of length 2 from vertex $i$ to vertex $j$, as $M^2_{i,j} = \sum_k M_{i,k} M_{k,j}$, so we are simply counting the number of times there is both an edge between vertex $i$ and vertex $k$ and an edge between vertex $k$ and vertex $j$.

This process generalizes to further powers of the matrix, i.e. $M^n_{i,j}$ counts the number of paths of length $n$ from vertex $i$ to vertex $j$.

So, if we sum up every value in the $nth$ power of the adjacency matrix we get the total number of paths with respect to the order of the vertices, or, the total number of patterns. (If we took the traditional approach and didn't take the order of vertices in a path into account, we would have to turn the diagonal to all 0s, divide the sum of all values by 2, then count all of the $n$-cycles in the graph. As you can see, the given problem makes the calculations much simpler.)

For example, $M^0$ is the $10 \times 10$ identity matrix. The sum of all the entries in this matrix is $10$, and we see that there are ten patterns of length $1$, i.e. consisting of pressing just one button.

Letting $a_k$ denote the total number of patterns of length $k$. Then, I have used Sage to compute the first ten values of the sequence: $\{a_k\}_{k=1}^{10} = 46,234,1160,5806,28946,144558,721402,3601260,17975020,89724802$. We see that $a_{k+1}$ is roughly equal to $5a_k$.

So, while there are $10^x$ PINs of length $x$, there are roughly $(46)5^{x-2}$ patterns of length $x$. The ratio of patterns to PINs, of length $x$, is then $\frac{1}{2^{x-1}}$. Therefore, we can see that patterns are significantly less secure than PINs.

KcH
  • 738