Cryptography Reference
In-Depth Information
Here's a basic algorithm for constructing
K
from a list of
m
pass-
words,
P
1
,P
2
, ···P
m
. Repeat this for each password,
P
i
.
1. Let
K
i
=
H
(
P
i
)
,where
H
is some cryptographically secure hash
function.
2. For all
K
j
⊕K
i
. This orthonormalization
step removes the part of the previous vectors that overlaps with
the new row. That is, it ensures that there will only be an even
number of bits that are one in both rows. It does this for all
previous values.
j<i
,let
K
i
=(
K
i
·K
j
)
3. If
K
i
=0
, then an error has occurred. The new chosen key is
not independent of the previous keys. Set
P
i
))
and
try again. Continue to hash the password until an acceptable
value of
K
i
=
H
(
H
(
K
i
is found that is orthonormal to the previous keys.
This algorithm does not compute the values of
K
i
independently
of each other. You must know the values of all
K
j
where
j<i
to
compute
K
i
. This is less than ideal, but it is unavoidable at this time.
Anderson, Needham and Shamir decided to turn this restriction into
a feature by casting it as a linear file access hierarchy. If you can read
file
.
Forcing all of the keys into a hierarchical order may not always
be desirable. Another technique for finding keys is to restrict each
person to a particular subspace. That is, split the keyspace into or-
thogonal parts. If person
i
, then you can read all files
j
where
j<i
i
wants to choose a particular
K
i
,thenthat
K
i
is in the right subspace.
The easiest way to split the keys into orthogonal subspaces is to
force certain bits in the key to be zero. Alice might use keys where
only the first ten bits can be set to 1, Bob might use keys where only
the second ten bits can be non-zero, and so on.
If necessary, Alice, Bob and the rest of the gang can agree on a
random rotation matrix,
person must check to see that
,anduseittorotatethesubspaces. So
Alice will only choose a key vector if
R
RK
i
has zeros in all the right
places.
This version of the file system is also a bit unwieldy. If you want to
read or write a file
D
, then youmay need to access as many as
m
other
rows. This factor can be substantial if
grows large. This can be
reduced by using non-binary values instead of bits for the individual
elements of
m
K
i
.
