LFSR (linear rückgekoppeltes Schieberegister)
Ein Schieberegister, dessen neues Bit eine lineare Funktion einiger alter Bits ist: billig in Hardware und genau deshalb allein als Chiffre gefährlich.
Ein LFSR besteht aus einer Bitreihe und einer Rückkopplungsfunktion. Bei jedem Takt rückt das Register um eine Stelle, und das neue Bit ist das XOR ausgewählter Abgriffe. Mit einem geeigneten Polynom ist die Periode maximal, 2^L − 1. Das macht es in Hardware leicht baubar und zu einer bequemen Schlüsselstromquelle. A5/1 im GSM kombinierte drei davon.
Die Linearität ist zugleich die Schwäche. Der Berlekamp-Massey-Algorithmus (1968–69) rekonstruiert ein LFSR der Länge L aus nur 2L Ausgabebits. Moderne Entwürfe setzen LFSRs deshalb nur zusammen mit nichtlinearen Schritten ein, nie allein.