Numb3rs 202: Bettor or Worse

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.

Rolling Codes

The method actually used in remote entry devices is somewhat more complicated than the examples described here. For more information about this method, and the history of attacks on it, see Keeloq

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 ai to denote the ith output, ai+1 = ai + 1 is a recursive formula. If a0 = 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.

Modular Arithmatic
Our new rolling code will be given by taking a number, squaring it, and modding out by n (modding out means taking the remainder under division).
This can be rewritten as ai+1 = ai2 mod n
  • Does this generally generate a better code for larger n or smaller n? Why?
  • Which inputs make for the shortest periods, and which inputs make for the largest?

    • A Different Sort of Rolling Code
      Take a number of length n and square it, adding zeroes at the beginning if neccesary to obtain a number of length 2n+1. Take the middle n digits of this number as the output.