home *** CD-ROM | disk | FTP | other *** search
/ Esprit de Apple Corps / EDAC-2.iso / Graphics / Bulla.Disk / LOD3.6.DOC < prev    next >
Text File  |  1990-05-18  |  30KB  |  652 lines

  1. The LOD/H Technical Journal, Issue #3: File 06 of 11
  2.  
  3.               |||||||||||||||||||||||||||||||||||||||||||||||||||
  4. +-+-+-+-+-+-+/                                                   \+-+-+-+-+-+-+
  5.  \  L  \        Secure Data Encryption with Cellular Automatons        /  L  /
  6.    \  O  \                                                           /  O  /
  7.      \  D  \                          by                           /  D  /
  8.        +-+-+-+                                                   +-+-+-+
  9.          \  L  \                  The Mentor                   /  L  /
  10.            \  O  \                                           /  O  /
  11.              \  H  \    A Legion of Doom Presentation!     /  H  /            
  12.  
  13.                +-+-+-+                                   +-+-+-+
  14.                 \_\_\_\_________________________________/_/_/_/
  15.  
  16.  
  17.      One of the key issues that concerns anyone who has sensitive or illegal
  18. information on their computer system is preventing unauthorized access to this
  19. information.  Even if you hit a key that deletes everything on the hard disk
  20. when you see that four-door sedan pull up in the driveway, any idiot with
  21. Norton's Utilities (IBM) or Copy II+ (Apple) can recover anything that's on
  22. your drive with minimal effort.  A delete command only changes a flag in the
  23. VTOC (volume table of contents), it doesn't actually *remove* the file from
  24. your system.
  25.      There are two methods to ensure that your data can't be read by a sector
  26. editor or recovered by NU.  The first is to overwrite everything with a NULL
  27. (FF) or anything else for that matter.  I've seen one batch file that does a
  28. global delete, creates a file that says 'EAT HOT DEATH', and then begins
  29. copying it until disk space is full.  Unfortunately, you can't always guarantee
  30. that you will be able to get to your computer before someone else does.
  31.       The second method is to encrypt your data.  Most people have visions of
  32. data encryption being some sort of arcane process akin to summoning demons or
  33. talking with Dead Cow Cult members (two closely related process- es.)  In
  34. practice, it isn't that difficult.  This file is intended to show some very
  35. short programs that will encrypt data beyond the ability of any- thing short of
  36. a dedicated mainframe to crack. 
  37.  
  38.      How to use:  The code examples I provide will be in MicroSoft's
  39. AmigaBASIC.  It is fairly generic and you should be able to convert it over to
  40. IBM, //e,c,gs, Mac, ST, C64, or any flavor of mainframe you like.  For those of
  41. you setting up systems on Packet-Switched Networks (such as the LOD/H system
  42. one of our members is implementing) data encryption should be considered
  43. absolutely necessary to maintain security.
  44.       The terseness of the routines make them easy to insert in a bulletin
  45. board also, although conversion into C or Assembly would be necessary for
  46. decent speed.
  47.  
  48.       Intro to Cryptography:  Long before computers were around, there was a
  49. need for data security.  Everyone used lemon juice as 'invisible ink' when they
  50. were a kid, heating it over a candle to bring it out.  And everyone has seen
  51. the substitution code where "A" = 1, B = "2", "Z" = 26, etc... 
  52.       The easiest form of encryption involves a variation of the previous. 
  53. First of all, don't think of A = 1 as a substitution, think of it as a
  54. remapping.  Let's say we have a language made up of the five vowels, and we
  55. wanted to remap them to the numbers 1-5.  Our map would look like this:
  56. "AEIOU12345" and our mapping function would be f(c) = POSITION(c) + x where c =
  57. the letter to map and x is the key (in this case 5.)  So every time we needed
  58. to encrypt a letter, we would take its position in the map, add 5 to it, and
  59. come up with the character to substitute.  For the entire alphabet, the mapping
  60. function would be f(c) = POS(c) + 26 for the map "A..Z,1..26".
  61.        Your map should be composed of all the characters that will be used for
  62. encryption.  In a text only encrypter, this will consist of all the printable
  63. characters your machine can use.  The same method can be used to encrypt binary
  64. files, but it's not as clear as text only for a teaching example.
  65.        The problem with this simple form of encryption is that your average C64
  66. could crack it in a matter of minutes.  Enter into the next level of
  67. cryptography, random numbers.
  68.        During World War II the Allied Forces created a system to generate
  69. random electric noise, recorded this noise onto a wax cylinder, and scram- bled
  70. radio transmissions by mixing the seemingly random noise with the voice
  71. transmission.  The soldiers in the field needed an imprint of the same cylinder
  72. to be able to understand the message.  Think of the wax cy- linder as a
  73. 'filter' for the crypted message.
  74.        A random number generator can be easily used to encrypt data providing
  75. you realize the following-  a random number generator on a computer is not
  76. really random.  If you initialize the generator with the same seed value on two
  77. seperate occasions, it will return the same sequence of psuedo- random
  78. numbers.  Most BASIC's use the RANDOMIZE <seed> command to start the generator
  79. off.  If you leave off the seed, they get a seed from the system clock or some
  80. other fairly random source, providing a much truer random selection.  But by
  81. declaring the seed yourself, you can be sure that you will be able to reference
  82. this same string of numbers, a string that is very hard to figure out without
  83. the key (seed.) 
  84.         Program Listing 1 is an example of a BASIC encrypt/decrypt system that
  85. uses the built-in random number generator include on the machine (or language
  86. implementation.)
  87.  
  88. Program Listing 1
  89. -----------------
  90.  
  91. REM ************************************************************************
  92. REM
  93. REM  Ok, this is an example of very basic encryption.  It takes the input
  94. REM  string and the input key and processes them using the machine's built
  95. REM  in random number generator.  This version is written in AmigaBASIC 1.2.
  96. REM  It can be compacted quite a bit by writting it in C, but it's an easy
  97. REM  algorithm to crack.
  98. REM
  99. REM ************************************************************************
  100.  
  101. INPUT "String to be encoded"; C$
  102. INPUT "Key Please! ";K
  103.  
  104.  
  105. REM ************************************************************************
  106. REM
  107. REM  When you use the RANDOMIZE command, it seeds the random number gener-
  108. REM  ator with the key K.  *EVERY* time you seed the generator with the same
  109. REM  value, you will get the same sequence of psuedo-random numbers.  Since
  110. REM  the built in random-number generator uses a linear algorithm to gener-
  111. REM  ate the sequence, it's easy (relatively) to crack.
  112. REM
  113. REM ************************************************************************
  114.  
  115. RANDOMIZE K
  116.  
  117. REM ************************************************************************
  118. REM
  119. REM  The only difference between encoding and decoding is which way you
  120. REM  move in your Q$ array space.  Encoding takes the original and shifts
  121. REM  to the right, decoding takes the codes value and shifts to the left.
  122. REM
  123. REM ************************************************************************
  124.  
  125. REREAD:
  126.   INPUT "Encode or Decode ? ";A$
  127.   A$=LEFT$(A$,1)
  128.   IF A$="E" OR A$="e" THEN
  129.     A=1
  130.     GOTO HEAD
  131.   END IF
  132.   IF A$="D" OR A$="d" THEN
  133.      A=-1
  134.   ELSE
  135.      GOTO REREAD
  136.   END IF
  137.  
  138. REM ************************************************************************
  139. REM
  140. REM  Q$ contains all the characters that can be encoded.  Every encoded
  141. REM  character will be mapped to a character in this array.  I haven't
  142. REM  included any non-standard characters, so you will have to customize
  143. REM  it to your particular keyboard/system.  I've included an error check
  144. REM  that will abort the encryption if it encounters a character that isn't
  145. REM  in Q$.  I have to use the STRING$ command to insert the spacebar and
  146. REM  the quote into the string.  It could also be done with a ASC(##) in
  147. REM  many basics.  You could expand this to include any non-printable
  148. REM  characters you'd like so you could do non-text files.
  149. REM
  150. REM ************************************************************************
  151.  
  152. HEAD:
  153.   SPACE = 32
  154.   QUOTE = 34
  155.   Q$="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
  156.   Q$=Q$+"1234567890!@#$%^&*()-=_+[]{};:'.,<>/?\|`~"
  157.   Q$=Q$+STRING$(1,SPACE)+STRING$(1,QUOTE)
  158.   QSIZ = LEN(Q$)
  159.  
  160. REM ************************************************************************
  161. REM
  162. REM  This is the main loop.  L = length of the string to encrypt.  In this
  163. REM  example, I am only encrypting a single string.  Most people who will
  164. REM  actually use this will change the FOR loop to run until an EOF is
  165. REM  encountered in the input file.  Since the syntax for that will vary
  166. REM  widely from system to system, I'll leave it out.
  167. REM
  168. REM ************************************************************************
  169.  
  170. L=LEN(C$)
  171. FOR I = 1 TO L
  172.  
  173. REM /* Finds the character I in the input string */
  174.   X$ = MID$(C$,I,1)
  175.  
  176. REM /* Finds the integer location of the character in Q$
  177. REM    returns variable POZ */ 
  178.   GOSUB LOKPOZ
  179.                                                                         
  180. REM /* RND returns a random # between 0 and 1.  Multiply it by the
  181. REM    size of array Q$ and you get the number of positions to move
  182. REM    when encoding or decoding. */
  183.   POZMV = (RND * QSIZ)
  184.  
  185. REM /* If you are encoding, you will shift to the right using addition.
  186. REM    you take the modula base QSIZ to keep the new character within
  187. REM    the bounds of Q$. */ 
  188.   IF A = 1 THEN
  189.     NUPOZ = (POZ + POZMV) MOD QSIZ
  190.   ELSE
  191. REM /* Otherwise, you subtract, which takes a bit more math to keep
  192. REM    up with.  Once you have the distance to shift, you must
  193. REM    convert it to a positive integer and then subtract two to
  194. REM    account for the head & tail of the array. */ 
  195.     NUPOZ = (POZ - POZMV) MOD QSIZ
  196.     NUPOZ = NUPOZ -2
  197.     IF NUPOZ < 1 THEN
  198.       NUPOZ = QSIZ - ABS(NUPOZ)
  199.     END IF
  200.   END IF
  201.  
  202. REM /* Now you assign the new character in array Q$ to Y$, and append
  203. REM    it to your converted string */ 
  204.   IF NUPOZ < 1 THEN
  205.     NUPOZ = QSIZ - ABS(NUPOZ)
  206.   END IF
  207.   Y$ = MID$(Q$,NUPOZ,1)
  208.   D$ = D$ + Y$
  209. NEXT I
  210.  
  211. PRINT  "Original = ";C$
  212. PRINT  "Modified = ";D$
  213. END
  214.  
  215. REM /* This finds character X$ in array Q$ and returns an integer
  216. REM    value of the location.  Called from the main loop. */
  217. LOKPOZ:
  218.   FOUND = 0
  219.   POZ = 1
  220.   TOP:
  221.     IF FOUND = 1 THEN
  222.       RETURN
  223.     ELSE
  224.       TMP$ = MID$(Q$,POZ,1)
  225.       IF X$ = TMP$ THEN
  226.         FOUND = 1
  227.       END IF
  228.       POZ = POZ + 1
  229.       IF POZ > QSIZ THEN
  230.         PRINT  "Error: Character '";X$"' not in array Q."
  231.         END
  232.       END IF
  233.     END IF
  234.   GOTO TOP       
  235.  
  236. REM **********************************************************************
  237.  
  238. End of Program Listing 1
  239.  
  240.         This method, while extremely simple, tight, and fast, is not fool-
  241. proof.  Most computers use the following algorithm for generating pseudo-
  242. random number sequences: x(t+1) = ax(t) + b
  243.         x(t+1) = next random number
  244.         x(t) = previous random number
  245.         a & b are constants that will cause a fairly even distribution
  246.  
  247.         For example, if you were using a three-bit system (8 possible postive
  248. integers) you might make a = 3 & b = 7 (there's a reason behind using prime
  249. numbers that is beyond the scope of this file.)  If you seed the argument with
  250. RANDOMIZE 5 you would get the following:
  251. First x: x = 3*5 + 7 | Since we're restricting ourselves to three bits, and
  252.          22 won't fit in three bits, we'd need to perform a modula 8 on the
  253.          number. (Modulo divides x by eight and keeps the remainder as the
  254.          new value of x.)  So  MOD(22,8) is equal to 6 (16 + 6 = 22).
  255.         
  256.          Ok, let's do some simple mapping using our vowel set and the above
  257. three-bit random number generator.  Let's say that the message reads "AAEOU"
  258. Our first random number was 6.  Our map looks like "AEIOU12345".  POS(A) + 6
  259. gives us 2 as the character. 
  260. Second x: x = 3*6 + 7 | MOD (25,8) = 1 | POS(A) + 1 gives us E.
  261. Third  x: x = 3*1 + 7 | MOD (10,8) = 2 | POS(E) + 2 gives us O.
  262. Fourth x: x = 3*2 + 7 | MOD (13,8) = 5 | POS(O) + 5 gives us 4.
  263. Fifth  x: x = 3*5 + 7 | MOD (22,8) = 6 | POS(U) + 6 wraps around the map to A.
  264.  
  265.          So our original "AAEOU" is crytped into "2E04A".  This may at first
  266. seem difficult to crack since 'A' mapped into a '2' on one pass and an 'E' on
  267. the other, thus preventing a freuquency analysis from breaking the code.
  268.         Unfortunately, if someone knows the random number algorithm, they can
  269. easily hack out the key.  Since most of the people using this will be using it
  270. on a pc, it would be trivial to get another pc to hack it out.  And even if you
  271. protect your random number algorithm, it is still a straight linear algebra
  272. problem that an AT could work on over a weekend and probably figure it out,
  273. especially if there is a fairly small map to work with.
  274.         
  275.           Solution: What we need to do is combine the random mapping with a
  276. random number generator that is tougher to figure out.  Enter cellular
  277. automatons.
  278.           CA's were first invented in the 1940's when John von Neumann (he of
  279. the famous bottleneck) started to explore the mathmatic implications of very
  280. simple machines.  CA's are made of geometric patterns of cells that change
  281. their state at each tick of a clock according to a fixed rule.  Early work
  282. provided automatons that could imitate a basic computer.  Since the CA's are
  283. inherently parallel (the entire geometry is updated each clock tick) and easy
  284. to put on a chip, there is speculation that the next generation of parallel
  285. processing computers will use CA's as a base rather than the Turing machine
  286. model.
  287.            You have probably seen a CA at work and not realized it if you've
  288. ever seen the computer graphic simulation 'LIFE' developed by John Conway at
  289. MIT to model real organisms.  The rule for automaton reproduction was incr-
  290. edibly simple: If a cell has two or three neighbors, no change in the cell.
  291. Fewer or more neighbors, it starves or is overcrowded to death, and repro-
  292. duction occurs when a blank space has exactly three neighbors.
  293.         Using these simple rules, incredibly complex patterns can be produced.
  294. Anything that can produce complex and varied results from a small algorithm is
  295. a good target for a random number application.  Enter Steven Wolfram from the
  296. Institute of Advanced Studies in Princeton, NJ.
  297.         Wolfram has been doing research on one-dimensional cellular machines,
  298. which have the advantage of being able to work with both todays machines and
  299. future parallel machines.  Wolfram has developed an automaton that is a one
  300. dimensional circular array modified by the rule:
  301.       
  302.         a(x,t) = a(x-1,t-1) XOR (a(x,t-1) OR a(x+1,t-1)) MOD k
  303.       
  304.         Where x is the position in the array and t is the time,
  305.         k is the number of available characters (k = LEN(Q$)),
  306.         and a is the one-dimensional array.                       
  307.  
  308.         This rule has several interesting properties.  The problem we had with
  309. linear algorithms was that simple algebra could be used to analyze the
  310. evolution of the algorithm (the patterns produced.)  All that you have to do is
  311. figure out how *one* cell evolves, then apply that pattern across the entire
  312. array.  In the above case, there is no way of analyzing the array at time t
  313. without loading the initial conditions and running the whole thing. 
  314.         The second thing to note is that there are k to the power of w (where w
  315. is the width (number of cells) in array a) possible states the machine can be
  316. in, and not all of these states have a predecessor that generates it.  These
  317. states are called 'Garden of Eden' states, and can only occur if they are set
  318. as an ititial condition. 
  319.          As a result, this rule is neither a one-to-one mathmatical mapping,
  320. nor is it and onto mapping of the set of arrays into itself.  In laymans'
  321. terms, this means that for any given array state it is impossible to tell what
  322. (if any) previous state generated it by mere pattern analysis.
  323.          While this isn't a file on breaking codes- about the only way to crack
  324. this one that's been discovered is to load *every* k**w state into memory and
  325. page through them searching for a pattern.  This method can be defeated easily
  326. by setting w to more than 30 cells (assuming k=256, all the ASCII characters.)
  327. If you are using my array Q$, you might want to set w to 40 or more.  Since 256
  328. to the 30th power is about a zillion bits, roughly equal to the largest memory
  329. bank in existence, there isn't much chance of anyone breaking it.  For the
  330. truly paranoid, set w to 50 and sleep easy at night.
  331.  
  332.          Anyway, back to the algorithm...
  333.  
  334.         Each of the cells is filled on one of the k integers from 0 to k-1,
  335. giving each cell k possible states.  Wolfram found that the string of bits
  336. occupying the 0 position (a(0,1), a(0,2), a(0,3)...) forms a random sequence
  337. that passes all statistical tests, sometimes with better results than standard
  338. DES algorithms.
  339.         Let's break this down and see what it's doing.  First of all, we will
  340. need two arrays.  Each array is set up thus:
  341.  
  342.                         Array for Time One                
  343.         |------|       |------|       |------|      |------|
  344.   |---->|a(0,1)|------>|a(1,1)|------>|a(2,1)|----->|a(3,1)|-----|
  345.   |     |------|       |------|       |------|      |------|     |        
  346.   |--------------------------------------------------------------|
  347.  
  348.                         Array for Time Two             
  349.         |------|       |------|       |------|      |------|
  350.   |---->|a(0,2)|------>|a(1,2)|------>|a(2,2)|----->|a(3,2)|-----|
  351.   |     |------|       |------|       |------|      |------|     |        
  352.   |--------------------------------------------------------------|
  353.  
  354.         The reason we need two arrays is so you can update the array without
  355. destroying anything in it.  In other words, you start out with array 1 active,
  356. then you update the array into array 2 and change the active array to 2.  On
  357. the next clock tick you will update the active array (now 2) into the inactive
  358. one (now 1) and set the active array back to 1.  You keep swapping like this.
  359. Logically, you only have one array- the active one.
  360.          To initialize the array, the ASCII values of each character in the key
  361. are plugged into the first LEN(KEY$) spaces in the array.  If you want to use a
  362. short key, modify the code to fill the *entire* array with values of the key
  363. (keep repeating a loop from 1 to W pulling characters out of K).  Since the key
  364. can be anything printable, use something 10-20 characters long that you can
  365. remember- "HACK TO LIVE, LIVE TO HACK" is one of my favorites.  Anyway, if you
  366. use a short (less than 10) key in this program, the distri- bution will be
  367. skewed for the first W MOD LEN(KEY$) itereations of the automaton, but will
  368. smooth out nicely after that.
  369.           After the array is filled, it operates exactly like the first program
  370. *except* when it need a random number of positions to move.  Then it drops
  371. down, updates each cell in the automaton, and then reads the value in A(0,time)
  372. as the random number to shift by.
  373.           Let's look at the modified encryption code.
  374.  
  375. REM ************************************************************************
  376. REM
  377. REM  This is an modification of Program 1 that doesn't use a machine
  378. REM  specific random number generator, but instead uses a cellular automaton
  379. REM  algorithm.  W is the width of the actual automaton.  A is dimensioned
  380. REM  at 32 to avoid having to reference element 0 of the array, which is
  381. REM  legal on some systems and illegal on the others.  This way it can
  382. REM  be implemented on anything.  Y is set for time 1, Y1 for time 2. 
  383. REM  These correspond to the second dimension in array A.
  384. REM
  385. REM ************************************************************************
  386.  
  387. W = 30
  388. DIM A(32,2)
  389. Y = 1
  390. Y1 = 2
  391.  
  392. REM ************************************************************************
  393. REM
  394. REM  Once again, you can set this up to use files instead of strings. And
  395. REM  note that, unlike the first example, the key doesn't have to be
  396. REM  numeric.
  397. REM
  398. REM ************************************************************************
  399.  
  400. INPUT "String to be encoded"; C$
  401. INPUT "Key Please! (Can be alpha-numeric) ";K$
  402.  
  403.  
  404. REM ************************************************************************
  405. REM
  406. REM  This is where K$ is broken down into a series of characters and their
  407. REM  ASCII value shoved sequentially into array A. 
  408. REM
  409. REM ************************************************************************
  410.  
  411. FOR I = 1 TO LEN(K$)
  412.   T$ = MID$(K$,I,1)
  413.   A(I,Y1) = ASC(T$)
  414. NEXT I 
  415.  
  416.  
  417. REM ************************************************************************
  418. REM
  419. REM  The only difference between encoding and decoding is which way you
  420. REM  move in your Q$ array space.  Encoding takes the original and shifts
  421. REM  to the right, decoding takes the codes value and shifts to the left.
  422. REM
  423. REM ************************************************************************
  424.  
  425. REREAD:
  426.   INPUT "Encode or Decode ? ";A$
  427.   A$=LEFT$(A$,1)
  428.   IF A$="E" OR A$="e" THEN
  429.     A=1
  430.     GOTO HEAD
  431.   END IF
  432.   IF A$="D" OR A$="d" THEN
  433.      A=-1
  434.   ELSE
  435.      GOTO REREAD
  436.   END IF
  437.  
  438. REM ************************************************************************
  439. REM
  440. REM  Q$ contains all the characters that can be encoded.  Every encoded
  441. REM  character will be mapped to a character in this array.  I haven't
  442. REM  included any non-standard characters, so you will have to customize
  443. REM  it to your particular keyboard/system.  I've included an error check
  444. REM  that will abort the encryption if it encounters a character that isn't
  445. REM  in Q$.  I have to use the STRING$ command to insert the spacebar and
  446. REM  the quote into the string.  It could also be done with a ASC(##) in
  447. REM  many basics.  You could expand this to include any non-printable
  448. REM  characters you'd like so you could do non-text files.
  449. REM
  450. REM ************************************************************************
  451.  
  452. HEAD:
  453.   SPACE = 32
  454.   QUOTE = 34
  455.   Q$="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
  456.   Q$=Q$+"1234567890!@#$%^&*()-=_+[]{};:'.><,/?\|"
  457.   Q$=Q$+STRING$(1,SPACE)+STRING$(1,QUOTE)
  458.   QSIZ = LEN(Q$)
  459.  
  460.  
  461. REM ************************************************************************
  462. REM
  463. REM  This is the main loop.  L = length of the string to encrypt.  In this
  464. REM  example, I am only encrypting a single string.  Most people who will
  465. REM  actually use this will change the FOR loop to run until an EOF is
  466. REM  encountered in the input file.  Since the syntax for that will vary
  467. REM  widely from system to system, I'll leave it out.
  468. REM
  469. REM ************************************************************************
  470.  
  471. L=LEN(C$)
  472. FOR H = 1 TO L
  473.  
  474. REM /* Finds the character I in the input string */
  475.   X$ = MID$(C$,H,1)
  476.  
  477. REM /* Finds the integer location of the character in Q$
  478. REM    returns variable POZ */ 
  479.   GOSUB LOKPOZ
  480.  
  481. REM /* CELLULAR updates the cells in the automaton, switches the active
  482. REM    time value, and returns X as the number of positions to shift. */
  483.   GOSUB CELLULAR
  484.  
  485. REM /* If you are encoding, you will shift to the right using addition.
  486. REM    you take the modula base QSIZ to keep the new character within
  487. REM    the bounds of Q$. */ 
  488.   IF A = 1 THEN
  489.     NUPOZ = (POZ + X) MOD QSIZ
  490.   ELSE
  491.  
  492. REM /* Otherwise, you subtract, which takes a bit more math to keep
  493. REM    up with.  Once you have the distance to shift, you must
  494. REM    convert it to a positive integer and then subtract two to
  495. REM    account for the head & tail of the array. */ 
  496.     NUPOZ = (POZ - X) MOD QSIZ
  497.     NUPOZ = NUPOZ - 2
  498.       IF NUPOZ < 1 THEN
  499.         NUPOZ = QSIZ - ABS(NUPOZ)
  500.       END IF
  501.     END IF
  502.  
  503. REM /* Now you assign the new character in array Q$ to Y$, and append
  504. REM    it to your converted string */ 
  505.   IF NUPOZ < 1 THEN
  506.     NUPOZ = QSIZ - ABS(NUPOZ)
  507.   END IF
  508.   Y$ = MID$(Q$,NUPOZ,1)
  509.   D$ = D$ + Y$
  510. NEXT H
  511.  
  512. PRINT  "Original = ";C$
  513. PRINT  "Modified = ";D$
  514. END
  515.  
  516. REM /* This finds character X$ in array Q$ and returns an integer
  517. REM    value of the location.  Called from the main loop. */
  518. LOKPOZ:
  519.   FOUND = 0
  520.   POZ = 1
  521.   TOP:
  522.     IF FOUND = 1 THEN
  523.       RETURN
  524.     ELSE
  525.       TMP$ = MID$(Q$,POZ,1)
  526.       IF X$ = TMP$ THEN
  527.         FOUND = 1
  528.       END IF
  529.       POZ = POZ + 1
  530.       IF POZ > QSIZ THEN
  531.         PRINT  "Error: Character '";X$"' not in array Q."
  532.         END
  533.       END IF
  534.     END IF
  535.   GOTO TOP     
  536.  
  537. REM ***********************************************************************
  538. REM 
  539. REM  This is the cellular automaton
  540. REM
  541. REM ***********************************************************************
  542.  
  543. CELLULAR:
  544.  
  545. REM /* Goes through the loop updating into the inactive time (1 or 2 dep-
  546. REM    ending on how Y and Y1 are assigned) */
  547.   FOR I = 1 TO W
  548.     A(I,Y) = A(I-1,Y1) XOR (A(I,Y1) OR A(I+1,Y1))
  549.   NEXT I
  550.  
  551. REM /* Updates the ends of the array (logical positions 0 and 31) that
  552. REM    are used in calculating other fields. */
  553.   A(0,Y) = A(W+1,Y1) XOR (A(0,Y1) OR A(1,Y1))
  554.   A(W+1,Y) = A(W,Y1) XOR (A(W+1,Y1) OR A(0,Y1))
  555.  
  556. REM /* Assigns the first cell to X as a random number */
  557.   X = A(1,Y)
  558.  
  559. REM /* Flips the active time */
  560.   TMP = Y
  561.   Y = Y1
  562.   Y1 = TMP
  563.  
  564. RETURN
  565.  
  566.          Ok, let's trace through a *small* example.  Assume our earlier
  567. map of "AEIOU12345" and an automaton of width 5.  For a key, we'll use
  568. "A15".
  569.  
  570. 1) Assign ASC(A) to a(1,1), ASC(1) to a(2,1), ASC(5) to a(3,1).
  571.    ("0" will represent an empty cell in this example.)
  572.    A(time 1) = 0 65 49 53 0 0 0
  573.    (Remember that an array of width 5 is going to have 7 actual elements)
  574.   
  575. 2) Now then, we want to encrypt the string "EE3"
  576.    First, we locate where E is in our map. LOKPOZ("E") = 2
  577.  
  578. 3) Now then, we update the automaton.
  579.    a(1,2) = 0 XOR (65 OR 49)
  580.    a(2,2) = 65 XOR (49 OR 53)
  581.    a(3,2) = 49 XOR (53 OR 0)
  582.    a(4,2) = 53 XOR (0 OR 0)
  583.    a(5,2) = 0 XOR (0 OR 0)
  584.   
  585.    Since this isn't a tutorial on binary numbers and boolean algebra, you'll
  586.    have to trust me on this one...
  587.   
  588.    a(1,2) = 113
  589.    a(2,2) = 116
  590.    a(3,2) = 4
  591.    a(4,2) = 53
  592.    a(5,2) = 0
  593.   
  594. 4) Now we update the ends.
  595.    a(0,2) = 0 XOR (0 OR 65)
  596.    a(6,2) = 0 XOR (0 OR 0)
  597.   
  598.    Again...
  599.    a(0,2) = 65
  600.    a(6,2) = 0
  601.   
  602. 5) Now we switch the active time from 1 to 2, and our new automaton is
  603.    a(time 2) = 65 113 116 4 53 0 0
  604.  
  605. 6) We then pull off a(1,2) as the number to shift by.
  606.  
  607. 7) Postion 2 + 113 (we're encoding, so we add) is 5 (modulo arithmatic.)
  608.  
  609. 8) "E" is encoded into "U".
  610.  
  611. 9) We repeat this two more times (you don't really want me to step through
  612.    it all, do you?) and end up with the encrypted version.
  613.   
  614.          Well, that's going to pretty much wrap this file up.  If you are
  615. interested in more files of this nature, let me know.  If you find this totally
  616. confusing, but want to learn more, call The Phoenix Project at 512/441-3088
  617. (300/1200/2400, 24 hours a day).  Our friendly and helpful LOD/H staff will be
  618. glad to assist you.  Other people who you might want to talk to about
  619. encryption include Dr. Cypher, Tuc, and Prime Suspect.
  620.          Also, if you are interested in seeing the above algorithm applied in
  621. other languages let me know.  If there's enough of a demand I'll release C,
  622. Modula-2, and ADA versions.
  623.  
  624.        This has been a Legion of Doom/Legion of Hackers presentation!
  625.  
  626.                               The Mentor
  627.                                  LOD/H
  628.                     
  629. *****************************************************************************
  630. References and Acknowledgments:
  631.  
  632. "How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits";
  633. M. Blum & S. Micali; SIAM Journal of Computing, vol. 13, p. 850 (1984)
  634.  
  635. "Functions of Random Variables"; John Freund & Ronald Walpole;
  636. Mathmatical Statistics, 4th Edition; Prentice-Hall Inc., NJ; pp. 240-71
  637.  
  638. "Building an Encryption System"; Peter Wayner
  639. Computer Language, Vol. 4, Num. 12, p. 67 (Dec. 1987 Issue)
  640.  
  641. "Random Sequence Generation by Cellular Automata"; Institute for Advanced
  642. Study; Advances in Applied Mathmatics;
  643.  
  644. "Breaking Pseudo-Random Number Based Cryptographic Algorithms"; M. Vahle &
  645. L. Tolendino;  CRYPTOLOGIA, Oct 1982, p. 319
  646.  
  647. Also my thanks to: TUC, The Leftist, Prime Suspect, and Dr. Cypher, who all
  648.      contributed to this one way or another.
  649.  
  650. ***************************************************************************
  651.  
  652.