Кіріспе
Меркл-Хеллман қалтасы криптожүйесі ең алғашқы ашық кілт криптожүйелерінің бірі болды. Ол 1978 жылы Ральф Меркл және Мартин Хеллман жариялаған. Ади Шамир 1984 жылы полиномиалдық уақыттағы шабуыл туралы жариялады. Осының нәтижесінде, бұл криптожүйе қазіргі таңда қауіпсіз деп есептеледі.
Тарих
Ашық кілт криптографиясы 1976 жылы Уитфилд Диффи және Мартин Хеллман тарапынан енгізілді. Олар сол кезде "бір бағытты қақпа есігі бар функция" деген жалпы ұғымды ұсынды – бұл функцияның керісін белгілі бір құпия "қақпа есігі ақпараты" болмаса есептеу өте қиын; бірақ олар мұндай функцияның нақты мысалын әлі таба алмады. Келесі бірнеше жылда басқа зерттеушілер RSA (1977) және Меркл-Хеллман (1978) сияқты бірнеше нақты ашық кілт криптожүйелерін ұсынды.
Сипаттама
Merkle–Hellman – бұл ашық кілт криптожүйесі, яғни екі кілт қолданылады: шифрлау үшін ашық кілт және шифрды ашу үшін жеке кілт. Ол жиынтықтың қосындысы мәселесіне негізделген (көкпар мәселесінің ерекше жағдайы). Мәселе мынадай: бүтін сандар жиынтығы және бүтін сан берілгенде, олардың қосындысы сол санға тең болатын жиынтықтың ішкі жиынтығын табу керек. Жалпы алғанда, бұл мәселе NP-толық деп белгілі. Дегенмен, егер жиынның әрбір мүшесі одан кіші сандардың барлық қосындысынан үлкен болса, онда мәселе «оңай» болып саналады және қарапайым ашкөз алгоритммен полиномиалдық уақытта шешіледі. Merkle–Hellman жүйесінде хабарды шифрды ашу үшін сырттай «қиын» көрінетін көкпар мәселесін шешу қажет. Жеке кілтке үдемелі өсетін сандар тізімі кіреді, ал ашық кілтке үдемелі өспейтін сандар тізімі кіреді, ол іс жүзінде - «жасырынып» алынған » нұсқасы. Жеке кілт сондай-ақ, қиын көкпар мәселесін пайдаланып, оңай көкпар мәселесіне айналдыруға болатын «сыртқы есік» ақпаратын қамтиды. RSA сияқты басқа ашық кілт криптожүйелерінен айырмашылығы, Merkle–Hellman жүйесіндегі екі кілттің орнын ауыстыруға болмайды; жеке кілтті шифрлау үшін пайдалануға болмайды. Сондықтан Merkle–Hellman криптографиялық қол қою арқылы растау үшін тікелей қолданылмайды, бірақ Шамир қол қоюға болатын нұсқасын жариялаған.
Unlike some other public key cryptosystems such as RSA, the two keys in Merkle Hellman are not interchangeable; the private key cannot be used for encryption. Thus Merkle Hellman is not directly usable for authentication by cryptographic signing, although Shamir published a variant that can be used for signing.
Кілтті жасау
1. Блок өлшемін таңдаңыз. Бұл кілтпен биттерге дейінгі бүтін сандарды шифрлауға болады. 2. Қосымша сандардың кездейсоқ суперөсімді тізбесін таңдаңыз. Суперөсімділік талабы мынаны білдіреді, яғни үшін 3. Кездейсоқ бүтін санды таңдаңыз, мысалы 4. Кездейсоқ бүтін санды таңдаңыз, яғни (яғни және өзара жай сандар). 5. Реттілікті есептеңіз
The superincreasing requirement means that , for
3. Choose a random integer such that
4. Choose a random integer such that (that is, and are coprime). 5. Calculate the sequence
where
The public key is and the private key is .
мұндағы . Ашық кілт – және құпия кілт – .
The superincreasing requirement means that , for
3. Choose a random integer such that
4. Choose a random integer such that (that is, and are coprime). 5. Calculate the sequence
where
The public key is and the private key is .
Шифрлау
Биттерден тұратын биттік хабарды қарастырайық, онда ең жоғары разрядты біт . нөлдік емес барлық үшін оларды таңдап, қосыңыз. Балама ретінде, келесіні есептеңіз: Шифрланған мәтін болады.
Шифрлау
Шифрланған мәтінді түсіндіру үшін біз оның сомасы болатын кіші жиынтығын табуымыз керек. Біз бұл мәселені кіші жиынтықты табу мәселесіне айналдырамыз. Бұл мәселе көпмүшелік уақытта шешіледі, өйткені тізбек суперауыспалы. 1. Кеңейтілген Евклид алгоритмін қолданып, модуль бойынша модульдік керіні есептеңіз. Керінің бар екеніне көз жеткізіңіз, өйткені олар өзара жай. -тің есептелуі хабардан тәуелсіз және жеке кілт жасалғанда бір рет жасалуы мүмкін. 2. Есептеңіз. 3. Төменде сипатталған қарапайым ашкөз алгоритм арқылы суперауыспалы тізбекті пайдалану арқылы сомасы мәселесін шешіңіз. -қа сома беретін элементтерінің тізімі болсын (яғни, ). 4. Хабарды құрастырыңыз, әр бит позициясында 1 және қалған барлық бит позицияларында 0 болады:
The computation of is independent of the message, and can be done just once when the private key is generated. 2. Calculate
3. Solve the subset sum problem for using the superincreasing sequence , by the simple greedy algorithm described below. Let be the resulting list of indexes of the elements of which sum to (That is, .) 4. Construct the message with a 1 in each bit position and a 0 in all other bit positions:
Криптоанализ
1984 жылы Ади Шамир жеке кілтті пайдаланбай, шифрланған хабарламаларды полиномдық уақытта түсіре алатын Меркл-Хеллман криптожүйесіне шабуыл жасады. Шабуыл ашық кілтті талдайды және және сияқты екі сан жұбын іздейді, осылайша суперарту тізбегін құрайды. Шабуылдың нәтижесінде табылған жұп жеке кілттегі -мен бірдей болмауы мүмкін, бірақ осы жұп сияқты, ол арқылы қиын рюкзак мәселесін суперарту тізбегін пайдаланып жеңіл мәселеге айналдыруға мүмкіндік береді. Шабуыл тек ашық кілтпен жұмыс істейді; шифрланған хабарламаларға қажеттілік жоқ. Шамирдің Меркл-Хеллман криптожүйесіне жасаған шабуылы, ашық кілттегі сандар кездейсоқ түрде шатастырылған жағдайда да полиномдық уақытта жұмыс істейді – бұл қадам криптожүйенің сипаттамасына әдетте қосылмайды, бірақ кейбір қарапайым шабуылдарға қарсы тиімді болуы мүмкін.