JLM
200
6010
7 22
:16
1
Uni
vers
ity o
f Was
hing
ton
CS
EP
590
TU �
Pra
ctic
al A
spec
ts o
f M
oder
n C
rypt
ogra
phy
Inst
ruct
ors:
Jos
h B
enal
oh, B
rian
LaM
acch
ia, J
ohn
Man
ferd
elli
Tues
days
: 6:3
0-9:
30,
Alle
n C
ente
r 305
Web
page
: http
://w
ww
.cs.
was
hing
ton.
edu/
educ
atio
n/co
urse
s/cs
ep59
0/06
wi/
Rec
omm
ende
d te
xts:
S
tinso
n, C
rypt
ogra
phy,
The
ory
and
Pra
ctic
e. 2
ndE
ditio
n, C
RC
Pre
ss,
2002
.M
enez
es, v
anO
rtsho
t, V
anst
one.
Han
dboo
k of
App
lied
Cry
ptog
raph
y.Fe
rgus
on a
nd S
chne
ier,
Pra
ctic
al C
rypt
ogra
phy.
JLM
200
6010
7 22
:16
2
New
Lec
ture
Sch
edul
e
10987654321
All
Thre
e to
pics
: Ele
ctio
ns, I
TAR
/Pol
itics
, Sid
e C
hann
els/
Tim
ing
Atta
cks,
DR
M, B
igN
umIm
plem
enta
tion
3/8
Josh
Ran
dom
Num
bers
/Elli
ptic
Cur
ve C
rypt
o3/
1
Bria
nTr
ust,
PK
I, K
ey M
anag
emen
t [La
st H
W
Ass
ignm
ent)
2/21
John
AE
S a
nd C
rypt
ogra
phic
Has
hes
2/14
John
Sec
urity
of B
lock
Cip
hers
2/7
Bria
nC
rypt
ogra
phic
Pro
toco
ls II
1/
31B
rian
Cry
ptog
raph
ic P
roto
cols
I1/
24Jo
shP
ublic
Key
Cip
hers
1/17
John
Sym
met
ric K
ey C
iphe
rs a
nd H
ashe
s1/
10Jo
shP
ract
ical
Asp
ects
of C
rypt
ogra
phy
1/3
Lect
urer
Topi
cD
ate
JLM
200
6010
7 22
:16
3
Sym
met
ric K
ey C
rypt
ogra
phy
and
Cry
ptog
raph
ic H
ashe
s -I
John
Man
ferd
elli
jlm@
cs.w
ashi
ngto
n.ed
ujm
anfe
r@m
icro
soft.
com
Porti
ons
© 2
004-
2005
, Joh
n M
anfe
rdel
li.
This
mat
eria
l is
prov
ided
with
out w
arra
nty
of a
ny k
ind
incl
udin
g, w
ithou
t lim
itatio
n, w
arra
nty
of n
on-in
fring
emen
t or s
uita
bilit
y fo
r any
pur
pose
. Th
is m
ater
ial i
s no
t gua
rant
eed
to b
e er
ror f
ree
and
is in
tend
ed fo
r ins
truct
iona
l use
onl
y.
JLM
200
6010
7 22
:16
4
Com
mun
icat
ions
Eng
inee
rs C
oat o
f A
rms
Plai
ntex
t(P
)
Noi
sy in
secu
rech
anne
lC
ompr
ess
(to s
ave
spac
e)
The
Sou
rce
Sen
der:
Alic
e
The
Sin
kR
ecei
ver:B
ob
Plai
ntex
t(P
)
Encr
ypt
(for c
onfid
entia
lity)
Enco
de(to
cor
rect
err
ors)
Noi
sy in
secu
rech
anne
lD
ecom
pres
s(to
sav
e sp
ace)
Dec
rypt
(for c
onfid
entia
lity)
Dec
ode
(to c
orre
ct e
rror
s)
JLM
200
6010
7 22
:16
5
Sym
met
ric E
ncry
ptio
n
�Sy
mm
etric
Key
cry
ptog
raph
ic a
lgor
ithm
s us
e a
secr
et
know
n to
the
auth
oriz
ed p
artie
s ca
lled
a �k
ey�.
Enc
rypt
ion
and
Dec
rypt
ion
use
the
sam
e ke
y.�
The
trans
form
atio
ns a
re s
impl
e an
d fa
st e
noug
h fo
r pra
ctic
al u
sean
d im
plem
enta
tion.
��K
eysp
ace�
larg
e en
ough
to p
rote
ct a
gain
st e
xhau
stiv
e se
arch
.�
The
encr
yptio
n al
gorit
hm m
ust b
e ef
ficie
ntly
inve
rtibl
e.�
Two
maj
or ty
pes:
Stre
am c
iphe
rs a
nd B
lock
cip
hers
Key
(k)
Cip
herte
xt(C
)E
ncry
pt
Ek(
P)
Pla
inte
xt (P
)
Key
(k)
Pla
inte
xt (P
)D
ecry
pt
Dk(
P)
Cip
herte
xt(C
)
JLM
200
6010
7 22
:16
6
Why
go
Ugl
y?
.622
ms/
op (8
B), 1
2.87
MB/
sec
DE
S
.016
ms/
op (1
B), 6
3 M
B/se
cR
C4
.53
ms/o
p (1
6B),
30M
B/se
cA
ES
-128
10.3
2 m
s/op
(128
B), 1
3 KB
/sec
RSA
-102
4 D
ecry
pt
.32
ms/
op (1
28B)
, 384
KB/
sec
RSA
-102
4 En
cryp
tSp
eed
Alg
orith
m
RS
A im
plem
enta
tion
uses
CR
T, K
aras
uba
and
Mon
tgom
ery.
Ti
min
gs d
o no
t inc
lude
set
up.
All
resu
lts a
re fo
r an
850M
Hz
x86.
JLM
200
6010
7 22
:16
7
Ugl
y II
8.25
MB
/sec
SH
A-5
12
24.7
5 M
B/s
ecS
HA
-256
48.4
6 M
B/s
ecS
HA-
1Sp
eed
Alg
orith
m
Tim
ings
do
not i
nclu
de s
etup
. A
ll re
sults
are
for a
n 85
0MH
z x8
6.
JLM
200
6010
7 22
:16
8
Ugl
y III
521
1536
025
6
384
8192
192
256
3072
128
224
2048
112
160
1024
80
Ellip
tic C
urve
K
ey S
ize
RSA
/DH
Key
Si
zeSy
mm
etric
Key
Size
JLM
200
6010
7 22
:16
9
Sui
te B
-C
ompu
tatio
n C
ost
64:1
256
32:1
192
10:1
128
6:1
112
3:1
80
Rat
io R
SA/D
H:E
CSy
mm
etric
Key
Siz
e
JLM
200
6010
7 22
:16
10
Adv
ersa
ries
and
thei
r Dis
cont
ents
Eve
Plai
ntex
t(P
)C
hann
elE
ncry
ptD
ecry
pt
Alic
eBo
b
Plai
ntex
t(P
)
Wire
tap
Adv
ersa
ry
Man
in th
e M
iddl
e A
dver
sary
Mal
lory
Plai
ntex
t(P
)En
cryp
tD
ecry
pt
Alic
eBo
b
Plai
ntex
t(P
)
Cha
nnel
JLM
200
6010
7 22
:16
11
Adv
ersa
ries
�C
rypt
ogra
phy
is c
ompu
ting/
com
mun
icat
ing
in th
e pr
esen
ce
of a
n A
dver
sary
�An
Adv
ersa
ry�s
stre
ngth
is c
hara
cter
ized
by:
�C
ompu
tatio
nal r
esou
rces
ava
ilabl
e to
the
adve
rsar
y:�
Exp
onen
tial t
ime/
mem
ory
�P
olyn
omia
l tim
e/m
emor
y�
Nat
ure
of a
cces
s to
cry
ptog
raph
ical
ly p
rote
cted
dat
a:
�P
roba
ble
plai
ntex
t atta
cks
�K
now
n pl
aint
ext/c
iphe
rtext
atta
cks
�C
hose
n pl
aint
ext a
ttack
s�
Ada
ptiv
e in
tera
ctiv
e ch
osen
pla
inte
xt a
ttack
s (o
racl
e m
odel
) �
Phys
ical
Acc
ess
�O
utsi
der t
hrea
t�
Insi
der T
hrea
t (Ti
min
g, s
ide
chan
nels
)�
Trus
ted
Insi
der T
hrea
t (So
me
key
acce
ss)
JLM
200
6010
7 22
:16
12
Cip
her R
equi
rem
ents
�W
W II
�U
nive
rsal
ly a
vaila
ble
(sim
ple,
ligh
t ins
trum
enta
tion)
-in
tero
pera
bilit
y�
Com
pact
, ru
gged
: Eas
y fo
r peo
ple
to u
se�
Secu
rity
in k
ey o
nly:
We
assu
me
that
the
atta
cker
kno
ws
the
com
plet
e de
tails
of t
he c
rypt
ogra
phic
alg
orith
m a
nd im
plem
enta
tion
�Ad
vers
ary
has
acce
ss to
som
e co
rres
pond
ing
plai
n an
d ci
pher
text
�N
ow
�Ad
vers
ary
has
acce
ss to
unl
imite
d ci
pher
text
and
lots
of c
hose
n te
xt�
Impl
emen
tatio
n in
dig
ital d
evic
es (p
ower
/spe
ed) p
aram
ount
�Ea
sy fo
r com
pute
rs to
use
�R
esis
tant
to ri
dicu
lous
am
ount
of c
ompu
ting
pow
er
JLM
200
6010
7 22
:16
13
Pra
ctic
al A
ttack
s
�E
xhau
stiv
e S
earc
h of
Key
spa
ce�
Exh
aust
ive
Sea
rch
of K
eysp
ace
Res
trict
ed b
y po
or
prac
tice.
�Fo
r exa
mpl
e no
n ra
ndom
key
gen
erat
ion
�E
xplo
iting
bad
key
Man
agem
ent/S
tora
ge�
Brib
ing
Key
hold
er�
Side
Cha
nnel
/Tim
ing
�E
xplo
iting
enc
rypt
ion
Err
ors
�Sp
oofin
g (A
TM P
IN)
�Le
akin
g du
e to
siz
e, p
ositi
on, l
angu
age
choi
ce, r
epet
ition
, fre
quen
cy, i
nter
sym
bol t
rans
ition
s
JLM
200
6010
7 22
:16
14
Som
e Fo
rmal
Atta
ck R
equi
rem
ents
�In
dist
ingu
isha
bilit
y:�
Giv
en tw
o m
essa
ges
and
the
encr
yptio
n of
one
of t
he
mes
sage
s (th
e ta
rget
cip
herte
xt),
it is
har
d to
det
erm
ine
whi
ch m
essa
ge is
enc
rypt
ed�
Rel
ated
to S
eman
tic S
ecur
ity
�N
on-M
alle
abili
ty :
�G
iven
a ta
rget
cip
herte
xt y
, it i
s ha
rd to
find
ano
ther
ci
pher
text
y�s
uch
that
the
corr
espo
ndin
g pl
aint
exts
are
�m
eani
ngfu
lly re
late
d�
RSA
Slid
e --
-Key
Man
agem
ent
JLM
200
6010
7 22
:16
15
Sec
urity
In P
ract
ice
�Ba
lanc
es ri
sk o
f los
s, u
sabi
lity
and
oper
atio
nal e
ffici
ency
ag
ains
t cos
ts�
Ris
k as
sess
ed a
gain
st �k
now
n� th
reat
and
abs
olut
e co
mpu
ting
mod
el.
(e.g
.-Li
near
cry
ptan
alys
is in
243
step
s ra
ther
that
O(f(
n))).
�Th
is re
quire
s an
inte
llige
nt a
sses
smen
t of e
ach
prob
lem
ca
se a
nd c
ompu
ting/
com
mun
icat
ion
envi
ronm
ent.
�Th
e gr
eate
st th
reat
to �g
ood
secu
rity�
is th
e in
sist
ence
on
perfe
ct s
ecur
ity.
JLM
200
6010
7 22
:16
16
Blo
ck C
iphe
r
�In
a b
lock
cip
her,
plai
ntex
t is
encr
ypte
d in
blo
cks
of m
el
emen
ts o
f the
alp
habe
t. In
the
bina
ry b
lock
cas
e, m
is th
e bl
ock
leng
th in
bits
and
Ek:
P !
C w
here
�P=
C=
{0,1
,�, 2
m-1
}.�
Sinc
e E k
is in
verti
ble,
Ekε
S N, t
he p
erm
utat
ions
on
N =
2m
elem
ents
. Th
us E
k: k !
S N.
�Th
ink
of k
as
sele
ctin
g an
ele
men
t fro
m S
N ,
whi
ch is
en
orm
ous.
�| S
N| =
N! º
√(2
pN
) (N
/e)N
. Fo
r exa
mpl
e, in
DE
S, t
he
keys
pace
has
N=2
56 e
lem
ents
, SN
has
mor
e th
an (2
64)N
elem
ents
whi
ch is
way
, way
mor
e th
an th
e nu
mbe
r of
elem
enta
ry p
artic
les
in th
e un
iver
se
JLM
200
6010
7 22
:16
17
Blo
ck C
iphe
rs: M
odes
�EC
B :
c i= E
k(pi)
�S
ame
plai
ntex
t get
s sa
me
ciph
erte
xt a
nyw
here
in s
tream
�N
ot s
eman
tical
ly s
ecur
e�
All
othe
r mod
es s
afer
for l
ong
com
mun
icat
ions
.�C
BC
: c0
= IV
, ci=
Ek(
p i+c
i-1)
�E
rrors
pro
paga
te tw
o bl
ocks
�C
an�t
use
parr
alle
l HW
or p
re-p
roce
ssin
g, s
low
er�O
FB: z
0=
IV, z
i= E
k(zi-1
), c i=
pi+
zi
�Li
mite
d er
ror p
ropa
gatio
n�C
FB: c
0=
IV, z
i= E
k(ci-1
), c i=
pi+
zi
�E
rror
pro
paga
tes
for a
few
blo
cks
but s
elf-s
ynch
roni
zing
�CTR
: zi=
Ek(n
once
|| i)
, ci=
pi+
zi
�N
ever
reus
e no
nce
key
com
bina
tion
�C
urre
nt fa
vorit
e: fa
st, r
ando
m a
cces
s, a
llow
s pr
epro
cess
ing,
sim
ilars
ecur
ity to
C
BC
JLM
200
6010
7 22
:16
18
Stre
am C
iphe
r �D
efin
ition
and
E
xam
ple
�A
Stre
am C
iphe
r tak
es a
n ar
bitra
ry s
eque
nce
of e
lem
ents
fro
m th
e (p
lain
text
) inp
ut a
lpha
bet t
o th
e (c
iphe
rtext
) out
put
alph
abet
. �
Exa
mpl
e fo
r the
bin
ary
alph
abet
:�
Let m
trep
rese
nts
the
bits
of t
he p
lain
text
, t =
1,2,
�
�Le
t ktbe
bits
sel
ecte
d fro
m a
rand
om s
ourc
e, t
=1,2
,�
�Le
t ctre
pres
ent t
he c
iphe
rtext
bits
. c t
= m
t⊕
k tde
fines
a
self-
reci
proc
al (s
elf i
nver
ting)
stre
am c
iphe
r cal
led
a on
e-tim
e pa
d.
�Yo
u ca
n�t b
eat o
ne ti
me
pads
for s
ecur
ity (c
an y
ou s
pot
why
they
are
sel
dom
use
d?)
JLM
200
6010
7 22
:16
19
The
�Man
ual�
Cip
hers
�Si
mpl
e Tr
ansp
ositi
on: G
rille
s, c
olum
nar t
rans
posi
tions
.�
Mon
oalp
habe
tic S
ubst
itutio
n: C
aesa
r, si
mpl
e su
bstit
utio
n�
Poly
alph
abet
ic s
ubst
itutio
n: V
igen
iere
�Po
lygr
aphi
c su
bstit
utio
n�
Hill,
Pla
yfai
r
�Ad
ditio
nal R
efer
ence
: A
rmy
cryp
tana
lysi
s m
anua
l, ht
tp://
ww
w.u
mic
h.ed
u/~u
mic
h/fm
-34-
40-2
/
JLM
200
6010
7 22
:16
20
Gro
up T
heor
y in
Cry
ptog
raph
y -1
�G
roup
s ar
e se
ts o
f ele
men
ts th
at h
ave
a bi
nary
ope
ratio
n w
ith th
e fo
llow
ing
prop
ertie
s:1.
If x,
y,z
eG
, xy
eG
and
(xy)
z=x(
yz).
It is
not
alw
ays
true
xy=y
x.2.
Ther
e is
an
iden
tity
elem
ent 1
eG
and
1x=
x1=x
for a
ll x
in G
3.Fo
r all,
x in
G th
ere
is a
n el
emen
t x-1
eG
and
x x
-1=1
= x-1
x�
One
ver
y im
porta
nt g
roup
is th
e gr
oup
of a
ll bi
ject
ive
map
s fro
ma
set o
f n e
lem
ents
to it
self
deno
ted
S nor
Sn.
The
se a
re c
alle
d th
e �p
erm
utat
ions
of n
ele
men
ts.�
The
�bin
ary
oper
atio
n� is
the
com
posi
tion
of m
appi
ngs.
Th
e id
entit
y el
emen
t lea
ves
ever
y el
emen
t alo
ne.
The
inve
rse
of a
map
ping
, x, �
undo
es� w
hat x
doe
s.
�If
se
S nan
d th
e im
age
of x
is y
we
can
writ
e th
is tw
o w
ays:
y=
s
(x);
this
is th
e us
ual f
unct
iona
l not
atio
n yo
ur u
sed
to w
here
m
appi
ngs
are
appl
ied
�from
the
left�
. W
hen
map
ping
s ar
e ap
plie
dfro
m th
e le
ft an
d s
and
d a
re e
lem
ents
of S
ns
dde
note
s th
e m
appi
ng o
btai
ned
by a
pply
ing
dfir
st a
nd th
en s
-i.e
. y=
s(d
(x)).
�So
me
peop
le a
pply
map
ping
s fro
m th
e rig
ht.
They
wou
ld w
rite
y=(x
) s.
For t
hem
, sd
deno
tes
the
map
ping
obt
aine
d by
app
lyin
g s
first
and
then
d-i
.e. y
= ((x
)s)d
.
JLM
200
6010
7 22
:16
21
Gro
up T
heor
y in
Cry
ptog
raph
y -2
�Th
e sm
alle
st k
suc
h th
at s
k =1
is c
alle
d th
e or
der o
f s.
G is
fini
te if
it
has
a fin
ite n
umbe
r of e
lem
ents
. In
a fi
nite
gro
up, a
ll el
emen
ts h
ave
finite
ord
er a
nd th
e or
der o
f eac
h el
emen
t div
ides
the
num
ber o
fel
emen
ts o
f G (L
agra
nge�
s Th
eore
m).
�E
xam
ple.
Let
G=
S 4.
�s
= 1!
2, 2!
3, 3!
4, 4!
1, d
= 1!
3, 2!
4, 3!
1, 4!
2.s
-1 =
1!
4, 2!
1, 3!
2, 4!
3�
Appl
ying
map
ping
s �fr
om th
e le
ft�, s
d= 1!
4, 2!
1,3!
2,4!
3.�
Som
etim
es s
is w
ritte
n lik
e th
is:
s=1 2 3 4
2 3 4 1
�So
met
imes
per
mut
atio
ns a
re w
ritte
n as
pro
duct
s of
cyc
les:
s
=(1234)
and
d= (13)(24).
JLM
200
6010
7 22
:16
22
Tran
spos
ition
s
�G
rille
s B U L L
W I N K
L E I S !
BWLAEUINEDLNIOLKSP
A D O P
E
ci= pS(i)where
S=(1)(2,5,17,16,12,11,7,6)(3,9,14,4,13,15,8,10)
JLM
200
6010
7 22
:16
23
Bre
akin
g C
ompl
etel
y fil
led
Col
umna
r Tr
ansp
ositi
on
Pro
cedu
re1.
Det
erm
ine
rect
angl
e di
men
sion
s (l,
w) b
y no
ting
that
mes
sage
le
ngth
=m =
l x
w.
Her
e m
=77,
so
l=7,
w=1
1 or
l=11
, w=7
2.A
nagr
am to
obt
ain
rela
tive
colu
mn
posi
tions
Not
e a
trans
posi
tion
is e
asy
to s
pot s
ince
lette
r fre
quen
cy is
the
sam
e as
re
gula
r Eng
lish.
Message (from Sinkov)
EOEYE GTRNP SECEH HETYH SNGND DDDET OCRAE RAEMH
TECSE USIAR WKDRI RNYAR ABUEY ICNTT CEIET US
JLM
200
6010
7 22
:16
24
Ana
gram
min
g�
Look
for w
ords
, dig
raph
s, e
tc.
�N
ote:
Eve
ryth
ing
is v
ery
easy
in c
orre
spon
ding
pl
ain/
ciph
erte
xtat
tack
1 E O E Y E G T R N P S
3 G N D D D D E T O C R
6 R N Y A R A N U E Y I
5 E U S I A R W K D R I
7 C N T T C E I E T U S
2 E C E H H E T Y H S N
4 A E R A E M H T E C S
1 E O E Y E G T R N P S
3 G N D D D D E T O C R
6 R N Y A R A N U E Y I
5 E U S I A R W K D R I
7 C N T T C E I E T U S
2 E C E H H E T Y H S N
4 A E R A E M H T E C S
!
JLM
200
6010
7 22
:16
25
Alp
habe
tic S
ubst
itutio
n
�A
mon
oalp
habe
ticci
pher
map
s ea
ch o
ccur
renc
e of
a
plai
ntex
t cha
ract
er to
one
cip
herte
xt c
hara
cter
�A
poly
alph
abet
icci
pher
map
s ea
ch o
ccur
renc
e of
a
plai
ntex
t cha
ract
er to
mor
e th
an o
ne c
iphe
rtext
cha
ract
er�
A po
lygr
aphi
cci
pher
map
s m
ore
than
one
pla
inte
xt
char
acte
r at a
tim
e�
Gro
ups
of p
lain
text
cha
ract
ers
are
repl
aced
by
assi
gned
gr
oups
of c
iphe
rtext
cha
ract
ers
JLM
200
6010
7 22
:16
26
Et T
u B
rute
?: S
ubst
itutio
ns
Cae
ser C
iphe
r
B U L L W I N K L E I S A D O P E
D W N N Y K P M N G K U C F Q S G
c= pCk, C= (ABCDEFGHIJKLMNOPQRSTUVWXYZ), k= 2 here
k=3 for classical Caeser
JLM
200
6010
7 22
:16
27
Atta
cks
on M
onoa
lpha
betic
S
ubst
itutio
n
�Le
tter F
requ
ency
A.0651738
B .0124248
C .0217339
D .0349835
E.1041442
F .0197881
G .0158610
H .0492888
I.0558094
J .0009033
K .0050529
L .0331490
M.0202124
N .0564513
O .0596302
P .0137645
Q.0008606
R .0497563
S .0515760
T .0729357
U.0225134
V .0082903
W .0171272
X .0013692
Y.0145984
Z .0007836
sp .1918182
�Pr
obab
le w
ord.
�C
orre
spon
ding
pla
in/c
iphe
r tex
t mak
es th
is tr
ivia
l.
JLM
200
6010
7 22
:16
28
Pol
ygra
phic
Freq
uenc
ies
�Bi
grap
hsEN
RE
ER
NT
TH
ON
IN
TE
AN
OR
ST
ED
NE
VE
ES
ND
TO
SE
AT
TI
�Tr
igra
phs
ENT
ION
AND
ING
IVE
TIO
FOR
OUR
THI
ONE
�W
ords
THE
OF
AND
TO
A
IN
THAT
IS
IIT
FOR
AS
WITH
WAS
HIS
HE
BE
NOT
BY
BUT
HAVE
YOU
WHICH
ARE
ON
JLM
200
6010
7 22
:16
29
Lette
r Fre
quen
cy B
ar G
raph
JLM
200
6010
7 22
:16
30
Lette
r Fre
quen
cy B
ar G
raph
Le
tte
r Fr
eq
uen
cy
0102030405060
1
Le
tte
r
Count
a b c d e f g h i j k l m n o p q r s t u v w x y z
JLM
200
6010
7 22
:16
31
Shi
fted
Lette
r Fre
quen
cy B
ar G
raph
JLM
200
6010
7 22
:16
32
Vig
ener
e M
ultia
lpha
betic
Cip
her
6 A
lpha
bet D
irect
Sta
ndar
d E
xam
ple
(Key
wor
d: S
YM
BO
L)
ABCDEFGHIJKLMNOPQRSTUVWXYZ
PLAIN: GET OUT NOW
--------------------------
KEY: SYM BOL SYM
STUVWXYZABCDEFGHIJKLMNOPQR CIPHER: YCF PIE FMI
YZABCDEFGHIJKLMNOPQRSTUVWX
MNOPQRSTUVWXYZABCDEFGHIJKL
BCDEFGHIJKLMNOPQRSTUVWXYZA
OPQRSTUVWXYZABCDEFGHIJKLMN
LMNOPQRSTUVWXYZABCDEFGHIJK
JLM
200
6010
7 22
:16
33
Con
stru
ctin
g V
ig A
lpha
bets
Dire
ct S
tand
ard:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Rev
erse
Sta
ndar
d:ZYXWVUTSRQPONMLKJIHGFEDCBA
Key
wor
d D
irect
(Key
wor
d: N
EW
YO
RK
CIT
Y):
NEWYORKCITABDFGHJLMPQRSUVZ
Key
wor
d Tr
ansp
osed
(Key
wor
d: C
HIC
AG
O):
CHIAGO
BDEFJK
LMNPQR
STUVWX
YZ
CBLSYHDMTZIENUAFPVGJQWOKRX
JLM
200
6010
7 22
:16
34
Sol
ving
Vig
ener
e
1.D
eter
min
e N
umbe
r of A
lpha
bets
�R
epea
ted
runs
yie
ld in
terv
al d
iffer
ence
s. N
umbe
r of
alph
abet
s is
the
gcd
of th
ese.
(K
asis
ki)
�St
atis
tics:
Inde
x of
coi
ncid
ence
2.
Det
erm
ine
Pla
inte
xt A
lpha
bet
3.D
eter
min
e C
iphe
rtext
Alp
habe
ts
JLM
200
6010
7 22
:16
35
Sta
tistic
al T
ests
for A
lpha
bet I
dent
ifica
tion
�In
dex
of c
oinc
iden
ce fo
r let
ter f
requ
ency
�C
an c
hoos
e sa
me
lette
rs f i
choo
se 2
way
s
IC =
S if i(
f i-1)
/(n(n
-1)),
so
IC º
S ip i
2
�Fo
r Eng
lish
Text
IC º
.07
�Fo
r Ran
dom
Tex
t IC
= 1/
26=.
038
�IC
is u
sefu
l for
det
erm
inin
g nu
mbe
r of a
lpha
bets
(key
leng
th) a
nd
alig
ning
alp
habe
ts.
For n
lette
rs e
ncip
here
d w
ith m
alp
habe
ts:
�IC
(n,m
)= 1
/m (n
-m)/(
n-1)
(.07
) + (m
-1)/m
n/(n
-1) (
.038
)
�O
ther
Sta
tistic
s�
Vow
el C
onso
nant
pai
ring
�D
igra
ph, t
rigra
ph fr
eque
ncy
JLM
200
6010
7 22
:16
36
Rev
iew
of A
ttack
s on
Pol
yalp
habe
t
�Le
tter F
requ
ency
, mul
tigra
m fr
eque
ncie
s, tr
ansi
tion
prob
abili
ties
�In
dex
of C
oinc
iden
ce�
Alp
habe
t Cha
inin
g�
Slid
ing
Pro
babl
e Te
xt�
Lim
ited
Key
spac
e se
arch
�Lo
ng re
peat
ed s
eque
nces
in c
iphe
rtext
�M
arko
ff lik
e co
ntac
t pro
cess
es�
Dec
imat
ion
of s
eque
nces
�Lo
g w
eigh
ts�
Gen
erat
rix�
Dire
ct a
nd in
dire
ct s
ymm
etrie
s
JLM
200
6010
7 22
:16
37
Pol
ygra
phic
Sub
stitu
tion
�P
layF
air D
igra
phic
Sub
stitu
tion
OHNMA
FERDL
IBCGK TH!
QM
PQSTU
VWXYZ
JLM
200
6010
7 22
:16
38
Hill
Cip
her
�Th
e H
ill c
iphe
r is
a bl
ock
ciph
er w
ith b
lock
siz
e is
2 o
ver t
he �n
orm
al�
alph
abet
.�
Assi
gn e
ach
lette
r a n
umbe
r bet
wee
n 0
and
25 (i
nclu
sive
) �
For e
xam
ple,
a =
0, b
= 1
, . .
., z
= 25
(z is
use
d as
spa
ce)
�Le
t p1p
2be
two
succ
essi
ve p
lain
text
lette
rs.
c 1c 2
are
the
ciph
erte
xtou
tput
whe
re
�Ap
ply
the
inve
rse
of th
e �k
ey m
atrix
� [k 1
1k 1
2 | k
21k 2
2] to
tran
sfor
m
ciph
erte
xtin
to p
lain
text
�W
orks
bet
ter i
f we
add
spac
e (2
7=33
lette
rs) o
r thr
ow o
ut a
lette
r (25
=52 )
c 1=
k 11p
1+
k 12p
2(m
od 2
6)
c 2=
k 21p
1+
k 22p
2(m
od 2
6)
JLM
200
6010
7 22
:16
39
Bre
akin
g H
ill
�Th
e H
ill ci
pher
is re
sist
ant t
o a
ciph
erte
xt o
nly
atta
ck w
ith
limite
d ci
pher
text
. �
Incr
easi
ng th
e bl
ock
size
incr
ease
s th
e re
sist
ance
.
�It
is tr
ivia
l to
brea
k us
ing
a kn
own
plai
ntex
t atta
ck.
�
The
proc
ess
is m
uch
like
the
met
hod
used
to b
reak
an
affin
e ci
pher
. C
orre
spon
ding
pla
inte
xt/c
iphe
rtext
are
used
to s
et u
p a
syst
em o
f equ
atio
ns w
hose
sol
utio
ns a
re th
e ke
y bi
ts.
JLM
200
6010
7 22
:16
40
Info
rmat
ion
Theo
ry M
otiv
atio
n
�H
ow m
uch
info
rmat
ion
is in
a b
inar
y st
ring?
�G
ame:
I ha
ve a
val
ue b
etw
een
0 an
d 2n -
1 (in
clus
ive)
, fin
d it
by a
skin
g th
e m
inim
um n
umbe
r of y
es/n
o qu
estio
ns.
�W
rite
the
num
ber a
s [b
n-1b
n-2�
b 0] 2
.�
Que
stio
ns: I
s b n
-11?
, Is
bn-
21?
, �
, Is
b0
1?�
So, w
hat i
s th
e am
ount
of i
nfor
mat
ion
in a
num
ber b
etw
een
0 an
d 2n -
1?
�A
nsw
er: n
bits
�Th
e sa
me
ques
tion:
Let
X b
e a
prob
abilit
y di
strib
utio
n ta
king
on
valu
es
betw
een
0 an
d 2n
-1 w
ith e
qual
pro
babi
lity.
Wha
t is
the
info
rmat
ion
cont
ent o
f a o
bser
vatio
n?�
Ther
e is
a m
athe
mat
ical
func
tion
that
mea
sure
s th
e in
form
atio
n in
an
obse
rvat
ion
from
a p
roba
bilit
y di
strib
utio
n. I
t�s d
emot
ed H
(X).
�H
(X)=
Si�
p ilg
(pi)
JLM
200
6010
7 22
:16
41
Info
rmat
ion
Theo
ry
�Th
e �d
efin
ition
� of H
(X),
whi
ch is
cal
led
entro
py, h
as tw
o de
sire
able
prop
ertie
s�
Dou
blin
g th
e st
orag
e (th
e bi
ts y
our f
amili
ar w
ith) d
oubl
es th
e in
form
atio
n co
nten
t�
H(1
/2, 1
/3, 1
/6)=
H(1
/2, 1
/2) +
½ H
(2/3
,1/3
)�
It w
as o
rigin
ally
dev
elop
ed to
stu
dy h
ow e
ffici
ently
one
can
relia
bly
trans
mit
info
rmat
ion
over
�noi
sy� c
hann
el.
�Ap
plie
d by
Sha
nnon
to C
rypt
ogra
phy
(Com
mun
icat
ion
Theo
ry o
f S
ecre
cy S
yste
ms.
B
TSJ,
194
9)
�En
tropy
whi
ch m
easu
res
�am
ount
� of u
ncer
tain
ty th
at is
repr
esen
ted
in a
sa
mpl
e dr
awn
from
a s
toch
astic
dis
tribu
tion
�Th
us in
form
atio
n le
arne
d ab
out Y
by
obse
rvin
g X
is I(
Y,X
)= H
(Y)-
H(Y
|X).
�C
an b
e us
ed to
est
imat
e re
quire
men
ts fo
r cry
ptan
alys
is o
f a c
iphe
r.
JLM
200
6010
7 22
:16
42
Info
rmat
ion
Theo
ry in
Cry
ptog
raph
y
�St
udyi
ng k
ey s
earc
h�
Dis
tribu
tion
A: 2
bit
key
each
key
equ
ally
like
ly�
Dis
tribu
tion
B: 4
bit
key
each
key
equ
ally
like
ly�
Dis
tribu
tion
C: n
bit
key
each
key
equ
ally
like
ly�
Dis
tribu
tion
A�:
2 bi
t key
sel
ecte
d fro
m d
istri
butio
n (1
/2, 1
/6,1
/6,
1/6)
�D
istri
butio
n B
�: 4
bit k
ey s
elec
ted
from
dis
tribu
tion
(1/2
, 1/3
0, 1
/30,
�
, 1/3
0)�
Dis
tribu
tion
C�:
n bi
t key
sel
ecte
d fro
m d
istri
butio
n (1
/2, ½
1/(2
n -1)
,�, ½
1/(2
n -1)
)
JLM
200
6010
7 22
:16
43
Info
rmat
ion
Theo
ry in
Cry
ptog
raph
y
�H
ow m
uch
info
rmat
ion
is th
ere
in a
key
dra
wn
from
a ra
ndom
var
iabl
e X �
Dis
tribu
tion
A: H
(X)=
¼ lg
(4) +
¼ lg
(4) +
¼ lg
(4) +
1/4
lg(4
) = 2
bits
�D
istri
butio
n B:
H(X
)= 1
6 x
(1/1
6 lg
(16)
)= 4
bits
�D
istri
butio
n C
: H(X
)= 2
nx
(1/2
n ) lg
(2n )
= n
bits
�D
istri
butio
n A
�: H
(X) =
½ lg
(2) +
3 x
(1/6
lg(6
))= 1
.79
bits
�D
istri
butio
n B
�: H
(X) =
½ lg
(2) +
15
x(1/
30 lg
(30)
)= 2
.95
bits
�D
istri
butio
n C
�: H
(X) =
½ lg
(2) +
1/2
2n -
1 x(
1/(2
n -1)
lg(2
n -1)
) ºn/
2+1
bits
JLM
200
6010
7 22
:16
44
Info
rmat
ion
Theo
ry in
Cry
ptog
raph
y
�W
hat i
s th
e ex
pect
ed n
umbe
r of k
eys
that
mus
t be
tried
to
dete
rmin
e a
key
draw
n fro
m a
rand
om v
aria
ble
X�
Dis
tribu
tion
A: E
(X)=
¼ (1
+2+3
) = 1
.5 tr
ials
�D
istri
butio
n B
: E(X
)= 1
/16
(1+2
+�+1
5)=7
.5 tr
ials
�D
istri
butio
n C
: E(X
)= 1
/2n
(1+2
+ �
+2n )
= (2
n -1)
/2 tr
ials
�D
istri
butio
n A
�: E
(X) =
½ x
1 +
1/6
(2+3
)= 4
/3 tr
ials
�D
istri
butio
n B
�: E
(X) =
½ X
1 +
1/30
(2+3
+�+1
5)=
125/
12 tr
ials
�D
istri
butio
n C
�: E
(X) =
½ X
1 +
½ 1
/(2n -
1)(2
+3+�
+2n -
1)=
½ +
¼ 1
/(2n -
1) (2
n -1)
(2n +
1)tri
als
JLM
200
6010
7 22
:16
45
Equ
ivoc
atio
n an
d B
ayes
The
orem
�H
E=
Lim
n!¶
S(x
[1],�
,x[n
])(1
/n)P
r(X
=(x[
1],�
,x[n
]))
lg(P
r(X
=(x[
1],�
,x[n
])))
�Fo
r ran
dom
stre
am o
f let
ters
�
HR=
S i(1
/26)
lg(2
6)=4
.700
4�
For E
nglis
h�
HE
nglis
h=
1.2-
1.5
(so
Eng
lish
is a
bout
75%
redu
ndan
t)�
Ther
e ar
e ap
prox
imat
ely
T(n)
= 2nH
n s
ymbo
l mes
sage
s th
at c
an
be d
raw
n fro
m th
e m
eani
ngfu
l Eng
lish
sam
ple
spac
e.
�H
(X,Y
)= H
(Y)+
H(X
|Y)
�Ba
yes:
P(x
|y) P
(y)=
P(x
)P(y
|x)
�X
and
Y ar
e in
depe
nden
t if P
(X,Y
)= P
(X)P
(Y)
JLM
200
6010
7 22
:16
46
Som
e In
form
atio
n Th
eory
The
orem
s
�H
(K|C
)= H
(M|C
)+ H
(K|M
,C)
Pro
of:
H(K
|C)=
H(K
,C)-
H(C
), H
(K|M
,C)=
H(M
, K, C
)-H(M
,C).
H(M
|C)=
H(M
,C) �
H(C
). T
hus,
H(K
|C)=
H(K
,C)-
H(M
,C)+
H(M
|C).
H(M
|K,C
)= H
(M,K
,C)-
H(K
,C),
but H
(M|K
,C)=
0 s
ince
ther
e is
no
unce
rtain
ty in
the
mes
sage
giv
en th
e ci
pher
text
and
the
key.
H
(K|M
,C)=
H(M
,K,C
)-H
(M,C
). S
o H
(K|M
,C)=
H(K
,C)-
H(M
,C).
Th
us H
(K|C
)= H
(K|M
,C)+
H(M
|C).
�Pe
rfect
Sec
urity
: P
(C|M
)=P
(C)
JLM
200
6010
7 22
:16
47
Uni
city
and
Ran
dom
Cip
hers
Que
stio
n: H
ow m
any
mes
sage
s do
I ne
ed to
tria
l dec
ode
so
that
the
exp
ecte
d nu
mbe
r of f
alse
key
s fo
r whi
ch a
ll m
m
essa
ges
land
in th
e m
eani
ngle
ss s
ubse
t is
less
than
1?
Ans
wer
: Th
e un
icity
poi
nt.
Nic
e ap
plic
atio
n of
Info
rmat
ion
Theo
ry.
Theo
rem
: Le
t H b
e th
e en
tropy
of t
he s
ourc
e (s
ay E
nglis
h)
and
let S
be th
e al
phab
et.
Let K
be
the
set o
f (e
quip
roba
ble)
key
s. T
hen
u= lg
(|K|)/
(lg(|S
|)-H
).
JLM
200
6010
7 22
:16
48
Uni
city
for R
ando
m C
iphe
rs
Cip
her M
essa
ges
|S|n
Non
-Mea
ning
ful M
essa
ges
Mea
ning
ful M
essa
ges
2Hn
Dec
odin
g w
ith c
orre
ct k
ey
Dec
odin
g w
ith in
corre
ct k
ey
JLM
200
6010
7 22
:16
49
Uni
city
Dis
tanc
e fo
r Mon
oalp
habe
t
HC
aese
rKey
= H
rand
om=
lg(2
6)=
4.70
04H
Engl
ish
º1.
2.
For C
aese
r, u
º lg
(26)
/(4.7
-1.2
) º 4
sym
bols
, for
cip
herte
xt
only
atta
ck.
For k
now
n pl
aint
ext/c
iphe
rtext
, onl
y 1
corr
espo
ndin
g pl
ain/
ciph
er s
ymbo
l is
requ
ired
for u
niqu
e de
code
.Fo
r arb
itrar
y su
bstit
utio
n, u
º lg
(26!
)/(4.
7-1.
2) º
25
sym
bols
fo
r cip
herte
xt o
nly
atta
ck.
For c
orre
spon
ding
pl
ain/
ciph
erte
xt a
ttack
, abo
ut 8
-10
sym
bols
are
requ
ired.
Bot
h es
timat
es a
re re
mar
kabl
y cl
ose
to a
ctua
l exp
erie
nce.
JLM
200
6010
7 22
:16
50
App
licat
ion:
One
Tim
e P
ads
are
�unb
reak
able
�
M, C
, K a
re n
bits
long
P(M
=x|C
=y)=
P(M
=x a
nd C
=y)/P
(C=y
). P
(M=x
and
C=y
) =P
(M=x
and
K=x
∆ y)
=P(M
=x)P
(K=x
∆
y)=P
(M=x
)2-n
P(C
=y)=
SxP
(M=x
and
C=y
)= S
xP(M
=x)2
-n=2
-n
So
P(M
=x|C
=y)=
P(M
=x) 2
-n/2
-n=P
(M=x
)
JLM
200
6010
7 22
:16
51
Info
rmat
ion
Theo
retic
Est
imat
esto
bre
ak m
onoa
lpha
bet O
(1)
~30
lette
rsC
iphe
rtext
onl
ySu
bstit
utio
n
O(1
)~1
0 le
tters
Kno
wn
plai
ntex
tSu
bstit
utio
n
11
corr
espo
ndin
g pl
ain/
ciph
er p
air
Kno
wn
plai
ntex
tC
aese
r
26 c
ompu
tatio
nsU
= 4.
7/1.
2=4
lette
rsC
iphe
rtext
onl
yC
aese
r
Com
puta
tiona
l R
esou
rces
Info
rmat
ion
Res
ourc
esTy
pe o
f Atta
ckC
iphe
r
JLM
200
6010
7 22
:16
52
Mix
ing
cryp
togr
aphi
c el
emen
ts to
pro
duce
st
rong
cip
her
�D
iffus
ion
�tra
nspo
sitio
n�
Usi
ng g
roup
theo
ry, t
he a
ctio
n of
a tr
ansp
ositi
on t
on a
1a 2
�a k
coul
d be
w
ritte
n as
at(
1)a t(
2)�
a t(k)
.�
Con
fusi
on �
subs
titut
ion
�U
sing
gro
up th
eory
, the
act
ion
of a
sub
stitu
tion
son
a1
a 2�
a kco
uld
be
writ
ten
as s
(a1)
s(a
2) �
s(a
k) .
�Tr
ansp
ositi
ons
and
subs
titut
ions
may
dep
end
on k
eys.
Key
ed
perm
utat
ions
may
be
writ
ten
as s
k(x).
Inci
dent
ially
, a b
lock
cip
her o
n b
bits
is n
othi
ng m
ore
than
a k
eyed
per
mut
atio
n on
2b
sym
bols
.
�Ite
rativ
e C
iphe
rs �
key
depe
ndan
t sta
ged
itera
tion
of c
ombi
natio
n of
ba
sic
elem
ents
is v
ery
effe
ctiv
e w
ay to
con
stru
ct c
iphe
r. (D
ES
,AE
S)
JLM
200
6010
7 22
:16
53
The
�Mac
hine
� Cip
hers
�Si
mpl
e M
anua
l Whe
els
�W
heat
ston
e�
Jeffe
rson
�R
otor
�En
igm
a�
Heb
urn
�SI
GA
BA
�TY
PE
X
�St
eppi
ng s
witc
hes
�Pu
rple
�M
echa
nica
l Lug
and
cag
e�
M20
9
JLM
200
6010
7 22
:16
54
Jeffe
rson
Cip
her
JLM
200
6010
7 22
:16
55
Eni
gma
JLM
200
6010
7 22
:16
56
Gro
up T
heor
y fo
r Rot
ors
�Th
eore
m: I
f s=(a11a12… a1i) (a11… a1j) … (a11… a1k)
then
ds
d-1= (
da11
da12…
da1i) (
da11…
da1j) … (
da11…
da1k).
�W
hen
perm
utat
ions
are
writ
ten
as p
rodu
cts
of c
ycle
s, it
is v
ery
easy
to
calc
ulat
e th
eir o
rder
. (It
is th
e LC
M o
f the
leng
th o
f the
cyc
les)
.�
Writ
ing
cryp
togr
aphi
c pr
oces
ses
as g
roup
ope
ratio
n ca
n be
ver
y us
eful
. Fo
r exa
mpl
e, if
R d
enot
es th
e m
appi
ng o
f a �r
otor
� and
C=(
1,2,
�,2
6),
the
map
ping
of t
he ro
tor �
turn
ed� o
ne p
ositi
on is
CR
C-1
.
Ref
eren
ce:
Rot
man
, Gro
up T
heor
y.
Lang
, Alg
ebra
.H
all,
Gro
up T
heor
y. C
hels
ea.
JLM
200
6010
7 22
:16
57
Dia
gram
mat
ic E
nigm
a S
truct
ure
Mes
sage
flow
s rig
ht to
left
U: U
mke
hrw
alze
(rev
ersi
ng d
rum
)N
,M,L
: Firs
t (fa
stes
t), s
econ
dth
ird ro
tors
S: S
teck
er (p
lugb
oard
)
UL
MN
S
Lam
ps
Keyb
oard
B
L
Dia
gram
cou
rtesy
of C
arl E
lliso
n
JLM
200
6010
7 22
:16
58
Mili
tary
Eni
gma
Enc
rypt
ion
Equ
atio
nc= (p) PiNP-i PjMP-j PkLP-k U PkL-1P-k PjM-1P-j PiN-1P-i
�K:
Key
boar
d�
P=(A
BCD
EFG
HIJ
KLM
NO
PQR
STU
VWXY
Z)�
N: F
irst R
otor
�M
: Sec
ond
Rot
or�
L: T
hird
Rot
or�
U: R
efle
ctor
. N
ote:
U=U
-1.
�i,j
,k: N
umbe
r of r
otat
ions
of f
irst,
seco
nd a
nd th
ird ro
tors
re
spec
tivel
y.
�La
ter m
ilita
ry m
odel
s ad
ded
plug
-boa
rd (S
) and
add
ition
al
roto
r (no
t inc
lude
d).
The
equa
tion
with
Plu
gboa
rd is
:c=(p)S PiNP-i PjMP-j PkLP-k U PkL-1P-k PjM-1P-j PiN-1P-i S-1
JLM
200
6010
7 22
:16
59
Eni
gma
Dat
a
Rotors
Input ABCDEFGHIJKLMNOPQRSTUVWXYZ
Rotor I
EKMFLGDQVZNTOWYHXUSPAIBRCJ
Rotor II
AJDKSIRUXBLHWTMCQGZNPYFVOE
Rotor III
BDFHJLCPRTXVZNYEIWGAKMUSQO
Rotor IV
ESOVPZJAYQUIRHXLNFTGKDCMWB
Rotor V
VZBRGITYUPSDNHLXAWMJQOFECK
Rotor VI
JPGVOUMFYQBENHZRDKASXLICTW
Rotor VII
NZJHGRCXMYSWBOUFAIVLPEKQDT
Reflector B (AY) (BR) (CU) (DH) (EQ) (FS) (GL) (IP)
(JX) (KN) (MO) (TZ) (VW)
Reflector C (AF) (BV) (CP) (DJ) (EI) (GO) (HY) (KR)
(LZ) (MX) (NW) (TQ) (SU)
Ring Turnover
Rotor I
RRotor II
FRotor III
WRotor IV
KRotor V
ARotors VI
A/N
JLM
200
6010
7 22
:16
60
Mili
tary
Eni
gma
Key
Len
gth
�Ke
y Le
ngth
(rot
or o
rder
, rot
or p
ositi
ons,
plu
gboa
rd)
�60
roto
r ord
ers.
lg(6
0)=
5.9
bits
.�
26*2
6*26
= 1
7576
initi
al ro
tor p
ositi
ons.
lg(1
7576
)= 1
4.1
bits
of k
ey�
10 e
xcha
ngin
g st
ecke
rs w
ere
spec
ified
yie
ldin
g C
(26,
2)
C(2
4,2)
�C
(8,2
)/10!
= 1
50,7
38,2
74,9
37,2
50.
lg(1
50,7
38,2
74,9
37,2
50)=
47.
1 bi
ts a
s us
ed�
Bits
of k
ey: 5
.9 +
14.
1 +
47.1
= 6
7.1
bits
�N
ote:
plu
gboa
rd tr
iple
s en
tropy
of k
ey!
�R
otor
Wiri
ng S
tate
�
lg(2
6!) =
88.
4 bi
ts/ro
tor.
�To
tal K
ey in
clud
ing
roto
r wiri
ng:
�67
.1 b
its +
3 x
88.
4 bi
ts =
312
.3 b
its
JLM
200
6010
7 22
:16
61
Met
hod
of B
aton
s
�Ap
plie
s to
Eni
gma
�W
ithou
t plu
gboa
rd�
With
fast
roto
r ord
erin
g kn
own
and
only
the
fast
roto
r mov
ing
�W
ith a
�crib
��
Let N
be
the
fast
roto
r and
Z th
e co
mbi
ned
effe
ct o
f the
oth
er a
ppar
atus
, th
en N
-1ZN
(p)=
c.�
Sin
ce Z
N(p
)=N
(c),
we
know
the
wiri
ng o
f N a
nd a
crib
, we
can
play
the
crib
aga
inst
eac
h of
the
26 p
ossi
ble
posi
tions
of N
for t
he p
lain
text
and
th
e ci
pher
text
. In
the
corr
ect p
ositi
on, t
here
will
be
no �s
critc
hes�
or
cont
radi
ctio
ns in
repe
ated
lette
rs.
�Th
is m
etho
d w
as u
sed
to �a
naly
ze� t
he e
arly
Eni
gma
varia
nts
used
in
the
Spa
nish
Civ
il W
ar a
nd is
the
reas
on th
e G
erm
ans
adde
d th
e pl
ugbo
ard.
�C
ount
erm
easu
re: M
ove
fast
roto
r nex
t to
refle
ctor
.
JLM
200
6010
7 22
:16
62
Ger
man
Key
Man
agem
ent b
efor
e 5/
40
�D
aily
key
s w
ere
dist
ribut
ed o
n pa
per m
onth
ly a
nd d
istri
bute
d by
co
urie
r. E
ach
daily
key
con
sist
ed o
f a li
ne s
peci
fyin
g:�
(dat
e, ro
tor o
rder
, rin
g se
tting
s, p
lug
setti
ngs
-10)
�Fo
r eac
h m
essa
ge1.
Ope
rato
r cho
oses
a 3
-lette
r seq
uenc
es, t
he �i
ndic
ator
� and
the
�text
�2.
Ope
rato
r set
roto
r pos
ition
s to
indi
cato
r and
enc
rypt
ed te
xt tw
ice.
3.
Mac
hine
roto
r pos
ition
s w
ere
rese
t to
�text
� pos
ition
s an
d th
e m
essa
ge
encr
ypte
d.4.
Ope
rato
r pre
pend
ed in
dica
tor a
nd tw
ice
encr
ypte
d ro
tor o
rder
text
to
trans
mitt
ed m
essa
ge.
�Th
is w
as d
one
to a
void
sta
rting
roto
rs in
the
sam
e po
sitio
n fo
r eac
h m
essa
ge w
ithou
t eno
rmou
s ke
y lis
ts.
�G
ood
mot
ivat
ion.
Bad
idea
.
JLM
200
6010
7 22
:16
63
Cha
nges
Ger
man
use
of E
nigm
a
1.P
lugb
oard
add
ed�
6/30
2.K
ey s
ettin
g m
etho
d �
1/38
3.R
otor
s IV
and
V �
12/3
84.
Mor
e pl
ugs
-1/
395.
End
of m
essa
ge k
ey p
air e
ncip
herm
ent �
5/40
JLM
200
6010
7 22
:16
64
Pol
ish
(Rej
ewsk
i) A
ttack
�R
ejew
ski e
xplo
ited
wea
knes
s in
Ger
man
key
ing
proc
edur
e to
de
term
ine
roto
r wiri
ng�
Rej
ewsk
i had
cip
herte
xt fo
r sev
eral
mon
ths
but n
o G
erm
an E
nigm
a.�
Rej
ewsk
i had
Ste
cker
set
tings
for 2
mon
ths
(from
a G
erm
an s
py v
ia th
e Fr
ench
in 1
2/32
), le
avin
g 26
5.2
bits
of k
ey (t
he w
iring
s) to
be
foun
d. H
e di
d.�
Pole
s de
term
ine
the
daily
key
s�
Rej
ewsk
i cat
alog
ued
the
char
acte
ristic
s of
roto
r set
tings
to d
etec
t dai
ly
setti
ngs.
He
did
this
with
two
conn
ecte
d En
igm
as o
ffset
by
3 po
sitio
ns (t
he
�cyc
loto
met
er�).
�In
9/3
8, w
hen
the
�mes
sage
key
� was
no
long
er s
elec
ted
from
sta
ndar
d se
tting
(the
Eni
gma
oper
ator
to c
hoos
e a
diffe
rent
enc
iphe
rmen
t sta
rt ca
lled
the
indi
cato
r), R
ejew
ski�s
cha
ract
eris
tics
stop
ped
wor
king
.�
Zyga
lski
dev
elop
ed a
new
cha
ract
eris
tic a
nd c
ompu
tatio
n de
vice
(�Zy
gals
ki
shee
ts�)
to c
atal
og c
hara
cter
istic
s w
hich
app
eare
d w
hen
1st /4
th,
2nd /5
th,3
rd/6
thci
pher
text
lette
rs in
enc
rypt
ed m
essa
ge k
eys
(�Fem
ales
�) w
ere
the
sam
e.
JLM
200
6010
7 22
:16
65
How
Rej
ewsk
i did
it
Rec
allc=(p)S PiNP-i PjMP-j PkLP-k U PkL-1P-kPjM-1P-j PiN-1P-I S-
1
Let Q= MLUL-1M-1=Q-1
Then
the
first
6 p
erm
utat
ions
(use
d to
enc
rypt
set
tings
twic
e) a
re:
–A=A-1= SP1NP-1QP1N-1P-1S-1, B=B-1= SP2NP-2QP2N-1P-2S-1
–C=C-1= SP3NP-3QP3N-1P-3S-1, D=D-1= SP4NP-4QP4N-1P-4S-1
–E=E-1= SP5NP-5QP5N-1P-5S-1, F=F-1= SP6NP-6QP6N-1P-6S-1
Thei
r pro
duct
s an
d w
hat t
hey
reve
al a
bout
enc
rypt
ed s
ettin
gs
(c1c2c3c4c5c6):
–AD= SP1NP-1QP1N-1P3NP-4QP4N-1P-4S-1.(c1)AD= c4.
–BE= SP2NP-2QP2N-1P3NP-5QP5N-1P-5S-1. (c2)BE= c5.
–CF= SP3NP-3QP3N-1P3NP-6QP6N-1P-6S-1. (c3)CF= c6.
So
we
can
find AD
, BE
andCF
afte
r abo
ut 8
0 m
essa
ges.
JLM
200
6010
7 22
:16
66
How
Rej
ewsk
i did
it (c
ontin
ued)
We
don�
t kno
w S
, N o
r Q.
Sup
pose
–AD= (dvpfkxgzyo)(eijmunqlht)(bc)(rw)(a)(s)
–BE= (blfqveoum)(hjpswizrn)(axt)(cgy)(d)(k)
–CF= (abviktjgfcqny)(duzrehlxwpsmo)
Now
the
follo
win
g tw
o si
mpl
e G
roup
The
ory
Theo
rem
s he
lp:
1. T
he p
rodu
ct o
f tw
o pe
rmut
atio
ns o
f the
sam
e de
gree
con
sist
ing
of
prod
ucts
of d
isjo
int t
rans
posi
tions
has
an
even
num
ber o
f cyc
les
of th
e sa
me
leng
th a
nd th
e ea
ch e
lem
ent o
f a tr
ansp
ositi
on
ends
up
in d
iffer
ent c
ycle
s of
the
sam
e le
ngth
.2.
Tw
o pe
rmut
atio
ns in
Sn
are
conj
ugat
e (s
=r-
1 dr) i
ff th
ey h
ave
the
sam
e cy
cle
stru
ctur
e.
JLM
200
6010
7 22
:16
67
How
Rej
ewsk
i did
it (c
oncl
usio
n)
�U
sing
the
first
theo
rem
, the
exp
ress
ion
for C
F gi
ves
13 p
ossi
bilit
ies
for C
and
F,
27(
=3x9
) pos
sibi
litie
s fo
r B a
nd E
and
20(
=2x1
0) p
ossi
bilit
ies
for A
and
D.
�H
isto
gram
s of
the
enci
pher
ed m
essa
ge k
eys
show
ed s
pike
s. R
ejew
ski
dedu
ced,
cor
rect
ly, t
hat t
hese
wer
e of
ten
for p
lain
text
key
s A
AA
, BB
B, C
CC
, et
c. --
-tha
t allo
wed
him
to li
ne u
p cy
cles
bet
wee
n th
e th
ree
Enig
ma
pairs
.�
This
det
erm
ines
A,B
,C,D
,E a
nd F
.�
Rej
ewsk
i was
giv
en 2
mon
ths
of k
ey s
heet
s, c
arry
ing
the
Stec
ker s
ettin
gs.
From
them
he
rem
oved
the
Stec
ker a
nd s
olve
d th
e eq
uatio
ns fo
r the
fast
roto
r.
For e
xam
ple:
–S-1AS= P1NP-1QP1N-1P-1with S-1AS and P, known.
�Th
is le
aves
onl
y tw
o pe
rmut
atio
ns Q
and
N (t
he fa
st ro
tor)
unk
now
n an
d Q
is in
pr
ecis
ely
the
right
form
to a
pply
the
seco
nd g
roup
theo
ry re
sult.
�Th
us w
e ca
n ob
tain
bot
h Q
and
N (s
ee p
osts
crip
t).�
Sin
ce a
ll th
e ro
tors
are
in th
e fa
st p
ositi
on a
t som
e tim
e, w
e (a
s R
ejew
ski)
can
obta
in a
ll th
e w
iring
s.
JLM
200
6010
7 22
:16
68
How
Rej
ewsk
i did
it (p
osts
crip
t)
A=SP1NP-1QP1N-1P-1S-1 !A’=S-1P-1AP1S= NP-1QP1N-1
B=SP2NP-2QP2N-1P-2S-1 !B’=S-1P-2BP2S= NP-2QP2N-1
So,
A’B’=NP-1QP1QP2N-1
Similarly,
C’D’= NP-2QP1QP3N-1
So
C’D’= NP-1N-1A’B’NPN-1
JLM
200
6010
7 22
:16
69
Dig
ital B
lock
Cip
hers
Com
plic
ated
key
ed in
verti
ble
func
tions
con
stru
cted
from
ite
rate
d el
emen
tary
roun
ds.
� Con
fusi
on: n
on-li
near
func
tions
(RO
M lo
okup
)�D
iffus
ion:
per
mut
e ro
und
outp
ut b
its�K
ey m
ixin
g: x
or�k
ey s
ched
ule�
at b
egin
ning
of r
ound
Characteristics:
�Fas
t�D
ata
encr
ypte
d in
fixe
d �b
lock
siz
es� (
64,1
28,2
56 b
it bl
ocks
are
co
mm
on).
�Key
and
mes
sage
bits
non
-line
arly
mix
ed in
cip
herte
xt
DE
S (1
974)
des
ign
was
wat
ersh
ed in
pub
lic s
ymm
etric
key
cr
ypto
.
JLM
200
6010
7 22
:16
70
Dat
a E
ncry
ptio
n S
tand
ard
�Fed
eral
His
tory
� 197
2 st
udy
�RFP
: 5/7
3, 8
/74
�NS
A: S
-Box
influ
ence
, key
siz
e re
duct
ion
�Pub
lishe
d in
Fed
eral
Reg
iste
r: 3/
75�F
IPS
46:
Jan
uary
, 197
6.�I
BM �Des
cend
ant o
f Fei
stel
�sLu
cife
r�D
esig
ners
: Hor
st F
eist
el, W
alte
r Tuc
hman
, Don
Cop
pers
mith
, Ala
n K
onhe
im, C
arl M
eyer
, Mik
e M
atya
s, R
oy A
dler
, Edn
a G
ross
man
, Bill
N
otz,
Lyn
n S
mith
, and
Bry
ant T
ucke
rman
�Bru
te F
orce
Cra
ckin
g�E
FS D
ES
Cra
cker
: $25
0K, 1
998.
1,5
36 c
usto
m c
hips
. Can
bru
te
forc
e a
DE
S k
ey in
day
s�D
eep
Cra
ck a
nd d
istri
bute
d.ne
tbre
ak a
DE
S k
ey in
22.
25 h
ours
.
JLM
200
6010
7 22
:16
71
Hor
st F
eist
el: L
ucife
r
�Ea
rly 1
970s
: Firs
t ser
ious
nee
ds fo
r civ
ilian
enc
rypt
ion
(in e
lect
roni
c ba
nkin
g)�
IBM
�s re
spon
se: L
ucife
r, an
iter
ated
SP
cip
her
�Lu
cife
r (v0
):�
Two
fixed
, 4x4
s-b
oxes
, S0
& S 1
�A
fixed
per
mut
atio
n P
�Ke
y bi
ts d
eter
min
ew
hich
s-b
ox is
to b
e us
ed a
t eac
h po
sitio
n�
8 x
64/4
= 1
28 k
ey b
its(fo
r 64-
bit b
lock
, 8 ro
unds
)...
. . .
.P
S0S
1S
0S
1S
0S
1
. . .
.S
0S
1S
0S
1S
0S
1
P. . .
.S
0S
1S
0S
1S
0S
1
x
EK(x
)G
raph
ic b
y cs
chen
@cc
.nct
u.ed
u.tw
JLM
200
6010
7 22
:16
72
From
Luc
ifer t
o D
ES
�8
fixed
, 6x4
s-b
oxes
(non
-inve
rtibl
e)�
expa
nsio
n E
(si
mpl
e du
plic
atio
n of
16
bits
) �
roun
d ke
ys a
re u
sed
only
for x
or w
ith th
e in
put
�56
-bit
key
size
�16
x 4
8 ro
und
key
bits
are
sel
ecte
d fro
m
the
56-
bit m
aste
r key
by
the
�key
sc
hedu
le�.
x
S1
S2
S8
. . .
.
P
f(x, k
i)
k i
32
⊕48
E
32 b
its
JLM
200
6010
7 22
:16
73
Itera
ted
Feis
tel C
iphe
r
Pla
inte
xt
Cip
herte
xtr Fei
stel
Rou
nds
k 1 k 2
k r
Key
Sch
edul
e
Key
JLM
200
6010
7 22
:16
74
f
Feis
tel R
ound
F(K,
X)=
non-
linea
r fun
ctio
n
k i
Gra
phic
cou
rtesy
of J
osh
Ben
aloh
Not
e: If
si(L
,R)=
(L∆
f(E(R
) ∆k i)
,R) a
nd t
(L,R
)= (R
,L),
this
roun
dis
ts
i(L,R
).
To in
vert:
sw
ap h
alve
s an
d ap
ply
sam
e tra
nsfo
rm w
ith s
ame
key:
sit
tsi(L
,R)=
(L,R
).
JLM
200
6010
7 22
:16
75
DE
S R
ound
Fun
ctio
n
Sub
-key
6/4-
bit s
ubst
itutio
ns
32-b
it pe
rmut
atio
n
32 b
its
48 b
its
Slid
e co
urte
sy o
f Jos
h B
enal
oh
JLM
200
6010
7 22
:16
76
Cha
inin
g Fe
iste
l Rou
nds
f f
k i k i+1
JLM
200
6010
7 22
:16
77
Feis
tel C
iphe
rs d
efea
t sim
ple
atta
cks
�Af
ter 2
to 4
roun
ds to
get
flat
sta
tistic
s.�
Para
llel s
yste
m a
ttack
�So
lve
for k
ey b
its o
r con
stra
in k
ey b
itsk i(
1)=
a 11(
K)p
1 c 1
+ a
12(K
)p2 c 1
+�
+ a 1
N(K
)pnc
n�
�
�
�
k i(m
)= a
m1(
K)p 1
c1 +
a m2(
K)p
2 c 1
+�
+ a m
N(K
)pnc
n
�So
lvin
g Li
near
equ
atio
ns fo
r coe
ffici
ents
det
erm
inin
g ci
pher
c 1=
f 11(K
)p1+
f 12(
K)p
2+�
+ f 1n
(K)p
nc 2
= f 21
(K)p
1+ f 2
2(K
)p2+
�+
f 2n(K
)pn
�
�
�
�c m
= f m
1(K
)p1+
f m2(
K)p
2+�
+ f m
n(K
)pn
�E
ven
a w
eak
roun
d fu
nctio
n ca
n yi
eld
a st
rong
Fei
stel
cip
her i
f ite
rate
d su
ffici
ently
.�
Prov
ided
it�s
non
-line
ar
JLM
200
6010
7 22
:16
78
DE
S
64-b
it P
lain
text
64-b
it C
iphe
rtext
56-b
it K
ey16
Fei
stel
Rou
ndsk 1
(48
bits
)k 2 k 1
6
JLM
200
6010
7 22
:16
79
f
DE
S R
ound
F(K,
X)=
non-
linea
r fun
ctio
nk i (4
8 bi
ts)
L (3
2 bi
ts)
R (3
2 bi
ts)
L� (3
2 bi
ts)
R� (
32 b
its)
JLM
200
6010
7 22
:16
80
JLM
200
6010
7 22
:16
81
JLM
200
6010
7 22
:16
82
JLM
200
6010
7 22
:16
83
DE
S D
escr
ibed
Alg
ebra
ical
ly
si(L
,R)=
(L∆
f(E(R
) ∆k i)
,R)
k i is
48
bit s
ub-k
ey fo
r rou
nd i
and
f(x)=
P(S
1S2S
3…
S8(x
)). H
ere,
eac
h S
�bo
x op
erat
es o
n 6
bit
quan
titie
s an
d ou
tput
s 4
bit q
uant
ities
. P
per
mut
es th
e re
sulti
ng 3
2 ou
tput
bits
.t(
L,R
)= (R
,L).
Eac
h ro
und
(exc
ept l
ast)
is t
si.
Not
e th
at t
t =
t 2 =
1= s
i si=
si2 .
Full
DE
S is
:D
ESK(
x)=
IP-1
s16
t ..
. s
3 t
s2
t s
1 IP
(x)
So
its in
vers
e is
DES
K-1(x
)= IP
-1s
1 t
... s
14 t
s15
t s
16 IP
(x)
JLM
200
6010
7 22
:16
84
DE
S K
ey S
ched
ule
C0D
0= P
C1(
K)
Ci+
1=
LeftS
hift(
Shi
ft i, C
i), D
i+1
= Le
ftShi
ft(Sh
ifti,
Di),
K i=
PC
2(C
i||D
i)
Shi
ft i=
<1,2
,2,2
,2,2
,2,1
,2,2
,2,2
,2,2
,1,1
>
Not
e: Ir
regu
lar K
ey s
ched
ule
prot
ects
aga
inst
rela
ted
key
atta
cks.
[Bih
am, N
ew T
ypes
of C
rypt
anal
ytic
Atta
cks
usin
g R
elat
ed K
eys,
TR
-753
, Tec
hnio
n]
JLM
200
6010
7 22
:16
85
DE
S K
ey S
ched
ule
pc1[64]
57 49 41 33 25 17 09 01 58 50 42 34 26 18 10 02
59 51 43 35 27 19 11 03 60 52 44 36 63 55 47 39
31 23 15 07 62 54 46 38 30 22 14 06 61 53 45 37
29 21 13 05 28 20 12 04 00 00 00 00 00 00 00 00
pc2[48]
14 17 11 24 01 05 03 28 15 06 21 10 23 19 12 04
26 08 16 07 27 20 13 02 41 52 31 37 47 55 30 40
51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32
JLM
200
6010
7 22
:16
86
DE
S K
ey S
ched
ule
Key
sch
edul
e ro
und
110 51 34 60 49 17 33 57 2 9 19 42 3 35 26 25 44 58 59
1 36 27 18 41
22 28 39 54 37 4 47 30 5 53 23 29 61 21 38 63 15 20 45
14 13 62 55 31
Key
sch
edul
e ro
und
22 43 26 52 41 9 25 49 59 1 11 34 60 27 18 17 36 50 51
58 57 19 10 33
14 20 31 46 29 63 39 22 28 45 15 21 53 13 30 55 7 12 37
6 5 54 47 23
JLM
200
6010
7 22
:16
87
DE
S D
ata
S4 (hex)
7 d e 3 0 6 9 a 1 2 8 5 b c 4 f
d 8 b 5 6 f 0 3 4 7 2 c 1 a e 9
a 6 9 0 c b 7 d f 1 3 e 5 2 8 4
3 f 0 6 a 1 d 8 9 4 5 b c 7 2 e
S5 (hex)
2 c 4 1 7 a b 6 8 5 3 f d 0 e 9
e b 2 c 4 7 d 1 5 0 f a 3 9 8 6
4 2 1 b a d 7 8 f 9 c 5 6 3 0 e
b 8 c 7 1 e 2 d 6 f 0 9 a 4 5 3
S6 (hex)
c 1 a f 9 2 6 8 0 d 3 4 e 7 5 b
a f 4 2 7 c 9 5 6 1 d e 0 b 3 8
9 e f 5 2 8 c 3 7 0 4 a 1 d b 6
4 3 2 c 9 5 f a b e 1 7 6 0 8 d
JLM
200
6010
7 22
:16
88
DE
S D
ata
E
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
S7 (hex)
4 b 2 e f 0 8 d 3 c 9 7 5 a 6 1
d 0 b 7 4 9 1 a e 3 5 c 2 f 8 6
1 4 b d c 3 7 e a f 6 8 0 5 9 2
6 b d 8 1 4 a 7 9 5 0 f e 2 3 c
S8 (hex)
d 2 8 4 6 f b 1 a 9 3 e 5 0 c 7
1 f d 8 a 3 7 4 c 5 6 b 0 e 9 2
7 b 4 1 9 c e 2 0 6 a d f 3 5 8
2 1 e 7 4 a 8 d f c 9 0 3 5 6 b
Note: DES can be made more secure
against linear attacks by changing
the order of the S-Boxes: Matsui,
On Correlation between the order of
S-Boxes and the Strength of DES.
Eurocrypt,94.
JLM
200
6010
7 22
:16
89
S B
oxes
as
Pol
ynom
ials
ove
r GF(
2)
1,1: 56+4+35+2+26+25+246+245+236+2356+16+15+156+14+146+145+13+135+134+1346+1
345+13456+125+1256+1245+123+12356+1234+12346
1,2: C+6+5+4+45+456+36+35+34+346+26+25+24+246+2456+23+236+235+234+2346+1+15+
156+134+13456+12+126+1256+124+1246+1245+12456+123+1236+1235+12356+
1234+12346
1,3: C+6+56+46+45+3+35+356+346+3456+2+26+24+246+245+236+16+15+145+13+1356+13
4+13456+12+126+125+12456+123+1236+1235+12356+1234+12346
1,4: C+6+5+456+3+34+346+345+2+23+234+1+15+14+146+135+134+1346+1345+1256+
124+1246+1245+123+12356+1234+12346
JLM
200
6010
7 22
:16
90
DE
S D
ata
P
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25
Not
e on
app
lyin
g pe
rmut
atio
ns:
For p
erm
utat
ions
of b
it po
sitio
ns, l
ike
P ab
ove,
the
tabl
e en
tries
con
sist
ing
of tw
o ro
ws,
the
top
row
of w
hich
is “i
n or
der”
mea
ns th
e fo
llow
ing.
If t
is
abo
ve b
, the
bit
at b
is m
oved
into
pos
ition
t in
the
perm
uted
bit
strin
g. F
or e
xam
ple,
af
ter a
pply
ing
P, a
bove
, the
mos
t sig
nific
ant b
it of
the
outp
ut s
tring
was
at p
ositi
on 1
6 of
th
e in
put s
tring
.
JLM
200
6010
7 22
:16
91
Hom
ewor
k
Rev
iew
DE
S d
escr
iptio
n by
read
ing
http
://w
ww
.aci
.net
/kal
liste
/des
.htm
orht
tp://
ww
w.it
l.nis
t.gov
/fips
pubs
/fip4
6-2.
htm
You
nee
d to
kno
w D
ES
wel
l for
a fu
ture
cla
ss a
s w
ell a
s fo
r pr
oble
m n
umbe
r 5.
JLM
200
6010
7 22
:16
92
DE
S D
ata
S1 (hex)
e 4 d 1 2 f b 8 3 a 6 c 5 9 0 7
0 f 7 4 e 2 d 1 a 6 c b 9 5 3 8
4 1 e 8 d 6 2 b f c 9 7 3 a 5 0
f c 8 2 4 9 1 7 5 b 3 e a 0 6 d
S2 (hex)
f 1 8 e 6 b 3 4 9 7 2 d c 0 5 a
3 d 4 7 f 2 8 e c 0 1 a 6 9 b 5
0 e 7 b a 4 d 1 5 8 c 6 9 3 2 f
d 8 a 1 3 f 4 2 b 6 7 c 0 5 e 9
S3 (hex)
a 0 9 e 6 3 f 5 1 d c 7 b 4 2 8
d 7 0 9 3 4 6 a 2 8 5 e c b f 1
d 6 4 9 8 f 3 0 b 1 2 c 5 a e 7
1 a d 0 6 9 8 7 4 f e 3 b 5 2 c
JLM
200
6010
7 22
:16
93
Cry
ptog
raph
ic H
ashe
s
A c
rypt
ogra
phic
has
h (�
CH
�) is
a �o
ne w
ay fu
nctio
n,� h
, fro
m a
llbi
nary
st
rings
(of a
rbitr
ary
leng
th) i
nto
a fix
ed b
lock
of s
ize
n (c
alle
d th
e si
ze
of th
e ha
sh) w
ith th
e fo
llow
ing
prop
ertie
s:1.
Giv
en y
=h(x
) it i
s in
feas
ible
to c
alcu
late
a x
� ∫x
such
that
y=h
(x�).
(�
One
way
,� �n
on-in
verti
bilit
y� o
r �pr
e-im
age�
resi
stan
ce).
Fun
ctio
ns
satis
fyin
g th
is c
ondi
tion
are
calle
d O
ne W
ay H
ash
Func
tions
(OW
HF)
2.G
iven
u, i
t is
infe
asib
le to
find
w s
uch
that
h(u
)=h(
w).
(wea
k co
llisi
on
resi
stan
ce, 2
ndpr
e-im
age
resi
stan
ce).
3.It
is in
feas
ible
to fi
nd u
, w s
uch
that
h(u
)=h(
w).
(stro
ng c
ollis
ion
resi
stan
ce).
Not
e 3!
2. F
unct
ions
sat
isfy
ing
this
con
ditio
n ar
e ca
lled
Col
lisio
n R
esis
tant
Fun
ctio
ns (C
RFs
).
�Ju
st li
ke S
ymm
etric
cip
hers
ratio
of w
ork
fact
or fo
r com
puta
tion
of
hash
vs
wor
k fa
ctor
to b
reak
has
h sh
ould
be
very
hig
h.�
Adve
rsar
y ha
s co
mpl
ete
info
rmat
ion
on c
ompu
ting
hash
and
(o
bvio
usly
) can
com
pute
as
man
y ha
shes
from
the
targ
et a
s sh
e w
ants
.
JLM
200
6010
7 22
:16
94
Obs
erva
tions
on
Cry
ptog
raph
ic H
ashe
s
�H
ashe
s ar
e a
stro
ng �c
heck
sum
��
OW
HF
and
CR
F co
nditi
ons
mak
e C
Hs
satis
fy m
any
of th
e pr
oper
ties
of �r
ando
m fu
nctio
ns�
�Sm
all c
hang
es s
houl
d cr
eate
larg
e ch
ange
s (o
ther
wis
e th
e pr
e-im
age
of n
ear n
eigh
bors
are
nea
r nei
ghbo
rs m
akin
g co
llisi
ons
easy
to
find
)�
Smal
l inp
ut c
hang
es s
houl
d be
sta
tistic
ally
unr
elat
ed (u
ncor
rela
ted)
to
cha
nges
in a
sub
set o
f the
has
h bi
ts�
Anal
ysis
of C
Hs
very
sim
ilar t
o S
ymm
etric
Cip
her t
echn
ique
sP
opul
ar p
ract
ical
cry
ptog
raph
ic h
ashe
s�
MD
4, M
D5
(now
�bro
ken�
)�
SH
A-1
, SH
A-2
24, S
HA
-256
, SH
A-3
84, S
HA
-512
(las
t 4 a
re �S
HA
-2�)
�R
IPE
MD
JLM
200
6010
7 22
:16
95
Obs
erva
tions
�C
ollis
ion
Res
ista
nce !
2nd
pre-
imag
e re
sist
ance
�Le
t f(x
)= x
2 -1
(mod
p).
�
f(x) a
cts
like
a ra
ndom
func
tion
but i
s no
t a O
WH
F si
nce
squa
re ro
ots
are
easy
to
calc
ulat
e m
od p
.�
Let f
(x)=
x2
(mod
pq)
. �
f(x) i
s a
OW
HF
but i
s ne
ither
col
lisio
n no
r 2nd
pre-
imag
e re
sist
ant
�If
eith
er h
1(x)
or h
2(x)
is a
CR
HF
so is
h(x
)= h
1(x)
|| h
2(x)
�
MD
C+s
igna
ture
& M
AC+u
nkno
wn
Key
requ
ire a
ll th
ree
prop
ertie
s�
Idea
l Wor
k Fa
ctor
s:
Key
reco
very
, com
puta
tiona
l res
ista
nce
2tM
ACC
ollis
ion
2n/2
CR
HF
Pre-
imag
e2n
dPr
e-im
age
2nO
WH
FPr
oper
tyW
ork
Type
JLM
200
6010
7 22
:16
96
Wha
t are
Has
h Fu
nctio
ns G
ood
for?
�M
odifi
catio
n D
etec
tion
Cod
es (M
DC
s): T
his
is a
stro
ng
chec
ksum
(int
egrit
y ch
eck)
. Som
etim
es c
alle
d �u
nkey
ed�
hash
es.
�M
essa
ge A
uthe
ntic
atio
n C
ode
(MA
Cs)
: If s
hare
d se
cret
is
part
of th
e ha
sh,
two
parti
es c
an d
eter
min
e au
then
ticat
ed
inte
grity
with
CH
s. C
alle
d �k
eyed
has
hes�
.�
Mes
sage
Dig
ests
(MD
s):
Enc
rypt
ing
(with
priv
ate
key)
the
CH
of a
mes
sage
(its
MD
) act
s as
a c
ertif
icat
ion
that
the
mes
sage
was
�app
rove
d� b
y po
sses
sor o
f priv
ate
key.
Thi
s is
cal
led
a D
igita
l Sig
natu
re.
[Not
e: y
ou c
ould
�sig
n� th
e w
hole
mes
sage
rath
er th
an th
e ha
sh b
ut th
is w
ould
take
oo
dles
of t
ime
by c
ompa
rison
.]
JLM
200
6010
7 22
:16
97
Wha
t are
Has
h Fu
nctio
ns G
ood
for?
�U
niqu
ely
and
secu
rely
iden
tifie
s bi
t stre
ams
like
prog
ram
s.
Has
h is
stro
ng n
ame
for p
rogr
am.
�En
tropy
mix
ing:
Sin
ce C
Hs
are
rand
om fu
nctio
ns in
to fi
xed
size
blo
cks
with
the
prop
ertie
s of
rand
om fu
nctio
ns, t
hey
are
ofte
n us
ed to
�mix
� bia
sed
inpu
t to
prod
uce
a �s
eed�
for a
ps
uedo
-ran
dom
num
ber g
ener
ator
.�
Pass
wor
d P
rote
ctio
n: S
tore
sal
ted
hash
of p
assw
ord
inst
ead
of p
assw
ord
(Nee
dham
).�
Bit C
omm
ittm
ent
JLM
200
6010
7 22
:16
98
One
-Way
Fun
ctio
ns
Has
hes
com
e fro
m tw
o ba
sic
clas
ses
of o
ne-w
ay fu
nctio
ns�
Mat
hem
atic
al�
Mul
tiplic
atio
n: Z
=X�Y
�M
odul
ar E
xpon
entia
tion:
Z =
YX(m
od n
) (C
haum
vP
Has
h)�
Ad-h
oc (S
ymm
etric
cip
her-
like
cons
truct
ions
)�
Cus
tom
Has
h fu
nctio
ns (M
D4,
SH
A, M
D5,
RIP
EM
D)
JLM
200
6010
7 22
:16
99
Cha
um-v
anH
eijs
t-Pfit
zman
n C
ompr
essi
on F
unct
ion
�Su
ppos
e p
is p
rime,
q=(
p-1)
/2 is
prim
e, a
is a
prim
itive
root
in F
p, b
is
rand
om.
�g:
{1,2
,�,q
-1}2!
{1,2
,�,p
-1},
q=(p
-1)/2
by:
�g(
s, t)
= a
sbt
(mod
p)
�N
ot u
sed
in p
ract
ice:
too
slow
.�
Red
uctio
n to
dis
cret
e lo
g:Su
ppos
e g(
s, t)
= g(
u, v
) can
be
foun
d. T
hen
asbt
(mod
p)=
au
bv(m
od p
). S
o as
-u(m
od p
)= b
v-t(m
od p
). L
et b
= ax
(mod
p).
The
n (s
-u)=
x(y-
t) (m
od p
-1).
But p
-1=
2q s
o w
e ca
n so
lve
for x
, thu
s de
term
inin
g th
e di
scre
te lo
g of
b.
JLM
200
6010
7 22
:16
100
Mer
kle/
Dam
gard
Con
stru
ctio
n
Com
pres
sion
Func
tion
(f)
Has
h V
alue
Pad
ded
n bi
t blo
cks
Hi-1
Gra
phic
by
Josh
Ben
aloh
Inpu
t: x=
x 1||�
||xt
Inpu
t is
usua
lly p
adde
d
H0=
IVH
i= f(
Hi-1
, xi)
h(x)
= g(
h t)
JLM
200
6010
7 22
:16
101
A C
rypt
ogra
phic
Has
h: S
HA
-1
Com
pres
sion
Func
tion
160-
bit s
tate
512-
bit i
nput
160
bits
of s
tate
Slid
e by
Jos
h B
enal
oh
JLM
200
6010
7 22
:16
102
A C
rypt
ogra
phic
Has
h: S
HA
-1 Pic
ture
from
Wik
iped
ia
JLM
200
6010
7 22
:16
103
Pad
ding
�St
anda
rd te
chni
que
�Le
t las
t mes
sage
blo
ck h
ave
k bi
ts.
If k=
n, m
ake
a ne
w
bloc
k an
d se
t k=
0.�
Appe
nd a
1 to
last
blo
ck le
avin
g r=
n-k-
1 re
mai
ning
bits
in
blo
ck.
�If
r>=6
4, a
ppen
d r-6
4 0s
then
app
end
bit l
engt
h of
in
put e
xpre
ssed
as
64 b
it un
sign
ed in
tege
r�
If r<
64, a
ppen
d n-
r0�s
(to
fill o
ut b
lock
), ap
pend
n-6
4 0�
s at
beg
inni
ng o
f nex
t blo
ck th
en a
ppen
d bi
t len
gth
of
inpu
t exp
ress
ed a
s 64
bit
unsi
gned
inte
ger
JLM
200
6010
7 22
:16
104
Tech
niqu
e fo
r CH
s fro
m B
lock
Cip
hers
Let i
nput
be
x= x
1||
x 2||
� ||
xtw
here
eac
h x i
is n
bits
long
. Le
t g b
e a
func
tion
taki
ng a
n n
bit i
nput
to a
n m
bit
inpu
t. L
et E
(k, x
) be
a bl
ock
ciph
er w
ith m
bit
keys
pace
and
n bi
t blo
ck.
Let H
0= IV
.
Con
stru
ctio
n 1
Hi=
E(g
(Hi-1
), x i)
⊕H
i-1
Con
stru
ctio
n 2
Hi=
E(x
i, H
i-1) ⊕
Hi-1
Con
stru
ctio
n 3
Hi=
E(g
(Hi-1
), x i)
⊕x i
⊕H
i-1
Not
e: B
ecau
se o
f col
lisio
ns n
sho
uld
be >
64.
Idea
lly, m
=n a
nd g
= id
. D
ES
w
ith n
= 64
is to
o sm
all.
AE
S w
ith n
=m=1
28 is
bet
ter.
JLM
200
6010
7 22
:16
105
Birt
hday
Atta
cks
�Pr
obab
ility
of c
ollis
ion
dete
rmin
ed b
y �B
irthd
ay P
arad
ox�
calc
ulat
ion:
�
(1-1
/n) (
1-2/
n) �
(1-(k
-1)/n
)= (n
!/k!)/
nk
�Pr
obab
ility
of c
ollis
ion
is >
.5 w
hen
k2>
n.�
Nee
d 28
0 bl
ocks
for S
HA
.�
1+x c
ex, P
i=1i=
k(1
-i/n)
ce-
k(k-
1)/(2
n)
JLM
200
6010
7 22
:16
106
Atta
cks
on C
rypt
ogra
phic
Has
hes
�Be
rson
(199
2) u
sing
diff
eren
tial c
rypt
anal
ysis
on
1 ro
und
MD
-5.
�Bo
er a
nd B
osse
laer
s (1
993)
, Pse
udo
colli
sion
in M
D5.
�D
obbe
rtin
(199
6), C
ollis
ions
in c
ompr
essi
on fu
nctio
n. A
ttack
s in
spire
d R
IPE
MD
pro
posa
l.�
Bih
am a
nd C
hen
(200
4), C
ollis
ions
in S
HA
-0.
�C
haba
ud a
nd J
oux
(200
4), C
ollis
ions
in S
HA
-0 .
�W
ang,
Fen
g, L
ai, Y
u, (2
004)
, MD
4, M
D5,
RIP
EM
D�
Wan
g et
al,
(200
4, 2
005)
, SH
A-1
�S
HA
-1 h
as s
tood
up
best
: be
st k
now
n th
eore
tical
atta
ck (1
1/05
) req
uire
s 263
oper
atio
ns.
JLM
200
6010
7 22
:16
107
MA
Cs
usin
g H
ashe
s
�Pr
efix
and
suf
fix a
ttack
s�
Has
h(k 1
, Has
h(k 2
, m))
�H
ash(
k|p|
m|k
)
�H
MAC
K(x
)= S
HA-
1(K⊕
opad
|| S
HA
-1(K
⊕ip
ad)||
x)
JLM
200
6010
7 22
:16
108
Win
now
ing
and
Cha
ffing
(Riv
est)
�W
ant t
o se
nd 1
001.
Pic
k ra
ndom
stre
am (m
i) an
d em
bed
mes
sage
at p
ositi
ons
(say
) 3, 7
, 8 1
4 M
AC
ea
ch p
acke
t (m
mi).
�M
ake
sure
MA
C is
cor
rect
onl
y in
mes
sage
po
sitio
ns
JLM
200
6010
7 22
:16
109
Hom
ewor
k 1-
Que
stio
n 1
Enc
rypt
the
follo
win
g m
essa
ge u
sing
a V
igen
iere
ciph
er w
ith d
irect
st
anda
rd a
lpha
bets
. K
ey: J
OS
H.
All persons born or naturalized in the United States, and
subject to the jurisdiction thereof, are citizens of the
United States and of the state wherein they reside. No
state shall make or enforce any law which shall abridge
the privileges or immunities of citizens of the United
States; nor shall any state deprive any person of life,
liberty, or property, without due process of law; nor deny
to any person within its jurisdiction the equal protection
of the laws.
Upp
er c
ase
only
! Tu
rn p
lain
and
cip
her t
ext i
nto
5 le
tter g
roup
s.C
alcu
late
the
inde
x of
coi
ncid
ence
of t
he p
lain
text
and
cip
herte
xt.
Bre
ak th
e ci
pher
text
into
4 c
olum
ns.
Wha
t is
the
inde
x of
coi
ncid
ence
of
each
col
umn?
JLM
200
6010
7 22
:16
110
Hom
ewor
k 1-
Que
stio
n 1
(add
endu
m)
ALLPE RSONS BORNO RNATU RALIZ EDINT HEUNI TEDST ATESA NDSUB JECTT
OTHEJ URISD ICTIO NTHER EOFAR ECITI ZENSO FTHEU NITED STATE SANDO
FTHES TATEW HEREI NTHEY RESID ENOST ATESH ALLMA KEORE NFORC EANYL
AWWHI CHSHA LLABR IDGET HEPRI VILEG ESORI MMUNI TIESO FCITI ZENSO
FTHEU NITED STATE SNORS HALLA NYSTA TEDEP RIVEA NYPER SONOF LIFEL
IBERT YORPR OPERT YWITH OUTDU EPROC ESSOF LAWNO RDENY TOANY PERSO
NWITH INITS JURIS DICTI ONTHE EQUAL PROTE CTION OFTHE LAWS
JLM
200
6010
7 22
:16
111
Hom
ewor
k 1-
Que
stio
n 2
Bre
ak th
e V
igen
iere
base
d ci
pher
text
belo
w.
Pla
inte
xt a
nd c
iphe
rtext
alph
abet
s ar
e di
rect
sta
ndar
d.W
hat i
s th
e ke
y le
ngth
? W
hat i
s th
e ke
y?
If th
e ke
y le
ngth
is k
, how
long
a c
orre
spon
ding
pla
in, c
iphe
rtext
sequ
ence
be
giv
en to
sol
ve?
Can
you
giv
e an
upp
er b
ound
on
the
pure
ci
pher
text
leng
th n
eede
d?
IGDLK MJSGC FMGEP PLYRC IGDLA TYBMR KDYVY XJGMR TDSVK ZCCWG ZRRIP
UERXY EEYHE UTOWS ERYWC QRRIP UERXJ QREWQ FPSZC ALDSD ULSWF FFOAM
DIGIY DCSRR AZSRB GNDLC ZYDMM ZQGSS ZBCXM OYBID APRMK IFYWF MJVLY
HCLSP ZCDLC NYDXJ QYXHD APRMQ IGNSU MLNLG EMBTF MLDSB AYVPU TGMLK
MWKGF UCFIY ZBMLC DGCLY VSCXY ZBVEQ FGXKN QYMIY YMXKM GPCIJ HCCEL
PUSXF MJVRY FGYRQ
JLM
200
6010
7 22
:16
112
Hom
ewor
k 1-
Que
stio
n 3
Con
side
r a m
essa
ge s
ourc
e M
(x) w
ith th
e fo
llow
ing
dist
ribut
ion:
M: P
(x=0
)= p
M: P
(x=1
)= q
, with
p+q
=1an
d a
one
time
pad
sele
cted
from
dis
tribu
tion
P(x
)P
: P(x
=0)=
½P
: P(x
=1)=
½C
onsi
der t
he c
iphe
rtext
form
ed b
y �x
orin
g� th
e m
essa
ge m
with
the
pad
p, s
o th
at c
= m∆
pW
hat i
s th
e ci
pher
text
dist
ribut
ion
C?
Cal
cula
te H
(M),
H(P
), H
(C).
Cal
cula
te:
I(M|C
)= H
(M)-
H(M
|C)
Sup
pose
, P: P
(x=0
)=3/
4 an
d P
(x=1
)=1/
4. W
hat i
s th
e ci
pher
text
dist
ribut
ion
and
H(M
), H
(P),
H(C
) and
I(M
|C) n
ow.
JLM
200
6010
7 22
:16
113
Hom
ewor
k 1-
Que
stio
n 4
Cal
cula
te th
e ou
tput
of t
he fi
rst t
wo
roun
ds o
f DE
S w
ith in
put m
essa
ge
0x31
3233
3435
3637
38 a
nd k
ey 0
x00a
bcde
fabc
def8
9.
The
inpu
t to
roun
d 1
(afte
r ini
tial p
erm
utat
ion)
and
the
first
2 ro
und
keys
are
giv
en
belo
w.
For f
ixed
key
, DE
S is
a p
erm
utat
ion
on 2
64le
tters
. A
ppro
xim
atel
y ho
w m
any
such
per
mut
atio
ns a
re th
ere?
(H
int:
Use
S
tirlin
g�s
appr
oxim
atio
n.)
Com
pare
this
to th
e si
ze o
f the
key
spa
ce fo
r DE
S.
Round 01 Key: 01001111 01010111 00000111 10111001 01011100 10101011
Round 02 Key: 00101111 00100111 01101001 00111011 01111111 00100100
Input to DES: 00110100 00110011 00110010 00110001
00111000 00110111 00110110 00110101
Round 1 Input: 00000000 11111111 11100001 10101010
00000000 11111111 00010000 01100110
JLM
200
6010
7 22
:16
114
Hom
ewor
k 1-
Que
stio
n 5
(Ext
ra
Cre
dit)
Giv
en a
one
roto
r mac
hine
, M, d
epic
ted
belo
w w
ith e
quat
ion
Ci R
-1C
-iU
C-i R
Ci (
p)=c
with
C, U
, R b
elow
.
R:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
EKMFLGDQVZNTOWYHXUSPAIBRCJ
U: ABCDEFGHIJKLMNOPQRSTUVWXYZ
YRUHQSLDPXNGOKMIEBFZCWVJAT
C: T
he c
yclic
per
mut
atio
n A!
B, B
!C
, etc
UR
Lam
ps
Keyb
oard
JLM
200
6010
7 22
:16
115
Hom
ewor
k 1-
Que
stio
n 5
(con
t)
Cal
cula
te th
e ci
pher
text
deriv
ed fr
om th
e pl
aint
ext: HELLOWORLD
Wha
t do
you
thin
k th
e in
dex
of c
oinc
iden
ce o
f the
cip
herte
xtfro
m a
50
lette
r mes
sage
is?
If th
e ke
y w
as th
e �s
tarti
ng p
ositi
on,�
i, of
M, h
ow m
any
lette
rsof
cor
resp
ondi
ng p
lain
/cip
her t
ext w
ould
you
nee
d to
find
the
key?
How
m
any
ciph
erte
xton
ly le
tters
?
The
follo
win
g m
ay b
e he
lpfu
l:R
-1ABCDEFGHIJKLMNOPQRSTUVWXYZ
UWYGADFPVZBECKMTHXSLRINQOJ
JLM
200
6010
7 22
:16
116
Gen
eral
Mod
ern
Ref
eren
ces
Bla
ke, S
erou
ssi,
and
Sm
art,
Elli
ptic
Cur
ves
in C
rypt
ogra
phy,
Cam
brid
ge
Bre
ssou
d an
d W
agon
, Com
puta
tiona
l Num
ber T
heor
y. K
ey P
ress
.B
ach
and
Sha
llit,
Alg
orith
mic
Num
ber T
heor
y.B
erle
kam
p, A
lgeb
raic
Cod
ing
Theo
ry.
Rep
rinte
d by
Aeg
ean
Par
k P
ress
.B
iham
and
Sha
mir,
Diff
eren
tial C
rypt
anal
ysis
of D
ES
. Spr
inge
r.B
oneh
, Tw
enty
Yea
rs o
f atta
cks
on R
SA
. N
otic
es A
MS
.B
uchm
ann,
Intro
duct
ion
to C
rypt
ogra
phy.
Spr
inge
r.C
ohen
, A C
ours
e in
Com
puta
tiona
l Alg
ebra
ic N
umbe
r The
ory.
Spr
inge
r.D
amga
rd, L
ectu
res
on D
ata
Sec
urity
. Spr
inge
r.G
olum
b, S
hift
Reg
iste
r Seq
uenc
es.
Rep
rinte
d by
Aeg
ean
Par
k P
ress
.K
oblit
z, A
Cou
rse
in N
umbe
r The
ory
and
Cry
ptog
raph
y. S
prin
ger.
Kob
litz,
Alg
ebra
ic A
spec
ts o
f Cry
ptog
raph
y. S
prin
ger.
Kon
heim
, Cry
ptog
raph
y: A
Prim
er.
Wile
y.
JLM
200
6010
7 22
:16
117
Gen
eral
Mod
ern
Ref
eren
ces
Land
au, D
ES
, AE
S,
Sur
vey
artic
le.
Not
ices
AM
S.
Mac
Will
iam
s et
. al.,
The
ory
of E
rror
Cor
rect
ing
Cod
es.
Nor
th H
olla
nd.
Men
ezes
, van
Oor
shot
, Van
ston
e, H
andb
ook
of A
pplie
d C
rypt
ogra
phy.
(O
nlin
e: h
ttp://
ww
w.c
acr.m
ath.
uwat
erlo
o.ca
/hac
/). C
RC
Pre
ss.
Rhe
e, C
rypt
ogra
phy
and
Sec
ure
Com
mun
icat
ions
.R
ives
t, C
lass
not
es o
n S
ecur
ity a
nd C
rypt
o on
line.
(web
.mit.
edu)
.S
chne
ier,
App
lied
Cry
ptog
raph
y. W
iley.
Sim
ovits
, The
DE
S: D
ocum
enta
tion
and
Eva
luat
ion.
Aeg
ean
Par
k P
ress
.S
tinso
n, C
rypt
ogra
phy:
The
ory
and
Pra
ctic
e. C
RC
Pre
ss.
Wel
ch, C
odes
and
Cry
ptog
raph
y. O
xfor
d.
Web
site
s: w
ww
.rsa.
com
, ww
w.c
ount
erpa
ne.c
om, w
ww
.iacr
.org
has
load
s of
pre
prin
ts.
JLM
200
6010
7 22
:16
118
End
Pap
er
�D
one