|
Lfsrs And Prng
|
|
Topic Started: May 13 2006, 02:54 PM (217 Views)
|
|
loki
|
May 13 2006, 02:54 PM
Post #1
|
- Posts:
- 87
- Group:
- Members
- Member
- #48
- Joined:
- April 28, 2006
|
- Code:
-
/* modified LFSR and Simplied MERSENNE TWISTER GENERATOR
Developed by LOKI for submission to The Crypto Forum
LFSRs have long been used as a pseudo-random number
generator for use in stream ciphers (especially in military
cryptography), due to the ease of construction from simple
electromechanical or electronic circuits, long periods, and
very uniformly distributed outputs. However the outputs of
LFSRs are completely linear, leading to fairly easy cryptanalysis.
The Mersenne twister is a pseudorandom number generator developed
in 1997 by Makoto Matsumoto and Takuji Nishimura. It provides for
fast generation of very high quality pseudorandom numbers, having
been designed specifically to rectify many of the flaws found in
older algorithms.
*/
#include <stdio.h>
#define mask_lfsr 0x80000057UL
static unsigned long ShiftRegister=0;
void seed_LFSR(unsigned long seed) {
if (seed == 0) /* avoid calamity */
seed = 1;
ShiftRegister = seed;
}
int LFSR(void) {
int i;
unsigned long a[624];
a[0]=19937;
for(i=1;i<227;i++) {
a[i] ^= ((ShiftRegister >> 1) ^ 0x9908B0DFUL);
a[i] ^= a[i-1];
ShiftRegister ^= (a[i] ^ mask_lfsr);
}
for(i=227;i<435;i++) {
a[i] ^= ((ShiftRegister >> 1) ^ 0x99B47ECEUL);
a[i] ^= a[i-1];
a[i] ^= (a[i] ^ a[i-227]);
ShiftRegister ^= (a[i] ^ mask_lfsr);
}
for(i=435;i<624;i++) {
a[i] ^= ((ShiftRegister >> 1) ^ 0x99B47ECEUL);
a[i] ^= a[i-1];
a[i] ^= (a[i] ^ a[i-435]);
ShiftRegister ^= (a[i] ^ mask_lfsr);
}
ShiftRegister ^= ((((ShiftRegister >> 7)
^ (ShiftRegister << 5)
^ (ShiftRegister >> 3)
^ (ShiftRegister << 2)
^ (ShiftRegister >> 1)
^ ShiftRegister )
& 1 ) << 31 )
| ( ShiftRegister << 1 );
ShiftRegister &= 0x00000001;
return ShiftRegister;
}
int main(void) {
int i;
printf("LFSR : Using no seed\n");
for(i=0;i<32;i++) {
LFSR();
printf("%u", ShiftRegister);
}
printf("\n\nLFSR : Using seed %u\n", 1);
seed_LFSR(1);
for(i=0;i<32;i++) {
LFSR();
printf("%u", ShiftRegister);
}
printf("\n\nLFSR : Using seed %u\n", 2);
seed_LFSR(2);
for(i=0;i<32;i++) {
LFSR();
printf("%u", ShiftRegister);
}
printf("\n\nLFSR : Using seed %u\n", 3);
seed_LFSR(4);
for(i=0;i<32;i++) {
LFSR();
printf("%u", ShiftRegister);
}
printf("\n\nLFSR : Using seed %u\n", mask_lfsr);
seed_LFSR(0x80000057);
for(i=0;i<32;i++) {
LFSR();
printf("%u", ShiftRegister);
}
printf("\n\nprinting 512 bits using seed %u\n", 0x9908B0DF);
seed_LFSR(0x9908B0DF);
for(i=0;i<512;i++) {
LFSR();
printf("%u", ShiftRegister);
}
return 0;
}
|
|
c(x) = 3x3 + x2 + x + 2; Find the inverse
|
| |
|
loki
|
May 27 2006, 04:11 AM
Post #2
|
- Posts:
- 87
- Group:
- Members
- Member
- #48
- Joined:
- April 28, 2006
|
I didn't notice a few errors in the above submission. Here is my latest implementation. Since its 1 30 am right now I am not in the mood to start converting the defines and varibles into arrays and use just one lfsr. So please forgive the overloaded code at the moment, until I do it.
Version 2:
linear congruential generator based on 8 linear feedback shift registers.
- Code:
-
#include <stdio.h>
#include <math.h>
#define MODMULT(a,b,c,m,s) q = a/s; s = b*(s-a*q) - c*q; if (s<0) s+=m;
#define mask_lfsr0 0x80000057UL
#define mask_lfsr1 0x8E7F8157UL
#define mask_lfsr2 0x8F819257UL
#define mask_lfsr3 0x8192A357UL
#define mask_lfsr4 0x82A3B457UL
#define mask_lfsr5 0x83B4C557UL
#define mask_lfsr6 0x84C5D657UL
#define mask_lfsr7 0x85D6E757UL
unsigned long ShiftRegister0 = 0;
unsigned long ShiftRegister1 = 0;
unsigned long ShiftRegister2 = 0;
unsigned long ShiftRegister3 = 0;
unsigned long ShiftRegister4 = 0;
unsigned long ShiftRegister5 = 0;
unsigned long ShiftRegister6 = 0;
unsigned long ShiftRegister7 = 0;
unsigned long x[7];
unsigned long clcg(void);
void init_lcg(unsigned long initX0, unsigned long initX1,
unsigned long initX2, unsigned long initX3,
unsigned long initX4, unsigned long initX5,
unsigned long initX6, unsigned long initX7);
void seed_lfsr(unsigned long seed);
unsigned long LFSR0(void); unsigned long LFSR1(void);
unsigned long LFSR2(void); unsigned long LFSR3(void);
unsigned long LFSR4(void); unsigned long LFSR5(void);
unsigned long LFSR6(void); unsigned long LFSR7(void);
int main(void) {
int i;
unsigned long lcg;
seed_lfsr(19);
init_lcg(LFSR0(), LFSR1(), LFSR2(), LFSR3(), LFSR4(), LFSR5(), LFSR6(), LFSR7());
for(i=0;i<10;i++) {
printf("%u\n", clcg());
}
return 0;
}
unsigned long clcg(void) {
unsigned long q;
unsigned long z;
MODMULT(50021, 40009, 16001, 2147483999UL, x[0])
MODMULT(50033, 40039, 16061, 2147483929UL, x[1])
MODMULT(50051, 40099, 16073, 2147483869UL, x[2])
MODMULT(50069, 40129, 16103, 2147483813UL, x[3])
MODMULT(50087, 40169, 16141, 2147483783UL, x[4])
MODMULT(50101, 40213, 16193, 2147483777UL, x[5])
MODMULT(50119, 40253, 16231, 2147483659UL, x[6])
MODMULT(50129, 40343, 16747, 2147483629UL, x[7])
z = (x[0] - x[1]) + (x[2] - x[3]) + (x[4] - x[5]) + (x[6] - x[7]);
if ( z < 1 )
z += 2147483562;
return z * 5;
}
void init_lcg(unsigned long initX0, unsigned long initX1,
unsigned long initX2, unsigned long initX3,
unsigned long initX4, unsigned long initX5,
unsigned long initX6, unsigned long initX7) {
x[0] = initX0;
x[1] = initX1;
x[2] = initX2;
x[3] = initX3;
x[4] = initX4;
x[5] = initX5;
x[6] = initX6;
x[7] = initX7;
}
void seed_lfsr(unsigned long seed) {
if (seed == 0) /* avoid calamity */
seed = 1;
ShiftRegister0 = seed + mask_lfsr0;
ShiftRegister1 = seed + mask_lfsr1;
ShiftRegister2 = seed + mask_lfsr2;
ShiftRegister3 = seed + mask_lfsr3;
ShiftRegister4 = seed + mask_lfsr4;
ShiftRegister5 = seed + mask_lfsr5;
ShiftRegister6 = seed + mask_lfsr6;
ShiftRegister7 = seed + mask_lfsr7;
}
unsigned long LFSR0(void) {
int i;
unsigned long a[624];
a[0]=19937;
for(i=1;i<227;i++) {
a[i] ^= ((ShiftRegister0 >> 1) ^ 0x9908B0DFUL);
a[i] ^= a[i-1];
ShiftRegister0 ^= (a[i] ^ mask_lfsr0);
}
for(i=227;i<435;i++) {
a[i] ^= ((ShiftRegister0 >> 1) ^ 0x99B47ECEUL);
a[i] ^= a[i-1];
a[i] ^= (a[i] ^ a[i-227]);
ShiftRegister0 ^= (a[i] ^ mask_lfsr0);
}
for(i=435;i<624;i++) {
a[i] ^= ((ShiftRegister1 >> 1) ^ 0x99B47ECEUL);
a[i] ^= a[i-1];
a[i] ^= (a[i] ^ a[i-435]);
ShiftRegister0 ^= (a[i] ^ mask_lfsr0);
}
ShiftRegister0 ^= ((((ShiftRegister0 >> 7)
^ (ShiftRegister0 << 5)
^ (ShiftRegister0 >> 3)
^ (ShiftRegister0 << 2)
^ (ShiftRegister0 >> 1)
^ ShiftRegister0 )
& 1 ) << 31 )
| ( ShiftRegister0 << 1 );
ShiftRegister0 &= 0x000000FFUL;
return ShiftRegister0;
}
unsigned long LFSR1(void) {
int i;
unsigned long a[624];
a[0]=39877;
for(i=1;i<227;i++) {
a[i] ^= ((ShiftRegister1 >> 1) ^ 0x9908B0DFUL);
a[i] ^= a[i-1];
ShiftRegister1 ^= (a[i] ^ mask_lfsr1);
}
for(i=227;i<435;i++) {
a[i] ^= ((ShiftRegister1 >> 1) ^ 0x99B47ECEUL);
a[i] ^= a[i-1];
a[i] ^= (a[i] ^ a[i-227]);
ShiftRegister1 ^= (a[i] ^ mask_lfsr1);
}
for(i=435;i<624;i++) {
a[i] ^= ((ShiftRegister1 >> 1) ^ 0x99B47ECEUL);
a[i] ^= a[i-1];
a[i] ^= (a[i] ^ a[i-435]);
ShiftRegister1 ^= (a[i] ^ mask_lfsr1);
}
ShiftRegister1 ^= ((((ShiftRegister1 >> 7)
^ (ShiftRegister1 << 5)
^ (ShiftRegister1 >> 3)
^ (ShiftRegister1 << 2)
^ (ShiftRegister1 >> 1)
^ ShiftRegister1 )
& 1 ) << 31 )
| ( ShiftRegister1 << 1 );
ShiftRegister1 &= 0x000000FFUL;
return ShiftRegister1;
}
unsigned long LFSR2(void) {
int i;
unsigned long a[624];
a[0]=13291;
for(i=1;i<227;i++) {
a[i] ^= ((ShiftRegister2 >> 1) ^ 0x9908B0DFUL);
a[i] ^= a[i-1];
ShiftRegister2 ^= (a[i] ^ mask_lfsr2);
}
for(i=227;i<435;i++) {
a[i] ^= ((ShiftRegister2 >> 1) ^ 0x99B47ECEUL);
a[i] ^= a[i-1];
a[i] ^= (a[i] ^ a[i-227]);
ShiftRegister2 ^= (a[i] ^ mask_lfsr2);
}
for(i=435;i<624;i++) {
a[i] ^= ((ShiftRegister2 >> 1) ^ 0x99B47ECEUL);
a[i] ^= a[i-1];
a[i] ^= (a[i] ^ a[i-435]);
ShiftRegister2 ^= (a[i] ^ mask_lfsr2);
}
ShiftRegister2 ^= ((((ShiftRegister2 >> 7)
^ (ShiftRegister2 << 5)
^ (ShiftRegister2 >> 3)
^ (ShiftRegister2 << 2)
^ (ShiftRegister2 >> 1)
^ ShiftRegister2 )
& 1 ) << 31 )
| ( ShiftRegister2 << 1 );
ShiftRegister2 &= 0x000000FFUL;
return ShiftRegister2;
}
unsigned long LFSR3(void) {
int i;
unsigned long a[624];
a[0]=26591;
for(i=1;i<227;i++) {
a[i] ^= ((ShiftRegister3 >> 1) ^ 0x9908B0DFUL);
a[i] ^= a[i-1];
ShiftRegister3 ^= (a[i] ^ mask_lfsr3);
}
for(i=227;i<435;i++) {
a[i] ^= ((ShiftRegister3 >> 1) ^ 0x99B47ECEUL);
a[i] ^= a[i-1];
a[i] ^= (a[i] ^ a[i-227]);
ShiftRegister3 ^= (a[i] ^ mask_lfsr3);
}
for(i=435;i<624;i++) {
a[i] ^= ((ShiftRegister3 >> 1) ^ 0x99B47ECEUL);
a[i] ^= a[i-1];
a[i] ^= (a[i] ^ a[i-435]);
ShiftRegister3 ^= (a[i] ^ mask_lfsr3);
}
ShiftRegister3 ^= ((((ShiftRegister3 >> 7)
^ (ShiftRegister3 << 5)
^ (ShiftRegister3 >> 3)
^ (ShiftRegister3 << 2)
^ (ShiftRegister3 >> 1)
^ ShiftRegister3 )
& 1 ) << 31 )
| ( ShiftRegister3 << 1 );
ShiftRegister3 &= 0x000000FFUL;
return ShiftRegister3;
}
unsigned long LFSR4(void) {
int i;
unsigned long a[624];
a[0]=8861;
for(i=1;i<227;i++) {
a[i] ^= ((ShiftRegister4 >> 1) ^ 0x9908B0DFUL);
a[i] ^= a[i-1];
ShiftRegister4 ^= (a[i] ^ mask_lfsr4);
}
for(i=227;i<435;i++) {
a[i] ^= ((ShiftRegister4 >> 1) ^ 0x99B47ECEUL);
a[i] ^= a[i-1];
a[i] ^= (a[i] ^ a[i-227]);
ShiftRegister4 ^= (a[i] ^ mask_lfsr4);
}
for(i=435;i<624;i++) {
a[i] ^= ((ShiftRegister4 >> 1) ^ 0x99B47ECEUL);
a[i] ^= a[i-1];
a[i] ^= (a[i] ^ a[i-435]);
ShiftRegister4 ^= (a[i] ^ mask_lfsr4);
}
ShiftRegister4 ^= ((((ShiftRegister4 >> 7)
^ (ShiftRegister4 << 5)
^ (ShiftRegister4 >> 3)
^ (ShiftRegister4 << 2)
^ (ShiftRegister4 >> 1)
^ ShiftRegister4 )
& 1 ) << 31 )
| ( ShiftRegister4 << 1 );
ShiftRegister4 &= 0x000000FFUL;
return ShiftRegister4;
}
unsigned long LFSR5(void) {
int i;
unsigned long a[624];
a[0]=62039;
for(i=1;i<227;i++) {
a[i] ^= ((ShiftRegister5 >> 1) ^ 0x9908B0DFUL);
a[i] ^= a[i-1];
ShiftRegister5 ^= (a[i] ^ mask_lfsr5);
}
for(i=227;i<435;i++) {
a[i] ^= ((ShiftRegister5 >> 1) ^ 0x99B47ECEUL);
a[i] ^= a[i-1];
a[i] ^= (a[i] ^ a[i-227]);
ShiftRegister5 ^= (a[i] ^ mask_lfsr5);
}
for(i=435;i<624;i++) {
a[i] ^= ((ShiftRegister5 >> 1) ^ 0x99B47ECEUL);
a[i] ^= a[i-1];
a[i] ^= (a[i] ^ a[i-435]);
ShiftRegister5 ^= (a[i] ^ mask_lfsr5);
}
ShiftRegister5 ^= ((((ShiftRegister5 >> 7)
^ (ShiftRegister5 << 5)
^ (ShiftRegister5 >> 3)
^ (ShiftRegister5 << 2)
^ (ShiftRegister5 >> 1)
^ ShiftRegister5 )
& 1 ) << 31 )
| ( ShiftRegister5 << 1 );
ShiftRegister5 &= 0x000000FFUL;
return ShiftRegister5;
}
unsigned long LFSR6(void) {
int i;
unsigned long a[624];
a[0]=17;
for(i=1;i<227;i++) {
a[i] ^= ((ShiftRegister6 >> 1) ^ 0x9908B0DFUL);
a[i] ^= a[i-1];
ShiftRegister6 ^= (a[i] ^ mask_lfsr6);
}
for(i=227;i<435;i++) {
a[i] ^= ((ShiftRegister6 >> 1) ^ 0x99B47ECEUL);
a[i] ^= a[i-1];
a[i] ^= (a[i] ^ a[i-227]);
ShiftRegister6 ^= (a[i] ^ mask_lfsr6);
}
for(i=435;i<624;i++) {
a[i] ^= ((ShiftRegister6 >> 1) ^ 0x99B47ECEUL);
a[i] ^= a[i-1];
a[i] ^= (a[i] ^ a[i-435]);
ShiftRegister6 ^= (a[i] ^ mask_lfsr6);
}
ShiftRegister6 ^= ((((ShiftRegister6 >> 7)
^ (ShiftRegister6 << 5)
^ (ShiftRegister6 >> 3)
^ (ShiftRegister6 << 2)
^ (ShiftRegister6 >> 1)
^ ShiftRegister6 )
& 1 ) << 31 )
| ( ShiftRegister6 << 1 );
ShiftRegister6 &= 0x000000FFUL;
return ShiftRegister6;
}
unsigned long LFSR7(void) {
int i;
unsigned long a[624];
a[0]=41381;
for(i=1;i<227;i++) {
a[i] ^= ((ShiftRegister7 >> 1) ^ 0x9908B0DFUL);
a[i] ^= a[i-1];
ShiftRegister7 ^= (a[i] ^ mask_lfsr7);
}
for(i=227;i<435;i++) {
a[i] ^= ((ShiftRegister7 >> 1) ^ 0x99B47ECEUL);
a[i] ^= a[i-1];
a[i] ^= (a[i] ^ a[i-227]);
ShiftRegister7 ^= (a[i] ^ mask_lfsr7);
}
for(i=435;i<624;i++) {
a[i] ^= ((ShiftRegister7 >> 1) ^ 0x99B47ECEUL);
a[i] ^= a[i-1];
a[i] ^= (a[i] ^ a[i-435]);
ShiftRegister7 ^= (a[i] ^ mask_lfsr7);
}
ShiftRegister7 ^= ((((ShiftRegister7 >> 7)
^ (ShiftRegister7 << 5)
^ (ShiftRegister7 >> 3)
^ (ShiftRegister7 << 2)
^ (ShiftRegister7 >> 1)
^ ShiftRegister7 )
& 1 ) << 31 )
| ( ShiftRegister7 << 1 );
ShiftRegister7 &= 0x000000FFUL;
return ShiftRegister7;
}
|
|
c(x) = 3x3 + x2 + x + 2; Find the inverse
|
| |
|
loki
|
May 27 2006, 02:09 PM
Post #3
|
- Posts:
- 87
- Group:
- Members
- Member
- #48
- Joined:
- April 28, 2006
|
Version 2a: Reduced Version.
- Code:
-
#include <stdio.h>
#define MODMULT(a,b,c,m,s) q = a/s; s = b*(s-a*q) - c*q; if (s<0) s+=m;
unsigned long mask_lfsr[8] = {0x80000057UL,
0x8E7F8157UL,
0x8F819257UL,
0x8192A357UL,
0x82A3B457UL,
0x83B4C557UL,
0x84C5D657UL,
0x85D6E757UL};
unsigned long a_vector[8] = {0x4DE1UL,
0x9BC5UL,
0x33EBUL,
0x67DFUL,
0x229DUL,
0xF257UL,
0x11UL,
0xA1A5UL};
unsigned long shiftregister[8];
unsigned long x[8];
/* function prototypes */
unsigned long clcg(void);
void init_lcg(unsigned long initX0, unsigned long initX1,
unsigned long initX2, unsigned long initX3,
unsigned long initX4, unsigned long initX5,
unsigned long initX6, unsigned long initX7);
void seed_lfsr(unsigned long seed);
unsigned long lfsr(int n);
int main(void) {
int i;
unsigned long lcg;
seed_lfsr(19);
init_lcg(lfsr(0),lfsr(1),lfsr(2),lfsr(3),lfsr(4),lfsr(5),lfsr(6),lfsr(7));
for(i=0;i<10;i++) {
printf("%u\n", clcg());
}
return 0;
}
unsigned long clcg(void) {
unsigned long q;
unsigned long z;
MODMULT(50021, 40009, 16001, 2147483999UL, x[0])
MODMULT(50033, 40039, 16061, 2147483929UL, x[1])
MODMULT(50051, 40099, 16073, 2147483869UL, x[2])
MODMULT(50069, 40129, 16103, 2147483813UL, x[3])
MODMULT(50087, 40169, 16141, 2147483783UL, x[4])
MODMULT(50101, 40213, 16193, 2147483777UL, x[5])
MODMULT(50119, 40253, 16231, 2147483659UL, x[6])
MODMULT(50129, 40343, 16747, 2147483629UL, x[7])
z = (x[0] - x[1]) + (x[2] - x[3]) + (x[4] - x[5]) + (x[6] - x[7]);
if ( z < 1 )
z += 2147483562;
return z * 5;
}
void init_lcg(unsigned long initX0, unsigned long initX1,
unsigned long initX2, unsigned long initX3,
unsigned long initX4, unsigned long initX5,
unsigned long initX6, unsigned long initX7) {
x[0] = initX0;
x[1] = initX1;
x[2] = initX2;
x[3] = initX3;
x[4] = initX4;
x[5] = initX5;
x[6] = initX6;
x[7] = initX7;
}
void seed_lfsr(unsigned long seed) {
int i;
if (seed == 0) /* avoid calamity */
seed = 1;
for(i=0;i<8;i++)
shiftregister[i] = seed + mask_lfsr[i];
}
unsigned long lfsr(int n) {
int i;
unsigned long a[624];
a[0]=a_vector[n];
for(i=1;i<227;i++) {
a[i] ^= ((shiftregister[n] >> 1) ^ 0x9908B0DFUL);
a[i] ^= a[i-1];
shiftregister[n] ^= (a[i] ^ mask_lfsr[n]);
}
for(i=227;i<435;i++) {
a[i] ^= ((shiftregister[n] >> 1) ^ 0x99B47ECEUL);
a[i] ^= a[i-1];
a[i] ^= (a[i] ^ a[i-227]);
shiftregister[n] ^= (a[i] ^ mask_lfsr[n]);
}
for(i=435;i<624;i++) {
a[i] ^= ((shiftregister[n] >> 1) ^ 0x99B47ECEUL);
a[i] ^= a[i-1];
a[i] ^= (a[i] ^ a[i-435]);
shiftregister[n] ^= (a[i] ^ mask_lfsr[n]);
}
shiftregister[n] ^= ((((shiftregister[n] >> 7)
^ (shiftregister[n] << 5)
^ (shiftregister[n] >> 3)
^ (shiftregister[n] << 2)
^ (shiftregister[n] >> 1)
^ shiftregister[n] )
& 1 ) << 31 )
| ( shiftregister[n] << 1 );
shiftregister[n] &= 0x000000FFUL;
return shiftregister[n];
}
|
|
c(x) = 3x3 + x2 + x + 2; Find the inverse
|
| |
| 1 user reading this topic (1 Guest and 0 Anonymous)
|
![]](http://209.85.122.85/static/1/pip_r.png)
11:26 PM Mar 21
