############################################################################### # RSA Demonstration Package Revision 3.01 (9/11/1997) # File: http://www.math.ncsu.edu/~kaltofen/rsa/rsa.mpl # # Copyright: Erich Kaltofen, 8/9/1989 (Mathematica) # and 8/10/1992, 9/9/1997 (Maple) # Harold Bien, 8/11/94 (see Version History below) # Permission to use provided the copyright notice is not removed. # # Provides File I/O and Maple V Command line RSA encryption/decryption # with authentication options. # # For an example of using the RSA package, see the files # http://www.math.ncsu.edu/~kaltofen/public.html/rsa.txt # http://www.math.ncsu.edu/~kaltofen/public.html/rsa.mws # # Introduction # ---------------------------- # A note on typographical conventions used in the following text # Procedure names are typed as-is without any surrounding delineations, # e.g. find_key. Arguments to procedures are usually given as where you are to replace with a suitable integer, # string, list or other Maple type WITHOUT the less than/greater than # signs (<>). These signs are used merely to denote a variable, and not # the verbatim name. # # Some arguments are surrounded with square braces ([]). This indicates that # their presence is optional and may be omitted. Arguments separated by a # vertical bar (|) can only be specified one at a time, i.e. given # myfunc(A | B), the only legal calls would be: # > myfund(A) # or # > myfunc(B) # # Commands to be typed in Maple are prefaced with the familiar Maple # prompt, '>' # # Preparing Maple to use the RSA package # --------------------------- # To use: # First, you must load the package into memory. This is accomplished # by loading the rsa.m (or rsa.mpl) file, then using the 'with' command. # For example, # > read(`rsa.m`): # Notice the use of backquotes to delineate the string # > with(rsa); # # Generating a private key # ---------------------------- # Then, you must first generate a set of private/public keys. # Do this with the find_key function. find_key is called with only one # positive integer argument: start. find_key will return a prime number # suitable for the RSA encryption/decryption algorithim. The greater the # starting number, the more secure the encryption. Note, however, that the # greater the starting number, the longer it may take for Maple V to # generate a key. # # Explanation of the keys # ----------------------- # The key returned by find_key is only ONE component of a RSA key. In order # to generate a PUBLIC KEY, you must multiply two find_key keys together, # resulting in a large composite number factorable only into two large # primes (your two find_key keys). The _ENTIRE_ strength of the RSA # encryption relies upon the 'enemy' not being able to factor your public # key. Since your public key is divisible only by your two large prime # numbers, it is unlikely for the 'enemy' to discover your two prime # numbers. This assumption relies on the fact that the factorization of a # number remains computationally intensive, and the larger the factors of an # integer, the more computationally intensive is the procedure. The two prime # numbers together (not multiplied, merely separated) consitute your PRIVATE # KEY. Note, however, that while Maple V has no intrinsic limits on the # size of your private keys, Maple V strings are limited in length to 499 # characters, and the encryption process must break your plaintext string into # blocks large enough for the RSA encryption. The size of the block is # dependent (and directly proportional to) the size of your keys. # Therefore, this package will not work for very large keys. # # It may be useful to save your keys in a Maple document for future reference. # Be sure to save the two prime numbers generated with find_key separately, ie. # as Key1 and Key2 or as a list [Key1, Key2]. The list is the preferred # method as almost all procedures implemented here require a list of the two # keys. # # Note that in all procedures, you may refer to the key by the symbolic name, # rather than the long string of digits. Even when Maple asks for an # authentication key, you can enter in the symbolic # name or the entire string of digits. # # Encoding a Maple string # ----------------------- # To encode a Maple string (delimited by backquotes), use the procedure # encode with the following arguments: # encode(, <PublicKey>, [<Authenicate>, <List of Private Keys>]) # where # PlainText is the string containing the message you wish to be encoded # PublicKey is the _published_ key of the recipient (an integer) # Authenticate is either "true" or "false", and indicates whether or # not you wish to authenticate or "sign" the message with your private keys # List of Private Keys is a list of the private key pair # # If you use the Authentice feature (Authenticate set to true), you will # also need to supply the procedure with your list of private keys. This # is accomplished by adding a list of private keys to the arguments. # For example, # # > encode(`This is a test`, 391, TRUE, [29, 41]) # # would encode the message `This is a test` for a person whose public key # is 391 (17 and 23 are their private keys) and sign the message with your # private key 29 and 41 [Note: the order of your private keys are not # important]. # # The authentication process merely encodes a global string called # AUTHENTICATE_STRING. Set this string to whatever message you like; # if you leave it blank, Maple will simply use the variable name # AUTHENTICATE_STRING as its value. # # If the Authenticate option is FALSE, then you do not need # to enter your private keys. For example, # # > encode(`This is a test`, 17*23); # # would encode the message "This is a test" for a person with the private # keys 17 and 23 and the public key 17*23=391. # [NOTE: The keys here are merely for illustrative purposes. In reality, # the keys are usually much larger, sometimes in the 100 digit region.] # # Decoding a Maple string # ----------------------- # To decode a Maple string, use the procedure decode within Maple. # decode takes the following arguments: # decode(<CipherText>, <List of Private Keys>) # # where CipherText is the list of numbers returned by encode and # List of Private keys is a list of your private keys. Note the use # of brackets to denote a list. Your private keys must be entered # as a list in order for decode to work properly. It will complain # if you do not give it a list of integers. # # For example, to decode the above string, you would enter # > decode([339, 348, 265, 276, 315, 265, 276, 315, 79, 315, 24, 16, # > 276, 24], [17, 23]); # # If the message was signed or authenticated, decode will notify you of # the fact and then prompt for the public key of the sender. # If the public key of the sender is entered, the program will # then decode the authentication string. If the encoder did not set a # specific authentication string via AUTHENTICATE_STRING, then the message # will be simply AUTHENTICATE_STRING. # # If a plaintext message or the plaintext message that is expected does not # appear, and instead garbage appears, then the message was not signed by # the person who published the public key or was incorrectly signed. # # Encoding a file # --------------- # Encode a file using the encode_file procedure with the following arguments: # encode_file(<Input file name>, <Output Filename>, <Public Key>, # [<Authenticate>, <Private Keys>]) # where # Input file name is a string denoting the filename for input # Output file name is a string denoting the filename for output # Public Key is an integer that is the public key of the intended recipient # Authenticate is a boolean (TRUE/FALSE) value that requests authentication # if TRUE # Private Keys is a list of two private keys used for the authentication # # You will not see the results of the encryption in Maple. The results # are instead saved to "output file name". The procedure will only work # for simple ASCII text files (ASCII code below 128). The Private Keys # list is optional, and is required only if you enter true for # Authenticate. The authentication message is slightly different from # that of encode - it's still AUTHENTICATE_STRING, but has a bit more text # prefixed to it. # # Decoding a file # ---------------- # Decode a file using the decode_file procedure with the following arguments: # decode_file(<Input file name>, <Output filename>, <List of Private Keys>) # where # Input file name is a string denoting the filename to be decoded # Output filename is a string denoting the name of the file into which the # decoded message should be saved # List of private keys is a list of our private keys (should be two keys) # If authentication is provided, decode_file will ask for the public key of # the sender. Enter it as a Maple expression, including the terminating # semicolon (";"). # # # Version History # ======================================================================= # Version 1.0 by Erich Kaltofen written for NSF's Young Scholars Program # Modified on 8/10/94 (Maple V Release 3.0) for Version 2.1, # and on 8/11/94 (Version 2.1) # by Harold Bien for file I/O and authentication, comments added as # well as type-safe checking of parameters # (Bien was a participant in the 1994 YSP) # Modified on 2/13/95 (Maple V Release 2.0) for Version 2.2 # Version 2.2: Changed power_mod so that it will no longer terminate # with the error, "Stack Overflow". Note, however, that # large keys will take a long time as the power_mod # function is no longer employed but the standard regular # function is used in its stead. # Modified on 2/19/95 (Maple V Release 2.0) for Version 2.3 # Version 2.3: Deleted power_mod. In its stead, uses inert &^ function # to calculate a^e mod n # Modified on 9/2/97 (Maple V Release 4.0) for Version 2.4 # Version 2.4: Finished commenting code # Added directions for use # Created companion rsa-ex.mws (Maple V Release 4 # worksheet) # Fixed encode_file's duplicate listing of # authenticate variables # Modified on 9/3/97 (Maple V Release 4.0) for Version 2.4.1 # Version 2.4.1: Cleaned up source code, fixed spelling errors # Modified on 9/9/97 by Erich Kaltofen # Version 3.0 # major changes: a. installed switch `RSA/use_Maple_internals` if faster Maple # procedures are wanted # Note: the package was intended as a demo program and all # operations were meant to be transparent, like power_mod and # convert/fromASCII, convert/toASCII # b. rewrote power_mod iteratively # c. pack/unpack now also give the precise character count, so that # file-based encryption/decryption produces identical files # d. based decode_file on fprintf rather than writeto # e. eliminated true/false switches for authentication # Version 3.01 # added close(fd) to decode_file [bug only showed in Windows95] `RSA/use_Maple_internals` := true; # switch to more efficient Maple functions # Use &^ instead of power_mod, # convert(...,bytes) instead of convert(...,toASCII), convert(...,fromASCII) # Package form # To use short forms of procedure names, type command "with(RSA)" # Define the package RSA:=table(): # A package routine is defined as the short procedural name as the index to # the package table and the contents of the table is the actual # procedural code # ********************************** # Initialization Procedure # To Call: VOID # Returns: VOID # Remarks: (Here only for a hook for # future versions, current version # does not require initialization) # ********************************** `RSA/init`:=proc() # Cannot use the write/open/close procedures in Maple V R3 due to bug that will # crash the system when the command "interface(quiet=true);" is executed, # which open procedure executes # readlib(write); ** NOTE ** Maple V R3.0 _WILL_ CRASH if # this statement is not commented out end; # End of `RSA/init` procedure # ********************************* # Convert String to ASCII number Procedure # To Call: convert(<string>:string, toASCII) # Returns: <ASCII Code>:integer # Remarks: Returns the ASCII # representation of the character # in the string. The <string> # parameter must be only 1 character # ********************************* RSA[`convert/toASCII`]:=proc(string) local ctrlstring, # List of ASCII characters i; # Index variable into list of ASCII # string option `Copyright (c) 1992, 1997 by Kaltofen and Bien`; if `RSA/use_Maple_internals` then RETURN(convert(string, bytes)[1]); fi; # Printable ASCII characters in order for conversion from ascii values ctrlstring := `..........\n..................... !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ(\\)^_``abcdefghijklmnopqrstuvwxyz{|}~.`; # Check first if string is greater then length 1 if length(string) > 1 then # Return with error message if so ERROR(`parameter <string>:string should be of length 1 only, but was passed `, string, ` with length `, length(string)); fi; # If its a period, then return ASCII for period (046) if string = `.` then RETURN(046); fi; # Try to find character for i to 128 do if substring(ctrlstring, i..i) = string then # Return ASCII code by position in ctrlstring RETURN(i-1); fi; od; # Character not within first 128 ASCII codes # Return with error message identifying the routine that was invocated and displays the string passed ERROR(`Warning! Tried to convert illegal character (not in standard ASCII),`, string, `, to ASCII.`); end; # End of RSA[`convert/toASCII`] # *********************************** # Convert Number to ASCII string # To Call: convert(<ASCII Code>:integer, from ASCII) # Returns: <ASCII Character>:string # Remarks: Converts an ASCII code to # a character # *********************************** RSA[`convert/fromASCII`]:=proc(ascii_val) local ctrlstring; # String of ASCII characters in order option `Copyright (c) 1992, 1997 by Kaltofen and Bien`; if `RSA/use_Maple_internals` then RETURN(convert([ascii_val], bytes)); fi; # Printable characters for conversion from ASCII values in order ctrlstring := `..........\n..................... !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ(\\)^_``abcdefghijklmnopqrstuvwxyz{|}~.`; # Check if ASCII value is out of range if (ascii_val < 0) or (ascii_val > 128) then # Return with error if so ERROR(`cannot convert ASCII codes greater than 128 or invalid ASCII code passed: `, ascii_val); fi; # Return character at position ascii_val+1 (zero adjustment) from ctrlstring which is in ACSII code order substring(ctrlstring, (ascii_val+1)..(ascii_val+1)) end; # End of RSA[`convert/fromASCII`] # ************************************ # Decode a ciphertext string with RSA # but do not translate back into ASCII # To Call: decode_nopack(<plaintext>:string, <Private Keys>:list) # Returns: <List of Integers>:list # Remarks: Decodes a ciphertext string # with private keys, but will not # translate the plaintext into string # of ASCII characters # ************************************ RSA[decode_nopack]:= proc(plaintext::string, PrivateKeys::list) local i, # Array index ints, # List of numbers (decoded) P, # Private key 1 Q, # Private key 2 magicexp, # Magic exponent publickey, # Public key CodedInts; # List of numbers (encoded) option `Copyright (c) 1992, 1997 by Kaltofen and Bien`; # Get the private keys P := PrivateKeys[1]; Q := PrivateKeys[2]; # Calculate the magic exponent using keys magicexp := iquo(2*(P-1)*(Q-1) + 1, 3); # Calculate the public key publickey := P*Q; # Translate string into array of numbers CodedInts:=pack(plaintext, blocking_factor(publickey)); # Clear decoded array ints:=[CodedInts[1]]; # Loop through array of encoded numbers for i from 2 to nops(CodedInts) do # Decode and add to array ints := [op(ints), unscramble(CodedInts[i], magicexp, publickey) ] od; RETURN(ints) end; # ************************************ # Encode a plaintext string with RSA # To Call: encode(<plaintext>:string, <Public Key>:integer [, <Private Keys>:list [, <signature>:string]]) # Returns: <List of Integers>:list # or [<List of Integers>, <List of Integers>] if authentication requested # Remarks: Encodes a plaintext string # with public key, will authenticate # if asked to with Private Keys. # The global string AUTHENTICATE_STRING # defines the string to be written # for authentication, unless a signature is given # ************************************ RSA[encode]:=proc(plaintext::string, PublicKey::integer) local b, # Blocking factor i, # Index variable ListInts, # List of integers (packed string) PrivateKeys, # List of private keys for authentication magic_exp, # magic exponent AuthCodedInts, # List of ciphertext numbers AuthPublicKey, # Authorization public key AuthIntsList, # List of plaintext authentication string numbers CodedInts, # List of Coded integers Signature; # Signature used for authentication option `Copyright (c) 1992, 1997 by Kaltofen and Bien`; # Find blocking factor to cut up string b:=blocking_factor(PublicKey); # Translate string into list of integers ListInts:=pack(plaintext, b); # Reset list of coded integers; first entry is length of string CodedInts:=[ListInts[1]]; # Loop through list of integers for i from 2 to nops(ListInts) do # Add next encoded number to list CodedInts:=[op(CodedInts), scramble(ListInts[i], PublicKey)]; od; # Check if authentication is requested if nargs>2 then if type(args[3], list) then PrivateKeys:=args[3]; # Encode authenticate string # Calculate exponent magic_exp:=iquo(2*(PrivateKeys[1]-1)*(PrivateKeys[2]-1)+1, 3); # Calculate Public Keys for Encryption AuthPublicKey:=PrivateKeys[1]*PrivateKeys[2]; if nargs>3 then Signature := args[4]; else Signature := AUTHENTICATE_STRING; fi; # List of Integers of Signature AuthIntsList:=pack(Signature, blocking_factor(AuthPublicKey)); # Reset List of Coded Ints AuthCodedInts:=[AuthIntsList[1]]; for i from 2 to nops(AuthIntsList) do AuthCodedInts:=[op(AuthCodedInts), unscramble(AuthIntsList[i], magic_exp, AuthPublicKey)]; od; # Return Authenticate String with Ciphertext RETURN([CodedInts, AuthCodedInts]); else # Return error if not supplied with list ERROR(`authenticate option requires a list of private keys, not `, args[3]); fi; else # No Authentication requested, return ciphertext RETURN(CodedInts); fi; end; # End of RSA[encode] # *************************************** # Decode ciphertext with RSA # To Call: decode(<List of Code Numbers>:list, <List of Private Keys>:list, [<Authenticate>:boolean | <AuthPublicKey:integer]) # Returns: <plaintext>:string # Remarks: Will decode RSA encrypted text # with automatic dection of authentication # string. Authenticate parameter should # only be used if you wish to decipher # only the signature. If only authenticate # is requested, then Private Keys list # should contain only 1 member, the public # key. # *************************************** RSA[decode]:=proc(CodedInts::list, PrivateKeys::list) local b, # Blocking Factor i, # Index variable ListInts, # Plaintext integers magic_exp, # Magic exponent AuthPublicKey, # For authenticate string K, # Public key AuthIntsList, # List of plaintext authenticate string AuthCodedInts; # option `Copyright (c) 1992, 1997 by Kaltofen and Bien`; # Check if authenticate only is requested if nargs>2 then # Ensure correct type if type(args[3], boolean) then # If true then if args[3] then # Get decoded signature AuthCodedInts := CodedInts[2]; # Reset list of integers AuthIntsList:=[AuthCodedInts[1]]; # Get public key AuthPublicKey:=PrivateKeys[1]; # Calculate the blocking factor b:=blocking_factor(AuthPublicKey); # Unscramble authentication string for i from 2 to nops(AuthCodedInts) do AuthIntsList:=[op(AuthIntsList), scramble(AuthCodedInts[i], AuthPublicKey)]; od; # Return string RETURN(unpack(AuthIntsList, b)); fi; else if type(args[3], integer) then AuthPublicKey := args[3]; else ERROR(`third parameter should be a boolean or integer, not a `, args[3]); fi; fi; fi; # Check for embedded authentication code if type(CodedInts[1], list) then if not(assigned(AuthPublicKey)) then # Notify user lprint(`Authentication information detected. Automatic verification continuing...`); # First check authentication # Get public key from user AuthPublicKey:=readstat(`Please enter the sender's public key >`); fi; # Reset authentication number list AuthIntsList:=[CodedInts[2][1]]; # Calculate the blocking factor b:=blocking_factor(AuthPublicKey); # Unscramble string for i from 2 to nops(CodedInts[2]) do AuthIntsList:=[op(AuthIntsList), scramble(CodedInts[2][i], AuthPublicKey)]; od; # Print string lprint(`Verified authentication string as`); lprint(unpack(AuthIntsList, b)); # Skip line for message lprint(`Body of Message Follows.\n`); # Next unscramble message # Reset List of Ints ListInts:=[CodedInts[1][1]]; # Calculate magic exponent magic_exp:=iquo(2*(PrivateKeys[1]-1)*(PrivateKeys[2]-1)+1, 3); # Calculate Public Key K:=PrivateKeys[1]*PrivateKeys[2]; # Unscramble message for i from 2 to nops(CodedInts[1]) do ListInts:=[op(ListInts), unscramble(CodedInts[1][i], magic_exp, K)]; od; # Calculate new blocking factor b:=blocking_factor(PrivateKeys[1]*PrivateKeys[2]); # Return string RETURN(unpack(ListInts, b)); else # Reset List of Ints ListInts:=[CodedInts[1]]; # Get Public Key K:=PrivateKeys[1]*PrivateKeys[2]; # Calculate Magic Exponent magic_exp:=iquo(2*(PrivateKeys[1]-1)*(PrivateKeys[2]-1)+1, 3); # Unscramble message for i from 2 to nops(CodedInts) do ListInts:=[op(ListInts), unscramble(CodedInts[i], magic_exp, K)]; od; # Calculate new blocking factor b:=blocking_factor(PrivateKeys[1]*PrivateKeys[2]); # Return string RETURN(unpack(ListInts, b)); fi; end; # End of RSA[decode] # ********************************* # Encrypt a file with RSA Procedure # To Call: encode_file(<input-filename>:string, <output-filename>:string, <publickey>:integer # [, <private_keys>:list [, <signature>:string]]) # Returns: Nothing # Remarks: Encode using RSA and PublicKey. # Last argument specifies signature, and # if true must also include the private # keys. If authentication is requested, # signature:string should be set to # the authentication string that should # be printed upon decoding. If not set, # the decoder will still specify that it # was signed, and use the contents of # the global variabe AUTHENTICATE_STRING # as a signature # ********************************* RSA[encode_file]:=proc(filename::string, output::string, K::integer) local eof, # EOF flag buffer, # Current line to encode width, # Saved width variable PrivateKeys, # List of private keys Signature; option `Copyright (c) 1992, 1997 by Kaltofen and Bien`; description `Encryption of file through RSA encryption scheme`; if nargs>3 then if type(args[4], list) then PrivateKeys:=args[4]; else ERROR(`\'PrivateKeys\' argument should be a list, but instead is `, args[4]); fi; fi; if nargs>4 then if type(args[5], string) then Signature := args[5]; else ERROR(`\'Signature\' argument should be a string, but instead is `, args[5]); fi; else Signature := AUTHENTICATE_STRING; fi; eof:=false; # Flag file not finished width:=interface(screenwidth); interface(screenwidth=499); writeto(output); # Empty output file writeto(terminal); if assigned(PrivateKeys) then appendto(output); lprint(`Signature Follows`); lprint(RSA[decode_nopack](cat(`\nEncrypted with RSA system implemented by Kaltofen and Bien. `, Signature), PrivateKeys)); writeto(terminal); fi; while not eof do buffer:=readline(filename); # Get next line if type(buffer, integer) then # Check if end of file eof:=true; # If so, then signal and exit loop break; fi; buffer:=cat(buffer,`\n`); # Else append newline to buffer, which was stripped through reading appendto(output); lprint(RSA[encode](buffer, K)); # Write ciphertext to file writeto(terminal); od; interface(screenwidth=width); print(`File encryption complete`); end; # ************************************* # Decode a file with RSA encryption # To Call: decode_file(<input-filename>:string, <output-filename>:string, <List of Private Keys>:list # [, <Public Signature Key>:integer]) # Returns: Nothing # Remarks: Decodes a file with RSA # If the file was encrypted # with a signature, the # procedure will automatically # detect this and ask for the # public key. # ************************************* RSA[decode_file]:=proc(filename::string, output::string, PrivateKeys::list) local eof, # EOF flag buffer, # Current line to decode authenticate, # Authentication flag width, # Saved width of screen K, # Public key fd; option `Copyright (c) 1992, 1997 by Kaltofen and Bien`; description `Decryption of RSA encoded file`; eof:=false; # Flag not at EOF yet fd := open(output,WRITE); # for unbuffered I/O while not eof do # Loop until end of file buffer:=readline(filename); # Read line in file if buffer=`Signature Follows` then if nargs > 3 then K := args[4]; else K:=readstat(`Authentication information detected.\nPlease enter public key of sender >`); fi; lprint(`Authentication information verification:`); buffer:=readline(filename); if type(buffer, integer) then ERROR(`corrupt file.`); fi; buffer:=parse(buffer); print(RSA[decode]([[],buffer],[K],true)); lprint(`Continuing with message processing.`); elif type(buffer, integer) then # Check if at end eof:=true; # If so, then exit loop break; else buffer:=parse(buffer); fprintf(fd, `%s`, decode(buffer, PrivateKeys)); # Else write plaintext to file fi; od; close(fd); print(`File decryption complete`); end; # ************************************* # Find a Key Procedure # To Call: find_key(<Starting Number>:integer) # Returns: <key>:integer # Remarks: Returns a key for RSA. Not sure # if this algorithim will check for non- # masking keys. (Need public key). # ** CAUTION ** Public Key produced MAY NOT # be secure! Be sure of masking! # # Original Remark: Find a probabilistic # prime P>=Start with irem(P, 3)=2 # ************************************* # Modified for source clarity RSA[find_key] := proc(Start::integer) local int; # Key number option `Copyright (c) 1992, 1997 by Kaltofen and Bien`; # Begin search at Start int := Start; # Cannot be even if irem(int, 2) = 0 then int := int + 1; fi; # Cannot be multiple of 3 if irem( int, 3 ) = 0 then int := int + 2; fi; # Cannot be congruent to 1 mod 3 if irem( int, 3 ) = 1 then int := int + 4; fi; # Must be prime while not(isprime(int)) do int := int + 6 od; # should check if safe against p-1 or elliptic factoring algorithm # But does _NOT_ # Return key anyway RETURN(int) end; # End RSA[find_key] # +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ # Start of Internal Functions # (Internal Functions are also accesible to user for greater flexibility) # internal functions # *********************************** # Get blocking factor procedure # To Call: blocking_factor(<Key>:integer) # Returns: <blocking factor>:integer # Remarks: Returns the number of bytes # key can fit. Should be implemented # as a function, but left as is for # package definition. # *********************************** RSA[blocking_factor] := proc(Key) local count; option `Copyright (c) 1992, 1997 by Kaltofen and Bien`; # Calculate count := iquo(trunc( evalf(log(Key)/log(2)) ), 8); # Following 4 lines added as a check against _very_ small keys if count = 0 then ERROR(`Keys too small. Use larger keys.`); fi; RETURN(count); end; # End of RSA[blocking_factor] # ********************************** # Pack text into list of numbers (via ASCII) # To Call: pack(<Text>:string, <Blocking Factor>:integer) # Returns: <List of Numbers>:list # Remarks: the first integer in the list is the length of <Text> # ********************************** RSA[pack] := proc(text::string, b::integer) local chars, # Text with blanks len, # Length of string i, j, k, # Index variables ints, # List of integers code, # ASCII code nb, # Number of blocks of text blanks; # String of blanks for filling option `Copyright (c) 1992, 1997 by Kaltofen and Bien`; # Calculate blocking size nb := length(text)/b; # Refit if needed if type(nb, integer) then len := nb; else len := trunc(nb + 1); fi; # append some blanks so that blocking doesn't run out of characters # Reset blanks blanks := ``; # Keep adding until length is divisible for i to len*b - length(text) do blanks := `` . blanks . ` `; od; # Append the blanks # this hack fails for very long keys # ** WARNING ** Maximum length of string is 499. This _MAY_ exceed string length chars := text . blanks; # Reset List of integers and index j := 0; ints := [length(text)]; # Loop through string and translate into ASCII numbers for i to len do code := 0; for k to b do j := j+1; code := 2**8 * code + convert(substring(chars, j..j), toASCII); od; ints := [op(ints), code]; od; # Return list of numbers RETURN(ints) end; # End RSA[pack] # *************************************** # Unpack integers into ASCII characters # To Call: unpack(<List of ASCII Codes>:list, <Blocking Factor>:integer) # Returns: <ASCII Characters>:string # Remarks: <Blank> # *************************************** RSA[unpack]:= proc(intlist::list, b::integer) local len, # Length of ASCII string blocks i, j, k, # Index variables block, # Cuurent block of text text; # Final message option `Copyright (c) 1992, 1997 by Kaltofen and Bien`; # Calculate length of list len := nops(intlist); # Reset text string to NULL text := ``; # Loop through and translate from ASCII code to text for i from 2 to len do block := ``; j := intlist[i]; for k to b do block := cat(convert(irem(j, 2**8), fromASCII), block); j := iquo(j, 2**8) od; text := cat(text, block); od; # Return Text RETURN(substring(text, 1..intlist[1])); end; # End of RSA[unpack] # ********************************* # Scramble number procedure via RSA # To Call: scramble(<Number>:integer, <PublicKey>:integer) # Returns: <Cipher Number>:integer # Remarks: Internal Function # ********************************* RSA[scramble]:=proc(Int:: integer, PublicKey::integer) option `Copyright (c) 1992, 1997 by Kaltofen and Bien`; # Scramble via Int^3 mod PublicKey and return RETURN(irem( irem( Int*Int, PublicKey) * Int, PublicKey)); end; # End of RSA[scramble] # ********************************* # Unscramble number via RSA # To Call: unscramble(<Coded Number>:integer, <Magic Exponent>:integer, <Public Key>:integer) # Returns: <Clear Number>:integer # Remarks: Internal Function # ********************************* RSA[unscramble]:=proc(CodedInt, MagicExp, PublicKey) option `Copyright (c) 1992, 1997 by Kaltofen and Bien`; # Calculate n^(1/3) mod K using pq s.t. pq=K and return RETURN(power_mod( CodedInt, MagicExp, PublicKey)); end; # End of RSA[unscramble] # ********************************* # Fast modular multiplication # To Call: power_mod(a:integer, e:integer, m:integer) # Returns: <answer>:integer # Remarks: Solves for a^e mod m # ********************************* RSA[power_mod]:=proc(a::integer, e::integer, m::integer) local half, # Needed for solving half of it accu, i, list_of_bits; option `Copyright (c) 1992, 1997 by Kaltofen and Bien`; if `RSA/use_Maple_internals` then RETURN( a &^ e mod m); fi; # x^0 mod n is always 1 if e = 0 then RETURN(1); fi; # x^1 = x if e = 1 then RETURN(irem(a, m)); fi; # recursive approach (runs out of stack for large expos) # # Otherwise, do hard computation # # Do half of computation # half := power_mod(a, iquo(e, 2), m); # # # Do other half and return value # if type(e,even) then # RETURN(Expand(half*half) mod m); # else # RETURN(Expand(half*half*a) mod m); # fi; # iterative version of recursive approach # (is, in fact, Horner evaluation of exponent polynomial) list_of_bits := convert(e, base, 2); accu := a; # Invariant: accu = a^(trunc(e/2^k)) mod m, where k is such that 2^k <= e < 2^(k+1) for i from 2 to nops( list_of_bits ) do accu := Expand(accu*accu) mod m; if list_of_bits[nops( list_of_bits ) - i + 1] = 1 then accu := Expand(accu*a) mod m; # Invariant: accu = a^(trunc(e/2^(k-i+1))) mod m fi; od; RETURN(accu); end; # End of RSA[power_mod]