Linear Feedback Shift Registers

LM - 2006/02/08

Linear Feedback Shift Registers - LFSR - are used as pseudo-random number generators for Cryptography and Spread Spectrum Radio applications. See [1] or Bruce Schneier, BOOK: Applied Cryptography for more information.

Testing LFSR, we need information on runs length: i.e. the number of consecutive Ones or Zeroes occurring in a sequence of generated stream of bytes. This is my solution to the problem.

 #
 # runs_len 
 # calculates the runs lengths given a list of bytes.
 # It returns a list of runs-lengths
 #_____________________________________________________________________ 
 proc runs_len {bytelist} {
          # Change Bytes_list into hexadecimal_string 
         foreach b $bytelist {
                 append bstr [format "%02X" [expr {$b & 0xff}]]
         }
         # Change into Binary_string
         binary scan [binary format H* $bstr] B* bits
 
         # Runs extraction
         set runlist [split [regsub -all {(0+|1+)} $bits "&-"] -]
         set runlist [lreplace $runlist end end]
        
        # Runs-length list creation 
         foreach r $runlist {
                 lappend lenlist [string length $r]
         }
         return $lenlist
 }

 #____________________________________________________________________
 # A simple tester
 set bytelist { 0xa6 0xb0 0x35 0xf2 0x18 0xc4}
 puts [runs_len $bytelist]

Category Cryptography