De hoeveelste macht van 10 wordt als "onmogelijk" beschouwd?

[Patrick4WF]

Ik heb ooit ergens gelezen dat het volgende door wiskundigen als onmogelijk beschouwd wordt....
 
Trek uit een boek van 52 kaarten een kaart en stop ze er terug in.
Doe dat 30 keer na mekaar.
De kans dat je 30 keer na mekaar dezelfde kaart trekt zou iets zijn van 1/ 10⁴³?
Heb dat niet nagerekend...
 
Wiskundigen zouden dit in principe beschouwen als onmogelijk.
En mocht het wel kunnen wat dan met 60 dagen (2 maanden)?
 
Puur theoretisch kan het natuurlijk wel maar praktisch lijkt het mij nonsens om dat als een reële mogelijkheid te beschouwen...
 
Dank voor het neerpennen van eventuele opinies hierover...

[Benm]

Het is, denk ik, een kwestie van toepassing. 
 
In sommige gevallen kun je dingen heel snel testen, bijvoorbeeld iets als een wachtwoord waarvan je de hash weet, maar niet het oorspronkelijke wachtwoord. In eerste instantie zou je denken dat 1 ronde hashing het compleet onmogelijk maakt om van hash naar het originele wachtwoord te komen, maar er zijn genoeg methodes om zoiets toch te kunnen doen. 
 
Zonder slimme methodes, dus domweg bruteforcen van een wachtwoord dat compleet random is, is niet heel eenvoudig. Als je iets hebt dat 6 karakters lang is,  met onderscheid tussen hoofdletters en de mogelijkheid tot gebruik van getallen heb je 62^6 mogelijkheden. Dat geeft een respectabele 56 miljard mogelijke wachtwoorden van 6 karakters lang, Hoe goed dat is? Niet bijster gezien een gewone computer die dingen kan checken met een snelheid van pakweg 100 miljoen per seconde is dat met een paar weken wel gedaan.. door dom te raden zonder enige aanname van hoe mensen in de werkelijkheid een wachtwoord maken. 
 
Maar de vraag is dan wat 'onmogelijk' is om praktisch uit te rekenen, ofwel wat "veilig" wordt bevonden. Voor encryptie en dergelijke is her een soort regel dat iets bij 2^40 pogingen compleet onveilig is. Dit was ooit een issue waarbij encryptie in principe 2^64 bits had, maar door fouten in implementatie een behoorlijk aantal van die bits verloor en het daarmee eenvoudig te kraken maakte. 
 
Tegenwoordig zou je iets eerder als veilig beschouwen met 256 bit sleutels, en 2^256 ~ 10^80 - een stuk stricter dan de kans dat je 30 kaarten opeenvolgend gelijke kaarten uit een dek trekt met schudden tussendoor, al weet ik niet of de kans daarop werkelijk ~10^43 is. Ergens geloof ik wel dat dat getal klopt, de kans dat je een compleet dek van 52 kaarten precies gelijk neerlegt is in de orde van 10^68.  

[EvilBro]

Ik heb ooit ergens gelezen dat het volgende door wiskundigen als onmogelijk beschouwd wordt....

Misschien heb je dat ooit ergens gelezen, maar het is onzin.
 

De kans dat je 30 keer na mekaar dezelfde kaart trekt zou iets zijn van 1/ 10⁴³?

\(\frac{1}{52^{29}} \approx 10^{-49.76}\)

Hieruit zal ook een verwachtingswaarde voor het aantal pogingen volgen van ongeveer \(10^{49}\).
 

En mocht het wel kunnen wat dan met 60 dagen (2 maanden)?

In 61 dagen zit het volgende aantal seconden:

\(61 \cdot 24 \cdot 60 \cdot 60 = 5270400 \approx 5 \cdot 10^6\)

Het verschil in ordegrootte tussen dit en de verwachtingswaarde is enorm. Het is niet waarschijnlijk dat je voldoende pogingen kunt doen in 2 maanden om toevallig een serie van 30 te krijgen.
 

In eerste instantie zou je denken dat 1 ronde hashing het compleet onmogelijk maakt om van hash naar het originele wachtwoord te komen, maar er zijn genoeg methodes om zoiets toch te kunnen doen.

Vanuit een hash kun je het oorspronkelijke wachtwoord niet terughalen. Meerdere wachtwoorden hebben immers dezelfde hash. Je kunt wel een wachtwoord vinden dat dezelfde hash heeft als het (onbekende) oorspronkelijke wachtwoord.

[Patrick4WF]

In 61 dagen zit het volgende aantal seconden:

\(61 \cdot 24 \cdot 60 \cdot 60 = 5270400 \approx 5 \cdot 10^6\)

Het verschil in ordegrootte tussen dit en de verwachtingswaarde is enorm. Het is niet waarschijnlijk dat je voldoende pogingen kunt doen in 2 maanden om toevallig een serie van 30 te krijgen.

 
Wat ik bedoelde is de grootte van de kans om na 60 keer trekken en schudden, opnieuw dezelfde kaart te trekken...

[Benm]

Vanuit een hash kun je het oorspronkelijke wachtwoord niet terughalen. Meerdere wachtwoorden hebben immers dezelfde hash. Je kunt wel een wachtwoord vinden dat dezelfde hash heeft als het (onbekende) oorspronkelijke wachtwoord.

 
Dat klopt inderdaad, je vindt maar 1 van de mogelijke oorspronkelijke wachtwoorden. Maar bij 256 bits hashes heb je wel goed kans dat de kortste mogelijkheid het wachtwoord is: ik vermoed dat er net eens twee wachtwoorden van 6 karakters lang zijn met dezelfde sha1 of md5 hash, maar pin me daar niet op vast. 

[tempelier]

Misschien wordt er aan onwaarschijnlijkheidsprincipe van Borel gedoeld?

[Benm]

Ik ken vooral de cryptografische kant van het verhaal, en hoe 'goed' iets moet zijn om als 'onkraakbaar' gezien te worden. 
 
Vaak worden er hier forse marges gebruikt voor het geval dat er onvoorziene zwaktes in een algoritme of implementatie zitten. Dat kan behoorlijk verschillen qua 'onmogelijkheid'. Neem bijvoorbeeld de 160 bits SHA-1 hashes: bij foutloze implementatie kost het  je pakweg 10 miljoen jaar om 2 documenten te maken met dezelfde hash maar verschillende inhoud. Als gevolg van fouten in implementatie kun je 2 pdf's maken met verschillende inhoud maar gelijke hashes in pakweg 100 jaar. Deze jaren zijn jaren op een snelle grafische processor, per stuk. Die 100 jaar werk kun je met 1000 processors dus ook in 1 maand doen. 
 
Dingen met fysieke kaarten hebben hun beperking in de snelheid waarmee je het zou kunnen doen. Uiteraard kun je het in software simuleren, of in enige mate gewoon beredeneren: Als je de eerste 51 kaarten in de correcte volgorde trekt is de kans dat de 52e ook correct is 100%, er is tenslotte maar 1 kaart over om te kiezen. Als je de eerste 50 correct trekt is de kans dat de laatste 2 correct zijn ook groot, 50%. 
 
30 kaarten is daarmee een heel lastige situatie, met een kans van 1/52, 1/51... 1/21. As je dat punt eenmaal voorbij bent neemt de kans weer toe dat je het restant ook correct pakt, waarbij het na 50 kaarten nog maar 1/2 is voor de volgende ronde. 

[Professor Puntje]

Misschien wordt er aan onwaarschijnlijkheidsprincipe van Borel gedoeld?

 
Dat wordt besproken in dit boek:
 
https://books.google.nl/books?id=kXYaBQAAQBAJ&printsec=frontcover&dq=onwaarschijnlijkheidsprincipe&hl=nl&sa=X&ved=0ahUKEwi7w4Dxo-bfAhVQKuwKHW9dCyQQ6AEIKDAA#v=snippet&q=Borel&f=false
 
Ik heb dat boek inmiddels ook zelf aangeschaft, maar ik moet het nog lezen.