# PERMPOLYPRNG, a simple PRNG based on permutation polynomials mod 2**n. # Prologue. # If f(), a permutation polynomial mod 2**n, is employed in the iteration # x' = f(x), it is well known that the lower order bits of the sequence of words # x obtained are very poor statistically. On the other hand, for values of n # that are not too small, the higher order bits are found to be very good # statistically. See the test statistics for n=32 in Appendix further below. # For larger values of n this tendency persists, as the user may easily # convince himself via corresponding modifications of our illustrative example. # Consequently it appears to be a good idea to design a PRNG that delivers the # superior quality pseudo-randomness of the higher order bits of x. # While we have thus made use of (naturally limited) empirical data, there is # in fact a rigorous theoretical explanation of the said phenomenon in general # terms. From certain results proved by E. Lerner in his recent PhD thesis, it # can namely be inferred that for sufficently large n, the sequence of higher # order bits of the words x of the iteration is practically indistinguishable # from a truly random one. # The kernel of the present software is the function getbitsecseq() which # collects a user-specified number of the higher order bits from each word x of # the iteration x'=f(x) into a byte array. It may be noted that getbitsecseq() # could be easily translated from Python into any other programming languages # in case of need. The case of n=32 and taking the leading 8 bits for output # seems interesting. (Specification of the polynomial and the seed would take # a total of 128 bits.) # Version 1.0, released on 05.03.2015. # Code lines of documents with the same version number are always identical. # There may be interim modifications of comment lines. The most recent document # of PERMPOLYPRNG can be obtained from # http://s13.zetaboards.com/Crypto/topic/7355166/1/ # This software may be freely used: # 1. for all personal purposes unconditionally and # 2. for all other purposes under the condition that its name, version number # and authorship are explicitly mentioned and that the author is informed of # all eventual code modifications done. # The author is indebted to TPS for review and suggestions throughout # PERMPOLYPRNG's development phase. Any remaining deficiencies of the software # are however the sole responsibilty of the author. # Constructive critiques and comments are sincerely solicited. # Email address of the author: mok-kong.shen@t-online.de ############################################################################### # The functions fullperiodcriteria(), evalpermpoly(), invpermpoly() are # general functions required for computation with permutation polynomials # mod 2**n. # Modify user-supplied coefficients of the polynomial poly so as to satisfy the # full-period criteria of a permutation polynomial mod 2**n. The degree of poly # is required to be at least 2. m denotes the number of coefficients of the # polynomial, i.e. degree of polynomial plus 1. For the criteria see ref.[1], # p.283. # [1] V. Anashin, A. Khrennikov, Applied Algebraic Dynamics, Berlin, 2009. # http://www.degruyter.com/view/supplement/9783110203011_Errata.pdf # We use for simplification of coding a restricted form of the criteria, namely: # c_0 = c_1 = 1 mod 4 # c_i = 0 mod 4 for all other i def fullperiodcriteria(poly,m): global np1,tpwnm1 if m<3: print("Error in fullperiodcriteria") exit(1) gg=(tpwnm1<<2)&tpwnm1 permpoly=poly[:] for i in range(2): permpoly[i]=(permpoly[i]&gg)|1 for i in range(2,m): permpoly[i]&=gg return(permpoly) # Evaluate permpoly with argument x with Horner's method. def evalpermpoly(permpoly,m,x): global np1,tpwnm1 y=permpoly[m-1] for i in range(m-2,-1,-1): y=(y*x+permpoly[i])&tpwnm1 return(y) # Inverse of evalpermpoly(). First derivative of permpoly(x) = 1 mod 2. Hensel's # lifting lemma leads to the iteration: x_(i+1)=x_i-g(x_i) mod 2**(i+1), with # g(x)=permpoly(x)-y. See ref.[1], p.306. def invpermpoly(permpoly,m,y): global np1,tpwnm1 if (((permpoly[0]-y)&tpwnm1)&1)==0: x=0 else: x=1 for i in range(2,np1,1): x=(x-(evalpermpoly(permpoly,m,x)-y))&tpwnm1 return(x) # The PRNG of our design. Use x0 as seed to generate bit sequences (to be # collected into the byte array byarray) from employing a section of bits from # bi2-th down to bi1-th (inclusive) of each n-bit word obtained via the # iteration x' = f(x) where f() is the given permutation polynomial mod 2**n. # Note our use in the illustrative example of statements like # bys=getbitsecseq(.....) but not getbitsecseq(.....) alone i.e. without the # assignment to a variable, since otherwise there would under circumstances be # a huge print-out of the returned byarray. def getbitsecseq(x0,bi2,bi1,byn): global n,np1,tpwnm1,polynormdegree,polynorm np1=n+1 tpwnm1=(2**n)-1 numbcoeff=polynormdegree+1 assert len(polynorm)==numbcoeff assert n > bi2 >= bi1 >= 0 and bi2-bi1 < n # print("Bit section used is from",bi2,"th bit to",bi1,"th bit of a", # n,"bit word") # ith element of the list ones contains a value of i one-bit. ones=[0] v=0 for i in range(1,np1): v<<=1 v|=1 ones.append(v) # Slightly modify, if required, the user given coefficients to ensure full # period. poly=fullperiodcriteria(polynorm,numbcoeff) biw=bi2-bi1+1 shf=bi2+1-biw mask=ones[biw]<>shf nbits+=biw while nbits>=8: df=nbits-8 byarray.append(w>>df) byi+=1 w&=ones[df] nbits-=8 byarray=byarray[:byn] return(byarray) ################################################################################ # Print a section of byarray, beginning at index i1 for a length leng, in # hexadecimal format. (In Python arrays start at index 0.) def printhex(byarray,i1,leng): assert (i1+leng)<=len(byarray) hexstr="" for i in range(i1,i1+leng): u=hex(byarray[i]) if len(u)==3: v='0'+u[2:] else: v=u[2:] hexstr+=v print(hexstr) return ############################################################################################# import sys # Illustrative example. # The communication partners have in general to agree on the same (identical) # following system parameter values: n=32 polynormdegree=2 # polynorm is a list of user-chosen pseudo-random values (list length = # polynomdegree + 1) of n bits to serve as the coefficients of the permutation # polynomial to be used to generate pseudo-random values, from which certain # higher order bits will be extracted to become the output of our PRNG. polynorm=[0xad6caf7a, 0xc58358c8, 0x2e72ea7b] # User-chosen seed for the run of the PRNG. seed=0x8e4c43e3 # Use the leading bit of each word. testbyteamount=(2**24)/8 bys=getbitsecseq(seed,n-1,n-1,testbyteamount) sys.stdout.write(bys)