Proving the randomness of a random number generator?

[afonso.ez at terra.com.br]

Well, you just can't prove a PRNG is secure. It would be like proving that the AES 
is secure, or that factoring integers is hard. It just can't be done (aside theoretical 
discutions about P=NP). 

What you can do, at most, is show that it has the same strength than a known 
difficult problem. A PRNG  using AES as central core, and correctly designed, can 
be shown to be as strong as AES itself. Or you can use a hard problem like 
discrete logarithm to construct one that carries on the same difficulty for 
predictability. 

I think, under the reasonable assumption that they know what they are asking, your 
best approach world be to show that breaking it is as hard as some other problem, 
and that depends exactly on how the PRNG was designed. If it's just a bunch of 
XOR and S-Boxes or if it is something like a Linear Feedback Shift Register PRNG, 
I think you can't do it.



Afonso Araujo Neto





On 2 Dec 2005 at 11:54, Lee Parkes wrote:

> Hi,
> Apologies if this has been asked before.
> 
> The company I work for has been asked to prove the randomness of a
> random number generator. I assume they mean an PRNG, but knowing my
> employer it could be anything.. I've turned the work down on the basis
> of having another gig that week. However, it raised the issue of just
> how this could be achieved. As far as I'm aware there are no strong
> mathematicians in the team, so it will get thrown out to the first
> available person (cool idea, eh?). There will most likely be very
> little time allocated to do it.
> 
> So, the question is, how can the randomness of a PRNG be proved within
> reasonable limits of time, processing availability and skill?
> 
> Thanks,
>  Lee
> 
> -- 
> --
> leep at bogus.net DOC #25 GLASS #136 www.mud-dog.org
> I Need A Reason To Stand Up And Fight
> Need To Believe What I See - The Silver Drop - Mnemic
> 
> ---------------------------------------------------------------------
> The Cryptography Mailing List Unsubscribe by sending "unsubscribe
> cryptography" to majordomo at metzdowd.com
> 



---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com