RSA криптожүйесінде кілттерді генерациялау

В данной статье рассмотрена криптосистема RSA и выбор длинны параметров p и q в данной криптосистеме, а так же рассмотрены вероятностные алгоритмы проверки на простоту выбранных параметров.

Ключевые слова: криптосистема RSA, простые числа, вероятностные алгоритмы

Соңғы бірнеше онжылдықтар ішінде, адамзат үлкен көлемді ақпараттарды жіберу қиындықтарымен кездесті. Жіберу кезінде бұл ақпараттарды рұқсатынсыз көру немесе оқу мәселесін шешу қазіргі таңда ең өзекті мәселелердің біріне айналды. Алгоритмнің қауіпсіздігі оның кілттеріне негізделген. Кілттерді генерациялау барысында криптографиялық әлсіз процессті қолдансаңыз, онда сіздің жүйеңіз жалпы әлсіз болады. Ең сенімді алгоритмдер бәріне мәлім болғанымен, шифрленген хабарламаның кілттерін, мүмкін мәндері бойынша іріктеу арқылы есептеп алуға болады. Ақпараттану заманында ассиметриялық криптожүйелерді жиі қолданады. Себебі, ассиметриялық криптожүйелердің ерекшелігі екі кілттің қолдануында. Біреуі бәріне мәлім болса, екіншісі құпия болып табылады және олар математикалық қандай да бір заңдылықпен байланысқан. Яғни, ашық кілтпен шифрленген хабарды білгенімен құпия хабарды аша алмайсыз, ал құпия кілттің көмегімен дешифрлей алсаңызда ашық хабарды шифрлей алмайсыз. Ең қиыны кілттерді құпия түрінде сақтау болып табылады. Оларды тарату кезіндегі жіберілген қателіктердің, сонымен қатар немқұрай сақтаудың салдарынан бұзушы жабық ақпаратқа қол жеткізе алады. Осыдан кілттерді басқару есебі туындайды. [1]

Кілттерді басқару жүйесінің негізгі этаптары:

 кілттерді генерациялау,

 кілттерді тарату,

 кілттерді қолдану,

 кілттерді тексеру,

 кілттерді жаңарту,

 кілттерді жою.

Ақпараттарды қорғау үшін криптографиялық жүйеде ең тиімді және жиі қолданылатын жүйелердің бірі RSA криптожүйесі болып табылады. Бұл криптожүйені 1978 жылы Р.Л Райвест, А.Шамир және Л.Адлеман деген үш математик ғалымдар ойлап тапқан. Өте қарапайым және «ашық кілтті криптожүйенің» тамаша үлгісі болғандықтан қазір бүкіл әлемде кеңінен таралған. Бұл криптожүйенің негізгі қиындығы –модулінің жай сандарға жіктелуі болып табылады. RSA криптожүйесі үлкен сандарды факторизациялау күрделілігіне негізделген жақсы криптоберіктілікпен ерекшеленеді. Бұл алгоритм мәліметтерді шифрлеу режимінде және электронды сандық қолтаңба режимінде жұмыс істей алатын ең бірінші толыққанды алгоритм болып саналады. Ол ашық жүйелер үшін дүниежүзілік стандартқа айналды. Сонымен қатар RSA SWIFT, ANSI X9.31 rDSA және американдық банктер үшін қолданылатын жобасының X9.44 стандартының бөлігі болып табылады. Бұл алгоритм жеке криптографиялық өнімі ретінде, сонымен қатар қосымшаларға ендірілген құрал ретінде қолданылады. [2]

Заманауи криптографияның математикалық негізі ретінде сандар теориясы қолданылады. Жоғарыда криптожүйенің негізгі қиындығы үлкен санның екі үлкен жай сандарға жіктелуі туралы атап айтқандай, бұл саладағы көптеген зерттеулердің ішінде ең өзектілерінің бірі санды жай не жай еместігіне тексеру болып табылады. RSA криптожүйесінің n=pq модулін есептеу үшін p,q екі үлкен жай сандары қолданылады. Осыған байланысты RSA криптожүйенің кілттерін генерациялау жылдамдығы n модулін есептеу барысындағы, таңдалған сандардың жай не жай емес мәселесін шешу жолдарымен анықталған. [3]

Қазіргі таңда санның жай, не жай емес екендігін тексеретін алгоритмдер мен тесттар бар. Санның жай не жай еместігін ерте заманнан бастап зерттегенмен, ең басты бағыты ХХ ғасырдың ІІ-ші жартысында бастау алды. Оның себебі кілттерді генерациялауда үлкен жай сандардың қолданылуы болып табылады. Жай сандарды тексеру алгоритмдері екіге бөлінеді: детерминирленген және ықтималды. Олардың ішінде кең таралған және жиі қолданылатын ықтималды алгоритмдер болып табылады.

XVII ғасырда француз математигі Пьер Ферма сандарды жай санға тексеруге арналған мүмкін тесттердің бәрінің негізі болатын тұжырымдаманы енгізіп кеткен.Ферманың кіші теоремасы:

Егер p — жай сан болса, a — кез келген бүтін сан болса, онда

ал егер p а-ны бөлмесе, онда

Бұл теоремаға сүйеніп, санды жай санға тексеру үшін қолданылатын мықты тесттердің бірін құруға болады.

есептейміз. Егер нәтижесінде 1 шықса, онда ол сан жай сан болып табылады. Ал егер, 1-ге тең емес болса, онда ол сан құрама сан болып шығады.

Ықтималды алгоримдердің ең жиі қолданылатын тесттері Соловей-Штрассен мен Миллер-Рабин.

Соловей-Штрассен тесті Эйлер критерияларына және квадраттық шегеру ұғымына негізделген. Квадраттық шегеру дегеніміз — кез келген санның квадратын p модулі бойынша бөлгендегі қалдығы болып табылатын бүтін санын айтамыз:

Эйлер критериясы: p— жай сан болсын, . квадраттық шегеру болып табылады, егер салыстыруы орындалса.

Соловей-Штрассен тесті еңбекті көп қажет етпейді және k рет орындалғаннан кейін санды жай екенін анықтау қатесінің ықтималдылығы ден аспайды. Бірақ практика жүзінде бұл тестің сенімділік дәрежесі жеткіліксіз. Соловей-Штрассен тестіне қарағанда, жоғарырақ сенімділікті Миллер-Рябин тесті береді. Бұл тест Ферма тестімен бірігу жолында алынған. Келесі салыстырулардың көмегімен , (N,t — тақ сандар) құрама сандарды шығарып тастайды. Бұл тесті k рет орындалғаннан кейін санды жай екенін анықтау қатесінің ықтималдылығы ден аспайды. Осыған байланысты, санның жай екендігін анықтайтын алгоритмдер (мысалы Миллер-Рабин алгоритмі), RSA криптожүйесіндегі кілттерді генерациялауда атқаратын рөлі өте маңызды. [5]

RSA зертханасы қарапайым есептер үшін кілттің ұзындығы 1024 битке тең, ал маңыздырақ есептер үшін кілттердің ұзындығы 2048 битке және одан да ұзынырақ болуына нұсқау береді. Мысалы, Қазақстан Республикасының қауіпсіздігін қамтамасыз ету стандартында СТ РК 1073–2007, 3-ші қауіпсіздік деңгейін қамтамасыз ету үшін кілттің ұзындығы 4000 бит, ал 4-ші қауіпсіздік деңгейін қамтамасыз ету үшін кілттің ұзындығы 8000 бит болуы керек екендігі көрсетілген. [1]

Төменде қарастырған тесттердің типтері және қолдану саласы көрсетілген. [4]

Қорытындылай келе, ассиметриялық криптожүйелердің маңызы қазіргі таңда өте зор. Олардың қолдану саласы кең тараған: интернетте, банкттерде, ЭСҚ ны құруда және т. б. Бұл олардың криптоберіктілігінің арқасында жүзеге асырылып келе жатыр. Криптоберіктілігі — санды жай көбейткіштеріне жіктеу, ақырғы өрісте логарифмді есептеу және алгебралық теңдеулердің түрбірлерін табу сияқты математикалық күрделі есептерді шешу қиындығына негізделген. RSA сияқты, басқада ашық кілтті жүйелердің беріктілігі кілттеріне байланысты. Кілттерін генерациялау барысында оның жай сан болуы өте маңызды. Себебі, ашық кілтті жүйелерде кілтті генерациялау үшін тек қана үлкен жай сандар қолданылады. Қазіргі таңда санды жай не жай емес екендігін тексеретін алгоритмдер көп, бірақ ең кең қолданатын алгоритмдер ықтималды тестер болып табылады. Кілттердің ұзындықтары компьютерлердің есептеу қуаттылығының артуына байланысты ұзарып келе жатыр. Мүмкін болашақта ашық кілтті жүйелер үшін кілттердің ұзындығына байланысты басқа да ұсыныстар болуы мүмкін, ал қазіргі таңда кілттер ұзынырақ болған сайын, жүйе криптоберік болып табылады. Бұл кілттерді жай сан болуын тексеретін тесттерді қазіргі күнге дейін модификациялап, ең тиімді тесттерін ұсынуда.

1. Главчев М. И, Дроздов Ю. Ю. К вопросу генерации ключей для асимметричных криптосистем. Вестник Национального технического университета Харьковский политехнический институт. Серия: Информатика и моделирование. № 46 / 2004
2. Aithozhaeva., S. T. Tynymbaev. Aspects of hardware reduction modulo in asymmetric cryptography E.Zh. Kazakh national technical university named after K. I. Satpayev, Almaty 2014
3. Байсалов Е. Р. Криптографияның математикалық негіздері. Алматы.: «Қазақ университеті», 2003, 43б.
4. Кучин Борис «Защита информации» Обзор проверок на простоту. Московский Физико-технический Институт (ГУ МФТИ) Кафедра радиотехники. 2005
5. Балабанов А. А., Агафонов А. Ф., Рыку В. А. «Алгоритм быстрой генерации ключей в криптографической системе RSA»— Вестник научно-технического развития, 2009 № 7(23). — С. 11.