# This is file: http://www.math.ncsu.edu/~kaltofen/rsa/rsa.txt # RSA Demonstration Package # Version 3.01 for Maple V Release 4 # Copyright (C) 1992. 1997 Erich Kaltofen, Harold Bien # # For more information regarding the use of each individual function, # please consult # the text procedure file http://www.math.ncsu.edu/public.html/rsa.mpl # # **** NOTE: you may execute this worksheet. It has been tested on # Solaris and Windows95. # however, the worksheet encrypts the contents of a # file plaintext.txt which you should create first # # First, load the RSA package into Maple > read(`rsa.mpl`): # Then, load the package into memory > with(RSA); [blocking_factor, convert/fromASCII, convert/toASCII, decode, decode_file, decode_nopack, encode, encode_file, find_key, pack, power_mod, scramble, unpack, unscramble] # For purpose of demostration, we turn the fast internal Maple # procedures off. That means that we use the packages own procedures # for doing things like converting characters to ASCII code. > `RSA/use_Maple_internals` := false; RSA/use_Maple_internals := false # In order to use any of the RSA procedures, we need to generate a set # of private keys for two people: the recipient and the sender. To # generate a key, we use the function find_key, which will return only # one key at a time. In order to create a set of keys, use the find_key # function twice. find_key takes only one argument, startnum, that sets # the minimum value for a key. For more secure keys, use larger # startnum's. For this example, a small value will suffice. > find_key(17); 17 # 17 was the minimum value, and it turns out that 17 was a suitable key. # To generate the next smallest key, simply ask find_key with one value # higher than the key returned. For instance, in this example, we ask # for a minimum key value of 18, 1 larger than the given 17. > find_key(18); 23 # [Why didn't we just ask for find_key(1) and obtain the minimum key? # Since the RSA package must block out the message into blocks of bits, # the length of the block determined by the length of the key, if the # key is too small, then you will get a "Division by zero" error in the # procedure unpack. To solve this problem, simply use larger keys. It # has been my experience that the smallest public key value is 391 # composed of the two prime numbers 17 and 23. Anything else below 391 # seems to result in a "Divison by zero" error. Future versions may # give a better error message.] # # Now we have a complete set of keys for one person. We shall call this # person the recipient. To save these keys for future use, we can # simply store them as Maple variables. > key1[recpt]:=17; key2[recpt]:=23; key1[recpt] := 17 key2[recpt] := 23 # Separately, these two numbers, 17 and 23, constitute the recipient's # private keys. The recipient's public key is simply the product of the # private keys, hence > pubkey[recpt]:=17*23; pubkey[recpt] := 391 # We follow a similar procedure to obtain the next two smallest keys for # the sender > key1[send]:=find_key(24); key1[send] := 29 > key2[send]:=find_key(30); key2[send] := 41 > pubkey[send]:=key1[send]*key2[send]; pubkey[send] := 1189 # Notice how large the public key quickly becomes. The strength of the # RSA encryption lies in the difficulties behind factoring the public # key. Since there is no general purpose algorithim for factoring an # integer, one must painstakingly plod through each prime number to # factor an integer. With large integers, this task becomes # computationally intractable to current technology. # # Now, let's send a test message to the recipient. To send a message in # Maple, one simply sends a Maple string to the function encode. encode # takes two arguments, with options for up to four arguments. The # simplest form of encode is simply encode(, <Public Key>) # where one gives encode the message to encode in the form of a Maple # string and the public key of the recipient. For example, > cipher:=encode(`This is a test`, pubkey[recpt]); cipher := [14, 339, 348, 265, 276, 315, 265, 276, 315, 79, 315, 24, 16, 276, 24] # RSA encryption provides a way to validate your message as coming from # you. To do this, simply add your private keys as a list. In this # case, encode takes the following arguments: encode(<Plaintext>, # <Public key>, [<Private key 1>, <Private key2>]) as in the following # example: > cipher_sign:=encode(`This is a test`, pubkey[recpt], [key1[send], > key2[send]]); cipher_sign := [[14, 339, 348, 265, 276, 315, 265, 276, 315, 79, 315, 24, 16, 276, 24], [35, 620, 563, 1029, 695, 337, 1028, 503, 695, 695, 253, 197, 503, 337, 563, 253, 695, 337, 1117, 503, 503, 518, 337, 695, 1029, 197, 518, 503, 1021, 337, 1117, 979, 337, 1028, 503, 389]] # Note that by authenticating your message, the ciphertext (or the list # of numbers returned) is now a list of a list of numbers, i.e. there # are now two lists instead of one. The first list is the # authentication information, and the second the encoded message. # # The RSA package is smart enough to figure out if you've authenticated # a message, and will automatically prompt you for the public key of the # sender for verification if detected. # # To decode the following messages, use the procedure decode. decode # takes two arguments: decode(<Ciphertext>, <List of Private keys>). # Note how often we use lists of our private keys. Let's facilitate # future uses of the private keys by storing them as a list > private_keys[send]:=[key1[send], key2[send]]; private_keys[send] := [29, 41] > private_keys[recpt]:=[key1[recpt], key2[recpt]]; private_keys[recpt] := [17, 23] # Now, let's call decode with our newly fomed private keys. > decode(cipher, private_keys[recpt]); This is a test # Just to check to ensure that the encryption actually works, let's see # what happens if we instead gave it the sender's private keys. > decode(cipher, private_keys[send]); Error, (in convert/fromASCII) cannot convert ASCII codes greater than 128 or invalid ASCII code passed: , 150 # The above error message is indicative of an incorrect key. Sometimes # you just get garbage, but more often you will get the above error # message. Now let's see what happens when we give decode a signed # (authenticated) message > decode(cipher_sign, private_keys[recpt],pubkey[send]); Verified authentication string as This message has been signed by me. Body of Message Follows. This is a test # Note that decode detected the authentication information and requested # the sender's public key. Note also that one can simply enter a # symbolic name (a Maple variable name) rather than the actual value # (this can be a timesaver if the public key, as is often the case, is # very long). Since the input is actually Maple input, you must # terminate it with the ever-present Maple semicolon (";"). # Now let's encode a plaintext ASCII file using RSA. The file we will # encode will be called plaintext.txt, the resultant encyrypted file # will be called ciphertext.txt, and the message will be the same "This # is a test". # Before we can encrypt the file, we must first create an ASCII text # file. Note that the package cannot encrypt/decrypt binary files or # files containing ASCII codes over 128. Also, certain non-printable # ASCII codes (such as CR/LF/FF) are lost in the translation and printed # as as period ("."). # To encode a file, use the simple function encode_file which takes # three arguments: # encode_file(<Input file>, <Output file>, <Public Key>) > encode_file(`plaintext.txt`, `ciphertext.txt`, pubkey[recpt]); File encryption complete # Note that encode_file returns nothing, and beware of where encode_file # may place your encoded file. It usually places it in the default # directory, which may or may not be the same as your plaintext.txt # file, leading often to confusion. To avoid this confusion, simply # enter an absolute path rather than a relative path. # Now, let's encode the file and authenticate it. The output file this # time will be ciphersig.txt > encode_file(`plaintext.txt`, `ciphersig.txt`, pubkey[recpt], > private_keys[send]); File encryption complete # Again, nothing is returned. Now let's see if it worked. # To decode a file, use the function decode_file. decode_file takes # similar arguments as decode with the addition of two arguments in # front: the input file name and the output file name. Also, # decode_file is smart enough to figure out if authentication # information is needed, and if so, request for the public key of the # sender. > decode_file(`ciphertext.txt`, `decoded.txt`, private_keys[recpt]); File decryption complete # decode_file will NOT print out the results in Maple. You must read it # using an ASCII text editor or open the file separately in Maple as a # text file. # # Now let's decode the authenticated version. > decode_file(`ciphersig.txt`, `decodsig.txt`, private_keys[recpt], > pubkey[send]); Authentication information verification: Encrypted with RSA system implemented by Kaltofen and Bien. Th\ is message has been signed by me. Continuing with message processing. File decryption complete # Note that this time decode_file asked for the public key of the # sender. Again, since this is a Maple input, you must termiante it # with a semicolon. If you had decided to enter the key directly as a # number, you must still terminate it with a semicolon, or else Maple # will complain and ask for the public again. # # The authentication process for encode_file is different from encode in # that the authentication string is no longer just simply the value of # AUTHENTICATE_STRING, but rather the concatenation of "Encrypted with # RSA system implemented by Kaltofen and Bien" and AUTHENTICATE_STRING. # Later versions of the RSA package may do the same for encode, but as # of version 3.0 this is not done. # # The decoded file is still not displayed, only the authentication # information is shown in Maple. Also, the decoded file has no # indications that it was authenticated. The authentication message # appears only in Maple. # # As a final example, let's encode another Maple string but this time # with our own Authentication string. > AUTHENTICATE_STRING:=`This message has been signed by me.`; AUTHENTICATE_STRING := This message has been signed by me. # Now, let's encode the test message again. > cipher2:=encode(`This is a test`, pubkey[recpt], private_keys[send]); cipher2 := [[14, 339, 348, 265, 276, 315, 265, 276, 315, 79, 315, 24, 16, 276, 24], [35, 620, 563, 1029, 695, 337, 1028, 503, 695, 695, 253, 197, 503, 337, 563, 253, 695, 337, 1117, 503, 503, 518, 337, 695, 1029, 197, 518, 503, 1021, 337, 1117, 979, 337, 1028, 503, 389]] > decode(cipher2, private_keys[recpt], pubkey[send]); Verified authentication string as This message has been signed by me. Body of Message Follows. This is a test # Note that the global string AUTHENTICATE_STRING is used. This means # that if we were to continue authentication other messages, including # files (with encode_file), our custom message would be used. # # For more information, look at the source code (rsa.mpl). Above each # function definition is a short synopsis of how to use that function, # and the source is well commented. Please direct any further # questions/inquiries to: # Harold Bien <hbien@jhu.edu> # 3925 Beech Ave. APT 214A # Baltimore, MD 21211 # # or # # Erich Kaltofen <kaltofen@math.ncsu.edu> # Dept of Math # NCSU # Raleigh, NC 27695 # # [Please note: this program was written only as "hobby" of the authors, # and there is no guaranteed support for it, nor can the authors make # major modifications that would require a lot of time and effort.] # # [The RSA package was originally written by Erich Kaltofen of the # Rensealer Polytechnic Institute in Troy, New York. As a homework # assignment, Harold Bien was asked to develop two authentication # procedures that would electronically sign encrypted and decrypted # messages with RSA. He then added file encryption.]