Clock drift

From Wikipedia, the free encyclopedia

Clock drift refers to several related phenomena where a clock does not run in the exact right speed compared to another clock. That is, after some time the clock "drifts apart" from the other clock.

This phenomenon is also used for instance in computers to build random number generators.

[edit] Clock drift in normal clocks

Normal clocks such as clocks at home and wristwatches usually drift compared to the actual time. That is why one must reset their time periodically. Clocks often drift differently depending on their quality, the exact power they get from the battery, the surrounding temperature and so on. Thus the same clock can have different clock drift rates at different occasions.

More advanced clocks and old mechanical clocks often have some kind of speed trimmer where one can adjust the speed of the clock and thus reduce the clock drift. For instance, in pendulum clocks the clock drift can be manipulated by slightly changing the length of the pendulum.

[edit] Atomic clocks, the Earth and relativity

Atomic clocks are very precise and have nearly no clock drift at all. The rotation of the Earth itself actually has more clock drift (less accuracy) than modern atomic clocks. Thus to keep the Coordinated Universal Time (UTC) in line with the Earth's rotation some years a leap second has to be added.

As Einstein predicted clock drift can also occur in any clock when they are moved to new locations or travel at high speed due to relativistic effects. For instance the atomic clocks in GPS satellites experience this effect.

[edit] Random number generators

Computer programs often need good random numbers, especially when doing cryptography. There are several similar ways clock drift can be used to build random number generators (RNGs).

One way to build a hardware random number generator is to use two independent clock crystals, one that for instance ticks 100 times per second and one that ticks 1 million times per second. On average the faster crystal will then tick 10000 times for each time the slower one ticks. But since clock crystals are not precise the exact number of ticks will vary. That variation can be used to create random bits. For instance if the number of fast ticks is even a 0 is chosen, and if the number of ticks is odd a 1 is chosen. Thus such a 100/1000000 RNG circuit can produce 100 truly random bits per second. Note that care has to be taken so the RNG does not become biased, otherwise it might for instance produce more 0s than 1s.

There is also a similar way to build a kind of "software random number generator". This involves comparing the timer tick of the computer (the tick that usually is 100 times per second) and the speed of the CPU. If the computer timer and the CPU run on two independent clock crystals the situation is ideal and more or less the same as the previous example. But even if they both use the same clock crystal the process/program that does the clock drift measurement is "disturbed" by many more or less unpredictable events in the CPU such as interrupts and other processes and programs that runs at the same time. Thus the measurement will still produce fairly good random numbers. (Some argue they are then not true random numbers but they seem to be good enough for most needs.)

The pseudocode below shows a "software random number generator" that produces 256 random bits and that loads the CPU fully for about 1/3 of a second. This assumes the system tick is 100 times per second and a fairly fast modern computer where the number of loops per tick will be high so each loop will vary with at least 8 bits worth of randomness. The measurement is done 32 times (during 32 separate ticks), each time producing 8 bits of randomness.

(* Code for a software random number generator. *)

var  RNGarray: array[0..31] of byte;   (* An array of 32 bytes. *)

(* Do 32 clock drift measurements. *)
for x := 0 to 31 do begin

  tick := clock();

  (* Count loops until the next tick. *)
  loop := 0;
  while clock() = tick do begin
    loop := loop + 1
  end; (* tick loop *)

  (* Use the lower 8 bits since those are the ones that vary wildly. *)
  RNGarray[x] := loop modulo 256

end (* index loop *)

(* The RNGarray now contains 256 random bits. *)

Note that most hardware random number generators such as the ones described above are fairly slow. Therefore most programs only use them to create a good seed that they then feed to a pseudorandom number generator or a cryptographically secure pseudorandom number generator to produce many random numbers fast.