Ашық кілтті қолданатын алгоритмдер
МАЗМҰНЫ
Кіріспе
3
1.
Нысанның техникалық шарттары
5
1.1
Криптографияның негізгі түсініктемелері мен тарихы
5
1.2
Күрделілік теориясы
9
1.3
Сандар теориясы
13
1.4
Жай сандар генерациясы
18
Бірінші бөлім бойынша қорытынды
20
2.
Жобаның нысаны
21
2.1
Криптографиялық кілттерді басқару
21
2.2
Симметриялық (құпиялы) әдістемелер мен алгоритмдер
24
2.3
Асимметриялық (ашық) әдістемелер мен алгоритмдер
26
2.4
Ашық кілтті қолданатын алгоритмдер
29
2.5
Ашық кілтті қолданатын алгоритмдердің қауіпсіздігі
30
2.6
Екінші бөлім бойынша қорытынды
31
3.
Нысанның техникалық параметрлерін есептеу
32
3.1
Қол қапшық алгоритмін есептеу
32
3.2
RSA алгоритмі
36
3.3
RSA шифрлеу жүйесі
37
3.4
RSA алгоритмінің жұмыс істеу жылдамдығы
42
3.5
RSA қауіпсіздігі
43
Үшінші бөлім бойынша қорытынды
50
Қорытынды
51
Пайдаланылған Әдебиет тізімі
52
1 қосымша
54
КІРІСПЕ
Диплом жұмысының өзектілігі: Евклид және Диофант, Ферма, Эйлер, Гаусс, Чебышев сонымен Эрмит еңбектерінде диофан түріндегі теңдеулердің шешу жөніндегілері маңызды ойлар бар болып табылады, сол уақыттар үшін үлкен болып саналатын сандарының ең жақын мәндерін іздеу үшін талаптар бар болып айқындалады. Соңғы кездерде екі он жылдардағы криптографиялар ЭЕМ-гі кең тарқалуындағы солармен қатар сұраныстардың дамуытуларына қарай сандар теорияларының алгоритмдіктері сұрақтарына дамуларының қарқынды болып келеді.Сонымен қатар есептеушілердегі машиналарының немесе лектрондықтардың құралдардың адамның барлық қызметтерімеен ой-өрісіне қарай жоғарланады. Бұндайсыз қазіргі кездегі криптографияны елестету мүмкін емес болып айқындалады. Жалпы мәтіндерді шифрлеу арқылы және солармен қатар оны бұзудыда ЭЕМ арқылы бүтін сандардың өңдеу ретіндегілерімен қатар елестетуге болатындығын білеміз, сонымен осындай амалдар орындалатын тәсілдері кейбір функциялары арқылы солай секілді бүтін сандарының белгілі бір жиынындада орында алатын болып саналады. Бұлардың барлығы қазіргі кезде криптографияларда олардың сандарының теорияларымен қатар болуына жағдай жасалынатын болып табылады. Сонымен қатар олармен байланысты, кейбір криптографиялар жүйелерінің тұрақтылығымен қатар тек кейбір сандықтар-теориялықта есептер арқылы да күрделілігімен қатар негізделетін болған болатын. Дегенмен ЭЕМ мүмкіндігі шекті болып айқындалады. Ұзындағы сандық тізбектерді белгілі бір өлшемді блоктарға бөлуге де тура келетіндігінде немесе әр блоктарды бөлек шифрлеуге тура келетін болып айқындалады. Осылардың әр қайсысы біз барлық шифрленетін сандардыңда теріс емес және берілген m санынан кіші емес деп санайтын болатындығымызда болып отыр. Сонымен қатар осындай шектеулер арқылы солармен байланысты одан әрі шифрлеуденде алынатын сандарғада қатысты болып айқындалады.
Соның негізіндегілеріндегі нақты қолданылатындағы шифрлеулер жүйесі алынатын болып табылады, авторлардың барлық есімдерінің алғашқы аттарына сәйкестігімен қатар RSA деп саналатын болатындығында болып отыр. Осындай функциялардың төмендегіндей болып келетіндігін айқындаймыз:
- fx функциясының мәндерінен қатар есептейтін әлдеқайда жылдам әдістері бар болып табылады;
- f-1xкері функцияларының мәндеріндегілері есетейтін жылдам әдістері бар болып табылады;
- fx функциясының құпиясы бар екендігіне, дегенмен оны анықтасақ, f-1x мәндерін тез есептеуге болатындығы болып табылады, сонымен қатар қарсы жағдайда f-1x есептеуге ауыр болатындығы, көп уақытты кетіретін, шешуге мүмкін емес есепке айналатын болып табылатындығында.
RSA осы жылдардың ішіндегі ұсынылған ашық кілттердің қолданатын алгоритмдерінің ішіндегілерінің ең оңай түсінуге және жүзеге асыруға болатын алгоритмдері болып айқындалады.
Бұл дипломдық жұмыс криптографияның ашық кілтті қолданатын алгоритмдердің бірі - RSA-ға арналған болып айқындалады.
Диплом жұмысының мақсаты: Криптографиялық кілттердіңкөмегімен желілерді қорғауды қамтамасыз ету және RSA алгоритмін қазіргі таңдағы технологияларды пайдалана отырып, ақпаратты қорғау саласында кеңінен қолдана алатын автоматтандыру жүйесін құру.
Жұмыстың мақсаты дипломдық жұмыс барысында шешілген келесі міндеттерді анықталған болатын:
oo сандар теориясын, оның бөлімдерінің бірі жан сандарды зерттеу. Өте үлкен жай сандарды іздеу;
oo екілік жүйедегі сандармен жұмыс жасау;
oo ашық және жабық кілттердің құрылымын зерттеу;
oo бір компьютерден екінші бір компьютерге ақпаратты шифрлеп жібергенде, барлық қауіпсіздік ережелерін сақтау және зерттеу болып табыалды.
Дипломдық жұмыс кіріспеден, үш бөлімнен, қорытындыдан, әдебиеттер тізімінен тұрады. Кіріспеде жұмыстың өзектілігі берілген, мақсаты қойылған, сол мақсатқа қол жеткізу міндеттерінен тұратындығын айтамыз.Сонымен қатар зерттеу объектісі және маңыздылығы анықталып қарастырылған болатын.
Бірінші бөлімде криптографияның негізгі түсініктерімен қатар олардың тарихы, олардың жұмыс істеу принциптерімен алгоритмдері, сонымен қоса RSA алгоритмдері пайдаланылатын математикалық негіздемелері туралы теориялық анықтамалар да орын алған болатын. Бірінші бөлімнің басты қорытындысы - криптографияның бастамасын түсіндірулерімен қатар, оның әдістемелерінен қатар алгоритмдеріндегі таныстыру болып табылады.
Екінші бөлім ашық кілтті қолданатын алгоритмдерге, соның ішінде, RSA алгоритміне арналған бөлім болып табылады. Осыларға орай қорытындылар жасалынды.
Үшінші бөлімде NET платформасына, оның құрылымы мен сипаттамасына арналған боылп айқындалады. Сонымен қатар бұл бөлімдегілер C-тың басқа объектілі-бағытталған болып программалардан айырмашылығын көрсетілген болып айқындалатындығында болып отыр.
Сонымен қатар олардағы жұмыстың қойылымына, яғни бағдарламалық бөлімге арналған болып табылады. Онда әрбір батырманың мақсатына дейін айтылып кеткен болып табылады.
1 НЫСАННЫҢ ЖАҒДАЙЫНЫҢ ТЕХНИКАЛЫҚ ШАРТТАРЫ
1.1 Криптографияның негізгі түсініктемелері мен тарихы
Ақпараттарды оларды түрлендірулерімен қатар басқа адам оқи алмайтындай етіп қорғаулардағы мәселелері адамзат алдында бұрыннан тұрған мәселелердің бірі болып айқындалады. Криптографияның тарихы яғни - адамзат тілінің тарихының замандасымен байланысты болып келеді. Олармен бірге, жазу алғашқыда криптографиялық жүйелерінің болуына табылатын, себебі, ежелге қоғамда солармен тек ерекше таңдаулы адамдардан иелік ететін болып табылады. Ежелдегі Египет және Үндістан киелі кітаптарымен қатар соған мысал бола айқындалатындығында болып отыр. Криптография жазудың кең таралуындағы олармен байланыстары дербес ғылым ретінде қалыптаса басталатын болып келеді.
Криптография тарихтарында олармен қатар шартты түрде төрт қадамға бөлңп қарастыруға болады, олар төмендегідей:
oo жай криптографиялар;
oo ресми криптографиялар;
oo ғылыми криптографиялар;
oo компьютерлік криптографиялар болып.
Сонымен қатар жай криптографиялар үшін (XVI ғасырлар басында олармен қатар) қарсыластырылатын кез келген шифрлік мәтін мазмұнына қарай қатысты шатыстыру тән болып табылады. Мысалы, бастапқы қадамдағылары ақпаратты сақтаулары үшін криптографиямен қатар барабар кодтаулары арқылы және стеганография әдістері қолданатын болып келеді.
Көптеген қолданылыстағылардың шифрлар орын ауыстырулар және моноалфавиттіктері ауыстырулары арқылы жүзеге асырылатын болып табылады. Жарияланған мысалдардың бірі болып табылатын Цезарь шифры табылған болып келеді, олардың мәтіндегі алдыңғыдағы әріпті алфавитте одан алыс тұратын әріптерге ауыстырулары арқылы жүзеге асырылатындығында болып отыр. Басқа шифрлері, полибианды квадраттар, грек жазушысы Полибий шығарған, алфавитпен өлшемі 5 және 5 болатын квадратты кестеге кездейсоқ толтырылатын грек алфавитінің көмегімен жүзеге асатын жалпы моноалфавитті орын ауыстыру болып саналады. Барлық әріп квадратта одан төмен тұратын әріппен ауыстырылған болатын. Сондықтан ресми криптография қадамы (XVғ.аяғы-XX ғ. басы) криптоанализдің ресми және салыстырмалы түрде тұрақты шифрлерінің пайда болуымен байланысты болып айқындалады.
5B07.19.РЭТ.5101
5B07.16.РЭТ.01.01
5B07.15.РЭТ.31.01
5B07.15.РЭТ.01.01
Әдеб.
Орындаған
Орындаған
Орындаған
Орындаған
Жетекші
Өлш.
..Өлш.
..Өлш.
..Өлш.
..
Бет
Беттер
ҚР Бжәне ҒМ ҚазККА
РТ кафедрасы
және ҒМ ҚазККА
РТ кафедрасы
Криптографиялық кілттердіңкөмегімен желілерді қорғауды қамтамасыз ету
Бекітемін
Н.бақылау
Н.бақылау
Н.бақылау
Н.бақылау
Қолы
КүніКүніКүніКүні
Бет
Бет
Бет
Бет
Құжат №
Мекебаева А.К.
Т.бақылау
Нурыллаев Н.Д.
Мекебаева А.К.
Кусамбаева Н.
Липская М.А.
5B07.19.РЭТ.5101
5B07.16.РЭТ.01.01
5B07.15.РЭТ.31.01
5B07.15.РЭТ.01.01
Әдеб.
Орындаған
Орындаған
Орындаған
Орындаған
Жетекші
Өлш.
..Өлш.
..Өлш.
..Өлш.
..
Бет
Беттер
ҚР Бжәне ҒМ ҚазККА
РТ кафедрасы
және ҒМ ҚазККА
РТ кафедрасы
Криптографиялық кілттердіңкөмегімен желілерді қорғауды қамтамасыз ету
Бекітемін
Н.бақылау
Н.бақылау
Н.бақылау
Н.бақылау
Қолы
КүніКүніКүніКүні
Бет
Бет
Бет
Бет
Құжат №
Мекебаева А.К.
Т.бақылау
Нурыллаев Н.Д.
Мекебаева А.К.
Кусамбаева Н.
Липская М.А.
5
5
54
54
Дж
Дж
Бет
Бет
Өлш
Өлш
Қүні
Қүні
Сонымен қатар Еуропа мемлекеттеріндегі осындай Қайта өрлеу дәуірлері кезіндегі пайда болған болатын, сондықтан ғылымдар мен сауданың дамуы ақпаратты қорғауларының әдістерімен қажет болған кезде пайда болып айқындалады. Осындай қадамдағы маңызды рөлдері Леон Батисте Альберти атқарылады, олар көп әліппелі орындар ауыстырудағылар алғаш ұсынған итальян архитекторы болып табылалған. Жалпы XVI ғасырда Блез Вижинер дипломатының атына ие болған бұл шифр берілген мәтінді кілтпен әріпті тізбекті қосу тәсілінен болып табылады. Осылардың шифр туралы трактат атты еңбегі криптологияларымен қатар олардың жөніндегі алғашқы еңбегі болып табылатындығында болып отыр. Ең алдымен бір рет баспа жұмыс болып Иоганн Трисемустың Полиграфиялары (1508 жыл) еңбегі болып айқындалады. Олар үлкен еместегі, алайда маңызды жаңалық ашқан болатын, полибиандік квадрататы қабылдауларындағы әдістері немесе әріп жұптарын шифрлеулері болып айқындалатын.
Көп әліппелі ауыстыруларының қарапайымдылығына әрі тұрақты әдісі болатындағына XIX ғасырларда Чарльз Уитстонмен ашылғандағы Плейфер шифры пайдаланылады. Уитстон маңыздылығы жаңалықтардағы екілік квадрат арқылы шифрлеу әдісін ашқан екен. Плейфер және Уитстон шифрлары бірінші дүниежүзілік соғысқа дейін пайдаланылады. Сонымен қатар XIX ғасырда голландықтар Керкхоффы сол уақыттарға дейінгілердегі өзекті болып табылатын криптографиялық жүйелерінің басты талаптарын ұсынылған болатын, дегенмен шифрлардың құпиялылығының алгоритм еместігімен қатар, кілттің құпиялылығына негізделуі қажет болып айқындалады. Ғылымға деігейіндегі оларға жоғары крипто тұрақтылықтармен қамтамасыз ететіндігі криптографияның соңғы сөзі болып шифрларды автоматтандыруға мүмкіндік берген роторлық крипто жүйе болып айқындалады.
Сондай жүйелердегі барлық болып 1790-жылы болашақ президент Томас Джефферсонмен пайдаланылған механикалық машиналары болып табылған болатындығында болып отыр. Сонымен жалпы әліппелі ауыстырулардағы роторлықтар машиналары көмегімен бір-біріне қарай айналымдағы жасайтындығы роторлардың вариациясы арқылы болып айқындалады.
Роторлық машиналардың практикалық жағынан сұранысқа XX ғасыр басында ие болып айқындалады. Сонымен қатар алғашқы қолданыстағы енген машиналары болып 1917-жылы Эдвард Хебернмен жасалынатындығы, Артур Кирхпен жаңартылған немістері Enigma машинасы болған болатын. Роторлық машиналар ІІ дүниежүзілік соғыс кезінде кең қолданылған болатын. Жалпы неміс Enigma машинасынан өзге Sigaba, Турех, Red, Orange, Purple2 пайдаланған болатын. Роторлық жүйелеріндегі-ресми криптографияның шырқау шегі болып табылады, өйткені олар салыстырмалы түрдегілердегі тұрақты шифрлар тарататын болған болатын. Роторлық жүйелердегілері байланысты сәтті криптошабуылдар 40-жылдары ЭЕМ-нің пайда болуымен мүмкін болып айқындалады.
Сонымен барлық ғылымилардағы криптографияның айрықша белгілерімен қатар (XX ғасырдың 30-60-жылдарымен қатар ) барлық жоғары математикалық негізделгендегі тұрақты криптожүйелерінің пайда болуымен қатар болып келеді. Сонымен қатар 30-жылдардың басына қарай ғылыми түрдегі криптографияның негізі болып айқындалатын математика бөлімдерімен қатар толық қалыптасқан болып отыр, жалпы ықтималдықтар теориясымен қатар немесе математикалық статистикаларымен, жалпы алгебралар арқылыда, сандар теориясымен, алгоритм теориялары арқылы ақпарат теорияларымен қатар, кибернетикалары болып табылады. Ерекше бөлімі болып Клод Шеннонның Құпия жүйелердегі байланыс теорияларымен қатар (1949) атты түрегі еңбегі болып келеді, мұнда ақпаратты криптографиялық қорғаудың теориялық принциптерімен қатар айқындалған болатын. Жалпы шеннон араласулары және сонымен бөліну атты ұғымдарды енгізілген болатын.
Сонымен жалпы 60-жылдардағы көшбасшылардағылары мен қатар криптографиялықтардағылары мектептермен блоктық сандардың жасалуына көшті, олар роторлықтарымен криптожүйелермен салыстырғандағы аса тұрақты, алайда олардағы тек сандық электронды құрылымдарды жүзеге асырудағылары ғана қамтамасыз етілетін болды.
Сонымен қатар компьютерлік криптографиялардың (XX ғасырдың 70-жылдары) өнімділігі криптожүйелерінің таратуға жеткіліктілігі, шифрлеудің жоғары жылдамдығын қамтамасыз ететіндігі және олармен қатар қолдық және механикалық шифрлардің есептеулердің машиналарының шығуына байланысты пайда болып табылады.
Криптожүйелеріні алғашқы кластарымен қатар болып қолданулары кезіндегілерінің қуатты әрі жинақты есептеулерімен құралдарының пайда болуына байланыстылығы шыққан блоктық шифрлармен болып айқындалады. 70-жылдардағы шифрлеулерінің DES американдық стандарты жасалынған болатын Солардың авторларының бірі болғандығы Хорст мен Фейстел, олар блоктық шифрларымен қатар моделін айқындап, соның негізіндегі жасалынған аса тұрақты симметриялық криптожүйелерді пайдаланылатын.
Сондықтан DES-тердің жалпы пайда болуларымен қатар криптоанализ байланысты, американдық алгоритмдерге шабуылдары үшін бұлар криптоанализдердің жалпы түрдегі бірнеше тәсілдері жасалынады (сызықтық, дифференциалды және тағыда басқа), практикалық қолданылулары жағынан тек есептеулерінің машиналардың пайда болуымен мүмкін болып табылады.
Жалпы 70-жылдың ортасындағы қазіргі кездегі криптографияда төңкеріс болып айқындалады - асимметриялық криптожүйелердегі жалпы пайда болғандағы, ол жақтардағыларының арасындағылары бір-біріне құпия кілттің таратылуындағы қамтамасыз етілетін қолданылады. Осындай негізгі еңбек тердегі Уитфилд Диффимен және Мартин Хеллманмен 1976-жылы жарияланған Қазіргі кездегі криптографиялары бағыттары болып айқындалады. Бұл жердегі ең басындағы болып шифрліктері ақпараттардың кілтсіз таратылуларындағы принциптерімен қатар негізделген болып айқындалады. Асимметриялық криптожүйелердің жалпы идеяларына тәуелсіз қатысты болып айқындалады. Жалпы айтқанда Ральф Меркли болып қолданылды. Бірнеше жылдардан кейінгі Рон Ривест, Ади Шамир немесе Леонард Адлеман RSA жүйесін ашқан болатын, олар дегеніміз алғашқы уақыттардағы практикалық түрдегі асимметриялық криптожүйелерімен қатар болып қолданылды, олардың тұрақтылығымен үлкен сандарының факторизациясымен байланысты мәселесіне негізделген болып қолданылады. Асимметриялықтар криптографиялар бірден бірнеше қолданбалы болып бағыттар арқылы ашқан болатын, сонымен электронды сандық қолтаңба және электронды ақша болып айқындалды.
Жалпы айқтанда 80-90-жылдардағы фейстелдік еместігі шифрлар жасалды (SAFER, RC6), ал 2000-жылы ашық халықаралық сайыстан соң шифрлеудің АҚШ-тың жаңа ұлттық стандарттарының AES шықты болған болатын. Соғыстан кейінгілерінің кезеңнен бастап осы күндегі дейін есептеулері машиналардың пайда болуы болып криптографиялық әдістерінің жаңартылуларымен қатар өңделуін қамтамыз еткен болатын. Неліктен криптографиялық әдістерінің қолданулары ақпараттықтардың жүйелердің ең маңыздысы мәселесі болып айқындалды. Бір жағынанда, компьютерліктер торлардалары қолданулары арқылы кеңейді, негізіндегі, мемлекеттіктегі, әскери, коммерциялық және жеке түрдегілері ақпараттың өте үлкен мөлшеріндегі таратылатын ғаламдықтары торап интернет жүйесіндегілерінің қолданулары кеңейген болатын. Басқа жағындағылары, жаңа қуаттағылармен компьютерлердің пайда болуы болып табылған болатын, жүйелік немесе нейрондық есептеулердің технологиясымен қатар жақында ғана анықтаулары мүмкіндігі емес деп саналған криптографиялық жүйелердің дискредитациясына қол жеткізуге мүмкіндік берілген болатын. Ақпаратты түрлендірулері арқылы қорғаулар мәселесімен криптологиялары (kryptos - құпия, logos - ғылым) пайдаланатын болып табылады. Криптологиялары екі бағытқа бөлінетін болады - криптографиялары және криптоанализ болып табылады. Бұлардағы бағыттардың мақсаттары қарама-қарсы болып табылады.
Криптография ақпаратты түрлендіруде математикалық әдістерді іздеу және зерттеумен айналысады. Криптоанализдің айналысатын сфералар жүйесі - ақпараттың кілтін білмей шифрын анықтау.
Қазіргі криптография өзіне 4 үлкен бөлімді қосады:
- симметриялық криптожүйелер;
- ашық кілтті криптожүйелер;
- электрондық қолтаңба жүйелері;
- кілттерді басқарулары.
Криптографиялық әдістерінің қолданудың негізгі мақсаты - байланыс каналдары арқылы жасырын ақпаратты таратулары (мысалы, электрондық пошталар), жіберілгендігі хабарламалардың ақиқаттығы, шифрлі түрде ақпаратты сақтаулар болып табылады.
Криптографиялық жүйелерінің қаншалықты қиындары және сенімді болғанымен олардың практикалық қолданылуының әлсіз жағы-кілттерді үлестіру мәселесі болып табылады. Ол үшін ақпараттық жүйелерінің екі субьектісімен олардың арасындағы жасырын ақпараттарын алмасулары мүмкін және кілт солардың біреуімен генерацияланулары қажжет болып табылалады, жасырын түрдегі әрі қарай басқасына жіберілуі қажет болып табылады. Дегенмен барлық кілтті таратулар үшін криптожүйелерді қолдану қажет болып табылады. Бұл мәселені классикалық және қазіргідегі алгебрадан алынған нәтижелері негізінде шешулер үшін ашық кілтті жүйелер ұсынылатын болып табылады. Бұлардың барлық мәні ақпараттық жүйелерінің әрбірдегі хабар алушысымен екі кілт генерацияланады, олар бір-бірімен белгілі ережелерге сәйкес байланысты болады. Бір кілт ашық, екіншісі жабық болып жарияланатын болады. Ашық кілт жарияланады және кез-келген хабарлама жібергісісінің келетін адам үшін белгілі болып айқындалады. Құпия кілт жарияланбайтын болады.
Сонымен қатар бастапқы мәтіндегі хабар алушының барлық ашық кілтімен шифрленіп, оларға жіберілетін болады. Шифрленген мәтіндердің негізінен ашық кілтпен байланысты шифры анықталулары мүмкін емес болып табылады. Хабарламаны дешифрлеулер тек хабар алушыға ғана белгілі болатын жабық кілтті қолданулар арқылы ғана мүмкіндік болып саналады. Ашық кілтті криптографиялықтар жүйелер қайта оралмайтын немесе біржақты функциялар деп аталатындықтан ортақ қасиеті бар жұмыс істейтін болады. Берілген х үшін f(x) мәнін есептеу оңай болып табылады, алайда тек y=f(x) болса, х есептеудің оңай тәсілі жоқ дегенді білдіреді.
Жалпы біржақты функциялардың көптеген кластары ашық кілтті жүйенің көптүрлілігін тудындайтын болады. Алайда біржақтылары функциялардың барлығымен қатар ақпараттық жүйесінде қолдануға жарай берілмейтін болады. Қайта оралмайтындар деген түсініктемелерде теориялық қайта ораламсыздығы еместігі, белгіленген уақыттары интервалында қазіргі уақыттағы есептеу құралдарын пайдалану арқылы кері мәнін практикалық тұрғыдан есептей алмау болып айқындалады. Сонымен қатар,ақпаратты тиімді сақтаулары үшін ашық кілтті жүйелерге екі айқын әрі маңызды талап қойылатын болады:
- бастапқы мәтіндерінің түрленуі қайтымсыз болу қажет болады және ашық кілт негізінде қайта қалпына келмеу қажет болып табылады.
- ашық кілт негізінде жабық кілтті анықтаулары жаңа технологиялық тұрғыдан мүмкін емес болу қажеттігін білдіреді. Мұндай шифрды анықтауда күрделіліктерін төменгі бағасы көрсетілуі қажеттігін білдіреді.
Ашық кілтті шифрлеулер алгоритмдері кең қолданысқа ие болып табылады. RSA алгоритмдерінің ашық жүйелері үшін әлемдік дефакто стандарттары болып табылады. Қазіргі уақытта ұсынылатын ашық кілтті криптожүйелерінің қайтымсыз түрленудің төмендегідей топтарына жіктеліп қарастырылады, оларға жататындары мыналар:
- үлкен сандарды көбейткіштерге жіктеулер;
- соңғы өрісте логарифмді есептеулер;
- алгебралық теңдеулердің түбірлерін анықтаулар болып.
Ашық кілтті криптожүйелерді үш түрлі мақсатта қолдануға болады, оларға жататындар:
- жіберілген және сақтаудағы мәліметтердің өзіндік қорғаулары құралы ретінде болып саналады;
- кілттерді үлестіру құралы ретіндегеліре және ашық кілтті жүйелердег алгоритмдері дәстүрлі криптожүйелермен салыстырғанда аса көп еңбекті қажетті болып табылады;
- тұтынушыларды аутентификациялаулары құралы ретінде болып табылады.
1.2 Күрделілік теориясы
Күрделілік теориясында криптографиялық әдістерімен алгоритмдердің әр түрлі есептеулерінің күрделіліктеріне қарай әдістемелік талдаулар жасауға мүмкіндік бере алады. Олар дегеніміз криптографиялық әдістермен қатар алгоритмдерін салыстырулары арқылы, оның қаншалықты қауіпсіздігіне екендігін анықтайтын болады.
Алгоритмнің күрделілігіне жататындар: Алгоритмнің күрделілігі оның орындалуға байланысты керекті есептеуліктері қуаттарымен бірге есептеледі. Есептемелік алгоритмнің жалпы күрделілігімен қатар мынадай екі параметрмен өлшенетін болады, олар: T(уақытқа байланыстағылары туындайтын күрделілік) және S (кеңістікке байланыстылары туындайтын күрделілік және жадыға қойылатын талаптары) болып табылады. Дегенмен жалпы T және S, n айнымалысына тәуелділігі функция ретінде қарастырылатын болады. Мұндағы, n-бұл қабылданғандағы ақпараттардың шамасы болып табылады. Жалпы айтқанда есептемелік алгоритмнің күрделілігін жалпы функциясы арқылы жазылады. Олар күрделілік функциясының жай бөлшектерге жіктеулерінің түрлері болып табылады. Мысалыға айтар болсақ, егер 4n2+7n+12 алгоритмінің уақытқа байланыстылығы туындайтын күрделілігі болғандықтан, есептеулік күрделілігі n2 болып келеді, оны О(n2) деп белгілейтін боламыз.
Алгоритмдерді жалпы олардың уақыттық және де кеңістіктік күрделілігіне қатар олармен байланысты жіктейтін болады. Егерде алгоритм n-ға тәуелді болмаса, онда ондай алгоритмдерді тұрақты деп атап атады, О(1) деп белгілейді. Егер уақыттық күрделілігі О(n) болып табылса, онда алгоритмді сызықтық деп атайтын боламыз. Сонымен қатар жалпы алгоритмдердің квадраттықтылығы, кубтық немесе тағы да басқа түрлері болып табылады. Бұлар дегеніміз алгоритмдердің барлығы-полиноминалды болып айқындалады, ал олардың күрделілігімен қатар О(nm), мұндағы m - тұрақты шама болып табылады.Уақыттық күрделілігімен қатар барлық жалпы қарастырылған полиноминалды алгоритмдерді полиноминалды уақыттық алгоритмдер деп санайтын боламыз.
Жалпы күрделілігі О(tf(n)) есептелетін алгоритмдерді экспоненциалдық алгоритмдер деп атаймыз, мұндағы t - бірден үлкен тұрақты шама, ал f(n) - белгілі бір полиноминалды функциясы болып саналады. Күрделілігіне О(сf(n)) есептелетін экспоненциалдықтарға алгоритмдердің жалпы түрдегі жиынын суперполиноминалды деп анықтайды, мұндағы с-тұрақты шамалар, ал f(n) тұрақтыдан қарағанда тездетіп өсетіндер делінген, бірақ сызықтыдан баяуларымен қатар болатын функциясының бірі болып саналады.
1.1-кесте. n=106 шамасындағы әр түрлі алгоритмдердің жалпы уақыт күрделілігіне тәуелділігі
Түрлері
Күрделілігі
n=106 үшін операциялар саны
Қажет болатын уақыт
Тұрақтылығы
О(1)
1
1 мкс
Сызықтықтары
О(n)
106
1 с
Квадраттықтар
О(n2)
1012
11.6 күн
Кубтықтар
О(n3)
1018
32000 жыл
Экспоненциалдық
О(2n)
10301030
Біздің ғаламымыздың өмір сүру уақытынан 10301006 есе үлкен
Сонымен қатар жалпы компьютерлер үшін уақыттың өлшемділігінің бірлігі микросекундтарымен болғандықтан, компьютерлердегі тұрақты алгоритмдерді-1 микросекундтасы арқылы, сызықты алгоритмдерді-1 секундта, ал квадратты алгоритмдері-11.6 күнде есептей алатын болған. Кубтық алгоритмдердің жалпы 32000 жылдарындағы есептейтін болғандықтандағы, экспоненциалдық алгоритмдер туралы айтудың қажеті жоқтығын білеміз.
Шифрленген алгоритмдерді күшпен ашулары арқылы проблемасын қарастыратып көретін боламыз. Мұндай ашулардың уақыттылықтарымен қатар күрделілігі мүмкіндігі болатындары кілттердің санына тура пропорционал болып келеді. Сонымен кілттің ұзындығынан тәуелді деген сөзді білдіреді. Егер n - кілттің ұзындығы болатын болса, ал онда күшпен салып ашудың күрделілігі О(2n)-ге тең болып табылады.
Проблеманың күрделілігіне жататындар:
Күрделілік теориясымен қатар белгілі бір алгоритмдердің шешудің проблемасына ғана қарастырмайтын болады, дегенменде жалпы проблеманың қаншалықты күрделілігі екенін де анықтайтын боламыз. Атап айтқанда олар сол проблеманы шешуге керекті минималдылары уақытты және жадының көлемін қарастыратын болады. Оларды Тьюринг машинасы деп атайтын болады. Тьюринг машинасымен қатар шекзіз жадымен жабдықталғандығына қарай, алгоритмді оқу және жазу үшін арналған есептеудің наңыз моделі болып айқындалатын болған.
Полиноминалды уақыттық жалпы алгоритмдер арқылыда шешілетіндігі проблемаларды шешілетін проблемалар деп атайтын болады. Яғни, оларда белгілі ақпараттары үшін белгілі уақыттары бөлініп, сол уақыттағылармен қатар шешілетін болады. Полиноминалдылардағы уақыттары ішінде шешілмейтін проблемаларды шешілмейтін деп атайтын боламыз. Кейбір жағдайлардағы, шешілмейтін проблемаларды қиын (ауыр) проблемалар деп те атайтын боламыз. Алан Тьюринг кейбіреулері проблемаларды шешудің алгоритмін табу мүмкін еместігін дәлелдейтін болады.
Барлық проблемалардың және олардың шешілуіне байланысты барлық сәйкесінше кластарға бөлуге болатындығын айтамыз. Ең маңыздысы кластар төменде көрсетілген болып табылады.
1.1-сурет. Шешілетін проблемалар класы
Сонымен қатар ең төменгі жағында орналасқан Р класы полиномиальды уақыттардағы жалпы шешуге болатындығы барлық мәселелерден тұратын болады. NP-класы-полиномиальды уақыттағыларын тек барлық Тьюрингтің детерминацияланбаған машинасында шешуге болатындығын барлық түрдегілер мәселелер болып саналады және оларға жататынжар мыналар: жорамал жасай алатын Тьюрингтің қарапайым машинасының нұсқасы дегенді айтамыз. Машина мәселенің шешуіндегілері жорамалдай алады- не сәтті табу арқылы, не болмаса барлық жорамалдарды параллельды таңдап, барлық жорамалдарды полиномиальды уақытта тексеретін болады.
NP-ның криптографиядағы маңызы және оларға енгізілетіндер: көптеген симметриялықтардағы алгоритмдер және ашық кілттілердегі бар алгоритмдер детерминацияланбаған полиномиальды уақытта бұзылуы мүмкіндігін айтамыз. Берілген С шифрлік мәтіндері үшін криптоаналитик Х ашық мәтінді және к кілтін талғайды және полиномиальды уақытта Х және к арқылы шифрлеу алгоритмін тексере отырып, оның нәтижесіндегі С-ға тең болу мәселесін тексеретін болады. Бұлардың теориялық маңыздылығы зор, себебі осы алгоритмдердің барлық криптоанализінің күрделілігінің жоғарғы шегін анықтайтын боламыз. Тәжірибеде бұл әрине барлық полиномиальдылары уақыттарымен орындалатын детерминацияланған алгоритмдері, дәл осыны криптоаналитик іздеу тиіс деп айтамыз. Осындай алгоритмдері шифрлердің барлық класстарына байланысты бірдей қолданыла алмайтындығы, ол бір қолдануларға жарайтын блокноттар үшін жарамайды кез-келген С үшін Х, к көптеген жұптары шифрлеу алгоритмін орындау кезіндегі С-ны береді, бірақ Х-тің көбісі мәнсіз, мүмкін бола алмайтын ашық мәтіндер болып табылады.
NP-класына Р класы кіреді, себебі полиномиальды уақытта орындалатындығы Тьюрингтің детерминацияланған байланыс машинасында орындалатын кез-келген мәселелер полиномиальды уақытта Тьюрингтің детерминацияланбаған машинасында орындала алады, тек жорамалдау сатысы болмайды.
Дегенмен барлық NP мәселелердің Тьюрингтің детерминацияланғандығы машинасында полиномиальды уақытта орындалатын болса, онда Р = NP болып табылады. Сонымен кейбір NP мәселелер басқаларымен салыстырғанда аса күрделілігі және ешқашанда Р-ның NP-ға тең еместігі дәлелденбеген болып табылады. Сонымен қатар күрделілік теориясы саласында жұмыс жасайтын адамдардың барлығы бұл класстар тең бола алмайды деген пікірді ұстанатын болған.
Барлыңы ең маңыздысы нақты NP-мәселелер осы класстың басқа мәселелері секілді өте қиын екендігін дәлелдеуге болатындығында болып отыр. Стивен Кук орындалушылық мәселесінің NP-толық болатынын дәлелдеген болатын. Бұлар дегеніміз-егер орындалушылық мәселесі полиномиальды уақытта шешілсе, онда олардағы Р = NP болып көрсетіледі, керісінше егер NP класының кез-келген мәселесі үшін шешімнің полиномиальды уақыты бар детерминацияланған алгоритмі болмайтындығы дәлелденсе, орындалушылық мәселесі үшін де полиномиальды уақыты бар детерминацияланған алгоритмі болмайтындығын дәлелдеу көрсететін болған. NP-да орындалушылық мәселесінен ауыр мәселе жоқ болып табылады.
Сонымен қатар куктың негізқалаушылық жұмысы басылғаннан соң, орындалушылық мәселелеріне байланысты эквивалентті мәселелер бар екендігі анықталатын болады. Эквиваленттілікке байланыстардағы жалпы бұл мәселелерде NP-толық болып, NP класына кіретін барлық мәселелер тәрізді қиын мәселе болып табылады деп білеміз. Егер олардың барлық детерминацияланған полиномиальды уақытта шешілетіндігі дәлелденсе, онда Р сұрағының NP-ға қарсы сұрағы шешімін табатын болады. Р = NP сұрағы рас па екендігі күрделі есептеулері арқылы теориясының негізгі шешілмеген сұрағы болып саналатын болған және жақын арада өз шешімін табады деп күтіледі. Егер Р = NP болатындығын біреу көрсете алса, онда осы кітаптың біраз бөлігі қажетсіз болып табылады және оларға жататындар: шифрлардың көптеген класстары детерминацияланбаған полиномиальды уақытта бұзылады дегенді білдіреді. Сондықтан Р = NP болса, онда олар әлсіз детерминацияланған әлсіз алгоритмдермен бұзылады деп білеміз.
Сонымен қатар жалпы кейінгі болып күрделілік иерархиясында PSPACE класы жүргізілетін болады. Сонымен PSPACE класының мәселелері болып полиномиальды кеңістікте шешілуі мүмкін немесе полиномиальды уақыттары ішіндегі шешілуілері міндетті емес болып келетін болады. PSPACE өзіне NP -ны қосады, бірақ PSPACE мәселелері NP-ға қарағанда аса күрделі болып табылады. Әрине, бұлар әлі дәлелденбеген болатын. Сонымен қатар, PSPACE-толық деп аталатын келесі қасиетке ие мәселелер класы бар және егер олардың кез-келгені NP-мәселе болса, онда PSPACE = NP, және егер олардың кез-келгені Р-мәселе болса, онда PSPACE = P болып табылады. .
Жалпы EXPTIME мәселелер қатарлары болып саналады. Бұлардың мәселелер экспоненциалды уақытта шешіледі деп білеміз. EXPTIME-толық мәселелер расында да детерминацияланған полиномиальды уақыт аралығында шешіле алмайтындығы дәлелденуі мүмкін болып табылады. Сонымен қатар, Р EXPTIME-ге тең болмайтындығы дәлелденген болатын.
1.3 Сандар теориясы
Айыру арифметикасын барлығымызға мектеп кезінен мәлім. Оны кейде арифметикалық сағат деп те атайтын болған. Егер Милдред әкесіне үйде 10:00 болам деп айтып, 13 сағатқа кешігіп қалса, онда үйіне ол қашан келеді және неше жылға әкесі оны жүргізуші құқығынан айырады? Бұл арифметика 12 модуль бойынша. Жиырма үш 12 модулі бойынша 11 болып табылады.
(10+13) mod 12 = 23 mod 12 = 11 mod 12
Бұларды басқаша 23 пен 11 эквиваленттігі бойынша 12 модулімен жазуға болатынын білеміз:
10+13 =11(mod 12)
Көбінесе, егерде а = b+кn кейбіреулері бүтін к үшін болса, а = b (с) болып табылады. Дегенмен а кері емес болса және b 0 мен n аралығында орналасса, онда b-ны а-ның n-ға қатынасы кезіндегі қалдығы деп қарастыруға болып табылады. Әр кездері b а n модулі бойынша есептен алу деп айтылатын болған. Кейде олардағы а n модулі бойынша конгруэнтты b деп те аталады. Екеуі де бір мағынаны білдіретін.
0-ден n-1-ге дейінгі сандар жиыны n модулі бойыншада есептен алудың толық жиынын құрайтын болған. Бұлар дегеніміз кез-келген бүтін а үшін оның қалдығы n модулі бойынша 0 мен n-1 аралығында орналасқан кез-келген сандары болып айқындалады.
а mod n операциясы 0 мен n-1 аралығында орналасқан кез-келген бүтін а-ның қалдығын білдіреін білеміз. Бұл операциялардағы модульге келтіру деп аталатын айтамыз. Мысалыға айтар болсам, 5 mod 3= 2 деп білеміз.
Бұлар дегеніміз mod анықтамасы бағдарламалауларына олардың тілінде көрсетілген анықтамалардан ерекшеленуі мүмкіндігін білдіреді Мысалыға айтар болсақ, PASСAL тілінде қалдықты алуларымен қатар операторы кейде кері сан шығарылатын болған. Олар -(n-1) және n-1 аралығындағы санды қайтарылып беріледі. С тілінде % операторы бірінші өрнекті екіншісіне бөлуден алынған қалдықты қайтарылады, олар егерде операндалардың кез-келгені кері сан болса кері мән берілетін болады. Мұндай кітаптағы барлық алгоритмдер үшін егер ол кері санды шығарып тұрса, қалдықты алу операциясының нәтижесін алулары үшін не қосатындығын тексерілетін болған.
Сонымен қатар қалдықтар арифметикасы жай арифметикаға өте ұқсас:ол коммутативті және дистрибутивті болып саналады. Сонымен қатар, жалопы әрбір аралық нәтижені n модулі бойынша келтірулері жалпы есептеудегі соңғы нәтижені n модулі бойынша келтіргендегі нәтижені беретін болады.
(а+b) mod n=((а mod n)+(b mod n)) ) mod n (1.1)
(а-b) mod n=((а mod n)-(b mod n)) ) mod n (1.2)
(а.b) mod n=(( а mod n).(b mod n)) ) mod n (1.3)
(а.(b+с)) mod n=(((а.b) mod n)+((а.с) mod n)) mod n (1.4)
mod n есептеулері әдетінде криптографияда көп қолданылатын болады, өйткені дискретті логарифмдер және mod n квадраттық түбірін есептеулері оңай емес мәселе болуы қажет болып саналады. Есептен шығарулары арифметикасы компьютерлерде оңай жүзеге асады, өйткені ол аралық мәндер мен нәтижелер диапазонын шектейді. n-ның к-битті есептеулеріне кез-келген қосулары, алулары және көбейтудің аралық нәтижелері 2 к биттен артық болмайтыны болып табылады. Сонымен қатар барлық есептеулердегілердің арифметикасында дәрежеге келтіру үшін үлкен аралық нәтижелерді қолданбай орындауға болытынын білеміз. Кейбір әр санның дәрежесін басқа санның модулі бойынша есептеулері көбейтулері мен бөлудің тізбегі болып табылады, алайда оларды тездететін тәсілдер бар болып келеді:
ax mod n (1.5)
Сондай жалпы тәсілдердің бірі модуль бойынша көбейтулер санын азайтуға тырысатын болған, екіншісі бойынша -модуль бойынша жеке есептеулерді қолданулары болып табылады. Операциялар дистрибутивті болғандықтан, дәрежеге келтіруді тізбекті көбейтулер ағынын әр ретте олардың нәтижелерін ала отырып тез орындауға болады. Қазір сіздер айырмашылықты байқамайсыңдар, бірақ ол тек 200-биттік сандарды көбейткен кезде білінеді.
Мысалы, егер сіз а8 mod n есептегіңіз келсе, оны 7 рет көбейтіп, 1 рет модулі бойынша келтірудің қажеті жоқ:
(а.а.а.а.а.а.а) mod n
Оның орнына 3 кіші көбейтулер мен 3 кіші модульге келтіруді орындаңыз:
((а2 mod n)2 mod n2) mod n
Дәл осылай,
a16 mod n =(((а2 mod n)2 mod n)2 mod n)2 mod n
aх есептеу, мұнда х 2-нің дәрежесі болмайды, аса қиын емес. Екілік жазба х-ті 2:25 дәрежелер қосындысы түрінде береді- бұл бинарлық 11001, сондықтан 25=24+23+20. Сондықтан
a25 mod n=(а.а24) mod n=(а.а8.а16) ) mod n=(а.((а2)2)2)(((а2)2)2)2) mod n=(а.а(((а.а2)2)2)2) ) mod n
Аралық нәтижелерді ойластырылған сақтаумен енді тек 6 есептеу қажет:
(((((((а2mod n).а) 2mod n) 2 mod n) 2 mod n) 2 mod n) 2.а) mod n
Мұндай әдіс қосу тізбегі немесе екілік квадрат пен көбейту әдісі деп аталады. Ол негізінде санның екілік көрінісі жататын қосудың жай және айқын тізбегін қолданады.
Модуль бойынша кері мәнде:
Кері мән дегеніміз не екендігі естеріңізде ме? 4-14 үшін кері мән, себебі 4.14=1. Есептеу әлемінде мәселе күрделенеді: 4.х=1(mod 7)
Бұл теңдеу х пен к анықталуына эквивалентті, 4х=7 к+1
Мұнда, х пен к -бүтін сандар. Жалпы есеп мақсаты х-ті табу, ол
1=a.xmod n (1.6)
Бұны былай да жазуға болады:
a-1=xmod n (1.7)
Модуль бойынша кері мәндерді есептеу оңай емес. Кейде оның шешімі болады, кейде болмайды. Мысалы, 5 санының модулі бойынша кері мәні 14 модулі бойынша 3-ке тең. Басқа жағынан 2 санында 14 модулі бойынша кері мәні болмайды.
Жалпы жағдайда, (7) теңдеуінде а мен n сыбайлас жай болса, тек қана 1 шешімі болады. Егер а мен n сыбайлас жай болмаса, онда (7) теңдеуінің шешімі болмайды. Егер n жай сан болса, онда 1-ден (n -1)-ге дейінгі кез-келген сан n-мен сыбайлас жай болады және n модулі бойынша дәл сондай кері мәнге ие болады.
Эйлер функциясы:
Кері мәнді есептеудің басқа да әдісі бар, алайда оны әр кезде қолдана беруге болмайды. mod n берілген қалдықтар жиынтығы деп қалдықтардың толық жиынын жиын бөлігі және оның мүшелері n-мен сыбайлас жай болады. Мысалы, mod 12-нің келтірілген қалдықтар жиыны -{1,5,7,11}. Егер n -жай сан болса, онда mod n-нің келтірілген қалдықтар жиыны бұл- 1-ден n-1-ге дейінгі сандардың жиыны. 1-ге тең емес кез-келген сан үшін 0 саны ешқашан берілген қалдықтар жиынының құрамына кірмейді.
Эйлер функциясын φ(n) түрінде жазады, - бұл n модулі бойынша берілген қалдықтар жиынындағы элементтер саны. Басқаша айтқанда, φ(n)- n-нен кіші және онымен сыбайлас жай сан болатын бүтін оң сандар саны.
Егер n-жай сан болса, онда
φn=n-1 (1.8)
Егер мынадай теңдеу белгілі болса,
n=pq (1.9)
мұндағы р мен q-жай сандар болса, онда
φn=p-1q-1 (1.10)
болады. Бұл сандар кейбір алгоритмдерде ашық кілтпен келеді. Бұның себебі мынада: Эйлер теоремасы мен Ферманың кіші теоремасын сәйкес жалпылағанда, егер ЕҮОБ(а, n )=1 болса, онда
aφnmod n=1 (1.11)
Енді а-1 mod n есептеу қиын емес:
x=aφn-1mod n (1.12)
Мысалы, қандай сан 7 модулі бойынша 5 санына кері мәнге ие болады? 7 жай сан болғандықтан, φ(7) =7-1=6.
Осылайша 5 санына 7 модулі бойынша кері мән мынаған тең болады:
56-1 mod 7=55 mod 7=3.
Бұл кері мәндерді есептеу тәсілін х мәнін табудың ортақ мәселесіне кеңейтуге болады:
a.xmod n=b (1.13)
Эйлер жалпыламасын қолдана отырып, мынаны шешеміз:
xb.aφn-1mod n (1.14)
Эвклид алгоритмін қолдана отырып, мынаны табамыз:
x=b.a-1mod nmod n (1.15)
Жалпы жағдайда кері мәндер алгоритмін есептегенде Эвклид алгоритмі Эйлердің жалпыламасына қарағанда тезірек, әсіресе 500 битті сандар үшін. Егер ЕҮОБ(а, n )!=1 болса да шешімін табуға болады. Бұл жағдайда (а*х) mod n= b, не бірнеше шешімі, не бірде-бір шешімі болмайды.
Лежандр символы:
Лежандр символы L(а,р) егер а - кез келген бүтін сан болса, ал р-2-ден үлкен жай сан болса анықталған болады. Ол 0,1 немесе -1-ге тең болады.
L (а, р) =0, егер а р-ға бөлінсе.
L (а, р) =1, егер а -р модулі бойынша квадраттық есептен алу болса.
L (а, р) =-1, егер а -р модулі бойынша квадраттық есептен алу болмаса.
La,p=ap-12mod p (1.16)
Немесе келесі алгоритмді қолдануға болады:
1) Егер а=1 болса, онда L(а,р) =1
2) Егер а жұп болса, онда L(а,р) = L(а2,р)*(-1)(у2-1)8
3) Егер а жұп болмаса, онда L(а,р) = L(р mod а,р)*(-1)(а-1)(р-1)4
Көбейтінділерге жіктеу
Көбейтінділерге жіктеу дегеніміз - оның жай көбейтінділерін табу деген сөз.
10=2.5
60=2.2.3.5
252601=41.61.101
2113-1=3391.23279.1868569.65993.106 6818132868207
Көбейтінділерге жіктеу сандар теориясының ең көне мәселесі болып табылады. Бұл процесс қиын емес, тек уақыт талап етеді. Қазіргі таңда ең күшті алгоритм болып мынау табылады:
Сандардың сандық өрісінің торы - бұл 110 және одан да көп бөлік үшін ең тез алгоритм болып табылады. Алғашқыда ол пайдалы болған жоқ, алайда соңғы жылдары ол жақсартылған. Ол көбейтінділерге жіктеуді өте тез орындау үшін әлі біршама жаңа, алайда жақын арада барлығы өзгереді.
Квадраттық тор - бұл 110 ондық бөліктен кіші сандарды көбейтінділерге жәіктеудегі ең тез әдіс. Бұл әдістің жаңартылған нұсқасы полиномиальды квадраттық тор болып табылады. Ең тез нұсқасы полиномиальды квадраттық тордың үлкен санды екілік вариациялау әдісі болып табылады.
Эллипстік қисық әдісттеріне жатқызатындарымыз-43 бөліктегілрдегі көбейтінділерді жіктеуде қолданылатындығын айтамыз.
Монте-Карло Поллард әдістеріне жатқызатынымыздар; Үзіліссіз бөлшектер алгоритмдерінің-бұл алгоритм орындалу уақытына сай келмейтіндігін айтады.
Екілік санау жүйелеріне жатқызатындарымыз:
Екілік санаулар жүйелерінің математиктері мен философтармен компьютерлерінің шықпас бұрынғы (XVII-XIX ғасырларда) пайда болған болатын. Белгілі математиктер Лейбниц: "Екілер арқылы санаулардағы ғылым үшін ең негізгі болып айқындалады-деп көрсеткен болатын. Сонымен қатар жалпы сандарды қарапайым түрлерге келтіру кезіндегілері 0 мен 1 болғанда , әр жерде тамаша тәртіп пайда болғандығы. Солардан кейін екілік санау жүйелері ұмытылатын болған, тек 1936-1938 жылдарындағы американдық инженер және математик Клод Шеннон екілік санаулар жүйелерінің конструирленген электрондық схемалары үшін қолданысын тапқан болатын.
Сонымен қатар екілік санау жүйелері-негізі 2 болатын санау жүйесі дегенді білдіреді. 0 мен 1 сандары қолданылатын болады. Екілік санаулардағы жүйесі сандық құрылғылармен қатар қолданылатын болады, себебі әлдеқайда ыңғайлы және барлық талаптарға сай келеді екен:
oo Жүйелердегі жалпы мәндеріне қаншалықты аз болатын болса, соншалықты жеке элементтер дайындау ыңғайлы болып саналады.
oo элементтің күй элементтері аз болған сайын да, оның кедергігелері шыдамдылығы жоғары болып саналады және ол соншалықты тез жұмыс атқаратын болады.
Қосулар мен көбейтулерді жасау кестесінің қарапайымдылығы-сандарға қолданылатын қарапайым амалдарына бірге болып табылады.
1.4 Жай сандар генерациясы
Жай сан деп-бірден үлкен және тек бірге дейінгі, өзіне ғана бөлінетін бүтін сандарды айтамыз: ол басқа ешқандай сандарға олармен бөліне алмайды. Екі - жай сандар болып қалады. Жай сан болып 73, 2521, 2365347734339 және 2756839-1 бола алатынын айтаыз. Жай сандардың шексіздігіне байланысты көп түрі бар. Ашық кілттегілері криптографиялары көбінесе үлкен жай сандарды пайдаланатын болған, олар (512 бит және одан да көп) болып қалыптасады.
Ашық кілттері бар алгоритмдердердің жалпы бірге үшін жай сандар қажет болып табылады. Олардың біршама үлкендігі желісі үшін көптеген жиыны қажет болып саналады. Генерация математикасына көшпес бұрын бірнеше айқын сұрақтарға жауап беретін болсақ.
Егерде барлық әрқайсысына өзінің жай сандары қажет болатын болса, қор таусылмайды ма? деген сұрақ, әрине жоқ таусылмайды. Шын мәнінде 1-ден 512 битке дейінгі 10151 сан бар. n-ге жақын сандар үшін кездейсоқ таңдалынған сан жай болу ықтималдығы 1ln n болып табылады. Сондықтан да олар жай сандардың n-нен кіші толық сандары n( ln n) болып қарастырылады екен. Әлемде барлығымен қатар 1077 атом түрлері бар болады. Егер ғаламшардағы барлық атомдардары үшін әр микросекунда сайындағы миллиард сандар керек болса, онда жай сандардың тек 10109 керек болатындығында болып отыр, сонда жай сандардың 10151 қала беретіндігін айтамыз.
Егер екі адамдардың бірдей жай санды кездейсоқ таңдаса? Ондай болмайтындығын білеміз және 10151 санддарды таңдағанда сәйкес келулерімен қатар ықтимаалдығы өте аз болып саналады. Егер біреулер барлық жай сандардың базасын құратын болса, онда олар оны ашық кілті бар алгоритмдерді ашуға қолдана ала ма дегенді айтады, әрине жоқ болып табылады. Егерде сіз 1 гигабайт ақпаратты 1 грамм салмағы бар құрылғыда сақтасаңыз да, ондағы ақпаратты одан шығара алмайтындығынызды білдіреді. Егерде барлық көбейтінділерге жіктеулері сонша қиын болатын болса, онда жай сандардағы генерациясы қалайша оңай болатыны білеміз? n саны жай ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Кіріспе
3
1.
Нысанның техникалық шарттары
5
1.1
Криптографияның негізгі түсініктемелері мен тарихы
5
1.2
Күрделілік теориясы
9
1.3
Сандар теориясы
13
1.4
Жай сандар генерациясы
18
Бірінші бөлім бойынша қорытынды
20
2.
Жобаның нысаны
21
2.1
Криптографиялық кілттерді басқару
21
2.2
Симметриялық (құпиялы) әдістемелер мен алгоритмдер
24
2.3
Асимметриялық (ашық) әдістемелер мен алгоритмдер
26
2.4
Ашық кілтті қолданатын алгоритмдер
29
2.5
Ашық кілтті қолданатын алгоритмдердің қауіпсіздігі
30
2.6
Екінші бөлім бойынша қорытынды
31
3.
Нысанның техникалық параметрлерін есептеу
32
3.1
Қол қапшық алгоритмін есептеу
32
3.2
RSA алгоритмі
36
3.3
RSA шифрлеу жүйесі
37
3.4
RSA алгоритмінің жұмыс істеу жылдамдығы
42
3.5
RSA қауіпсіздігі
43
Үшінші бөлім бойынша қорытынды
50
Қорытынды
51
Пайдаланылған Әдебиет тізімі
52
1 қосымша
54
КІРІСПЕ
Диплом жұмысының өзектілігі: Евклид және Диофант, Ферма, Эйлер, Гаусс, Чебышев сонымен Эрмит еңбектерінде диофан түріндегі теңдеулердің шешу жөніндегілері маңызды ойлар бар болып табылады, сол уақыттар үшін үлкен болып саналатын сандарының ең жақын мәндерін іздеу үшін талаптар бар болып айқындалады. Соңғы кездерде екі он жылдардағы криптографиялар ЭЕМ-гі кең тарқалуындағы солармен қатар сұраныстардың дамуытуларына қарай сандар теорияларының алгоритмдіктері сұрақтарына дамуларының қарқынды болып келеді.Сонымен қатар есептеушілердегі машиналарының немесе лектрондықтардың құралдардың адамның барлық қызметтерімеен ой-өрісіне қарай жоғарланады. Бұндайсыз қазіргі кездегі криптографияны елестету мүмкін емес болып айқындалады. Жалпы мәтіндерді шифрлеу арқылы және солармен қатар оны бұзудыда ЭЕМ арқылы бүтін сандардың өңдеу ретіндегілерімен қатар елестетуге болатындығын білеміз, сонымен осындай амалдар орындалатын тәсілдері кейбір функциялары арқылы солай секілді бүтін сандарының белгілі бір жиынындада орында алатын болып саналады. Бұлардың барлығы қазіргі кезде криптографияларда олардың сандарының теорияларымен қатар болуына жағдай жасалынатын болып табылады. Сонымен қатар олармен байланысты, кейбір криптографиялар жүйелерінің тұрақтылығымен қатар тек кейбір сандықтар-теориялықта есептер арқылы да күрделілігімен қатар негізделетін болған болатын. Дегенмен ЭЕМ мүмкіндігі шекті болып айқындалады. Ұзындағы сандық тізбектерді белгілі бір өлшемді блоктарға бөлуге де тура келетіндігінде немесе әр блоктарды бөлек шифрлеуге тура келетін болып айқындалады. Осылардың әр қайсысы біз барлық шифрленетін сандардыңда теріс емес және берілген m санынан кіші емес деп санайтын болатындығымызда болып отыр. Сонымен қатар осындай шектеулер арқылы солармен байланысты одан әрі шифрлеуденде алынатын сандарғада қатысты болып айқындалады.
Соның негізіндегілеріндегі нақты қолданылатындағы шифрлеулер жүйесі алынатын болып табылады, авторлардың барлық есімдерінің алғашқы аттарына сәйкестігімен қатар RSA деп саналатын болатындығында болып отыр. Осындай функциялардың төмендегіндей болып келетіндігін айқындаймыз:
- fx функциясының мәндерінен қатар есептейтін әлдеқайда жылдам әдістері бар болып табылады;
- f-1xкері функцияларының мәндеріндегілері есетейтін жылдам әдістері бар болып табылады;
- fx функциясының құпиясы бар екендігіне, дегенмен оны анықтасақ, f-1x мәндерін тез есептеуге болатындығы болып табылады, сонымен қатар қарсы жағдайда f-1x есептеуге ауыр болатындығы, көп уақытты кетіретін, шешуге мүмкін емес есепке айналатын болып табылатындығында.
RSA осы жылдардың ішіндегі ұсынылған ашық кілттердің қолданатын алгоритмдерінің ішіндегілерінің ең оңай түсінуге және жүзеге асыруға болатын алгоритмдері болып айқындалады.
Бұл дипломдық жұмыс криптографияның ашық кілтті қолданатын алгоритмдердің бірі - RSA-ға арналған болып айқындалады.
Диплом жұмысының мақсаты: Криптографиялық кілттердіңкөмегімен желілерді қорғауды қамтамасыз ету және RSA алгоритмін қазіргі таңдағы технологияларды пайдалана отырып, ақпаратты қорғау саласында кеңінен қолдана алатын автоматтандыру жүйесін құру.
Жұмыстың мақсаты дипломдық жұмыс барысында шешілген келесі міндеттерді анықталған болатын:
oo сандар теориясын, оның бөлімдерінің бірі жан сандарды зерттеу. Өте үлкен жай сандарды іздеу;
oo екілік жүйедегі сандармен жұмыс жасау;
oo ашық және жабық кілттердің құрылымын зерттеу;
oo бір компьютерден екінші бір компьютерге ақпаратты шифрлеп жібергенде, барлық қауіпсіздік ережелерін сақтау және зерттеу болып табыалды.
Дипломдық жұмыс кіріспеден, үш бөлімнен, қорытындыдан, әдебиеттер тізімінен тұрады. Кіріспеде жұмыстың өзектілігі берілген, мақсаты қойылған, сол мақсатқа қол жеткізу міндеттерінен тұратындығын айтамыз.Сонымен қатар зерттеу объектісі және маңыздылығы анықталып қарастырылған болатын.
Бірінші бөлімде криптографияның негізгі түсініктерімен қатар олардың тарихы, олардың жұмыс істеу принциптерімен алгоритмдері, сонымен қоса RSA алгоритмдері пайдаланылатын математикалық негіздемелері туралы теориялық анықтамалар да орын алған болатын. Бірінші бөлімнің басты қорытындысы - криптографияның бастамасын түсіндірулерімен қатар, оның әдістемелерінен қатар алгоритмдеріндегі таныстыру болып табылады.
Екінші бөлім ашық кілтті қолданатын алгоритмдерге, соның ішінде, RSA алгоритміне арналған бөлім болып табылады. Осыларға орай қорытындылар жасалынды.
Үшінші бөлімде NET платформасына, оның құрылымы мен сипаттамасына арналған боылп айқындалады. Сонымен қатар бұл бөлімдегілер C-тың басқа объектілі-бағытталған болып программалардан айырмашылығын көрсетілген болып айқындалатындығында болып отыр.
Сонымен қатар олардағы жұмыстың қойылымына, яғни бағдарламалық бөлімге арналған болып табылады. Онда әрбір батырманың мақсатына дейін айтылып кеткен болып табылады.
1 НЫСАННЫҢ ЖАҒДАЙЫНЫҢ ТЕХНИКАЛЫҚ ШАРТТАРЫ
1.1 Криптографияның негізгі түсініктемелері мен тарихы
Ақпараттарды оларды түрлендірулерімен қатар басқа адам оқи алмайтындай етіп қорғаулардағы мәселелері адамзат алдында бұрыннан тұрған мәселелердің бірі болып айқындалады. Криптографияның тарихы яғни - адамзат тілінің тарихының замандасымен байланысты болып келеді. Олармен бірге, жазу алғашқыда криптографиялық жүйелерінің болуына табылатын, себебі, ежелге қоғамда солармен тек ерекше таңдаулы адамдардан иелік ететін болып табылады. Ежелдегі Египет және Үндістан киелі кітаптарымен қатар соған мысал бола айқындалатындығында болып отыр. Криптография жазудың кең таралуындағы олармен байланыстары дербес ғылым ретінде қалыптаса басталатын болып келеді.
Криптография тарихтарында олармен қатар шартты түрде төрт қадамға бөлңп қарастыруға болады, олар төмендегідей:
oo жай криптографиялар;
oo ресми криптографиялар;
oo ғылыми криптографиялар;
oo компьютерлік криптографиялар болып.
Сонымен қатар жай криптографиялар үшін (XVI ғасырлар басында олармен қатар) қарсыластырылатын кез келген шифрлік мәтін мазмұнына қарай қатысты шатыстыру тән болып табылады. Мысалы, бастапқы қадамдағылары ақпаратты сақтаулары үшін криптографиямен қатар барабар кодтаулары арқылы және стеганография әдістері қолданатын болып келеді.
Көптеген қолданылыстағылардың шифрлар орын ауыстырулар және моноалфавиттіктері ауыстырулары арқылы жүзеге асырылатын болып табылады. Жарияланған мысалдардың бірі болып табылатын Цезарь шифры табылған болып келеді, олардың мәтіндегі алдыңғыдағы әріпті алфавитте одан алыс тұратын әріптерге ауыстырулары арқылы жүзеге асырылатындығында болып отыр. Басқа шифрлері, полибианды квадраттар, грек жазушысы Полибий шығарған, алфавитпен өлшемі 5 және 5 болатын квадратты кестеге кездейсоқ толтырылатын грек алфавитінің көмегімен жүзеге асатын жалпы моноалфавитті орын ауыстыру болып саналады. Барлық әріп квадратта одан төмен тұратын әріппен ауыстырылған болатын. Сондықтан ресми криптография қадамы (XVғ.аяғы-XX ғ. басы) криптоанализдің ресми және салыстырмалы түрде тұрақты шифрлерінің пайда болуымен байланысты болып айқындалады.
5B07.19.РЭТ.5101
5B07.16.РЭТ.01.01
5B07.15.РЭТ.31.01
5B07.15.РЭТ.01.01
Әдеб.
Орындаған
Орындаған
Орындаған
Орындаған
Жетекші
Өлш.
..Өлш.
..Өлш.
..Өлш.
..
Бет
Беттер
ҚР Бжәне ҒМ ҚазККА
РТ кафедрасы
және ҒМ ҚазККА
РТ кафедрасы
Криптографиялық кілттердіңкөмегімен желілерді қорғауды қамтамасыз ету
Бекітемін
Н.бақылау
Н.бақылау
Н.бақылау
Н.бақылау
Қолы
КүніКүніКүніКүні
Бет
Бет
Бет
Бет
Құжат №
Мекебаева А.К.
Т.бақылау
Нурыллаев Н.Д.
Мекебаева А.К.
Кусамбаева Н.
Липская М.А.
5B07.19.РЭТ.5101
5B07.16.РЭТ.01.01
5B07.15.РЭТ.31.01
5B07.15.РЭТ.01.01
Әдеб.
Орындаған
Орындаған
Орындаған
Орындаған
Жетекші
Өлш.
..Өлш.
..Өлш.
..Өлш.
..
Бет
Беттер
ҚР Бжәне ҒМ ҚазККА
РТ кафедрасы
және ҒМ ҚазККА
РТ кафедрасы
Криптографиялық кілттердіңкөмегімен желілерді қорғауды қамтамасыз ету
Бекітемін
Н.бақылау
Н.бақылау
Н.бақылау
Н.бақылау
Қолы
КүніКүніКүніКүні
Бет
Бет
Бет
Бет
Құжат №
Мекебаева А.К.
Т.бақылау
Нурыллаев Н.Д.
Мекебаева А.К.
Кусамбаева Н.
Липская М.А.
5
5
54
54
Дж
Дж
Бет
Бет
Өлш
Өлш
Қүні
Қүні
Сонымен қатар Еуропа мемлекеттеріндегі осындай Қайта өрлеу дәуірлері кезіндегі пайда болған болатын, сондықтан ғылымдар мен сауданың дамуы ақпаратты қорғауларының әдістерімен қажет болған кезде пайда болып айқындалады. Осындай қадамдағы маңызды рөлдері Леон Батисте Альберти атқарылады, олар көп әліппелі орындар ауыстырудағылар алғаш ұсынған итальян архитекторы болып табылалған. Жалпы XVI ғасырда Блез Вижинер дипломатының атына ие болған бұл шифр берілген мәтінді кілтпен әріпті тізбекті қосу тәсілінен болып табылады. Осылардың шифр туралы трактат атты еңбегі криптологияларымен қатар олардың жөніндегі алғашқы еңбегі болып табылатындығында болып отыр. Ең алдымен бір рет баспа жұмыс болып Иоганн Трисемустың Полиграфиялары (1508 жыл) еңбегі болып айқындалады. Олар үлкен еместегі, алайда маңызды жаңалық ашқан болатын, полибиандік квадрататы қабылдауларындағы әдістері немесе әріп жұптарын шифрлеулері болып айқындалатын.
Көп әліппелі ауыстыруларының қарапайымдылығына әрі тұрақты әдісі болатындағына XIX ғасырларда Чарльз Уитстонмен ашылғандағы Плейфер шифры пайдаланылады. Уитстон маңыздылығы жаңалықтардағы екілік квадрат арқылы шифрлеу әдісін ашқан екен. Плейфер және Уитстон шифрлары бірінші дүниежүзілік соғысқа дейін пайдаланылады. Сонымен қатар XIX ғасырда голландықтар Керкхоффы сол уақыттарға дейінгілердегі өзекті болып табылатын криптографиялық жүйелерінің басты талаптарын ұсынылған болатын, дегенмен шифрлардың құпиялылығының алгоритм еместігімен қатар, кілттің құпиялылығына негізделуі қажет болып айқындалады. Ғылымға деігейіндегі оларға жоғары крипто тұрақтылықтармен қамтамасыз ететіндігі криптографияның соңғы сөзі болып шифрларды автоматтандыруға мүмкіндік берген роторлық крипто жүйе болып айқындалады.
Сондай жүйелердегі барлық болып 1790-жылы болашақ президент Томас Джефферсонмен пайдаланылған механикалық машиналары болып табылған болатындығында болып отыр. Сонымен жалпы әліппелі ауыстырулардағы роторлықтар машиналары көмегімен бір-біріне қарай айналымдағы жасайтындығы роторлардың вариациясы арқылы болып айқындалады.
Роторлық машиналардың практикалық жағынан сұранысқа XX ғасыр басында ие болып айқындалады. Сонымен қатар алғашқы қолданыстағы енген машиналары болып 1917-жылы Эдвард Хебернмен жасалынатындығы, Артур Кирхпен жаңартылған немістері Enigma машинасы болған болатын. Роторлық машиналар ІІ дүниежүзілік соғыс кезінде кең қолданылған болатын. Жалпы неміс Enigma машинасынан өзге Sigaba, Турех, Red, Orange, Purple2 пайдаланған болатын. Роторлық жүйелеріндегі-ресми криптографияның шырқау шегі болып табылады, өйткені олар салыстырмалы түрдегілердегі тұрақты шифрлар тарататын болған болатын. Роторлық жүйелердегілері байланысты сәтті криптошабуылдар 40-жылдары ЭЕМ-нің пайда болуымен мүмкін болып айқындалады.
Сонымен барлық ғылымилардағы криптографияның айрықша белгілерімен қатар (XX ғасырдың 30-60-жылдарымен қатар ) барлық жоғары математикалық негізделгендегі тұрақты криптожүйелерінің пайда болуымен қатар болып келеді. Сонымен қатар 30-жылдардың басына қарай ғылыми түрдегі криптографияның негізі болып айқындалатын математика бөлімдерімен қатар толық қалыптасқан болып отыр, жалпы ықтималдықтар теориясымен қатар немесе математикалық статистикаларымен, жалпы алгебралар арқылыда, сандар теориясымен, алгоритм теориялары арқылы ақпарат теорияларымен қатар, кибернетикалары болып табылады. Ерекше бөлімі болып Клод Шеннонның Құпия жүйелердегі байланыс теорияларымен қатар (1949) атты түрегі еңбегі болып келеді, мұнда ақпаратты криптографиялық қорғаудың теориялық принциптерімен қатар айқындалған болатын. Жалпы шеннон араласулары және сонымен бөліну атты ұғымдарды енгізілген болатын.
Сонымен жалпы 60-жылдардағы көшбасшылардағылары мен қатар криптографиялықтардағылары мектептермен блоктық сандардың жасалуына көшті, олар роторлықтарымен криптожүйелермен салыстырғандағы аса тұрақты, алайда олардағы тек сандық электронды құрылымдарды жүзеге асырудағылары ғана қамтамасыз етілетін болды.
Сонымен қатар компьютерлік криптографиялардың (XX ғасырдың 70-жылдары) өнімділігі криптожүйелерінің таратуға жеткіліктілігі, шифрлеудің жоғары жылдамдығын қамтамасыз ететіндігі және олармен қатар қолдық және механикалық шифрлардің есептеулердің машиналарының шығуына байланысты пайда болып табылады.
Криптожүйелеріні алғашқы кластарымен қатар болып қолданулары кезіндегілерінің қуатты әрі жинақты есептеулерімен құралдарының пайда болуына байланыстылығы шыққан блоктық шифрлармен болып айқындалады. 70-жылдардағы шифрлеулерінің DES американдық стандарты жасалынған болатын Солардың авторларының бірі болғандығы Хорст мен Фейстел, олар блоктық шифрларымен қатар моделін айқындап, соның негізіндегі жасалынған аса тұрақты симметриялық криптожүйелерді пайдаланылатын.
Сондықтан DES-тердің жалпы пайда болуларымен қатар криптоанализ байланысты, американдық алгоритмдерге шабуылдары үшін бұлар криптоанализдердің жалпы түрдегі бірнеше тәсілдері жасалынады (сызықтық, дифференциалды және тағыда басқа), практикалық қолданылулары жағынан тек есептеулерінің машиналардың пайда болуымен мүмкін болып табылады.
Жалпы 70-жылдың ортасындағы қазіргі кездегі криптографияда төңкеріс болып айқындалады - асимметриялық криптожүйелердегі жалпы пайда болғандағы, ол жақтардағыларының арасындағылары бір-біріне құпия кілттің таратылуындағы қамтамасыз етілетін қолданылады. Осындай негізгі еңбек тердегі Уитфилд Диффимен және Мартин Хеллманмен 1976-жылы жарияланған Қазіргі кездегі криптографиялары бағыттары болып айқындалады. Бұл жердегі ең басындағы болып шифрліктері ақпараттардың кілтсіз таратылуларындағы принциптерімен қатар негізделген болып айқындалады. Асимметриялық криптожүйелердің жалпы идеяларына тәуелсіз қатысты болып айқындалады. Жалпы айтқанда Ральф Меркли болып қолданылды. Бірнеше жылдардан кейінгі Рон Ривест, Ади Шамир немесе Леонард Адлеман RSA жүйесін ашқан болатын, олар дегеніміз алғашқы уақыттардағы практикалық түрдегі асимметриялық криптожүйелерімен қатар болып қолданылды, олардың тұрақтылығымен үлкен сандарының факторизациясымен байланысты мәселесіне негізделген болып қолданылады. Асимметриялықтар криптографиялар бірден бірнеше қолданбалы болып бағыттар арқылы ашқан болатын, сонымен электронды сандық қолтаңба және электронды ақша болып айқындалды.
Жалпы айқтанда 80-90-жылдардағы фейстелдік еместігі шифрлар жасалды (SAFER, RC6), ал 2000-жылы ашық халықаралық сайыстан соң шифрлеудің АҚШ-тың жаңа ұлттық стандарттарының AES шықты болған болатын. Соғыстан кейінгілерінің кезеңнен бастап осы күндегі дейін есептеулері машиналардың пайда болуы болып криптографиялық әдістерінің жаңартылуларымен қатар өңделуін қамтамыз еткен болатын. Неліктен криптографиялық әдістерінің қолданулары ақпараттықтардың жүйелердің ең маңыздысы мәселесі болып айқындалды. Бір жағынанда, компьютерліктер торлардалары қолданулары арқылы кеңейді, негізіндегі, мемлекеттіктегі, әскери, коммерциялық және жеке түрдегілері ақпараттың өте үлкен мөлшеріндегі таратылатын ғаламдықтары торап интернет жүйесіндегілерінің қолданулары кеңейген болатын. Басқа жағындағылары, жаңа қуаттағылармен компьютерлердің пайда болуы болып табылған болатын, жүйелік немесе нейрондық есептеулердің технологиясымен қатар жақында ғана анықтаулары мүмкіндігі емес деп саналған криптографиялық жүйелердің дискредитациясына қол жеткізуге мүмкіндік берілген болатын. Ақпаратты түрлендірулері арқылы қорғаулар мәселесімен криптологиялары (kryptos - құпия, logos - ғылым) пайдаланатын болып табылады. Криптологиялары екі бағытқа бөлінетін болады - криптографиялары және криптоанализ болып табылады. Бұлардағы бағыттардың мақсаттары қарама-қарсы болып табылады.
Криптография ақпаратты түрлендіруде математикалық әдістерді іздеу және зерттеумен айналысады. Криптоанализдің айналысатын сфералар жүйесі - ақпараттың кілтін білмей шифрын анықтау.
Қазіргі криптография өзіне 4 үлкен бөлімді қосады:
- симметриялық криптожүйелер;
- ашық кілтті криптожүйелер;
- электрондық қолтаңба жүйелері;
- кілттерді басқарулары.
Криптографиялық әдістерінің қолданудың негізгі мақсаты - байланыс каналдары арқылы жасырын ақпаратты таратулары (мысалы, электрондық пошталар), жіберілгендігі хабарламалардың ақиқаттығы, шифрлі түрде ақпаратты сақтаулар болып табылады.
Криптографиялық жүйелерінің қаншалықты қиындары және сенімді болғанымен олардың практикалық қолданылуының әлсіз жағы-кілттерді үлестіру мәселесі болып табылады. Ол үшін ақпараттық жүйелерінің екі субьектісімен олардың арасындағы жасырын ақпараттарын алмасулары мүмкін және кілт солардың біреуімен генерацияланулары қажжет болып табылалады, жасырын түрдегі әрі қарай басқасына жіберілуі қажет болып табылады. Дегенмен барлық кілтті таратулар үшін криптожүйелерді қолдану қажет болып табылады. Бұл мәселені классикалық және қазіргідегі алгебрадан алынған нәтижелері негізінде шешулер үшін ашық кілтті жүйелер ұсынылатын болып табылады. Бұлардың барлық мәні ақпараттық жүйелерінің әрбірдегі хабар алушысымен екі кілт генерацияланады, олар бір-бірімен белгілі ережелерге сәйкес байланысты болады. Бір кілт ашық, екіншісі жабық болып жарияланатын болады. Ашық кілт жарияланады және кез-келген хабарлама жібергісісінің келетін адам үшін белгілі болып айқындалады. Құпия кілт жарияланбайтын болады.
Сонымен қатар бастапқы мәтіндегі хабар алушының барлық ашық кілтімен шифрленіп, оларға жіберілетін болады. Шифрленген мәтіндердің негізінен ашық кілтпен байланысты шифры анықталулары мүмкін емес болып табылады. Хабарламаны дешифрлеулер тек хабар алушыға ғана белгілі болатын жабық кілтті қолданулар арқылы ғана мүмкіндік болып саналады. Ашық кілтті криптографиялықтар жүйелер қайта оралмайтын немесе біржақты функциялар деп аталатындықтан ортақ қасиеті бар жұмыс істейтін болады. Берілген х үшін f(x) мәнін есептеу оңай болып табылады, алайда тек y=f(x) болса, х есептеудің оңай тәсілі жоқ дегенді білдіреді.
Жалпы біржақты функциялардың көптеген кластары ашық кілтті жүйенің көптүрлілігін тудындайтын болады. Алайда біржақтылары функциялардың барлығымен қатар ақпараттық жүйесінде қолдануға жарай берілмейтін болады. Қайта оралмайтындар деген түсініктемелерде теориялық қайта ораламсыздығы еместігі, белгіленген уақыттары интервалында қазіргі уақыттағы есептеу құралдарын пайдалану арқылы кері мәнін практикалық тұрғыдан есептей алмау болып айқындалады. Сонымен қатар,ақпаратты тиімді сақтаулары үшін ашық кілтті жүйелерге екі айқын әрі маңызды талап қойылатын болады:
- бастапқы мәтіндерінің түрленуі қайтымсыз болу қажет болады және ашық кілт негізінде қайта қалпына келмеу қажет болып табылады.
- ашық кілт негізінде жабық кілтті анықтаулары жаңа технологиялық тұрғыдан мүмкін емес болу қажеттігін білдіреді. Мұндай шифрды анықтауда күрделіліктерін төменгі бағасы көрсетілуі қажеттігін білдіреді.
Ашық кілтті шифрлеулер алгоритмдері кең қолданысқа ие болып табылады. RSA алгоритмдерінің ашық жүйелері үшін әлемдік дефакто стандарттары болып табылады. Қазіргі уақытта ұсынылатын ашық кілтті криптожүйелерінің қайтымсыз түрленудің төмендегідей топтарына жіктеліп қарастырылады, оларға жататындары мыналар:
- үлкен сандарды көбейткіштерге жіктеулер;
- соңғы өрісте логарифмді есептеулер;
- алгебралық теңдеулердің түбірлерін анықтаулар болып.
Ашық кілтті криптожүйелерді үш түрлі мақсатта қолдануға болады, оларға жататындар:
- жіберілген және сақтаудағы мәліметтердің өзіндік қорғаулары құралы ретінде болып саналады;
- кілттерді үлестіру құралы ретіндегеліре және ашық кілтті жүйелердег алгоритмдері дәстүрлі криптожүйелермен салыстырғанда аса көп еңбекті қажетті болып табылады;
- тұтынушыларды аутентификациялаулары құралы ретінде болып табылады.
1.2 Күрделілік теориясы
Күрделілік теориясында криптографиялық әдістерімен алгоритмдердің әр түрлі есептеулерінің күрделіліктеріне қарай әдістемелік талдаулар жасауға мүмкіндік бере алады. Олар дегеніміз криптографиялық әдістермен қатар алгоритмдерін салыстырулары арқылы, оның қаншалықты қауіпсіздігіне екендігін анықтайтын болады.
Алгоритмнің күрделілігіне жататындар: Алгоритмнің күрделілігі оның орындалуға байланысты керекті есептеуліктері қуаттарымен бірге есептеледі. Есептемелік алгоритмнің жалпы күрделілігімен қатар мынадай екі параметрмен өлшенетін болады, олар: T(уақытқа байланыстағылары туындайтын күрделілік) және S (кеңістікке байланыстылары туындайтын күрделілік және жадыға қойылатын талаптары) болып табылады. Дегенмен жалпы T және S, n айнымалысына тәуелділігі функция ретінде қарастырылатын болады. Мұндағы, n-бұл қабылданғандағы ақпараттардың шамасы болып табылады. Жалпы айтқанда есептемелік алгоритмнің күрделілігін жалпы функциясы арқылы жазылады. Олар күрделілік функциясының жай бөлшектерге жіктеулерінің түрлері болып табылады. Мысалыға айтар болсақ, егер 4n2+7n+12 алгоритмінің уақытқа байланыстылығы туындайтын күрделілігі болғандықтан, есептеулік күрделілігі n2 болып келеді, оны О(n2) деп белгілейтін боламыз.
Алгоритмдерді жалпы олардың уақыттық және де кеңістіктік күрделілігіне қатар олармен байланысты жіктейтін болады. Егерде алгоритм n-ға тәуелді болмаса, онда ондай алгоритмдерді тұрақты деп атап атады, О(1) деп белгілейді. Егер уақыттық күрделілігі О(n) болып табылса, онда алгоритмді сызықтық деп атайтын боламыз. Сонымен қатар жалпы алгоритмдердің квадраттықтылығы, кубтық немесе тағы да басқа түрлері болып табылады. Бұлар дегеніміз алгоритмдердің барлығы-полиноминалды болып айқындалады, ал олардың күрделілігімен қатар О(nm), мұндағы m - тұрақты шама болып табылады.Уақыттық күрделілігімен қатар барлық жалпы қарастырылған полиноминалды алгоритмдерді полиноминалды уақыттық алгоритмдер деп санайтын боламыз.
Жалпы күрделілігі О(tf(n)) есептелетін алгоритмдерді экспоненциалдық алгоритмдер деп атаймыз, мұндағы t - бірден үлкен тұрақты шама, ал f(n) - белгілі бір полиноминалды функциясы болып саналады. Күрделілігіне О(сf(n)) есептелетін экспоненциалдықтарға алгоритмдердің жалпы түрдегі жиынын суперполиноминалды деп анықтайды, мұндағы с-тұрақты шамалар, ал f(n) тұрақтыдан қарағанда тездетіп өсетіндер делінген, бірақ сызықтыдан баяуларымен қатар болатын функциясының бірі болып саналады.
1.1-кесте. n=106 шамасындағы әр түрлі алгоритмдердің жалпы уақыт күрделілігіне тәуелділігі
Түрлері
Күрделілігі
n=106 үшін операциялар саны
Қажет болатын уақыт
Тұрақтылығы
О(1)
1
1 мкс
Сызықтықтары
О(n)
106
1 с
Квадраттықтар
О(n2)
1012
11.6 күн
Кубтықтар
О(n3)
1018
32000 жыл
Экспоненциалдық
О(2n)
10301030
Біздің ғаламымыздың өмір сүру уақытынан 10301006 есе үлкен
Сонымен қатар жалпы компьютерлер үшін уақыттың өлшемділігінің бірлігі микросекундтарымен болғандықтан, компьютерлердегі тұрақты алгоритмдерді-1 микросекундтасы арқылы, сызықты алгоритмдерді-1 секундта, ал квадратты алгоритмдері-11.6 күнде есептей алатын болған. Кубтық алгоритмдердің жалпы 32000 жылдарындағы есептейтін болғандықтандағы, экспоненциалдық алгоритмдер туралы айтудың қажеті жоқтығын білеміз.
Шифрленген алгоритмдерді күшпен ашулары арқылы проблемасын қарастыратып көретін боламыз. Мұндай ашулардың уақыттылықтарымен қатар күрделілігі мүмкіндігі болатындары кілттердің санына тура пропорционал болып келеді. Сонымен кілттің ұзындығынан тәуелді деген сөзді білдіреді. Егер n - кілттің ұзындығы болатын болса, ал онда күшпен салып ашудың күрделілігі О(2n)-ге тең болып табылады.
Проблеманың күрделілігіне жататындар:
Күрделілік теориясымен қатар белгілі бір алгоритмдердің шешудің проблемасына ғана қарастырмайтын болады, дегенменде жалпы проблеманың қаншалықты күрделілігі екенін де анықтайтын боламыз. Атап айтқанда олар сол проблеманы шешуге керекті минималдылары уақытты және жадының көлемін қарастыратын болады. Оларды Тьюринг машинасы деп атайтын болады. Тьюринг машинасымен қатар шекзіз жадымен жабдықталғандығына қарай, алгоритмді оқу және жазу үшін арналған есептеудің наңыз моделі болып айқындалатын болған.
Полиноминалды уақыттық жалпы алгоритмдер арқылыда шешілетіндігі проблемаларды шешілетін проблемалар деп атайтын болады. Яғни, оларда белгілі ақпараттары үшін белгілі уақыттары бөлініп, сол уақыттағылармен қатар шешілетін болады. Полиноминалдылардағы уақыттары ішінде шешілмейтін проблемаларды шешілмейтін деп атайтын боламыз. Кейбір жағдайлардағы, шешілмейтін проблемаларды қиын (ауыр) проблемалар деп те атайтын боламыз. Алан Тьюринг кейбіреулері проблемаларды шешудің алгоритмін табу мүмкін еместігін дәлелдейтін болады.
Барлық проблемалардың және олардың шешілуіне байланысты барлық сәйкесінше кластарға бөлуге болатындығын айтамыз. Ең маңыздысы кластар төменде көрсетілген болып табылады.
1.1-сурет. Шешілетін проблемалар класы
Сонымен қатар ең төменгі жағында орналасқан Р класы полиномиальды уақыттардағы жалпы шешуге болатындығы барлық мәселелерден тұратын болады. NP-класы-полиномиальды уақыттағыларын тек барлық Тьюрингтің детерминацияланбаған машинасында шешуге болатындығын барлық түрдегілер мәселелер болып саналады және оларға жататынжар мыналар: жорамал жасай алатын Тьюрингтің қарапайым машинасының нұсқасы дегенді айтамыз. Машина мәселенің шешуіндегілері жорамалдай алады- не сәтті табу арқылы, не болмаса барлық жорамалдарды параллельды таңдап, барлық жорамалдарды полиномиальды уақытта тексеретін болады.
NP-ның криптографиядағы маңызы және оларға енгізілетіндер: көптеген симметриялықтардағы алгоритмдер және ашық кілттілердегі бар алгоритмдер детерминацияланбаған полиномиальды уақытта бұзылуы мүмкіндігін айтамыз. Берілген С шифрлік мәтіндері үшін криптоаналитик Х ашық мәтінді және к кілтін талғайды және полиномиальды уақытта Х және к арқылы шифрлеу алгоритмін тексере отырып, оның нәтижесіндегі С-ға тең болу мәселесін тексеретін болады. Бұлардың теориялық маңыздылығы зор, себебі осы алгоритмдердің барлық криптоанализінің күрделілігінің жоғарғы шегін анықтайтын боламыз. Тәжірибеде бұл әрине барлық полиномиальдылары уақыттарымен орындалатын детерминацияланған алгоритмдері, дәл осыны криптоаналитик іздеу тиіс деп айтамыз. Осындай алгоритмдері шифрлердің барлық класстарына байланысты бірдей қолданыла алмайтындығы, ол бір қолдануларға жарайтын блокноттар үшін жарамайды кез-келген С үшін Х, к көптеген жұптары шифрлеу алгоритмін орындау кезіндегі С-ны береді, бірақ Х-тің көбісі мәнсіз, мүмкін бола алмайтын ашық мәтіндер болып табылады.
NP-класына Р класы кіреді, себебі полиномиальды уақытта орындалатындығы Тьюрингтің детерминацияланған байланыс машинасында орындалатын кез-келген мәселелер полиномиальды уақытта Тьюрингтің детерминацияланбаған машинасында орындала алады, тек жорамалдау сатысы болмайды.
Дегенмен барлық NP мәселелердің Тьюрингтің детерминацияланғандығы машинасында полиномиальды уақытта орындалатын болса, онда Р = NP болып табылады. Сонымен кейбір NP мәселелер басқаларымен салыстырғанда аса күрделілігі және ешқашанда Р-ның NP-ға тең еместігі дәлелденбеген болып табылады. Сонымен қатар күрделілік теориясы саласында жұмыс жасайтын адамдардың барлығы бұл класстар тең бола алмайды деген пікірді ұстанатын болған.
Барлыңы ең маңыздысы нақты NP-мәселелер осы класстың басқа мәселелері секілді өте қиын екендігін дәлелдеуге болатындығында болып отыр. Стивен Кук орындалушылық мәселесінің NP-толық болатынын дәлелдеген болатын. Бұлар дегеніміз-егер орындалушылық мәселесі полиномиальды уақытта шешілсе, онда олардағы Р = NP болып көрсетіледі, керісінше егер NP класының кез-келген мәселесі үшін шешімнің полиномиальды уақыты бар детерминацияланған алгоритмі болмайтындығы дәлелденсе, орындалушылық мәселесі үшін де полиномиальды уақыты бар детерминацияланған алгоритмі болмайтындығын дәлелдеу көрсететін болған. NP-да орындалушылық мәселесінен ауыр мәселе жоқ болып табылады.
Сонымен қатар куктың негізқалаушылық жұмысы басылғаннан соң, орындалушылық мәселелеріне байланысты эквивалентті мәселелер бар екендігі анықталатын болады. Эквиваленттілікке байланыстардағы жалпы бұл мәселелерде NP-толық болып, NP класына кіретін барлық мәселелер тәрізді қиын мәселе болып табылады деп білеміз. Егер олардың барлық детерминацияланған полиномиальды уақытта шешілетіндігі дәлелденсе, онда Р сұрағының NP-ға қарсы сұрағы шешімін табатын болады. Р = NP сұрағы рас па екендігі күрделі есептеулері арқылы теориясының негізгі шешілмеген сұрағы болып саналатын болған және жақын арада өз шешімін табады деп күтіледі. Егер Р = NP болатындығын біреу көрсете алса, онда осы кітаптың біраз бөлігі қажетсіз болып табылады және оларға жататындар: шифрлардың көптеген класстары детерминацияланбаған полиномиальды уақытта бұзылады дегенді білдіреді. Сондықтан Р = NP болса, онда олар әлсіз детерминацияланған әлсіз алгоритмдермен бұзылады деп білеміз.
Сонымен қатар жалпы кейінгі болып күрделілік иерархиясында PSPACE класы жүргізілетін болады. Сонымен PSPACE класының мәселелері болып полиномиальды кеңістікте шешілуі мүмкін немесе полиномиальды уақыттары ішіндегі шешілуілері міндетті емес болып келетін болады. PSPACE өзіне NP -ны қосады, бірақ PSPACE мәселелері NP-ға қарағанда аса күрделі болып табылады. Әрине, бұлар әлі дәлелденбеген болатын. Сонымен қатар, PSPACE-толық деп аталатын келесі қасиетке ие мәселелер класы бар және егер олардың кез-келгені NP-мәселе болса, онда PSPACE = NP, және егер олардың кез-келгені Р-мәселе болса, онда PSPACE = P болып табылады. .
Жалпы EXPTIME мәселелер қатарлары болып саналады. Бұлардың мәселелер экспоненциалды уақытта шешіледі деп білеміз. EXPTIME-толық мәселелер расында да детерминацияланған полиномиальды уақыт аралығында шешіле алмайтындығы дәлелденуі мүмкін болып табылады. Сонымен қатар, Р EXPTIME-ге тең болмайтындығы дәлелденген болатын.
1.3 Сандар теориясы
Айыру арифметикасын барлығымызға мектеп кезінен мәлім. Оны кейде арифметикалық сағат деп те атайтын болған. Егер Милдред әкесіне үйде 10:00 болам деп айтып, 13 сағатқа кешігіп қалса, онда үйіне ол қашан келеді және неше жылға әкесі оны жүргізуші құқығынан айырады? Бұл арифметика 12 модуль бойынша. Жиырма үш 12 модулі бойынша 11 болып табылады.
(10+13) mod 12 = 23 mod 12 = 11 mod 12
Бұларды басқаша 23 пен 11 эквиваленттігі бойынша 12 модулімен жазуға болатынын білеміз:
10+13 =11(mod 12)
Көбінесе, егерде а = b+кn кейбіреулері бүтін к үшін болса, а = b (с) болып табылады. Дегенмен а кері емес болса және b 0 мен n аралығында орналасса, онда b-ны а-ның n-ға қатынасы кезіндегі қалдығы деп қарастыруға болып табылады. Әр кездері b а n модулі бойынша есептен алу деп айтылатын болған. Кейде олардағы а n модулі бойынша конгруэнтты b деп те аталады. Екеуі де бір мағынаны білдіретін.
0-ден n-1-ге дейінгі сандар жиыны n модулі бойыншада есептен алудың толық жиынын құрайтын болған. Бұлар дегеніміз кез-келген бүтін а үшін оның қалдығы n модулі бойынша 0 мен n-1 аралығында орналасқан кез-келген сандары болып айқындалады.
а mod n операциясы 0 мен n-1 аралығында орналасқан кез-келген бүтін а-ның қалдығын білдіреін білеміз. Бұл операциялардағы модульге келтіру деп аталатын айтамыз. Мысалыға айтар болсам, 5 mod 3= 2 деп білеміз.
Бұлар дегеніміз mod анықтамасы бағдарламалауларына олардың тілінде көрсетілген анықтамалардан ерекшеленуі мүмкіндігін білдіреді Мысалыға айтар болсақ, PASСAL тілінде қалдықты алуларымен қатар операторы кейде кері сан шығарылатын болған. Олар -(n-1) және n-1 аралығындағы санды қайтарылып беріледі. С тілінде % операторы бірінші өрнекті екіншісіне бөлуден алынған қалдықты қайтарылады, олар егерде операндалардың кез-келгені кері сан болса кері мән берілетін болады. Мұндай кітаптағы барлық алгоритмдер үшін егер ол кері санды шығарып тұрса, қалдықты алу операциясының нәтижесін алулары үшін не қосатындығын тексерілетін болған.
Сонымен қатар қалдықтар арифметикасы жай арифметикаға өте ұқсас:ол коммутативті және дистрибутивті болып саналады. Сонымен қатар, жалопы әрбір аралық нәтижені n модулі бойынша келтірулері жалпы есептеудегі соңғы нәтижені n модулі бойынша келтіргендегі нәтижені беретін болады.
(а+b) mod n=((а mod n)+(b mod n)) ) mod n (1.1)
(а-b) mod n=((а mod n)-(b mod n)) ) mod n (1.2)
(а.b) mod n=(( а mod n).(b mod n)) ) mod n (1.3)
(а.(b+с)) mod n=(((а.b) mod n)+((а.с) mod n)) mod n (1.4)
mod n есептеулері әдетінде криптографияда көп қолданылатын болады, өйткені дискретті логарифмдер және mod n квадраттық түбірін есептеулері оңай емес мәселе болуы қажет болып саналады. Есептен шығарулары арифметикасы компьютерлерде оңай жүзеге асады, өйткені ол аралық мәндер мен нәтижелер диапазонын шектейді. n-ның к-битті есептеулеріне кез-келген қосулары, алулары және көбейтудің аралық нәтижелері 2 к биттен артық болмайтыны болып табылады. Сонымен қатар барлық есептеулердегілердің арифметикасында дәрежеге келтіру үшін үлкен аралық нәтижелерді қолданбай орындауға болытынын білеміз. Кейбір әр санның дәрежесін басқа санның модулі бойынша есептеулері көбейтулері мен бөлудің тізбегі болып табылады, алайда оларды тездететін тәсілдер бар болып келеді:
ax mod n (1.5)
Сондай жалпы тәсілдердің бірі модуль бойынша көбейтулер санын азайтуға тырысатын болған, екіншісі бойынша -модуль бойынша жеке есептеулерді қолданулары болып табылады. Операциялар дистрибутивті болғандықтан, дәрежеге келтіруді тізбекті көбейтулер ағынын әр ретте олардың нәтижелерін ала отырып тез орындауға болады. Қазір сіздер айырмашылықты байқамайсыңдар, бірақ ол тек 200-биттік сандарды көбейткен кезде білінеді.
Мысалы, егер сіз а8 mod n есептегіңіз келсе, оны 7 рет көбейтіп, 1 рет модулі бойынша келтірудің қажеті жоқ:
(а.а.а.а.а.а.а) mod n
Оның орнына 3 кіші көбейтулер мен 3 кіші модульге келтіруді орындаңыз:
((а2 mod n)2 mod n2) mod n
Дәл осылай,
a16 mod n =(((а2 mod n)2 mod n)2 mod n)2 mod n
aх есептеу, мұнда х 2-нің дәрежесі болмайды, аса қиын емес. Екілік жазба х-ті 2:25 дәрежелер қосындысы түрінде береді- бұл бинарлық 11001, сондықтан 25=24+23+20. Сондықтан
a25 mod n=(а.а24) mod n=(а.а8.а16) ) mod n=(а.((а2)2)2)(((а2)2)2)2) mod n=(а.а(((а.а2)2)2)2) ) mod n
Аралық нәтижелерді ойластырылған сақтаумен енді тек 6 есептеу қажет:
(((((((а2mod n).а) 2mod n) 2 mod n) 2 mod n) 2 mod n) 2.а) mod n
Мұндай әдіс қосу тізбегі немесе екілік квадрат пен көбейту әдісі деп аталады. Ол негізінде санның екілік көрінісі жататын қосудың жай және айқын тізбегін қолданады.
Модуль бойынша кері мәнде:
Кері мән дегеніміз не екендігі естеріңізде ме? 4-14 үшін кері мән, себебі 4.14=1. Есептеу әлемінде мәселе күрделенеді: 4.х=1(mod 7)
Бұл теңдеу х пен к анықталуына эквивалентті, 4х=7 к+1
Мұнда, х пен к -бүтін сандар. Жалпы есеп мақсаты х-ті табу, ол
1=a.xmod n (1.6)
Бұны былай да жазуға болады:
a-1=xmod n (1.7)
Модуль бойынша кері мәндерді есептеу оңай емес. Кейде оның шешімі болады, кейде болмайды. Мысалы, 5 санының модулі бойынша кері мәні 14 модулі бойынша 3-ке тең. Басқа жағынан 2 санында 14 модулі бойынша кері мәні болмайды.
Жалпы жағдайда, (7) теңдеуінде а мен n сыбайлас жай болса, тек қана 1 шешімі болады. Егер а мен n сыбайлас жай болмаса, онда (7) теңдеуінің шешімі болмайды. Егер n жай сан болса, онда 1-ден (n -1)-ге дейінгі кез-келген сан n-мен сыбайлас жай болады және n модулі бойынша дәл сондай кері мәнге ие болады.
Эйлер функциясы:
Кері мәнді есептеудің басқа да әдісі бар, алайда оны әр кезде қолдана беруге болмайды. mod n берілген қалдықтар жиынтығы деп қалдықтардың толық жиынын жиын бөлігі және оның мүшелері n-мен сыбайлас жай болады. Мысалы, mod 12-нің келтірілген қалдықтар жиыны -{1,5,7,11}. Егер n -жай сан болса, онда mod n-нің келтірілген қалдықтар жиыны бұл- 1-ден n-1-ге дейінгі сандардың жиыны. 1-ге тең емес кез-келген сан үшін 0 саны ешқашан берілген қалдықтар жиынының құрамына кірмейді.
Эйлер функциясын φ(n) түрінде жазады, - бұл n модулі бойынша берілген қалдықтар жиынындағы элементтер саны. Басқаша айтқанда, φ(n)- n-нен кіші және онымен сыбайлас жай сан болатын бүтін оң сандар саны.
Егер n-жай сан болса, онда
φn=n-1 (1.8)
Егер мынадай теңдеу белгілі болса,
n=pq (1.9)
мұндағы р мен q-жай сандар болса, онда
φn=p-1q-1 (1.10)
болады. Бұл сандар кейбір алгоритмдерде ашық кілтпен келеді. Бұның себебі мынада: Эйлер теоремасы мен Ферманың кіші теоремасын сәйкес жалпылағанда, егер ЕҮОБ(а, n )=1 болса, онда
aφnmod n=1 (1.11)
Енді а-1 mod n есептеу қиын емес:
x=aφn-1mod n (1.12)
Мысалы, қандай сан 7 модулі бойынша 5 санына кері мәнге ие болады? 7 жай сан болғандықтан, φ(7) =7-1=6.
Осылайша 5 санына 7 модулі бойынша кері мән мынаған тең болады:
56-1 mod 7=55 mod 7=3.
Бұл кері мәндерді есептеу тәсілін х мәнін табудың ортақ мәселесіне кеңейтуге болады:
a.xmod n=b (1.13)
Эйлер жалпыламасын қолдана отырып, мынаны шешеміз:
xb.aφn-1mod n (1.14)
Эвклид алгоритмін қолдана отырып, мынаны табамыз:
x=b.a-1mod nmod n (1.15)
Жалпы жағдайда кері мәндер алгоритмін есептегенде Эвклид алгоритмі Эйлердің жалпыламасына қарағанда тезірек, әсіресе 500 битті сандар үшін. Егер ЕҮОБ(а, n )!=1 болса да шешімін табуға болады. Бұл жағдайда (а*х) mod n= b, не бірнеше шешімі, не бірде-бір шешімі болмайды.
Лежандр символы:
Лежандр символы L(а,р) егер а - кез келген бүтін сан болса, ал р-2-ден үлкен жай сан болса анықталған болады. Ол 0,1 немесе -1-ге тең болады.
L (а, р) =0, егер а р-ға бөлінсе.
L (а, р) =1, егер а -р модулі бойынша квадраттық есептен алу болса.
L (а, р) =-1, егер а -р модулі бойынша квадраттық есептен алу болмаса.
La,p=ap-12mod p (1.16)
Немесе келесі алгоритмді қолдануға болады:
1) Егер а=1 болса, онда L(а,р) =1
2) Егер а жұп болса, онда L(а,р) = L(а2,р)*(-1)(у2-1)8
3) Егер а жұп болмаса, онда L(а,р) = L(р mod а,р)*(-1)(а-1)(р-1)4
Көбейтінділерге жіктеу
Көбейтінділерге жіктеу дегеніміз - оның жай көбейтінділерін табу деген сөз.
10=2.5
60=2.2.3.5
252601=41.61.101
2113-1=3391.23279.1868569.65993.106 6818132868207
Көбейтінділерге жіктеу сандар теориясының ең көне мәселесі болып табылады. Бұл процесс қиын емес, тек уақыт талап етеді. Қазіргі таңда ең күшті алгоритм болып мынау табылады:
Сандардың сандық өрісінің торы - бұл 110 және одан да көп бөлік үшін ең тез алгоритм болып табылады. Алғашқыда ол пайдалы болған жоқ, алайда соңғы жылдары ол жақсартылған. Ол көбейтінділерге жіктеуді өте тез орындау үшін әлі біршама жаңа, алайда жақын арада барлығы өзгереді.
Квадраттық тор - бұл 110 ондық бөліктен кіші сандарды көбейтінділерге жәіктеудегі ең тез әдіс. Бұл әдістің жаңартылған нұсқасы полиномиальды квадраттық тор болып табылады. Ең тез нұсқасы полиномиальды квадраттық тордың үлкен санды екілік вариациялау әдісі болып табылады.
Эллипстік қисық әдісттеріне жатқызатындарымыз-43 бөліктегілрдегі көбейтінділерді жіктеуде қолданылатындығын айтамыз.
Монте-Карло Поллард әдістеріне жатқызатынымыздар; Үзіліссіз бөлшектер алгоритмдерінің-бұл алгоритм орындалу уақытына сай келмейтіндігін айтады.
Екілік санау жүйелеріне жатқызатындарымыз:
Екілік санаулар жүйелерінің математиктері мен философтармен компьютерлерінің шықпас бұрынғы (XVII-XIX ғасырларда) пайда болған болатын. Белгілі математиктер Лейбниц: "Екілер арқылы санаулардағы ғылым үшін ең негізгі болып айқындалады-деп көрсеткен болатын. Сонымен қатар жалпы сандарды қарапайым түрлерге келтіру кезіндегілері 0 мен 1 болғанда , әр жерде тамаша тәртіп пайда болғандығы. Солардан кейін екілік санау жүйелері ұмытылатын болған, тек 1936-1938 жылдарындағы американдық инженер және математик Клод Шеннон екілік санаулар жүйелерінің конструирленген электрондық схемалары үшін қолданысын тапқан болатын.
Сонымен қатар екілік санау жүйелері-негізі 2 болатын санау жүйесі дегенді білдіреді. 0 мен 1 сандары қолданылатын болады. Екілік санаулардағы жүйесі сандық құрылғылармен қатар қолданылатын болады, себебі әлдеқайда ыңғайлы және барлық талаптарға сай келеді екен:
oo Жүйелердегі жалпы мәндеріне қаншалықты аз болатын болса, соншалықты жеке элементтер дайындау ыңғайлы болып саналады.
oo элементтің күй элементтері аз болған сайын да, оның кедергігелері шыдамдылығы жоғары болып саналады және ол соншалықты тез жұмыс атқаратын болады.
Қосулар мен көбейтулерді жасау кестесінің қарапайымдылығы-сандарға қолданылатын қарапайым амалдарына бірге болып табылады.
1.4 Жай сандар генерациясы
Жай сан деп-бірден үлкен және тек бірге дейінгі, өзіне ғана бөлінетін бүтін сандарды айтамыз: ол басқа ешқандай сандарға олармен бөліне алмайды. Екі - жай сандар болып қалады. Жай сан болып 73, 2521, 2365347734339 және 2756839-1 бола алатынын айтаыз. Жай сандардың шексіздігіне байланысты көп түрі бар. Ашық кілттегілері криптографиялары көбінесе үлкен жай сандарды пайдаланатын болған, олар (512 бит және одан да көп) болып қалыптасады.
Ашық кілттері бар алгоритмдердердің жалпы бірге үшін жай сандар қажет болып табылады. Олардың біршама үлкендігі желісі үшін көптеген жиыны қажет болып саналады. Генерация математикасына көшпес бұрын бірнеше айқын сұрақтарға жауап беретін болсақ.
Егерде барлық әрқайсысына өзінің жай сандары қажет болатын болса, қор таусылмайды ма? деген сұрақ, әрине жоқ таусылмайды. Шын мәнінде 1-ден 512 битке дейінгі 10151 сан бар. n-ге жақын сандар үшін кездейсоқ таңдалынған сан жай болу ықтималдығы 1ln n болып табылады. Сондықтан да олар жай сандардың n-нен кіші толық сандары n( ln n) болып қарастырылады екен. Әлемде барлығымен қатар 1077 атом түрлері бар болады. Егер ғаламшардағы барлық атомдардары үшін әр микросекунда сайындағы миллиард сандар керек болса, онда жай сандардың тек 10109 керек болатындығында болып отыр, сонда жай сандардың 10151 қала беретіндігін айтамыз.
Егер екі адамдардың бірдей жай санды кездейсоқ таңдаса? Ондай болмайтындығын білеміз және 10151 санддарды таңдағанда сәйкес келулерімен қатар ықтимаалдығы өте аз болып саналады. Егер біреулер барлық жай сандардың базасын құратын болса, онда олар оны ашық кілті бар алгоритмдерді ашуға қолдана ала ма дегенді айтады, әрине жоқ болып табылады. Егерде сіз 1 гигабайт ақпаратты 1 грамм салмағы бар құрылғыда сақтасаңыз да, ондағы ақпаратты одан шығара алмайтындығынызды білдіреді. Егерде барлық көбейтінділерге жіктеулері сонша қиын болатын болса, онда жай сандардағы генерациясы қалайша оңай болатыны білеміз? n саны жай ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Ұқсас жұмыстар
Пәндер
- Іс жүргізу
- Автоматтандыру, Техника
- Алғашқы әскери дайындық
- Астрономия
- Ауыл шаруашылығы
- Банк ісі
- Бизнесті бағалау
- Биология
- Бухгалтерлік іс
- Валеология
- Ветеринария
- География
- Геология, Геофизика, Геодезия
- Дін
- Ет, сүт, шарап өнімдері
- Жалпы тарих
- Жер кадастрі, Жылжымайтын мүлік
- Журналистика
- Информатика
- Кеден ісі
- Маркетинг
- Математика, Геометрия
- Медицина
- Мемлекеттік басқару
- Менеджмент
- Мұнай, Газ
- Мұрағат ісі
- Мәдениеттану
- ОБЖ (Основы безопасности жизнедеятельности)
- Педагогика
- Полиграфия
- Психология
- Салық
- Саясаттану
- Сақтандыру
- Сертификаттау, стандарттау
- Социология, Демография
- Спорт
- Статистика
- Тілтану, Филология
- Тарихи тұлғалар
- Тау-кен ісі
- Транспорт
- Туризм
- Физика
- Философия
- Халықаралық қатынастар
- Химия
- Экология, Қоршаған ортаны қорғау
- Экономика
- Экономикалық география
- Электротехника
- Қазақстан тарихы
- Қаржы
- Құрылыс
- Құқық, Криминалистика
- Әдебиет
- Өнер, музыка
- Өнеркәсіп, Өндіріс
Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.
Ақпарат
Қосымша
Email: info@stud.kz