Есептеу машиналары мен электрондық құралдар

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Курстық жұмыс
Тегін: Антиплагиат
Көлемі: 26 бет
Таңдаулыға:

КІРІСПЕ
Есептеу машиналары мен электрондық құралдар адамның барлық қызметі мен
ой-өрісіне енді. Оларсыз қазіргі заманғы криптографияны елестету мүмкін
емес. Мәтінді шифрлеу мен оны бұзуды ЭЕМ көмегімен бүтін сандарды өңдеу
ретінде елестетуге болады, бұл амалдар орындалатын тәсілдер кейбір
функциялар секілді бүтін сандардың белгілі бір жиынында орындалады.
Курстық жұмыс кіріспеден, 2 бөлімнен, қорытындыдан және әдебиеттер
тізімінен тұрады.
Курстық жұмыстың 1 бөлімінде криптографияның негізгі түсініктемелері
мен тарихы туралы айталған. Криптография тарихын шартты түрде 4 қадамға
бөлуге болады:
1) жай криптография
2) ресми криптография
3) ғылыми криптография
4) компьютерлік криптография
Жай криптография үшін (XVI ғасыр басына дейінгі кезең) қарсыласты кез
келген шифрлік мәтін мазмұнына қатысты шатыстыру тән. Бастапқы қадамда
ақпаратты сақтау үшін криптографиямен барабар кодтау және стеганография
әдістері қолданды.
Криптожүйелердің алғашқы класы болып қолдану кезінде қуатты әрі
жинақты есептеу құралдарының пайда болуына байланысты шыққан блоктық
шифрлар болды.
Курстық жұмыстың 2 бөлімінде Бөлім 2. Ашық кілтті қолданылатын
алгоритмдер ашық кілтті қолданатын алгоритмдердің қауіпсіздігі және RSA
алгоритмі туралы түсінік берілген.
RSA - ұсынылған ашық кілтті қолданатын алгоритмдер ішінде ең оңай
түсінуге және жүзеге асыруға болатын алгоритм болып табылады. Бұл
алгоритмді ғылымға 1978-жылы американдық Р. Ривест, А. Шамир және Л.
Адлеман (R.L.Rivest. A.Shamir. L.Adleman) енгізді. Осы авторлардың
есімдерінің алғашқы аттарына сәйкес RSA деп аталды. Бұл функция мынадай:
1) функциясының мәндерін есептейтін әлдеқайда жылдам әдіс бар;
2) кері функциясының мәндерін есетейтін жылдам әдіс бар;
3) функциясының құпиясы бар, егер оны анықтасақ, мәндерін тез
есептеуге болады;
4) қарсы жағдайда есептеуге ауыр, көпуақытты кетіретін, шешуге
мүмкін емес есепке айналады.
Менің курстық жұмысымның мақсаты ашық және жабық кілттердің құрылымын
зерттеу және RSA алгоритмі арқылы ақпаратты шифрлеудің ерекшеліктеріне
түсінік беру. Ассимметриялық криптография негіздеріне сипаттамасын
қарастыру.
Бөлім 1. Криптография негіздемесі

1.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-жылдарда көшбасшы криптографиялық мектептер блоктық сандар жасауға
көшті, олар роторлық криптожүйелермен салыстырғанда аса тұрақты, алайда
олар тек сандық электронды құрылымдарды жүзеге асыруды ғана қамтамасыз
етті.
1.2. Ассимметриялық криптография

Компьютерлік криптография (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 Ашық кілтті қолданатын алгоритмдердің қауіпсіздігі

Ашық кілтті қолданатын криптография тұжырымын Уитфилд Диффи және
Мартин Хеллман, сондай-ақ Ральф Меркл ұсынған болатын. Олардың
криптографияға енгізген салымы – кілтті жұбымен қолану – шифрлеу кілті және
дешифрлеу кілті – және біреуінен екіншісін алу мүмкін еместік сенімі. Ең
алғаш рет 1976-жылы Диффи және Хеллман өз ойын Ұлттық компьютерлік
конференциясында (National Computer Confrens) көрсетіп, бірнеше айдан кейін
олардың жұмысының негізі болатын “New Directions in Cryptography”
(Криптографияның жаңа бағыты) басылып шықты.
1976-жылдан кейін көптеген ашық кілтті қолданатын криптографиялық
алгоритмдер ұсынылған. Олардың көбі қауіпсіз емес. Ал қауіпсіз дегендердің
көбі жүзеге асыруға жарамсыз болып келеді.
Әрі өнімді, әрі қауіпсіз болып келетін алгоритмдер көп емес. Әдетте
бұндай алгоритмдер негізгі қиын мәселеге негізделген. Осы әрі қауіпсіз,
әрі өнімді алгоритмдердің кейбіреуі кілттерді бөлуге ғана жарамды.
Басқалары шифрлеуге және кілттерді бөлуге де жарамды. Үшіншілері тек цифрлі
жазуға ғана жарамды болып келеді. Тек қана үш алгоритм кілтті бөлуге де,
шифрлеуге де, цифрлі жазуға да жарамды: RSA, ELGamal және Rabin. Бұл
алгоритмдердің барлығы баяу. Олар симметриялы алгоритмге қарағанда
шифрлеуді де, дешифрлеуді де баяу жасайды. Әдетте олардың жылдамдығы үлкен
мәліметтер көлемін шифрлеуге аз болады.
Будан криптожүйелер оқиғаларды жылдамдатуға мүмкіндік береді:
хабарламаны шифрлеуде кездейсоқ кілтті симметриялы алгоритм қолданылады,
ал ашық кілтті қолданатын алгоритм кездейсоқ сеансты кілтті шифрлеуге
қолданылады.
Криптоаналитиканың ашық кілтке қолданатын кірісінің болуы, оның
шифрлеуге кез-келген хабарламаны алуына мүмкіндік береді. Яғни,
криптоаналитик берілгеннен Р болжап, оны оңай тексере алады. Егер
жеткілікті іздеуге мүмкіндік беретін, ашылған мәтіннің мүмкін саны сонша аз
болса, бұл күрделі мәселе болып табылады, бірақ бұл мәселені кездейсоқ
биттер жолының хаттамасымен толтыра оңай шешуге болады. Бұл біртекті ашық
мәтіндерге әр түрлі шифромәтіндер сәйкес келуіне әкеледі.
Егер ашық кілтті қолданатын алгоритм сеансты кілтті шифрлеу үшін
қолданылса әсіресе маңызды болады. Ева Бобаның ашық кілтпен қолданатын
шифрлеуін сеансты кілттердің барлық мүмкін мәліметтер базасын жасай алады.
Әрине, бұл көп уақыт пен жады орнын алады, бірақ экспортқа рұқсат етілген
40биттік немесе 56биттік кілт DES-тегі күшпен бұзу қайда қалай көп уақыт
пен жадтағы орынды қажет етеді. Ева осындай мәліметтер базасын жасай
салысымен Бобтың кілтін алып, оның почтасын оқи алады. Ашық кілтті
қолданатын алгоритмдер таңдалған ашық мәтінді ашуға қарсы тұра алатындай
құрылған. Оның қауіпсіздігі құпия кілтті ашық бойынша алу қиыншылығына
негізделген болса, сол сияқты ашық мәтінді шифромәтін бойынша алу
қиыншылығына да негізделген. Егер шифрлеу мен жазбаға бірдей кілттер
қолданса, жүйеде шифрлеумен өңделген операциялар цифрлік жазбаға үшін бұл
ашуды болдырмау мүмкін емес. Сондықтан қрамды бөлігін ғана емес, жүйенің
барлығын толығымен көру қажет.

2.2. Қол қапшық алгоритмі

Ашық кілтті қолданатын шифрлеуді тарату үшін ең алғашқы алгоритм Ральф
Меркл мен Мартин Хеллман өңдеген қол қапшық алгоритмі болды. Ол тек шифрлеу
үшін ғана қолданылатын, бірақ кейіннен Ади Шамир цифрлі жазбаға бейімдеді.
Қол қапшық алгоритмінің қауіпсіздігі қол қапшық мәселесі – NP толық
мәселесіне сүйенеді.
Қол қапшық мәселесі қиын емес. Әр түрлі салмақта көп заттар берілген
болса, қол қапшықтың салмағы белгілі бір мәнге ие болатындай етіп, кейбір
заттарды қол қапшыққа салуға болады ма? Формальді түрде, М1,М2...Мn және
қосындысы S, bi мәнін есепте, егер

(1)

bi ноль немесе бір ғана бола алады. Бір қол қапшыққа затты салады
дегенді білдіреді, ал ноль салмайды дегенді білдіреді. Мысалға заттардың
салмағы 1,5,6,11,14 және 20 деген мәндерге ие болсын. Сіз қол қапшыққа 5,6
және 11 мәндерін қолдана салмағы 22 болатындай етіп сала аласыз. Қол
қапшыққа 24 болатындай етіп сала алмайсыз. Бұл мәселе заттардың санынң
өсуіне байланысты өзгереді, яғни мәселні шешуге болады.
Маркл–Хеллмен қол қапшық алгоритмінің негізінде хатты шифрлеу идеясы
жатыр. Үйіндіден заттарды таңдау ашық мәтінді блок көмегімен, ұзындығы
үйіндідегі зат санына сәйкес келеді, ал шифромәтін алынған қосынды болып
келеді. Қол қапшық мәселесі көмегімен шифрлеудің шифромәтіні көрсетілген:
Ашық мәтін 1 1 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0
0 1 1 0 0 0

Қол қапшық 156 11 14 20 156 11 14 20 156 11 14 20 156 11 14 20

Шифромәтін 1+5+6+20=32 5+11+14=30 0=0 5+6=11

Негізінде қол қапшықтың екі түрлі мәселесі бар: бірін сызықтық уақыт
ішінде шешіледі, ал екіншісі – жоқ. Оңай мәселені қиындатуға болады. Ашық
кілт шифрлеуге оңай қолдануға болатын қиын мәселені көрсетеді, бірақ хатты
дешифрлеуге болмайды. Жабық кілт хатты дешифрлеудің оңай әдісін беретін,
оңай мәселе болып табылады.
Күрт өсетін қол қапшықтар. Қол қапшықтың оңай мәселесі деген не?
Салмақ тізімі күрт өсетін қатар болса, алынған қол қапшық мәселесін оңай
шешуге болады. Күрт өсетін қатар– бұл әр мүшесі алдыңғы мүшелерінің
қосындысынан үлкен болатын қатар. Мысалға, {1,3,6,13,27,52} қатар күрт
өсетін, ал {1,3,4,9,15,25} қатары – жоқ.
Күрт өспейтін немесе қалыпты қол қапшықтар қиын мәселені көрсетеді,
олар үшін тез алгоритм табылмады. Қол қапшыққа қандай зат салу керектігін
тек бір әдіспен, дұрыс шешіміне кездескенше, мүмкін болатын шешімдерді
методикалық тексеру арқылы анықтауға болады. Қатарға тағы бір мүше қосатын
болсақ, шешуін табуы екі есе қиындайды. Бұл қатарға бір зат қоссаң шешімін
табу бір операцияға өсетін күрт өсетін қол қапшықтан қайда қалай қиын.
Меркл-Хелман алгоритмі осы қасиетке негізделген. Жабық кілт күрт өсетін қол
қапшық салмақ қатарының мәселесі болып табылады. Ашық кілт – бұрынғы
шешімді қарапайым қол қапшықтың салмақ қатарының мәселесі. Меркл мен
Хеллман модульдік ариметиканы қолдану арқылы күрт өсетін қол қапшық
мәселесін қарапайым қол қапшықтың мәселесіне айналдырды.
Қол қапшықтың күрделі өсу тізбегі жабық кілт болып табылады, ал дұрыс
тізбектелген қол қапшық - ашық.
Қол қапшықтың нұсқалары. Меркл–Хеллман жүйесінің ашылуынан кейін қол
қапшық негізінде көптеген жүйелер ұсынылған еді: бір неше ретті қол қапшық,
Грэм –Шамир қол қапшықтары және т.б. Олардың барлығы талдау жасалып, бір
криптографиялық әдістің қолдануымен бұзылған.
Қол қапшықтың нұсқалары қазіргі уақытта қауіпсіз болғпнымен, Char-
Rivest қол қапшық алгоритмі, арнайы ашуға қарамастан, қажетті есептеулер
саны оның пайдасын азайтады. Powerline System нұсқасы қауіпсіз емес.
2.3. RSA алгоритмі

1978-жылы американдық Р. Ривест, А. Шамир және Л. Адлеман (R.L.Rivest.
A.Shamir. L.Adleman) функциясына мысал ұсынды, олар ерекше қасиеттерге
ие. Соның негізінде нақты қолданылатын шифрлеу жүйесі алынды, авторлардың
есімдерінің алғашқы аттарына сәйкес RSA деп аталды. Бұл функция мынадай:
1) функциясының мәндерін есептейтін әлдеқайда жылдам әдіс бар;
2) кері функциясының мәндерін есептейтін жылдам әдіс бар;
3) функциясының құпиясы бар, егер оны анықтасақ, мәндерін тез
есептеуге болады;
4) қарсы жағдайда есептеуге ауыр, көп уақытты кетіретін, шешуге
мүмкін емес есепке айналады.
RSA осы жылдар ішінде ұсынылған ашық кілтті қолданатын алгоритмдер
ішінде ең оңай түсінуге және жүзеге асыруға болатын алгоритм.
Евклид пен Диофант, Ферма, Эйлер, Гаусс, Чебышев пен Эрмит
еңбектерінде диофантты теңдеулерді шешу жөнінде маңызды ойлар жатыр, сол
заман үшін үлкен болып саналатын сандардың ең жақын мәнін табу үшін амалдар
бар. Соңғы екі он жылдықта криптография мен ЭЕМ-нің кең таралуына
байланысты сұраныстың дамуына орай сандар теориясының алгоритмдік сұрақтары
даму үстінде. Есептеу машиналары мен электрондық құралдар адамның барлық
қызметі мен ой-өрісіне енді. Оларсыз қазіргі заманғы криптографияны
елестету мүмкін емес. Мәтінді шифрлеу мен оны бұзуды ЭЕМ көмегімен бүтін
сандарды өңдеу ретінде елестетуге болады, бұл амалдар орындалаиын тәсілдер
кейбір функциялар секілді бүтін сандардың белгілі бір жиынында орындалады.
Мұның бәрі қазіргі заманғы криптографияда сандар теориясының болуына жағдай
жасайды. Сонымен қатар, кейбір криптожүйелердің тұрақтылығы тек кейбір
сандық –теориялық есептер күрделілігімен негізделеді. Бірақ ЭЕМ мүмкіндігі
шекті болып табылады. Ұзын сандық тізбекті белгілі бір өлшемді блоктарға
бөлуге тура келеді және әр блокты бөлек шифрлеуге тура келеді. Одан әрі біз
барлық шифрленетін сандарды теріс емес және берілген m санынан кіші емес
деп санаймыз.Мұндай шектеулер одан әрі шифрлеуден алынатын сандарға да
қатысты. Бұл осы сандарды бойынша есептеуге мүмкіндік береді.
Шифрленетін функция есептеу сақинасының бір-біріне сыбайлас жүйе ретінде
қарастырылынады:

(2)

ал саны шифрленген түрдегі хабарламасын көрсетеді. Мұндай
түрдің қарапайым шифры – алмастыру шифры, k-бүтін сан үшін болатын
көрініске тән. Мұндай шифрды Юлий Цезарь де қолданған. Әрине, -тің
әрбір көрінісі ақпаратты сақтау үшін қолданылады.

1978-жылы американдық Р. Ривест, А. Шамир және Л. Адлеман (R.L.Rivest.
A.Shamir. L.Adleman) функциясына мысал ұсынды, олар ерекше
қасиеттерге ие. Соның негізінде нақты қолданылатын шифрлеу жүйесі алынды,
авторлардың есімдерінің алғашқы аттарына сәйкес RSA деп аталды. Бұл функция
мынадай:

1) функциясының мәндерін есептейтін әлдеқайда жылдам әдіс
бар;

2) кері функциясының мәндерін есетейтін жылдам әдіс бар;

3) функциясының құпиясы бар, егер оны анықтасақ,
мәндерін тез есептеуге болады; қарсы жағдайда есептеуге
ауыр, көпуақытты кетіретін, шешуге мүмкін емес есепке айналады.
Мерклдың қол қапшық алгоритмінен кейін көп ұзамай алғашқы, нағыз,
шифрлеу және цифрлік жазбада қолдануға болатын: RSA ашық кілтті қолданатын
алгоритм пайда болды. RSA осы жылдар ішінде ұсынылған ашық кілтті
қолданатын алгоритмдер ішінде ең оңай түсінуге және жүзеге асыруға болатын
алгоритм. Массачусетс Технологиялық институтында баспаға шықпас бұрын, RSA
жүйесіне арналған доклад көшірмесі белгілі математик Мартин Гарднерге
жіберілді, ол 1977-жылы Scientific American журналына шифрлеудің осы
жүйесіне қатысты мақала жариялады.
2.3.1. RSA шифрлеу жүйесі
және натурал сандар болсын. RSA сұлбаның функциясының
орындалуы келесідегідей құрылған:

(3)
хатына расшифровка жасау үшін келесі теңдікті шешу жеткілікті
болып табылады:
.
(4)
Бұл теңдік және кейбір шарттарында жалғыз ғана шешімі
болады. Бұл шарттарды сипаттау үшін және шешімін табу жолын түсіндіру
үшін бізге Эйлер функциясы деп аталатын бір теоритико-сандық функция қажет
болады. Бұл функция натуралды аргументтің деп белгіленеді және
1- ден -ге дейінгі кесіндінің бүтін ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.