Pearson Hashing’de Collision Bulmak

Pearson Hashing bildiğiniz üzere 8bitlik bir hash fonksiyonudur. Pearosn Hashing kriptografik bir hash fonksiyonu değildir bu yüzden collision bulmak oldukça kolaydır. Sadece 0 ile 255 arasındaki değerleri verir çıktı olarak. Bu küçük uzay da bize kolayca Collision bulmamıza sebep olmakta.

Pigeonhole prensibini kullanırsak çakışma bulmak için hesaplamamız gereken hash sayısı 8 bitlik olduğu için bir fazlası olmalıdır yani 2⁸+1. 257 değer denememiz gerekmektedir kesin olarak bir çakışma bulmamız için.

Bir de Birthday paradoksundan yararlanırsak %100’lik bir oranda Collision yakalamak için yaklaşık 46 değere bakmak yeterli olacaktır. %50 için 2^(8/2) 16 değer yeterli olacaktır.

İyice Garanti olsun diye 66 değer üzerinden gidip şu kodu çalıştırırsak:

Çalışma çıktısı olarak da şunu verelim ve 1’de çakışma bulduğumuzu gösterelim:

8 bitte Collision bulmak oldukça kolay ancak günümüz hash fonksiyonları gibi 128,256,512 bit gibi büyüklükte uzaylar kullanırsanız bulmak için evdeki bilgisayarınızın yetmediği durumlar oluşur.

Originally published at anilkaynr.wordpress.com on November 6, 2018.