Przykład 1
- n 10000
- 32 bity
0.011642
Jakie P kolizji przy 10000 i 32 bitach? 0.011642. Birthday, nie atak.
Prawdopodobieństwo kolizji hasha
Wpisz n i bity. 10000 i 32 dają 0.011642. 100000 i 32 dają 1. 2000000 i 64 dają 1.0842e-7. Przybliżenie urodzin, nie atak.
To p ≈ 1 − exp(−n(n−1)/(2×2^b)). Nie atak na funkcję skrótu. Bity hasła są na entropii hasła.
Wynik
Wprowadź dane i kliknij Oblicz.
Jak to działa?
Prawdopodobieństwo kolizji hasha na tej karcie to przybliżenie paradoksu urodzin. 10000 i 32 bity dają 0.011642. 100000 i 32 dają 1. 2000000 i 64 dają 1.0842e-7. Karta nie łamie MD5 i nie szuka preimage.
Pole hash-n jest liczbą elementów. Pole hash-b jest bitami skrótu. hash-target-p i hash-show-log10 są w fill. Wzór to 1 − exp(−n(n−1)/(2×2^b)). 10000 przy 32 bitach zostawia 0.011642. Duże n przy 32 bitach saturuje kartę do 1.
0.011642 nie jest atakiem. 1 nie znaczy, że ktoś złamał hash. 1.0842e-7 przy 64 bitach nadal jest przybliżeniem. Wpisujesz n i b sam. To nie laboratorium krypto.
Entropia hasła obok mnoży długość przez log2. Base64 liczy narzut. Tu 10000 i 32 zostają 0.011642, sam birthday.
Wpisz 10000 i 32, zostaw próg 0.01 i log10 wyłączone, potem Oblicz. Wynik to 0.011642. 100000 przy 32 daje 1.
10000 i 32 dają 0.011642. 100000 i 32 dają 1. 2000000 i 64 dają 1.0842e-7. Inne n przy 32 zmienia 0.011642.
Wzór
p ≈ 1 − exp(−n(n−1)/(2×2^b)). Przybliżenie urodzin, nie atak na hash.
Jak korzystać
- Wpisz n 10000 i bity 32.
- Zostaw próg 0.01 i log10 wyłączone. Kliknij Oblicz. Wynik to 0.011642.
- 100000 i 32 dają 1. 2000000 i 64 dają 1.0842e-7.
- To przybliżenie urodzin, nie atak.
- Sąsiednia karta liczy bity hasła, nie kolizję.
10000 i 32 dają 0.011642
Birthday p ≈ 1 − exp(−n(n−1)/(2×2^b)). 10000 i 32 dają 0.011642. To nie atak.
- Prawdopodobieństwo
- Wynik P. 10000 i 32 zostawiają 0.011642. Nie laboratorium.
- kolizji
- Dwa wejścia, jeden skrót. 100000 i 32 dają 1. Nie preimage.
- hasha
- Bity w hash-b. 2000000 i 64 dają 1.0842e-7. Nie atak.
Przykłady
Przykład 2
- n 100000
- 32 bity
1
Jakie P przy 100000 i 32? 1.
Przykład 3
- n 2000000
- 64 bity
1.0842e-7
Jakie P przy 2000000 i 64? 1.0842e-7.
Powiązane kalkulatory
Najczęstsze pytania
Ile przy 10000 i 32 bitach?
0.011642. Przybliżenie urodzin, nie atak.
Ile przy 100000 i 32?
1. Duże n przy krótkim skrócie saturuje kartę.
Ile przy 2000000 i 64?
1.0842e-7. Ten sam wzór, dłuższy skrót.
Czy to atak na MD5 albo SHA?
Nie. Karta nie szuka kolizji w funkcji. Samo P z n i b.
Po co hash-target-p i log10?
Są w fill. Extras trzymają P z n i b, z log10 wyłączonym.
Czy 0.011642 jest dokładne?
To przybliżenie 1 − exp(...). Nie enumeracja par.
Czym to różni się od entropii hasła?
Tam 12 i 95 dają 78.8 bits. Tu 10000 i 32 dają 0.011642.
Czy zero w n liczy?
Nie. n i bity muszą być dodatnie.
Czy preimage jest na karcie?
Nie. Tylko P kolizji z paradoksu urodzin.
Paradoks dnia urodzin
Kolizja hasha występuje, gdy dwa różne wejścia dają tę samą wartość skrótu. Przykład intuicyjny: dwa różne pliki z tą samą sumą kontrolną CRC32 — narzędzie „myśli”, że to ten sam obiekt, choć bajty się różnią.
W grupie 23 osób jest już ponad 50% szans, że dwie mają urodziny w ten sam dzień — mimo że rok ma 365 dni. To samo dzieje się z hashami: liczba par do porównania rośnie znacznie szybciej niż liczba elementów, dlatego kolizje pojawiają się dużo wcześniej, niż intuicja by wskazywała.
Wzór przybliżony
Kalkulator używa uproszczonej granicy urodzinowej: P ≈ n² / (2 × 2^b), gdzie n to liczba elementów, a 2^b to liczba możliwych wartości skrótu o długości b bitów. Wynik jest przycinany do maksymalnie 100%. Przy n = 2^(b/2) wzór daje ok. 50% — to praktyczna reguła: "połowa punktu urodzinowego to pierwiastek z liczby możliwych skrótów".
Typowe rozmiary skrótów
| Algorytm | Długość (bity) | Status |
|---|---|---|
| CRC32 | 32 | Kontrola integralności, nie kryptograficzny. |
| MD5 | 128 | Złamany kryptograficznie — nie używać do bezpieczeństwa. |
| SHA-1 | 160 | Wycofywany — praktyczne kolizje wykazane od 2017 r. |
| SHA-256 | 256 | Powszechny standard, uznawany za bezpieczny. |
Znaczenie dla bezpieczeństwa
- Krótkie skróty (32-64 bity) świetnie nadają się do wykrywania błędów transmisji, ale przy milionach elementów kolizje są praktycznie gwarantowane.
- Dla identyfikatorów, deduplikacji plików czy cache — kolizja to zwykle drobna niedogodność (odporność na to zapewnia dodatkowe porównanie danych).
- Dla podpisów cyfrowych, certyfikatów i kontroli integralności bezpieczeństwa kolizja to realne zagrożenie (atakujący może podstawić złośliwe dane o tym samym skrócie) — tam liczą się tylko algorytmy odporne kryptograficznie (SHA-256 i nowsze).
Ograniczenia przybliżenia
Wzór urodzinowy jest przybliżeniem górnej granicy — dokładne prawdopodobieństwo jest odrobinę niższe, szczególnie gdy n jest bliskie 2^b. To narzędzie liczy prawdopodobieństwo kolizji jakiejkolwiek pary, nie odporność na atak "preimage" (znalezienie danych dających konkretny, wybrany skrót) — to inny, znacznie trudniejszy problem kryptograficzny.
Przykłady
- 10 000 elementów, hash 32-bitowy → ok. 1,16% szans na kolizję.
- 65 536 elementów, hash 32-bitowy → dokładnie 50% szans na kolizję (punkt urodzinowy).
- 1 000 000 elementów, hash 64-bitowy → ok. 2,7 × 10⁻⁸ — praktycznie zerowe ryzyko.
FAQ — kolizje hasha
- Co to jest kolizja hasha?
- To sytuacja, w której dwa różne dane wejściowe dają identyczny skrót (hash). Każda funkcja skrótu ma to nieuniknione ze względu na skończoną liczbę możliwych wyjść.
- Dlaczego 32-bitowy hash ma tak wysokie ryzyko kolizji już przy tysiącach elementów?
- Bo liczba par do porównania rośnie w tempie n², nie n — to właśnie efekt paradoksu dnia urodzin. Przy 4 miliardach możliwych wartości (2^32) kolizja jest prawdopodobna już przy ok. 65 tysiącach elementów.
- Czym różni się kolizja od ataku "preimage"?
- Kolizja to znalezienie jakiejkolwiek pary danych z tym samym skrótem. Preimage to znalezienie danych dających konkretny, wybrany skrót — znacznie trudniejszy problem, nieliczony przez ten kalkulator.
- Jaki rozmiar hasha jest bezpieczny dla mojego przypadku?
- Do deduplikacji i cache — 64 bity zwykle wystarczą. Do bezpieczeństwa kryptograficznego (podpisy, certyfikaty, hasła) — używaj SHA-256 (256 bitów) lub wyżej, nigdy MD5/SHA-1.
- Co pokazuje log₁₀(P)?
- Logarytm dziesiętny prawdopodobieństwa — przydatny, gdy P jest ekstremalnie małe (np. 10⁻²⁰), bo łatwiej porównywać rzędy wielkości niż same ułamki.
- Czy wynik jest dokładny?
- To przybliżenie górnej granicy z paradoksu urodzin — bardzo bliskie dokładnej wartości dla typowych zakresów, ale nie identyczne matematycznie.
- Dlaczego MD5 i SHA-1 są uznawane za niebezpieczne?
- Nie dlatego, że są "krótkie" w sensie tego kalkulatora, ale dlatego, że znaleziono metody generowania kolizji znacznie szybciej niż przewiduje sam paradoks urodzin — czyli słabości w samym algorytmie, nie tylko w długości skrótu.
- Czy mogę użyć tego do oszacowania ryzyka kolizji UUID?
- Tak — UUID v4 to w praktyce 122 bity losowości; podając b=122 i szacowaną liczbę wygenerowanych UUID otrzymasz orientacyjne prawdopodobieństwo kolizji.