From: urlichs@smurf.sub.org (Matthias Urlichs)
Newsgroups: de.comm.misc
Subject: Re: authentification in Emails
Date: 5 Sep 1992 01:36:32 +0200
Organization: University of Karlsruhe, FRG
NNTP-Posting-Host: 127.0.0.1

In de.comm.misc, article <1279@sol.ccc.de>,
  Frank.Simon@sol.ccc.de (Frank Simon) writes:
> 
> michael@galaga.stgt.sub.org (Michael Dreher) writes:
> >In article <714782996snx@rabe.obb.sub.org> ralf@rabe.obb.sub.org (Ralf G. R. Bergs) writes:
> >> Ich GLAUBE, das verwechselst Du was (oder etwa ich?  ;-))
> >Ich bin mir nicht ganz sicher, aber soviel ich weiss meint die Firma,
> >welche RSA anbietet, sie haette ein Copyright auf das Verfahren und
> >das schliesst den Sourcecode ja wohl mit ein.
> Die haben ein Copyright auf IHRE Implementation. Klar. Aber das
> VERFAHREN ist PD. :-)
> 
Das sagst du so einfach und fuer Europa trifft das momentan auch zu, aber in
den Staaten ist es patentiert. Schwachsinn, ein Patent auf Algorithmen
ueberhaupt zuzulassen...

> >Wo gibt es denn ausserhalb der USA einen Sourcecode dafuer ???
> Fuer RSA ?  Bei der GMD, an der Uni Hildesheim, bei ... irgendwann
> hat hier jemand mal so ein TEil gepostet (ist aber Jahre her).
> 
Man nehme Mathematica und lade den folgenden Krempel.

Date:	Fri, 4 Sep 1992 15:13:07 +0200
From:	<grady@public.btr.com>
Message-Id: <9209041313.AA01242@public.BTR.COM>

(* The RSA algorithm implemented in Mathematica language.

Posted 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'.  If you are concerned that this method will
bias the selected prime toward the lower of 'prime pairs,' just roll
the die an extra time or two for a larger modulus: remember, every
additional digit of p means many more times as many potential prime
candidates.)

In the July, 1992 'Communications of the ACM', Ronald Rivest
suggests choosing a modulus, '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 in place of this
comment  (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
message spoofing) *)

(********************************************************************)
(*  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: (1) Mathematica is widely available on a variety of
platforms throughout the world; (2) 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.);
(3) Mathematica is not export controlled; (4) Mathematica uses
high-level constructs that make the code much easier to understand;
(5) Mathematica code is usually quite efficient anyway, given that
the compute-bound parts are well-thought-out and implemented by the
Mathematica kernel team; (6) Mathematica is efficient enough to
actually produce useful, not just toy, results; (7) Since Mathematica
is a general system for doing arithmetic, not a cryptographic-dedicated
application, Trojans are much harder to embed in MMA to thwart using it
for a particular cryptographic purpose. *)

-- 
Science is facts; just as houses are made of stones, so is science made
of facts; but a pile of stones is not a house and a collection of facts
is not necessarily science.
		-- Henri Poincaire
-- 
Matthias Urlichs  --  urlichs@smurf.sub.org -- urlichs@smurf.ira.uka.de   /(o\
Humboldtstrasse 7 -- 7500 Karlsruhe 1 -- Germany  --  +49-721-9612521     \o)/
Newsgroups: de.comm.misc