lfsr.h

AVR单片机控制nokia3510i nokia6100液晶显示屏的库文件及例程

/*
 Copyright:      Hagen Reddmann  mailto HaReddmann at T-Online dot de
 Author:         Hagen Reddmann
 Remarks:        this Copyright must be included
 known Problems: none
 Version:        1997-2004, first implemented on Delphi 5
 Description:    Shrinking Generator - Linear Feedback Shift Register
                 secure PRNG, Pseudo Random Number Generator
                 very good statistical properties

                 Encryption algorithm designed by D. Coppersmith, H. Krawczyk, and
                 Y. Mansour ("The Shrinking Generator", Advances in Cryptology -
                 CRYPTO '93 Proceedings, Springer-Verlag, 1994).

                 Two LFSR A and S; A's output is filtered by S's output.
                 The two LFSR's are run in parallel, and a bit from A is let through
                 only when the bit from S is 1.

                 This implementation use 31-bit A and 32-bit S,
                 requiring primitive polynomials in GF(2) in A of degree 31 and in S of degree 32.

                 This implementation is fully compatible to the MCU BasicCard from www.zeitcontrol.de

               security considerations:
                 The LFSR-SG here isn't secure if the polynomials are known.
                 See "Improved Cryptoanalysis of the Self-Shrinking Generator"
                     Erik Zenner, Matthias Krause, Stefan Lucks
                     Theoretische Informatik, University of Mannheim (Germany)
                 A Self-Shrinking Generator from W. Meier and O. Staffelbach
                 is similar to a Shrinking Generator with the exception of the
                 use of only one LFSR instead two. They security considerations
                 are that a SG-LFSR with registerlengths L = A + S is same secure
                 as a 2L Self-Shrinking generator. In above paper is it assumed 
                 that a Self-Shrinking-generator with registerlength of > 120 bit is secure.
                 Thus, 31+32 = 63Bit for this implementation are equal to a 126 bit Self-
                 Shrinking Generator, and a 63 Bit LFSR-SG such as in this source ist considered
                 as secure, but....
                 In this implementation we use 31 + 32 = 63 Bit and this is definitely
                 to short for strong cryptography but far better as other PRNG's used on AVR.
                 Why? a brute force attack on a 63 Bit polynomial is today fully possible.
                 In the ZeitControls BasicCard, a MCU SmartCard, the weakest
                 cipher used is this LSFR-SG here. The Polynomials are stored
                 in the SmartCard AND the external communication Software.
                 So we must assume the Polynomials are KNOWN and can be easily
                 examined by reverse engineering.

  AVR Version:   WinAVR C, as assembler
                 176 bytes .text
                   8 bytes .data
                 faster, stronger and more compact as inbuilt gcc-lib rand()
                 maximal period 2**63-1
                 plain assembler with free usage of register file should be reduce down to 72 bytes .text

  Customizing:   open lfsr.inc choose from the table a Polymon_S and Polynom_A value and recompile.

*/

#include <inttypes.h>

uint32_t lfsr_S = 1;  // lfsr-sg register, MUST be alays != 0
uint32_t lfsr_A = 1;

// setup lfsr-sg registers and ensure register S,A always != 0
#define lfsr_setup(S, A) {lfsr_S = S | 1; lfsr_A = A | 1;}

// generate pseudo random bits, only last maximal 32 bits returned, but the LFSR can be forward seeked upto 256 bits
// ATTENTION, calling lfsr(0) seeks 256 bits forward instead 0 bits.
extern uint32_t lfsr(uint8_t bitcount);