Doğumgünü Akını - Doğumgünü Akını Nedir? Doğumgünü Akını Hakkında Bilgiler

Doğumgünü akını - Doğumgünü akını nedir? Doğumgünü akını Hakkında Bilgiler


Vikipedi, özgür ansiklopedi


Git ve: kullan, ara
Doğumgünü akını, olasılık kuramındaki doğumgünü probleminin ardındaki matematiği kullanan bir kriptografik akındır Akının amacı bir f işlevine girdi olarak verilen x1 ve x2'nin f(x1) = f(x2) koşulunu sağlamasıdır Böyle bir x1,x2 ikilisi çakışma olarak adlandırılmaktadır Çakışma bulma yöntemi, f işlevini gelişigüzel girdilerle hesaplayıp çakışma koşulunun sağlanıp sağlanmadığını incelemektir Bu yöntem, yukarıda sözü edilen doğumgünü probleminden yararlanır Şöyle ki; bir f(x) işlevi eşit olasılıklı H farklı sonuç üretiyorsa ve H yeterince büyükse f(x1) = f(x2) koşulunu sağlayan x1 ve x2 değerleri kolayca bulunabilir

Matematiksel ifadesi


Bir H kümesinden gelişigüzel n değerlerini seçtiğimizi varsayalım p(n;H) ifadesini de bir n değerinin birden çok kez seçilmesi olasılığı olarak tanımlayalım Böylece,

n(p;H), seçilebilecek en küçük sayıyı gösteriyorsa bir çakışmanın meydana gelme olasılığı en az p'ye eşittir Yukarıdaki eşitlik tersine çevrildiğinde aşağıdaki eşitliğe ulaşılır
5'lik bir çakışma olasılığı temel alındığında

Q(H)'nin ilk çakışma bulununcaya dek seçilen değer sayısını belirttiğini varsayalım Bu sayı,

Örneğin, 64 bitlik bir öz kullanıldığında ortaya çıkan farklı sonuç sayısı yaklaşık 18 × 1019'dur Tüm bu sonuçların gözlenme olasılıkları birbirine eşitse bir çakışmanın meydana gelmesi için en çok 51 × 109 denemeye gerek duyulacaktır Bu değer, doğumgünü sınırı olarak adlandırılır Bu değer, n bitlik kodlar için 2n / 2 olarak hesaplanmıştır[1] Diğer örnekler ise aşağıdaki tabloda gösterilmiştir
Bit sayısıOlası
sonuç sayısı
1%1%25%50%75%3243 × 109222299329 × 10393 × 10350 × 10477 × 10411 × 1056418 × 10196119 × 10261 × 10319 × 10561 × 10619 × 10861 × 10833 × 10951 × 10972 × 10912834 × 103826 × 101082 × 101126 × 101382 × 101426 × 101683 × 101726 × 101814 × 101922 × 101931 × 101925612 × 107748 × 102915 × 103148 × 103215 × 103448 × 103515 × 103748 × 103726 × 103840 × 103857 × 103838439 × 1011589 × 104828 × 105089 × 105128 × 105389 × 105428 × 105689 × 105648 × 105774 × 105710 × 105851213 × 1015416 × 106852 × 106916 × 107152 × 107216 × 107452 × 107516 × 107688 × 107614 × 107719 × 1077
Tablo, tüm öz değerlerinin oluşma olasılıklarının eşit olduğu durumda gerekli olan değer sayılarını göstermektedir
İşlev çıktılarının farklı yoğunlukta dağıldığı durumların çakışma olasılığını artırdığı kolayca gözlenebilmektedir Bir öz işlevinin 'dengesi' o işlevin doğumgünü akınlarına karşı direncini ifade etmekte, MD ve SHA gibi popüler özlerin zayıf noktalarının aydınlatılması çalışmalarını tetiklemektedir (Bellare ve Kohno, 2004)




Sayısal imzaların akına karşı duyarlığı


Sayısal imzalar, doğumgünü akınına duyarlı olabilmektedirler Bir m iletisi önce f(m) ile imlenmektedir Burada f bir kriptografik öz işlevini göstermektedir Alice'in Bob'u kandırmaya çalıştığını varsayalım Alice önce yasal bir m sözleşmesi hazırlar ve ardından sahte bir m' sözleşmesini imzalar Alice daha sonra m üzerinde bazı yazım değişiklikleri yaparak birden fazla m sözleşmesi elde etmeye çalışır
Alice, sahte m' sözleşmesini de aynı yolla çoğaltır ve öz işlevini yasal ve sahte sözleşmeler üzerine uygulayarak f(m) = f(m') koşulunun sağlandığı ilk değeri bulur Yasal sözleşmeyi Bob'a imzalatan Alice, bu imzayı sahte sözleşmeye ekler Böylece, Bob'un sahte sözleşmeye imza koyduğu "kanıtlanmış" olur
Bu akının önüne geçebilmek amacıyla imzayı oluşturan öz işlevinin çıktı uzunluğu artırılmaktadır Çalışma süresi katbekat artan bu akın böylece uygulanamaz hale dönüşmektedir
Pollard'ın rho algoritması, ayrık logaritmaların hesaplanmasında doğumgünü akınını kullanan bir yöntemdir

Kaynakça


İngilizce Vikipedi'deki 20022009 tarihli Birthday attack maddesi
Mihir Bellare, Tadayoshi Kohno: Öz İşlevinin Dengesi ve Doğumgünü Akınları Üzerindeki Etkisi EUROCRYPT 2004: s 401–418
Uygulamalı Kriptografi, 2 baskı, Bruce Schneier
CISSP Hepsi İçinde Çalışma Kılavuzu, 4 baskı, Shon Harris