Cryptography Reference
In-Depth Information
from
m
for comparison. Both of the latter options entail additional workload
over merely storing(
d
A
(
m
)
,m
). Furthermore,
Z
is a randomized operation in
the sense that the same input may produce different compressed outputs at
different times, say,
Z
(
m
)=
x
at time
t
1
, and
Z
(
m
)=
y
at time
t
2
, with
x
=
y
.
However, any version can decompress to get the correct version of compression
by any other version; in other words,
Z
−
1
(
x
)=
Z
−
1
(
y
)=
m.
Yet, forming, say,
d
A
(
m
) at time
t
1
would restrict the PGP scheme to the
version of
Z
applied at time
t
1
, since we would have to verify Alice's application
of that version of the compression at time
t
1
, which is an unacceptable shackle
to put on the security mechanism. Last, speakingof security, encipheringis
applied after compression for increased cryptographic security since
Z
(
m
) has
less redundancy that does
m
, so cryptanalytic attacks are made much tougher
on Mallory.
ZIP compression is a freeware/shareware package that is perhaps the most
frequently used compression mechanism for virtually any computingplatform.
It is based upon an algorithm, called LZ77 (see [299]), developed in 1977. Since
a version of LZ77 is used in all versions of ZIP, we will describe the basic features
that make up the algorithm. The source data is input to the algorithm as 9-bit
words
8.1
(a binary 1 followed by 8-bit ASCII
8.2
representation of the word) to be
processed from left to right. The algorithm uses two buffers, called the
sliding-
history buffer
and the
look-forward buffer
. The former contains
W
∈
N
already
processed words, and the latter contains
W
to-be-processed words. The
buffers interact as follows. The algorithm tries to match
n
∈
N
2 words from the
initial part of the look-ahead buffer to a bitstringin the slidin-history buffer.
If no match is found, the first word in the look-ahead buffer is output as a 9-bit
word, and it is also input to the sliding-history buffer, which discards its last
9-bit word. If a match is found; the longest match bitlength,
, is calculated;
the matched word is output as a three-tuple consistingof the bitlenth of the
word, its indicator value, and a pointer to the prior word of the same value;
the
-bit word is input to the sliding-history buffer; and the last
-bit word is
discarded from that buffer.
Decompression of the compressed data in the algorithm uses the pointers,
bitlength, and value fields to replace the compressed strings with the original
text.
8.1
Typically, the term
word
refers to a fixed-size integer of given bitlength in the main
memory of a given computer. Usually, the bitlengths are one of 8, 16, 32, 64, or 128. A word
can then be represented by its binary representation as a single word in the computer, such
as a 16-bit word having a representation in computer memory as one of the values between 0
and 65535 = 2
16
≥
1.
8.2
ASCII is the acronym for
American Standard Code for Information Interchange
. Each
symbol is represented as a 7-bit word, and allows for 128 possible symbols to be so represented.
Typically, a bit is appended to the 7-bit word as either a parity-check bit or an error-check
bit to see if an error occurred in transmission. The mechanism for ASCII conversion is radix-
64 transformation, wherein binary blocks of three bytes each are converted into four ASCII
symbols, each of which is appended with an error check in the form of a
cyclic redundancy
check
; see pages 541 and 542. Note that the term “radix” is a synonym for “base”.
−
Search WWH ::
Custom Search