birthday attack

• digital signaturelerin anasini belleme yontemi. asli $una dayanir:
  
  c(n,k) = choose(n,k) = [n!]/[k!(n-k)!] diye yazalim.
  
  iki ki$ilik bir sinifta ayni gun iki dogumgununun olma ihtimali kactir? 1/365.
  uc ki$ilik bir sinifta? a$agi yukari c(3,2)/365
  dort ki$ilik bir sinifta? yine a$agi yukari c(4,2)/365 (a$agi yukari diyoruz cunku bunu inclusion exclusion ile yapmak gerekir, biraz daha azdir)
  bu sayi boyle hayvanca artar.
  
  bu da ne demektir? herhangi bir hash fonksyonuna n mesaji tabi tutarsaniz, en az iki tanesinin e$it cikma olasiligi n buyudukce kat kat^** buyur. o zaman biz $ebek bir insansak ne yapariz? "ben sakip sabanci butun malvarligimi skatanic'e devrediyorum" diye bir yaziyi aliriz, hash fonksyonuna tabi tutariz, outputuna a diyelim. $imdi bir tebrik mesajini 500 degi$ik versyonla yazariz, "bayraminizi kutlarim", "bayraminizi ictenlikle kutlarim" ve bunun gibi. gordugumuz gibi buyuk ihtimalle birinden biri a output verecektir. bunu veren mesaji alip, sakip sabanci'nin sekreterine veririz, parayi yari-yariya kiri$acagimiza soz veririz, ve bu mesaja sabancinin imza^* atmasini saglariz.
  
  digital signature sadece hash fonksyonunun uzerine atildigi icin, sabanci'nin butun malvarligi elimizdedir. sekretere paranin yarisini verirsiniz vermezsiniz o sizin bileceginiz i$.
  
  bundan korunmak icin yapmamiz gereken $ey, ba$kasinin yazdigi bir mesaji imzalamadan once, bir-iki karakter degi$tirmek olacaktir. bu $ekilde, mesajda bir bo$luk ekleseniz bile hash fonksyon outputunda buyuk degi$iklikler olacagi icin, melun ki$iler emellerine ula$amayacaklardir.
• (bkz: dogum gunu paradoksu)
• önünüzde n tane arabanın bulunduğunu ve bu arabaları seçmesi için k kişilik 2 gruba ayrılmış kişilerden biri olduğunuzu düşünün.
  diğer gruptaki birisi ile aynı arabayı seçme ihtimaliniz nedir?
  
  versiyonu hash fonksiyonlarını alaşağı etmekte kullanılabilen olasılığın muğlak anlamlılığından beslenen bir yöntem.
  alice saray beklerken fred'in araya girip bataklık vermesinin önünü açan yöntemdir.
  bob napar bu esnada orası bilinmemektedir.
  
  odada 23 kişi var ve bu kişilerden 2sinin aynı gün doğmuş olma olasılığı %50 den fazladır. tabii ki hepsi farklı günde doğmuş olabilirler. meybi
  yıl 365 gün kbl edelim.
  
  odadakilerden 1 kişinin yılın belli bir günü doğduğunu kabullenip herhangi bir 2. kişinin o gün doğmamış olma olasılığını hesaplarsak 364/365 bulmuş oluruz.
  peki ya 3. kişi için belli 2 günden farklı günde doğmuş olma olasığı için ise 2 gün gitti ve 363/365 olarak bulduk.
  peki soru bu 3 kişinin farklı günlerde doğmuş olma olasılığı nedir dersek işler güzelce karışır ve
  (364/365)*(363/365) olarak bulunur.
  baştaki soruya dönersek yanı bu 23 kişinin aynı gün doğmuş olma olasılığına bakarsak bu yukarıdaki yöntem devam ettirilip bulunan sonuç 1 den çıkartılırsa elde edilir.
  
  1-(hepsinin farklı günlerde doğmuş olma olasılığı) bulunduğunda yaklaşık olarak %50 yapmaktadır.
  
  ilginçtir güzeldir ama tam bir .... dır.