User talk:Wonderstruck
Welcome
Hello Wonderstruck and
CSPRNGs and root-finding algorithms
Re this edit of yours: Could you please explain the link? I'm having trouble seeing the connection. Thanks. -- Jitse Niesen (talk) 00:15, 14 February 2007 (UTC)
- Sure. A PRNG is an algorithm that takes a finite number of bits as input (the "seed") and produces a much larger (though finite) number of output bits. Therefore, every PRNG can be represented as a function, , where is the seed. More formally:
- One of the requirements of a cryptographically secure PRNG is that it has to pass the "next-bit test". One way to formulate the next-bit test is to define a function that evaluates to the leftmost bits of . A PRNG passes the next-bit test if and only if for every , the probability of correctly guessing , given only , is no higher than 50%.
- Imagine that Alice wants to convince her colleague, Bob, that a given PRNG fails the next-bit test. Bob chooses a random 128-bit secret , computes , and reveals to Alice. If Alice can predict the next 100 bits of PRNG output (that is, if she can correctly guess the value of ) without being given , then Bob will be convinced that fails the next-bit test.
- Let . If Alice can use a root-finding algorithm to find such that , then it is likely that , and, therefore, that .
- In other words, if a PRNG can be solved using a root-finding algorithm (in polynomial time), then it is not cryptographically secure. So, cryptographically secure PRNGs are designed so that they can't be solved (in polynomial time) by any known root-finding algorithms.
- Does that make sense?
- P.S. I just added the link as an interesting bit of trivia, so if you think it should be removed, that's fine.
- -- Wonderstruck 05:40, 14 February 2007 (UTC)
Disputed fair use rationale for Image:AmigaBASIC.png
Thank you for uploading
If it is determined that the image does not qualify under fair use, it might be deleted by adminstrator within a few days in accordance with our
Your input is needed on the SOPA initiative
Hi Wonderstruck,
You are receiving this message either because you expressed an opinion about the proposed SOPA blackout before full blackout and soft blackout were adequately differentiated, or because you expressed general support without specifying a preference. Please ensure that your voice is heard by clarifying your position accordingly.
Thank you.
Message delivered as per request on ANI. -- The Helpful Bot 16:46, 14 January 2012 (UTC)
Barnstar
ArbCom elections are now open!
Hi,
You appear to be eligible to vote in the current
ArbCom Elections 2016: Voting now open!
Hello, Wonderstruck. Voting in the
The
If you wish to participate in the 2016 election, please review the candidates' statements and submit your choices on the voting page. MediaWiki message delivery (talk) 22:08, 21 November 2016 (UTC)
ArbCom 2017 election voter message
Hello, Wonderstruck. Voting in the
The
If you wish to participate in the 2017 election, please review the candidates and submit your choices on the voting page. MediaWiki message delivery (talk) 18:42, 3 December 2017 (UTC)
ArbCom 2018 election voter message
Hello, Wonderstruck. Voting in the
The
If you wish to participate in the 2018 election, please review the candidates and submit your choices on the voting page. MediaWiki message delivery (talk) 18:42, 19 November 2018 (UTC)