In this episode, Charlie tries to identify a crimal via the car keys in her purse. He explains that the remote used to unlock a car from a distance will be difficult to trace since it uses a rolling code. After all, if a remote entry device were to transmit the same signal each time, it would be a relatively simple manner for a thief to intercept and duplicate said signal. Instead, car keys use a mathematical algorithm to send a different n digit number each time the button is pressed, which the locking mechanism can identify as right or wrong.
The goal of a rolling code is to use a structured formula to change an n-digit number over time. A number of formulas for this change will be recursive. A formula is recursive if the output at a given time depends on previous outputs. For example, if we use a_{i} to denote the ith output, a_{i+1} = a_{i} + 1 is a recursive formula. If a_{0} = 12, the resulting sequence of outputs will be 13, 14, 15, 16, etc.
Another common recursive formula is used to generate the Fibbonacci sequence. The sequence begins with the numbers 0 and 1. Each successive number is the sum of the previous two. The sequence thus continues 0, 1, 1, 2, 3, 5, 8, 13, 21...etc.
Recursive formualas make for good rolling codes, as a thief would generally need to figure out the recursive formula, the initial input, and the number of iterations that have occured in order to predict the next output. However, to use practically, a sequence cannot be simply increasing as above- the remote key and car would eventually be overloaded by the length of the digits. Thus, the function must somehow control the length of outputs.
Modular arithmatic is frequently used to control the length of numbers in computer science. Some of you may be familiar with the term 'modulus' from programming or 'clock arithmatic'. In modular arithmatic, integers that differ by a given positive number are considered equal. For example, 0 = 4 = 8 = 12 mod 4. Similarly, 1 = 7 = 13 = 19 mod 6. You can use modular arithmatic to find shorter expressions of numbers If you are working mod n, simply take the remainder of each number under division by n. The resulting numbers will, in particular, all be smaller than n.
One problem with rolling codes described by recursive functions such as these is a finite period. If a code depends only on the previous output, then as soon as the code repeats a single output, it must cycle. Watch out for this problem while working with your rolling codes.