skatanic

  • 1554
  • 0
  • 0
  • 0
  • 12 yıl önce

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.

devamını okuyayım »
24.11.2002 10:22