Path: utzoo!mnetor!uunet!husc6!cca!mirror!billc
From: billc@mirror.TMC.COM (Bill Callahan)
Newsgroups: sci.crypt
Subject: New(?) Random Number Genrator
Message-ID: <12968@mirror.TMC.COM>
Date: 20 Apr 88 21:13:23 GMT
Reply-To: billc@prism.UUCP (Bill Callahan)
Organization: Mirror Systems, Cambridge Mass.
Lines: 34


-There is a tantalizing article in the science section of the NYTimes
-today.  Does anyone know anything about it?  The work was done by
-Dr Micali of MIT along with "a loose group of mathematicians --- also
-including Andrew Yao, Manuel Blum, Lenore Blum, Shafi Goldwasser, and
-Michael Shub".  The article in the Times presents the result as a way
-to generate random numbers, but I wonder if that is the real
-significance.  A brief quote: 
-
-       "The new technique involves taking some starting number,
-	multiplying it by itself, dividing by the product of two
-	primes, taking the remainder and using it to repeat the
-	process over and over again.  The mathematicians have proved
-	that there is a peculiar connection between the randomness of
-	the outcome and the difficulty of factoring large numbers.
-	Specifically, they have proved that if factoring large numbers
-	is truly hard --- as most believe likely --- the resulting
-	sequence will be indistinguishable from true randomness."
-
-       "Conversely, if some structure or pattern could be found
-	in the sequence, that pattern would be, in effect, the
-	long-sought solution to the factoring problem."

	Of course, this means that we could use the a very simple
	encryption technique where we XOR each new random number with
	the next 'word' of our plaintext.  If what the article talks
	about is true, as long as we pick big primes and don't allow our
	message to get longer than the product of them (to avoid
	cyclicity problems) the code should be hard to crack.

Bill Callahan	voice: 617-661-0777, ext. 149
Mirror Systems	2067 Massachusetts Avenue  Cambridge, MA, 02140
	billc@mirror.TMC.COM
        UUCP   :  {mit-eddie, pyramid, wjh12, cca, datacube}!mirror!billc