Monday, December 11, 2017

#1 2004-02-15 11:36:18 pm

Scott Lewis
Member
From:: Richmond, VA
Registered: 2003-06-10
Posts: 58
Website

Encrypting Messages (Pt 3)

To this point, we have established a solid foundation for our encryption method. We know how to convert our characters to their numerical equivalents, use a multiplier to find a substitution character and how to find the key and convert the encrypted character back again. Everything we will do from here out will build on what we've covered so far.

As I mentioned at the end of Part 2, we are going to break our text into larger blocks and encrypt multiple characters in a single pass. The first question that we have to answer is "How do we find a numerical value for two or more characters at once?". The answer, as you will shortly see, is quite simple. We create an array, or a virtual one at least, of all the possible character combinations using the 256 ASCII characters. As was previously stated, as the block length grows, the number of possible combinations increases exponentially. However, we will not need to actually create the array. I will show you how to have AppleScript do the math to find the location that the character combo in question "would" occupy in such an array.

To illustrate how this works let's take the word "cat" and figure out the numerical value for each letter. Previously we had been referring to a letter's numerical value as its position in the alphabet. We are now going to incorporate the entire set of ASCII characters from 1 to 255. We will eleminate ASCII character 0 because it is an empty string, which in our encryption routine will never be evaluated.

So our example "cat" breaks down to 99-97-116 because c = ASCII number 99, a = 97, and t = 116. But these numbers don't really help us much because looking at the first few combinations within our array we find "aaa", "aab", "aac", "aad" and so on. So we need a formula that tells us how far in the array we have to go until the first letter of the block is "c".  As we move forward through our array we notice that the first letter is changing very slowly, while the second letter is changing more quickly and the third letter more quickly still. Sort of the way the second hand, minute hand and hour hand work on a clock. We can define this rate of change very easily: for every 255 times the third character changes, the second character changes once, and for every 255 times the second character changes, the first character changes once. Writing this as a mathematical formula we get (char1 * (255^2)) + (char2 * (255)) + char3. Now our numberical values for "cat", 99-97-116 have a place to be useful. Plugging them into our equation we get (99 * (255^2)) + (97 * 255) + 116. Using this formula we get a numerical value for "cat" of 2074. This means that the offset of "cat" in our array of all possible 3-letter combinations of the alphabet is 6462326.

Before we write the routine for converting text to numbers, it will need a little explanation. The first thing we need to define is the size of the set of available characters. In this case it is 255 because we will be using the ASCII characters from 1 to 255. The next item that needs explanation is the variable "theExp". Remember that we said in order to get the first and second characters in "cat" to change from "a" to "b", we have to go through the entire set of 255 characters. This works very much the same way that the second hand has to go around the clock face one entire rotation before the minute hand moves and the same holds true that in order for the hour hand to move once, the minute hand must go around the clock face once and the second hand 60 times. This could be defined as 3 hours 3 mins 3 seconds = (3 * 60^2) + (3 * 60) + 3. The exponent for the first character will be 1 less than the length of our text block, for the second character it wil be 2 less than the length of the text block and so on. The value of the last character will always be added to the value of the block.

So here is the routine:

<span id="subheadtext">Converting Text to numerical values</span>

Applescript:


on convertToNum(textBlock, setSize)
   set theExp to ((length of textBlock) - 1)
   set pVal to 0
   repeat with i from 1 to ((length of textBlock) - 1)
       set pVal to pVal + ((ASCII number ((character i of textBlock) as string)) * (setSize ^ theExp))
       set theExp to theExp - 1
   end repeat
   set pVal to pVal + (ASCII number ((character (length of textBlock) of textBlock) as string))
   return pVal
end convertToNum

Now that we have the numerical value of our plaintext "cat" we can use the routine for encrypting that we created in part 2. But before we do, let's modify the routine a bit to allow for a "shift" of the characters, just for fun or to complicate things, however you choose to look at it.

Our routine was:

<span id="subheadtext">Encipher Text</span>

Applescript:


on encipherText(p, m, n)
   set c to (p * m) mod n
   return c
end encipherText

Now let's make it look like this:

<span id="subheadtext">The new cipher routine</span>

Applescript:


on cipher(m, s, n, p)
   return (((m * p) + s) mod n)
end cipher

If you recall, I said that you could use the same routine to perform double-duty because the same formula, using inverse values for m and s, will both encipher and decipher our text. And that is what we have done with our routine called "cipher(m,s,n,p)" where m=multiplier, s=shift, n=modulus, and p=text.

We are now only one step away from having a fully functioning encryption system, albeit a rather un-secure one. The only piece we are lacking is some way to convert the numerical values back into text. This works essentially the exact opposite as our routine for converting to numbers. Again, however, we will need to explain a couple of the pieces and procedures. Looking at the code below you will see the familiar "theExp" variable. In this routine it works the same as in the routine for converting to numbers but we will use it slightly differently. You might also recognize the "setSize" variable, which again, tells the routine the size of the character set with which we are working. There is a new variable however, "b", that is used to tell the "convertToText" routine what size our text blocks are.

You will notice that we are using a new operator as well, "div". In case you aren't familiar with div, it is, in essence, the opposite of the modulus. While the modulus tells us what's left over, without regard to how many times a number divides another, div tells us how many times a number divides another without regard to what is left over. The way it is working in our routine is that since we have the numerical value of a block of three characters, in order to find the text equivalent of the first and second characters, we need to figure out how many times we had to travel through the entire set of characters to get the numerical value. It performs the inverse function of multiplying the numerical value by the size of the set to the power of the exponent or (char1 * (setSize^theExp)). Once we have determined the starting point for character 1, we can subtract its value from the overall value of the block, leaving blockValue - (char1 * (setSize^theExp)), and proceed to the next character. We only need perform this process on the overall block value up to the next to the last character. We determine the value of the last character by adding what is left over because if we have done our math correctly and written all of the script steps correctly, what is left over should not only be less than the set size but should also be the ASCII number corresponding to the text character.

<span id="subheadtext">Converting numerical values to text</span>

Applescript:


on convertToText(pVal, b, setSize)
   set theExp to (b - 1)
   set pValList to {}
   repeat with i from 1 to (b - 1)
       set thisVal to (pVal div (setSize ^ theExp))
       set pVal to pVal - (thisVal * (setSize ^ theExp))
       set the end of pValList to thisVal
       set theExp to (theExp - 1)
   end repeat
   set the end of pValList to pVal
   repeat with j from 1 to (count items of pValList)
       set item j of pValList to (ASCII character (item j of pValList))
   end repeat
   return ((items of pValList) as string)
end convertToText

All that is left is the simple matter of breaking long blocks of text into three character blocks, or trigraphs. This can be achieved with a simple repeat loop as shown below. I won't go into explanation as it is pretty self-explanatory. One thing I will point out however, is that the length of each block MUST be 3 characters (or whatever block size you choose to use). To do this, simply have the routine check to see if the length of the entire message modulo 3 is 0, meaning that 3 divides into the length of the text an even number of times. If it does not have it add a random character to the end of the message by having the computer pick a random number between 1 and 255 and adding its ASCII equivalent to the end of the message text.

<span id="subheadtext">Breaking the text string into blocks</span>

Applescript:


on makeBlocks(theText, b)
   repeat until ((length of theText) mod b) = 0
       set theText to (theText & (ASCII character (random number from 1 to 255)) as string)
   end repeat
   set myList to {}
   repeat with i from 1 to (length of theText) by b
       set the end of myList to ((characters i thru (i + (b - 1)) of theText) as string)
   end repeat
   return myList
end makeBlocks

There is only one last topic to discuss before I give you the entire script put together. This method, in order to accurately encipher and decipher text, depends entirely on choosing two numbers that are relatively prime to one another. In case you have forgotten, I will define it again. Two numbers are relatively prime when the only factor they have in common is 1. The routine for calculating multiplicative inverses was given in Part 1 of this series but keep in mind that since it is trying every number, it can take a very, very long time if you are working with very large numbers. Also keep in mind that any number larger than the modulus need not be tried because when that number is lowered by the modulus it will correspond to some number smaller than the modulus. I would highly recommend using small numbers of 3 to 5 digits.

<span id="subheadtext">And here's the entire script:</span>

Applescript:


set pText to "The Eagle Has Landed"

global b, setSize

set b to 3
set setSize to 255
set m to 481
set s to 580

set pList to makeBlocks(pText, 3)

return main(pList)

on main(bList)
   set cText to ""
   repeat with i from 1 to (length of bList)
       set pText to item i of bList
       set pNum to convertToNum(pText, setSize)
       set cNum to cipher(m, s, setSize ^ b, pNum)
       set cText to cText & convertToText(cNum, b, setSize)
   end repeat
   return cText
end main

on cipher(m, s, n, p)
   return (((m * p) + s) mod n)
end cipher

on convertToText(pVal, b, setSize)
   set theExp to (b - 1)
   set pValList to {}
   repeat with i from 1 to (b - 1)
       set thisVal to (pVal div (setSize ^ theExp))
       set pVal to pVal - (thisVal * (setSize ^ theExp))
       set the end of pValList to thisVal
       set theExp to (theExp - 1)
   end repeat
   set the end of pValList to pVal
   repeat with j from 1 to (count items of pValList)
       set item j of pValList to (ASCII character (item j of pValList))
   end repeat
   return ((items of pValList) as string)
end convertToText

on makeBlocks(theText, b)
   repeat until ((length of theText) mod b) = 0
       set theText to (theText & (ASCII character (random number from 1 to 255)) as string)
   end repeat
   set myList to {}
   repeat with i from 1 to (length of theText) by b
       set the end of myList to ((characters i thru (i + (b - 1)) of theText) as string)
   end repeat
   return myList
end makeBlocks

on convertToNum(textBlock, setSize)
   set theExp to ((length of textBlock) - 1)
   set pVal to 0
   repeat with i from 1 to ((length of textBlock) - 1)
       set pVal to pVal + ((ASCII number ((character i of textBlock) as string)) * (setSize ^ theExp))
       set theExp to theExp - 1
   end repeat
   set pVal to pVal + (ASCII number ((character (length of textBlock) of textBlock) as string))
   return pVal
end convertToNum

I will leave it up to you to test the script but I will help you out by giving you the first set of keys. Typically the encryption keys are noted as Ke=(m,s), and the decryption keys ad Kd=(m,s). So to start you off, Ke=(487, 580); and Kd=(34048, 13414910).

I hope that this series has been, at the very minimum, entertaining and educational even if AppleScript is not ideally suited for truly secure encryption. Even though this method is not secure enough to send credit card or other highly sensitive information, you may find that you can put it to good use. If you do come up with some good ways to use this code or if you know more than this novice cryptographer please drop me a line and share your thoughts and/or insight. I make no claims to being an expert, just a hobbyist so I am always interested in learning from those with more experience.

And finally, I must eat some crow here. I said at the end of Part 2 that I would introduce you to the RSA Encryption Method and that it could be done on a small scale with AppleScript. But I won't and it can't. Why? You may well ask. Well, it seems that when I actually sat down and started trying to write some AppleScript to do this, it could not be done. Even using prime numbers of only two digits, the numbers got so big that the sytem could not handle them and returned only errors telling me that the result of the operation was too large. If you are interested in seeing the code, I will be happy to email it on a request basis, or if the demand is great enough I will be happy to do a "theoretical" piece on it.


A reasonable man adapts himself to the world he sees. An unreasonable man tries to adapt the world he sees to himself.  Therefore, all advancement in society is achieved by unreasonable men. --Paraphrase of a quote by George Bernard Shaw


Filed under: Encryption, Lewis

Offline

 

Board footer

Powered by FluxBB

RSS (new topics) RSS (active topics)