RSA криптожүйесінің қауіпсіздігі мен тездігі

RSA криптожүйесінің қауіпсіздігі екі үлкен жай сандардың көбейтіндісі болып табылатын үлкен санды жіктеу есебін шешудің қиындығына негізделген. Шынында, RSA алгоритмінің сенімділігі құпия және ашық кілттерді құрғаннан кейінгі және сандарының мәндерінің жойылып кететіндігінде. Бұл жағдайда құпия k_b кілтінің мәнін ашық K_b кілтінің мәніне сай анықтау қиынға түседі, себебі N модулінің бөлгіштерін P ж әне Q –ді табу есебін шешуге тура келеді. N модулінің мәнін жай көбейткіштерге P ж әне Q –ге жіктеу (N)=(P -1)(Q -1), функциясының мәнін анықтауға және одан әрі құпия k_b кілтінің мәнін K_b * k_b º1(mod (N)) немесе

k_b = K_b ^-1(mod (P-1)(Q-1)) қолдана отырып табуға мүмкіндік береді.RSA алгоритмін криптографиялық талдаудың тағы бір әдісі (N)=(P -1)(Q -1) функциясының мәнін тікелей есептеу.

x = P+Q=N+ 1- (N);

y= (P - Q)² = (P+Q)²-4*N; (N)-ді біле отырып, x- ті одан кейін y- ті анықтауға болады. Ал олар арқылы келесі қатынастарды пайдаланып:

P=1/2(x+ ), Q=1/2(x- ),

P, Q сандарын табуға болады. Бірақ бұл шабуыл N модулінің мәнін жай көбейткіштерге P æәíå Q –ге жіктеу есебінен қарапайым емес. 1994 жылы 129 ондық цифрдан тұратын сан жіктелген болатын. Оны орындау үшін математиктер А. Ленстра мен М.Манасси желіге қосылған 1600 компьютерді пайдаланып бөлшектенген есептеуді ұйымдастырған болатын.

Полиг-Хеллманның шифрлеу үрдісі Бұл әдіс RSA криптожүйесінің шифрлеу үрдісіне ұқсас. Ол да шифрлеу мен керішифрлеу үшін әртүрлі кілттерді пайдаланатын болғандықтан, симметриялық емес әдіске жатады. Екінші жағынан, бұл үрдіде шифрлеу кілтін керішифрлеу кілтінен және керісінше оңай табуға болатындықтан, ашық кілтті криптожүйеге жатқызу да қиын. Екі кілтті де құпия сақтауға тура келеді. Шифрлеу C = P^e mod n Керішифрлеу

P = C^d mod n, мұндағы e*d≡1(қандай да бір құрмалас санның модулі бойынша). Бұл әдістің RSA –дан айырмашылығы n саны екі үлкен жай сандар арқылы табылмайды. N Саны құпия кілттің бөлігі ретінде қалуы тиіс. Егер қарсылас e және n сандарын білетін болса, d санын жеңіл таба алады. Ал егер ол e және d сандарын білмесе, E=log _pC (mod n) мәнін есептеуіне тура келеді. Мұның қиын есеп екені белгілі. Полиг-Хеллманның шифрлеу үрдісі США мен Канадада патенттелген.

Дата добавления: 2015-10-24