BASICS

Return to main page




# 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.



Return to main page