World of A1200

home *** CD-ROM | disk | FTP | other *** search

/ World of A1200 / World_Of_A1200.iso / programs / misc / rsa / rsread.me < prev next >

Wrap

Text File | 1995-02-27 | 63KB | 1,075 lines

A DEMONSTRATION of the RSA ENCRYPTION ALGORITHM. ================================================ #################################################### # # # The author of this demonstration disk is : # # # # Mr. N. Hensor # # 86, Teignmouth Road # # London NW2 - 4DX # # # # THERE ARE SEVERAL INSECURE FEATURES TO THIS # # PACKAGE. ANYONE WISHING TO PURCHASE THE SECURE # # VERSION, CONTACT ME AT THE ABOVE ADDRESS BY # # MAIL IN THE FIRST INSTANCE. # # # # I also have a wide range of modules for other # # cryptographic algorithms available. # # [In C and assembler (Mororola processors)] # # and will write new modules as required. # # # #################################################### #------------------------------------------------# This program will only run on Motorola 68020 processors ie Amiga 1200 systems. It will not run on Motorola 68000 systems (Amiga 500/600/1000/2000) #------------------------------------------------# The Rivest-Shamir-Adleman encryption algorithm is one of several recently developed techniques for encryption which put immense security for telecommunications and file-archives within reach of the home computer user. This software was written starting with the following objectives: (a) The highest possible level of telecommunications security should be made available to the widest possible market. (b) Encryption speed considerations should not be allowed to intrude on questions of encryption quality, but once a scheme had been decided upon, assembler routines would be used to obtain the best possible speed. If you ask the question "What is the ultimate encryption method?", there is, and never will be, a clear cut answer. However if you draw up a list of say 10 candidates, then some of them are not suitable for use on micro-computers. Of the remaining half-dozen which are suitable, comparisons of security are difficult to arrive at. The RSA algorithm would be on everyones shortlist and provides immense security. This algorithm belongs to a class of encryption schemes known as "Public-Key" encryption schemes. These schemes provide a simple solution to the age-old problem of key-distribution. The algorithm is particularly suited to ensure telecommunications security but can also be used for personal file security. A detailed discussion of the algorithm can be found in many reference books, but the next section contains a thumb-nail sketch of the method - see also the last section on 'Number Theory' for a more mathematical description. The Basics of the RSA algorithm =============================== The algorithm makes heavy use of raising integers to an integer power and then reducing the result using an integer modulus. A brief review of these operations is given at the end of this report, but a detail knowledge of number theory is not necessary to use the R.S.A. algorithm. [All numbers are integers from this point on unless stated otherwise] The RSA algorithm makes use of the following steps for encryption: (a) The message is broken into blocks of numbers. (b) Each number is raised to a power {e} (the encryption exponent) and reduced relative to a composite modulus {N} = p.q. (p,q prime nos) (c) (Optional) The resulting number is changed into text - solely for the purpose of transmission if a modem or hard copy print-out is to be used for transmission. The resulting text can be restored to its original state by: (a) similar to (c) above. (c) Each number is raised to a power {d} (the decryption exponent) and reduced relative to the same modulus {N} as above. (d) The resulting number is changed back to text. The results of these operations depend solely on the 3 numbers {N}, {d} and {e}. Of these {N} and {e} are published - possibly by use of printed lists, possibly by use of a mailed floppy disk or any other convenient means. It is presumed at this point that a potential eavesdropper obtains copies of these numbers. Hence no security is provided by {N} and {e} and all security is provided by keeping {d} secret. This number must be kept locked away and if ever it is suspected that {d} has been compromised, then a new set of numbers {N}, {e}, {d} found, the new {N}, {e} published and the new {d} locked away - in short send any potential eavesdropper back to square 1. There are billions of billions ...........of billions of satisfactory numbers (more than the number of molecules in the whole of the universe) and this software package enables them to be found. It might be argued that since {N} and {e} are openly published, then it might be possible for a potential eavesdropper to obtain a {d} by analysis of {N} and {e}. This is possible if {N} (which is a product of 2 prime numbers) can be factorized or if modular-logarithms can be found. Factorization and modular-logarithms are a well known "hard" numerical problems, and we shall briefly discuss factorisation below. (modular-logarithms are just as hard) Factorization algorithms do exist - they are just not very good. The best available (the Number Field Sieve 1989) has a run time proportional to a constant raised to a power of (n^(1/3). log(n)^(2/3)) where n is the size of the number to be factorized in either decimal digits or binary bits. To appreciate the significance of this formula, let us consider some published results concerning factoring times : (1) A 116 digit composite was factorised [EUROCRYPT 1990] by several computers (total power about 400 MIPS) in 12 months. (2) C. Pomerance sketched out (in 1988) the design of a specialised factoring computer built from custom VLSI chips costing $10,000,000. This machine would be roughly 16,000 MIPS (or 16 GIPS). (National intelligence agencies can be expected to possess such machines.) This machine was built to work an older factoring algorithm known as the quadratic sieve algorithm. (3) Computing power increases by about a factor of 16 per decade and costs fall by a factor of about 100 per decade. Using these figures, we can estimate factorization times for a 16 GIPS (year 1990) machine working the number-field-sieve algorithm as : Decimal Digits |Approximate Factorization Time at year| in {N} | 1990 | 2000 | 2010 | ======================================================= 100 | 3 days | 4.5 hrs | 15 mins | 150 | 56 days | 3.1 days | 4.6 hrs | 200 | 1.2 yrs | 31.6 days | 2.0 days | 300 | 48.7 yrs | 3.1 yrs | 70.7 days | 400 | 866 yrs | 54 yrs | 3.4 yrs | 500 | forget it | 688 yrs | 43 yrs | ------------------------------------------------------- The column for a year 2000 machine refers to a 256 GIPS machine and for 2010, a 4096 GIPS machine. [Want to be rich and famous? Want to lie in the Caribbean sun wondering where your next £100m is coming from? - Easy - just find a method of factoring large composites!] The point of this table is that factorization time climbs so steeply that any opponent just has to give up at some point. If he can factor 200 digit composites then use 300 digit composites or 400 digits and so on. All of this would be academic if it were equally hard to put a suitable composite together in the first place. In fact your humble Amiga 1200 can find suitable 500-digit composites in about 5.25 hrs of running time which all the computers on the planet, working in collusion, would take centuries to split apart. From the point of view of users, the table is revealing in other ways. It should be clear that security can be set at any desired level with this algorithm, in proportion to the risks attendant upon disclosure. If large sums of money or even life and limb are at risk, then choose an {N} with upwards of 300 digits and change these parameters regularly. On the other hand a personal diary might be satisfactory with a 100 digit {N} and not bother changing it at all - a 'mere' 100 MIPS machine would still take 1.5 years to factor it! The drawback with choosing very large {N} values is the speed of encryption. Very roughly the speed of encryption (chars/sec)falls off nearly as the square of the number of digits in {N}. With an {N} of about 100 digits, this software encrypts/decrypts at about 1000 chars/min and with an {N} of 500 digits, encryption rate falls to about 100 chars/min. Clearly the size of {N} has to be carefully considered before selection. In the software you will be asked to set a value for the size of {N} in binary bits. It takes about 3.32 binary bits to represent each decimal digit and hence if an {N} of 300 digits is desired, this corresponds to about 1000 binary bits. FOR THIS DEMONSTRATION SYSTEM, THE MAXIMUM SIZE OF {N} IS LIMITED TO 350 BITS (105 DECIMAL DIGITS). Getting Started with the Software ================================= The software package is a collection of modules and movement from module to module is controlled by the special function keys. F10 is always an exit key and the lower number keys are used for selections. At the top level, F1-F4 will be the most used keys. Pressing F3 and F4 permit access to various housekeeping utilities. As a first step press F3 to go into the ENTER/EXAMINE TEXT section. A list of three utilities will then appear. Let us first check that the printer is correctly set up. This demonstration software package assumes: (a) The printer is connected to the parallel port. (b) The printer DIP switches are set to receive English symbols (ISO 4) and will insert a carriage-return when it receives a new-line(0x0A) command. The Amiga uses a new-line command on its own as a line terminator. (c) This software package requires the printer to act in a similar way to an old fashioned teletype in that visual access is required to each line as it is printed. Lasers and inkjets do not usually permit this and paper consumption with these will be excessive if it is necessary to keep pressing 'form-feed'. The ideal printer is a daisy-wheel type printing to fanfold paper but a dot-matrix type is also satisfactory. Press now F3 which will transfer any disk-file to the printer after you have entered the file AmigaDOS path-name. If the outcome is not satisfactory, then the DIP switches on the printer may have to be adjusted and F3 tried again until success has been obtained. As a second test of the printer, let us use the silent-screen facility. In this software package, the message which has to remain secure is always kept off the VDU. VDU's are insecure in that it is possible to capture the electromagnetic emissions and reconstitute the display using a nearby receiver. Even a printer is moderately insecure since cases of shredded paper being reconstituted have been revealed. (It is also possible that the acoustic emissions from a dot-matrix printer could be processed to obtain the characters being printed.) However if the printer output is incinerated and the ash pulverised, then a printer will be secure. By default, the silent-screen message entry facility (F1) will not echo input to the printer; it will pass it straight to a disk file "RS:RSpublic/silent.txt". However it is possible to change this by altering a global variable in section F4, so exit F3, go into F4, then press F1 now to enter the 'RESET GLOBAL VARIABLES' section. The 5 global variables "nRabin","FileStnData","SStoprinter","Adapt" and "CharSet" can now be changed. Press now the following keys in order: 7,<enter>,1,<enter>,1,<enter>,TRUE,<enter>,1,<enter> and then F1 signalling all OK, and F1 again to indicate session-use only. The significance of these variables will be explained shortly, but for the moment setting "SStoprin" to 1 will force section F3-F1 to echo your input line-by-line to the printer. (These variables remain in their set-state until section F1 is re-entered or until the Amiga is reset). Now we are ready to enter the silent screen section so press F3,F1. You will be given the option of exiting the section but press F1 to proceed. (These early-exit options are included to provide a way out for anyone making a wrong key-press) Enter now any line of text. Note that the cursor moves but that no text appears on the VDU. When you press <enter>, the line is output to the printer and can be inspected together with a chance to accept/reject it. In this way a message can be built up line by line until a zero-length line is input signifying the end of text entry. Before you do this make sure that 1 of your lines contains a "£" sign and check that your printer correctly reproduces it. If it does not, then your printer DIP switches will need adjusting until it is set to receive English symbols. [You may find difficulty in getting your printer to print # (0x23) and £ (0xa3) at the same time. Some printers (Windows compatibles, ECMA-94 character set, etc) can do this; others will only print one or the other : Try entering £# then by changing your printer switches to English or USA the results may be ## or ££. If this happens, then make a decision as to which you prefer, set the printer to suit and avoid the use of the non-functioning key] When you have completed line entry, you might re-enter section F3 to examine the complete text that you have just entered. The only section of F3 not discussed so far is the file destruction section (F2). In the full system a U.S. Dept. of Defence recommendation for erasure of files on magnetic media is used. In brief the file is overwritten 3 times, then declared empty. IN THIS DEMONSTRATION SYSTEM, THE FILE DESTRUCTION ROUTINE HAS BEEN SHORTED OUT, LEAVING YOUR FLOPPY DISKS IN AN INSECURE STATE. [THE AmigaDOS 'DELETE' FUNCTION IS INSECURE - it destroys pointers but not the file itself] You can still enter F2 to check it out, BUT NO FILE-DESTRUCTION WILL TAKE PLACE. Let us now consider the problem of finding prime numbers. Recall that {N} has to be the product of 2 (possibly more) prime numbers. Several other modern cryptographic techniques make use of the properties of primes, and all these need to be able to find new primes at the drop of a hat. Section F4-F5 permits direct access to the prime number seeking software. This section is a stand alone module not related to the main purpose of the package. It is included to satisfy any ultra-suspicious customer who might suspect that this package is using trickery in finding a set of R.S.A. parameters. For the moment all we need to know is that these modules are the same ones used by F6 (the R.S.A. parameter set-up section) and it is easier to get familiar with the prime number seeking software using F5 than F6. So press F5 now. Press F1 to get past the early-exit check and then start to enter your "job-file". Enter the following numbers: 250 <enter> 240 <enter> 1 <enter> 1 <enter> 250 <enter> 240 <enter> 2 <enter> 1 <enter> 250 <enter> 240 <enter> 3 <enter> 1 <enter> Then press F1 to approve your input. This job-file will find one prime number of each type supported, each of moderate size. (250-240 bits) There is no point in seeking large primes on this familiarisation tour, since all that happens is that the machine takes longer and longer. [ON THIS DEMONSTRATION DISK ONLY PRIMES SMALLER THAN 300 BITS CAN BE FOUND] No further input is needed so sit back and watch the machine work. The software uses a random number generator to set up a random number of the required size on the line of integers to act as a starting 'seed' for the search. Blocks of numbers ( 1block = 768 consecutive numbers throughout this package) are now searched for primes. Searching is a two stage process. The first stage eliminates all numbers divisible by all the small primes up to a variable limit. When this stage is complete, there are usuallly about 30-40 numbers remaining which might still be prime. The remaining candidates are then tested using Rabin's algorithm. Rabin's algorithm takes as input 2 numbers: (a) The candidate number to be tested for primality. (b) A random integer called a "witness" used in the test. It has two possible outcomes: NOT PRIME: If this is returned, then the candidate is DEFINITELY not prime. PRIME: If this is returned, there is a 75% chance that the number is prime, and a 25% chance that it is not. Hence, there is a chance that a candidate is not actually a prime but the test indicates that it is. In this event, the "witness" is known as a "false witness". Now this, by itself, won't do. However, if we apply the test again with a new "witness", the chances of finding 2 false witnesses in succession are 0.25 * 0.25 or 1 chance in 16, and we can carry on finding new witnesses, testing again and driving down the probability of error by a further factor of 4. After 10 trials the chances of an error are approximately 1 in 1 million. The number of Rabin tests to be applied is held in a variable called nRabin. if you have been following this introduction in detail, you will recall that we set nRabin to a value of 7 in the Miscellaneous section F1.(This value is too low for serious work, but is good enough for demonstration purposes.) By default this value is set at 30 which will give very high quality results - many authorities recommend a value of 20. This test is implemented in assembler for maximum speed. Returning now to the progress report on screen, each candidate is being examined in this way until a successful outcome is obtained. When a prime has been found, it is written to file "df0:RSpublic/prime.data", and the next item on the job-file started. This output file can be printed out using Miscellaneous F2 when all tasks are completed. If you have entered the job-file as above, then the prime.data file will contain: (a) 1 simple prime. (b) 1 RSA-suitable prime. (c) 1 safe prime. What do these terms mean? A simple prime is just any prime number. The first few are 2,3,5,7,11 etc. An RSA-suitable prime is a prime suitable for use with the RSA algorithm. Recall that {N} is the product of 2 primes conventionally refered to as {p} and {q} ie N = p * q. When the RSA algorithm was first published, a method of attacking it was discovered which although feeble, can be countered by finding a {p} and {q} with a form such that: p = 2.k'.p' + 1 p' = 2.k''.p''+ 1 ( ditto for q ) Where k' and k'' are small primes and p, p', p'' are large primes. These recommendations are built into this package. The technique is to find a simple prime to serve as p'', then try succesive low primes k'' until a prime p' is found. If you watch the progress report, you will see k'' increase apparently erratically. This occurs because p' is tested with a seive as a first stage, but this takes place so quickly that no attempt is made to display the results. When the seive is unable to eliminate the p', the k'' is displayed and Rabin's test is used on p'. Once a p' has been found, the cycle is repeated to find a p which will be the RSA-suitable prime we require. One property of this technique is that the size of p cannot be precisely controlled since the size of the "k's" is not known in advance. Later on when you use this module to set up an {N} value for encryption purposes you will find that the {N} value that is output will be a few bits different from your input demand, and this is a result of the technique described above. A safe-prime was a name used in a text-book discussing problems in cryptology. I personally don't believe there to be anything "safe" about them - look upon it as just a label (and one not recognised elsewhere). A safe-prime as defined here is a prime such that: p = 2.p' + 1 where p' is a simple-prime Such primes have (p-1)/2 primitive roots,(see nomenclature) and since there are a lot of them, it is a simple matter to find one. Such values are needed to set up the 3 128-bit linear congruential random number generators which provide a source of random bits for various low-grade tasks in this demonstration package.[L.C.G.'s are insecure for cryptographic work and IN THE FULL PACKAGE, BLUM-BLUM-SHUB (B.B.S.) GENERATORS ARE USED.] Safe-primes have a nasty property in that there are very large gaps containing none of them. If your starting point leaves you in such a gap, you may prefer to reset your Amiga rather than wait for it to exit. The "cycle-time" refered to at the base of the screen is a rough estimate of the time to make one Rabin test. It is not better than about 10% or 2 secs whichever is greater. Another big influence on total run time, is the distribution of primes themselves. For 250-bit numbers about 1 number in 173 is a simple prime and for 750-bit numbers about 1 in 520. (Safe primes are much rarer than this - these ratios are roughly squared in this case) Allowing for both cycle-time and distibution, the total run-time varies in proportion to the cube of the number of bits set (simple prime) (but with a wide scatter on individual runs). The full software package can handle numbers of 2024 bits (approx 616 decimal digits) but you will be limited to 300 bits in MISCELLANEOUS F5 of this demonstration system. If you have been working steadily through this introduction, you should by now be developing a feel for the trade-off between speed and security provided by the RSA algorithm. So by now you will be ready to set up your personal {N}, {e}, {d} parameters. In this text these 3 numbers are called a station and setting them up called station set-up. In regular computer parlance, the word station refers to the hardware of a terminal, but in this report, the word station refers to an individual users numbers. In an office with say 1 terminal and 20 users, we would say that there were 20 stations. In setting up a station, we go through the following steps: (a) Find {p}, {q} - 2 RSA-suitable primes. (b) Find {N} = p * q. (c) Find a value called {Phi}. (d) Find values {d}, {e} which depend upon {Phi} The values {N}, {d}, {e} have to be saved and the values {p}, {q}. {Phi} can be discarded. Since we assume that a potential eavesdropper can find out {N} and {e} without too much trouble, we must be aware that: If {N}, {e} are known by an eavesdropper (the normal case), then knowledge of ANY ONE OF THE VALUES {p}, {q}, or {Phi} DESTROYS THE SECURITY OF THE RSA SCHEME. Consequently, we must take great care with the disposal of these 3 values. By default, in this package, these 3 values are not stored on disk, displayed on the VDU or output to the printer. ie they are only ever stored in memory and these values can be destroyed by powering the machine down after station set-up is completed. However, for educational purposes, it is possible to over-ride this state of affairs by setting flag "FileStnData" to 1 in Miscellaneous F1. If you have been following this introduction in detail, you will already have done this - if not set this flag to 1 now. When this flag is set, all 6 station numbers are written to file "RS:RSpublic/prime.data" in the order {p}, {q}, {N}, {Phi}, {d}, {e}, and can be copied to the printer using Miscellaneous F2, when the station set-up is complete. One final point should be made before we enter the station set-up section. Setting up a new station destroys the old station parameters on your disk. Consequently, you must be working with a fresh copy of your disk so that you retain a copy of your old parameters. This is necessary for the following reasons: (i) If you are changing your station numbers regularly as a security measure, there will always be someone who sends you messages using your obsolete station values, and you will be unable to decrypt these messages if your old station values are lost. Incidentally this problem highlights the need for rigid procedures in distributing station numbers. (ii) If you are archiving your incoming messages for future reference purposes, these messages must be stored in encrypted form and your old station parameters will always be needed to read these old messages. With this demonstration system, such considerations are not important and can be brushed aside. If you have real security problems, the demonstration system is not suitable. So now armed with a freshly copied disk, we can now set up a new station so press F6. Before the main work starts the 3 128-bit pseudo-random number generators used for various low-grade tasks are reset. Each of these is set up by: (a) Finding a safe-prime of suitable size as a modulus. (actually the size is in the range 112-128 bits) This is done automatically using the old generators. (b) Finding a multiplier which can be manually input or set automatically (just press <enter> when prompted). If you input the multiplier yourself, it will be left or right shifted until it is of a satisfactory size - in other words your input controls the most significant bits (they may not be immediately recognisable since they may have been bit-shifted). This multiplier should be a primitive root, so it is tested and if it is not a primitive root then (multiplier+1), (multiplier+2) etc are tried until a primitive root is found. When all 3 generators have been reset, (normally a few minutes only) the main station numbers are started upon. You will be prompted to input the number of bits in {N}. This is the key variable which we have discussed above which dictates security level and encryption speed. FOR THE PURPOSE OF THIS DEMONSTRATION DISK, {N} IS LIMITED TO 350 BITS which provides only moderate security in commercial applications, and can be broken within hours by the national intelligence agencies. Enter 330 now - this will suffice for demonstration purposes. Three prime-searching displays will now appear, 2 RSA primes and 1 simple prime, in that order.(these are {p}, {q} and {d} being found) (There are internal checks on the suitability of the {d} value found, and if these fail, the simple-prime section will be re-entered to find another {d}) Then {N}, {PHI} and {e} are found without display. After this you will be asked to input a password. It should be clear from the discussion above that all security in the RSA scheme relies on {d} being kept secret, and once it has been revealed all security vanishes. In an office environment, it is very easy to leave a disk lying about in a moments carelessness, with the possibility of security being compromised. If your security problems are severe, then you would have to adopt this assumption and reset your station parameters. However if your problems are less severe (ie unlikely to be attracting the interest of national agencies) it would be beneficial if the {d} value were hidden from a lesser opponent. The scheme that has been used is: (a) The {d} value is exclusive-ORed with a random value and scatter loaded into a large (8k) array of random numbers. (b) The precise details of this operation are controlled by a password together with the 128-bit pseudo-random number generator in drawer "RS:RSprivate". (c) The password is turned into a number in this process and the following points about this should be noted. (i) Upper-case and lower-case letters produce the same bit-patterns in the number - hence a password of "FRED" will be just as effective in retrieving {d} as "fred". (ii) The symbols "g", "G", "w", "W", "0" all produce no set bits in the number. Hence passwords like "www" produce a number of zero which would produce a crash.(such passwords are trapped and refused) (iii) All symbols on the light-tan keys are active and contribute to the number, which means that passwords like "A U" produces a different number from "A U" (different number of spaces) ie all punctuation symbols have an effect. (iv) Passwords of up to 160 characters are allowed, and 'crunched' down to a suitable size. This means that every single character must be correctly reproduced. It is very difficult to correctly enter a 160-character password when it is not displayed on the VDU and about 30 characters is a more practical upper limit. This system could only be "broken" by a very sophisticated opponent - and not then when a B.B.S. generator is in use. After your password has been input, the station set-up will take a further few minutes to complete. Your new station parameters will be in "RS:RSpublic/Ne1.data" (holds {N}, {e}) and "RS:RSprivate/d1.data" (hides {d}). Since we have FileStnData set, all six station parameters have been copied to "RS:RSpublic/prime.data" file and so you can go into Miscellaneous F2 and have them printed out. At this point the {N},{e} pair may need to be circulated to other network members. In the full system, this is accomplished by copying {N} and {e} to a seperate disk "RSStation:" using Miscellaneous F4 and posting this to all members who can add in their own pair, copy it and then pass it on. On this demonstration system, there is no seperate disk, and using Miscellaneous F4 adds the {N},{e} pair into a file "RS:RSstation/Station.data". In order to circulate this, you will have to use AmigaDOS to copy this file to a spare disk and circulate it in this way. This demonstration system permits only 2 stations in this file. For users who are just experimenting with the system, it is not necessary to circulate your numbers in this way and you can just write messages to yourself. (hence skip Miscellaneous F4) Now we are ready to start encrypting messages. The "silent screen" utility is intended for use when entering secure messages, but any word processor package will do for demonstration purposes, so prepare a short message now. The following points should be observed in message preparation: (a) Firstly consider the 2 Global variables <CharSet> and <AdapT>. Two plaintext character sets are available with this package - the MAXimum and MINimum character sets. The MAXimum set consists of : {abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 !"£$%^&*()_+|-=\{}[]:@;#<>,.?/'~<space> + a few control symbols} These are the shifted/unshifted light-tan keys (+ the dark-tan key at top left) on the Amiga. (This will cover just about all needs for normal commercial correspondance. However, the set EXCLUDES the BREAK control-symbol (0x1b) which is used by word processing packages to force a printer to print in 'itallic' or 'bold' or change-font etc. ALL SUCH PRINT ENHANCEMENT FEATURES SHOULD BE OMITTED. Nothing serious will happen if they are included - any unrecognised symbol is transmuted into a '?' symbol which may spoil the appearance of a message but leaves the content unchanged.) The MINimum character set consists of : {ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.? space + control symbols} (The cryptograms are about 15% shorter if this set is used which will be useful if the cryptogram has to be manually entered at the receivers end. NOTE : Adaptive compression is not used with this set.) No internal checks are done on texts before encryption. At encryption, non-valid characters are changed to '?'. This means that you should have a clear idea of the valid characters before entering text. For instance, if the MINimum set is in use, lower-case symbols are all changed to '?' ensuring any 'message' composed of them is meaningless after decryption. These alphabets are compressed by a zero-order Huffman scheme as a first stage in encryption. The compression can be made adaptive or non-adaptive by setting global variable AdapT. Adaptive compression results in a cryptogram about 10-15% shorter than when non-adaptive compression is used. Both sender and receiver must have global variables CharSet and Adapt set the same way or else garbage will be the result. The default settings are MAXimum character set + adaptive compression. (b) The two symbols <.s> or <.e> must not occur together in the file name. As will be explained below the decryption module searches for the occurences of these to determine wether an encrypted file has been signed or not. Hence file-names like <my.script> may cause trouble. (the solution is simple - just rename your file) Encryption is a straightforward operation - just press F1 and respond as prompted. If this is your first entry into this section, do not select "signing" when requested. (It is not possible to 'sign' a cryptogram intended for your own archive or use - the two operations cancel one another out). If your input file was eg "df1:my.text" then the encrypted file will be eg "df1:my.text.1e001". As a message passes through encryption and decryption stages, the following appendages are added : <1> - the MAXimum plaintext alphabet was used by the originator. <2> - the MINimum plaintext alphabet was used by the originator. <s> - this message has been signed. <e> - this message has been encrypted. <d> - this message has been decrypted. <u> - this message has been un-signed. [D is any decimal digit below] <eDDD> - DDD is the destination station reference number. <sDDD> - DDD is the originators station reference number.[Optional] NOTE : 3, any only 3 digits are entered here. NOTE : As issued, this disk has a station reference number of 001. After you set up your own set of station parameters, and attempt to store these values in 'RSstation/Station.data' for distribution, you will be prompted to input a new station reference value and this is added to this file as well as being stored in RSpublic/diskstnref. (In the full system, RSstation/Station.data is a seperate disk which is posted to other network members and the two values must agree. Hence: FROM THIS MOMENT ON, YOUR PERSONAL STATION REFERENCE VALUE SHOULD NOT BE CHANGED - it should stay 'attached' to you as long as you remain in the network.) In this demonstration system the same rule should be followed since only two different station reference numbers are allowed in RSstation/Station.data and there is no deletion provision. thus: my.text.1s012e987 implies : MAXimum alphabet/signed by station 12/ intended for station 987. my.text.1s012e987du implies : as above but then decrypted and unsigned, ie a recovered plaintext. my.text.2e987 implies : MINimum alphabet/plain encryption intended for station 987. my.text.2e987d implies : as above but then decrypted, another recovered plaintext. The purpose of these appendages is: (a) To prevent overwriting of the original message. (b) To indicate the status of intermediate files. (c) To pass over to the receiver details which he needs for a successful decryption. (If the decryption section finds non-standard file appendages, then the information has to be manually input in response to prompts.) IN THIS DEMONSTRATION SYSTEM, THE INTERMEDIATE FILE GENERATED DURING SIGNING (eg my.text.1s012) IS ALSO WRITTEN TO THE DIRECTORY HOLDING YOUR ORIGINAL MESSAGE. THIS FILE IS INSECURE (the plaintext can be recovered from it by use of the public-key). IN THE SECURE SYSTEM, IT IS HELD IN ram: AND DESTROYED AFTER POWERING DOWN. Your encrypted files can now be printed out using F3 - F3. Note that it is a straightforward text-file consisting of symbols 0-9, A-F, + spaces (+ ASCII control symbols) and hence is suitable for printout or modem transmission. You will also notice that the file is roughly 1.5-times longer than your original file. Decryption is also straightforward. Just press F2 and respond to the prompts. You might like to experiment with erroneous passwords to convince yourself that it is impossible to retrieve {d} successfully without a correct password. Your decrypted file will be in file "df1:my.text.1e001d" which can be printed out and will be identical to your original file. If it is not then your original text contained non-valid characters whose presense will be revealed by "?" symbols appearing in strange places. We can now do a signed encryption. To do this go through the following steps: (a) Make a second copy of the demonstration disk. (b) Run Miscellaneous F6 (station set-up) on both disks seperately keeping note of the passwords. (c) Copy {N},{e} to the RS:RSstation/Station.data file on the first disk using Miscellaneous F4 - keeping note of the station reference number you choose. (d) Use AmigaDOS to copy RS:RSstation/Station.data across from disk 1 to the corresponding file on disk 2. (e) Add the {N},{e} values on disk 2 into file RS:RSstation.Station.data using Miscellaneous F4 - use a different station reference number or else the first {N},{e} pair will be overwritten. The file will now hold both pairs of {N},{e}. (f) Copy RS:RSstation.Station.data back from disk 2 to disk 1 (AmigaDOS). (g) Write some 'message' on disk 1 for disk 2, giving disk 2's station reference number when requested. (h) The cryptogram can be copied across to disk 2 (AmigaDOS) - simulating transmission. (i) Switch to disk 2, and decrypt the message. You might like to try this stage with standard and with non-standard appendages. In the non-standard case you will be prompted for encryption details. Thats all Folk's! The only section that we have not visited is Miscellaneous F3, which is not much use until such time as "Station.data" is part-filled by using F4. Both of these sections are self-evident. The principal assembler routine at the heart of this software has been timed at 7 times faster on the Amiga 1200 than on an Amiga 600.(the extra length of the multiply and divide instructions play a big part in this). The Amiga 4000 should provide a 4-5 speed gain above an Amiga 1200. METHODS OF ATTACKING THE R.S.A. ALGORITHM ========================================= [Some of these attacks apply to any encryption technique] The subject of cryptanalysis has certain formal definitions used in discussions of the subject. These are : Participants : (1) Alice and Bob are the 2 people trying to communicate secretly. (2) Eve is an eavesdropper. Eve is passive (does not react to any 'cracked' messages) and tries very hard to remain undetected. (3) Mallet is a malicious intruder. His objectives may include fraud, spreading disinformation etc etc. Mallet is active, and will be detected once he makes his move - once he has defrauded a company he has to run for it. Mallet is generally an Eve in the early stages of an operation. [The distinction between active and passive is fuzzy in real life. Most Eve's will respond actively when the payoff is high enough :- but the response will be 'engineered' to lead suspicion away from Eve.] If Mallet is forced to be an Eve by a counter-intelligence department (ie his objective of company fraud is prevented) then this is success at least as far as the accounts department is concerned. Success against Eve is harder to achieve and 'damage-limitation' is the order of the day. If Alice changes her R.S.A. parameters every day,(or hour), then Eve can only gain partial intelligence even if she use one of the methods below to achieve a break. Methods of Attack : This can be a large list, but for our purposes the following suffice. (1) Ciphertext only. This is the method known to the general public. A wire-tapper collects cryptograms and rushes them round to a bespectacled mathematician who feeds them to his supercomputer, and within moments out pops the plaintext. Such a method is hopeless against the R.S.A. if Alice knows her business. (2) Known plaintext attack. In this method, Eve (or Mallet) trick Alice into transmitting a message written by her. This is usually done by allowing important information to 'fall' into Alice's possession. Such a message has zero-entropy (see nomenclature) to Eve and gives her a good analytical position. This attack is irrelevant to the R.S.A. scheme - ENcryption details are openly published: only DEcryption details are secret - hence there is nothing to uncover. (3) Chosen Plaintext attack. This is an extension of (2) whereby if the first trial fails, a modified text is tried until a break occurs. With the R.S.A. scheme, it is conceivable that say 10,000,000 common (low-entropy) messages could be encrypted and stored by Eve and then compared with actual cryptograms. The counter to this is to use various entropy-enhancing features with the R.S.A. such as Initiallising Vectors and padding (see nomenclature for details). (4) Differential analysis attack. This was only made public in 1990 by Biham and Shamir. In this Eve compares ciphertexts which originate from nearly identical plaintexts. No success against the R.S.A. from this technique has yet been published, but anyway I.V.'s and padding will counter it. (5) Illegal methods. These include threats, bribery, theft, bugging the machine to record key-strokes or the plaintext en-route to the printer or analysing acoustic emmisions from the printer. Damage limitation is the order of the day. It is useful to have a procedure in place enabling threatened individuals to reveal their plight without the sky falling on them. Knowledge of a blackmailing operation, enables a cordon-sanitaire to be put around the target. Illegal methods are far and away the easiest way of breaking into an R.S.A. scheme and highlight the fact that any encryption scheme can only be a part of overall security policy. (6) Trickery. (a) If Eve can induce Alice to 'sign' a message which she has not checked, she may be able to retieve {d} in some circumstances. This is the electronic equivalent of signing a blank cheque, and should never be done. (b) If Mallet can break into the telephone network on the line between Alice and Bob, he might be able to masquerade as the other to each of them. This wont work if a public-key data base is in use but can work if Alice and Bob are stangers and need to exchange public-keys as a first stage in setting up a session. This is the so called man-in-the-middle attack. A technique to force Mallet to become an Eve has been published, but the best solution is to use pre-arranged public-keys. Non-wire communication methods, such as cellular radio or satellite systems are very hard to break into in this way, even for national agencies. (7) Number theory methods. (a) Factorise {N} - this has been discussed above. (b) Calculate a logarithm (mod composite). This is not discussed but is as hard as (a). (c) Use of {N},{e} and a ciphertext block [C]. [A bit 'tuff-sums' this so you may prefer to skip this section secure in the knowledge that the attack and its counter are well understood, and the attack will fail] You will need to be familiar with the number theory section (at the end) to understand this :- Suppose an analyst performs :- C[1] = <C[0]^e> N over and over checking each new C[] to see if a C[i+1] is plaintext. hence C[2] = <C[1]^e> N = <C[0]^(e^2)> N and C[i] = <C[0]^(e^i)> N Hence if ever e^i = d = e^(-1)(mod LAMBDA(N)) then a break will have occured. This occurs when k.LAMBDA(LAMBDA(N)) - 1 = i (and k=1 will do) The counter to this attack i to ensure LAMBDA(LAMBDA(N)) is very large. Recall that in this package N = p.q and that p and q are of the form p = 2.k'.p' + 1 q = 2.l'.q' + 1 p'=2.k''.p''+ 1 q'=2.l''.q''+ 1 where p,p',p'',q,q',q'' are all large primes and k',k'',l',l'' are small (different) primes ( < about 14 bits ) Hence since LAMBDA(N) = 2.k'.l'.p'.q' then LAMBDA(LAMBDA(N)) = lcm[PHI(k'),PHI(l'),PHI(p'),PHI(q')] The exact value of this expression depends on the make-up of k' and l' but we can say LAMBDA(LAMBDA(N)) = K.2.p''.q'' where K>2 Now since the k's and l's are <= about 14 bits then bitsize (p''.q'') >= bitsize (N) - 58 Hence if N = 200 digits (660 bits) then bitsize (p''.q'') approx= 600 bits and p''.q'' is the number of iterations an analyst has to perform to succeed in this attack. To realise how difficult this is, the number of molecules in the whole known universe - out to 30 billion light years - is a number with about 280 bits in binary. In fact so long as p''.q'' > 100 bits (ie N > 160 bits [50 decimal digits]) this attack is hopeless. (d) Find PHI(N) or LAMBDA(N) and then find {d} from e.d = k.LAMBDA(N) + 1 or (k.PHI(N)) + 1). These can only be found after {N} has been factorised which may take a few millenia, but, lets look on the bright side, once p and q are known, d is easy to find. #--------------------------------------------------------------# NOMENCLATURE ============ composite : A non-prime. Hence a composite can be expressed as the product of at least 2 primes. encrypt : The process of transforming a message to an unintelligible form. (see decrypt). In the RSA scheme, the recipients public-key is needed to accomplish this. Thus if a message has to be transmitted to say 7 different people, then 7 seperate encryptions will be needed. Also since the public-keys are not secret in the RSA scheme, a third-party could use the public-keys to forge a message.("signing" stops this possibility) entropy : A measure of whatever is unknown about an event or message. Entropy is measured in binary bits, and depends upon the number of outcomes and the probability of each outcome. Events which are certain have zero entropy and events which have uncertain outcomes have high entropy. Some examples might help : Event : The sun will rise tomorrow morning :- entropy zero. (the sun will definitely rise tomorrow morning, and if it doesnt, no one will be worrying about the damage done to applied maths) Event : The outcome of a fair coin-toss : entropy 1 bit. (only 2 outcomes are possible and these can be represented by 1 bit being set or not-set) Event : The outcome of a 32 equal-horse race : entropy 5 bits. (2^5 = 32 can represent each possible outcome) Event : The outcome of a 32 unequal-horse race : entropy < 5 bits. (More complicated this. The result depends on the odds of each horse winning. Consider 2 extreme cases : (i) 1 entrant is a Derby winner, the others are donkeys from Blackpool beach. The entropy is nil. (ii) All entrants are equally likely to win. This is the 5-bit entropy case above and is the maximum-entropy case. Event : Any message of 80 characters : entropy 0-100 bits(approx). (If the message is in ASCII format, it will need 640 bits to store it. However not all letters are equally likely - 'e' is much more likely than 'z' - and by comparison with the unequal-horse race - the entropy per letter will be much less than 8 bits typically 3.7 bits. In fact careful measurements of English text indicate that the entropy per character is only about 1.2 bits. As evidence of this, consider the following incomplete sentence: T-- ra-- -- Sp--n -all- ------ on th- p---n With a little guesswork, we conclude that the sentence is: The rain in Spain falls mainly on the plain Put simply: many letters are superfluous (zero-entropy!) The transmitter of secure messages must try to keep the entropy of his messages high, while an eavesdropper is always hoping that he can find a low entropy message. One way of attacking cryptographic systems is to 'feed' messages to Alice (possibly using the newspapers) and then monitor her cryptograms. Such messages have zero, or low, entropy to Eve. If Alice is unskilled, she might write low-entropy messages out of ignorance. Such messages include the letter headings and tailings of commercial correspondance - the company name,address,'Dear Sirs' formalities etc are all zero-entropy; the letter reference number will have low entropy; and if the text is right-justified, may include several hundred 'space' symbols (low-entropy). decrypt : The process of transforming an unintelligible message back to an intelligible state.(see encrypt) In the RSA scheme, the recipients private-key is needed to accomplish this. The private-key must be kept secret - all secrecy in the RSA scheme relies on this. In this implementation the private-key can only be accessed by entry of a password. Initiallisation Vector : This is an entropy-enhancing technique useful with low-entropy messages or when unskilled operatives are using a network (see also padding). In this method, the first number block is all random bits (from a secure generator). This is encrypted and transmitted. The real message starts with the second block which is exclusive-or'd with the first block - this is just a reversible process which makes the entropy of the second block greater than that of the first block (very high). This is then encrypted and transmitted. The receiver can decrypt this system easily so long as he knows that an I.V. is in use. (The easiest way to organise this is for all network members to agree to use I.V.'s.) Third and subsequent blocks are treated in a similar way. This technique is not supported by this demonstration system. key : The information needed to encrypt/decrypt a message. Conventionally one key does both functions but in the RSA scheme a "public-key" is used for encryption and a "private-key" for decryption. Public-keys can be openly distributed to anyone who asks for them without loss of security. originator : The person who wishes to transmit a message to a recipient. padding : This is an entropy-enhancing technique (see also Initiallisation Vector). In this the first (or last), say, 32 bits of a block are filled with random bits. Even if the entropy of the message was zero, the entropy of a padded block will be >= the entropy of the padding ie about 32 bits leaving an analyst with a tough problem. The technique can be extended to 64 or even 96 bits if needed, but the encryption rate (chars/sec) drops off in proportion. This technique is not supported by this demonstration system. private-key : The information needed to decrypt a message. In the RSA scheme the private-key is a single very-large number refered to as {d} (for decryption exponent). public-key : The information needed to encrypt a message. This is invariably the recipients public-key which may be published in a document like a telephone directory, but in this implementation will be found from in disk-file "Station.data". If you are yourself the recipient (adding to a personal secure archive) then the public-key will be available in disk-file "RS:RSpublic/Ne1.data". In the RSA scheme the public-key consists of 2 very large numbers {N} and {e}. recipient : The only person who can decrypt an incoming encrypted message. Equivalently, the person to whom the message is directed. signing : The process by which an originator identifies a message uniquely with himself. In the RSA scheme, signing is a similar process to encryption but using {d} (the private key) as the encryption exponent rather than {e}. A signed message is not secure by itself and must be followed immediately by a standard encryption to make it secure. The resulting signed and encrypted message can only be decrypted by the intended recipient, who can then be completely certain of the originators identity. A signed message cannot be forged by a third party intent on mischief. Hence a recipient receiving instructions involving high-risk to himself might want to insist on the instructions being signed as proof of the originators identity. Signing is a very strong concept cryptographically. There is every hope that it will be accepted in law shortly as contractually binding. The concept of "signing" opens up a whole new field of use for cryptology beyond the obvious secret communication one. Using signed messages, "deals" or "contracts" can be struck instantly between any two parties anywhere on the planet without the need for signed and witnessed documents. An all-electronic contract would consist of a signed message of proposal and a reply of a signed message of acceptance. Such all-electronic dealing cannot be forged by a third party and neither signatory could deny that a deal had been struck at some future date. Various protocols also exist for getting such signed contracts electronically 'witnessed' by neutral third parties in a manner that mimics witnessing of paper contracts. primitive-root : A number (a) such that the set of numbers {<a> mod p, <a*a> mod p, ......<a^(p-1)> mod p } [p prime] is the set {1, 2, 3, ........(p-1)} permutated (ie shuffled up). #---------------------------------------------------------------# A LITTLE NUMBER THEORY ====================== Modular Arithmetic ------------------ The result of the operation a mod b is the remainder resulting from subtracting (or adding) b from a until 0<=a<=(b-1) Hence: 5 mod 3 = 2 -1 mod 3 = 2 8 mod 4 = 0 etc. Clearly the result is always in the range 0.......(b-1). More complex operations can be tackled by evaluating "a" first and then finding a mod b as above. Hence: <7cubed> mod 3 = 7*7*7 mod 3 = 343 mod 3 = 1 In this text we shall use brackets <> to delineate the boundaries of the modular operation, hence: <5> 3 means 5 mod 3 = 2. The folloowing formulae are useful in evaluations : <x + y> = <<x> + <y>> <x - y> = <<x> - <y>> <x * y> = <<x> * <y>> Hence : 62^50 mod 5 = <62 * 62 ..(50 times) ..62> 5 = < 2 * 2 ..(50 times) .. 2> 5 substituting <2^10> 5 = <1024> 5 = 4 we get = <4 * 4 * 4 * 4 * 4> 5 = <1024> 5 = 4 Shortly, we shall need to distinguish between different sets of integers. In particular, we shall need the following 3 sets : The set Z => the set of all integers. The set Zn => the set of all integers which can result from the mod operation defined above. Clearly Z3 = {0,1,2} Note that the order of Zn (the number of elements in Zn) is equal to n. The set Zn* => the subset of Zn of those elements of Zn which are mutually prime to n. Z6* = {1,5}. Note that 0 is not in this set since gcd(0,n) = n. (gcd means greatest common divisor, and 2 numbers are mutually prime when gcd(a,b)=1). The order of Zn* has a special symbol - PHI. PHI can be calculated from the following : (i) PHI(p) = p-1 (p any prime) (ii) PHI(p^n) = (p-1).p^(n-1) (iii) if N = p^e.q^f... (p,q.. prime) then PHI(N) = PHI(p^e).PHI(q^f)...... eg PHI(252) = PHI(2^2.3^2.7) = 2 .6 .6 = 72 The theory above is of particular relevance in the following 3 theorems: (i) Fermat's little theorem (for a an element of Zn) a^(p-1) = 1 (mod p) eg for a = 3, and p = 7 then <3^6> 7 = <9^3> 7 = <2^3> 7 = <8> 7 = 1 (ii) Eulers theorem extends Fermat's theorem (which applies to primes) to composites : a^PHI(n) = 1 (mod n) (for a an element of Zn*) eg for a = 5, and n = 6 , then PHI(6) = 2 and Euler's theorem gives 5^2 = 25 = 1 (mod 6) From Euler's theorem we can get : a^PHI(n) * a^PHI(n) = a^(2.PHI(n)) = 1 * 1 = 1 (mod n) and by extension a^(k.PHI(n)) = 1 mod n and multiplying this by a gives a^(k.PHI(n) + 1) = a mod n *** key relation *** NOTE : This last statement applies even when 'a' is in Zn but not in Zn*. eg a = 3, n = 6, PHI(6) = 2, then <3^3> 6 = <3^5> 6 = etc = 3 but Euler's theorem fails with these numbers : ie <3^2> 6 = 3 So the key relation is valid for all values, but Eulers theorem only works for elements of Zn*. (iii) Charmichaels Theorem provides a stronger statement than Euler's theorem : a^LAMBDA(n) = 1 mod n LAMBDA(n) can be calculated from : if N = 2^a.p^e.q^f...... then LAMBDA(2^a) = 2^(a-1) if a<3 or = 2^(a-2) if a>=3 and LAMBDA(N) = lcm [ LAMBDA(2^a), PHI(p^e), PHI(q^f)......] (where lcm => lowest common multiple) eg LAMBDA(28) = lcm [ LAMBDA(2^2), PHI(7) ] = lcm [ 2^1 , 6 ] = lcm [ 2, 6 ] = 6 the following relate LAMBDA to PHI : (a) LAMBDA(n) <= PHI(n) (b) LAMBDA(n) divides into PHI(n) without remainder. (c) LAMBDA(p.q) <= PHI(p.q) / 2 (p,q both primes) The formula for LAMBDA above is about the easiest thing to get wrong that I know of. Check your grasp by finding the following : LAMBDA(LAMBDA(103)) = 16 LAMBDA(LAMBDA( 17)) = 4 LAMBDA(LAMBDA( 31)) = 4 The R.S.A. algorithm relies principally on Eulers theorem and the ability to find 2 numbers such that :- e.d = k.PHI(N) + 1 Having found a pair of numbers such as {e} and {d} then from Eulers theorem for any 'a' (in Zn) a ^ (e.d) = a (mod N) and we have a simple process which recovers the number we started out with. The expression above can be rewritten : (a ^ e) ^ d = a (mod N) which suggests that if we form C = a ^ e (mod N) we can recover a from C : a = C ^ d (mod N) Now all this is very interesting, but is no proof of cryptographic merit. We have merely explained one more method of transmuting a message {a} into a cryptogram {C} and then recovering it. There are thousands of such methods known. Why should this be superior to any other? This is a big question, which cannot be pursued here. Suffice it to say that it has withstood all assault so far. #-------------------------------------------------------------#