From: Adam Shostack <adam@lighthouse.homeport.org>
Date: Sun, 3 Mar 1996 06:07:38 +0800
To: tcmay@got.net (Timothy C. May)
Subject: Re: Truly Random Numbers
In-Reply-To: <ad5df17e0002100488bd@[205.199.118.202]>
Message-ID: <199603022126.QAA17169@homeport.org>
MIME-Version: 1.0
Content-Type: text


	My expectation would be that your numbers are not random in a
cryptographic sense, and that this route of attack is much less
efficient than others that would be used.

	I'll note that PGP does NOT take your data entered and convert
it to numbers, but takes timings to choose a hard to predict starting
point for its prime searching.

	I'd expect this use of timings is better than using the large
random number you entered, but in a theory sense only.  Both are
pretty difficult; thats why we like large numbers. :)

Adam


Timothy C. May wrote:

| (In fact, I'd venture that merely asking people to type in digits would
| produce starting points that essentially would be very random...maybe some
| clustering here and there, or an unequal number of digits, or too equal a
| distribution, but adequate. An since an attacker could not know what the
| sources of randomness were for some particular person, I doubt strongly
| that factoring the modulus would be any easier.)
| 
| Suppose a =
| 4801747274372727828487361830183561393615106551195496693610351528409257572926
| 659
| 2027575902673957001560102249600798767153757681546836352857811107361291541511
| 
| (which is about 140-150 digits, "randomly" entered by me)
| 
| and p is computed as the first prime larger than this.
| 
| q found the same way
| 
| Now, is the modulus, n = pq, any more factorable than if a "more random"
| source of p and q were used?
| 
| (I am actually asking this as a real question. Does anyone know if
| factoring is significantly easier for such not-completely-random numbers? I
| would expect that in theory it is, but in practice this is not a useful
| point of entry into factoring n. Just a hunch.)
| 
| --Tim
| 
| 
| Boycott "Big Brother Inside" software!
| We got computers, we're tapping phone lines, we know that that ain't allowed.
| ---------:---------:---------:---------:---------:---------:---------:----
| Timothy C. May              | Crypto Anarchy: encryption, digital money,
| tcmay@got.net  408-728-0152 | anonymous networks, digital pseudonyms, zero
| W.A.S.T.E.: Corralitos, CA  | knowledge, reputations, information markets,
| Higher Power: 2^756839 - 1  | black markets, collapse of governments.
| "National borders aren't even speed bumps on the information superhighway."
| 
| 
| 
| 


-- 
"It is seldom that liberty of any kind is lost all at once."
					               -Hume