🚀 go-pugleaf

(* The RSA algorithm implemented in Mathematica language.

Given to the net by Grady Ward (grady@btr.com), who takes
all blame for errors and omissions.  Credit for the following
should go to:
Stephen Wolfram, et al. developers of Mathematica,
Rivest-Shamir-Adleman for the RSA algorithm, RSA Data Security, Inc.
for MD5 and further RSA development, and Dorothy Denning for her
excellent technical survey of cryptology. *)

(********************************************************************)
(*  PART ONE USE Mathematica TO COMPUTE THE PUBLIC AND PRIVATE KEYS *)
(********************************************************************)

(* Mathematica code to select proper 'p' and 'q' factors of large 'n'
modulus such that n = p*q.  The large seed for both 'p' and 'q' is
simply fulfilled by purchasing a ten-sided die from a gaming shop
and rolling it many times.  (Suggested by Knuth, v. 2  'The Art of
Computer Programming')

In the July, 1992 'Communications of the ACM', Ronald Rivest
suggests choosing an 'n' of at least 1100 bits for the highest level
"Certification" authority likely to be usable for at least twenty-five
years (given certain assumptions about increases in computing power
over time); this "Certification" level of security translates roughly
to creating an 'n' of about 334 decimal digits. This in turn means
choosing 'p' and 'q' about 167 digits long each.  On a Macintosh IIfx,
computing 'n' takes about twenty hours, given a seed 'p' of 168 digits
and a seed 'q' of 167 digits. *)


p = (* replace this comment with a seed (of at least, say, 150 decimal
digits *);
If[EvenQ[p],p++]; (* make sure seed is an odd number *)

(* Find the first prime following the random seed *)
(* Note: the Mathematica 2.1 test "PrimeQ' uses the Rabin strong
pseudoprime test and the Lucas test (MMA 2nd ed, P. 849).

While long recommended to prevent certain factoring attacks against
the RSA modulus, making sure that the candidate primes, p and q,
have a large prime factor for p-1 and q-1, has reputedly recently
been questioned by Ronald Rivest *)

(* the next statement loops until it finds a probably prime p that
has only a large prime factors for p-1 and/or for 2p+1.  Note that
the code shown, though reasonably concise, does about 30% more work
than actually needed for possible candidates.  (Why?) *)
While[!PrimeQ[p] || (!PrimeQ[p+p+1] && !PrimeQ[(p-1)/2]),p += 2];

(* if p is prime and p-1 has a large prime factor, write p to file
named "pout" on volume named "internal" *)
If[PrimeQ[(p-1)/2], p >> "internal:pout";

(* if p is prime and 2p+1 has a large prime factor, write 2p+1 to
file named "pout" on volume named "internal," overwriting any
previous contents. *)

If[PrimeQ[p+p+1],p >> "internal:pout"];

(* Use similar code as above to compute 'q' *)

q = (* put a completely new large seed here (at least, say,
150 decimal digits; have it differ in length from 'p' above
by one or two digits. *);
If[EvenQ[q],q++]; (* make sure seed is an odd number *)

(* Find the first prime following the random seed *)
While[!PrimeQ[q] || (!PrimeQ[q+q+1] && !PrimeQ[(q-1)/2]),q += 2];

(* if q is prime and q-1 has a large prime factor, write q to file
named "qout" on volume named "internal" *)
If[PrimeQ[(q-1)/2], q >> "internal:qout";

(* if q is prime and 2q+1 has a large prime factor, write 2q+1 to
file named "qout" on volume named "internal," overwriting any
previous contents. *)

If[PrimeQ[q+q+1],q >> "internal:qout"];

(********************************************************************)

(* now compute the 'n' modulus *)
n = p * q;

(* and compute the Euler totient function for two primes, p and q *)
PhiN = (p-1)(q-1);

(* choose a new secret prime number 'd' that is bigger than the
larger of 'p' and 'q' plus one and is smaller than 'n'.  Any
randomly selected prime in this range will do. (See D. Denning:
'Cryptography and Data Security', p. 104) *)

d = (* insert a new random seed here about the same length in
decimal digits of 'n' *)

If[EvenQ[d],d++]; (* make sure first candidate is odd *)

While[!PrimeQ[d], d += 2];

(* write private exponent 'd' to the file 'dout' on volume 'internal' *)
d >> "internal:dout";

(* finally, compute the public exponent... *)
e = PowerMod[d,-1,PhiN];

(* and save it to an external file.  Although you can use an 'e' as
small as 3 (Knuth p. 387), it ought to be large enough to ensure that
every possible message undergoes reduction modulo 'n'
(Denning, p. 104) *)
e >> "internal:eout";

(* AT THIS POINT, YOU HAVE COMPLETELY COMPUTED YOUR PUBLIC AND PRIVATE
KEYS.  YOU MUST KEEP EVERYTHING SECRET BUT 'e' and 'n', WHICH OUGHT TO
BE WIDELY PUBLISHED.  IF YOU WISH, YOU MAY NOW THROW AWAY 'p', 'q',
'PhiN', ONLY KEEPING 'd' (SAFELY ENCRYPTED, OF COURSE, BY, SAY, TRIPLY
ENCRYPTING USING DES IN CBC MODE USING THREE DISTINCT RANDOM KEYS.) *)

(********************************************************************)
(*  PART TWO TEST THE PUBLIC KEY                                    *)
(********************************************************************)

(* Now let's test our new public key and modulus.  Say the message
someone wants to send to us is the Godelized answer to the universe,
42.  The sender encrypts 42 by:   *)

m = 42;
Em = PowerMod[m,e,n]
(* where 'Em' is the encrypted message, 'm' is the plaintext message,
'e' is the public exponent, and 'n' is the modulus. *)

(* The sender then transmits Em to us via any insecure means, say,
internet e-mail... :-) *)


(* now let's decrypt the above message with our secret key, 'd' *)
Dm = PowerMod[Em,d,n]

(* where 'Dm' is the decrypted message, 42.
This, however, is not a good message to send to us because
(1) an opponent could have guessed it by brute-force exponentiation
of many trial messages, and (2) a message without some internal check,
such as the 'digital signature' of the sender, or at least a relatively
strong checksum (such as MD5 message digest algorithm) makes substitution
of a phony encrypted message possible (ciphertext substitution or
masquerading) *)

(********************************************************************)
(*  PART THREE SHOW HOW Mathematica CAN ENCRYPT PLAINTEXT DISK FILES*)
(********************************************************************)

(* Now for a higher level example. We read 128 ASCII bytes from a
file, arithmetically pack them into a single numerical "message,"
and encrypt using the public key exponent 'e' and modulus 'n.' *)

(* open the plaintext ASCII file 'message' on volume 'internal' *)
filenum = OpenRead["internal:message"];

(* read the ASCII file text and block in 128 byte pieces *)
ablock = ReadList[filenum,Table[Byte,{128}]];
messum = 0;
(t = 1;Label[frob];
nextchar = Part[Part[ablock,1 (* or instead of '1', use a variable
here to step through all the 128 byte blocks of 'filenum' *)],t];
messum = messum * 256 + nextchar;
t++;
If[t < 128, Goto[frob]];)

(* the variable 'messum' now contains the first 128 bytes of the
file 'message' arithmetically packed into a single number.  If
you computed an 'n' that is greater than 1024 bits (256^128) long
(that is, more than about 311 decimal digits) the message represented
by 'messum' will be an appropriate size for an encryption modulo
'n', that is, 'messum' can never exceed the value n-1.

(* encrypt the message and write to file 'encrypted' *)
PowerMod[messum,e,n] >> "internal:encrypted"
Close[filenum];

(* now send the 'encrypted' file to the owner of the public key,
'e' and 'n' *)

(********************************************************************)

(* The recipient of the above message decrypts it... *)

OpenRead["encrypted"]; 
(* read the encrypted message as a single decimal representation
into 'Emessum' *)
Emessum = Read["internal:encrypted",Expression];

(* and translate it into the 'plaintext' arithmetically packed value...*)
messum = PowerMod[Emessum,d,n]

(* by successive divisions of 256, retrieve the original ASCII message
characters... *)

(********************************************************************)
(*  PART FOUR  EPILOGUE                                             *)
(********************************************************************)

(* Exercises for the reader: debug the above :-) then complete the
code to (1) read, block, and successively write encrypted blocks from
plain ASCII files of arbitrary length; (1a) strengthen the encryption
by using CBC (cipher block chaining) and IV (initialization vector);
(2) finish the decrypt code to unpack and write the decrypted plaintext;
(3) add the 'authentication' code so that an arbitrary ASCII file can
be 'digested', say by use of MD5 (courtesy RSA Data Security, Inc.),
or DES in krunch mode, and signed using your private exponent 'd'. *)


(* Why use Mathematica for doing RSA when surely more efficient
hardware and software implementations are available?

My answers: (0) Mathematica is widely available on a variety of
platforms throughout the world; (1) Mathematica output in general is
not subject to patent claims or licensing (although to *use* the code
above in the USA may require licensing by RSA Data Security, Inc.);
(2) Mathematica is not export controlled; (3) Mathematica uses
high-level constructs that make the code much easier to understand;
(4) Mathematica code is usually quite efficient anyway, given that
the compute-bound parts are well-thought-out and implemented by the
Mathematica kernel team; (5) Mathematica is efficient enough to
actually produce useful, not just toy, results. *)

flames to:
grady@btr.com  v 1.0   5 August 92