//============================================================================= // drt/sys/slfsr.cpp // Pseudo-random number generating functions, which are implemented using // a linear feedback shift register (LFSR). // // References // "Applied Cryptography", // Section 16.2, "Linear Feedback Shift Registers", // by Bruce Schneier, 2nd ed., 1996, // John Wiley & Sons, ISBN 0-471-11709-9. // The author can be contacted at: . // // History // 0.01, 1998-08-22, David R Tribble. // First cut. // // 0.02, 1998-08-23, David R Tribble. // Added class MyLFSR for testing. // // 0.03, 1998-09-03, David R Tribble. // Added 8-bit at-a-time optimization for LFSR::genrand(). // // 0.04, 1998-09-20, David R Tribble. // Moved 8-bit optimization constants and tables into local class // 'DrtLFSR96'. // // 0.05, 1998-09-25, David R Tribble. // Combined class DrtLFSR with the local class DrtLFSR96 and renamed it to // class DrtLFSR96. // Renamed class DrtLFSRKey to DrtLFSRKey96. // Renamed class MyLFSR to MyLFSR96. // // 1.00, 1999-03-09, David R Tribble. // Moved from drt/scm/ to drt/sys. // // Copyright ©1998-1999, by David R. Tribble, all rights reserved. // See "drt/sys/copyr.txt" for more information. //----------------------------------------------------------------------------- // Identification static const char id[] = "@(#)drt/sys/slfsr.cpp 1.00"; // System includes #include #define drt_std_assert_h 1 #if TEST #include #define drt_std_limits_h 1 #include #define drt_std_stdio_h 1 #include #define drt_std_string_h 1 #include #define drt_std_time_h 1 #endif // Special includes #include "sdefs.hpp" #include "slfsr.hpp" // Local includes #include "sdebug.hpp" // Local wrappers drt_namespace_begin //----------------------------------------------------------------------------- // Shared class constants //----------------------------------------------------------------------------- #if DrtLFSR96_VS/100 != 2 #error Class DrtLFSR96 has changed #endif // Feedback bits: 95,87,86,85,72,75,64 // 1000.0000.1110.0000.0000.1001.0000.0001 /*static*/ const drt_uint32_t DrtLFSR96::MASK2 = 0x80E00901; // Feedback bits: 55,53,47,42,33 // 0000.0101.1010.0000.1000.0100.0000.0010 /*static*/ const drt_uint32_t DrtLFSR96::MASK1 = 0x05A08402; // Feedback bits: 23,20,13,2,3,4,6,7 // 0000.0000.1001.0000.0010.0000.1101.0100 /*static*/ const drt_uint32_t DrtLFSR96::MASK0 = 0x009020D4; //----------------------------------------------------------------------------- // const DrtLFSR96::SMASK[], // const DrtLFSR96::SRESULT[] // Pre-computed bitmask and result tables containing values for shifting // and exclusive-or'ing the LFSR. // // Note // These tables are generated by the program that results when this file // is compiled with the macro 'TEST' set to a nonzero value. // See MyLFSR96::preCompute8() below. //----------------------------------------------------------------------------- #define slfsr_cpp 1 #include "slfsrtab.cpp" //----------------------------------------------------------------------------- // Shared class constants //----------------------------------------------------------------------------- #if DrtLFSR96_VS/100 != 2 #error Class DrtLFSR96 has changed #endif /*static*/ const int DrtLFSR96::VS = DrtLFSR96_VS; // Class version /*static*/ const unsigned int DrtLFSR96::MAGIC = 0xD2D03330; // Class magic number //----------------------------------------------------------------------------- // Shared class variables //----------------------------------------------------------------------------- #if DrtLFSR96_VS/100 != 2 #error Class DrtLFSR96 has changed #endif /*static*/ DrtTraceGroup DrtLFSR96::s_grp("DrtLFSR96", __FILE__, __DATE__, __TIME__); //----------------------------------------------------------------------------- // DrtLFSR96::~DrtLFSR96() // Destructor. //----------------------------------------------------------------------------- /*virtual*/ /*void*/ DrtLFSR96::~DrtLFSR96() { #if DrtLFSR96_VS != 200 #error Class DrtLFSR96 has changed #endif DrtTrace dbg(s_grp, "~DrtLFSR96", this); // Validate this object validate(); // De-initialize members // (None) } //----------------------------------------------------------------------------- // DrtLFSR96::DrtLFSR96() // Default constructor. //----------------------------------------------------------------------------- /*DrtLFSR96*/ DrtLFSR96::DrtLFSR96(): m_magic(MAGIC), m_vers(VS) { #if DrtLFSR96_VS != 200 #error Class DrtLFSR96 has changed #endif DrtTrace dbg(s_grp, "DrtLFSR96", this); // Initialize members m_lfsr[0] = 0x00000000; m_lfsr[1] = 0x00000000; m_lfsr[2] = 0x00000000; } //----------------------------------------------------------------------------- // DrtLFSR96::validate() // Validate this object. // // Notes // Fails an assert() if this object is invalid. //----------------------------------------------------------------------------- void DrtLFSR96::validate() const { #if DrtLFSR96_VS/100 != 2 #error Class DrtLFSR96 has changed #endif //DrtTrace dbg(s_grp, "validate", this); // Validate this object assert(("DrtLFSR96", this != null)); // Check for null assert(DrtLFSR96::m_magic == MAGIC); // Check magic number assert(DrtLFSR96::m_vers/100 == VS/100); // Check version number } //----------------------------------------------------------------------------- // DrtLFSR96::dump() // Dump the contents of this object to the debugging trace output. //----------------------------------------------------------------------------- /*virtual*/ void DrtLFSR96::dump() const { #if DrtLFSR96_VS != 200 #error Class DrtLFSR96 has changed #endif //DrtTrace dbg(s_grp, "dump", this); // Validate this object validate(); // Lock the debug output context DrtTrace::enterContext(); // Dump the contents of this (base) object #if is_incomplete___ ... #else drt_std::printf("DrtLFSR96::dump() is incomplete\n"); #endif // Done DrtTrace::leaveContext(); } //----------------------------------------------------------------------------- // DrtLFSR96::setState() // Initialize the LFSR with the new state vector value in 'st'. //----------------------------------------------------------------------------- void DrtLFSR96::setState(const unsigned char st[96/8]) { #if DrtLFSR96_VS/100 != 2 #error Class DrtLFSR96 has changed #endif // Check args assert((DrtLFSR96::setState, st != null)); if (st == null) return; // Re-initialize the LFSR int i, j; for (i = 0, j = 0; i < 96/32; i++) { drt_uint32_t x = 0x00000000; for (int k = 0; k < 32/8; k++, j++) { x <<= 8; x += st[j]; } m_lfsr[i] = x; } } //----------------------------------------------------------------------------- // DrtLFSR96::setState() // Initialize the LFSR with the new state vector value in 'st'. //----------------------------------------------------------------------------- void DrtLFSR96::setState(const drt_uint32_t st[96/32]) { #if DrtLFSR96_VS/100 != 2 #error Class DrtLFSR96 has changed #endif // Check args assert((DrtLFSR96::setState, st != null)); if (st == null) return; // Re-initialize the LFSR m_lfsr[0] = st[0]; m_lfsr[1] = st[1]; m_lfsr[2] = st[2]; } //----------------------------------------------------------------------------- // DrtLFSR96::getState() // Retrieve the current state vector of the LFSR, placing it into 'st'. //----------------------------------------------------------------------------- void DrtLFSR96::getState(drt_uint32_t st[96/32]) const { #if DrtLFSR96_VS/100 != 2 #error Class DrtLFSR96 has changed #endif // Check args assert((DrtLFSR96::getState, st != null)); if (st == null) return; // Extract the contents of the LFSR st[0] = m_lfsr[0]; st[1] = m_lfsr[1]; st[2] = m_lfsr[2]; } //----------------------------------------------------------------------------- // DrtLFSR96::getState() // Retrieve the current state vector of the LFSR, placing it into 'st'. //----------------------------------------------------------------------------- void DrtLFSR96::getState(unsigned char st[96/8]) const { #if DrtLFSR96_VS/100 != 2 #error Class DrtLFSR96 has changed #endif // Check args assert((DrtLFSR96::getState, st != null)); if (st == null) return; // Extract the contents of the LFSR int i, j; for (i = 0, j = 0; i < 96/32; i++) { drt_uint32_t x; x = m_lfsr[i]; for (int k = 0; k < 32/8; k++, j++) { st[j] = x & 0xFF; x >>= 8; } } } //----------------------------------------------------------------------------- // DrtLFSR96::genrand8() // Generate an 8-bit integer pseudo-random number from the LFSR. // // Returns // An 8-bit pseudo-random binary value. //----------------------------------------------------------------------------- int DrtLFSR96::genrand8() { #if DrtLFSR96_VS/100 != 2 #error Class DrtLFSR96 has changed #endif // Generate an 8-bit value by repeatedly shifting the LFSR return (static_cast(int, genrand(8))); } //----------------------------------------------------------------------------- // DrtLFSR96::genrand16() // Generate a 16-bit integer pseudo-random number from the LFSR. // // Returns // A 16-bit pseudo-random binary value. //----------------------------------------------------------------------------- unsigned int DrtLFSR96::genrand16() { #if DrtLFSR96_VS/100 != 2 #error Class DrtLFSR96 has changed #endif // Generate a 16-bit value by repeatedly shifting the LFSR return (static_cast(unsigned int, genrand(16))); } //----------------------------------------------------------------------------- // DrtLFSR96::genrand32() // Generate a 32-bit integer pseudo-random number from the LFSR. // // Returns // A 32-bit pseudo-random binary value. //----------------------------------------------------------------------------- unsigned long DrtLFSR96::genrand32() { #if DrtLFSR96_VS/100 != 2 #error Class DrtLFSR96 has changed #endif // Generate a 32-bit value by repeatedly shifting the LFSR return (static_cast(unsigned long, genrand(32))); } //----------------------------------------------------------------------------- // DrtLFSR96::genrand() // Generate an n-bit integer pseudo-random number from the LFSR. // Width 'n' can be up to 'sizeof(unsigned long) * UCHAR_BITS' in size. // // Returns // An n-bit pseudo-random binary value. // // Algorithm // The algorithm used is a linear feedback shift register (LFSR) in a // modified Galois configuration. // // Each shifting of the LFSR is done by taking the lowest bit, b, // complementing it, and then exclusive-or'ing it with several bits at // special positions in the LFSR. The whole register is then shifted one // bit to the right, resulting in the next LFSR state. Bit b is one bit // of pseudo-random output. // // To generate an N-bit pseudo-random value, the LFSR is shifted N times, // and the N output bits are concatenated together into a single output // word. // // Pictorially, the shift looks like: // ~b --> axxxxxxp:xxxxxxxy:xxxxxxxb --> ~b --> output bit // ^ ^ ^ | // | | | | // xor xor xor | // | | | v // +-----------+--------+----------+ // // Arithmetically, the exclusive-or'ing looks like (where B = ~b): // axxxxxxp:xxxxxxxy:xxxxxxxb // (+) B B B // ------------------------------ // axxxxxxp:xxxnxxxy:xxxrxxxb // // The intermediate result is then shifted right one bit: // Baxxxxxx:pxxxnxxx:yxxxrxxx // // The next state of the LFSR looks like: // Baxxxxxx:pxxxnxxx:yxxxrxxx // // Notes // Implemented as a 96-bit LFSR in a modified Galois configuration. // By itself, this is probably not very cryptographically secure. //----------------------------------------------------------------------------- unsigned long DrtLFSR96::genrand(int n) { #if DrtLFSR96_VS/100 != 2 #error Class DrtLFSR96 has changed #endif // Generate an n-bit value by repeatedly shifting the LFSR unsigned long t = 0x00000000; // Shift the LFSR 8 bits at a time for ( ; n >= 8; n -= 8) { drt_uint32_t b; // Get the low 8 bits (the byte) 'b' from the LFSR b = m_lfsr[0] & 0x000000FF; // Shift result of byte 'b' into the resulting n-bit value t = (t << 8) | DrtLFSR96::SRESULT[b]; // Shift the LFSR 8 bits { drt_uint32_t c; drt_uint32_t d; c = (m_lfsr[2] & 0x000000FF) << 32-8; m_lfsr[2] = (m_lfsr[2] >> 8); d = (m_lfsr[1] & 0x000000FF) << 32-8; m_lfsr[1] = (m_lfsr[1] >> 8) | c; m_lfsr[0] = (m_lfsr[0] >> 8) | d; } // Feed (exclusive-or) byte 'b' back into the LFSR, using table masks m_lfsr[0] ^= DrtLFSR96::SMASK[b][0]; m_lfsr[1] ^= DrtLFSR96::SMASK[b][1]; m_lfsr[2] ^= DrtLFSR96::SMASK[b][2]; // Adjust the high 8 bits of the LFSR m_lfsr[2] ^= (b << 32-8); } // Shift the LFSR one bit at a time for ( ; n > 0; n--) { // Get the low bit 'b' from the LFSR drt_uint32_t b; b = ~m_lfsr[0] & 0x00000001; // Shift bit 'b' into the resulting n-bit value t = (t << 1) | b; // Feed (exclusive-or) bit 'b' back into the LFSR if (b != 0) { // Feed back bit 'b' into the LFSR by exclusive-or'ing with masks m_lfsr[0] ^= DrtLFSR96::MASK0; m_lfsr[1] ^= DrtLFSR96::MASK1; m_lfsr[2] ^= DrtLFSR96::MASK2; // Set up for the shift b = 0x80000000; } // Shift the LFSR one bit, inserting bit 'b' at the high end drt_uint32_t c; c = (m_lfsr[2] & 0x00000001) ? 0x80000000 : 0x00000000; m_lfsr[2] = (m_lfsr[2] >> 1) | b; b = (m_lfsr[1] & 0x00000001) ? 0x80000000 : 0x00000000; m_lfsr[1] = (m_lfsr[1] >> 1) | c; m_lfsr[0] = (m_lfsr[0] >> 1) | b; } // Return the resulting n-bit value return (static_cast(unsigned long, t)); } drt_namespace_end //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- #if TEST drt_namespace_begin //----------------------------------------------------------------------------- // class MyLFSR96 // Class for testing class 'DrtLFSR96'. // // History // 100, 1998-08-25, David R Tribble. // First cut. // // 200, 1998-08-25, David R Tribble. // Renamed this class to MyLFSR96. //----------------------------------------------------------------------------- #define MyLFSR96_VS 200 // Class version class MyLFSR96: public DrtLFSR96 { public: // Shared functions static void preCompute8(); // Pre-compute shifted bitmasks public: // Functions /*void*/ ~MyLFSR96() {} // Destructor /*MyLFSR96*/ MyLFSR96() {} // Default constructor public: // Operators const MyLFSR96 & operator =(const MyLFSR96 &r); // Assignment operator bool operator ==(const MyLFSR96 &r) const; // Equality operator }; bool MyLFSR96::operator ==(const MyLFSR96 &r) const { return (m_lfsr[0] == r.m_lfsr[0] and m_lfsr[1] == r.m_lfsr[1] and m_lfsr[2] == r.m_lfsr[2]); } const MyLFSR96 & MyLFSR96::operator =(const MyLFSR96 &r) { m_lfsr[0] == r.m_lfsr[0]; m_lfsr[1] == r.m_lfsr[1]; m_lfsr[2] == r.m_lfsr[2]; return (*this); } //----------------------------------------------------------------------------- // MyLFSR96::preCompute8() // Pre-compute the xor bitmasks used by the LFSR, for performing multiple // shifts simultaneously. // // Notes // The output from this should be used as the source file "slfsrtab.cpp". //----------------------------------------------------------------------------- /*static*/ void MyLFSR96::preCompute8() { int i; int bresult[0x100]; // Generate initialized table of LFSR bitmask values printf("//======================================" "=======================================\n"); printf("// slfsrtab.cpp\n"); printf("//\n"); printf("// Generated with bitmask { 0x%08lX, 0x%08lX, 0x%08lX }\n", (unsigned long) DrtLFSR96::MASK0, (unsigned long) DrtLFSR96::MASK1, (unsigned long) DrtLFSR96::MASK2); printf("//--------------------------------------" "---------------------------------------\n\n\n"); printf("#ifndef slfsr_cpp\n"); printf("#error This file cannot be compiled by itself\n"); printf("#endif\n\n"); printf("#if DrtLFSR96_VS/100 != 2\n"); printf("#error DrtLFSR96_VS has changed\n"); printf("#endif\n\n"); printf("\n"); printf("//--------------------------------------" "---------------------------------------\n\n"); printf("/*static*/\n"); printf("const drt_uint32_t\tDrtLFSR96::SMASK[0x100][96/32] =\n"); printf("{\n"); // Shift the LFSR through all possible values of an 8-bit 'b' for (i = 0x00; i < 0x100; i++) { drt_uint32_t lfsr[3]; drt_uint32_t low; int t = 0x00; int r = i; // Initialize the LFSR, setting LSB of the LFSR to byte 'b' lfsr[2] = 0x00000000; lfsr[1] = 0x00000000; lfsr[0] = 0x00000000; low = i; // Shift the LFSR for 8 bits (8 times) for (int j = 0; j < 8; j++) { drt_uint32_t b; // Get the low bit 'b' from the LFSR b = ~low & 0x00000001; // Shift bit 'b' into the resulting n-bit value t = (t << 1) | b; // Feed (exclusive-or) bit 'b' back into the LFSR if (b != 0) { // Feed back bit 'b' into the LFSR by exclusive-or'ing lfsr[0] ^= DrtLFSR96::MASK0; lfsr[1] ^= DrtLFSR96::MASK1; lfsr[2] ^= DrtLFSR96::MASK2; low ^= DrtLFSR96::MASK0; } // Shift/rotate the working bitmask one bit drt_uint32_t c; b = (~lfsr[0] & 0x00000001) ? 0x80000000 : 0x00000000; c = (lfsr[2] & 0x00000001) ? 0x80000000 : 0x00000000; lfsr[2] = (lfsr[2] >> 1) | b; b = (lfsr[1] & 0x00000001) ? 0x80000000 : 0x00000000; lfsr[1] = (lfsr[1] >> 1) | c; lfsr[0] = (lfsr[0] >> 1) | b; low >>= 1; } bresult[i] = t; printf(" { 0x%08lX, 0x%08lX, 0x%08lX },\t// 0x%02X -> 0x%02X\n", (unsigned long) lfsr[0], (unsigned long) lfsr[1], (unsigned long) lfsr[2], i, t); } printf("};\n\n\n"); // Generate initialized table of mask values printf("//--------------------------------------" "---------------------------------------\n\n"); printf("/*static*/\n"); printf("const unsigned char\tDrtLFSR96::SRESULT[0x100] =\n"); printf("{\n"); for (i = 0x00; i < 0x100; i++) { if (i%8 == 0) printf(" "); printf(" 0x%02X,", bresult[i]); if (i%0x10 == 7) printf("\t// 0x%02X-0x%02X", i-7, i-7+0xF); if (i%8 == 8-1) printf("\n"); } printf("};\n\n\n"); printf("// End slfsrtab.cpp\n"); } //----------------------------------------------------------------------------- // Class Program // This class embodies the execution of this entire program. // // History // 100, 1998-09-20, David R Tribble. // First cut. //----------------------------------------------------------------------------- #define Program_VS 100 // Class version class /*DRTDECL*/ Program { public: // Shared functions static int main(int argc, const char *const *argv); // Execute this program private: // Functions // Constructors and destructors not provided /*void*/ ~Program(); // Destructor /*Program*/ Program(); // Default constructor /*Program*/ Program(const Program &r); // Copy constructor const Program & operator =(const Program &r); // Assignment operator }; //----------------------------------------------------------------------------- // Program::main() // Test driver. // // Usage // slfsr [-option]... [+size] [times] // slfsr -g >slfsrtab.cpp // // Options: // -d Show duplicate numbers. // -g Print pre-computed "slfsrtab.cpp" table (only). // -h Print a histograph. // -n Don't print the numeric values. // -r Display contents (state) of the LFSR after each number. // +size Word size (in bits), default is 32. // times Number of numeric values to print (default is 200). //----------------------------------------------------------------------------- /*static*/ int Program::main(int argc, const char *const *argv) { bool doPrint = true; bool doHist = false; bool doState = false; bool doDup = false; int size = 32; unsigned long times = 200; unsigned long dups = 0; // Check option args while (argc > 0+1 and argv[1][0] == '-') { if (strcmp(argv[1], "-g") == 0) { MyLFSR96::preCompute8(); return (0); } else if (strcmp(argv[1], "-d") == 0) doDup = true; else if (strcmp(argv[1], "-h") == 0) doHist = true; else if (strcmp(argv[1], "-n") == 0) doPrint = false; else if (strcmp(argv[1], "-r") == 0) doState = true; else { fprintf(stderr, "Unknown option '%s'\n", argv[1]); return (127); } argc--, argv++; } // Check other option args if (argc > 0+1 and argv[1][0] == '+') { sscanf(argv[1], "%d", &size); argc--, argv++; } // Check args if (argc > 0+1) { sscanf(argv[1], "%lu", ×); if (times <= 0) times = UINT_MAX; argc--, argv++; } // Instantiate an LFSR object printf("Create an LFSR object...\n"); MyLFSR96 r; MyLFSR96 r1; // Initialize the LFSR unsigned long s; // Generate some random numbers using the LFSR object unsigned long first = 0x00000000; unsigned long ldup = 1; static unsigned long counts[0x100]; printf("Create %lu random numbers of %d bits...\n\n", times, size); if (not doPrint) printf("(Each dot indicates 10,000 numbers)\n"); for (unsigned long j = 1; j <= times and j != 0; j++) { unsigned long x; if (doPrint and doState) { unsigned char st[96/8]; r.getState(st); printf("[%02X]", st[0]); } // Generate a pseudo-random number from the LFSR x = r.genrand(size); counts[x & 0x00FF]++; if (doPrint) { if (size > 24) { printf(" %08lX", x); if (j%8 == 0) printf("\n"); } else if (size > 16) { printf(" %06lX", x); if (j%10 == 0) printf("\n"); } else if (size > 8) { printf(" %04lX", x); if (j%15 == 0) printf("\n"); } else { printf(" %02lX", x); if (j%25 == 0) printf("\n"); } } else if (j%10000 == 0) { printf("."); if (j%500000 == 0) { printf(" %luk\n", j/1000); fflush(stdout); } } if (j%10000000 == 0 or doState) { unsigned char st[96/8]; if (j%500000 != 0) printf(" "); r.getState(st); printf("@%06lu " "%02X%02X%02X%02X:%02X%02X%02X%02X:%02X%02X%02X%02X\n", j, st[11], st[10], st[9], st[8], st[7], st[6], st[5], st[4], st[3], st[2], st[1], st[0]); fflush(stdout); } if (doDup) { if (first == 0x00000000) { first = x; ldup = j; r1 = r; } else { if (x == first) { printf("\ndup at %lu (+%lu)\n", j, j-ldup); for (int k = j%500000/10000; k > 0; k--) printf(" "); ldup = j; dups++; } if (r == r1) { printf("\ndup state at %lu (+%lu)\n", j, j-ldup); for (int k = j%500000/10000; k > 0; k--) printf(" "); ldup = j; } } } } printf("\n"); // Print histogram if (doHist) { unsigned long lo = UINT_MAX; unsigned long hi = 0; printf("Histogram:\n"); for (int i = 0x00; i < 0x100/4; i++) { for (int j = 0; i+j < 0x100; j += 0x100/4) { printf(" %02X:%-10lu ", i+j, counts[i+j]); if (lo > counts[i+j]) lo = counts[i+j]; if (hi < counts[i+j]) hi = counts[i+j]; } printf("\n"); } printf("Range: [%lu, %lu]\n", lo, hi); } // Print duplicate dummary if (doDup) { printf("Duplicates: %lu\n", dups); } return (0); } drt_namespace_end //----------------------------------------------------------------------------- // ::main() // Test driver. //----------------------------------------------------------------------------- int main(int argc, char **argv) { return (drt_namespace::Program:: main(argc, const_cast(const char *const *, argv))); } #endif // TEST // End slfsr.cpp