Cryptography Reference
In-Depth Information
the notation (0
,
2
,
5) refers to the polynomial 1 +
x
2
+
x
5
. Note that there are many
primitive polynomials for every given degree
m
. For instance, there exist 69,273,666
different primitive polynomials of degree
m
= 31.
Table 2.3
Primitive polynomials for maximum-length LFSRs
(0,1,2)
(0,1,3,4,24) (0,1,46)
(0,1,5,7,68)
(0,2,3,5,90)
(0,3,4,5,112)
(0,1,3)
(0,3,25)
(0,5,47)
(0,2,5,6,69)
(0,1,5,8,91)
(0,2,3,5,113)
(0,1,4)
(0,1,3,4,26) (0,2,3,5,48) (0,1,3,5,70)
(0,2,5,6,92)
(0,2,3,5,114)
(0,2,5)
(0,1,2,5,27) (0,4,5,6,49) (0,1,3,5,71)
(0,2,93)
(0,5,7,8,115)
(0,1,6)
(0,1,28)
(0,2,3,4,50) (0,3,9,10,72) (0,1,5,6,94)
(0,1,2,4,116)
(0,1,7)
(0,2,29)
(0,1,3,6,51) (0,2,3,4,73)
(0,11,95)
(0,1,2,5,117)
(0,1,3,4,8)
(0,1,30)
(0,3,52)
(0,1,2,6,74)
(0,6,9,10,96) (0,2,5,6,118)
(0,1,9)
(0,3,31)
(0,1,2,6,53) (0,1,3,6,75)
(0,6,97)
(0,8,119)
(0,3,10)
(0,2,3,7,32) (0,3,6,8,54) (0,2,4,5,76)
(0,3,4,7,98)
(0,1,3,4,120)
(0,2,11)
(0,1,3,6,33) (0,1,2,6,55) (0,2,5,6,77)
(0,1,3,6,99)
(0,1,5,8,121)
(0,3,12)
(0,1,3,4,34) (0,2,4,7,56) (0,1,2,7,78)
(0,2,5,6,100) (0,1,2,6,122)
(0,1,3,4,13) (0,2,35)
(0,4,57)
(0,2,3,4,79)
(0,1,6,7,101) (0,2,123)
(0,5,14)
(0,2,4,5,36) (0,1,5,6,58) (0,2,4,9,80)
(0,3,5,6,102) (0,37,124)
(0,1,15)
(0,1,4,6,37) (0,2,4,7,59) (0,4,81)
(0,9,103)
(0,5,6,7,125)
(0,1,3,5,16) (0,1,5,6,38) (0,1,60)
(0,4,6,9,82)
(0,1,3,4,104) (0,2,4,7,126)
(0,3,17)
(0,4,39)
(0,1,2,5,61) (0,2,4,7,83)
(0,4,105)
(0,1,127)
(0,3,18)
(0,3,4,5,40) (0,3,5,6,62) (0,5,84)
(0,1,5,6,106) (0,1,2,7,128)
(0,1,2,5,19) (0,3,41)
(0,1,63)
(0,1,2,8,85)
(0,4,7,9,107)
(0,3,20)
(0,1,2,5,42) (0,1,3,4,64) (0,2,5,6,86)
(0,1,4,6,108)
(0,2,21)
(0,3,4,6,43) (0,1,3,4,65) (0,1,5,7,87)
(0,2,4,5,109)
(0,1,22)
(0,5,44)
(0,3,66)
(0,8,9,11,88) (0,1,4,6,110)
(0,5,23)
(0,1,3,4,45) (0,1,2,5,67) (0,3,5,6,89)
(0,2,4,7,111)
2.3.2 Known-Plaintext Attack Against Single LFSRs
As indicated by its name, LFSRs are linear. Linear systems are governed by linear
relationships between their inputs and outputs. Since linear dependencies can rela-
tively easily be analyzed, this can be a major advantage, e.g., in communication sys-
tems. However, a cryptosystem where the key bits only occur in linear relationships
makes a highly insecure cipher. We will now investigate how the linear behavior of
a LFSR leads to a powerful attack.
If we use an LFSR as a stream cipher, the secret key
k
is the feedback coefficient
vector (
p
m
−
1
,...,
p
1
,
p
0
). An attack is possible if the attacker Oscar knows some
plaintext and the corresponding ciphertext. We further assume that Oscar knows the
degree
m
of the LFSR. The attack is so efficient that he can easily try a large num-
ber of possible
m
values, so that this assumption is not a major restriction. Let the
known plaintext be given by
x
0
,
x
1
,...,
x
2
m
−
1
and the corresponding ciphertext by
y
0
,
y
1
,...,
y
2
m
−
1
. With these 2
m
pairs of plaintext and ciphertext bits, Oscar recon-
structs the first 2
m
key stream bits:
s
i
≡
x
i
+
y
i
mod 2;
i
= 0
,
1
,...,
2
m
−
1
.
The goal is now to find the key which is given by the feedback coefficients
p
i
.
