# BASICS, a simple encryption scheme (with authentication) based on permutations # and dynamic substitutions of characters. # Prologue. # The kernel of this software is the function encryptionprocessing(), which # processes its input (a user-given text string transformed into a list of # characters in the global variable glist) with the following two steps, which # are in principle entirely classical (excepting the measures to achieve # dynamics/variability of processing): # # (1) Perform a pseudo-random permutation of the characters. See permutation(). # # (2) Perform a substitution of the characters with a pseudo-randomly generated # polyalphabetical substitution table, with the columns of the table being # selected not by a user-given key as is done in classical cryptography but # by a dynamic value sigma that is dependent on all the preceding plaintext # and ciphertext characters that have been processed so far. (sigma is thus # a generalization of the classical autokey.) Each column thus selected has # a use-count increased by 1 and the alphabet in the column is renewed when # the use-count reaches a user-given maximum value. (The use-count of a # column further influences the result of substitution via in effect a # rotation of the alphabet in the column by that amount. cf. the columns of # a Vigenere substitution table.) Hence our substitution table as a whole # is also dynamic, i.e. dependent on the actual data being processed. This # dynamics of substitution processing not only greatly enhances the # complexity of cryptanalysis facing the adversary but also results in the # property of high error propagation in case any plaintext or ciphertext # character is modified, thus enabling the realization of authentication # (integrity check), a feature absent in classical cryptography. See # substitution(). # The above is done in each round (with different secondary seeds for getting # the PRNs needed in the different rounds). The round number can be arbitrarily # chosen. For our targeted users, the common people with their fairly limited # volume of message to be processed with any one given session key, employing # one round is amply sufficient in the present author's opinion. Measurement # showed that, with the parameter values chosen the same as in the illustrative # example further below, the encryption processing time on a common PC for a # message of 10000 characters is about 0.2 sec. # It may be remarked that, of a number of symmetric encryption schemes designed # by the present author till the present, the present one is the most # straightforward and simple one in programming logic, since it fairly closely # follows the popularly known principles of classical cryptography, though # on the other hand highly exploits the advantages of processing with computers # to achieve the benefits of dynamics as mentioned above. # Version 1.0, released on 03.08.2015. # Code lines of documents with the same version number are always identical. # There may be interim modifications of comment lines. # 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. # A list of present author's software that are currently directly maintained by # himself is available at http://mok-kong-shen.de. Users are advised to # download such software from that home page only. # The author is indebted to TPS for review and suggestions throughout # BASICS' development phase. Any remaining deficiencies of the software # are however the sole responsibilty of the author. # Constructive critiques, comments and suggestions of extensions and # improvements are sincerely solicited. Address of the author: # # Email: mok-kong.shen@t-online.de # # Mail: Mok-Kong Shen, Postfach 340238, Munich 80099, Germany # # (Sender data optional, if no reply required.) ################################################################################ import random # Compute from sessionkeyextension an integer v and concatenate it to secretkey # to form sessionkey. See Epilogue. def formsessionkey(): global secretkey,sessionkeyextension global sessionkey assert type(secretkey)==type(0) and type(sessionkeyextension)==type("a") by=bytearray(sessionkeyextension,'latin-1') lby=len(by) assert lby > 0 v=0 for i in range(lby): v<<=8 v|=by[i] sessionkey=(secretkey<<(lby*8))|v return # Initialization, computing the authenstring for authentication and the needed # secondary seeds in the different rounds of processing. Invoked in # basicsencrypt() and basicsdecrypt(). def initbasics(): global sessionkey,lenauthenstring,roundnumber global authenstring,seeds global alpha,lenalpha,usecountmax,sigma assert lenauthenstring > 0 and roundnumber > 0 and usecountmax > 0 lenalpha=len(alpha) # Check that the characters in alpha are unique. for h in alpha: assert alpha.count(h)==1 # Seed Python's built-in PRNG with the sessionkey. formsessionkey() random.seed(sessionkey) # Compute authenstring. authenstring="" for i in range(lenauthenstring): authenstring+=random.choice(alpha) # We choose to employ 128-bit secondary seeds. seedsb=128 seeds=[random.getrandbits(seedsb) for i in range(roundnumber*2+1)] return # Pseudo-random permutation of the characters in the global variable glist. # kn=1: encryption. # kn=2: decryption. def permutation(seed,kn): assert kn in [1,2] global glist random.seed(seed) lenlist=len(glist) if kn==1: random.shuffle(glist) else: permseq=[i for i in range(lenlist)] random.shuffle(permseq) hlist=["" for i in range(lenlist)] for i in range(lenlist): hlist[permseq[i]]=glist[i] glist=hlist return # A dynamic polyalphabetical substitution of the characters in the global # variable glist. A dynamic (i.e. dependent on the actual state of encryption # processing) pseudo-random value sigma is used to select the column of the # substitution table subtab for use to process a given plaintext character. See # also Prologue. # kn=1: encryption. # kn=2: decryption. def substitution(seed,kn): global sessionkey,lenauthenstring,roundnumber global alpha,lenalpha,usecountmax,sigma global subtab,usecount global glist assert kn in [1,2] # Seed Python's built-in PRNG with the secondary seed seed given as parameter. random.seed(seed) # Compute the initial pseudo-random polyalphabetical substitution table subtab. # subtab has lenalpha columns. Its k-th column is subtab[k]. # Initialize a vector subvec with the characters of the alphabet. subvec=list(alpha) # subtab is initially empty. subtab=[] for j in range(lenalpha): # Pseudo-randomly shuffle subvec. random.shuffle(subvec) # Let the result be a new column of subtab. subtab.append(subvec[:]) # Counts of usage of the individual columns of the substitution table. usecount=[0 for j in range(lenalpha)] # Count of total characters processed sofar. chrcount=0 # Initialization of sigma to a pseudo-random value. sigma=random.randint(0,lenalpha-1) # Process glist to hlist. # Get the length of glist. lenlist=len(glist) # hlist is initially empty. hlist=[] for ii in range(lenlist): if kn==1: # Case of encryption. # Get a plaintext character p from glist. p=glist[ii] # Find the index of p in the alphabet alpha. pidx=alpha.index(p) # Note that usecount of the column selected by sigma influences the index to # obtain the ciphertext character (the alphabet in the column is in effect # rotated by the amount of usecount, which is increased by 1 after that column # is accessed). # Compute the index of the corresponding ciphertext character c in the column # subtab[sigma] of the substitution table with consideration of the usecount # there. cidx=(pidx+usecount[sigma])%lenalpha # Obtain the ciphertext character c. c=subtab[sigma][cidx] # Add c to hlist. hlist.append(c) else: # Case of decryption. c=glist[ii] cidx=subtab[sigma].index(c) pidx=(cidx-usecount[sigma])%lenalpha p=alpha[pidx] hlist.append(p) # Increase the usecount of the column. usecount[sigma]+=1 # When usecount of a column reaches usecountmax, the column is renewed. Thus # the entire substitution table is dynamically modified during processing. if usecount[sigma]>=usecountmax: random.shuffle(subvec) subtab[sigma]=subvec[:] usecount[sigma]=0 # Update sigma with certain (nonlinear) function values of p and c. We choose # to use the function subtab[hh].index(). (hh indexes each time a different # column of subtab, hence obtaining different functions.) Thus sigma is a # dynamic entity that depends on all the p and c so far being processed in a # highly complex way. chrcount+=1 hh=chrcount%lenalpha sigma=(sigma+subtab[hh].index(p)+subtab[hh].index(c))%lenalpha # The processing result is now in glist. glist=hlist return # Perform for each round a permutation and substitution of the characters in the # global variable glist. An additional permutation at the end renders the scheme # symmetrical. The result of processing is in glist. # kn=1: encryption. # kn=2: decryption. def encryptionprocessing(kn): global sessionkey,lenauthenstring,roundnumber global authenstring,seeds assert kn in [1,2] if kn==1: for round in range(roundnumber): sk=round*2 permutation(seeds[sk],kn) substitution(seeds[sk+1],kn) # A final additional permutation. sk=roundnumber*2 permutation(seeds[sk],kn) else: sk=roundnumber*2 permutation(seeds[sk],kn) for round in range(roundnumber-1,-1,-1): sk=round*2 substitution(seeds[sk+1],kn) permutation(seeds[sk],kn) return # Main encryption function. A warning is issued in case alpha contains space and # the ciphertext string obtained ends in spaces, so that no operator error could # occur on decryption because of that. def basicsencrypt(plaintextstring): global authenstring,seeds global alpha,lenalpha,usecountmax,sigma global glist # Check that plaintext string contains only characters in alpha. for p in plaintextstring: assert p in alpha # Initialization. initbasics() # Add the authentication string to the given plaintext string. plaintextstring+=authenstring # Obtain from it a list of characters and store it into the global variable # glist. glist=list(plaintextstring) # Perform encryption processing of the characters in glist. encryptionprocessing(1) # Transform the list of characters glist into a character string # ciphertextstring. ciphertextstring="".join(glist) # Issue a warning to the user, in case ciphertextstring ends in spaces. if ' ' in alpha: cc=0 for i in range(len(ciphertextstring)-1,-1,-1): if ciphertextstring[i]!=' ': break cc+=1 if cc>0: print("Warning: ciphertextstring has",cc,"spaces at its end which must "\ "not be ignored on decryption *********") return(ciphertextstring) # Main decryption function. def basicsdecrypt(ciphertextstring): global sessionkey,lenauthenstring,roundnumber global authenstring,seeds global glist initbasics() glist=list(ciphertextstring) encryptionprocessing(2) plaintextstring="".join(glist) # The current plaintextstring has at its end a section corresponding to the # authenstring generated by the sender. authenstringcheck=plaintextstring[-lenauthenstring:] # Check that the two are identical. if authenstringcheck!=authenstring: print("Authentication (integrity check) failed *********") exit(111) # Drop the authenstring. plaintextstring=plaintextstring[:-lenauthenstring] return(plaintextstring) # Read a text file, return a textstring. def readtextfile(textfilename): fp=open(textfilename+".txt","r") textstring=fp.read() fp.close() return(textstring) # Write a textstring to a text file. def writetextfile(textstring,textfilename): fp=open(textfilename+".txt","w") fp.write(textstring) fp.close() return ################################################################################ # Installation of the software. # Both communication partners have to download the same version 3x of Python # from http://www.python.org. (Employing the same version of Python ensures # against any potentially possible incompatibilities among different versions.) # The present code can be stored in a file named e.g. basics.py and the # example given further below run in Python's GUI IDLE. (File --> Open to find # and open the file, then in the window showing the code Run --> Run Module to # run it. One could also type basics.py in a DOS-window.) Modifications # of the code in the code window, e.g. the plaintext string, can be done online # and the code re-run. ################################################################################ # Illustrative example. # System parameters agreed upon by the communication partners of our example: # Parameters for forming a session-dependent seed for Python's built-in PRNG. # secretkey is an integer in hexadecimal or decimal format, sessionkeyextension # is a text string. See Epilogue. secretkey=0x4a98717c70e997c2715e87c3fa1ef559 sessionkeyextension="JYN 03.08.2015 TP236" # Length of authenstring for authentication (integrity check). lenauthenstring # must be > 0, should not be too small. lenauthenstring=20 # Number of rounds of encryption processing, see basicsencrypt(), must be > 0, # see also Prologue. roundnumber=1 # When a column of the substitution table has been used usecountmax times, it # will be renewed. usecountmax must be > 0. Small values are to be preferred in # order to achieve good dynamics in encryption processing. usecountmax=5 # Alphabet of characters employed in processing. alpha can be an arbitrarily # larger set of characters than those actually occur in the given plaintext and # determines the characters occurring in the ciphertext. alpha="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ.,; ?+-*/_!&" # Sender side specific coding. plaintextstring=\ "Das hoechste Glueck ist immer das, welches unsere Maengel verbessert und "\ "unsere Fehler ausgleicht. -- J. W. von Goethe" ciphertextstring=basicsencrypt(plaintextstring) # We assume that the sender desires to examine the ciphertext string. print("ciphertextstring:") print() print(ciphertextstring) print() # Write ciphertextstring to a file for sending to the receiver. writetextfile(ciphertextstring,"ciphertext") # Receiver side specific coding. ciphertextstring1=readtextfile("ciphertext") plaintextstring1=basicsdecrypt(ciphertextstring1) print("Message received:") print() print(plaintextstring1) print() print() # The following lines serve to check whether our code has indeed correctly # functioned. print("Sender's message is correctly obtained by the receiver:", plaintextstring==plaintextstring1) print() print() ################################################################################ # Appendix. # Users who are new to Python or who begin to use a new version of the Python # software may like to know a bit about the statistical qualities of its # built-in PRNG which is employed in BASICS. The following code is intended to # serve for that purpose. prnbitn is the number of bits of the PRNs to be # generated and must be a multiple of 8. testseed is any arbitrary seed chosen # for running the test. One may like to try a number of different prnbitn and # testseed. import math,random # Maurer's Universal Test, see [1]. # [1] J-S. Coron, D. Naccache, An Accurate Evaluation of Maurer's Universal Test. # http://www.jscoron.fr/publications/universal.pdf qq=2560 qqp1=qq+1 kk=256000 qqkkp1=qq+kk+1 def maurertest(bb): global qq,qqp1,kk,qqkkp1 eftu=7.1836656 # y1 and y2 are for rho=0.01 and rho=0.001 respectively. y1=2.5758 y2=3.2905 t=[0 for i in range(256)] for i in range(1,qqp1,1): t[bb[i]]=i sum=0.0 for i in range(qqp1,qqkkp1,1): sum+=math.log10(i-t[bb[i]]) t[bb[i]]=i tu=(sum/kk)/math.log10(2.0) c=math.sqrt(0.3732189+(0.3730195*256)/kk) sigma=c*math.sqrt(3.2386622/kk) t11=eftu-y1*sigma t12=eftu+y1*sigma t21=eftu-y2*sigma t22=eftu+y2*sigma return(tu,t11,t12,t21,t22) def maurertestresult(h,gg): global chnum global qq,qqp1,kk,qqkkp1 if h*chnum < qqkkp1: print("Error in maurertestresult") exit(6) bb=[0 for k in range(h*chnum)] u=0 k1=-1 k2=chnum-1 for i in range(h): g=gg[i] for k in range(k2,k1,-1): bb[u]=g&0xff g>>=8 u+=1 k1+=chnum k2+=chnum tu,t11,t12,t21,t22 = maurertest(bb) return(round(tu,4)) def randtest(prnbitn,testseed): global chnum if prnbitn<8 or (prnbitn%8)!=0: print("Error randtext: Wrong prnbitn") exit(55555) chnum=prnbitn//8 h=qqkkp1//chnum if h*chnum < qqkkp1: h+=1 random.seed(testseed) tpwbitnm1=2**prnbitn-1 print("PRNs generated with random.randint():") gg=[random.randint(0,tpwbitnm1) for i in range(h)] tu=maurertestresult(h,gg) print("Test statistics:",tu) print("PRNs generated with random.getrandbits():") gg=[random.getrandbits(prnbitn) for i in range(h)] tu=maurertestresult(h,gg) print("Test statistics:",tu) return # User chosen test parameters: prnbitn=128 testseed="My arbitrarily chosen seed" print("Test of Python's PRNG, parameters used:") print("prnbitn:",prnbitn) print("testseed:",testseed) print("Results should lie in [7.1781, 7.1893]") randtest(prnbitn,testseed) ################################################################################ # Epilogue. # We presume that the computer, on which this software is run, is free from # malware infection via software and/or hardware means and that there are no # emission security risks. # In the way personally preferred by the present author, the parameter # "sessionkey" employed to seed Python's PRNG at initialization time consists of # two components: "secretkey", which should have sufficient entropy, e.g. # stemming from dice throws, and which could be used for a certain longer time # period before being renewed, and "sessionkeyextension", which is dynamic, i.e. # different for different sessions and which need not be secret (since it is its # variability that is important in the present context), being composed of # certain variable session-dependent data, e.g. date, time, subject, message # serial number, etc. In case there is no systematic scheme of derivation of # "sessionkeyextension" to be used by the receiver, it can be sent in the clear # to him. In view of the high dynamics of our sessionkey and the comparatively # low volumes of communications of our targeted users, our use of Python's # built-in PRNG is obviously entirely secure in practice. For a utility to # convert dice throws to a hexadecimal sequence, see DICE. # In general it is advantageous for the present scheme to limit the character # set of plaintexts to a small value, e.g. 26 for lower case, while on the other # hand employing an alpha (which determines the number of different characters # occurring in the ciphertext) that is sufficiently large yet without causing # inconvenience or errors for the transmission channel employed, e.g. being # printable and easily recognizable. # It may be remarked that certain functions of Python's random module could be # simply simulated with any PRNG that delivers a byte stream. See PERMPOLYPRNG. # Users who have also interest in public key cryptography may note that the # present author has a Python code of RSA key generation and encryption in his # software PROVABLEPRIME, which contains some comments of general interet.