Cryptography Reference
In-Depth Information
My considerations about the computing time may even be underestimated. Who
do you think can listen in on your DES code?
Visual Cryptanalysis
The heading of this section is the title of a paper published by the well-known
cryptanalyst Adi Shamir, who introduced it at EUROCRYPT '98 [Shamvis].
The simplified basic statement might initially seem spooky: throw away all
computer technology and buy yourself a high-resolution black-and-white neg-
ative film for aerial photographs, a photographic developer, and a black-color
spray can. How on earth would anybody be able to run a cryptanalysis with
that sort of material?
Photographic films are suitable for parallel processing. Though the development
of a film takes ages compared with electronic bit processing, the film contains
a very large number of bits. We divide the film's image field into as small areas
as possible, which we will call 'dots' for the sake of simplicity. A black dot
corresponds to value 1, a non-black dot to value 0. We use this mask to expose
a second film, and the inverse bit pattern will form once we've developed this
film — where there was a 1, there's a 0 now, and vice versa. Logically, we have
executed a NOT operation, but processed all 'film bits' in parallel.
In contrast, if we superimpose two or more films so they are exactly congruent,
and use this bunch to expose another film, then a dot on this (bottom) film will
turn black, provided there are only non-black dots on top of it. This corre-
sponds to the NOR operation, written as
∼
(a
|
b) expression in C. If we expose
consecutively rather than concurrently, we do a NAND operation:
∼
(a&b).
Yes, we could even do a XOR operation by utilizing the solarization effect.
This effect says that, when exposing the negative for too long, it will no longer
be blackened, but remain white after the development. To do a XOR operation,
we prepare two films with dark gray instead of black dots and expose them long
enough so that solarization occurs in the transparent places. In contrast, if there
is only one gray dot on top, there is still blackening, while there will be almost
no blackening in two superimposed gray dots. We may have to additionally use
a photographic reducer; amateur photographers who develop their films them-
selves know such tricks. (This method was not described in the original paper.)
To make a long story short: we can use this method to 'compute' very com-
plex logical expressions. Though the process is slow, we actually process an
extraordinarily large amount of bits in each step. The hardware friendliness
of DES is vulnerable to this algorithm. If we accommodate all possible keys
