From Wikipedia, the free encyclopedia
ഒരു ഗൂഢശാസ്ത്ര ആക്രമണമാണ് ജന്മദിനാക്രമണം (Birthday attack), സംഭാവ്യത സിദ്ധാന്തത്തിലെ ജന്മദിനപ്രശ്നത്തിനു പിന്നിലെ ഗണിതത്തെ ഫലപ്രദമായി ഉപയോഗപ്പെടുത്തി നടത്തുന്നതിനാലാണ് ഈ പേര് ലഭിക്കുവാൻ കാരണം. എന്ന ഫലനം ഉണ്ടെങ്കിൽ ഈ ആക്രമണത്തിലെ ലക്ഷ്യം എന്നത് സാധ്യമാകുന്ന രണ്ട് വ്യത്യസ്ത എന്ന ഇൻപുട്ടുകൾ കണ്ടുപിടിക്കലാണ്, അങ്ങനെയുള്ള എന്ന ജോഡി ഇൻപുട്ടുകളെ കൊളീഷൻ (collision) എന്ന് പറയുന്നു. ഒരു കൊളീഷൻ കണ്ടുപിടിക്കുന്നതിന് വേണ്ടി യാദൃച്ഛികമായോ, യാദൃച്ഛികം എന്ന രൂപേണയോ തിരഞ്ഞെടുക്കുന്ന വ്യത്യസ്ത ഇൻപുട്ടുകളിൽ ഫലനത്തിന്റെ ഫലങ്ങൾ കണ്ടുപിടിക്കുകയാണ് ഈ ആക്രമണത്തിൽ ചെയ്യുന്നത്. പ്രതേകിച്ച് എന്ന ഫലനത്തിന്റെ ഔട്ട്പുട്ടായി എന്ന വലിയ ഗണത്തിലെ വ്യത്യസ്ത അംഗങ്ങൾ ഒരേ സംഭാവ്യതയിലാണ് ലഭിമാകുന്നതെങ്കിൽ ജന്മദിനപ്രശ്നം അനുസരിച്ച് ഈ രീതി ഫലപ്രദമാണ്. ശരാശരി വ്യത്യസ്ത ശ്രമങ്ങൾക്ക് ശേഷം എന്നത് സാധ്യമാകുന്ന രണ്ട് വ്യത്യസ്ത എന്ന ഇൻപുട്ടുകൾ ലഭിക്കുമെന്നാണ് ഇതുവഴി പ്രതീക്ഷിക്കുക.
എന്ന ഗണത്തിൽ നിന്നും ഇൻപുട്ടുകൾ ഏകതാനമായും യാദൃച്ഛികമായും തിരഞ്ഞെടുക്കുന്നു എന്ന് കരുതുക, ഇതിൽ ആവർത്തനം അനുവദനീയവുമാണ്. എന്നത് ഒരു വില തന്നെ ഒന്നിൽ കൂടുതൽ തവണ തിരഞ്ഞെടുക്കപ്പെടുന്നു എന്നതിന്റെ സംഭാവ്യതയാണെങ്കിൽ, അത് ഇങ്ങനെയെഴുതാം
ഇവിടെ തിരഞ്ഞെടുക്കേണ്ട കുറഞ്ഞ എണ്ണം വിലകൾ ആണെങ്കിൽ, ഒരു കൊളീഷൻ കണ്ടെത്തുന്നതിനുള്ള ഏറ്റവും കുറഞ്ഞ സംഭാവ്യത ആണ്, മുകളിലെ വ്യജ്ഞകം വിപരീത രൂപത്തിലെഴുതുന്നതുവഴി ഇങ്ങനെ ലഭിക്കുന്നു.
ഇവിടെ സംഭാവ്യത 0.5 ആയി നൽകുകയാണെങ്കിൽ നമുക്ക് ലഭിക്കുക
ആദ്യത്തെ കൊളീഷൻ കണ്ടുപിടിക്കുന്നതിനു മുൻപ് എണ്ണം വിലകൾ തിരഞ്ഞെടുക്കേണ്ടി വരും എങ്കിൽ, ഈ സംഖ്യ ഏതാണ്ട് ഇങ്ങനെ കണ്ടെത്താം
ഉദാഹരണത്തിന്, ഇവിടെ 64 ബിറ്റ് ഹാഷാണ് ഉപയോഗിക്കപ്പെട്ടെതെങ്കിൽ മൊത്തം 1.8 × 1019 വ്യത്യസ്ത ഔട്ട്പുട്ടുകൾ ലഭ്യമാണ്. ഈ ഔട്ട്പുട്ടുകളെല്ലാം ഒരേ സംഭാവ്യതയിലാണ് നിലകൊള്ളുന്നതെങ്കിൽ ബ്രൂട്ട് ഫോഴ്സ് (brute force) രീതിയിൽ ഏകദേശം 5.1 × 109 ശ്രമങ്ങൾക്കൊണ്ട് ഒരു കൊളീഷൻ കണ്ടെത്തുവാൻ സാധിക്കുന്നതാണ്. ഈ വിലയെ ജന്മദിന നിബദ്ധം (birthday bound) എന്നു വിളിക്കുന്നു. പൊതുവായി n-ബിറ്റ് കോഡുകൾക്ക് ഈ വില ഉപയോഗിച്ച് കണ്ടെത്താവുന്നതാണ്.[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 |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.