A születésnap paradoxon egy érdekes paradoxon a szó hétköznapi értelmében. Matematikai értelemben nem paradoxon, azért nevezik paradoxonnak, mert ellent mond a „józan észnek”.
A születésnap paradoxon azt mondja ki, hogy (bizonyos fontos elhanyagolásokkal) igaz, hogy amennyiben egy teremben 23 személy tartózkodik legalább kettő ugyan azon a napon tartja a születésnapját több, mint 50%. 60 személy estén ez a valószínűség már 99% felett van.
Ez az állítás azért megdöbbentő, mert egy év 365 és 1/4 napból áll, és a 24 ennek a számnak kevesebb mint 10%-a, és mégis 50% a valószínűsége, hogy két ember ugyan azon a napon született.
Játszunk egy kicsit a számokkal:
Tettünk néhány egyszerűsítést az egyszerűbb számítás érdekében:
- Az egy évet tekintsük 365 naposnak (tekintsünk el a szökőévektől)
- Tekintsünk el a születések számának éven belüli hullámzásától, tételezzük fel, hogy, az év bármely napján ugyan annyi ember születik.
- Tekintsünk el attól, hogy a vizsgált személyek között ikrek is lehetnek
Azt józan ésszel is könnyű belátni, hogy ha az év egyes időszakaiban több ember születik (az eloszlás nem egyenletes), a várt esemény valószínűsége megnő.
Ezt a jelenséget használják ki az úgynevezett „születésnapi támadás” esetén. Ilyenkor a támadó figyeli a megtámadott titkosított adatforgalmat, esetleg valamilyen módszerrel még az adatforgalmat forszírozza is. Megpróbál annyi adatforgalmat összegyűjteni, amely már nagy valószínűséggel tartalmaz azonos tartalmú titkosított blokkokat.
Most elővezethetném a levezetést, hogy egy kulccsal legfeljebb hány blokknyi adatot lehet titkosítani, azonban ezt hagyjuk meg a titkosítási rendszerek tervezőinek.
Szuperhatékony módszerek
Az a tény, hogy ha egy helyiségben 60 személy tartózkodik már 99% a valószínűsége, hogy ketten ugyan azon a napon ünneplik a születésnapjukat a szuperhatékony módszerek demonstrálására alkalmas.
Ha szükségünk van egy olyan csoportra, ahol két ember egy napon ünnepli a születésnapját (tételezzük fel, hogy ezt csak a helyszínen tudjuk ellenőrizni), akkor 166 (365+1) embert kell meghívnunk. Amennyiben megelégszünk a 99%-os valószínűséggel elég csak 60-at.
Ez bizonyos esetekben nagyon komoly megtakarításokat eredményezhet.