Cryptography Reference
In-Depth Information
corrections. In some cases, these modifications introduce only a few
changes to the file and the error-correcting codes can recover them.
This additional strength is hard to measure because there is no easy
way to predict the damage waiting for the file.
On occasion, it makes sense to split a message into a number of
different parts to be shipped through different channels. Ideally, the
message could be reconstructed if a few of the parts have been com-
promised along the way. The part could either be lost or scrambled
by a malicious courier. In either case, error-correcting codes can de-
fend against this problem.
Better secret splitting
solutions are found
in Chapter 4.
A system of error-correcting codes comes in any number of fla-
vors. Many of the most commonly used codes have the ability to
carry
k
bits in a packet of
n
bits and find the right answer if no more
than
errors have been made. There are many possible codes that
come with different values of
m
, but you never get anything
for free. If you have 7 bits and you want each block to carry at least
4 bits of information, then one standard code can only correct up to
one error per block. If you want to carry 6 bits of information in a 7-
bit block, then you can't successfully correct errors and you can only
detect them half of the time.
The best metaphor for understanding error-correcting codes is to
think about spheres. Imagine that each letter in a message is repre-
sented as the center of a sphere. There are 26 spheres for each letter
and none of them overlap. You send a message by sending the coor-
dinates to this point at the center. Occasionally a transmission glitch
might nudge the coordinates a bit. When the recipient decodes the
message, he or she can still get the correct text if the nudges are small
enough so the points remain inside the sphere. The search for the
best error-correcting codes involves finding the best way to pack the
spheres so that you can fit the most spheres in a space and transmit
the most characters.
Although mathematicians talk about sphere packing on an ab-
stract level, it is not immediately obvious how this applies to the digi-
tal world where everything is made up of binary numbers that are on
or off. How do you nudge a zero a little bit? If you nudge it enough,
when does it becomes a one? How do you nudge a number like 252,
which is 11111100 in binary? Obviously a small nudge could convert
this into 111111101, which is 253. But what if the error came along
when the first bit was going through the channel? If the first bit was
changed the the number would become 011111100. That is 114, a
change of 128, which certainly doesn't seem small. That would imply
that the spheres really couldn't be packed too closely together.
The solution is to think about the bits independently and to mea-
k
,
n
,and
m
