## ← PRNG Implementation Solution - Applied Cryptography

• 2 Followers
• 54 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=yYdv2swiNmA" data-team="udacity"></div> ``` 1 Language

Showing Revision 4 created 05/25/2016 by Udacity Robot.

1. The answer is no. It repeats values too
2. infrequently. This may seem a little surprising.
3. If it was random, well the probability of two
4. consecutive values being equal should be to
5. the negative 128, a very low probability, but
6. not zero. If this is an encryption cipher, well
7. it satisfies the property of invertibility. So
8. any value thats different here encrypts to a
9. different value. So that would mean that for
10. our actual pseudo random number generator, this
11. probability is actually equal to zero. And thats
12. different from what it would be in a real random
13. sequence. This probability is low enough that we
14. still wouldnt expect a repetition for a long
15. time, but we would expect to have one within
16. the first two to the 70 outputs. And we
18. to see why we would expect one this soon.
19. Still a pretty big number, but it would be enough
20. to distinguish this from pure randomness. So to
21. fix that, there is a couple of things we could do.
22. One is to occasionally change the key and after
23. some number of outputs we can take one output,
24. instead of using it as an output we use it as the
25. new key. So even if we dont have any more
26. randomness, we will still change the key; that
27. will affect this probability, it will no
28. longer be zero, we will start seeing values
29. that have some probability of repeating what
30. we saw with the previous key. So well
31. get a new key every few million outputs.
32. The other concern is whether this pool of
33. randomness is good enough? On Unix machines
34. there is a pool of randomness stored in
35. /dev/random and it is collecting events that
36. are believed to be random and out of the
37. control of the attacker. These could be user
38. actions like key presses; these could be
39. things that you collect over the network.
40. There is some risk that these could be compromised,
41. that some of them could be controlled or at
42. least predictable to the attacker. So we want
43. to have multiple pools of randomness and
44. combine them in a way that makes it very
45. difficult for an attacker to control this seed.
46. And this is essentially what the Fortuna
47. Pseudo Random Number Generator does
48. and thats one of the more popular widely
49. used ones. It does use this routine to avoid
50. this apparently non-random property and it uses
51. multiple pools of randomness selected in a way
52. that makes it very hard for an attacker to control
53. what the seed is, even if the attacker can
54. control one or a few of the pools of randomness.