Криптографиялық кілттермен басқару.RSA алгоритмі
Евклид пен Диофант, Ферма, Эйлер, Гаусс, Чебышев пен Эрмит еңбектерінде диофантты теңдеулерді шешу жөнінде маңызды ойлар жатыр, сол заман үшін үлкен болып саналатын сандардың ең жақын мәнін табу үшін амалдар бар. Соңғы екі он жылдықта криптография мен ЭЕМ.нің кең таралуына байланысты сұраныстың дамуына орай сандар теориясының алгоритмдік сұрақтары даму үстінде. Есептеу машиналары мен электрондық құралдар адамның барлық қызметі мен ой.өрісіне енді. Оларсыз қазіргі заманғы криптографияны елестету мүмкін емес. Мәтінді шифрлеу мен оны бұзуды ЭЕМ көмегімен бүтін сандарды өңдеу ретінде елестетуге болады, бұл амалдар орындалаиын тәсілдер кейбір функциялар секілді бүтін сандардың белгілі бір жиынында орындалады. Мұның бәрі қазіргі заманғы криптографияда сандар теориясының болуына жағдай жасайды. Сонымен қатар, кейбір криптожүйелердің тұрақтылығы тек кейбір сандық .теориялық есептер күрделілігімен негізделеді. Бірақ ЭЕМ мүмкіндігі шекті болып табылады. Ұзын сандық тізбекті белгілі бір өлшемді блоктарға бөлуге тура келеді және әр блокты бөлек шифрлеуге тура келеді. Одан әрі біз барлық шифрленетін сандарды теріс емес және берілген m санынан кіші емес деп санаймыз.Мұндай шектеулер одан әрі шифрлеуден алынатын сандарға да қатысты. Бұл осы сандарды бойынша есептеуге мүмкіндік береді. Шифрленетін функция есептеу сақинасының бір.біріне сыбайлас жүйе ретінде қарастырылынады:
Ал, саны шифрленген түрдегі хабарламасын көрсетеді. Мұндай түрдің қарапайым шифры . алмастыру шифры, k.бүтін сан үшін болатын көрініске тән. Мұндай шифрды Юлий Цезарь де қолданған. Әрине, .тің әрбір көрінісі ақпаратты сақтау үшін қолданылады.
1978.жылы американдық Р. Ривест, А. Шамир және Л. Адлеман (R.L.Rivest. A.Shamir. L.Adleman) функциясына мысал ұсынды, олар ерекше қасиеттерге ие. Соның негізінде нақты қолданылатын шифрлеу жүйесі алынды, авторлардың есімдерінің алғашқы аттарына сәйкес RSA деп аталды. Бұл функция мынадай:
1) функциясының мәндерін есептейтін әлдеқайда жылдам әдіс бар;
2) кері функциясының мәндерін есетейтін жылдам әдіс бар;
3) функциясының «құпиясы» бар, егер оны анықтасақ, мәндерін тез есептеуге болады; қарсы жағдайда есептеуге ауыр, көп уақытты кетіретін, шешуге мүмкін емес есепке айналады.
Ал, саны шифрленген түрдегі хабарламасын көрсетеді. Мұндай түрдің қарапайым шифры . алмастыру шифры, k.бүтін сан үшін болатын көрініске тән. Мұндай шифрды Юлий Цезарь де қолданған. Әрине, .тің әрбір көрінісі ақпаратты сақтау үшін қолданылады.
1978.жылы американдық Р. Ривест, А. Шамир және Л. Адлеман (R.L.Rivest. A.Shamir. L.Adleman) функциясына мысал ұсынды, олар ерекше қасиеттерге ие. Соның негізінде нақты қолданылатын шифрлеу жүйесі алынды, авторлардың есімдерінің алғашқы аттарына сәйкес RSA деп аталды. Бұл функция мынадай:
1) функциясының мәндерін есептейтін әлдеқайда жылдам әдіс бар;
2) кері функциясының мәндерін есетейтін жылдам әдіс бар;
3) функциясының «құпиясы» бар, егер оны анықтасақ, мәндерін тез есептеуге болады; қарсы жағдайда есептеуге ауыр, көп уақытты кетіретін, шешуге мүмкін емес есепке айналады.
Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Дипломдық жұмыс
Тегін: Антиплагиат
Көлемі: 46 бет
Таңдаулыға:
Жұмыс түрі: Дипломдық жұмыс
Тегін: Антиплагиат
Көлемі: 46 бет
Таңдаулыға:
КІРІСПЕ
Евклид пен Диофант, Ферма, Эйлер, Гаусс, Чебышев пен Эрмит еңбектерінде
диофантты теңдеулерді шешу жөнінде маңызды ойлар жатыр, сол заман үшін
үлкен болып саналатын сандардың ең жақын мәнін табу үшін амалдар бар. Соңғы
екі он жылдықта криптография мен ЭЕМ-нің кең таралуына байланысты
сұраныстың дамуына орай сандар теориясының алгоритмдік сұрақтары даму
үстінде. Есептеу машиналары мен электрондық құралдар адамның барлық қызметі
мен ой-өрісіне енді. Оларсыз қазіргі заманғы криптографияны елестету
мүмкін емес. Мәтінді шифрлеу мен оны бұзуды ЭЕМ көмегімен бүтін сандарды
өңдеу ретінде елестетуге болады, бұл амалдар орындалаиын тәсілдер кейбір
функциялар секілді бүтін сандардың белгілі бір жиынында орындалады. Мұның
бәрі қазіргі заманғы криптографияда сандар теориясының болуына жағдай
жасайды. Сонымен қатар, кейбір криптожүйелердің тұрақтылығы тек кейбір
сандық –теориялық есептер күрделілігімен негізделеді. Бірақ ЭЕМ мүмкіндігі
шекті болып табылады. Ұзын сандық тізбекті белгілі бір өлшемді блоктарға
бөлуге тура келеді және әр блокты бөлек шифрлеуге тура келеді. Одан әрі біз
барлық шифрленетін сандарды теріс емес және берілген m санынан кіші емес
деп санаймыз.Мұндай шектеулер одан әрі шифрлеуден алынатын сандарға да
қатысты. Бұл осы сандарды бойынша есептеуге мүмкіндік береді.
Шифрленетін функция есептеу сақинасының бір-біріне сыбайлас жүйе ретінде
қарастырылынады:
Ал, саны шифрленген түрдегі хабарламасын көрсетеді. Мұндай
түрдің қарапайым шифры – алмастыру шифры, k-бүтін сан үшін болатын
көрініске тән. Мұндай шифрды Юлий Цезарь де қолданған. Әрине, -тің
әрбір көрінісі ақпаратты сақтау үшін қолданылады.
1978-жылы американдық Р. Ривест, А. Шамир және Л. Адлеман (R.L.Rivest.
A.Shamir. L.Adleman) функциясына мысал ұсынды, олар ерекше
қасиеттерге ие. Соның негізінде нақты қолданылатын шифрлеу жүйесі алынды,
авторлардың есімдерінің алғашқы аттарына сәйкес RSA деп аталды. Бұл функция
мынадай:
1) функциясының мәндерін есептейтін әлдеқайда жылдам әдіс бар;
2) кері функциясының мәндерін есетейтін жылдам әдіс бар;
3) функциясының құпиясы бар, егер оны анықтасақ,
мәндерін тез есептеуге болады; қарсы жағдайда есептеуге ауыр,
көп уақытты кетіретін, шешуге мүмкін емес есепке айналады.
RSA осы жылдар ішінде ұсынылған ашық кілтті қолданатын алгоритмдер
ішінде ең оңай түсінуге және жүзеге асыруға болатын алгоритм.
Бұл дипломдық жұмыс криптографияның ашық кілтті қолданатын
алгоритмдердің бірі – RSA-ға арналған.
Осыған орай дипломдық жұмыстың мақсаты – RSA алгоритмін қазіргі
таңдағы технологияларды пайдалана отырып, ақпаратты қорғау саласында
кеңінен қолдана алатын автоматтандыру жүйесін құру.
Жұмыстың мақсаты дипломдық жұмыс барысында шешілген келесі міндеттерді
анықтады:
1. Сандар теориясын, оның бөлімдерінің бірі жан сандарды зерттеу. Өте
үлкен жай сандарды іздеу
2. Екілік жүйедегі сандармен жұмыс жасау
3. Ашық және жабық кілттердің құрылымын зерттеу
4. Бір компьютерден екінші бір компьютерге ақпаратты шифрлеп
жібергенде, барлық қауіпсіздік ережелерін сақтау және зерттеу
Дипломдық жұмыс кіріспеден, төрт бөлімнен, қорытындыдан, әдебиеттер
тізімінен және қосымшадан тұрады. Кіріспеде жұмыстың өзектілігі берілген,
мақсаты қойылған, сол мақсатқа қол жеткізу міндеттерінен тұрады. Зерттеу
объектісі және пәні, оның методологиялық негізі және жұмыстың практикалық
маңыздылығы анықталған. Бірінші бөлімде криптографияның негізгі түсініктері
мен тарихы, оның жұмыс істеу принциптері мен алгоритмдері, сонымен қатар,
RSA алгоритмінде қолданатын математикалық негіздемелер туралы теориялық
анықтамалар орын алған. Бірінші бөлімнің басты қорытындысы –
криптографияның бастамасын түсіндіру, оның әдістемелері мен алгоритмдерін
таныстыру болып табылады. Екінші бөлім ашық кілтті қолданатын
алгоритмдерге, соның ішінде, RSA алгоритміне арналған. Үшінші бөлім .NET
платформасына, оның құрылымы мен сипаттамасына арналған. Бұл бөлімде C#-тың
басқа объектілі-бағытталған программалардан айырмашылығын көрсетілген.
Төртінші бөлім жұмыстың қойылымына, яғни бағдарламалық бөлімге арналған.
Онда әрбір батырманың мақсатына дейін айтылып кеткен. Ал олардың
бағдарламалық кодтары қосымшаларда жазылып кеткен.
Қорытынды бөлімінде дипломдық жұмыс тақырыбы бойынша жалпылама
қорытындылар жасалған.
КРИПТОГРАФИЯ НЕГІЗДЕМЕСІ
1 Криптографияның негізгі түсініктемелері мен тарихы
Ақпаратты оны түрлендіру арқылы басқа адам оқи алмайтындай қорғау
мәселесі адамзат алдында бұрыннан тұрған мәселелердің бірі болып табылады.
Криптография тарихы – адамзат тілінің тарихының замандасы. Оған қоса, жазу
алғашқыда криптографиялық жүйе болы табылды, себебі, ежелге қоғамда онымен
тек ерекше таңдаулы адамдар ған иелік етті. Ежелгі Египет пен Үндістанның
киелі кітаптары соған мысал бола алады. Криптография жазудың кең таралуына
байланысты дербес ғылым ретінде қалыптаса бастады.
Криптография тарихын шартты түрде 4 қадамға бөлуге болады:
1) жай криптография
2) ресми криптография
3) ғылыми криптография
4) компьютерлік криптография
Жай криптография үшін (XVI ғасыр басына дейінгі кезең) қарсыласты кез
келген шифрлік мәтін мазмұнына қатысты шатыстыру тән. Бастапқы қадамда
ақпаратты сақтау үшін криптографиямен барабар кодтау және стеганография
әдістері қолданды.
Көптеген қолданылатын шифрлар орын ауыстырулар немесе моноалфавиттік
ауыстыру арқылы жүзеге асырылды. Жарияланған мысалдардың бірі болып Цезарь
шифры табылады, ол мәтіндегі алдыңғы әріпті алфавитте одан алыс тұратын
әріпке ауыстыру арқылы жүзеге асырылады. Басқа шифр, полибианды квадрат,
грек жазушысы Полибий шығарған, алфавитпен өлшемі 5х5 болатын квадратты
кестеге кездейсоқ толтырылатын грек алфавитінің көмегімен жүзеге асатын
жалпы моноалфавитті орын ауыстыру болып табылады. Әр әріп квадратта одан
төмен тұратын әріппен ауыстырылады.
Ресми криптография қадамы (XVғ.аяғы-XX ғ. басы) криптоанализдің ресми
және салыстырмалы түрде тұрақты шифрлерінің пайда болуымен байланысты.
Еуропа елдерінде бұл Қайта өрлеу дәуірі кезінде пайда болды, яғни ғылым мен
сауданың дамуы ақпаратты қорғаудың әдістері керек болған кезде пайда болды.
Бұл қадамдағы маңызды рөлді Леон Батисте Альберти атқарды, ол көп әліппелі
орын ауыстыруды алғаш ұсынған итальян архитекторы. 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) болса,
х есептеудің оңай тәсілі жоқ.
Біржақты функциялардың көптеген кластары ашық кілтті жүйенің
көптүрлілігін тудырады. Алайда біржақты функциялардың барлығы ақпараттық
жүйесінде қолдануға жарай бермейді. Қайта оралмайтын деген түсінікте
теориялық қайта ораламсыздығы емес, белгіленген уақыт интервалында қазіргі
заманғы есептеу құралдарын қолдану арқылы кері мәнін практикалық тұрғыдан
есептей алмау айтылады. Сондықтан, ақпаратты тиімді сақтау үшін ашық кілтті
жүйелерге екі айқын әрі маңызды талап қойылады:
1) Бастапқы мәтіннің түрленуі қайтымсыз болу керек және ашық кілт
негізінде қайта қалпына келмеу керек.
2) Ашық кілт негізінде жабық кілтті анықтау жаңа технологиялық
тұрғыдан мүмкін емес болу керек. Мұнда шифрды анықтауда
күрделіліктің төменгі бағасы көрсетілуі керек.
Ашық кілтті шифрлеу алгоритмдері кең қолданысқа ие болды. RSA алгоритмі
ашық жүйелер үшін әлемдік де-факто стандарты болды. Қазіргі таңда
ұсынылатын ашық кілтті криптожүйелер қайтымсыз түрленудің төмендегідей
топтарына жіктеледі:
1) Үлкен сандарды көбейткіштерге жіктеу;
2) Соңғы өрісте логарифмді есептеу;
3) Алгебралық теңдеулердің түбірлерін анықтау.
Ашық кілтті криптожүйелерді 3 түрлі мақсатта қолдануға болады:
1) Жіберілген және сақтаудағы мәліметтерді өзіндік қорғау құралы
ретінде.
2) Кілттерді үлестіру құралы ретінде. Ашық кілтті жүйелер алгоритмдері
дәстүрлі криптожүйелермен салыстырғанда аса көп еңбекті қажет
етеді.
3) Тұтынушыларды аутентификациялау құралы ретінде.
2 Математикалық негіздемелер
2.1 Күрделілік теориясы
Күрделілік теориясы криптографиялық әдістер мен алгоритмдердің әр түрлі
есептеу күрделіліктеріне қарай әдістемелік талдау жасауға мүмкіндік береді.
Ол криптографиялық әдістері мен алгоритмдерін салыстыра отырып, оның
қаншалықты қауіпсіз екендігін анықтайды.
Алгоритмнің күрделілігі
Алгоритмнің күрделілігі оның орындалуға керекті есептеулік қуаттарымен
есептеледі. Есептемелік алгоритмнің күрделілігі мынадай екі параметрмен
өлшенеді: 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) тұрақтыдан қарағанда тездетіп өсетін,
бірақ сызықтыдан баяу болатын функция.
3-кесте. 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)-
ге тең.
Проблеманың күрделілігі
Күрделілік теориясы белгілі бір алгоритмді шешудің проблемасын ғана
қарастырмайды, сонымен қатар, проблеманың қаншалықты күрделі екенін де
анықтайды. Атап айтқанда, сол проблеманы шешуге керекті минималды уақытты
және жадының көлемін қарастырады. Оны Тьюринг машинасы деп атайды. Тьюринг
машинасы шекзіз жадымен жабдықталған, алгоритмді оқу және жазу үшін
арналған есептеудің наңыз моделі болып табылады.
Полиноминалды уақыттық алгоритмдер арқылы шешілетін проблемаларды
шешілетін проблемалар деп атайды. Яғни, белгілі ақпарат үшін белгілі уақыт
бөлініп, сол уақытта шешіледі. Полиноминалды уақыт ішінде шешілмейтін
проблемаларды шешілмейтін деп атайды. Кей жағдайларда, шешілмейтін
проблемаларды қиын (ауыр) проблемалар деп те атайды. Алан Тьюринг кейбір
проблемаларды шешудің алгоритмін табу мүмкін еместігін дәлелдеді.
Барлық проблемаларды олардың шешілуіне байланысты сәйкесінше кластарға
бөлуге болады. Ең маңызды кластар төменде көрсетілген.
Шешілетін проблемалар класы
3-сурет
Ең төменде орналасқан Р класы полиномиальды уақытта шешуге болатын
барлық мәселелерден тұрады. 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-ге тең болмайтындығы дәлелденген.
2.2 Сандар теориясы
Айыру арифметикасы
Айыру арифметикасын барлығымызға мектеп кезінен мәлім. Оны кейде
арифметикалық сағат деп те атаған. Егер Милдред әкесіне үйде 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)
(а-b) mod n=((а mod n)-(b mod n)) ) mod n
(2)
(а*b) mod n=(( а mod n)*(b mod n)) ) mod n
(3)
(а*(b+с)) mod n=(((а*b) mod n)+((а*с) mod n)) mod n
(4)
mod n есептеу әдетте криптографияда көп қолданылады, себебі дискретті
логарифмдер мен mod n квадраттық түбірін есептеу оңай емес мәселе болуы
мүмкін. Есептен шығару арифметикасы компьютерлерде оңай жүзеге асады,
себебі ол аралық мәндер мен нәтижелер диапазонын шектейді. n –ның к-битті
есептеулеріне кез-келген қосу, алу, көбейтудің аралық нәтижелері 2 к биттен
артық болмайды. Сондықтан есептеу арифметикасында дәрежеге келтіру үшін
үлкен аралық нәтижелерді қолданбай орындауға болады. Кейбір санның
дәрежесін басқа санның модулі бойынша есептеу көбейту мен бөлудің тізбегі
болады, алайда оларды тездететін тәсілдер бар:
ах mod n.
(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=(а*х) mod n
(6)
Бұны былай да жазуға болады:
а-1=х(mod n)
(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
(8)
Егер мынадай теңдеу белгілі болса,
n =рq
(9)
мұндағы р мен q-жай сандар болса, онда
φ(n) =(р-1)(q-1)
(10)
болады. Бұл сандар кейбір алгоритмдерде ашық кілтпен келеді. Бұның
себебі мынада: Эйлер теоремасы мен Ферманың кіші теоремасын сәйкес
жалпылағанда, егер ЕҮОБ(а, n )=1 болса, онда
а φ(n) mod n=1
(11)
Енді а-1 mod n есептеу қиын емес:
х=а φ(n)-1 mod n
(12)
Мысалы, қандай сан 7 модулі бойынша 5 санына кері мәнге ие болады? 7
жай сан болғандықтан, φ(7) =7-1=6.
Осылайша 5 санына 7 модулі бойынша кері мән мынаған тең болады:
56-1 mod 7=55 mod 7=3.
Бұл кері мәндерді есептеу тәсілін х мәнін табудың ортақ мәселесіне
кеңейтуге болады:
(а*х) mod n= b
(13)
Эйлер жалпыламасын қолдана отырып, мынаны шешеміз:
х= (b* а φ(n)-1) mod n
(14)
Эвклид алгоритмін қолдана отырып, мынаны табамыз:
х= (b* (а-1 mod n)) mod n
(15)
Жалпы жағдайда кері мәндер алгоритмін есептегенде Эвклид алгоритмі
Эйлердің жалпыламасына қарағанда тезірек, әсіресе 500 битті сандар үшін.
Егер ЕҮОБ(а, n )≠1 болса да шешімін табуға болады. Бұл жағдайда (а*х) mod
n= b, не бірнеше шешімі, не бірде-бір шешімі болмайды.
Лежандр символы
Лежандр символы L(а,р) егер а – кез келген бүтін сан болса, ал р-2-ден
үлкен жай сан болса анықталған болады. Ол 0,1 немесе -1-ге тең болады.
L (а, р) =0, егер а р-ға бөлінсе.
L (а, р) =1, егер а –р модулі бойынша квадраттық есептен алу болса.
L (а, р) =-1, егер а –р модулі бойынша квадраттық есептен алу болмаса.
L (а, р) = а(р-1)2 mod р.
(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 сандары
қолданылады. Екілік санау жүйесі сандық құрылғыларда қолданылады, себебі
әлдеқайда ыңғайлы және барлық талаптарға сай:
- Жүйеде мәндер қаншалықты аз болса, соншалықты жеке элементтер
дайындау ыңғайлы.
- Элементтің күй элементі аз болған сайын, оның кедергіге шыдамдылығы
жоғары болады және ол соншалықты тез жұмыс істейді.
Қосу мен көбейтуді жасау кестесінің қарапайымдылығы-сандарға
қолданылатын қарапайым амал
2.3 Жай сандар генерациясы
Жай сан деп – бірден үлкен және тек бірге, өзіне ғана бөлінетін бүтін
сан: ол басқа ешқандай санға бөліне алмайды. Екі - жай сан. Жай сан болып
73, 2521, 2365347734339 және 2756839-1 бола алады. Жай сандардың шексіз көп
түрі бар. Ашық кілтті криптография көбінесе үлкен жай сандарды пайдаланады
(512 бит және одан да көп).
Ашық кілті бар алгоритмдер үшін жай сандар қажет. Олардың біршама үлкен
желісі үшін көптеген жиыны керек. Генерация математикасына көшпес бұрын
бірнеше айқын сұрақтарға жауап берейік.
Егер әрқайсысына өзінің жай саны керек болса, қор таусылмайды ма? Жоқ.
Шын мәнінде 1-ден 512 битке дейінгі 10151 сан бар. n-ге жақын сандар үшін
кездейсоқ таңдалынған сан жай болу ықтималдығы 1ln n болады. Сондықтан,
жай сандардың n –нен кіші толық саны n( ln n) болады. Әлемде барлығы 1077
атом бар. Егер ғаламшардағы барлық атомдар үшін әр микросекунда сайын
миллиард сан қажет болса, онда жай сандардың тек 10109 керек болар еді,
сонда жай сандардың 10151 қалар еді.
Егер екі адам бірдей жай санды кездейсоқ таңдаса? Ондай болмайды.10151
санды таңдағанда сәйкес келу ықтимаалдығы өте аз. Егер біреу барлық жай
сандар базасын құрса, онда ол оны ашық кілті бар алгоритмдерді ашуға
қолдана ала ма? Жоқ. Егер сіз 1 гигабайт ақпаратты 1 грамм салмағы бар
құрылғыда сақтасаңыз да, ондағы ақпаратты одан шығара алмайсыз. Егер
көбейтінділерге жіктеу сонша қиын болса, онда жай сандар генерациясы
қалайша оңай болады? n саны жай сан ба деген сұраққа жауап беру n-нің
бөлінділері қандай деген сұраққа жауап беруге қарағанда әлдеқайда оңай.
Бөліндімен тексеру
Бұл көбейтінділерге жіктеудің ең көне тәсілінің әдісі әр жай санды
тексеруден,жіктелініп жатқан санның кіші немесе тең квадраттық түбірін
анықтаудан тұрады. Егер де белгілі бір себеппен санның жайлығын тексеру
керек болса, қателік деңгейін төмендетуге болады.
Көбейтінділерге жіктеудің келесі әдісімен кездейсоқ сандар генерациясы-
бұл жай сандарды іздеудің қате әдісі.Жай сандарды тексеру әдісінің
тексерілген бірнеше тәсілі бар.Тек тексеру деңгейі жоғары болса, бұл
тексеру әдісі тиімді болып келеді.Бұл тәсілмен генерацияланған жай сандарды
өндірістік жай сандар деп атайды: бұл сандар бақыланатын қате мүмкіндігі
бар сандар болып табылады.
250 санынан 1 тексеру –қате деп жорамалдайық. Бұл дегеніміз, 11015
ықтималдығымен тексеріс құрама санды жай деп айтады.
Lehmann
Басқа, одан қарапайым тест Леманнмен тәуелсіз анықталды. Бұл р санының
тексеруіндегі амалдар тізбегі:
1) р –дан кіші кез-келген а санын таңдаңыз.
2) а(р-1)2 mod р есептеңіз.
3) Егер а(р-1)2≠1 немесе -1(mod р) болса, онда р жай сан болмайды.
4) Егер а(р-1)2≡1 немесе -1(mod р) болса, онда р санының жай сан
болу ықтималдығы 50 пайыздан көп болмайды.
Осы тексерісті t рет орындаңыз. Егер есептеу нәтижесінің ықтималдығы 1
немесе -1 болса, бірақ әр уақытта 1 болмаса, онда р қателігі 12 t болатын
жай сан болып табылады.
3 Криптожүйелердің жұмыс істеу принциптері
Оқиғаны сипаттаудың қалыпты мысалы, криптография есебі туындайтын 1-
суретте көрсетілген:
Негізгі принцип
1-сурет
А мен В 1-суретте – қорғалынған ақпараттың заңды тұтынушылары, олар
ақпаратпен жалпыға бірдей байланыс каналы арқылы алмасқысы келеді. П –
заңсыз тұтынушы (қарсылас, хакер), жіберілген ақпаратты қағып алып, одан
өзіне қажетті жаңа ақпарат немесе мәлімет алғысы келетін адам. Бұл
қарапайым схеманы ақпаратты қорғау немесе шифрлеудің криптографиялық
әдістері қолданылатын әдеттегі оқиғаның моделі ретінде қарастыруға болады.
Тарихи тұрғыдан қарастырғанда, криптографияда кейбір әскери сөздер
бекінді (қарсылас, шифрге шабуыл). Олар криптографиялық түсініктердің ойын
нақты анықтайды. Оған қоса кең қолданылатын әскери терминология, код
түсінігі бойынша (әскери-теңіздік кодтар, Генералдық штаб коды, кодтық
кітаптар, кодтық белгілеулер және т.б.) теориялық криптографияда
қолданылмайды. Соңғы жылдары кодтау теориясы қалыптасты. Байланыс каналында
кездейсоқ бұзылудан ақпаратты қорғау әдістерін зерттейтін және жасайтын
кодтау теориясы пайда болды.
Криптография қарсылас жіберіліп жатқан ақпаратты қарсылас қағып алмау
үшін ақпаратты түрлендірумен айналысады. Мұнда байланыс каналы арқылы
қорғалынатын ақпарат емес, ал оның шифр арқылы түрлену нәтижесі жіберіледі
және қарсылас үшін осы шифрды анықтау қиынға соғады. Шифрды бұзу – шифрды
қолдану білімінсіз шифрленген ақпаратты қорғалынатын ақпаратты алу процесі.
Қарсылас ақпаратты алу ғана емес, сонымен қатар оны өшіруге, жоюға
тырысады. Бұл – ақпарат үшін басқа кедергі, ол қағып алу немесе шифр
бұзудан ерекшеленеді. Мұндай қауіптен қорғану үшін спецификалық әдістер
қолданылады. Яғни, заңды тұтынушыдан басқасына ақпарат беру керек кезінде
әртүрлі әдістермен қорғалыну керек. Әртүрлі типтен тұратын бөліктер
тізбегінен тұратын ақпаратты қорғайтын жағдай туып отыр. Қарсылас ең әлсіз
бөлікті іздейді. Бұдан келесі ереже шығады: бір бөлігін өте мықты қылудың
маңызы жоқ, егер бір бөлігі кемінде әлсіз болса.
Жақсы шифр ойлап табу оңай шаруа емес. Сондықтан жақсы шифрдың
өміршеңдігін ұзартып, оны көп ақпаратты шифрлеу үшін қолдану керек. Алайда,
қарсылас шифрды анықтап қойды деген қауіп туады, бұл жағдайда ауыстырылатын
кілт болады, сондықтан қарсылас әрі қарай ақпаратты оқи алмайды және шифр
ашу үшін жасаған амалдары нәтижесіз болады.
3.1 Криптографиялық кілттерді басқару
Криптографияда кілт ұғымы астарында шифрдің ауыстырылатын элементі
жатыр, ол тек нақты бір хабарламаны шифрлеуде қолданылады. Соңғы уақытта
қорғалынатын ақпараттың қауіпсіздігі кілтпен анықталады. Шифрмашина немесе
шифрлеу принципі бойынша қарсыласқа шифр белгілі деп санай бастады және
алдын-ала зерттеуге болатын, алайда қарсыласқа белгісіз, тек ақпараттың
түрленуіне байланысты кілт пайда болды. Енді заңды тұтынушылар шифрлік
хабарламалармен алмаспас бұрын қарсыластан құпиялы түрде кілттерімен алмасу
керек немесе байланыстың екі жағында бірдей кілт орнату керек. Ал қарсылас
үшін жаңа қиындық туады – кілтті анықтау, тек содан кейін кілтте шифрленген
ақпаратты оңай ашуға болады.
Криптографияның негізгі обьектісінің сипаттамасына қайта оралайық. Енді
оған сәйкес өзгерістер енгізу керек – қарсылас үшін мүмкін емес болатын
кілт алмасу үшін құпия каналды қосу.
Кілттерді қолдану мысалы
2-сурет
Мұндай байланыс каналын жасау өте оңай және оның ақпарат жүктемесі
күрделі емес. Барлық жағдайлар үшін ажырайтын бірегей шифр болмайтындығын
атап өту керек. Шифрлеу әдісін таңдау ақпараттың ерекшелігіне, оның
құндылығы мен иелерінің ақпаратты қорғау үшін мүмкіндіктеріне тікелей
байланысты. Ең алдымен қорғалынатын ақпараттың көптүрлілігін атап өтейік:
құжаттық, телефондық, теледидарлық, компьютерлік. Ақпараттың әр түрінің
өзіндік ерекше қасиеттері бар және бұл ерекшеліктер ақпаратты шифрлеу
әдісіне зор әсерін тигізеді. Үлкен рөлді көлемі мен шифрленген ақпараттың
таралу жылдамдығы атқарады. Шифр түрін таңдау және оның параметрлерін
орнату қорғалынатын құпия мен сектор түріне байланысты. Кейбір құпиялар (
мысалы, әскери, мемлекеттік) он жылдап сақталыну керек, ал кейбіреулері
(мысалы, биржалық) бірнеше сағаттан соң жариялануы мүмкін. Сонымен қатар,
ақпарат қорғалынатын қарсыластың мүмкіндігіне де байланысты. Бір жағдай,
бір немесе бірнеше қылмыскерлер тобына қарсы тұру, ал екіншісі, қуатты
мемлекеттік құрылымға қарсы тұру.
Кез келген қазіргі заманғы криптографиялық жүйе криптографиялық
кілттерді пайдалануға негізделген. Ол белгіленген әдістеме бойынша жұмыс
жасайды: шифрлеудің бір немесе бірнеше алгоритмі; осы шифрлеудің
алгоритмдері пайдаланатын кілттер; кілттерді басқару жүйелері; шифрленбеген
мәтін; шифрлік мәтін.
3.2 Симметриялық (құпиялы) әдістемелер мен алгоритмдер
Бұл әдістемеде шифрлеу үшін де, оның шифрын бұзғанда да хабар жіберуші
мен алушы да бірдей кілт қолдану керек. Егер кілт компрометтенген болмаса,
онда шифр бұзуда автоматты түрде хабар жіберушінің аутентификациясы жүреді,
себебі, тек хабар жіберушінің өзі ғана кілтке ие, тек хабар алушы ғана
шифрды ашатын кілтті біледі. Хабар жіберуші мен алушы –симметриялық кілтті
білетін жалғыз адамдар. Мәселе, тек осы кілттерді қалайша қауіпсіз
тасымалдауға болатындығында.
Симметриялық шифрлеудің алгоритмдері ондай қатты ұзақ емес кілтті
қолданады және көп мөлшерде мәліметті тез шифрлей алады. Симметриялық
кілттерді пайдалану реті:
1) Симметриялық құпия кілт қауіпсіз жасалынады, шығарылады, таратылады
және сақталынады.
2) Хабар жіберуші мәтін үшін хэш-функциясын есептеу арқылы электрондық
қолтаңба жасайды және алынған қатарды мәтінге тіркейді.
3) Хабар жіберуші шифрлеудің жылдам симметриялық алгоритмдерін
қолданады- шифрленген мәтінді алу үшін алынған пакетке симметриялық
құпия кілтін тіркеу арқылы шифрды бұзу тәсілін анықтайды. Осы
тәсілмен аудентификация жүреді, себебі хабар жіберуші симметриялық
құпия кілтін біледі және бұл пакет шифрын бұза алады.
4) Хабар жіберуші ғана шифрленген мәтінді біледі. Симметриялық құпия
кілт ешқашан қорғалмаған байланыс каналдар арқылы таратылмайды.
5) Хабар алушы дәл сол симметриялық құпия кілт алгоритмін пайдаланады.
Оның сәтті қалпына келуі құпия кілтті білетін адамды
аутентификациялайды.
6) Хабар алушы электрондық қолтаңбаны мәтіннен бөледі.
7) Хабар алушы басқа электрондық қолтаңбаны ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Евклид пен Диофант, Ферма, Эйлер, Гаусс, Чебышев пен Эрмит еңбектерінде
диофантты теңдеулерді шешу жөнінде маңызды ойлар жатыр, сол заман үшін
үлкен болып саналатын сандардың ең жақын мәнін табу үшін амалдар бар. Соңғы
екі он жылдықта криптография мен ЭЕМ-нің кең таралуына байланысты
сұраныстың дамуына орай сандар теориясының алгоритмдік сұрақтары даму
үстінде. Есептеу машиналары мен электрондық құралдар адамның барлық қызметі
мен ой-өрісіне енді. Оларсыз қазіргі заманғы криптографияны елестету
мүмкін емес. Мәтінді шифрлеу мен оны бұзуды ЭЕМ көмегімен бүтін сандарды
өңдеу ретінде елестетуге болады, бұл амалдар орындалаиын тәсілдер кейбір
функциялар секілді бүтін сандардың белгілі бір жиынында орындалады. Мұның
бәрі қазіргі заманғы криптографияда сандар теориясының болуына жағдай
жасайды. Сонымен қатар, кейбір криптожүйелердің тұрақтылығы тек кейбір
сандық –теориялық есептер күрделілігімен негізделеді. Бірақ ЭЕМ мүмкіндігі
шекті болып табылады. Ұзын сандық тізбекті белгілі бір өлшемді блоктарға
бөлуге тура келеді және әр блокты бөлек шифрлеуге тура келеді. Одан әрі біз
барлық шифрленетін сандарды теріс емес және берілген m санынан кіші емес
деп санаймыз.Мұндай шектеулер одан әрі шифрлеуден алынатын сандарға да
қатысты. Бұл осы сандарды бойынша есептеуге мүмкіндік береді.
Шифрленетін функция есептеу сақинасының бір-біріне сыбайлас жүйе ретінде
қарастырылынады:
Ал, саны шифрленген түрдегі хабарламасын көрсетеді. Мұндай
түрдің қарапайым шифры – алмастыру шифры, k-бүтін сан үшін болатын
көрініске тән. Мұндай шифрды Юлий Цезарь де қолданған. Әрине, -тің
әрбір көрінісі ақпаратты сақтау үшін қолданылады.
1978-жылы американдық Р. Ривест, А. Шамир және Л. Адлеман (R.L.Rivest.
A.Shamir. L.Adleman) функциясына мысал ұсынды, олар ерекше
қасиеттерге ие. Соның негізінде нақты қолданылатын шифрлеу жүйесі алынды,
авторлардың есімдерінің алғашқы аттарына сәйкес RSA деп аталды. Бұл функция
мынадай:
1) функциясының мәндерін есептейтін әлдеқайда жылдам әдіс бар;
2) кері функциясының мәндерін есетейтін жылдам әдіс бар;
3) функциясының құпиясы бар, егер оны анықтасақ,
мәндерін тез есептеуге болады; қарсы жағдайда есептеуге ауыр,
көп уақытты кетіретін, шешуге мүмкін емес есепке айналады.
RSA осы жылдар ішінде ұсынылған ашық кілтті қолданатын алгоритмдер
ішінде ең оңай түсінуге және жүзеге асыруға болатын алгоритм.
Бұл дипломдық жұмыс криптографияның ашық кілтті қолданатын
алгоритмдердің бірі – RSA-ға арналған.
Осыған орай дипломдық жұмыстың мақсаты – RSA алгоритмін қазіргі
таңдағы технологияларды пайдалана отырып, ақпаратты қорғау саласында
кеңінен қолдана алатын автоматтандыру жүйесін құру.
Жұмыстың мақсаты дипломдық жұмыс барысында шешілген келесі міндеттерді
анықтады:
1. Сандар теориясын, оның бөлімдерінің бірі жан сандарды зерттеу. Өте
үлкен жай сандарды іздеу
2. Екілік жүйедегі сандармен жұмыс жасау
3. Ашық және жабық кілттердің құрылымын зерттеу
4. Бір компьютерден екінші бір компьютерге ақпаратты шифрлеп
жібергенде, барлық қауіпсіздік ережелерін сақтау және зерттеу
Дипломдық жұмыс кіріспеден, төрт бөлімнен, қорытындыдан, әдебиеттер
тізімінен және қосымшадан тұрады. Кіріспеде жұмыстың өзектілігі берілген,
мақсаты қойылған, сол мақсатқа қол жеткізу міндеттерінен тұрады. Зерттеу
объектісі және пәні, оның методологиялық негізі және жұмыстың практикалық
маңыздылығы анықталған. Бірінші бөлімде криптографияның негізгі түсініктері
мен тарихы, оның жұмыс істеу принциптері мен алгоритмдері, сонымен қатар,
RSA алгоритмінде қолданатын математикалық негіздемелер туралы теориялық
анықтамалар орын алған. Бірінші бөлімнің басты қорытындысы –
криптографияның бастамасын түсіндіру, оның әдістемелері мен алгоритмдерін
таныстыру болып табылады. Екінші бөлім ашық кілтті қолданатын
алгоритмдерге, соның ішінде, RSA алгоритміне арналған. Үшінші бөлім .NET
платформасына, оның құрылымы мен сипаттамасына арналған. Бұл бөлімде C#-тың
басқа объектілі-бағытталған программалардан айырмашылығын көрсетілген.
Төртінші бөлім жұмыстың қойылымына, яғни бағдарламалық бөлімге арналған.
Онда әрбір батырманың мақсатына дейін айтылып кеткен. Ал олардың
бағдарламалық кодтары қосымшаларда жазылып кеткен.
Қорытынды бөлімінде дипломдық жұмыс тақырыбы бойынша жалпылама
қорытындылар жасалған.
КРИПТОГРАФИЯ НЕГІЗДЕМЕСІ
1 Криптографияның негізгі түсініктемелері мен тарихы
Ақпаратты оны түрлендіру арқылы басқа адам оқи алмайтындай қорғау
мәселесі адамзат алдында бұрыннан тұрған мәселелердің бірі болып табылады.
Криптография тарихы – адамзат тілінің тарихының замандасы. Оған қоса, жазу
алғашқыда криптографиялық жүйе болы табылды, себебі, ежелге қоғамда онымен
тек ерекше таңдаулы адамдар ған иелік етті. Ежелгі Египет пен Үндістанның
киелі кітаптары соған мысал бола алады. Криптография жазудың кең таралуына
байланысты дербес ғылым ретінде қалыптаса бастады.
Криптография тарихын шартты түрде 4 қадамға бөлуге болады:
1) жай криптография
2) ресми криптография
3) ғылыми криптография
4) компьютерлік криптография
Жай криптография үшін (XVI ғасыр басына дейінгі кезең) қарсыласты кез
келген шифрлік мәтін мазмұнына қатысты шатыстыру тән. Бастапқы қадамда
ақпаратты сақтау үшін криптографиямен барабар кодтау және стеганография
әдістері қолданды.
Көптеген қолданылатын шифрлар орын ауыстырулар немесе моноалфавиттік
ауыстыру арқылы жүзеге асырылды. Жарияланған мысалдардың бірі болып Цезарь
шифры табылады, ол мәтіндегі алдыңғы әріпті алфавитте одан алыс тұратын
әріпке ауыстыру арқылы жүзеге асырылады. Басқа шифр, полибианды квадрат,
грек жазушысы Полибий шығарған, алфавитпен өлшемі 5х5 болатын квадратты
кестеге кездейсоқ толтырылатын грек алфавитінің көмегімен жүзеге асатын
жалпы моноалфавитті орын ауыстыру болып табылады. Әр әріп квадратта одан
төмен тұратын әріппен ауыстырылады.
Ресми криптография қадамы (XVғ.аяғы-XX ғ. басы) криптоанализдің ресми
және салыстырмалы түрде тұрақты шифрлерінің пайда болуымен байланысты.
Еуропа елдерінде бұл Қайта өрлеу дәуірі кезінде пайда болды, яғни ғылым мен
сауданың дамуы ақпаратты қорғаудың әдістері керек болған кезде пайда болды.
Бұл қадамдағы маңызды рөлді Леон Батисте Альберти атқарды, ол көп әліппелі
орын ауыстыруды алғаш ұсынған итальян архитекторы. 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) болса,
х есептеудің оңай тәсілі жоқ.
Біржақты функциялардың көптеген кластары ашық кілтті жүйенің
көптүрлілігін тудырады. Алайда біржақты функциялардың барлығы ақпараттық
жүйесінде қолдануға жарай бермейді. Қайта оралмайтын деген түсінікте
теориялық қайта ораламсыздығы емес, белгіленген уақыт интервалында қазіргі
заманғы есептеу құралдарын қолдану арқылы кері мәнін практикалық тұрғыдан
есептей алмау айтылады. Сондықтан, ақпаратты тиімді сақтау үшін ашық кілтті
жүйелерге екі айқын әрі маңызды талап қойылады:
1) Бастапқы мәтіннің түрленуі қайтымсыз болу керек және ашық кілт
негізінде қайта қалпына келмеу керек.
2) Ашық кілт негізінде жабық кілтті анықтау жаңа технологиялық
тұрғыдан мүмкін емес болу керек. Мұнда шифрды анықтауда
күрделіліктің төменгі бағасы көрсетілуі керек.
Ашық кілтті шифрлеу алгоритмдері кең қолданысқа ие болды. RSA алгоритмі
ашық жүйелер үшін әлемдік де-факто стандарты болды. Қазіргі таңда
ұсынылатын ашық кілтті криптожүйелер қайтымсыз түрленудің төмендегідей
топтарына жіктеледі:
1) Үлкен сандарды көбейткіштерге жіктеу;
2) Соңғы өрісте логарифмді есептеу;
3) Алгебралық теңдеулердің түбірлерін анықтау.
Ашық кілтті криптожүйелерді 3 түрлі мақсатта қолдануға болады:
1) Жіберілген және сақтаудағы мәліметтерді өзіндік қорғау құралы
ретінде.
2) Кілттерді үлестіру құралы ретінде. Ашық кілтті жүйелер алгоритмдері
дәстүрлі криптожүйелермен салыстырғанда аса көп еңбекті қажет
етеді.
3) Тұтынушыларды аутентификациялау құралы ретінде.
2 Математикалық негіздемелер
2.1 Күрделілік теориясы
Күрделілік теориясы криптографиялық әдістер мен алгоритмдердің әр түрлі
есептеу күрделіліктеріне қарай әдістемелік талдау жасауға мүмкіндік береді.
Ол криптографиялық әдістері мен алгоритмдерін салыстыра отырып, оның
қаншалықты қауіпсіз екендігін анықтайды.
Алгоритмнің күрделілігі
Алгоритмнің күрделілігі оның орындалуға керекті есептеулік қуаттарымен
есептеледі. Есептемелік алгоритмнің күрделілігі мынадай екі параметрмен
өлшенеді: 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) тұрақтыдан қарағанда тездетіп өсетін,
бірақ сызықтыдан баяу болатын функция.
3-кесте. 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)-
ге тең.
Проблеманың күрделілігі
Күрделілік теориясы белгілі бір алгоритмді шешудің проблемасын ғана
қарастырмайды, сонымен қатар, проблеманың қаншалықты күрделі екенін де
анықтайды. Атап айтқанда, сол проблеманы шешуге керекті минималды уақытты
және жадының көлемін қарастырады. Оны Тьюринг машинасы деп атайды. Тьюринг
машинасы шекзіз жадымен жабдықталған, алгоритмді оқу және жазу үшін
арналған есептеудің наңыз моделі болып табылады.
Полиноминалды уақыттық алгоритмдер арқылы шешілетін проблемаларды
шешілетін проблемалар деп атайды. Яғни, белгілі ақпарат үшін белгілі уақыт
бөлініп, сол уақытта шешіледі. Полиноминалды уақыт ішінде шешілмейтін
проблемаларды шешілмейтін деп атайды. Кей жағдайларда, шешілмейтін
проблемаларды қиын (ауыр) проблемалар деп те атайды. Алан Тьюринг кейбір
проблемаларды шешудің алгоритмін табу мүмкін еместігін дәлелдеді.
Барлық проблемаларды олардың шешілуіне байланысты сәйкесінше кластарға
бөлуге болады. Ең маңызды кластар төменде көрсетілген.
Шешілетін проблемалар класы
3-сурет
Ең төменде орналасқан Р класы полиномиальды уақытта шешуге болатын
барлық мәселелерден тұрады. 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-ге тең болмайтындығы дәлелденген.
2.2 Сандар теориясы
Айыру арифметикасы
Айыру арифметикасын барлығымызға мектеп кезінен мәлім. Оны кейде
арифметикалық сағат деп те атаған. Егер Милдред әкесіне үйде 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)
(а-b) mod n=((а mod n)-(b mod n)) ) mod n
(2)
(а*b) mod n=(( а mod n)*(b mod n)) ) mod n
(3)
(а*(b+с)) mod n=(((а*b) mod n)+((а*с) mod n)) mod n
(4)
mod n есептеу әдетте криптографияда көп қолданылады, себебі дискретті
логарифмдер мен mod n квадраттық түбірін есептеу оңай емес мәселе болуы
мүмкін. Есептен шығару арифметикасы компьютерлерде оңай жүзеге асады,
себебі ол аралық мәндер мен нәтижелер диапазонын шектейді. n –ның к-битті
есептеулеріне кез-келген қосу, алу, көбейтудің аралық нәтижелері 2 к биттен
артық болмайды. Сондықтан есептеу арифметикасында дәрежеге келтіру үшін
үлкен аралық нәтижелерді қолданбай орындауға болады. Кейбір санның
дәрежесін басқа санның модулі бойынша есептеу көбейту мен бөлудің тізбегі
болады, алайда оларды тездететін тәсілдер бар:
ах mod n.
(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=(а*х) mod n
(6)
Бұны былай да жазуға болады:
а-1=х(mod n)
(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
(8)
Егер мынадай теңдеу белгілі болса,
n =рq
(9)
мұндағы р мен q-жай сандар болса, онда
φ(n) =(р-1)(q-1)
(10)
болады. Бұл сандар кейбір алгоритмдерде ашық кілтпен келеді. Бұның
себебі мынада: Эйлер теоремасы мен Ферманың кіші теоремасын сәйкес
жалпылағанда, егер ЕҮОБ(а, n )=1 болса, онда
а φ(n) mod n=1
(11)
Енді а-1 mod n есептеу қиын емес:
х=а φ(n)-1 mod n
(12)
Мысалы, қандай сан 7 модулі бойынша 5 санына кері мәнге ие болады? 7
жай сан болғандықтан, φ(7) =7-1=6.
Осылайша 5 санына 7 модулі бойынша кері мән мынаған тең болады:
56-1 mod 7=55 mod 7=3.
Бұл кері мәндерді есептеу тәсілін х мәнін табудың ортақ мәселесіне
кеңейтуге болады:
(а*х) mod n= b
(13)
Эйлер жалпыламасын қолдана отырып, мынаны шешеміз:
х= (b* а φ(n)-1) mod n
(14)
Эвклид алгоритмін қолдана отырып, мынаны табамыз:
х= (b* (а-1 mod n)) mod n
(15)
Жалпы жағдайда кері мәндер алгоритмін есептегенде Эвклид алгоритмі
Эйлердің жалпыламасына қарағанда тезірек, әсіресе 500 битті сандар үшін.
Егер ЕҮОБ(а, n )≠1 болса да шешімін табуға болады. Бұл жағдайда (а*х) mod
n= b, не бірнеше шешімі, не бірде-бір шешімі болмайды.
Лежандр символы
Лежандр символы L(а,р) егер а – кез келген бүтін сан болса, ал р-2-ден
үлкен жай сан болса анықталған болады. Ол 0,1 немесе -1-ге тең болады.
L (а, р) =0, егер а р-ға бөлінсе.
L (а, р) =1, егер а –р модулі бойынша квадраттық есептен алу болса.
L (а, р) =-1, егер а –р модулі бойынша квадраттық есептен алу болмаса.
L (а, р) = а(р-1)2 mod р.
(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 сандары
қолданылады. Екілік санау жүйесі сандық құрылғыларда қолданылады, себебі
әлдеқайда ыңғайлы және барлық талаптарға сай:
- Жүйеде мәндер қаншалықты аз болса, соншалықты жеке элементтер
дайындау ыңғайлы.
- Элементтің күй элементі аз болған сайын, оның кедергіге шыдамдылығы
жоғары болады және ол соншалықты тез жұмыс істейді.
Қосу мен көбейтуді жасау кестесінің қарапайымдылығы-сандарға
қолданылатын қарапайым амал
2.3 Жай сандар генерациясы
Жай сан деп – бірден үлкен және тек бірге, өзіне ғана бөлінетін бүтін
сан: ол басқа ешқандай санға бөліне алмайды. Екі - жай сан. Жай сан болып
73, 2521, 2365347734339 және 2756839-1 бола алады. Жай сандардың шексіз көп
түрі бар. Ашық кілтті криптография көбінесе үлкен жай сандарды пайдаланады
(512 бит және одан да көп).
Ашық кілті бар алгоритмдер үшін жай сандар қажет. Олардың біршама үлкен
желісі үшін көптеген жиыны керек. Генерация математикасына көшпес бұрын
бірнеше айқын сұрақтарға жауап берейік.
Егер әрқайсысына өзінің жай саны керек болса, қор таусылмайды ма? Жоқ.
Шын мәнінде 1-ден 512 битке дейінгі 10151 сан бар. n-ге жақын сандар үшін
кездейсоқ таңдалынған сан жай болу ықтималдығы 1ln n болады. Сондықтан,
жай сандардың n –нен кіші толық саны n( ln n) болады. Әлемде барлығы 1077
атом бар. Егер ғаламшардағы барлық атомдар үшін әр микросекунда сайын
миллиард сан қажет болса, онда жай сандардың тек 10109 керек болар еді,
сонда жай сандардың 10151 қалар еді.
Егер екі адам бірдей жай санды кездейсоқ таңдаса? Ондай болмайды.10151
санды таңдағанда сәйкес келу ықтимаалдығы өте аз. Егер біреу барлық жай
сандар базасын құрса, онда ол оны ашық кілті бар алгоритмдерді ашуға
қолдана ала ма? Жоқ. Егер сіз 1 гигабайт ақпаратты 1 грамм салмағы бар
құрылғыда сақтасаңыз да, ондағы ақпаратты одан шығара алмайсыз. Егер
көбейтінділерге жіктеу сонша қиын болса, онда жай сандар генерациясы
қалайша оңай болады? n саны жай сан ба деген сұраққа жауап беру n-нің
бөлінділері қандай деген сұраққа жауап беруге қарағанда әлдеқайда оңай.
Бөліндімен тексеру
Бұл көбейтінділерге жіктеудің ең көне тәсілінің әдісі әр жай санды
тексеруден,жіктелініп жатқан санның кіші немесе тең квадраттық түбірін
анықтаудан тұрады. Егер де белгілі бір себеппен санның жайлығын тексеру
керек болса, қателік деңгейін төмендетуге болады.
Көбейтінділерге жіктеудің келесі әдісімен кездейсоқ сандар генерациясы-
бұл жай сандарды іздеудің қате әдісі.Жай сандарды тексеру әдісінің
тексерілген бірнеше тәсілі бар.Тек тексеру деңгейі жоғары болса, бұл
тексеру әдісі тиімді болып келеді.Бұл тәсілмен генерацияланған жай сандарды
өндірістік жай сандар деп атайды: бұл сандар бақыланатын қате мүмкіндігі
бар сандар болып табылады.
250 санынан 1 тексеру –қате деп жорамалдайық. Бұл дегеніміз, 11015
ықтималдығымен тексеріс құрама санды жай деп айтады.
Lehmann
Басқа, одан қарапайым тест Леманнмен тәуелсіз анықталды. Бұл р санының
тексеруіндегі амалдар тізбегі:
1) р –дан кіші кез-келген а санын таңдаңыз.
2) а(р-1)2 mod р есептеңіз.
3) Егер а(р-1)2≠1 немесе -1(mod р) болса, онда р жай сан болмайды.
4) Егер а(р-1)2≡1 немесе -1(mod р) болса, онда р санының жай сан
болу ықтималдығы 50 пайыздан көп болмайды.
Осы тексерісті t рет орындаңыз. Егер есептеу нәтижесінің ықтималдығы 1
немесе -1 болса, бірақ әр уақытта 1 болмаса, онда р қателігі 12 t болатын
жай сан болып табылады.
3 Криптожүйелердің жұмыс істеу принциптері
Оқиғаны сипаттаудың қалыпты мысалы, криптография есебі туындайтын 1-
суретте көрсетілген:
Негізгі принцип
1-сурет
А мен В 1-суретте – қорғалынған ақпараттың заңды тұтынушылары, олар
ақпаратпен жалпыға бірдей байланыс каналы арқылы алмасқысы келеді. П –
заңсыз тұтынушы (қарсылас, хакер), жіберілген ақпаратты қағып алып, одан
өзіне қажетті жаңа ақпарат немесе мәлімет алғысы келетін адам. Бұл
қарапайым схеманы ақпаратты қорғау немесе шифрлеудің криптографиялық
әдістері қолданылатын әдеттегі оқиғаның моделі ретінде қарастыруға болады.
Тарихи тұрғыдан қарастырғанда, криптографияда кейбір әскери сөздер
бекінді (қарсылас, шифрге шабуыл). Олар криптографиялық түсініктердің ойын
нақты анықтайды. Оған қоса кең қолданылатын әскери терминология, код
түсінігі бойынша (әскери-теңіздік кодтар, Генералдық штаб коды, кодтық
кітаптар, кодтық белгілеулер және т.б.) теориялық криптографияда
қолданылмайды. Соңғы жылдары кодтау теориясы қалыптасты. Байланыс каналында
кездейсоқ бұзылудан ақпаратты қорғау әдістерін зерттейтін және жасайтын
кодтау теориясы пайда болды.
Криптография қарсылас жіберіліп жатқан ақпаратты қарсылас қағып алмау
үшін ақпаратты түрлендірумен айналысады. Мұнда байланыс каналы арқылы
қорғалынатын ақпарат емес, ал оның шифр арқылы түрлену нәтижесі жіберіледі
және қарсылас үшін осы шифрды анықтау қиынға соғады. Шифрды бұзу – шифрды
қолдану білімінсіз шифрленген ақпаратты қорғалынатын ақпаратты алу процесі.
Қарсылас ақпаратты алу ғана емес, сонымен қатар оны өшіруге, жоюға
тырысады. Бұл – ақпарат үшін басқа кедергі, ол қағып алу немесе шифр
бұзудан ерекшеленеді. Мұндай қауіптен қорғану үшін спецификалық әдістер
қолданылады. Яғни, заңды тұтынушыдан басқасына ақпарат беру керек кезінде
әртүрлі әдістермен қорғалыну керек. Әртүрлі типтен тұратын бөліктер
тізбегінен тұратын ақпаратты қорғайтын жағдай туып отыр. Қарсылас ең әлсіз
бөлікті іздейді. Бұдан келесі ереже шығады: бір бөлігін өте мықты қылудың
маңызы жоқ, егер бір бөлігі кемінде әлсіз болса.
Жақсы шифр ойлап табу оңай шаруа емес. Сондықтан жақсы шифрдың
өміршеңдігін ұзартып, оны көп ақпаратты шифрлеу үшін қолдану керек. Алайда,
қарсылас шифрды анықтап қойды деген қауіп туады, бұл жағдайда ауыстырылатын
кілт болады, сондықтан қарсылас әрі қарай ақпаратты оқи алмайды және шифр
ашу үшін жасаған амалдары нәтижесіз болады.
3.1 Криптографиялық кілттерді басқару
Криптографияда кілт ұғымы астарында шифрдің ауыстырылатын элементі
жатыр, ол тек нақты бір хабарламаны шифрлеуде қолданылады. Соңғы уақытта
қорғалынатын ақпараттың қауіпсіздігі кілтпен анықталады. Шифрмашина немесе
шифрлеу принципі бойынша қарсыласқа шифр белгілі деп санай бастады және
алдын-ала зерттеуге болатын, алайда қарсыласқа белгісіз, тек ақпараттың
түрленуіне байланысты кілт пайда болды. Енді заңды тұтынушылар шифрлік
хабарламалармен алмаспас бұрын қарсыластан құпиялы түрде кілттерімен алмасу
керек немесе байланыстың екі жағында бірдей кілт орнату керек. Ал қарсылас
үшін жаңа қиындық туады – кілтті анықтау, тек содан кейін кілтте шифрленген
ақпаратты оңай ашуға болады.
Криптографияның негізгі обьектісінің сипаттамасына қайта оралайық. Енді
оған сәйкес өзгерістер енгізу керек – қарсылас үшін мүмкін емес болатын
кілт алмасу үшін құпия каналды қосу.
Кілттерді қолдану мысалы
2-сурет
Мұндай байланыс каналын жасау өте оңай және оның ақпарат жүктемесі
күрделі емес. Барлық жағдайлар үшін ажырайтын бірегей шифр болмайтындығын
атап өту керек. Шифрлеу әдісін таңдау ақпараттың ерекшелігіне, оның
құндылығы мен иелерінің ақпаратты қорғау үшін мүмкіндіктеріне тікелей
байланысты. Ең алдымен қорғалынатын ақпараттың көптүрлілігін атап өтейік:
құжаттық, телефондық, теледидарлық, компьютерлік. Ақпараттың әр түрінің
өзіндік ерекше қасиеттері бар және бұл ерекшеліктер ақпаратты шифрлеу
әдісіне зор әсерін тигізеді. Үлкен рөлді көлемі мен шифрленген ақпараттың
таралу жылдамдығы атқарады. Шифр түрін таңдау және оның параметрлерін
орнату қорғалынатын құпия мен сектор түріне байланысты. Кейбір құпиялар (
мысалы, әскери, мемлекеттік) он жылдап сақталыну керек, ал кейбіреулері
(мысалы, биржалық) бірнеше сағаттан соң жариялануы мүмкін. Сонымен қатар,
ақпарат қорғалынатын қарсыластың мүмкіндігіне де байланысты. Бір жағдай,
бір немесе бірнеше қылмыскерлер тобына қарсы тұру, ал екіншісі, қуатты
мемлекеттік құрылымға қарсы тұру.
Кез келген қазіргі заманғы криптографиялық жүйе криптографиялық
кілттерді пайдалануға негізделген. Ол белгіленген әдістеме бойынша жұмыс
жасайды: шифрлеудің бір немесе бірнеше алгоритмі; осы шифрлеудің
алгоритмдері пайдаланатын кілттер; кілттерді басқару жүйелері; шифрленбеген
мәтін; шифрлік мәтін.
3.2 Симметриялық (құпиялы) әдістемелер мен алгоритмдер
Бұл әдістемеде шифрлеу үшін де, оның шифрын бұзғанда да хабар жіберуші
мен алушы да бірдей кілт қолдану керек. Егер кілт компрометтенген болмаса,
онда шифр бұзуда автоматты түрде хабар жіберушінің аутентификациясы жүреді,
себебі, тек хабар жіберушінің өзі ғана кілтке ие, тек хабар алушы ғана
шифрды ашатын кілтті біледі. Хабар жіберуші мен алушы –симметриялық кілтті
білетін жалғыз адамдар. Мәселе, тек осы кілттерді қалайша қауіпсіз
тасымалдауға болатындығында.
Симметриялық шифрлеудің алгоритмдері ондай қатты ұзақ емес кілтті
қолданады және көп мөлшерде мәліметті тез шифрлей алады. Симметриялық
кілттерді пайдалану реті:
1) Симметриялық құпия кілт қауіпсіз жасалынады, шығарылады, таратылады
және сақталынады.
2) Хабар жіберуші мәтін үшін хэш-функциясын есептеу арқылы электрондық
қолтаңба жасайды және алынған қатарды мәтінге тіркейді.
3) Хабар жіберуші шифрлеудің жылдам симметриялық алгоритмдерін
қолданады- шифрленген мәтінді алу үшін алынған пакетке симметриялық
құпия кілтін тіркеу арқылы шифрды бұзу тәсілін анықтайды. Осы
тәсілмен аудентификация жүреді, себебі хабар жіберуші симметриялық
құпия кілтін біледі және бұл пакет шифрын бұза алады.
4) Хабар жіберуші ғана шифрленген мәтінді біледі. Симметриялық құпия
кілт ешқашан қорғалмаған байланыс каналдар арқылы таратылмайды.
5) Хабар алушы дәл сол симметриялық құпия кілт алгоритмін пайдаланады.
Оның сәтті қалпына келуі құпия кілтті білетін адамды
аутентификациялайды.
6) Хабар алушы электрондық қолтаңбаны мәтіннен бөледі.
7) Хабар алушы басқа электрондық қолтаңбаны ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Ұқсас жұмыстар
Пәндер
- Іс жүргізу
- Автоматтандыру, Техника
- Алғашқы әскери дайындық
- Астрономия
- Ауыл шаруашылығы
- Банк ісі
- Бизнесті бағалау
- Биология
- Бухгалтерлік іс
- Валеология
- Ветеринария
- География
- Геология, Геофизика, Геодезия
- Дін
- Ет, сүт, шарап өнімдері
- Жалпы тарих
- Жер кадастрі, Жылжымайтын мүлік
- Журналистика
- Информатика
- Кеден ісі
- Маркетинг
- Математика, Геометрия
- Медицина
- Мемлекеттік басқару
- Менеджмент
- Мұнай, Газ
- Мұрағат ісі
- Мәдениеттану
- ОБЖ (Основы безопасности жизнедеятельности)
- Педагогика
- Полиграфия
- Психология
- Салық
- Саясаттану
- Сақтандыру
- Сертификаттау, стандарттау
- Социология, Демография
- Спорт
- Статистика
- Тілтану, Филология
- Тарихи тұлғалар
- Тау-кен ісі
- Транспорт
- Туризм
- Физика
- Философия
- Халықаралық қатынастар
- Химия
- Экология, Қоршаған ортаны қорғау
- Экономика
- Экономикалық география
- Электротехника
- Қазақстан тарихы
- Қаржы
- Құрылыс
- Құқық, Криминалистика
- Әдебиет
- Өнер, музыка
- Өнеркәсіп, Өндіріс
Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.
Ақпарат
Қосымша
Email: info@stud.kz