RSA Version 1.2b TURBO Pascal (tm) October 14, 1984 D.M. Fritz-Rohner P.O. Box 9080 Akron, Ohio 44305 RSASetUp, RSACrypt, and RSAClear may be used for noncommercial purposes only. No commercial use of this document or these programs may be made without the author's express written permission. The programs RSASetUp 1.2b, RSACrypt 1.1b, and RSAClear 1.1e implement a version of the Rivest-Shamir-Adleman (1) approach to public key cryptography using TURBO Pascal 2.0 (tm) and intend ed to run in CP/M 2.2 (tm) environments. These versions super cede, but do not obsolete, earlier releases. The following discussion and the subroutines in these pro grams depend on Knuth (2). Another introduction to this subject is found in Smith (3) with BASIC routines presented there avail- able in the PKS10/M.LBR library on some bulletin board systems. The object files were produced in a configuration such that the indispensable utility EX or a convenient command extension, like microShell (tm), may be used to facilitate I/O. These versions were compiled with a TURBO Options END address suitable to operation in an MP/M environment. ILLUSTRATION Pick two prime numbers, say, 3 and 11 and call them 'p' and 'q'; p = 3 q = 11 Multiply these numbers to form a 'public' product number 'n'; n = p x q = 33 Decrement each of the prime numbers and form the 'private' pro duct number; n' = (p-1) x (q-1) = 2 x 10 = 20 Find a number relatively prime to this number, i.e., does not share any factors with it. In this case the private product number may be factored; { Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } n' = 2 x 2 x 5 so that 3, 7, 9, 11, 13, 17, 19, or 21, etc. might be used as a 'key'. Then find a number that multiplied by this number and the product divided by n' the remainder is 1. That is, find the reciprocal of the key modulo n'. The corresponding reciprocals are 7, 3, 9, 11, 17, 13, 19, 21, etc. Pick one of these, say 3, as the public key, then the private key is 7; (d,d') = (3,7) with the other possible choices (7,3), (9,9), (11,11), (13,17), (17,13), (19,19), (21,21), etc. Now publish the numbers d and n. These numbers are used to encrypt. Keep d' private. Note the unattractive 'square roots' and the mutually complementary pairs. Someone wishes to send the message, 'HELP', to you. They encode the message using numbers with values in the range [0,(n-1)]. For example, let A = 32, B = 31, ..., Z = 7. And let 6 = EOM, denote end of message. So that; c , c , c , c , c = H, E, L, P, EOM = 25, 28, 21, 17, 6 1 2 3 4 5 Then form the sequence; d e , e , e , e , e where e = c mod n 1 2 3 4 5 i i That is, d 3 e = c mod n = 25 mod 33 1 1 d 3 e = c mod n = 28 mod 33 2 2 ... d 3 e = c mod n = 6 mod 33 5 So the encrypted message sent to you is; e , e , e , e , e = 16, 7, 21, 29, 18 1 2 3 4 5 { Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } To decrypt the message requires application of the corre sponding transformation; d' c = e mod n i i where d' is the 'private' key. That is; 7 c = 16 mod 33 1 7 c = 7 mod 33 2 ... 7 c = 18 mod 33 5 Which yields the original sequence; 25, 28, 21, 17, 6 = H, E, L, P, EOM RSA SetUp Application ===================== The program RSASetUp supports generation and testing of public and private product numbers and keys. This particular release uses radix 10 so that all numbers appearing in the examples are decimal. Input to the program consists of five random numbers pro- vided by the user. These numbers are used to initiate the search for prime factors with particular properties. The first two numbers are used to find 'p', the second two to find 'q', and the last number to find 'd'. The random numbers for generation of 'p' and 'q' are constrained to fewer than 64 digits each to help assure that the TURBO string type length is not exceeded. The random number used to initiate the search for d may be up to 255 digits. Following Knuth (2) we choose numbers to assure that p and q are not 'close'. This release uses the TURBO Random function to generate the test numbers required by the probabilistic pri mality test (2). See COMMENT section below. { Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } EXAMPLE 1 The random numbers were generated by drawing with replace ment using ordinary playing cards with face cards and jokers removed and values taken modulo 10; p1: 15378645 p2: 7223 q1: 569011 q2: 760 d0: 90854 The following is an annotated dialogue with RSASetUp using these numbers; A>rsasetup <- Command. Initialize: .. Be patient. Compose p: r1: 15378645 <- Input 1st random number. 15378645* .. Search downwards for prime. .. Each * denotes a probabilistic .. primality test. 15378641****** .. Found p1. r2: 7223 <- Input 2nd random number, p2. 111218331713* .. Form k, k >= p2, k even and .. congruent p1 mod 3. .. Find prime of form k*p1+1. 111310603559* .. Search upwards on even k. 111495147251******** .. Found p. 2 2 3 601 15459671 .. Try factoring p+1 over .. 'small' primes. Compose q: r1: 569011 <- Input 3rd random number, q1. 569011***** .. Found q1! r2: 760 <- Input fourth random number, q2. 432448361* .. Form k and search for same 439276493* .. form as for p. 442690559* 449518691* 452932757* 456346823******* .. Found q. 2 2 2 3 19014451 .. Try to factor q+1. Factor p: 111495147251 .. Summary. Factor q: 456346823 Product Number: 50880456227911033573 .. Product number n. Compose d: d0: 90854 <- Input 5th random number. 90855 .. Search for prime relative to 90857 .. p and q. { Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } Public Key: 90859 .. Found d. Private Key: 31150762526139197039 .. Compute d' so that .. d*d' mod (p-1)*(q-1) = 1. This process required 3 min 41 sec using a 4MHz Z-80 based system. EXAMPLE 2 For the numbers; p1: 83798947449192 p2: 8037159836 q1: 6702836446 q2: 316702 d0: 3 the following is the excerpted dialogue; Factor p: 673505540938802518493171 Factor q: 2123404954847849 Product Number: 1430125002746934077975498693071050539179 Public Key: 3 Private Key: 953416668497955602979970420575718132107 the generation of which required 12 min 56 sec. EXAMPLE 3 Numbers used in CHALLENGE, see below. EXAMPLE 4 For the numbers; p1: 15518583779449518110039545577 p2: 5222145577922089217 q1: 6008824107816112004 q2: 1726939819690 d0: 5192368 the following is the excerpted dialogue; Factor p: 81040303659465766099166750150404239070782928601 Factor q: 10376877623139581707321200412109 Product Number: 8409453136163470643156122058544049639514153768 29479649746062737794923122829509 { Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } Public Key: 5192369 Private Key: 6282552011668134376062956068120081882940185484158 37484526862877770664065862929 the generation of which required 2 hr 11 min 32 sec. EXAMPLE 5 For the numbers; p1: 42792903162038876741793833201 p2: 5251334500248543640310644653 q1: 48108587971617461248207 q2: 7879795162021658598594 d0: 356655217120480268 the following is the excerpted dialogue; Factor p: 2247198487406097477067836052277719957608999017369887 20761 Factor q: 379085818750444629059904329632899292667120189 Product Number: 8518810784931011955874437838237260204237939707 6643617313911966832546677419884547207483944896946543829 Public Key: 356655217120480269 Private Key: 4408567556048741142507080873744207288832183611289 1103321710629250645857752903220385520269143947038309 the generation of which required 4 hr 17 min 59 sec. Further examples may be found in the text files named DIALOG6, DIALOG7, DIALOG8, and DIALOG9 with performance summarized below. RSA Crypt and Clear Application =============================== The programs RSACrypt and RSAClear use the public product number and the public and private keys, respectively, to encrypt and decrypt specified files. This release makes no provision for piping the control information or for redirecting the text via the console. The following text is found in TEXT1; "We the People of the United States, in order to form a more perfect Union, establish Justice, insure domestic Tranquility, provide for the common defence, promote the general Welfare, and secure the Blessings of Liberty to ourselves and our Posterity, do ordain and establish this Constitution for the United States of America." { Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } The Preamble is not something ordinarily kept secret but is a readily recognized text. EXAMPLE 1 TEXT1 is encrypted with the following dialogue; A>rsacrypt Product Number: 50880456227911033573 Public Key: 90859 Infile: b:text1 Outfile: b:crypt1 **************************************************** where each * denotes a 'block' encryption. The file CRYPT1 is produced in 2 min 46 sec. The following console history; A>rsaclear Product Number: 50880456227911033573 Private Key: 31150762526139197039 Infile: b:crypt1 Outfile: b:clear1 **************************************************** decrypts CRYPT1 to form CLEAR1 which faithfully reproduces TEXT1 in 10 min 28 sec. EXAMPLE 2 Similar transactions for the product number and keys of Example 2 require 29 sec for encryption and 28 min 8 sec for decryption, using the following dialogues, respectively; Product Number: 1430125002746934077975498693071050539179 Public Key: 3 Infile: b:text1 Outfile: b:crypt1 ************************* Product Number: 1430125002746934077975498693071050539179 Private Key: 953416668497955602979970420575718132107 Infile: b:crypt1 Outfile: b:clear1 ************************* { Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } More complete dialogs for Examples 2, 4, and 5 are presented in the files DIALOG2, and DIALOG4 through DIALOG9. EXAMPLE 7 This example illustrates a problem that arises for longer numbers when using TURBO. TURBO buffers input in a 128 byte buffer and appends a final EOF character so that no more that 127 characters are input from a line with any tail discarded. There fore, RSAClear and RSACrypt assume that any input of 127 char acters means that more characters follow on the next line. If exactly 127 characters are in the string then the following line must be empty. For example, the files PUBLIC7 and PRIVATE7 contain the information to drive encryption and decryption for TEXT1: PUBLIC7 37266444656900288331155096688059111088627101584412222957281536519 10705768627710571238386389970072776413797381450882656552867163 2661608445849 41986347613815503065767490894544965 b:text1 b:crypt1 PRIVATE7 37266444656900288331155096688059111088627101584412222957281536519 10705768627710571238386389970072776413797381450882656552867163 2661608445849 12721034485902176169222785206366066259112317172652383448382414610 15278962407771023297005604627516785980553490605912044151221405 0787452026457 b:crypt1 b:clear1 Product number folding at ...36519 and private key at ...14610 are artifacts of text justification limits. The product number break at ...67163 and the private key at ...21405 are end of lines after 127 characters with their respective tails on following lines. Note that the TURBO Version 2 editor folds lines after 125 characters so that it is not compatible with the the read process scissoring after 127 characters. DIALOG8, along with PUBLIC8 and PRIVATE8 present another example. { Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } PERFORMANCE The table below summarizes the run time measurements for these examples. The numbers in parentheses show the correspond ing RSA routine version. For these measurements the file TEXT1 was used. example SetUp Crypt Clear ------- ----- ----- ----- # 1 3m 41s 2m 46s 10m 28s (~20 digits) (1.2a) (1.1a) (1.1c) # 2 12m 56s 29s 28m 08s (~40 digits) (1.2a) (1.1a) (1.1c) # 3 42m 08s 1m 59s 1h 05m 36s (~60 digits) (1.1) (1.1) (1.1) # 4 2h 11m 32s 9m 25s 1h 48m 52s (~80 digits) (1.1) (1.1) (1.1) # 5 4h 17m 59s 28m 27s 2h 48m 45s (~100 digits) (1.1) (1.1a) (1.1c) # 6 5h 05m 57s 54m 41s 3h 25m 28s (~120 digits) (1.2a) (1.1a) (1.1d) # 7 11h 11m 00s 1h 07m 49s 4h 50m 15s (~140 digits) (1.2a) (1.1a) (1.1d) # 8 27h 45m 46s 1h 30m 28s 6h 00m 38s (~160 digits) (1.2a) (1.1a) (1.1d) # 9 17h 28m 42s 1h 15m 02s 5h 01m 34s (~180 digits) (1.2b) (1.1b) (1.1e) CHALLENGE Cryptographic writeups seem to include a test. This test is different. Apply the following product number and public key to the file CRYPT2 to produce CLEAR2. This text has been encrypted by the author using the corresponding private key. This is what is meant by a signed message. If the author had your public keys then he could have further encrypted this message using them and sent the result to you. You would decrypt using your private key, and then authenticate the sender by applying his public keys in a decryption. { Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } Product Number: 162517290174883004568112175886923592338804341174003220375359 Public Key: 31 It required 24 min 43 seconds to sign TEXT2 into CRYPT2. It will require less than 51 sec to unsign the message and, in this case produce the clear text. COMMENT i. The security, if any, of this scheme is in p and q, not their product n. For example, suppose we take the reciprocal of d mod n for the numbers of Example 2; Product Number: 1430125002746934077975498693071050539179 Public Key: 3 Reciprocal: 953416668497956051983665795380700359453 Note that this is not the private key because the reciprocal is formed modulo the public product number n - not the private n'. At first sight it is startling that this looks so much like the 'secret' factor d'; Private Key: 953416668497955602979970420575718132107 A little work will show this is unavoidable since, necessarily, p*q >> p+q ; d' = [2*(p-1)*(q-1) + 1] / 3 x = [2*p*q + 1] / 3 d' = x - 2*(p+q) / 3 Further, the convolution property of multiplication guarantees that; p1 * q1 = x1 + ? p1 * q2 + p2 * q1 = x2 + ? ... p1 * qm + ... + pm * q1 = xm + ? ... pn * q1 = xm+n { Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } where the ? denote carries and the pi, qj, and xk denote digits of p, q, and x. The point is that a search does not n m need to consider 10 * 10 possibilities but only the max(n,m) highly constrained and astronomically smaller 10 . To paraphrase John Von Neumann; "Anyone who considers multiplicative congruential methods of producing ciphers is, of course, in a state of innocence." The security of this method relies on the competence and integrity of men like D.H. Lehmer and Donald Knuth; the continuing work of Rivest, Shamir and Adleman; and their mutual claim that factoring sufficiently large numbers is tough. ii. The TURBO Random function is used to generate test numbers for the Probabilistic Primality Test. The author does not have reference to any work qualifying this genera tor and has performed limited testing using period, Chi square, and autocorrelation measures. The file PERIOD.PAS presents a simple routine to display one facet of Random's performance. This routine prompts for a modulus and then performs period detection trials. One replicate appears as follows; Modulus: 16383 Trial Initial Period 1 15404 2194 2 11573 2488 3 8901 14908 4 8397 4033 5 8772 21009 6 8054 20782 7 13588 36053 8 6593 30487 9 5512 28 10 13355 67955 11 9292 8689 12 9502 5931 13 3953 14215 14 8894 9447 15 7334 46484 The supraperiodic behavior with respect to both modulus and range of integers suggests a shuffling generator of some sort. It is not reassuring in applications like RSA that this generator is proprietary. { Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } iii. The file being encrypted is processed as eight bit bytes so that either text or binary files may be encrypted. The last block is Random filled so that another encryption trial will not generally produce the same file with the same inputs. CP/M text files are terminated and filled with hexa decimal '1A'. Therefore, the exact length of the text in a file might be found by searching for encrypted patterns corresponding to '1A1A .. 1A', 'xx1A .. 1A', etc. There fore, any meaning of the message may not safely be trusted to its exact length. iv. The encrypted blocks are filed and retrieved as seven bit bytes - the low order seven. Therefore, the high order bit may be used for error control. v. RSA is a block cipher. This has the advantage that effects of error in one block are largely confined to that block's output - assuming the keys are intact. A disadvan tage is that block ciphers have a code book like vulnerabi lity called substitution. Suppose that a completed business form is encrypted. Suppose further that the form has an important question with only yes or no answers. Suppose by comparing known clear and cipher text that the corresponding blocks are deduced. It may be possible to substitute. The point is that cryptography is but one element of security. Sub stitution can be frustrated by authentication and seriali zation. Authentication is as simple and fast as computing and appending a CRC to the message before encryption and then stripping, computing, and comparing after decryption. vi. RSA is a convolutional cipher. Therefore, each key bit osculates with each message bit. For example, consider transformation of the following number using the keys of Example 2; d 12345678902345678903 mod n = 16334432371946908433 now, change one bit in the number to be encrypted; d 12345678902345678902 mod n = 13129402162712613628 { Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } or change one bit in the number to be decrypted; d' 16334432371946908432 mod n = 03578279340052214164 This problem and its many consequences are no differ ent for RSA than for any other convolutional system of cryptography. The point is the need to maintain integrity at all stages in a channel. Recovery from error may require search over the space of plausible error. vii. The run time ratios between encryption and decryption shown here a consequence of artificially small public keys. Note that the roles of any two numbers reciprocal modulo n' may be exchanged. Security is not necessarily proportional to CPU time and a small public key is largely a matter of considera tion. Since the receiver is saddled with a disproportionate burden in such cases it ill becomes a respondent to send extraneous material. Note that the key composition process assures availability of 3 as a key. viii. The use of COMPACT and UNCMPACT available on some bulletin boards can greatly reduce the total processing time by compressing even small files before encryption. Use of Richard Greenlaw's SQ and USQ may greatly dilate pro cessing time because the prepended coding tree may increase the effective size of messages that can reasonably be expected in micro driven applications. COMPACTion reduces message statistical redundancy which improves the security of almost any crypto scheme. Consi der the effect of COMPACTion on vulnerability to block substitution. The 'whitening' effect of COMPACT also frustrates detection of repeated blocks. ix. These routines perform incomplete and, therefore, un satisfactory operations to scrub memory of key traces. It would seem necessary to remove and secure any disks and cycle power to the machine assuming volatile memory. Operation in a multiuser environment with the present generation of micros is no more private than the 2001 pod conference. Such considerations are only a beginning in establishing and maintaining security for private informa tion. { Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } QUESTION i. If authentication is not an issue, can the sender pick any number as an encryption key d and use the receiver's public product number to encrypt? So long as the sender also tells the receiver the key d? Since the receiver knows how to compute reciprocals modulo his n' he just produces the d' and decrypts with it. ii. If the sender picks a key d that is relatively prime to his n' can he encrypt with it and send a signed message to the receiver? iii. Will a system based on three or more, rather than two numbers work? That is, let p, q, and r represent primes and n their product. Likewise, let p', q', and r' denote their respective decrements and n' their product. Compute d relatively prime to n and compute d' reciprocal to d modulo n'? iv. Can different public keys be safely assigned to different correspondents or different classes of correspon dence against the same product number? That is, can n be published with d , d , ... , d where the d are crafted to 1 2 m balance the respective correspondent imperatives? For example, can verbore-a-gram senders be constrained to use d that are large, have large set bit counts, and reciprocate to private keys with small numbers and low set bit counts? REFERENCE (1) A Method for Obtaining Digital Signatures and Public Key Cryptosystems R.L. Rivest, A. Shamir, and L.M. Adleman Communications of the Association for Computing Machinery Volume 21, Number 2, February, 1978 (2) The Art of Computer Programming, Volume 2 Seminumerical Algorithms D.E. Knuth Addison-Wesley, 2nd Edition, 1981 (3) Public Key Cryptography John Smith BYTE Magazine Volume 8, Number 1, January, 1983 { Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } Š{ Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } TURBO Pascal (tm) Borland International CP/M (tm) Digital Research microShell (tm) New Generation Systems { Copyright (C) 1984 D.M. Fritz-Rohner, Akron, Ohio 44305 } Š