Кіріспе

Ертедегі ашық кілт криптожүйесі

Криптографияда Мерклдің жұмбақтары – 1974 жылы Ральф Меркл жасаған және 1978 жылы жарияланған ашық кілт криптожүйесінің алғашқы құрылымы. Ол екі тарапқа бұрын ортақ құпиясы болмаса да, хабар алмасу арқылы ортақ құпияға келісуге мүмкіндік береді.

Сипаттама

Ал Элис пен Боб байланыс құруға ниетті делік. Боб Алисқа мынадай жолмен хабар жібере алады: біріншіден, ол көптеген жұмбақтарды жасайды, олардың әрқайсысы орташа деңгейде қиын болуы керек – Алис оларды орташа есептеу күшімен шеше алуы тиіс. Жұмбақтар белгісіз кілтпен шифрланған хабарлама түрінде болады; кілт күшпен бұзуға мүмкіндік беретіндей қысқа болуы керек. Боб барлық жұмбақтарды (яғни шифрланған хабарламаларды) Алиске жібереді, ол олардың біреуін кездейсоқ таңдап, шешеді. Шифрдан алынған шешімде идентификатор және сессия кілті болады, сондықтан Алис Бобқа қай жұмбақты шешкенін хабарлай алады. Енді екі тараптың да ортақ кілті бар: Алис, өйткені ол жұмбақты шешті, ал Боб, өйткені ол жұмбақты жіберді. Кез келген тыңшы (мысалы, Ева) үшін бұл қиын міндет – ол Алис қай жұмбақты шешкенін білмейді. Оның ең жақсы стратегиясы – барлық жұмбақтарды шешу, бірақ олардың саны көп болғандықтан, Ева үшін бұл Алиспен салыстырғанда едәуір көп есептеу ресурстарын қажет етеді.

Жоғары деңгейдегі сипаттама

Боб 2N хабарлама жасайды, онда "Бұл X хабарлама. Бұл симметриялық кілт Y" деп жазылған, мұнда X – кездейсоқ түрде жасалған идентификатор, ал Y – симметриялық шифрлау үшін кездейсоқ түрде жасалған құпия кілт. Сондықтан X және Y әр хабарлама үшін бірегей. Барлық хабарламалар осылай шифрланған, сол себепті пайдаланушы әр хабарламаны белгілі бір қиындықпен бұзуға тырыса алады. Боб барлық шифрланған хабарламаларды Алисаға жібереді. Алиса барлық шифрланған хабарламаларды алады және кездейсоқ түрде бір хабарламаны таңдайды. Алиса сол хабарлама ішінде X идентификаторы мен Y құпия кілтін анықтағаннан кейін, өзінің қара мәтінін Y құпия кілтімен шифрлайды және осы идентификаторды (қара мәтінде) шифрланған мәтінімен бірге Бобқа жібереді. Боб бұл идентификаторға сәйкес келетін құпия кілтті табады, себебі оны бастапқыда өзі жасаған, және Алисаның шифрланған мәтінін сол құпия кілт арқылы шешеді. Еске сала кетейік, тыңшы Ева Алисадан Бобқа (қара мәтінде) жіберілген X идентификаторын оқи алады, бірақ оны құпия кілт Y-мен байланыстырудың жолы жоқ, себебі Боб пен Алиса осы құпия кілтті ағымдағы байланыстарында пайдаланады, ал әр хабарламадағы X мәні кездейсоқ түрде жасалған.

Күрделілік пен қауіпсіздікті талдау

Пазл ойынының параметрлерін тыңшыға кодты бұзуды екі тараптың байланысуына қарағанда әлдеқайда қиындату үшін таңдауға болады, бірақ Меркл пазлдары қазіргі криптографиядағы қауіпсіздікті анықтайтын және талап ететін қиындықтардың үлкен сапалық айырмашылығын қамтамасыз етпейді. Боб жіберген пазлдардың саны m деп есептейік, ал бір пазлді шешу үшін Боб пен Алисаға n есептеу қадамы қажет болсын. Онда олар екеуі де O(m+n) уақыт күрделілігінде ортақ сессия кілтін анықтай алады. Керісінше, Ева барлық пазлдарды шешуі керек, бұл оған O(mn) уақыт алады. Егер m ≈ n болса, Еваның жұмысы Алиса мен Бобқа қарағанда шамамен квадраттық күрделілікке ие, яғни оның есептеу уақыты олардың уақытының квадратына тең. Сондықтан n-ді Алиса мен Боб үшін есептеу әлі де мүмкін болатындай, бірақ Еваның мүмкіндіктерін басып тастатындай жеткілікті үлкен етіп таңдау керек. Квадраттық күрделілік әдетте шабуылшыға қарсы жеткілікті қауіпсіз деп есептелмейді (немесе, керісінше, үлкен m және n үшін, қатысушылар үшін ыңғайлы). Бірақ бұл схема ашық кілтті криптографияның алғашқы мысалдарының бірі болып табылады және дискретті логарифм мәселесіне негізделген, әлдеқайда жоғары күрделілікке ие Diffie-Hellman кілт алмасу протоколына түрткі болды. 2008 жылы Боаз Барак және Мохаммад Махмуди Гидари ("Меркл пазлдары оңтайлы") осы квадраттық шекараны жақсарту мүмкін емес екенін көрсетті.