Ақпараттық қауіпсіздік негіздері
жүктеу/скачать 258.19 Kb.
|
| Дәріс №14
Тақырыбы: Дәрежеге көтеру әдісі Дискретті дәрежеге көтеруге негізделген бірнеше шифрлеу тәсілдері белгілі. Солардың ішінде кең тарағаны- ақырғы жолдағыларды дискретті дәрежеге көтеру тәсілі. Оларға Диффи-Хелман (DH) және Месси-Омур криптоалгоритмдері жатады. Крипторгафияның ашық кілтті идеясы біржақты функциялар идеясымен тығыз байланысты. Берілген х аргументі бойынша f(х ) функциясының мағынасын есептеп табу оңай, ал х-ты f(х)-дан табу өте қиын. Біз f(х) туралы функция ретінде айтамыз. Х-ты f(х)-тан есептеп табу тек криптоаналитик үшін ғана қиын. Ақпаратты заңды түрде қабылдап алушыда қажетті амалы болады. Осындай біржақты функциялар криптографиялық деп аталады. Ашық кілтті ақпараттарды қорғауда «жасырын амалы» бар біржақты функцияны қолданатын екі негізгі топтарды көрсетуге болады. Осындай функция ретінде дәреженің нақтылы көрсеткіші m және модулі n бар модульдік дәрежеге көтеру қолданылуы мүмкін. F(x)= хm mod n ( ) Кері операцияның тиімді алгоритмі - модуль n бойынша m-дәрежесінен түбір табу кез келген сандар үшін белгісіз. Бұл үлкен сандар үшін дискретті логарифмдеу деп аталатын проблема. Қолданылатын әдістердің біреуі түбірді табудың n саны белгілі жағдайында жай сандарға ыдыратудың тиімді алгоритмін пайдаланады. Бұл функцияның f(х) түрін біржақты «жасырын амалды» функцияға жатқызады. Рюкзакты салу (буып-түю) тәсілі Рюкзакты салуды жүзеге асыруда Меркле мен Хелман криптоалгоритмдері қолданылады. Осы алгоритмді мысал ретінде қарайық. Сандар жиынтығы берілген болсын (а1,а2...аn)=А, әр түрлі тұтас оң n сандардан және тағы да бір тұтас оң k санынан тұрады. Қосындысы k санына тең болатын а сандарын табу керек, егер ол мүмкін болса. Қарапайым жағдайда k саны рюкзак размерін көрсетеді, ал әрбір а саны рюкзакка салынуы мүмкін заттың размерін көрсетеді. Рюкзак толық толатындай заттар жиынтығын табу берілетін тапсырма болады. Мысал ретінде k =3231 санын және 10 тұтас сандар а1,...а10 жиынтығын аламыз 43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523. K саны бірнеше а сандарын қосқанда алынатынын байқаймыз: 13 сурет. Рюкзакты салу тәсілі. 129+473+903+561+1165=3231 =>3231 => 0101101100 (екі еселенген вектор) Осы сандарды қосып біз шешуін таптық, яғни рюкзакты толтырдық. Ситуация 13 суретте көрсетілген. Іс жүзінде А сандарын көбейтіп көптеп табуға және қай қосындының k санына тең болатындығын да табуға болады. Біздің жағдайымызда ол 210=1024 тең. Егер бірнеше жүз а сандары болса, не болады? 2300 көбейтулері арасында дұрыс шешім іздеу үшін компьютерлік өңдеуге келмейді. жүктеу/скачать 258.19 Kb. Достарыңызбен бөлісу:
|