ജന്മദിനാക്രമണം

വിക്കിപീഡിയ, ഒരു സ്വതന്ത്ര വിജ്ഞാനകോശം.

ഒരു ഗൂഢശാസ്ത്ര ആക്രമണമാണ് ജന്മദിനാക്രമണം (Birthday attack), സംഭാവ്യത സിദ്ധാന്തത്തിലെ ജന്മദിനപ്രശ്നത്തിനു പിന്നിലെ ഗണിതത്തെ ഫലപ്രദമായി ഉപയോഗപ്പെടുത്തി നടത്തുന്നതിനാലാണ് ഈ പേര് ലഭിക്കുവാൻ കാരണം. f എന്ന ഫലനം ഉണ്ടെങ്കിൽ ഈ ആക്രമണത്തിലെ ലക്ഷ്യം f(x_1)=f(x_2) എന്നത് സാധ്യമാകുന്ന രണ്ട് വ്യത്യസ്ത x_1,x_2 എന്ന ഇൻപുട്ടുകൾ കണ്ടുപിടിക്കലാണ്, അങ്ങനെയുള്ള x_1,x_2 എന്ന ജോഡി ഇൻപുട്ടുകളെ കൊളീഷൻ (collision) എന്ന് പറയുന്നു. ഒരു കൊളീഷൻ കണ്ടുപിടിക്കുന്നതിന് വേണ്ടി യാദൃച്ഛികമായോ, യാദൃച്ഛികം എന്ന രൂപേണയോ തിരഞ്ഞെടുക്കുന്ന വ്യത്യസ്ത ഇൻപുട്ടുകളിൽ f ഫലനത്തിന്റെ ഫലങ്ങൾ കണ്ടുപിടിക്കുകയാണ് ഈ ആക്രമണത്തിൽ ചെയ്യുന്നത്. പ്രതേകിച്ച് f(x) എന്ന ഫലനത്തിന്റെ ഔട്ട്പുട്ടായി H എന്ന വലിയ ഗണത്തിലെ വ്യത്യസ്ത അംഗങ്ങൾ ഒരേ സംഭാവ്യതയിലാണ് ലഭിമാകുന്നതെങ്കിൽ ജന്മദിനപ്രശ്നം അനുസരിച്ച് ഈ രീതി ഫലപ്രദമാണ്. ശരാശരി 1.25 \cdot \sqrt H വ്യത്യസ്ത ശ്രമങ്ങൾക്ക് ശേഷം f(x_1) = f(x_2) എന്നത് സാധ്യമാകുന്ന രണ്ട് വ്യത്യസ്ത x_1,x_1 എന്ന ഇൻപുട്ടുകൾ ലഭിക്കുമെന്നാണ് ഇതുവഴി പ്രതീക്ഷിക്കുക.

ഗണിതം[തിരുത്തുക]

പ്രധാന ലേഖനം: ജന്മദിനപ്രശ്നം

H എന്ന ഗണത്തിൽ നിന്നും n ഇൻപുട്ടുകൾ ഏകതാനമായും യാദൃച്ഛികമായും തിരഞ്ഞെടുക്കുന്നു എന്ന് കരുതുക, ഇതിൽ ആവർത്തനം അനുവദനീയവുമാണ്. p(n;H) എന്നത് ഒരു വില തന്നെ ഒന്നിൽ കൂടുതൽ തവണ തിരഞ്ഞെടുക്കപ്പെടുന്നു എന്നതിന്റെ സംഭാവ്യതയാണെങ്കിൽ, അത് ഇങ്ങനെയെഴുതാം

 p(n;H) \approx 1 - e^{-n(n-1)/(2H)} \approx 1-e^{-n^2/(2H)},

ഇവിടെ തിരഞ്ഞെടുക്കേണ്ട കുറഞ്ഞ എണ്ണം വിലകൾ n(p;H) ആണെങ്കിൽ, ഒരു കൊളീഷൻ കണ്ടെത്തുന്നതിനുള്ള ഏറ്റവും കുറഞ്ഞ സംഭാവ്യത p ആണ്, മുകളിലെ വ്യജ്ഞകം വിപരീത രൂപത്തിലെഴുതുന്നതുവഴി ഇങ്ങനെ ലഭിക്കുന്നു.

n(p;H)\approx \sqrt{2H\ln\frac{1}{1-p}},

ഇവിടെ സംഭാവ്യത 0.5 ആയി നൽകുകയാണെങ്കിൽ നമുക്ക് ലഭിക്കുക

n(0.5;H) \approx 1.1774 \sqrt H.

ആദ്യത്തെ കൊളീഷൻ കണ്ടുപിടിക്കുന്നതിനു മുൻപ് Q(H) എണ്ണം വിലകൾ തിരഞ്ഞെടുക്കേണ്ടി വരും എങ്കിൽ, ഈ സംഖ്യ ഏതാണ്ട് ഇങ്ങനെ കണ്ടെത്താം

Q(H)\approx \sqrt{\frac{\pi}{2}H}.

ഉദാഹരണത്തിന്, ഇവിടെ 64 ബിറ്റ് ഹാഷാണ് ഉപയോഗിക്കപ്പെട്ടെതെങ്കിൽ മൊത്തം 1.8 × 1019 വ്യത്യസ്ത ഔട്ട്പുട്ടുകൾ ലഭ്യമാണ്. ഈ ഔട്ട്പുട്ടുകളെല്ലാം ഒരേ സംഭാവ്യതയിലാണ് നിലകൊള്ളുന്നതെങ്കിൽ ബ്രൂട്ട് ഫോഴ്സ് (brute force) രീതിയിൽ ഏകദേശം 5.1 × 109 ശ്രമങ്ങൾക്കൊണ്ട് ഒരു കൊളീഷൻ കണ്ടെത്തുവാൻ സാധിക്കുന്നതാണ്. ഈ വിലയെ ജന്മദിന നിബദ്ധം (birthday bound) എന്നു വിളിക്കുന്നു. പൊതുവായി n-ബിറ്റ് കോഡുകൾക്ക് ഈ വില 2^{n/2} ഉപയോഗിച്ച് കണ്ടെത്താവുന്നതാണ്.[1] കുറച്ച് ഉദാഹരണങ്ങൾ പട്ടികയിൽ നൽകിയിരിക്കുന്നു.

ബിറ്റുകൾ സാധ്യമായ
ഔട്ട്പുട്ടുകൾ
(H)
യാദൃച്ഛിക കൊളിഷൻ കണ്ടെത്തുന്നതിനു വേണ്ട സംഭാവ്യത (p)
10−18 10−15 10−12 10−9 10−6 0.1% 1% 25% 50% 75%
32 4.3 × 109 2 2 2 2.9 93 2.9 × 103 9.3 × 103 5.0 × 104 7.7 × 104 1.1 × 105
64 1.8 × 1019 6.1 1.9 × 102 6.1 × 103 1.9 × 105 6.1 × 106 1.9 × 108 6.1 × 108 3.3 × 109 5.1 × 109 7.2 × 109
128 3.4 × 1038 2.6 × 1010 8.2 × 1011 2.6 × 1013 8.2 × 1014 2.6 × 1016 8.3 × 1017 2.6 × 1018 1.4 × 1019 2.2 × 1019 3.1 × 1019
256 1.2 × 1077 4.8 × 1029 1.5 × 1031 4.8 × 1032 1.5 × 1034 4.8 × 1035 1.5 × 1037 4.8 × 1037 2.6 × 1038 4.0 × 1038 5.7 × 1038
384 3.9 × 10115 8.9 × 1048 2.8 × 1050 8.9 × 1051 2.8 × 1053 8.9 × 1054 2.8 × 1056 8.9 × 1056 4.8 × 1057 7.4 × 1057 1.0 × 1058
512 1.3 × 10154 1.6 × 1068 5.2 × 1069 1.6 × 1071 5.2 × 1072 1.6 × 1074 5.2 × 1075 1.6 × 1076 8.8 × 1076 1.4 × 1077 1.9 × 1077
Table shows number of hashes n(p) needed to achieve the given probability of success, assuming all hashes are equally likely. For comparison, 10−18 to 10−15 is the uncorrectable bit error rate of a typical hard disk [1]. In theory, MD5, 128 bits, should stay within that range until about 820 billion documents, even if its possible outputs are many more.

അവലംബം[തിരുത്തുക]

  1. Jacques Patarin, Audrey Montreuil (2005). Benes and Butterfly schemes revisited (PostScript, PDF). Université de Versailles. ശേഖരിച്ചത്: 2007-03-15. 
"http://ml.wikipedia.org/w/index.php?title=ജന്മദിനാക്രമണം&oldid=1734764" എന്ന താളിൽനിന്നു ശേഖരിച്ചത്