EarthWeb   

HomeAccount InfoLoginSearchMy ITKnowledgeFAQSitemapContact Us
     

   
  All ITKnowledge
  Source Code

  Search Tips
  Advanced Search
   
  

  

Applied Cryptography, Second Edition: Protocols,  Algorthms, and Source Code in C Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C
by Bruce Schneier
Wiley Computer Publishing, John Wiley & Sons, Inc.
ISBN: 0471128457   Pub Date: 01/01/96
  Buy ItBookmark It

Search this book:
 
Previous Table of Contents Next


In order for a particular LFSR to be a maximal-period LFSR, the polynomial formed from a tap sequence plus the constant 1 must be a primitive polynomial mod 2. The degree of the polynomial is the length of the shift register. A primitive polynomial of degree n is an irreducible polynomial that divides x2n-1 + 1, but not xd + 1 for any d that divides 2n - 1 (see Section 11.3). For the mathematical theory behind all this, consult [643,1649,1648].


Figure 16.3  4-bit LFSR.

In general, there is no easy way to generate primitive polynomials mod 2 for a given degree. The easiest way is to choose a random polynomial and test whether it is primitive. This is complicated—something like testing random numbers for primality—but many mathematical software packages do this. See [970,971] for some methods.

Table 16.2 lists some, but by no means all, primitive polynomials mod 2 of varying degrees [1583,643,1649,1648,1272,691]. For example, the listing (32, 7, 5, 3, 2, 1, 0) means that the following polynomial is primitive modulo 2:

x32 + x7 + x5 + x3 + x2 + x + 1

It’s easy to turn this into a maximal-period LFSR. The first number is the length of the LFSR. The last number is always 0 and can be ignored. All the numbers, except the 0, specify the tap sequence, counting from the left of the shift register. That is, low degree terms in the polynomial correspond to taps near the left-hand side of the register.

To continue the example, the listing (32, 7, 5, 3, 2, 1, 0) means that if you take a 32-bit shift register and generate the new bit by XORing the thirty-second, seventh, fifth, third, second, and first bits together (see Figure 16.4), the resultant LFSR will be maximal length; it will cycle through 232 - 1 values before repeating.

The C code for this LFSR looks like:

int LFSR () {
     static unsigned long ShiftRegister = 1;
     /* Anything but 0. */
     ShiftRegister = ((((ShiftRegister >> 31)
                ^ (ShiftRegister >> 6)
                ^ (ShiftRegister >> 4)
                ^ (ShiftRegister >> 2)
                ^ (ShiftRegister >> 1)
                ^ ShiftRegister))
                & 0×00000001)
                << 31)
                | (ShiftRegister >> 1) ;
     return ShiftRegister & 0×00000001;
}


Figure 16.4  32-bit long maximal-length LFSR.

Table 16.2
Some Primitive Plynomials Mod 2

(1, 0) (36, 11, 0) (68, 9, 0) (97, 6, 0)
(2, 1, 0) (36, 6, 5, 4, 2, 1, 0) (68, 7, 5, 1, 0) (98, 11, 0)
(3, 1, 0) (37, 6, 4, 1, 0) (69, 6, 5, 2, 0) (98, 7, 4, 3, 1, 0)
(4, 1, 0) (37, 5, 4, 3, 2, 1, 0) (70, 5, 3, 1, 0) (99, 7, 5, 4, 0)
(5, 2, 0) (38, 6, 5, 1, 0) (71, 6, 0) (100, 37, 0)
(6, 1, 0) (39, 4, 0) (71, 5, 3, 1, 0) (100, 8, 7, 2, 0)
(7, 1, 0) (40, 5, 4, 3, 0) (72, 10, 9, 3, 0) (101, 7, 6, 1, 0)
(7, 3, 0) (41, 3, 0) (72, 6, 4, 3, 2, 1, 0) (102, 6 5 3 0)
(8, 4, 3, 2, 0) (42, 7, 4, 3, 0) (73, 25, 0) (103, 9, 9)
(9, 4, 0) (42, 5, 4, 3, 2, 1, 0) (73, 4, 3, 2, 0) (104, 11, 10, 1, 0)
(10, 3, 0) (43, 6, 4, 3, 0) (74, 7, 4, 3, 0) (105, 16, 0)
(11, 2, 0) (44, 6, 5, 2, 0) (75, 6, 3, 1, 0) (106, 15, 0)
(12, 6, 4, 1, 0) (45, 4, 3, 1, 0) (76, 5, 4, 2, 0) (107, 9, 7, 4, 0)
(13, 4, 3, 1, 0) (46, 8, 7, 6, 0) (77, 6, 5, 2, 0) (108, 31, 0)
(14, 5, 3, 1, 0) (46, 8, 5, 3, 2, 1, 0) (78, 7, 2, 1, 0) (109, 5, 4, 2, 0)
(15, 1, 0) (47, 5, 0) (79, 9, 0) (110, 6, 4, 1, 0)
(16, 5, 3, 2, 0) (48, 9, 7, 4, 0) (79, 4, 3, 2, 0) (111, 10, 0)
(17, 3, 0) (48, 7, 5, 4, 2, 1, 0) (80, 9, 4, 2, 0) (111, 49, 0)
(17, 5, 0) (49, 9, 0) (80, 7, 5, 3, 2, 1, 0) (113, 9, 0)
(17, 6, 0) (49, 6, 5, 4, 0) (81, 4, 0) (113, 15, 0)
(18, 7, 0) (50, 4, 3, 2, 0) (82, 9, 6, 4, 0) (113, 30, 0)
(18, 5, 2, 1, 0) (51, 6, 3, 1, 0) (82, 8, 7, 6, 1, 0) (114, 11, 2, 1, 0)
(19, 5, 2, 1, 0) (52, 3, 0) (83, 7, 4, 2, 0) (115, 8, 7, 5, 0)
(20, 3, 0) (53, 6, 2, 1, 0) (84, 13, 0) (116, 6, 5, 2, 0)
(21, 2, 0) (54, 8, 6, 3, 0) (84, 8, 7, 5, 3, 1, 0) (117, 5, 2, 1, 0)
(22, 1, 0) (54, 6, 5, 4, 3, 2, 0) (85, 8, 2, 1, 0) (118, 33, 0)
(23, 5, 0) (55, 24, 0) (86, 6, 5, 2, 0) (119, 8, 0)
(24, 4, 3, 1, 0) (55, 6, 2, 1, 0) (87, 13, 0) (119, 45, 0)
(25, 3, 0) (56, 7, 4, 2, 0) (87, 7, 5, 1, 0) (120, 9, 6, 2, 0)
(26, 6, 2, 1, 0) (57, 7, 0) (88, 11, 9, 8, 0) (121, 18, 0)
(27, 5, 2, 1, 0) (57, 5, 3, 2, 0) (88, 8, 5, 4, 3, 1, 0) (122, 6, 2, 1, 0)
(28, 3, 0) (58, 19, 0) (89, 38, 0) (123, 2, 0)
(29, 2, 0) (58, 6, 5, 1, 0) (89, 51, 0) (124, 37, 0)
(30, 6, 4, 1, 0) (59, 7, 4, 2, 0) (89, 6, 5, 3, 0) (125, 7, 6, 5, 0)
(31, 3, 0) (59, 6, 5, 4, 3, 1, 0) (90, 5, 3, 2, 0) (126, 7, 4, 2, 0)
(31, 6, 0) (60, 1, 0) (91, 8, 5, 1, 0) (127, 1, 0)
(31, 7, 0) (61, 5, 2, 1, 0) (91, 7, 6, 5, 3, 2, 0) (127, 7, 0)
(31, 13, 0) (62, 6, 5, 3, 0) (92, 6, 5, 2, 0) (127, 63, 0)
(32, 7, 6, 2, 0) (63, 1, 0) (93, 2, 0) (128, 7, 2, 1, 0)
(32, 7, 5, 3, 2, 1, 0) (64, 4, 3, 1, 0) (94, 21, 0) (129, 5, 0)
(33, 13, 0) (65, 18, 0) (94, 6, 5, 1, 0) (130, 3, 0)
(33, 16, 4, 1, 0) (65, 4, 3, 1, 0) (95, 11, 0) (131, 8, 3, 2, 0)
(34, 8, 4, 3, 0) (66, 9, 8, 6, 0) (95, 6, 5, 4, 2, 1, 0) (132, 29, 0)
(34, 7, 6, 5, 2, 1, 0) (66, 8, 6, 5, 3, 2, 0) (96, 10, 9, 6, 0) (133, 9, 8, 2, 0)
(35, 2, 0) (67, 5, 2, 1, 0) (96, 7, 6, 4, 3, 2, 0) (134, 57, 0)
(135, 11, 0) (152, 6, 3, 2, 0) (178, 87, 0) (270, 133, 0)
(135, 16, 0) (153, 1, 0) (183, 56, 0) (282, 35, 0)
(135, 22, 0) (153, 8, 0) (194, 87, 0) (282, 43, 0)
(136, 8, 3, 2, 0) (154, 9, 5, 1, 0) (198, 65, 0) (286, 69, 0)
(137, 21, 0) (155, 7, 5, 4, 0) (201, 14, 0) (286, 73, 0)
(138, 8, 7, 1, 0) (156, 9, 5, 3, 0) (201, 17, 0) (294, 61, 0)
(139, 8, 5, 3, 0) (157, 6, 5, 2, 0) (201, 59, 0) (322, 67, 0)
(140, 29, 0) (158, 8, 6, 5, 0) (201, 79, 0) (333, 2, 0)
(141, 13, 6, 1, 0) (159, 31, 0) (202, 55, 0) (350, 53, 0)
(142, 21, 0) (159, 34, 0) (207, 43, 0) (366, 29, 0)
(143, 5, 3, 2, 0) (159, 40, 0) (212, 105, 0) (378, 43, 0)
(144, 7, 4, 2, 0) (160, 5, 3, 2, 0) (218, 11, 0) (378, 107, 0)
(145, 52, 0) (161, 18, 0) (218, 15, 0) (390, 89, 0)
(145, 69, 0) (161, 39, 0) (218, 71, 0) (462, 73, 0)
(146, 5, 3, 2, 0) (161, 60, 0) (218, 83, 0) (521, 32, 0)
(147, 11, 4, 2, 0) (162, 8, 7, 4, 0) (225, 32, 0) (521, 48, 0)
(148, 27, 0) (163, 7, 6, 3, 0) (225, 74, 0) (521, 158, 0)
(149, 10, 9, 7, 0) (164, 12, 6, 5, 0) (225, 88, 0) (521, 168, 0)
(150, 53, 0) (165, 9, 8, 3, 0) (225, 97, 0) (607, 105, 0)
(151, 3, 0) (166, 10, 3, 2, 0) (225, 109, 0) (607, 147, 0)
(151, 9, 0) (167, 6, 0) (231, 26, 0) (607, 273, 0)
(151, 15, 0) (170, 23, 0) (231, 34, 0) (1279, 216, 0)
(151, 31, 0) (172, 2, 0) (234, 31, 0) (1279, 418, 0)
(151, 39, 0) (174, 13, 0) (234, 103, 0) (2281, 715, 0)
(151, 43, 0) (175, 6, 0) (236, 5, 0) (2281, 915, 0)
(151, 46, 0) (175, 16, 0) (250, 103, 0) (2281, 1029, 0)
(151, 51, 0) (175, 18, 0) (255, 52, 0) (3217, 67, 0)
(151, 63, 0) (175, 57, 0) (255, 56, 0) (3217, 576, 0)
(151, 66, 0) (177, 8, 0) (255, 82, 0) (4423, 271, 0)
(151, 67, 0) (177, 22, 0) (258, 83, 0) (9689, 84, 0)
(151, 70, 0) (177, 88, 0) (266, 47, 0)


Previous Table of Contents Next

Copyright © John Wiley & Sons, Inc.

HomeAccount InfoSubscribeLoginSearchMy ITKnowledgeFAQSitemapContact Us
Products |  Contact Us |  About Us |  Privacy  |  Ad Info  |  Home

Use of this site is subject to certain Terms & Conditions, Copyright © 1996-2000 EarthWeb Inc. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.