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 > > -- > -- > [EMAIL PROTECTED] 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 [EMAIL PROTECTED] > --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]