SoylentNews is people
SoylentNews
Want a FIPS 140-2 RNG? Look at the universe. The cosmic background radiation bathes Earth in enough random numbers to encrypt everything forever. Using the cosmic background radiation – the "echo of the Big Bang" – as a random number generation isn't a new idea, but a couple of scientists have run the slide-rule over measurements of the CMB power spectrum and reckon it offers a random number space big enough to beat any current computer.
Not in terms of protecting messages against any current decryption possibility: the CMB's power spectrum offers a key space "too large for the encryption/decryption capacities of present computer systems". A straightforward terrestrial radio telescope, this Arxiv paper states, should be good enough to make "astrophysical entropy sources accessible on comparatively modest budgets".
http://www.theregister.co.uk/2015/11/12/big_bang_left_us_with_a_perfect_random_number_generator/
(Score: 3, Interesting) by melikamp on Friday November 13 2015, @05:59PM
Very few practical PRNGs come with documentation suitable for mathematicians, let alone a thorough mathematical analysis, and the twister is no exception. This kind of goes with the territory, since on one hand we are trying to create something cryptographically secure, so it can't be too simple mathematically (actually, it kind of has to be convoluted just to resist the attempts to crack it), but on the other hand we are trying to make it reasonably fast and easy to code correctly.
I've been dabbling in PRNG research myself, and lately I am pretty unimpressed with all periodic PRNGs. Why settle for a period when we have a huge class of real numbers with essentially perfect properties: the normal numbers. One of the most interesting things I found out lately is that we get normal numbers when we concatenate the outputs of non-constant polynomials:
0.[f(1)][f(2)][f(3)]...
I conjecture that taking something like a 5th degree polynomial with 1000-digit coefficients will make a first grade monte-carlo PRNG: a provably normal sequence implemented in 2 lines of LISP or 20 lines of C, with reasonable speed & memory footprint. This is not a perfect solution from the crypto point of view, since we can roll it backwards, for one, but it's not too ugly either. I am really not that good with crypto, but it seems like if Charly starts reading the output from an unknown place, he's toast. He wouldn't even know where 5000 or so digits of f(n) end and those of f(n+1) begin, or indeed how many digits are in either, so guessing the state is far from a piece of cake.
Oh, and physics-based RNGs? One word: voodoo. What's good for a card game is not necessarily good for encryption or serious monte-carlo work. We (mathemnaticians) can't prove anything at all about numbers obtained from physical systems. I am sure a few physicists will claim that the quantum processes produce the true randomness a la Kolmogorov, but I am just not buying it. This seems like an extraordinary claim requiring a lot of evidence, and it's not even clear what kind of evidence could distinguish between a normal number and a "typical" rational with period 10^(10^10), which would make a difference between totally random and totally deterministic.
(Score: 0) by Anonymous Coward on Friday November 13 2015, @07:21PM
Not always, many applications of RNGs are not security related -- this is true for all applications of MT19937 because this is not a crypographically secure RNG (it is possible to determine the entire state of the generator by observing a handful of outputs).
All deterministic generators with bounded internal state will be periodic, because there are only finitely many possible states. If you generate enough outputs (more than the number of states), the generator must have repeated a state (by pigeon hole principle).
(Score: 2) by melikamp on Friday November 13 2015, @08:01PM
True, but of course there are very simple (non-halting) PRNGs with unbounded state. While technically bounded by the amount of available memory, they would not be bounded for any practical purpose. Like this one, for example, will print the most famous normal number, and won't run out of memory during our lifetimes:
; Using Common LISP for brevity, since having the long arithmetic really helps
(loop for x from 0 do (write x))
(Score: 2) by JoeMerchant on Friday November 13 2015, @09:57PM
5 1000 digit coefficients in 2 lines of code? Your monitor must be wider than mine.
🌻🌻 [google.com]
(Score: 2) by melikamp on Friday November 13 2015, @10:47PM
Well OK I meant the engine would fit into 2 lines. Here's a normal number printed by a 5th degree polynomial starting with p(x 0) and with coefficients ai :
(loop for x from x0 do (write (+ (* a5 (expt x 5)) (* a4 x x x x) (* a3 x x x) (* a2 x x) (* a1 x) a0)))
A generic state consisting of x and the coefficients would of course be many KiB, but of course it's not impossible to construct very large (non-generic) numbers quickly:
(expt 17 5000)
175633312108452721427154910593816375676045609188236147762172520926313101794626782377302959371185668182012124474768266306604248917384680807806747292682205706327215503961769087974347874640165762944001728597738340683565131284670575788748143866231551159686498529164599400846239981278615270503937793488580806658721202804281807054635951112907504929605445109539143506059421558862556445538020731806999633093042305375390661535397548186188359722677542179808885816588731936127218643639140365801564147090483867454453618553624775828498532004025435165448741825964917193729764165922701192888216794065640950423512843256411763281777945320998754729721884555541718397176355225703010383238024435800626063987134614462065403732660231342072837291206443476116603670199653489987679848862478846935043417196037431164309799400079790508606478813251682980006352221096750286975348109121230933525994636962933541395081273993469864500734110297241770420948833614171417329230122598315090109761690659280031012044865243874407114822664147257592623432654116599449304646288137778757203338682128403105312166782907518388167285439755453847363751166502631379670596798430845937039535447623509590468030323137066946856796935379197912644217029594115860854074935771345585184704373301849748566613193689138763679149561452923238919319638772662331219692427199125395731096771707168497391604287236115742516223987357937103839634451407001236040447203547136995985694892460991723457069383702445228969093822145109486906789026639918320490245755599683998095585127297241031190061204022875270887686252839020210211712169154657990736026710226339850420698394512386894379865146150863019264166856893763517860350169554503045225417960785146637386064190279519443935894697410337891638573966522504356407547460475444066388414884352420176752828409630299050590206071771426127643322001960002581803176902420999844839831174587339521358198795803924385754631860100520039828066064303471139304584911046045989339008351033521540532530569270839044739005330526718914657790718027280821592296613430481758002732284430460153868797091728276352908260317078133915312009449425835997822432454616608006853453350401960966064646756447320019117360389411391439965541982426068747741540989813986059814555213849989910607803919280164257909041865602294906920921681146589932261748790765236523314861238992658796426269836107535390268247536918766845976816061117199507574784898078209016708953021725491811963242729592560279999957972312183247487668073980051960842377251039253913335036326948294897532575295076409324552424290670885388876854518242746830052104741660458649796802994288178969550785944426942212761759761629583670742765723947321373617535406111245507333030398779754769441574514877729185675007932015210242382746728806982064749470453529454127372569007550564121383161649984487234982706965289643941242652698276888692091414163884067172633479640096267909812567164072306810473540472157017153388156168318249100092144563902987954263312189007040081249981863165047606815301894095801741242164263977977983854272252994000644471293686085939256540849642900999751121307978398745462437590183483874902215393338496926410324430086030708634674200722204979458059195450804167704388783966307047784146951568006533524749957739674673018801649837593125305519586523038286497824816823574252996315988586257489513329253365432866115320707115172290805547312473555181480796823554844931696882172285671191614680778662169300682478171059390782312961134037331146881605067229127438402954304991619585321855794388180388335037966158940297937636681454914894526018295822269239654261630129016241025639207851144843898941888142565093503336177896656603979127239011340388257777715792593515538442691165736674579252631904155815690510364895868523266977226037937076883264554570106327168988788362808023006778367678198260026687543048031439343329049912386407448774403354364481950230687659737861349416409383488355401457495516126078814054940444199039252923389473038724328061107690292994480219446676672720420515079572777012566338940400215780571339668241649781374396809924620882671477337968217432630896278471933541863784193488057966871793914262635142169767995136008387916675004251678144707365851843502125668268480493721475917212484122236621262451522315618953776969762410725679143974851786155299466206254182733980642613469283555849882375390208458159577529054311985282741027119213215400435797962035997928364507218358554234732569061653222940210448729100534501722823263110223320912133395116726595124349219370927716932359126979144248649671728123970706982510670289356817106369771576889715077717286309727625684088286043875925829576569501990707212512505716773955175244188333693166367426060106082268338286492759544576654882740073747589531157847387266800907118948558880021144340958991846110339075522166167379965123984458398090325282405745067439441508856555826504832585520305888976612772853535359059043269127979104154267286843636513913392310277099004392981566761533862959776796297712666807083359889063614166090530218032487690584535449814660374125284245843784055435388495021356698635724924278675525177262450838871550013502761842865823757189954680209176165142140267600467234107643161212849008680357734728786997246480183058318316366333813577230717087359194725919643928956278468035239826534426157148843377901224331418317991340920656177084922248280027560541334667582466664600425098435030170271758581828583498119210067195478204683184832876663453793279404719157892079220140821968978119281081913169674997713653884456598683826554698476432259869047623173196072427625121126216364020702961651669891448492145939734317039381874744536176661513901739078371264686483672560789801498973094388837135427649563835584022317066407952912476300380185569413414804306918237676145328082995274206308349230528913173655386784698362714288585780849346559927870551331556711878622808690431661198427464435899340401313300181379288349660725866965530214537256890330650174087174937067812646224052980930879643780528401385376015068289468949400760582595181958044455611426989333135918240692647062804185759340389331050492516816005585605294532148932699976324464041594917008337814060900347005883464822192868224304916159350147182396177631440826837303017736850976393921957658280400001
(Score: 2) by JoeMerchant on Saturday November 14 2015, @05:12AM
So, I like plotting series of recursive polynomial numbers (floating point) vs themselves, Poincaire style - you might like the results:
http://mangocats.com [mangocats.com]
🌻🌻 [google.com]
(Score: 2) by FatPhil on Sunday November 15 2015, @03:45PM
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves