This Month's Feature Column

Crypto Graphics

Mail to a friend

Print this article

Introduction

A new generation of `bar codes' is becoming ubiquitous, at least in the Western world. One principal motivation for this has been to foil counterfeiting, for example the counterfeiting of postage stamps. Many countries of Europe as well as Canada and the United States have implemented this scheme, although details vary from one country to the next.

In the near future, all pharmaceutical products sold in Europe will require similar authentication. There are other uses in packaging as well, although it is not clear to me what their purpose is.

In addition, correspondence from the IRS frequently includes data matrices but here, too, the purpose is not known to me.

Data matrices are not actually bar codes, which are one-dimensional. Instead, they (as well as nearly all of the new generation of similar code schemes) present a rather complicated 2D array. There are other candidates for 2D coding, but data matrices are among the most interesting. The advantage of 2D over 1D should be obvious - a 2D array can pack much more information in a small space. There is so much capacity, in fact, that there is room for extra bits of information to allow efficient error correction, which is a tremendous advantage. The largest allowable data matrix has dimensions 144 x 144, and allows 1558 bytes of message to be transmitted, with up to 620 errors correctable. This is an impressive amount of information. Looking at the sample images of postage stamps above, where cancellation and poor printing quality clearly causes trouble, will convince you that the system wouldn't be at all feasible without error correction.

In reading a data matrix, there are several layers that have to be peeled away and interpreted, and in many - for example postage and pharmaceutical authentication - the final layer to be seen is encrypted at the most sophisticated level of security currently available. In this article, I'll just describe how to unpack the simplest outermost level.

Bill Casselman
University of British Columbia, Vancouver, Canada
cass at math.ubc.ca