Thread View: sci.crypt
2 messages
2 total messages
Started by Bill Callahan
Wed, 20 Apr 1988 21:13
New(?) Random Number Genrator
Author: Bill Callahan
Date: Wed, 20 Apr 1988 21:13
Date: Wed, 20 Apr 1988 21:13
34 lines
2105 bytes
2105 bytes
-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
Re: New(?) Random Number Genrator
Author: Shamim Pogner Mohamed
Date: Thu, 21 Apr 1988 21:29
Date: Thu, 21 Apr 1988 21:29
36 lines
2126 bytes
2126 bytes
In article <12968@mirror.TMC.COM>, billc@mirror.TMC.COM (Bill Callahan) writes:
>
-There is a tantalizing article in the science section of the NYTimes
> -today. ... [ text removed ]
> - 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."
"Indistinguishable" by a polynomial-time probabilistic algorithm, I think.
Most results have narrowed the restrictions further - if "squaring modulo a
Blum-integer (where a Blum-integer is the product of two distinct primes
both congruent to 3 mod 4) is a weak one-to-one one-way function" comes
to mind (memory a little hazy on this).
The generator has been referred to as a "Cryptographically Secure
Pseudo-Random Bit Generator" (CSPRB generator)
I'm not sure of the converse. Do the gurus out there have any opinions?
References:
Goldreich, Goldwasser & Micali - "How to construct random functions"
(FOCS 1984) (A sort of measure of randomness)
Blum & Micali - "How to generate cryptographically strong sequences of
pseudo-random bits" (FOCS 1982) (CSPRB generators)
Blum, Blum & Shub - "A simple secure pseudo-random number generator"
(CRYPTO-82)
Yao - "Theory and applications of trapdoor functions" (FOCS 82) (on the
existence of CSPRB generators given a "weak one-way" function)
--
Shamim Mohamed, Dept. of Computer Science,
U of Arizona, Tucson AZ 85721 (602) 621-4891
{ihnp4,allegra,cmcl2...}!arizona!sham | sham@arizona.edu
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads