Powered by ViewCVS 1.0-dev
* imported original ECRYPT submissions after first automatic cleanup.
/* Frogbit demonstration and challenge program
Copyright (C) 1996 CONNOTECH Experts-Conseils Inc.
Author: Thierry Moreau
CONNOTECH Experts-Conseils Inc.
9130 Place de Montgolfier
Montreal, Qc
Canada
H2M 2A1
Date: April 17, 1996, revised April 2005
Revision History:
Bug fix in LFSR generator(!).
Idiosyncracies of 16-bit C.
Fixed a name clash with a BSD definition in string.h
Removed huffman coding for packing the final state in the verbose mode
Reverted to binary ciphertext file; default binary cleartext file;
command-line options starting with - instead of +
Added the -o[1-7] option to omit from 1 to 7 bits from the end of the file,
for enhanced flexibility in the standard challenge
Enhanced source code readability with the last source code change
Fixed a bug in state input rule enforcement
Implemented 20 LFSRs from pi hexadecimal notation instead of 10 simpler
LFSRs for the 10 frogbit PRNGs
Changed from most significant bit first to least significant bit first
Minor source code readability enhancements
Purposes: 1) to foster cryptanalysis attempts against the Frogbit
hash function,
2) to foster cryptanalysis attempts against the Frogbit
encryption, granted a 25-years old attack on the
underlying stream cipher.
Comment: This program provides a simple file encryption
capability, but the (claimed) distinctive advantage of
the Frogbit algorithm is DATA INTEGRITY protection. As
a consequence, the "challenge" aspect of this program
relates to finding collision in a hash function.
Prerequisite: This is cryptographic stuff. The intended reader is
familiar with the subject area.
Practical limitations: No attempt has been made to make the
encryption capability convenient and/or portable.
Little validation is applied to the input data (but the
parameter values are forced to abide by the theoretical
requirements). Moreover, although the cryptographic
strength of this program is conjectured to be good, an
important component (the underlying pseudo-random
algorithm) has been deliberately chosen to be an
INSECURE alternative.
User's guide:
This is ANSI C source code. The compiled program is a
command-line utility, taking four optional file names:
cleartext file, ciphertext file, final secret key file, and
initial secret key file.
The main challenge is to find two pairs <cleartext file,
initial secret key file> that produce the same final secret
key file.
The auxiliary challenge is to find an algorithm that
recovers the initial secret key file from a cleartext file
and the corresponding ciphertext file.
How to read this source code:
Sequentially. Housekeeping stuff is identified with /**/
/* at the beginning of each line. In addition, /*RULE*/
/* identifies places in the source code where a theoretical
rule is enforced (in the context of processing the initial
secret key file).
*/
/**********************************************************************/
/*** ***/
/*** The base Frogbit algorithm ***/
/*** ***/
/**********************************************************************/
typedef int ind_t;
typedef int bit;
/*--------------------------------------------------------------------*/
/*---------------- the state of the Frogbit algorithm ----------------*/
ind_t T[10]; /* the current permutation table, T(i-1-r'(i-1)) */
ind_t d_; /* the current key stream number, d'(i-1) */
bit s; /* the previous bit, s{i-1} */
/* local variables for the run length process */
ind_t r_; /* the current bounded run count, r'(i-1) */
ind_t acc_d; /* accumulated binary representation K2{i-1}, k2{i}*/
/*--------------------------------------------------------------------*/
/*------------------ keystream "drift" accumulators ------------------*/
/* These accumulators are for information purposes. Their final
values may come into play for a hash code. The active state of
the pseudo-random generators is dealt with later. */
struct cntr
{
unsigned long c; /* A count of consumed keystream bits ... */
int i; /* ... for this key stream source. */
} drift_cnt[10];
/*--------------------------------------------------------------------*/
/*------------------ the index permutation process -------------------*/
void index_permutation(int j)
{
int temp;
int temp_d_= T[j];
switch((d_<<1)+s)
{
case 0:
temp=T[0];T[0]=T[5];T[5]=T[2];T[2]=T[7];T[7]=temp;
temp=T[1];T[1]=T[8];T[8]=T[6];T[6]=T[4];T[4]=T[3];T[3]=T[9];
T[9]=temp;
break;
case 1:
temp=T[0];T[0]=T[2];T[2]=T[7];T[7]=temp;
temp=T[1];T[1]=T[3];T[3]=T[6];T[6]=T[9];T[9]=T[4];T[4]=T[8];
T[8]=T[5];T[5]=temp;
break;
case 2:
temp=T[0];T[0]=T[6];T[6]=T[8];T[8]=T[9];T[9]=T[5];T[5]=T[7];
T[7]=T[1];T[1]=temp;
temp=T[2];T[2]=T[4];T[4]=T[3];T[3]=temp;
break;
case 3:
temp=T[0];T[0]=T[6];T[6]=temp;
temp=T[1];T[1]=T[5];T[5]=T[3];T[3]=T[4];T[4]=T[2];T[2]=T[8];
T[8]=T[7];T[7]=T[9];T[9]=temp;
break;
case 4:
temp=T[0];T[0]=T[3];T[3]=T[6];T[6]=T[5];T[5]=T[1];T[1]=T[2];
T[2]=temp;
temp=T[4];T[4]=T[8];T[8]=T[7];T[7]=T[9];T[9]=temp;
break;
case 5:
temp=T[0];T[0]=T[6];T[6]=T[7];T[7]=T[3];T[3]=T[1];T[1]=T[2];
T[2]=T[9];T[9]=temp;
temp=T[4];T[4]=T[5];T[5]=T[8];T[8]=temp;
break;
case 6:
temp=T[0];T[0]=T[4];T[4]=T[3];T[3]=T[7];T[7]=T[6];T[6]=T[1];
T[1]=T[8];T[8]=T[5];T[5]=temp;
temp=T[2];T[2]=T[9];T[9]=temp;
break;
case 7:
temp=T[0];T[0]=T[5];T[5]=T[4];T[4]=temp;
temp=T[1];T[1]=T[9];T[9]=T[8];T[8]=T[6];T[6]=T[2];T[2]=T[3];
T[3]=T[7];T[7]=temp;
break;
case 8:
temp=T[0];T[0]=T[8];T[8]=T[9];T[9]=T[5];T[5]=T[3];T[3]=T[2];
T[2]=T[1];T[1]=temp;
temp=T[4];T[4]=T[6];T[6]=T[7];T[7]=temp;
break;
case 9:
temp=T[0];T[0]=T[9];T[9]=T[7];T[7]=T[8];T[8]=T[1];T[1]=T[4];
T[4]=T[2];T[2]=T[6];T[6]=temp;
temp=T[3];T[3]=T[5];T[5]=temp;
break;
case 10:
temp=T[0];T[0]=T[7];T[7]=T[2];T[2]=T[4];T[4]=T[1];T[1]=T[6];
T[6]=T[5];T[5]=T[9];T[9]=temp;
temp=T[3];T[3]=T[8];T[8]=temp;
break;
case 11:
temp=T[0];T[0]=T[1];T[1]=T[4];T[4]=T[7];T[7]=T[5];T[5]=T[2];
T[2]=T[8];T[8]=T[3];T[3]=temp;
temp=T[6];T[6]=T[9];T[9]=temp;
break;
case 12:
temp=T[0];T[0]=T[7];T[7]=T[6];T[6]=T[3];T[3]=temp;
temp=T[1];T[1]=T[4];T[4]=T[9];T[9]=T[2];T[2]=T[5];T[5]=T[8];
T[8]=temp;
break;
case 13:
temp=T[0];T[0]=T[3];T[3]=T[5];T[5]=T[2];T[2]=temp;
temp=T[1];T[1]=T[9];T[9]=T[7];T[7]=T[4];T[4]=T[6];T[6]=T[8];
T[8]=temp;
break;
case 14:
temp=T[0];T[0]=T[8];T[8]=T[4];T[4]=T[2];T[2]=T[1];T[1]=T[9];
T[9]=T[3];T[3]=temp;
temp=T[5];T[5]=T[7];T[7]=T[6];T[6]=temp;
break;
case 15:
temp=T[0];T[0]=T[9];T[9]=T[6];T[6]=T[3];T[3]=T[1];T[1]=T[5];
T[5]=temp;
temp=T[2];T[2]=T[4];T[4]=T[7];T[7]=T[8];T[8]=temp;
break;
case 16:
temp=T[0];T[0]=T[7];T[7]=T[2];T[2]=T[6];T[6]=T[1];T[1]=T[3];
T[3]=T[9];T[9]=T[8];T[8]=temp;
temp=T[4];T[4]=T[5];T[5]=temp;
break;
case 17:
temp=T[0];T[0]=T[4];T[4]=T[1];T[1]=T[7];T[7]=T[8];T[8]=temp;
temp=T[2];T[2]=T[9];T[9]=T[3];T[3]=T[5];T[5]=T[6];T[6]=temp;
break;
case 18:
temp=T[0];T[0]=T[2];T[2]=T[3];T[3]=T[8];T[8]=temp;
temp=T[1];T[1]=T[7];T[7]=T[5];T[5]=T[6];T[6]=T[4];T[4]=T[9];
T[9]=temp;
break;
case 19:
temp=T[0];T[0]=T[1];T[1]=T[6];T[6]=T[7];T[7]=T[3];T[3]=T[4];
T[4]=temp;
temp=T[2];T[2]=T[5];T[5]=T[9];T[9]=T[8];T[8]=temp;
break;
}
d_ = temp_d_;
}
/*--------------------------------------------------------------------*/
/*-------------------- the core Frogbit algorithm --------------------*/
bit get_PR_bit(ind_t PR_gen_selector,int ik); /* Forward reference:
key stream sources */
bit encipher_bit(bit m_i_)
{
int base;
bit k1_i_ = get_PR_bit(d_,0);
bit k2_i_ = get_PR_bit(d_,1);
bit s_i_ = m_i_^k1_i_;
drift_cnt[d_].c++;
if (s!=s_i_)
if (r_==0) base=0;
else base=(acc_d+1)<<1;
else if (r_!=0) base=(acc_d+3)<<1;
else
{
acc_d=k2_i_;
r_=1;
return s_i_^k2_i_;
}
index_permutation(base+k2_i_);
r_= 0;
s=s_i_;
return s_i_^k2_i_;
}
bit decipher_bit(bit e_i_)
{
int base;
bit k1_i_ = get_PR_bit(d_,0);
bit k2_i_ = get_PR_bit(d_,1);
bit s_i_ = e_i_^k2_i_;
drift_cnt[d_].c++;
if (s!=s_i_)
if (r_==0) base=0;
else base=(acc_d+1)<<1;
else if (r_!=0) base=(acc_d+3)<<1;
else
{
acc_d=k2_i_;
r_=1;
return s_i_^k1_i_;
}
index_permutation(base+k2_i_);
r_= 0;
s=s_i_;
return s_i_^k1_i_;
}
/*--------------------------------------------------------------------*/
/*------------ default initialization of the Frogbit state -----------*/
void start_cipher(void) /* This mechanism may be overridden, and indeed
it is when a secret key file includes more
than just the PRNG state. */
{
ind_t i;
d_= s= r_= 0;
for (i=0;i<10;i++)
{
T[i]=i;
drift_cnt[i].c=0;
drift_cnt[i].i=i;
}
/* do the processing as if m{i}=0 until one d(i) is drawn,
and do it once more */
do
encipher_bit(0);
while (r_!=0);
encipher_bit(0);
}
/*--------------------------------------------------------------------*/
/**/#include <stdio.h>
/**/#include <string.h>
/**/#include <stdlib.h>
/**/#include <ctype.h>
/**/#include <limits.h>
/**/#include <assert.h>
#if (INT_MAX<=32767)
#define L "l"
#else
#define L
#endif
/*--------------------------------------------------------------------*/
/*------------------- file encryption/decryption ---------------------*/
int omit_count=0;
void encipher(FILE *in, FILE *out)
{
int i, c, e;
int cnext;
cnext=getc(in);
if (EOF==cnext) return;
for (;;)
{
c=cnext;
cnext=getc(in);
if (EOF==cnext) break;
e=0;
for (i=1;i<=(1<<(CHAR_BIT-1));i<<=1)
if (encipher_bit(0!=(i&c))) e|=i;
fputc(e,out);
}
e=0;
for (i=1;i<=(1<<(CHAR_BIT-omit_count-1));i<<=1)
if (encipher_bit(0!=(i&c))) e|=i;
fputc(e,out);
}
void decipher(FILE *in, FILE *out)
{
int i, c, e;
int cnext;
cnext=getc(in);
if (EOF==cnext) return;
for (;;)
{
e=cnext;
cnext=getc(in);
if (EOF==cnext) break;
c=0;
for (i=1;i<=(1<<(CHAR_BIT-1));i<<=1)
if (decipher_bit(0!=(i&e))) c|=i;
fputc(c,out);
}
c=0;
for (i=1;i<=(1<<(CHAR_BIT-omit_count-1));i<<=1)
if (decipher_bit(0!=(i&e))) c|=i;
fputc(c,out);
}
/**********************************************************************/
/*** ***/
/*** read and write the Frogbit state ***/
/*** (minimal and extended secret keys) ***/
/*** ***/
/**********************************************************************/
/*--------------------------------------------------------------------*/
/*---------- the state of the 10 PRNGs (minimal secret key) ----------*/
unsigned long next [10][2]={{1,1},{1,1},{1,1},{1,1},{1,1}
,{1,1},{1,1},{1,1},{1,1},{1,1}};
/*--------------------------------------------------------------------*/
/*---- get the state from the file data, enforce theoretical rules ---*/
void adjust_prng_state(void); /* forward references */
void get_prng_design(int argc, char *argv[]);
void get_state(int argc, char *argv[])
{
int i;
/*{ PRNG state }*/
for (i=0;i<10;i++) {
if (argc>(2*i+1))
{
next[i][0]=strtoul(argv[2*i+1],NULL,0);
}
else
break;
if (argc>(2*i+2))
{
next[i][1]=strtoul(argv[2*i+2],NULL,0);
}
else
break;
}
if (argc>=21)
{
/*{ key-stream selection state }*/
d_= 0;
if (argc>21)
d_=strtoul(argv[21],NULL,0)%10; /*RULE*//* 0<=d_<10 */
/*{ index permutation state }*/
for (i=0;i<10;i++)
T[i]=i;
for (i=0;i<10;i++)
if (argc>(i+22))
{
int ii;
int cand=strtoul(argv[i+22],NULL,0)%10; /*RULE*//* 0<=T[i]<10 */
for (ii=i;ii<10;ii++)
if (T[ii]==cand)
break;
if (ii<10) /*RULE*//* the vector T[10] is a permutation */
{
for (;ii>i;ii--)
T[ii]=T[ii-1];
T[i]=cand;
}
}
else
break;
/*{ run length encoding (RLE) state }*/
s= r_= acc_d= 0;
if (argc>32)
s=strtoul(argv[32],NULL,0)%2; /*RULE*//* s is a single bit */
if (argc>33)
r_=strtoul(argv[33],NULL,0)%2; /*RULE*//* 0<=r_<2 */
if ((argc>34)&&(r_>0))
{
acc_d=strtoul(argv[34],NULL,0);
acc_d%=1<<r_; /*RULE*//* 0<=acc_d<(2**r_) */
}
if (argc>35)
/*{ PRNG design parameters }*/
get_prng_design(argc-34,argv+34); /* rules specific to the PRNG */
adjust_prng_state(); /* rules specific to the PRNG */
for (i=0;i<10;i++)
{
drift_cnt[i].c=0;
drift_cnt[i].i=i;
}
}
else
{ /* secret key limited to PRNG state, use
default Frogbit initialization */
adjust_prng_state(); /* rules specific to the PRNG */
start_cipher();
}
}
/*--------------------------------------------------------------------*/
/*----------- write the state to the final secret key file -----------*/
/**/void print_prng_design(FILE *fp); /* forward reference */
/**/void print_drift_accum(FILE *fp); /* forward reference */
/**/int verbose_flag=0;
/**/void print_state(FILE *fp)
/**/{
/**/ int i;
/**/ adjust_prng_state();
/**/ fprintf(fp,"{ PRNG state }");
/**/ for (i=0;i<10;i++)
/**/ {
/**/ fprintf(fp," 0x%" L "X 0x%" L "X",next[i][0],next[i][1]);
/**/ if (0==((i+2)%3)) fprintf(fp,"\n");
/**/ }
/**/ fprintf(fp,"\n");
/**/ if (verbose_flag)
/**/ print_drift_accum(fp);
/**/ fprintf(fp,"{ key-stream selection state } %d\n",d_);
/**/ fprintf(fp,"{ index permutation state }");
/**/ for (i=0;i<10;i++)
/**/ fprintf(fp," %d",T[i]);
/**/ fprintf(fp,"\n{ run length encoding (RLE) state } %d %d %d\n"
/**/ ,s,r_,acc_d%(1<<r_));
/**/ print_prng_design(fp);
/**/}
/**/int cmp_cntr(const void *a,const void *b)
/**/{
/**/ return ( (((struct cntr *)a)->c<((struct cntr *)b)->c)
/**/ ?-1
/**/ :(((struct cntr *)a)->c>((struct cntr *)b)->c)
/**/ );
/**/}
/**/void print_drift_accum(FILE *fp)
/**/{
/**/ int i;
/**/ qsort(drift_cnt,10,sizeof(drift_cnt[0]),cmp_cntr);
/**/ fprintf(fp,"{ keystream drift: %d:%" L "d"
/**/ ,drift_cnt[0].i,drift_cnt[0].c);
/**/ for(i=1;i<10;i++)
/**/ fprintf(fp," %d+%" L "d",drift_cnt[i].i
/**/ ,drift_cnt[i].c-drift_cnt[i-1].c);
/**/ fprintf(fp," }\n");
/**/}
/**********************************************************************/
/*** ***/
/*** housekeeping tasks ***/
/*** ***/
/**********************************************************************/
/*--------------------------------------------------------------------*/
/*-------- housekeeping: lexical analysis of secret key file ---------*/
/**/char file_buf[8*1024];
/**/void parse_state(FILE *fp)
/**/{
/**/ int argc;
/**/ char *argv[25+11];
/**/ char *s;
/**/ file_buf[fread(file_buf,1,sizeof(file_buf)-1,fp)]=0;
/**/ fclose(fp);
/**/ s=file_buf;
/**/ argv[0]="?";
/**/ for(argc=1;argc<(25+11);argc++)
/**/ {
/**/ for (;;)
/**/ {
/**/ char *end_comment;
/**/ argv[argc]=strtok(s," \n\r\t\v\f"); s=NULL;
/**/ if ((NULL==argv[argc])||('{'!=argv[argc][0]))
/**/ break;
/**/ for(;;)
/**/ {
/**/ end_comment=strchr(argv[argc],'}');
/**/ if (NULL!=end_comment) break;
/**/ argv[argc]=strtok(NULL," \n\r\t\v\f");
/**/ if (NULL==argv[argc])
/**/ break;
/**/ }
/**/ if (NULL==argv[argc])
/**/ break;
/**/ if (0!=*(end_comment+1))
/**/ {
/**/ argv[argc]=end_comment+1;
/**/ break;
/**/ }
/**/ }
/**/ if (NULL==argv[argc])
/**/ break;
/**/ }
/**/ get_state(argc,argv);
/**/}
/*--------------------------------------------------------------------*/
/*---------- housekeeping: help to the user in case of error ---------*/
/**/void usage(char *s)
/**/{
/**/ fprintf(stderr,
/**/ "usage: %s [flags] [inp [out [final [init]]]]\n"
/**/ "\n"
/**/ " Frogbit file encryption demo\n"
/**/ "\n"
/**/ "flags:\n"
/**/ " -e encryption operation (default)\n"
/**/ " -d decryption operation\n"
/**/ " -t cleartext file is text format (default is binary file)\n"
/**/ " -f force overwriting existing files\n"
/**/ " -v a more verbose final state file\n"
/**/ " -o[1-7] omit so many bits at the end of input file\n"
/**/ "\n"
/**/ "arguments\n"
/**/ " inp: input file name (default: standard input)\n"
/**/ " out: output file name (default: standard output)\n"
/**/ " final: final state file name (default: standard error)\n"
/**/ " init: initial state file name (secret key)\n"
/**/ ,s);
/**/}
/*--------------------------------------------------------------------*/
/*- housekeeping: the main program, checking command line parameters -*/
/**/int main (int argc, char *argv[])
/**/{
/**/ FILE *in=stdin;
/**/ FILE *out=stdout;
/**/ FILE *init_st=NULL;
/**/ FILE *final_st=stderr;
/**/ int decrypt_flag=0;
/**/ int binary_flag=1;
/**/ int force_flag=0;
/**/ int i;
/**/ for (i=1;i<argc;i++)
/**/ {
/**/ if ('-'==argv[i][0])
/**/ switch (toupper(argv[i][1]))
/**/ {
/**/ case 'D':
/**/ decrypt_flag=1;
/**/ case 'E':
/**/ break;
/**/ case 'F':
/**/ force_flag=1;
/**/ break;
/**/ case 'T':
/**/ binary_flag=0;
/**/ break;
/**/ case 'V':
/**/ verbose_flag=1;
/**/ break;
/**/ case 'O':
/**/ omit_count= ((argv[i][2]>='1')&&(argv[i][2]<='7'))
/**/ ?(argv[i][2]-'0')
/**/ :0;
/**/ break;
/**/ default:
/**/ {
/**/ fprintf(stderr,"Error: unknown flag!\n\n");
/**/ usage(argv[0]);
/**/ exit(EXIT_FAILURE);
/**/ }
/**/ }
/**/ else
/**/ break;
/**/ }
/**/ if (argc>(i))
/**/ {
/**/ in=fopen(argv[i],(binary_flag||decrypt_flag)?"rb":"r");
/**/ if (NULL==in)
/**/ fprintf(stderr,"Error: can't open file \"%s\"!\n\n",argv[i]);
/**/ }
/**/ if (argc>(i+1))
/**/ {
/**/ out=fopen(argv[i+1],"r"); if (out) fclose(out);
/**/ if ((NULL==out)||force_flag)
/**/ {
/**/ out=fopen(argv[i+1],(binary_flag||!decrypt_flag)?"wb":"w");
/**/ if (NULL==out)
/**/ fprintf(stderr,"Error: can't open file \"%s\"!\n\n",argv[i+1]);
/**/ }
/**/ else
/**/ {
/**/ fprintf(stderr,"Error: file \"%s\" already exists!\n\n"
,argv[i+1]);
/**/ out=NULL;
/**/ }
/**/ }
/**/ if (argc>(i+2))
/**/ {
/**/ final_st=fopen(argv[i+2],"r"); if (final_st) fclose(final_st);
/**/ if ((NULL==final_st)||force_flag)
/**/ {
/**/ final_st=fopen(argv[i+2],"w");
/**/ if (NULL==final_st)
/**/ fprintf(stderr,"Error: can't open file \"%s\"!\n\n"
,argv[i+2]);
/**/ }
/**/ else
/**/ {
/**/ fprintf(stderr,"Error: file \"%s\" already exists!\n\n"
,argv[i+2]);
/**/ final_st=NULL;
/**/ }
/**/ }
/**/ if (argc>(i+3))
/**/ {
/**/ init_st=fopen(argv[i+3],"r");
/**/ if (NULL==init_st)
/**/ fprintf(stderr,"Error: can't open file \"%s\"!\n\n",argv[i+3]);
/**/ }
/**/ if ((NULL==in)||(NULL==out)||(NULL==final_st))
/**/ {
/**/ usage(argv[0]);
/**/ exit(EXIT_FAILURE);
/**/ }
/**********************************************************************/
/*** ***/
/*** here is what this program really does! ***/
/*** ***/
/**********************************************************************/
if (NULL!=init_st) parse_state(init_st);/* use the initial key file */
else start_cipher(); /* use defaut (secret) key */
if (decrypt_flag)
decipher(in,out);
else
encipher(in,out);
print_state(final_st);
fclose(in);
fclose(out);
fclose(final_st);
return EXIT_SUCCESS;
}
/**********************************************************************/
/*** ***/
/*** the PRNG, pseudo-random number generator ***/
/*** ***/
/**********************************************************************/
/*
The following criteria were used to select a Pseudo-Random Number
Generator:
- EASILY cryptanalyzed (when used in a SIMPLE stream cipher),
- simple to program,
- single bit output,
- predictable period,
- "key space" close to 2**32 per generator.
The rationale for the first criteria is to present a SINGLE
challenge to cryptanalysis: the very FROGBIT algorithm.
We selected the "Linear Feedback Shift Register" (LFSR) generator
(also known as the Tausworthe generator). We use pairs of
independent LFSR generators to generate the bit pairs needed by
the Frogbit algorithm.
For purpose of programming, here are a few simple facts about the
LFSR generator:
i) the single parameter of a LFSR generator is a binary number
representing a "polynomial";
ii) the "degree" of this polynomial is the rank of the highest
bit of this number;
iii) the polynomial must be "irreductible", a property analogue
to the primality of numbers, but based on "polynomial
arithmetic",
iv) the degree of the polynomial must be a "Marsenne prime
number" (p such that 2**p-1 is prime), that is 2, 3, 5, 7,
13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, and
v) the state of the generator is a number strictly between 0
and 2**degree.
Briefly, our design allows any irreductible polynomial of degree
up to 31 (the 20 polynomials must be of the same degree).
An extra benefit of the LFSR is the ability to let the user
customize the generator. This feature is included in this program
in order to provide another variable for cryptanalysis purposes.
Essentially, we allow the "initial secret key file" to specify
the degree, and the 20 polynomials (actually, the program uses
the largest polynomial not exceeding the specified value). The
default polynomials are the 20 largest irreductible polynomials
of degree 31.
*/
/*--------------------------------------------------------------------*/
/*--------- the design parameters of the 10 LSFR generators ----------*/
int degree=31;
unsigned long poly[10][2]=
#define DEFAULT_POLYGONS \
{{0xA43F6A87,0x85A308A7},{0x931989F7,0x8370732D} \
/*3.243F6A88 85A308D3 13198A2E 03707344 */ \
,{0xA4093815,0xA99F31D1},{0x882EFA97,0xEC4E6C63} \
/* A4093822 299F31D0 082EFA98 EC4E6C89 */ \
,{0xC52821B5,0xB8D0135D},{0xBE54668B,0xB4E90C4B} \
/* 452821E6 38D01377 BE5466CF 34E90C6C */ \
,{0xC0AC2993,0xC97C50A9},{0xBF84D5A1,0xB54708F7} \
/* C0AC29B7 C97C50DD 3F84D5B5 B5470917 */ \
,{0x9216D5CF,0x8979FAF1},{0xD1310BA1,0x98DFB581}}; \
/* 9216D5D9 8979FB1B D1310BA6 98DFB5AC */
DEFAULT_POLYGONS
/*--------------------------------------------------------------------*/
/*-------------------- the LSFR generator program --------------------*/
bit get_PR_bit(ind_t ind,int ik)
{
/* parity of each byte value */
static const unsigned char parity[1<<CHAR_BIT]=
{0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1
,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0
,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0
,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1
,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0
,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1
,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1
,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0
};
union /* an ANSI C programmer's trick to access individual bytes
of a 32 bit number */
{
unsigned long whole;
unsigned char part[4];
} s;
bit return_value;
s.whole=next[ind][ik]&poly[ind][ik];
return_value=( parity[s.part[0]]
^parity[s.part[1]]
^parity[s.part[2]]
^parity[s.part[3]]
);
next[ind][ik]= (next[ind][ik]>>1)
|(((unsigned long)return_value)<<(degree-1));
return return_value;
}
/*--------------------------------------------------------------------*/
/*-- the theoretic rules specific to the state of the LSFR generator -*/
void adjust_prng_state(void)
{
int i;
for (i=0;i<10*2;i++)
{
next[i/2][i%2]&=(1UL<<degree)-1; /*RULE*//* for a degree "n"
polynomial,there are "n" bits of state */
if (0==next[i/2][i%2]) next[i/2][i%2]=1; /*RULE*//* the state =0
must be avoided */
}
}
/**********************************************************************/
/*** ***/
/*** we allow modification of the PRNG "design" parameters ***/
/*** ***/
/**********************************************************************/
/*--------------------------------------------------------------------*/
/*- get the LSFR design from the file data, enforce theoretical rules */
void prepare_irreductibles(void);
int is_irreductible(unsigned long n);
void get_prng_design(int argc, char *argv[])
{
unsigned long cur_poly;
int i;
/*{ PRNG design parameters }*/
if (argc>1)
degree=atoi(argv[1]);
/*RULE*//* the degree of the polynomials is a Marsenne prime
number between 13 and 31 inclusive */
if ((degree!=13)&&(degree!=17)&&(degree!=19))
degree=31;
prepare_irreductibles();
cur_poly=(1L<<degree)|((1L<<degree)-1);
for (i=0;i<10*2;i++)
{
if (argc>(i+2))
cur_poly=strtoul(argv[i+2],NULL,0);
for(;;)
{
/*RULE*//* the same degree applies to every polynomials */
/*RULE*//* an irreductible polynomial has term x**0 to 1 */
cur_poly &= (1L<<degree)-1;
cur_poly |= (1L<<degree)+1;
/*RULE*//* the polynomials must be irreductible */
if (is_irreductible(cur_poly))
{
int ii; /*RULE*//* the polynomials must be distinct */
for (ii=0;ii<i;ii++)
if (cur_poly==poly[ii/2][ii%2])
break;
if (ii>=i)
break;
}
cur_poly-=2; /* try another one */
}
poly[i/2][i%2]=cur_poly;
cur_poly-=2;
}
}
/*--------------------------------------------------------------------*/
/* write the LSFR design to the final file (if not the default design)*/
/**/void print_prng_design(FILE *fp)
/**/{
/**/ static const unsigned long def_poly[10][2]=DEFAULT_POLYGONS
/**/ int i;
/**/ for (i=0;i<10*2;i++)
/**/ if (poly[i/2][i%2]!=def_poly[i/2][i%2])
/**/ break;
/**/ if ((i<10*2)||(degree!=31)||verbose_flag)
/**/ {
/**/ fprintf(fp,"{ PRNG design parameters } %d",degree);
/**/ for (i=0;i<10;i++)
/**/ {
/**/ fprintf(fp," 0x%" L "X 0x%" L "X",poly[i][0],poly[i][1]);
/**/ if (0==((i+2)%3)) fprintf(fp,"\n");
/**/ }
/**/ fprintf(fp,"\n");
/**/ }
/**/}
/**********************************************************************/
/*** ***/
/*** polynomial arithmetic ***/
/*** ***/
/**********************************************************************/
/*--------------------------------------------------------------------*/
/*-------------------- polynomial multiplication ---------------------*/
/**/unsigned long mult_poly(unsigned long a, unsigned long b)
/**/{
/**/ unsigned long r=0;
/**/ unsigned long i;
/**/ for (i=1;i<=b;i<<=1)
/**/ {
/**/ if (b&i)
/**/ r^=a;
/**/ a<<=1;
/**/ }
/**/ return r;
/**/}
/*--------------------------------------------------------------------*/
/*----------------------- polynomial division ------------------------*/
/**/unsigned long div_poly( unsigned long div_end
/**/ , unsigned long div_or
/**/ , unsigned long *remainder)
/**/{
/**/ int m_end=-1;
/**/ int m_or=-1;
/**/ unsigned long r=0;
/**/ unsigned long rem=div_end;
/**/ int i;
/**/ for (i=0;i<(CHAR_BIT*sizeof(unsigned long));i++)
/**/ {
/**/ if (div_end&(1L<<i))
/**/ m_end=i;
/**/ if (div_or&(1L<<i))
/**/ m_or=i;
/**/ }
/**/ if (m_or<0) assert("Polynomial division by zero!");
/**/ for (;m_end>=m_or;m_end--)
/**/ {
/**/ if (rem&(1<<m_end))
/**/ {
/**/ rem ^= div_or<<(m_end-m_or);
/**/ r|=1<<(m_end-m_or);
/**/ }
/**/ }
/**/ *remainder=rem;
/**/ return r;
/**/}
/*--------------------------------------------------------------------*/
/*------------- find all 16 bit irreductible polynomials -------------*/
/**/#define NB_USHORT_IRREDUCTIBLES 4720
/**/unsigned int nb_ushort_irreductibles;
/**/unsigned short all_ushort_irreductibles[NB_USHORT_IRREDUCTIBLES];
/**/void prepare_irreductibles(void)
/**/{
/**/#define MAX 0x10000L
/**/#define INDICE(x) ((x-3)/2)
/**/ char *irreductible = (char *)malloc((size_t)INDICE(MAX));
/**/ long i;
/**/ long i_fact;
/**/ for (i=0;i<INDICE(MAX);i++)
/**/ irreductible[i] = 1;
/**/ for (i_fact=3;i_fact<MAX;i_fact+=2)
/**/ if (irreductible[INDICE(i_fact)])
/**/ for (i=2;;i++)
/**/ {
/**/ unsigned long ip=mult_poly(i_fact,i);
/**/ if (ip >= MAX)
/**/ break;
/**/ if (ip&1) irreductible[INDICE(ip)] = 0;
/**/ }
/**/ nb_ushort_irreductibles = 1;
/**/ for (i=0;i<INDICE(MAX);i++)
/**/ if (irreductible[i]) nb_ushort_irreductibles++;
/**/ assert(NB_USHORT_IRREDUCTIBLES==nb_ushort_irreductibles);
/**/ all_ushort_irreductibles[0] = 2;
/**/ i_fact = 1;
/**/ for (i=3;i<MAX;i+=2)
/**/ if (irreductible[INDICE(i)])
/**/ all_ushort_irreductibles[i_fact++] = i;
/**/ free(irreductible);
/**/#undef MAX
/**/#undef INDICE
/**/}
/*--------------------------------------------------------------------*/
/*----------------- 32 bit polynomial irreductibility ----------------*/
/**/int is_irreductible(unsigned long n)
/**/{
/**/ unsigned int i;
/**/ if (n>1)
/**/ for (i=0;i<nb_ushort_irreductibles;i++)
/**/ {
/**/ unsigned long rem;
/**/ if (all_ushort_irreductibles[i] >= n)
/**/ break;
/**/
/**/ div_poly(n,all_ushort_irreductibles[i],&rem);
/**/ if (0 == rem)
/**/ return 0;
/**/ }
/**/ return 1;
/**/}
/*--------------------------------------------------------------------*/
/*----------------------------- the end ------------------------------*/
|
eSTREAM Project Powered by ViewCVS 1.0-dev |
ViewCVS and CVS Help |