Collision Resistance ( ගැටුම් ප්‍රතිරෝධය) . (තුන්වන කොටස)

ගුප්ත ලේඛන හැශ් ශ්‍රිතයකින් ( Cryptographic Hash Function ) අපිට අවශ්‍ය වන පළමු ගුණංගය නම් එය ගැටිමට ප්‍රතිරෝධී විමයී. ( collision Resistance ) එකිනෙකට වෙනස් Input දෙකක් එකම Output එක ලබා දෙන විට ගැටුමක් ඇති වේ. Hash function එකක  ඝට්ටනය (Collision) කිසිවෙකුට සොයගත නොහැකි නම්  එය ඝට්ටනය ප්‍රතිරෝධී වේ.

ඝට්ටක ප්‍රතිරෝධය (Collision Resistance ) : X සහ Y ලෙස Input  දෙකක් දී ඇති විට Out put එක ලෙස එක Hash function එකක් ලැබෙයි නම් එය නැවත පසු පසට කිරිමේ දී අපට 2ක් සොය ගැනිමට නොහැකි නම් ඝට්ටක ප්‍රතිරෝධය නම් වේ.

එනම්, X=/=Y නමුත් H(X) = H (Y)

ඇත්ත වශයෙන්ම , ඔනැම හැශ් ශ්‍රිතයක් සදහා ගැටිම් පවතින අතර අපට මෙය සරල ගණන් කිරිමේ තර්කයකින් පසු ඔප්පු කළ හැක. Hash Function  එකේ Input  Space හී ඕනැම විශාලත්වයකින් යුත් සියලුම මෙවලම් අඩංගු වේ නමුත් Output Space (අවකශයේ) අඩංගු වන්නෙ නිශ්චිත දිගකින් සහ ප්‍රමාණයකින් සංයුත්ත වූ  මෙවලමකි. එනම් Input Space , Output Space  එකට සම්බන්ධ වන Input තිබිය යුතුය.ඇත්ත වශයෙන්   Input  විශාල ප්‍රමාණයක් සම්බන්ධ වන Output  කිහිපයක් ඇත.

අපි අහඹු Input තෝරාගෙන හෑශ් අගයක් ගණනය කරන්නෙ නම්, 2^256 +1 යෙදුම් ( Input ) පරික්ෂ කිරිමට බෝහෝ  කලකට පෙර ඉහළ සම්භවිතාවක් සමග ගැටීමක් සොයා ගෙන ඇත. ඇත්ත වශයෙන්ම අපි අහඹු ලෙස 2^130 +1 යෙදුම්  (Input ) තෝරා ගත්තෙ නම්, අවම වශයෙන් ඒවායින් 2කක් ගැටිමට 99.8 සම්භවිතාවක් ඇති බව පේනේ. මෙය තවදුරටත් පැහැදිලි කරගැනීමට Birthday Paradox මගින් වඩාත් සවිස්තරාත්මක විමස බලන්න.

(https://en.wikipedia.org/wiki/Birthday_problem , https://betterexplained.com/articles/understanding-the-birthday-paradox/)

මෙම ඝට්ටනය හදුනගැනිමේ ඇල්ගෙරිතම සෑම හැශ් ශ්‍රිතයක් සදහම ක්‍රියා කරයි. එහෙත් ඇත්ත වශයෙන්ම , ගැටලුව වන්නෙ එය කිරිමට බෝහෝ කලයක් ගත විමයී. 256 Bit Output  සහිත  Hash ශ්‍රිතයක් සදහා , ඔබට හැශ් ශ්‍රිතය  2^256 +1 වරක් ගණනය කළ යුතුය . විශාල සංඛ්‍යාවකි.පරිගණකයක්  තත්පරයකට හැශ් 10000 ක් ගණනය කරන්නෙ නම්, හැශ් 2^128ක් ගණනය කිරිමට වසර ඔක්ටිලියනයක් (10^27 (octillion)) ගතවනු ඇත. මේ ගැන තවත් ආකාරයට සිතිමේ දී , මනව වර්ගයා විසින් මෙතෙක් නිර්මාණය කරන ලද සෑම පරිගණකයක්ම පරිගණක ගත වී ඇති බව අපට පැවසිය හැකිය, එසේ වුවත් තවමත් ගැටීම අසිමිත වී ඇති  බව අපට පැවසිය හැකිය. එසේ වුවත් තවමත් ගැටිම අසිමිත ලෙස කුඩා වේ. එය කොතරම් කුඩා ද යත් ඉදිරි තප්පර දෙකේ දී යෝධ උල්කපාතයක් වැටී පෘථිවිය විනාශ කිරිමට ඇති ඉඩ මෙන් ය.

මේ අනුව ඕනැම ශ්‍රිතයක් සදහා ගැටීමක් සෙවිමට සමාන්‍ය නමුත් ප්‍රායෝගික නොවන  ඇල්ගොරිදම සොයාගෙන ඇත, ප්‍රශ්නය නම් ඝට්ටනයක් සොයා ගැනිමට විශෙෂිත හැශ් ශ්‍රිතයක් භාවිතා කළ හැකි වෙනත් ක්‍රමයක් තිබෙද? වෙනත් වචන වලින් කිවහොත් සමාන්‍ය ඝට්ටන හදුනගැනිමේ කාර්යක්ෂමව සොයා ගත හැකි වෙනත් ඇල්ගෝරිදමක් තිබිය හැක උදහරණයක් ලෙස, පහත හැශ් ශ්‍රිතය සලකා බලන්න  :

මෙම උදහරණයෙන් පෙන්නුම් කරන්නෙ අපගෙ සමාන්‍ය ඝට්ටන හදුනගැනිමේ ක්‍රමය , ප්‍රායෝගිකව භාවිතා කළ නොහැකි වුවද, කාර්යක්ෂම ඝට්ටන හදුනාගැනිමේ ක්‍රමයක් පවතින බවයි.

වෙනත් හැශ් ශ්‍රිත සදහා , එවැනි ක්‍රම තිබේදැයි අපි නොදනිමු, ඒවා ගැටිම්වලට ඔරොත්තු දෙන බවට තවම සැක කේරේ, කේසේ වෙතත්, කිසිදු හැශ් ශ්‍රිතයක් ගැටිමට ප්‍රතිරෝධී බව ඔප්පු වී නොමැත , ප්‍රායෝගික භාවිතා කරන ගුප්ත ලේඛන හැශ් ශ්‍රිතයෙන් ඝට්ටනය කිරිමට  උත්සහ කරමින් සිටින අතර එය   තවමත් සාර්ථක වී නොමැත  ඒ බැවින් එහි ඝට්ටක ප්‍රතිරෝධය තවමත් මිනිසුන් විශ්වාස කර්නු ලබයි. (MD5 ලෙස හදුන්වන හැශ් ශ්‍රිතය වැනි සමහර අවස්ථා වලදී , වසර ගණනාවක් වැඩ  කිරිමෙන් පසුව ගැටුම් සොයා ගන්නා ලදි, එහි ප්‍රතිඑලයක් ලෙස  MDS හැශ් ශ්‍රිතය ප්‍රායෝගික භාවිතය ඉවත් කර ඇත..)