CSC 15 Lab 8 : File Descrambling


 --------------------------- Part I: -----------------------------

      The purpose of the first part of the assignment is to descramble
a file that has been posted on the homepage along with its encryption
key.  The encryption key is in the form of a permutation.  For
example, if the first (0th) number of permutation is 45, then the
first letter of the original file is stored as the 46th letter in the
scrambled file.  If the file is longer than the permutation, then the
file is scrambled in segments, each segment is equal to the size of
the permutation.

You are to write a function 

descramble(scrambledfile,keyfile)

That reads the scrambled file into a string, desramble the string using the
key, then write the descrambled file to a new file, something with a
".descrambled" suffix

Here's some code you can use in your program:

------------
# reads permutation from file, returns array representation
def readkey(fname):
	P = []
	fd = open(fname,"r")   # opens file for reading
	S = "dfs"  # some non-empty string
	while S!= "":    # S will be "" at end of file
		S = fd.readline()  # read one line
		if S!="": P.append( int(S) )
	# ends while loop
	fd.close()
	return P  # returns array representing a permutation
# readkey

#### Here are some other functions you may need:

# Function to convert between strings and arrays of chars
# For example, stringtoarray("abc") returns ["a","b","c"]
# and arraytostring(["a","b","c"]) returns "abc"
def stringtoarray(S):
 	A = []
	i = 0
	while i<len(S):
		A.append(S[i])
		i += 1
	return A

def arraytostring(A):
	S = ""
	for c in A:  # "for each element/value c in array A"
		S = S+c
	return S
#arraytostring

# read string from entire file:
def readfile(filename):
    fd = open(filename,"r");
    F = fd.read();   # reads entire file into a string
    fd.close()
    return F   # returns string
#readfile

# write string S to (string) file
def writefile(S,filename):
    fd = open(filename,"w")
    fd.write(S)
    fd.close()  # nothing is returned: calls to writefile are statements
#writefile


####### The following functions are provided as hints, but you do not
# need to use them in your program.------------

# function to generate random permutation of size n:
def randperm(n):
    A = range(0,n)
#    i = 0
#    while i<n:
#        A.append(i)
#        i += 1

    # randomly swap:
    i = 0
    while i<len(A):
        j = randint(0,len(A)-1)
        A[i],A[j] = A[j],A[i]
        i += 1
    # while
    return A
# randperm

#### The following function scrambles a string using permutation P,
#### padding S to be of the right size. Do not copy it directly!  Think
#### carefully about how your program will differ.

def scramble(S, P):  #Scramble string S with permutation P
    pn = len(P)  # length of permutation array
    E = (len(S) + pn - (len(S)%pn)) * [' ']  # array of chars, padded 
    i = 0
    while i< len(S):
        seg = i/pn   # segment number
        j = i % pn   # segment offset
        E[ seg*pn + P[j] ] = S[i]
        i += 1
    # while
    return arraytostring(E)
# scramble


You should write one function to descramble a string, then ANOTHER function
to descramble an entire file (keep io separate from computation).
You should first test your descrambling function on the following encrypted
message:

"'amhshonrO eikp aatrmmiececom' w e mlnliledtsl: nduaytiae ltoetrwto  siwde no  he n snomtniuchomht gm liwsgrbelroeiap r .     ze   ai vdo rp"

which was encrypted with the permutation key 

[9, 14, 11, 19, 16, 18, 12, 6, 7, 15, 0, 5, 17, 4, 3, 10, 2, 1, 8, 13]

After you've descrambled the message, you may find some junk characters
at the end of the descrambled form.  This is to be expected, because the
array representation is padded to be divisible by the size of the permutation.


----------------------------- Part II ------------------------------

In the second part of the assignment, we will strengthen our scrambling
algorithm.  All we've done is swap the letters around in a message.
But the characters themselves are not scrambled: a 'B' in the original
message is still a 'B' in the encrypted form, just in a different position.
Now we shall map each character to a different one: for example, a 'B'
may occur as a '&' instead.  This will make the encryption harder to break.

You'll find the code to generate random permutations on the homepage.
lettermap = randperm(128) # will generate such a permutation.

Now given a character C, to encrypt it as another letter we need to

1. convert it to its ascii value:

   oc = ord(C)

2. Access the permutation array to get the encrypted code for C:

   code = lettermap[oc]

3. convert the ascii code to a char:

   cc = chr(code)

----

To descramble a character, you can use the same algorithm, except you
need the inverse permutation:

# Construct inverse permutation Q from P: if P[i]==j, then Q[j]==i
def invert(P):
    n = len(P)
    Q=n*[0] # make sure Q (return value) is of the right size first
    i = 0
    while i<n:
        Q[ P[i] ] = i
        i +=1
    return Q
# invert

We will combine the character map scramble with our original
algorithm. Each character will be mapped to a different character AND
stored in a different position in the string.  The new encryption
"key" will therefore consist of TWO permutations.  You need to now
rewrite all the functions to both scramble and descramble files.  Each
file containing a key will now begin with exactly 128 lines of numbers
representing the character map permutation, followed by the lines
representing the positional permutation.  


You can read in a permutation file and convert it to a string using
the following function:

def readperm(keyfile): # reads permutation from file, returns array
   fd = open(keyfile,"r");   
    Perm = []
    I = "blah"  # some non-empty string
    while I!="":
        I = fd.readline()  # read in one line as a string
        if I!="": Perm.append( int(I) )
    fd.close();
    return Perm
#readperm

For example, if a file name "myperm.txt" contains the following lines:
0
2
3
1

Then calling readperm("myperm.txt") will return the array [0,2,3,1]


Find another person in the class to test your programs against: give
the other person a scrambled file and a key, and have them descramble
it.