Cryptography Reference
In-Depth Information
(The 7-bit code frompage 47 shows how you can split up a secret into
seven parts so that it can be recovered if any six parts are available.)
There are numerous problems with this approach. First, some
bits are often more privileged than others. In the 7-bit scheme from
page 47 in Chapter 3, four of the seven bits hold the original message.
The other three are parity bits. If the right four are put together, then
the original secret is unveiled. If one of these bits ismissing, however,
then the parity bits are needed to get the secret.
Second, there can be some redundancy that allows people to un-
veil the secret even if they don't hold all of the parts. For instance, the
3-bit error-correcting code described on page 40 can recover the cor-
rect answer even if one of the three bits is changed. This is because
each bit is essentially turned into three copies of itself. If these three
copies are split into three parts, then they won't prevent each person
from knowing the secret. They have it in their hands. Their part is an
exact copy of the whole. This is an extreme example, but the same
redundancies can exist in other versions.
Deliberately adding
errors is one way to
prevent this.
A better solution is to use algorithms designed to split up secrets
so thatthey can't be recovered unless the correct number of parts
is available. Many different algorithms are available to do this, but
most of them are geometric in nature. This means that it is often
easy to understand themwith figures and diagrams.
4.2.1 Requiring All Parts
Many of the algorithms described later in this section can recover a
secret split into
parts are available. There are many
times when youmight want to require that all parts be present. There
are good algorithms that work quite well when
n
parts if only
k
n
=
k
,butarenot
flexible to handle cases when
. These basic algorithms
are described here before the other solutions are explained.
k
is less than
n
Repeating the same
encryption function
again and again can
introduce some
theoretical problems
and make analyzing the
system tricky.
One approach is to imitate safe deposit boxes and use
n
layers of
encryption. If
k
i
,thenyou
can take the secret and encrypt it repeatedly with each of
f
(
k
i
,X
)
encrypts a message
X
with key
n
different
keys. That is, compute:
f
(
k
1
,f
(
k
2
,f
(
k
3
,...f
(
k
n
,X
)
...
)))
.
Each person gets one of the
keysanditshouldbeobviousthat
the secret can't be recovered unless all of them are present. If one is
missing, then the chain is broken and the layers of encryption can't
be stripped off.
A simpler approach is to think of the secret as a number,
n
X
,and
thensplititinto
n
parts that all add up to that number,
X
1
+
X
2
+
