Disguising a Message
Because one aim of steganography is to hide messages in public places, it is helpful to disguise one's message. If it is part of a vector figure and one is jittering the coordinates, for example, then it would be good to make the jittered coordinates look no different than the original ones.
If a figure has undergone a series of GIS operations, such as topological cleaning, snapping, projection, and so on, then it is likely the least significant digits of its coordinates will look pretty random. Even if they don't, we could randomly jitter the coordinates we are not using for our message, just to ensure that all the coordinates look about the same.
So the trick lies in finding a way to disguise a message in such a way that changes made to it while it is in the channel can be detected and reversed. This turns out to be easy.
Disguise a message with a mask
The technique I use is to generate an essentially infinite series of pseudo-random bits starting with a known "seed" created from a password. These bits mask the message. There are several ways to do this. I chose the simple XOR operation. This operation interprets bits as "odd" and "even"--one is odd and zero is even--and adds them in the usual way: odd + even = odd, even + even = even, and odd + odd = even. The first random bit masks the first message bit, the second random bit masks the second message bit, and so on.
This operation has the very nice property that masking the disguised message exposes the original message, so it's not necessary to write a separate un-disguise routine. Furthermore, if a single bit is altered in the channel, then only the corresponding bit in the undisguised message is changed. This means that the process of disguise-transmit-undisguise does not mess up any error correction mechanism built into the message itself.
There are good ways to generate pseudo-random sequences. Unfortunately, most software, especially GIS software, does not use good methods. Therefore I had to implement a good pseudo-random number generator (RNG) from scratch.
Arithmetic for random number generation
The arithmetic is easy, but there's one complication: even in the simplest cases, it typically involves multiplying integers that can get as large as 2^31-2 (about two billion: 2*10^9). When you multiply two of those, you get results almost as large as 2^62. This will overflow the registers of any 32-bit computer and will not even fit into a double precision float. (Internally, Intel CPUs and their clones keep track of such integer overflows, so if you are programming at a low level, in C or Assembly language for instance, there is no problem.)
For example, in any language that uses double precision floating point values for numbers, 99,999,999 * 99,999,999 is equal to 9,999,999,800,000,000, which clearly is wrong because the product of two numbers ending in 9 must end in 1. Although the discrepancy is tiny, it will totally ruin any RNG algorithm.
The solution is to represent integers in the range 0..2^31 as pairs of smaller integers. I chose to represent them in the form a + b*2^16 where both a and b are less than 2^16 themselves. In effect, I implemented a system to add and multiply two-digit numbers to the base 2^16. I used the familiar algorithms of elementary school arithmetic, with one twist: the RNG algorithms only need the remainders upon division by 2^31-1.
For example, to add two of these numbers, notice that
(a + b*2^16) + (c + d*2^16) = (a+c) + (b+d)*2^16.
In the result, a+c and b+d could both be as large as 2^17, so in principle we might have to write
a+c = m*2^16 + n
where m is either 0 or 1 and n is less than 2^16. In effect, m is the "carry". So we then have
a+c + (b+d)*2^16 = n + (b+d+m)*2^16.
Now we inspect (b+d+m) and write it as
b+d+m = j*2^16 + k
where j is either 0 or 1. This is the second carry. Expanding everything we get
n + k*2^16 + j*2^32.
Now dividing 2^32 by 2^31-1 leaves a remainder of 2. Performing this division on the previous number must therefore give a remainder of
(n+2*j) + k*2^16
If we started out with two numbers each less than 2^31-1, then we can check that n+2*j does not exceed 2^16-1, so this result is in its final form.
Multiplication is not much harder.
If you would like to see the details, the arithmetic needed for random number generation is contained in four very short, heavily-commented procedures:
Number.AsPoint: Put a number into its a + b*2^16 representation modulo 2^31-1. (Six lines.)
Point.AsNumber: Express a value of the form a + b*2^16, modulo 2^31-1, as an ordinary number. (Three lines.)
Point.Add, Point.Multiply: Add and multiply modulo 2^31-1. (Two lines, twelve lines.)
Good random number generators
The RNGs themselves are "Multiple Recursive Generators" as described at http://crypto.mat.sbg.ac.at/results/karl/server/node7.html. They are a form of Fibonacci sequence. This is the familiar sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 144, ... found in mathematics and in many natural forms (the "golden mean" and sunflower spirals, for instance). The rule for making this sequence is simple: its "seeds" are 0 and 1, then each successive value is the sum of the preceding two: 1 = 0+1, 2 = 1+1, 3 = 1+2, etc.
The Fibonacci sequence is readily generalized in three ways:
- You can start with different seeds. For instance, using 1 and 3 to start instead of 0 and 1 gives the Lucas numbers 1, 3, 4, 7, 11, 18, 29, ... .
- Instead of just summing the previous two values, form a linear combination using fixed coefficients. For instance, you could take three times the previous plus twice its predecessor. This would give the sequence 0, 1, 3, 11, 39, 139, ... .
- You can extend the idea to include more than two previous values. For instance, sum the previous three values. (You will need more seeds, of course.) An example using seeds 0, 0, and 1 is 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, ... .
An MRG is obtained by using all three generalizations: generate seeds from a password, use the linear combination idea of #2, and use two or more previous values to generate the next (idea #3). At every step, retain only the remainder after dividing by some fixed value, m, often equal to 2^31-1.
If you use k previous values in #3, where k=2, 3, 4, or even larger, and choose "good" values for the coefficients in #2 (there is an art to finding values that make random-looking sequences: it won't do to take just any coefficients!), then the sequence can go for as long as m^k-1 values before it repeats. For example, with k=6 and m = 2^31-1, m^k-1 is greater than 10^55: an exceedingly large number indeed.
As a bonus, there are some MRGs with large values of k for which most of the coefficients are zero, meaning the multiplication is easy. I chose five of these for k = 2, 3, 4, 5, and 6. As a matter of notation, let x be the next value in the sequence, x[1] be the current value, x[2] be its predecessor, and so on. Here are the MRGs I implemented:
k=2: x = 1498809829*x[1] + 1160990996*x[2]
k=3: x = 65338*x[1] + 64636*x[3]
k=4: x = 64886*x[1] + 65322*x[4]
k=5: x = 107374182*x[1] + 104480*x[5]
k=6: x = 177786*x[1] + 64654*x[6]
Remember, the two multiplications and addition at each step are performed and then the remainder modulo 2^31-1 is computed, using the procedures described above.
The sequences of numbers generated in this fashion are converted to binary to make the sequences of pseudorandom mask bits. The execution speed is reasonably fast. Only two short procedures are needed: one to create the MRG from its coefficients and seeds, the other to generate the next value. They are available on the MRG Procedures page.
--William A. Huber, Spring 2002
