Криптографиялық кілттермен басқару.RSA алгоритмі

Евклид пен Диофант, Ферма, Эйлер, Гаусс, Чебышев пен Эрмит еңбектерінде диофантты теңдеулерді шешу жөнінде маңызды ойлар жатыр, сол заман үшін үлкен болып саналатын сандардың ең жақын мәнін табу үшін амалдар бар. Соңғы екі он жылдықта криптография мен ЭЕМ.нің кең таралуына байланысты сұраныстың дамуына орай сандар теориясының алгоритмдік сұрақтары даму үстінде. Есептеу машиналары мен электрондық құралдар адамның барлық қызметі мен ой.өрісіне енді. Оларсыз қазіргі заманғы криптографияны елестету мүмкін емес. Мәтінді шифрлеу мен оны бұзуды ЭЕМ көмегімен бүтін сандарды өңдеу ретінде елестетуге болады, бұл амалдар орындалаиын тәсілдер кейбір функциялар секілді бүтін сандардың белгілі бір жиынында орындалады. Мұның бәрі қазіргі заманғы криптографияда сандар теориясының болуына жағдай жасайды. Сонымен қатар, кейбір криптожүйелердің тұрақтылығы тек кейбір сандық .теориялық есептер күрделілігімен негізделеді. Бірақ ЭЕМ мүмкіндігі шекті болып табылады. Ұзын сандық тізбекті белгілі бір өлшемді блоктарға бөлуге тура келеді және әр блокты бөлек шифрлеуге тура келеді. Одан әрі біз барлық шифрленетін сандарды теріс емес және берілген m санынан кіші емес деп санаймыз.Мұндай шектеулер одан әрі шифрлеуден алынатын сандарға да қатысты. Бұл осы сандарды бойынша есептеуге мүмкіндік береді. Шифрленетін функция есептеу сақинасының бір.біріне сыбайлас жүйе ретінде қарастырылынады:
Ал, саны шифрленген түрдегі хабарламасын көрсетеді. Мұндай түрдің қарапайым шифры . алмастыру шифры, k.бүтін сан үшін болатын көрініске тән. Мұндай шифрды Юлий Цезарь де қолданған. Әрине, .тің әрбір көрінісі ақпаратты сақтау үшін қолданылады.
1978.жылы американдық Р. Ривест, А. Шамир және Л. Адлеман (R.L.Rivest. A.Shamir. L.Adleman) функциясына мысал ұсынды, олар ерекше қасиеттерге ие. Соның негізінде нақты қолданылатын шифрлеу жүйесі алынды, авторлардың есімдерінің алғашқы аттарына сәйкес RSA деп аталды. Бұл функция мынадай:
1) функциясының мәндерін есептейтін әлдеқайда жылдам әдіс бар;
2) кері функциясының мәндерін есетейтін жылдам әдіс бар;
3) функциясының «құпиясы» бар, егер оны анықтасақ, мәндерін тез есептеуге болады; қарсы жағдайда есептеуге ауыр, көп уақытты кетіретін, шешуге мүмкін емес есепке айналады.
        
        КІРІСПЕ
Евклид пен Диофант, Ферма, Эйлер, Гаусс, Чебышев пен Эрмит еңбектерінде
диофантты теңдеулерді шешу жөнінде ... ... ... сол ... үшін
үлкен болып саналатын сандардың ең жақын мәнін табу үшін ... бар. ... он ... ... мен ... кең ... байланысты
сұраныстың дамуына орай сандар теориясының алгоритмдік сұрақтары ... ... ... мен ... ... ... барлық қызметі
мен ой-өрісіне енді. Оларсыз қазіргі ... ... ... ... ... ... мен оны бұзуды ЭЕМ көмегімен бүтін сандарды
өңдеу ретінде елестетуге болады, бұл ... ... ... ... ... ... ... белгілі бір жиынында орындалады. Мұның
бәрі қазіргі ... ... ... ... ... ... ... қатар, кейбір криптожүйелердің тұрақтылығы тек кейбір
сандық –теориялық есептер күрделілігімен негізделеді. Бірақ ЭЕМ ... ... ... Ұзын ... ... белгілі бір өлшемді блоктарға
бөлуге тура келеді және әр блокты бөлек шифрлеуге тура ... Одан әрі ... ... ... ... емес және берілген m санынан кіші емес
деп санаймыз.Мұндай шектеулер одан әрі ... ... ... ... Бұл осы сандарды бойынша ... ... ... ... ... ... ... сыбайлас жүйе ретінде
қарастырылынады:
Ал, саны шифрленген түрдегі хабарламасын көрсетеді. Мұндай
түрдің қарапайым ...... ... k-бүтін сан үшін болатын
көрініске тән. Мұндай шифрды Юлий ... де ... ... ... ... ... ... үшін қолданылады.
1978-жылы американдық Р. Ривест, А. Шамир және Л. ... ... ... ... ... ... олар ерекше
қасиеттерге ие. Соның негізінде нақты қолданылатын шифрлеу ... ... ... алғашқы аттарына сәйкес RSA деп аталды. Бұл функция
мынадай:
1) функциясының мәндерін есептейтін әлдеқайда жылдам әдіс бар;
2) кері ... ... ... ... әдіс ... функциясының «құпиясы» бар, егер оны анықтасақ,
мәндерін тез ... ... ... ... ... ауыр,
көп уақытты кетіретін, шешуге мүмкін емес есепке айналады.
RSA осы жылдар ішінде ... ашық ... ... алгоритмдер
ішінде ең оңай түсінуге және жүзеге асыруға болатын алгоритм.
Бұл дипломдық жұмыс ... ашық ... ... бірі – RSA-ға арналған.
Осыған орай дипломдық жұмыстың ... – RSA ... ... ... ... отырып, ақпаратты қорғау ... ... ... автоматтандыру жүйесін құру.
Жұмыстың мақсаты дипломдық жұмыс барысында шешілген келесі ... ... ... оның ... бірі жан ... ... Өте
үлкен жай сандарды іздеу
2. Екілік жүйедегі сандармен жұмыс ... Ашық және ... ... ... ... Бір компьютерден екінші бір компьютерге ақпаратты шифрлеп
жібергенде, барлық қауіпсіздік ережелерін сақтау және ... ... ... төрт ... ... ... және қосымшадан тұрады. Кіріспеде жұмыстың өзектілігі берілген,
мақсаты қойылған, сол мақсатқа қол жеткізу міндеттерінен ... ... және ... оның методологиялық негізі және жұмыстың практикалық
маңыздылығы анықталған. Бірінші бөлімде криптографияның негізгі түсініктері
мен тарихы, оның ... ... ... мен ... сонымен қатар,
RSA алгоритмінде қолданатын математикалық негіздемелер туралы теориялық
анықтамалар орын ... ... ... ... ...
криптографияның бастамасын түсіндіру, оның әдістемелері мен ... ... ... ... ... ашық ... қолданатын
алгоритмдерге, соның ішінде, RSA ... ... ... ... ... оның ... мен сипаттамасына арналған. Бұл бөлімде C#-тың
басқа объектілі-бағытталған программалардан айырмашылығын көрсетілген.
Төртінші бөлім жұмыстың қойылымына, яғни ... ... ... ... батырманың мақсатына дейін айтылып кеткен. Ал олардың
бағдарламалық кодтары ... ... ... бөлімінде дипломдық жұмыс тақырыбы бойынша жалпылама
қорытындылар ... ... ... ... ... мен ... оны ... арқылы басқа адам оқи алмайтындай қорғау
мәселесі адамзат алдында бұрыннан тұрған мәселелердің бірі ... ... ... – адамзат тілінің тарихының замандасы. Оған қоса, жазу
алғашқыда ... жүйе болы ... ... ... ... ... ... таңдаулы адамдар ған иелік етті. Ежелгі Египет пен ... ... ... ... бола алады. Криптография жазудың кең таралуына
байланысты дербес ғылым ретінде қалыптаса бастады.
Криптография тарихын шартты ... 4 ... ... ... жай ... ресми криптография
3) ғылыми криптография
4) компьютерлік криптография
Жай криптография үшін (XVI ғасыр басына дейінгі кезең) ... ... ... ... ... қатысты шатыстыру тән. Бастапқы қадамда
ақпаратты сақтау үшін криптографиямен барабар ... және ... ... ... ... орын ауыстырулар немесе моноалфавиттік
ауыстыру арқылы жүзеге асырылды. Жарияланған мысалдардың бірі болып Цезарь
шифры ... ол ... ... ... ... одан алыс ... ауыстыру арқылы жүзеге асырылады. Басқа шифр, полибианды квадрат,
грек жазушысы Полибий шығарған, алфавитпен өлшемі 5х5 ... ... ... ... грек алфавитінің көмегімен жүзеге асатын
жалпы моноалфавитті орын ауыстыру болып табылады. Әр әріп ... ... ... ... ... ... ... (XVғ.аяғы-XX ғ. басы) криптоанализдің ресми
және салыстырмалы түрде тұрақты шифрлерінің ... ... ... ... бұл ... ... ... кезінде пайда болды, яғни ғылым мен
сауданың дамуы ақпаратты қорғаудың әдістері керек болған кезде пайда болды.
Бұл қадамдағы маңызды ... Леон ... ... ... ол көп ... ... алғаш ұсынған итальян архитекторы. XVI ғасырда Блез Вижинер
дипломатының ... ие ... бұл шифр ... ... ... әріпті
тізбекті қосу тәсілінен тұрған. Оның «шифр ... ... атты ... жөнінде алғашқы еңбегі болып табылады. Ең алғаш баспа жұмыс
болып Иоганн Трисемустың «Полиграфия» (1508 ж.) ... ... ... ... ... емес, алайда маңызды жаңалық ашты: полибиандік квадрататы
толтыру әдісі және әріп ... ... ... ... ... әрі ... әдісі болып XIX ғасырда
Чарльз Уитстонмен ашылған Плейфер шифры табылады. Уитстон маңызды жаңалық
«екілік квадрат» ... ... ... ... ... мен Уитстон шифрлары
І дүниежүзілік соғысқа дейін қолданылды. XIX ғасырда голландық Керкхофф осы
күнге дейін өзекті ... ... ... ... ... ... ... құпиялылығы алгоритм емес, кілттің
құпиялылығына ... ... ... ... оған ... ... ететін криптографияның соңғы сөзі болып
шифрларды автоматтандыруға мүмкіндік берген роторлық криптожүйе ... ... бірі ... ... ... ... Томас
Джефферсонмен жасалынған механикалық машина болды. Көп ... ... ... ... ... қарай айналым жасайтын роторлардың
вариациясы арқылы орындалады.
Роторлық машиналар практикалық жағынан сұранысқа XX ... ... ... ... ... ... машина болып 1917-жылы Эдвард Хебернмен
жасалынып, Артур Кирхпен ... ... Enigma ... ... ... ІІ дүниежүзілік соғыс кезінде кең ... ... ... өзге Sigaba, ... Red, Orange ,Purple2 ... ... ресми криптографияның шырқау шегі, себебі салыстырмалы ... ... ... ... ... сәтті криптошабуылдар 40-
жылдары ЭЕМ-нің пайда болуымен мүмкін болды.
Ғылыми криптографияның айрықша белгісі (XX ғасырдың 30-60-жылдары) ... ... ... тұрақты криптожүйелердің пайда болуы. 30-
жылдардың басына ... ... ... ... ... ... ... толық қалыптасты: ықтималдықтар теориясы және
математикалық статистика, жалпы ... ... ... ... ақпарат теориялары, кибернетика. Ерекше бөлімі ... ... ... жүйелердегі байланыс теориялары» (1949) атты еңбегі болды,
мұнда ақпаратты ... ... ... ... ... «араласу» және «бөліну» атты ұғымдарды енгізді.
60-жылдарда көшбасшы криптографиялық мектептер блоктық ... ... олар ... криптожүйелермен салыстырғанда аса тұрақты, алайда
олар тек сандық электронды құрылымдарды ... ... ғана ... ... (XX ғасырдың 70-жылдары) ... ... ... ... жоғары жылдамдығын
қамтамасыз ететін «қолдық» және «механикалық» шифрлар есептеу машиналардың
шығуына ... ... ... ... ... болып қолдану кезінде қуатты әрі жинақты
есептеу құралдарының пайда болуына байланысты шыққан блоктық шифрлар ... ... DES ... стандарты жасалды. Оның авторларының
бірі болған ... ... ол ... шифрлар моделін сипаттап, соның
негізінде жасалынған аса тұрақты симметриялық криптожүйелерді жасады.
DES-тің пайда болуымен криптоанализ ... ... ... үшін был ... ... тәсілдері жасалды (сызықтық,
дифференциалды және т.б.), практикалық қолданылу жағынан тек ... ... ... ... ... ... ... заманғы криптографияда төңкеріс болды –
асимметриялық ... ... ... ол ... ... ... кілттің таратылуын қамтамасыз етті. Мұндай негізгі ... ... және ... ... ... ... ... заманғы
криптография бағыттары» болып табылады. ... ең ... ... ... кілтсіз таратылу принциптері негізделген болатын. Асимметриялық
криптожүйелер идеясына тәуелсіз қатысты ... ... ... ... Рон Ривест, Ади Шамир және Леонард Адлеман RSA жүйесін ... ... ... ... ... ... ... оның
тұрақтылығы үлкен сандардың ... ... ... ... ... ... ... бағыттар ашты,
негізінен электронды ... ... және ... ... фейстелдік емес шифрлар жасалды (SAFER, RC6), ал ... ашық ... ... соң ... АҚШ-тың жаңа ұлттық стандарты
AES шықты. Соғыстан кейінгі кезеңнен бастап осы ... ... ... ... ... ... ... жаңартылуы мен өңделуін
тездетті. Неліктен криптографиялық әдістерді қолдану ақпараттық ... ... ... ... ... Бір ... ... торларда қолдану
кеңейді, негізінде, мемлекеттік, әскери, коммерциялық және жеке ... өте ... ... ... ғаламдық торап Интернет жүйесін
қолдану кеңейді. Басқа жағынан, жаңа ... ... ... ... және ... ... ... жақында ғана анықтау мүмкін
емес деп саналған криптографиялық ... ... ... ... ... ... түрлендіру арқылы қорғау мәселесімен
криптология (kryptos - құпия, logos - ғылым) айналысады. Криптология ... ...... және ... Бұл ... ... ... келеді.
Криптография ақпаратты түрлендіруде математикалық әдістерді іздеу және
зерттеумен айналысады. Криптоанализдің айналысатын сфералар ... ... ... ... шифрын анықтау.
Қазіргі криптография өзіне 4 үлкен бөлімді ... ... ... Ашық ... ... ... қолтаңба жүйелері.
- Кілттерді басқару.
Криптографиялық әдістерді ... ... ... – байланыс
каналдары арқылы жасырын ... ... ... ... ... ... ... шифрлі тұрде ақпаратты сақтау.
Криптографиялық жүйелер қаншалықты қиын және сенімді болғанымен
олардың практикалық ... ... жағы – ... ... ... үшін ... ... екі субьекті арасында жасырын ақпарат алмасу
мүмкін және кілт солардың біреуімен генерациялану керек, ... ... ... басқасына жіберілуі керек. Яғни, кілтті тарату үшін криптожүйені
қолдану керек. Бұл мәселені классикалық және ... ... ... негізінде шешу үшін ашық кілтті жүйелер ұсынылды. Олардың мәні
ақпараттық жүйенің әр хабар ... екі кілт ... олар ... белгілі ережеге сәйкес байланысады. Бір кілт ашық, екіншісі жабық
болып жарияланады. Ашық кілт ... және ... ... ... адам үшін ... ... ... кілт жарияланбайды.
Бастапқы мәтін хабар алушының ашық кілтімен шифрленіп, оған жіберіледі.
Шифрленген мәтіннің негізінен ашық ... ... ... ... ... ... тек хабар алушыға ғана белгілі болатын жабық кілтті
қолдану арқылы ғана мүмкін. Ашық кілтті ... ... ... немесе біржақты функциялар деп аталатын ортақ қасиеті бар қызмет
атқарады. Берілген х үшін f(x) мәнін есептеу оңай, ... тек y=f(x) ... ... оңай тәсілі жоқ.
Біржақты функциялардың көптеген ... ашық ... ... ... ... ... ... барлығы ақпараттық
жүйесінде қолдануға жарай бермейді. ... ... ... ... қайта ораламсыздығы емес, белгіленген уақыт интервалында қазіргі
заманғы есептеу құралдарын қолдану ... кері ... ... ... алмау айтылады. Сондықтан, ақпаратты тиімді сақтау үшін ашық кілтті
жүйелерге екі ... әрі ... ... ... ... мәтіннің түрленуі қайтымсыз болу керек және ашық кілт
негізінде қайта қалпына келмеу ... Ашық кілт ... ... ... ... жаңа ... мүмкін емес болу ... ... ... ... ... ... ... керек.
Ашық кілтті шифрлеу алгоритмдері кең қолданысқа ие ... RSA ... ... үшін әлемдік де-факто стандарты болды. Қазіргі ... ашық ... ... ... ... ... ... Үлкен сандарды көбейткіштерге жіктеу;
2) Соңғы өрісте логарифмді есептеу;
3) Алгебралық теңдеулердің түбірлерін анықтау.
Ашық кілтті криптожүйелерді 3 түрлі мақсатта ... ... ... және ... ... өзіндік қорғау құралы
ретінде.
2) Кілттерді үлестіру құралы ... Ашық ... ... алгоритмдері
дәстүрлі криптожүйелермен салыстырғанда аса көп ... ... ... ... ... ... ... негіздемелер
2.1 Күрделілік теориясы
Күрделілік теориясы криптографиялық әдістер мен алгоритмдердің әр ... ... ... ... талдау жасауға мүмкіндік береді.
Ол криптографиялық ... мен ... ... ... ... қауіпсіз екендігін анықтайды.
Алгоритмнің күрделілігі
Алгоритмнің күрделілігі оның орындалуға керекті ... ... ... ... ... ... екі параметрмен
өлшенеді: T(уақытқа байланысты туындайтын күрделілік) және S(кеңістікке
байланысты ... ... ... ... ... ... ... мен S, n айнымалысына тәуелді функция ретінде қарастырады. Мұндағы, n ... ... ... ... ... ... күрделілігін О() функциясы арқылы
жазады. Бұл күрделілік ... жай ... ... түрі ... ... егер ... алгоритмінің уақытқа байланысты туындайтын
күрделілігі болса, есептеулік күрделілігі n2 болып ... оны О(n2) ... ... ... ... ... ... жіктейді. Егер алгоритм n-ға тәуелді болмаса, онда ондай
алгоритмдерді тұрақты деп ... О(1) деп ... Егер ... О(n) болса, онда алгоритмді сызықтық деп атайды. Алгоритмдердің
квадраттық, кубтық және тағы да ... ... ... Бұл ...... болып келеді, ал олардың күрделілігі О(nm), мұндағы
m – ... ... ... ... бар ... ... ... алгоритмдер деп атайды.
Күрделілігі О(tf(n)) есептелетін алгоритмдерді экспоненциалдық
алгоритмдер деп атайды, мұндағы t – ... ... ... ... ал f(n) ... бір ... функция. Күрделілігі О(сf(n)) есептелетін
экспоненциалдық алгоритмдердің жиынын ... деп ... с – ... ... ал f(n) ... қарағанда тездетіп өсетін,
бірақ сызықтыдан баяу болатын функция.
3-кесте. 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 болса, онда олар әлсіз детерминацияланған
әлсіз алгоритмдермен бұзылады.
Келесі болып күрделілік иерархиясында PSPACE ... ... ... ... полиномиальды кеңістікте шешілуі мүмкін және
полиномиальды ... ... ... міндетті емес болып келеді. PSPACE өзіне
NP –ны қосады, бірақ PSPACE мәселелері NP-ға қарағанда аса ... ... әлі ... ... қатар, PSPACE-толық деп аталатын келесі
қасиетке ие ... ... бар: егер ... ... ... болса,
онда PSPACE = NP, және егер олардың кез-келгені Р-мәселе болса, ... = P ... ... ... бар. Бұл мәселелер экспоненциалды уақытта
шешіледі. EXPTIME-толық мәселелер расында да ... ... ... ... ... ... мүмкін.
Сонымен қатар, Р EXPTIME-ге тең болмайтындығы дәлелденген.
2.2 ... ... ... ... барлығымызға мектеп кезінен мәлім. Оны кейде
«арифметикалық сағат» деп те атаған. Егер Милдред әкесіне үйде 10:00 ... ... 13 ... ... қалса, онда үйіне ол қашан келеді және неше
жылға әкесі оны жүргізуші ... ... Бұл ... 12 ... ... үш 12 ... ... 11 болады.
(10+13) mod 12 = 23 mod 12 = 11 mod 12
Бұны басқаша 23 пен 11 ... ... 12 ... ... =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 ... mod n=((а mod n)-(b mod n)) ) mod ... mod n=(( а mod n)*(b mod n)) ) mod ... mod ... mod ... mod n)) mod ... n есептеу әдетте криптографияда көп қолданылады, себебі дискретті
логарифмдер мен mod n квадраттық ... ... оңай емес ... болуы
мүмкін. Есептен шығару арифметикасы компьютерлерде оңай жүзеге асады,
себебі ол аралық ... мен ... ... ... n ... к-битті
есептеулеріне кез-келген қосу, алу, көбейтудің аралық нәтижелері 2 к ... ... ... ... ... ... келтіру үшін
үлкен аралық нәтижелерді қолданбай орындауға ... ... ... ... ... модулі бойынша есептеу көбейту мен бөлудің тізбегі
болады, алайда оларды тездететін тәсілдер бар:
ах mod ... ... бірі ... бойынша көбейтулер санын ... ...... ... жеке ... қолдану. Операциялар
дистрибутивті болғандықтан, дәрежеге келтіруді тізбекті көбейтулер ағынын
әр ретте олардың нәтижелерін ала ... тез ... ... ... ... ... бірақ ол тек 200-биттік сандарды көбейткен
кезде білінеді.
Мысалы, егер сіз а8 mod n есептегіңіз ... оны 7 рет ... 1 ... ... келтірудің қажеті жоқ:
(а*а*а*а*а*а*а) mod n
Оның орнына 3 кіші көбейтулер мен 3 кіші модульге келтіруді орындаңыз:
((а2 mod n)2 mod n2) mod ... ... mod n =(((а2 mod n)2 mod n)2 mod n)2 mod ... есептеу, мұнда х 2-нің дәрежесі болмайды, аса қиын ... ... х-ті 2:25 ... ... ... ... бұл ... 11001,
сондықтан 25=24+23+20. Сондықтан
a25 mod n=(а*а24) mod n=(а*а8*а16) ) mod ... ... ) mod ... нәтижелерді ойластырылған сақтаумен енді тек 6 есептеу қажет:
(((((((а2mod n)*а) 2mod n) 2 mod n) 2 mod n) 2 mod n) 2*а) mod ... әдіс қосу ... ... ... ... пен ... әдісі деп
аталады. Ол негізінде санның екілік көрінісі жататын қосудың жай және айқын
тізбегін қолданады.
Модуль ... кері ... мән ... не ... естеріңізде ме? 4-1/4 үшін кері мән,
себебі 4*1/4=1. ... ... ... күрделенеді: 4*х=1(mod 7)
Бұл теңдеу х пен к анықталуына эквивалентті, 4х=7 к+1
Мұнда, х пен к –бүтін ... ... есеп ... х-ті ... ол
1=(а*х) mod ... ... да ... болады:
а-1=х(mod ... ... кері ... есептеу оңай емес. Кейде оның ... ... ... ... 5 ... модулі бойынша кері мәні ... ... 3-ке тең. ... жағынан 2 санында 14 модулі бойынша ... ... ... (7) ... а мен n ... жай болса, тек қана 1
шешімі болады. Егер а мен n ... жай ... онда (7) ... ... Егер n жай сан ... онда 1-ден (n -1)-ге ... ... сан n-мен сыбайлас жай болады және n модулі бойынша дәл сондай кері
мәнге ие болады.
Эйлер функциясы
Кері мәнді есептеудің басқа да ... бар, ... оны әр ... қолдана
беруге болмайды. mod n берілген қалдықтар жиынтығы деп қалдықтардың толық
жиынын жиын ... және оның ... n-мен ... жай ... ... ... ... қалдықтар жиыны –{1,5,7,11}. Егер n –жай сан ... mod n-нің ... ... ... бұл- 1-ден n-1-ге ... ... 1-ге тең емес ... сан үшін 0 саны ешқашан берілген
қалдықтар жиынының құрамына кірмейді.
Эйлер функциясын φ(n) түрінде жазады, - бұл n ... ... ... ... ... саны. Басқаша айтқанда, φ(n)- n-нен ... ... ... жай сан ... ... оң ... ... n-жай сан болса, онда
φ(n) = ... ... ... ... ... ... р мен q-жай ... болса, онда
φ(n) ... Бұл ... ... алгоритмдерде ашық кілтпен келеді. Бұның
себебі мынада: Эйлер теоремасы мен ... кіші ... ... егер ... n )=1 ... ... φ(n) mod ... а-1 mod n есептеу қиын емес:
х=а φ(n)-1 mod ... ... сан 7 ... бойынша 5 санына кері мәнге ие болады? 7
жай сан болғандықтан, φ(7) ... 5 ... 7 ... ... кері мән ... тең болады:
56-1 mod 7=55 mod 7=3.
Бұл кері мәндерді есептеу тәсілін х мәнін ... ... ... ... mod n= ... ... ... ... ... ... (b* а φ(n)-1) mod ... алгоритмін қолдана отырып, мынаны табамыз:
х= (b* (а-1 mod n)) mod ... ... кері ... ... есептегенде Эвклид алгоритмі
Эйлердің жалпыламасына қарағанда тезірек, әсіресе 500 битті сандар үшін.
Егер ЕҮОБ(а, n )≠1 ... да ... ... ... Бұл жағдайда (а*х) mod
n= b, не ... ... не ... ... ... символы
Лежандр символы L(а,р) егер а – кез келген бүтін сан болса, ал ... жай сан ... ... болады. Ол 0,1 немесе -1-ге тең болады.
L (а, р) =0, егер а р-ға бөлінсе.
L (а, р) =1, егер а –р ... ... ... ... алу ... (а, р) =-1, егер а –р модулі бойынша ... ... алу ... (а, р) = ... mod ... ... ... ... ... Егер а=1 болса, онда L(а,р) =1
2) Егер а жұп болса, онда L(а,р) = L(а/2,р)*(-1)(у2-1)/8
3) Егер а жұп болмаса, онда L(а,р) = L(р mod ... ... ... ... – оның жай ... табу ... жіктеу сандар теориясының ең көне мәселесі ... Бұл ... қиын ... тек уақыт талап етеді. Қазіргі таңда ең
күшті алгоритм болып мынау табылады:
Сандардың сандық ... торы – бұл 110 және одан да көп ... үшін ... ... ... табылады. Алғашқыда ол пайдалы болған жоқ, алайда соңғы
жылдары ол жақсартылған. Ол ... ... өте тез ... ... ... жаңа, алайда жақын арада барлығы өзгереді.
Квадраттық тор – бұл 110 ... ... кіші ... ... ең тез әдіс. Бұл әдістің жаңартылған нұсқасы полиномиальды
квадраттық тор болып табылады. Ең тез ... ... ... ... санды екілік вариациялау әдісі болып табылады.
Эллипстік қисық әдісі – 43 бөлікті көбейтінділерді жіктеуде қолданылды.
Монте-Карло Поллард әдісі; Үзіліссіз ... ... – бұл ... ... сай ... санау жүйесі
Екілік санау жүйесі математиктер мен философтармен компьютерлер шықпас
бұрын (XVII — XIX вв.) ... ... ... ... Лейбниц: "Екілер
арқылы санау... ғылым үшін ең негізгі болып саналады ... ,-деп ... ... ... ... ... 0 мен 1 ... , әр жерде тамаша
тәртіп пайда болады". Кейін Екілік санау ... ... тек 1936 — ... ... ... және ... Клод Шеннон екілік санау
жүйесінің конструирленген электрондық схемалар үшін ... ... ... ...... 2 ... санау жүйесі. 0 мен 1 сандары
қолданылады. Екілік санау ... ... ... қолданылады, себебі
әлдеқайда ыңғайлы және барлық талаптарға сай:
- Жүйеде мәндер қаншалықты аз болса, ... жеке ... ... ... күй элементі аз болған сайын, оның кедергіге шыдамдылығы
жоғары болады және ол соншалықты тез ... ... мен ... ... кестесінің қарапайымдылығы-сандарға
қолданылатын қарапайым амал
2.3 Жай сандар генерациясы
Жай сан деп – ... ... және тек ... ... ғана бөлінетін бүтін
сан: ол басқа ешқандай санға бөліне алмайды. Екі - жай сан. Жай сан ... 2521, ... және ... бола ... Жай ... ... ... бар. Ашық кілтті криптография көбінесе үлкен жай ... ... бит және одан да ... ... бар алгоритмдер үшін жай сандар қажет. Олардың біршама үлкен
желісі үшін ... ... ... Генерация математикасына көшпес ... ... ... ... ... ... ... жай саны керек болса, қор таусылмайды ма? Жоқ.
Шын мәнінде 1-ден 512 битке дейінгі 10151 сан бар. n-ге ... ... ... ... сан жай болу ... 1/ln n болады. Сондықтан,
жай сандардың n –нен кіші ... саны n/( ln n) ... ... барлығы 1077
атом бар. Егер ғаламшардағы барлық ... үшін әр ... ... сан ... болса, онда жай сандардың тек 10109 керек болар еді,
сонда жай сандардың 10151 қалар ... екі адам ... жай ... ... таңдаса? Ондай болмайды.10151
санды таңдағанда сәйкес келу ықтимаалдығы өте аз. Егер біреу барлық ... ... ... онда ол оны ашық кілті бар ... ... ала ма? Жоқ. Егер сіз 1 ... ... 1 ... салмағы бар
құрылғыда сақтасаңыз да, ... ... одан ... ... ... жіктеу сонша қиын болса, онда жай сандар генерациясы
қалайша оңай ... «n саны жай сан ба» ... ... ... беру ... қандай» деген сұраққа жауап беруге қарағанда әлдеқайда оңай.
Бөліндімен тексеру
Бұл көбейтінділерге ... ең көне ... ... әр жай санды
тексеруден,жіктелініп жатқан санның кіші немесе тең квадраттық түбірін
анықтаудан тұрады. Егер де ... бір ... ... ... тексеру
керек болса, қателік деңгейін төмендетуге болады.
Көбейтінділерге жіктеудің келесі әдісімен кездейсоқ сандар генерациясы-
бұл жай сандарды ... қате ... ... тексеру әдісінің
тексерілген бірнеше ... ... ... ... жоғары болса, бұл
тексеру әдісі ... ... ... ... ... жай сандарды
«өндірістік жай сандар» деп атайды: бұл сандар бақыланатын қате мүмкіндігі
бар сандар ... ... ... 1 ... ... деп ... Бұл дегеніміз, 1/1015
ықтималдығымен тексеріс құрама ... жай деп ... одан ... тест ... ... анықталды. Бұл р санының
тексеруіндегі амалдар тізбегі:
1) р –дан кіші кез-келген а санын таңдаңыз.
2) а(р-1)/2 mod р ... Егер ... ... -1(mod р) ... онда р жай сан ... Егер а(р-1)/2≡1 немесе -1(mod р) болса, онда р санының жай сан
болу ықтималдығы 50 пайыздан көп ... ... t рет ... Егер ... ... ықтималдығы 1
немесе -1 болса, бірақ әр уақытта 1 болмаса, онда р қателігі 1/2 t ... сан ... ... ... ... істеу принциптері
Оқиғаны сипаттаудың қалыпты мысалы, криптография есебі туындайтын 1-
суретте көрсетілген:
Негізгі принцип
1-сурет
А мен В 1-суретте – қорғалынған ... ... ... ... ... бірдей байланыс каналы арқылы алмасқысы келеді. П –
заңсыз тұтынушы (қарсылас, хакер), жіберілген ... ... ... ... ... жаңа ақпарат немесе мәлімет ... ... ... ... ... ... ... немесе шифрлеудің криптографиялық
әдістері қолданылатын әдеттегі оқиғаның моделі ретінде қарастыруға болады.
Тарихи тұрғыдан ... ... ... ... ... ... ... шабуыл). Олар криптографиялық түсініктердің ойын
нақты анықтайды. Оған қоса кең қолданылатын әскери ... ... ... ... ... Генералдық штаб коды, кодтық
кітаптар, кодтық белгілеулер және т.б.) ... ... ... ... кодтау теориясы қалыптасты. Байланыс каналында
кездейсоқ бұзылудан ақпаратты қорғау әдістерін ... және ... ... ... ... ... ... жатқан ақпаратты қарсылас қағып алмау
үшін ақпаратты түрлендірумен айналысады. ... ... ... арқылы
қорғалынатын ақпарат емес, ал оның шифр арқылы түрлену нәтижесі жіберіледі
және қарсылас үшін осы ... ... ... ... ... бұзу – шифрды
қолдану білімінсіз шифрленген ақпаратты қорғалынатын ... алу ... ... алу ғана емес, сонымен қатар оны өшіруге, ... Бұл – ... үшін ... ... ол ... алу ... ... ерекшеленеді. Мұндай қауіптен қорғану үшін спецификалық әдістер
қолданылады. Яғни, заңды тұтынушыдан басқасына ақпарат беру ... ... ... ... керек. Әртүрлі типтен ... ... ... ... ... ... туып ... Қарсылас ең әлсіз
бөлікті іздейді. Бұдан келесі ереже шығады: бір бөлігін өте мықты қылудың
маңызы жоқ, егер бір ... ... ... ... шифр ... табу оңай ... ... Сондықтан жақсы шифрдың
өміршеңдігін ұзартып, оны көп ақпаратты ... үшін ... ... ... ... анықтап қойды деген қауіп туады, бұл жағдайда ауыстырылатын
кілт болады, сондықтан ... әрі ... ... оқи ... және шифр
ашу үшін жасаған амалдары нәтижесіз болады.
3.1 Криптографиялық кілттерді басқару
Криптографияда кілт ұғымы астарында ... ... ... ол тек ... бір ... ... қолданылады. Соңғы уақытта
қорғалынатын ақпараттың қауіпсіздігі кілтпен анықталады. Шифрмашина немесе
шифрлеу ... ... ... шифр белгілі деп санай бастады және
алдын-ала зерттеуге болатын, ... ... ... тек ... байланысты кілт пайда болды. Енді заңды тұтынушылар шифрлік
хабарламалармен ... ... ... құпиялы түрде кілттерімен алмасу
керек немесе байланыстың екі жағында бірдей кілт орнату керек. Ал ... жаңа ... ... – кілтті анықтау, тек содан кейін кілтте шифрленген
ақпаратты оңай ашуға болады.
Криптографияның негізгі ... ... ... ... ... ... ... енгізу керек – қарсылас үшін мүмкін емес болатын
кілт алмасу үшін құпия ... ... ... ... ... каналын жасау өте оңай және оның ақпарат жүктемесі
күрделі емес. Барлық ... үшін ... ... шифр болмайтындығын
атап өту керек. ... ... ... ... ерекшелігіне, оның
құндылығы мен ... ... ... үшін ... ... Ең ... қорғалынатын ақпараттың көптүрлілігін атап өтейік:
құжаттық, телефондық, теледидарлық, компьютерлік. ... әр ... ... ... бар және бұл ... ... шифрлеу
әдісіне зор әсерін тигізеді. Үлкен рөлді көлемі мен шифрленген ... ... ... Шифр ... ... және оның параметрлерін
орнату қорғалынатын құпия мен сектор түріне байланысты. Кейбір құпиялар (
мысалы, әскери, ... он ... ... ... ал ... биржалық) бірнеше сағаттан соң жариялануы мүмкін. Сонымен қатар,
ақпарат қорғалынатын қарсыластың мүмкіндігіне де байланысты. Бір ... ... ... ... ... ... ... ал екіншісі, қуатты
мемлекеттік құрылымға қарсы тұру.
Кез ... ... ... криптографиялық жүйе криптографиялық
кілттерді пайдалануға ... Ол ... ... бойынша жұмыс
жасайды: шифрлеудің бір ... ... ... осы ... ... кілттер; кілттерді басқару жүйелері; шифрленбеген
мәтін; шифрлік мәтін.
3.2 Симметриялық (құпиялы) әдістемелер мен алгоритмдер
Бұл әдістемеде шифрлеу үшін де, оның ... ... да ... ... ... да бірдей кілт қолдану керек. Егер кілт ... ... шифр ... автоматты түрде хабар жіберушінің аутентификациясы жүреді,
себебі, тек хабар жіберушінің өзі ғана кілтке ие, тек ... ... ... ... кілтті біледі. Хабар жіберуші мен алушы –симметриялық кілтті
білетін жалғыз адамдар. Мәселе, тек осы ... ... ... ... ... алгоритмдері ондай қатты ұзақ емес ... және көп ... ... тез ... алады. Симметриялық
кілттерді пайдалану реті:
1) Симметриялық құпия кілт ... ... ... ... ... Хабар жіберуші мәтін үшін хэш-функциясын есептеу арқылы электрондық
қолтаңба жасайды және алынған қатарды мәтінге тіркейді.
3) ... ... ... ... ... ... ... мәтінді алу үшін алынған пакетке симметриялық
құпия кілтін тіркеу арқылы шифрды бұзу тәсілін анықтайды. Осы
тәсілмен ... ... ... ... ... симметриялық
құпия кілтін біледі және бұл пакет шифрын бұза алады.
4) Хабар жіберуші ғана шифрленген мәтінді біледі. ... ... ... ... ... ... ... таратылмайды.
5) Хабар алушы дәл сол симметриялық құпия кілт алгоритмін пайдаланады.
Оның ... ... ... ... ... білетін адамды
аутентификациялайды.
6) Хабар алушы электрондық қолтаңбаны мәтіннен бөледі.
7) Хабар алушы басқа ... ... ... ... үшін ... ... ... жүргізеді.
8) Хабар алушы осы екі электрондық қолтаңбаны салыстырады, салыстыру
үшін хабарламаның бүтіндігін тексереді.
Қазіргі таңда симметриялық әдістемеде қолданылатын құралдар:
- Kerberos, ... ... қол ... ... ... Ол ... мәліметтер базасын пайдаланады, мұнда барлық
тұтынушылардың құпия кілттерінің көшірмесі болады.
- Банкомат ... (ATM Banking ... Бұл ... банк ... және ... ... ... болып табылады. Мұнда да
симметриялық құпия кілттер әдістемесі қолданылады.
1-кесте. Симметриялық алгоритмдер сипаттамасы
|Типі ... ... (Data ... ... ... ... үкіметімен |
|Standard) ... ... ... 64 ... ... |
| ... ... ... кілт ... (тек 56 |
| |бит ... 16 ... 4 кезеңде жұмыс істейді: |
| |• ... ... ... ... Code |
| |Book ) - ... DES, екі әртүрлі алгоритм |
| ... |
| |• ... ... ... Block ... |
| ... шифрлеу оның алдындағы блокты шифрлеу |
| ... ... |
| |• Шығу ... кері ... ... |
| ... ... ... ... ... |
| ... |
| |• ... ... кері ... ... |
| ... ... ... |
| ... үшін ... ... ... үштік |64-биттік блоктық шифратор, DES-ті 3 рет үш |
|DES ... ... ... ... ... |
| ... ... ... 3-DES ... ... DES, оған кері байланыс |
| ... ... OFB ... CFB |
| ... шабуылдарға төзімді. ... ... ... ... DES ... ... |
|жылдам алгоритмдері)|қолданылады. |
| ... ... жаңа ... ... жатыр. |
|IDEA (халықаралық |64-биттік блоктық шифратор, 128-тік кілт, 8 |
|Шифрлеу алгоритмдері)|өтілім |
| ... ... ... ... деп ... |
| ... толық тексерісті өткен жоқ. ... ... АҚШ ... жобалары барысында |
| ... и ... ... |
| |Осы ... ... құпиялы болды. 64-биттік |
| ... ... ... ... ECB, CFB, |
| |OFB ... CBC режимдерінде қолданылады, 32 |
| ... ... ... блоктық шифратор, айнымалы өлшем |
| ... DES-ке ... екі есе ... ... |
| |DES ... ... ... шифрлеу қосылу|
| ... ... ... Data Security ... |
| ... ... алгоритм ... ... ... ... ... шифр, байт-ориентирлік, айнымалы өлшемді |
| ... ... ... екі есе ... |
| ... |
| |RSA Data Security ... ... ... |
| ... ... |32, 64 или 128 ... блок ... 0-ден 2048 |
| ... ... ... болады, 0-ден 255-ке дейін |
| ... ... RSA Data Security ... ететін |
| ... ... ... ... шифратор, 40 - 64 битті |
| ... 8 ... ... |
| ... ... басқа бұзу әдістері белгісіз. |
|Blowfish ... ... ... 448 ... ... |
| |16 ... болады, әр өтілімде ауыстырулар |
| ... ол ... және ... ... |
| |DES ... ... ... үшін |
| ... ... қолданысқа |Бұзуға болмайтын шифратор.Кілті болып ... ... ... осы ... ... массивтен |
|құрылғылар ... 'n' ... ... ... ... |
| ... алушыда бірдей кілт болады.Қолданыстан |
| ... ... ... және ... ... биттер|
| ... ... ... ... ... ... алгоритмдері, |
| ... ... ... ... ... |
| ... ... жарайтын кілттердің |
| ... ... ... ... қауіпсіздікті |
| ... ете ... ... Асимметриялық (ашық) әдістемелер мен алгоритмдер
Бұл әдістемеде кілттер бір уақытта жасалынғанмен, олардың шифрлары мен
оларды бұзатын ... ... ... Бір кілт бәріне белгілі болып
жасалынады, ... ... ... ... ... тек ... кілттің
шифрын бұзу арқылы белгілі болады.
Барлық асимметриялық криптожүйелер кілттердің тікелей ... ... ... ... ... ... бұларда
әлдеқайда ұзақ кілттер қолданылу керек. Бұл ... ... ... ... ресурстарында білінеді, эллипстік қисық
алгоритмдерінде ... бұл ... ... ... ... ... төмен жылдамдықтан құтылу үшін әр
хабарлама үшін уақытша симметриялық кілт генерацияланады және тек қана ... ... ... Хабарламаның өзі уақытша кілтпен
шифрленеді. Содан кейін бұл кілт ... ... ... кілтінің
көмегімен шифрленеді. Осыдан кейін шифрленген сеанстық кілт шифрленген
хабарламамен хабар ... ... ... ... асимметриялық
шифрлеудің дәл сол алгоритмін және сеанстық кілт шифрын бұзу үшін өзінің
құпия кілтін пайдаланады, ... ... кілт ... ... ... ... криптожүйелерде сеанстық кілт пен асимметриялық ... ... ... ... болу ... Егер ... ... кілт
(мысалы, 40-биттік DES) қолданса, онда асимметриялық кілттер қанша ақпарат
жинақтай алатындығын айтудың қажеті де жоқ. ... ашық ... ... ... ... оның ... ... алмастыру қиын
болғандықтан. Егер шабуылдаушы құпиялыасимметриялық ... ... ... ғана ... сонымен бірге одан әрі қарай ... ... ... пайдалану реті:
1) Асимметриялық ашық және құпия кілттер қауіпсіз жасалынады. Құпия
асимметриялық кілттер оның ... ... ... кілт
мәілметтер базасында сақталынады және сертификат беру орталығымен
әкімшілденеді.Тұтынушылар мұндай базада кілттерді ... ... ... ... ... болу керек. Кілтті
жасаушы оларды жойып жібергендігі ... ... ... ... ... жіберуші мәтін үшін хэш-функциясын есептеу арқылы электрондық
қолтаңба жасайды және алынған қатарды мәтінге ... ... ... ... ... ... алгоритмдерін
қолданады- шифрленген мәтінді алу үшін алынған пакетке симметриялық
құпия кілтін тіркеу арқылы шифрды бұзу тәсілін ... ... ... жүреді, себебі хабар жіберуші симметриялық
құпия кілтін біледі және бұл пакет шифрын бұза алады.
4) Енді сеанстық кілтті тарату мәселесін шешу ... ... ... ... ... ... ашық ... алу керек.Шифрленбеген сұранысты қағып алу шабуылдың ең кең
тараған түрі болып саналады. ... ... ... ... болады.
6) Хабар жіберуші запрашивает сертификат орталығынан асимметриялық
ашық кілтті хабар алушыға сұратады.Бұл процесс ... ... ... ... ... ... ... Сондықтан ашық
асимметриялық кілтке сертификат орталығында хабар жіберушімен қол
қойылынады. Бұл ... ... ... ... ... асимметриялық ашық кілтін пайдаланды ... сөз. ... ... ... ... туралы мәлімет болады.
7) Хабар алынған соң асимметриялық ашық кілт асимметриялық ... ... ... Егер ол компрометирленген болса, онда ол
қалыптан барлық тұтынушылар жүйесін ... ... ... ашық ... ... ... тастауға болады, бірақ
ол компрометирленген дегенге сенім қайда?
8) Енді асимметриялық ... ... ... сеанстық кілтті және
хабар алушының асимметриялық кілтін ... ... ... және
оны бұзу орындалады.
9) Ашифрленген сеанстық кілт шифрленген мәтінге ... ... ... ... ... ... алушыға жіберіледі.
Шифрленген сеанстық кілт қорғалмаған тор арқылы жіберілгендіктен,
әртүрлі шабуылдар үшін қолайлы болады.
11) ... ... ... сеанстық кілтті алынған пакетті бөліп алады.
12) Енді хабар алушыға сеанстық кілттің шифрын ... ... ... ... ... беру орталығының асимметриялық болу
керек.
14) Өзінің асимметриялық құпия ... ... ... ... ... ... ашады.
15) Хабар алушы дәл сол шифрлеу-шифрды бұзудың симметриялық алгоритмін
қолданады және ... ... кілт ... ... ... ... мен ... қолтаңбаны алады.
16) Хабар алушы электронды қолтаңбаны бастапқы мәтіннен бөледі.
17) ... ... ... беру ... хабар жіберушінің
асимметриялық ашық кілтін алады.
18) Бұл кілт ... соң, ... ... оның ... ... ... кейін мәтіннің хэш-функциясының шифры хабар жіберушінің ашық
кілтімен және ... ... ... ... ... ... ... бастапқы мәтіннің хэш-функциясы қайта тексеріледі.
21) Осы екі хэш-функциялар бастапқы мәтін өзгеріске ұшырамас ... ... ... криптожүйелерде
симметриялық сеанстық кілттерді шифрлеу үшін қолданылады.
Екі әртүрлі кілт қолданылады – біріншісі барлығына белгілі, екіншісі
құпияда ... ... бір ... ... ... тек ... кілттің
шифрын анықтаған соң ашуға болады.
2-кесте. Асимметриялық алгоритмдер сипаттамасы
|Тип ... ... ... ... кең ... |
| ... ... ... ... |
| ... күрделілігіне байланысты. |
|ECC(эллипстік ... ... ... ... ... негізделген|нүктесінде сипатталады, қызметке келтіру үшін |
|криптограмма) ... ... ... |
| ... ... шифрлеу |
| ... ... ... саналады, |
| ... ... ... шифрлар үлкен ақпаратты |
| ... зор рөл ... Оның ... |
| ... ашық ... ... |
| ... ... ... ... |
| ... Оның ... RSA, ... |
| ... DSA-ға ... бір ... ... ... ... нұсқасы, электрондық қолтаңбаны |
| ... үшін де ... |
4 АШЫҚ ... ... ... ... ... криптография тұжырымын Уитфилд Диффи және Мартин
Хеллман, сондай-ақ Ральф Меркл ұсынған болатын. ... ... ... – кілтті жұбымен қолану – шифрлеу кілті және дешифрлеу
кілті – және ... ... алу ... ... ... Ең ... ... Диффи және Хеллман өз ойын Ұлттық компьютерлік конференциясында
(National Computer Confrens) көрсетіп, ... ... ... ... негізі болатын “New Directions in Cryptography” ... ... ... ... ... ... ашық кілтті қолданатын криптографиялық
алгоритмдер ұсынылған. Олардың көбі қауіпсіз емес. Ал қауіпсіз дегендердің
көбі жүзеге асыруға ... ... ... өнімді, әрі қауіпсіз болып келетін алгоритмдер көп ... ... ... ... қиын ... ... Осы әрі қауіпсіз,
әрі ... ... ... ... бөлуге ғана жарамды.
Басқалары шифрлеуге және кілттерді бөлуге де жарамды. Үшіншілері тек цифрлі
жазуға ғана ... ... ... Тек қана үш ... ... ... де,
шифрлеуге де, цифрлі жазуға да жарамды: RSA, ELGamal және Rabin. ... ... ... Олар ... алгоритмге қарағанда
шифрлеуді де, дешифрлеуді де баяу ... ... ... жылдамдығы үлкен
мәліметтер көлемін шифрлеуге аз ... ... ... жылдамдатуға мүмкіндік береді:
хабарламаны шифрлеуде ... ... ... ... ... ашық ... қолданатын алгоритм кездейсоқ сеансты кілтті шифрлеуге
қолданылады.
4.1 Ашық кілтті қолданатын алгоритмдердің қауіпсіздігі
Криптоаналитиканың ашық ... ... ... ... ... кез-келген хабарламаны алуына мүмкіндік береді. ... ... Р ... оны оңай ... ... ... ... мүмкіндік беретін, ашылған мәтіннің мүмкін саны сонша аз
болса, бұл күрделі мәселе болып табылады, бірақ бұл ... ... ... ... толтыра оңай шешуге болады. Бұл біртекті ашық
мәтіндерге әр түрлі шифромәтіндер сәйкес келуіне әкеледі.
Егер ашық ... ... ... ... кілтті шифрлеу үшін
қолданылса әсіресе маңызды болады. Ева Бобаның ашық кілтпен ... ... ... ... мүмкін мәліметтер базасын жасай алады.
Әрине, бұл көп уақыт пен жады орнын алады, ... ... ... ... ... ... кілт DES-тегі күшпен бұзу қайда қалай көп ... ... ... ... етеді. Ева осындай мәліметтер базасын жасай
салысымен Бобтың кілтін алып, оның ... оқи ... Ашық ... ... ... ашық ... ... қарсы тұра алатындай
құрылған. Оның қауіпсіздігі құпия кілтті ашық ... алу ... ... сол ... ашық мәтінді шифромәтін бойынша ... да ... Егер ... мен ... бірдей кілттер
қолданса, жүйеде шифрлеумен өңделген операциялар цифрлік жазбаға үшін бұл
ашуды болдырмау мүмкін емес. Сондықтан ... ... ғана ... ... ... көру қажет.
4.2 Қол қапшық алгоритмі
Ашық кілтті қолданатын шифрлеуді тарату үшін ең алғашқы алгоритм Ральф
Меркл мен ... ... ... қол ... алгоритмі болды. Ол тек шифрлеу
үшін ғана қолданылатын, бірақ кейіннен Ади Шамир цифрлі жазбаға бейімдеді.
Қол қапшық алгоритмінің ... қол ... ... – NP толық
мәселесіне сүйенеді. Бірақ кейіннен оның қауіпсіз еместігі белгілі ... NP ... ... ашық ... қолданатынті криптографияда қолдану
мүмкіншілігін көрсетті.
Қол қапшық мәселесі қиын емес. Әр түрлі салмақта көп ... ... қол ... ... белгілі бір мәнге ие болатындай етіп, ... қол ... ... ... ма? ... түрде, М1,М2…Мn және
қосындысы S, bi мәнін есепте, егер
(17)
bi ноль ... бір ғана бола ... Бір қол ... затты салады
дегенді білдіреді, ал ноль салмайды ... ... ... ... ... және 20 деген мәндерге ие болсын. Сіз қол қапшыққа ... 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 ... ... 156 11 14 20 156 11 14 20 156 11 14 20 156 ... ... ... 5+11+14=30 ... қол ... екі ... мәселесі бар: бірін сызықтық уақыт
ішінде шешіледі, ал ... – жоқ. Оңай ... ... болады. Ашық
кілт шифрлеуге оңай қолдануға болатын қиын мәселені көрсетеді, бірақ хатты
дешифрлеуге ... ... кілт ... ... оңай ... ... мәселе болып табылады.
Күрт өсетін қол қапшықтар
Қол қапшықтың оңай мәселесі деген не? Салмақ тізімі күрт өсетін ... ... қол ... ... оңай ... ... Күрт ... бұл әр мүшесі алдыңғы мүшелерінің қосындысынан үлкен болатын қатар.
Мысалға, {1,3,6,13,27,52} қатар күрт ... ал ... ... ... өсетін қол қапшықтың шешімін табу ... ... ... ... ең ... ... салыстыр. Егер толық салмақ алынған саннан кіші
болса, оны қол қапшыққа салмаймыз. Егер толық ... ... ... ... ... онда қол ... саламыз. Қол қапшық салмағын осы санға
кемітіп, қатардың үлкендігі бойынша келесі ... ... Бұл ... ... Егер ... ... ... теңессе, онда шешімі
табылғаны. Қарсы жағдайда, there isn’t.
Мысалға, қол ... ... ... – 70, салмақ қатары
{1,3,6,13,27,52}. Ең үлкен салмақ 52, 70 кем, ... қол ... ... 52 ... ... ... ... 27, –ден үлкен,
сондықтан 27 қол қапшыққа салмаймыз. салмағы –ден кіші, сондықан
қол қапшыққа ... ... –ті ... ... Келесі
салмағы –тен үлкен, сондықтан қол қапшыққа –ны ... ... ... де, те қол ... салынады. Қол
қапшықтың толық ... –ге ... бұл ... ... өспейтін немесе қалыпты қол қапшықтар қиын мәселені көрсетеді,
олар үшін тез алгоритм табылмады. Қол ... ... зат салу ... бір ... ... шешіміне кездескенше, мүмкін болатын шешімдерді
методикалық тексеру арқылы анықтауға болады. Қатарға тағы бір мүше ... ... ... екі есе қиындайды. Бұл қатарға бір зат қоссаң шешімін
табу бір операцияға өсетін күрт өсетін қол ... ... ... ... ... осы қасиетке негізделген. Жабық кілт күрт өсетін қол
қапшық салмақ ... ... ... ... Ашық кілт – ... ... қол ... салмақ қатарының мәселесі. Меркл мен
Хеллман модульдік ариметиканы қолдану ... күрт ... қол ... ... қол ... мәселесіне айналдырды.
Жабық кілтті қолдану арқылы ашық кілтті құру
Алгоритм жұмысын сандар ... ... ... ... ... тізбегін алу үшін, қол қапшықтың күрделі ... ... ... ... m модульі бойынша барлық мәндерін n
санына ... ... мәні ... ... ... ... ... керек, мысалға 105. Көбейтінді модульмен өзара жәй сан ... ... 31. Қол ... ... ... ... ... mod 105=62
3*31 mod 105=93
6*31 mod 105=81
13*31 mod 105=88
27*31 mod 105=102
52*31 mod 105=37
Қорытынды – {62,93,81,88,102,37}
Қол қапшықтың күрделі өсу ... ... кілт ... ... ал ... қол ... - ашық.
Шифрлеу
Хатты шифрлеу үшін ең алдымен элемент сандары бір ұзындықта болатын,
қол қапшық ретімен ... ... ... ... ... ... мүшенің
бар болуын, ал ноль жоқ болуын көрсетеді деп саналады.
Мысалға, егер хат бинарлы түрде ... ... ... қол ... ... шифрлеуді келесідегідей көрсетеді:
Хат =011000110101101110
011000 сәйкес 93+81=174
110101 сәйкес 62+93+88+37=280
101110 сәйкес 62+81+88+102=333
Шифромәтінде 174, 280, 333 реті болады.
Дешифрлеу
Берілген ... ... ... ... кілтті біледі: түпкі күрделі өсетін
ретті, сонымен қатар қол қапшықтың дұрыс ретке ... үшін ... және m ... ... ... дешифрлеу үшін алдымен (mod m)
болатындай n-1 ... ... ... әр бір мәні n-1 mod ... ... кейін ашық мәтіннің мәнін алу үшін ... ... ... ... мысалды күрделі өсу реті {2,3,6,13,27,52}, m 105
тең, ал n 31 тең. Шифромәтін 174, 280, 333. Бұл ... n-1 61 ... ... 61 mod 105 ... ... ... 110101
сәйкес 101110
Шифрленген ашық мәтін 011000, 110101, 101110 болып табылады.
Практикалық іске асыру
Қатар күрт өсетін болмаған жағдайда да, алты ... ... қол ... ... шешу қиын емес. Ақиқат қол қапшықтар кем дегенде
250 элементтен тұруы қажет. Күрт өсетін қатардың әрбір ... ... 200 бен 400 ... ал ... ... 100 бен 200 бит ... ... іске асыруда бұндай мәндерді алу үшін ... ... ... қол ... ... ашу ... ... болып табылады. Егер
компьютер секундына миллион нұсқаны ... ... ... қол ... ... ... үшін жыл қажет болар еді. Миллион машиналар
бір уақытта жұмыс істеген уақытта жұмыс істессе де көп ... ... ... ... қауіпсіздігі
Қол қапшық мәселесіне негізделген криптожүйені миллион машина емес, жұп
криптограф қана ... ... ашық ... ... биті ... еді. ... Шамир белгілі бір жағдайда қол қапшықты бұзуға болатынын көрсетті.
Басқа да жетістіктер болған, бірақ жалпы ... ... ... бұза ... еді. ... ... мен Циппел күрт өсетін қатар қол
қапшықты қалыптыға өзгертуді қалпына келтіру үшін өзгерістің әлссіз ... ... ... ... ашылуынан кейін қол қапшық негізінде көптеген
жүйелер ұсынылған еді: бір неше ... қол ... Грэм ... ... және т.б. ... барлығы талдау жасалып, бір ... ... ... алгоритмдерді қолданатын басқа идеялар ұсынылған, бірақ олар да
бұзылған еді. Pieprzyk критожүйесі ... ... ... ... модульдік қол қапшыққа негізделген. Кейін ол да бұзылған.
Қол қапшықтың нұсқалары ... ... ... ... ... қол қапшық алгоритмі, «арнайы ашуға» қарамастан, қажетті ... оның ... ... ... System нұсқасы қауіпсіз емес.
4.3 RSA алгоритмі
Евклид пен Диофант, Ферма, Эйлер, Гаусс, Чебышев пен Эрмит еңбектерінде
диофантты теңдеулерді шешу жөнінде маңызды ... ... сол ... ... ... ... сандардың ең жақын мәнін табу үшін амалдар бар. Соңғы
екі он жылдықта криптография мен ... кең ... ... дамуына орай сандар теориясының алгоритмдік сұрақтары ... ... ... мен ... ... адамның барлық қызметі
мен ой-өрісіне енді. Оларсыз қазіргі заманғы ... ... ... Мәтінді шифрлеу мен оны бұзуды ЭЕМ көмегімен ... ... ... ... ... бұл ... ... тәсілдер кейбір
функциялар секілді бүтін сандардың белгілі бір жиынында орындалады. ... ... ... криптографияда сандар теориясының болуына жағдай
жасайды. Сонымен қатар, ... ... ... тек ... –теориялық есептер күрделілігімен негізделеді. Бірақ ЭЕМ мүмкіндігі
шекті болып ... Ұзын ... ... ... бір өлшемді блоктарға
бөлуге тура келеді және әр ... ... ... тура ... Одан әрі ... ... ... теріс емес және берілген m санынан кіші емес
деп санаймыз.Мұндай шектеулер одан әрі ... ... ... ... Бұл осы ... ... ... мүмкіндік береді.
Шифрленетін функция есептеу сақинасының бір-біріне сыбайлас жүйе ретінде
қарастырылынады:
(18)
ал саны ... ... ... көрсетеді. Мұндай
түрдің қарапайым шифры – алмастыру шифры, ... сан үшін ... тән. ... ... Юлий ... де ... ... -тің
әрбір көрінісі ақпаратты сақтау үшін қолданылады.
1978-жылы американдық Р. ... А. ... және Л. ... ... ... ... ... ұсынды, олар ерекше
қасиеттерге ие. Соның негізінде нақты қолданылатын ... ... ... есімдерінің алғашқы аттарына сәйкес RSA деп аталды. Бұл функция
мынадай:
4) функциясының мәндерін есептейтін әлдеқайда жылдам әдіс бар;
5) кері ... ... ... жылдам әдіс бар;
6) функциясының «құпиясы» бар, егер оны ... ... тез ... болады; қарсы жағдайда есептеуге ауыр,
көп уақытты кетіретін, шешуге мүмкін емес есепке айналады.
Мерклдың қол қапшық ... ... көп ... алғашқы, нағыз,
шифрлеу және цифрлік жазбада қолдануға болатын: RSA ашық ... ... ... ... RSA осы ... ... ... ашық кілтті
қолданатын алгоритмдер ... ең оңай ... және ... ... ... ... Технологиялық институтында баспаға шықпас бұрын, RSA
жүйесіне арналған доклад көшірмесі белгілі ... ... ... ол ... ... American ... ... осы
жүйесіне қатысты мақала жариялады. Тақырыбын аударатын болсақ, ол шифрын
бұзу үшін ... ... ... болатын жаңа шифр дегенді ... осы ... ... ... белгілі болуына жағдай жасайды. Осы мақала
криптографияға маман еместердің назарын аударуға және осы облыстың дамуына
жағдай ... бұл ... 20 ... ... жаңалық.
4.4 RSA шифрлеу жүйесі
және натурал сандар болсын. RSA ... ... ... ... ... ... үшін ... теңдікті шешу жеткілікті
болып табылады:
.
(20)
Бұл теңдік және кейбір шарттарында ... ғана ... Бұл ... ... үшін және ... табу жолын түсіндіру
үшін бізге Эйлер функциясы деп ... бір ... ... ... Бұл функция натуралды аргументтің деп белгіленеді және
1- ден -ге дейінгі кесіндінің ... ... ... жәй санына
теңестіріледі. Кез келген жәй саны мен натуралсаны үшін ... тең ... ... ... кез ... және натурал
өзара жәй сандар үшін ... ... жәй ... ... ... бұл ... ... оңай есептеп табуға
мүмкіндік береді. Егер (2) салыстыруда көрсеткіш дәрежесі өзара
жәй болса, (20) салыстырудың ... ғана ... ... Оны табу ... шартты қанағаттандыратын бүтін санын анықтаймыз:
(21)
Бұндай сан бар, себебі және бұл жалғыз ғана. Бұл жерде арықарай
да символымен және ең ... ... ... белгіленеді.
Эйлердің классикалық теоремасы -мен өзара жәй әрбір саны үшін
салыстырымыорындалады және осыдан қорытынды:
(22)
Яғни, жорамалында (20) ... ... ... ... түрде
табылады:
.
(23)
Егер әр түрлі жәй көбейткіштерден тұратын деп ... ... онда (23) ... ... да ... Шынымен, және деп белгілейік. Онда -ге
бөлінеді, ал (20) салыстыруынан ... ... (22) ...
тез табамыз. Онымен қатар те бар. алынған салыстыруды ... ... ... ... (1) ... тез ... ... мүмкін.
кері функциясы , есептеудегі ережелермен ... ... ... . (19) ... шешу үшін бар жоғы ... білу ... Шифрлеу үшін осылар ашық кілтті құрайды.
Ал кері функцияны есептеу үшін ... білу ... Олар ... ... Бір ... ... табу қиын ... тек жай көбейткіштерге
жіктеп, мәні ... (21) ... ... ... ... Бұл ... барлық қадамдары жылдам ... ... ... ... санын көбейткіштерге жіктей ең үлкен мәселені ... ... ... ға ... жай ... таңдай отырып және
оларды ға бөлу арқылы болады. Бірақ жай сандар дегеніміздің саны ... Егер ... ... ... жай ... саны ... ... Дөрекі айтқанда секундына миллион бөлуді орындайтын
компьютердің өзінежіктеуін ... үшін жыл ... ... ... ... бар, ... оларда баяу жұмыс істейді.
RSA жүйесінің авторлары санын екі көбейткіштің жіктелуі и
ретінде алған, мөлшермен олардың үлкендігі ... ... ... ... кейін,
.
(25)
Яғни, RSA жүйесі арқылы шифрлейтін хат алысуда ... ... ... алынады. Олардың көбейтіндісі тең. Одан кейін
саны таңдалады, ол (25) шартын ... ... (24) ... және d саны (21) ... есептеледі. ... d ... ... ... ... және Адлеман өз әдісін мысал ретінде көрсету үшін ағылшын
сөйлемін осы әдіспен шифрлеген. Алдымен ... ... (а=01, b=02, ... пробел=00) бүтін сан түрінде жазылған болатын, содан кейін (1)
елестету көмегімен
m=114381625757888867669325779976146612010218296721242362562561842935
706935245733897830597123563958705058989075147599290026879543541 ... екі сан ... ... ... 64 және 65 ... ... жазылған, қосымша айтылған. Бұл ... ... ... ... адамға 100$ жүлде беруге ант етілген.
,
Бұл оқиға тек 17 жыл ... ... ... 1994 жылы D. Atkins, ... А. К. Lenstra және Р. С. Leyland сөйлемнің ... ... ғана ... және сандары тең болып шыққан.
,
Бұл керемет шешім алгоритмнің көбейткіштерге жіктелуінен пайда ... ... ... деп аталған. Есептеудің орындалуы ресурстарды қажет
етті.
RSA қауіпсіздігі үлкен ... ... ... ... Ашық және ... ... екі ... жәй сандардың (100-200
разрядты немесе оданда артық) функциялары болып ... ... ... ... ... ... ашық мәтінді қалпына келтіру екі үлкен сандар
көбейткіштеріне жіктеумен балама деп шамаланады.
(26)
Басқа сөзбен айтқанда,
(27)
d мен n ... жай ... ... айта ... және - ... ... ал саны - ... хатты шифрлеу үшін алдымен цифрлік блоктарға бөлінеді, кішісі
(екілік ... 2 ... ең ... ... таңдалады, кішісі ).
Яғни, егер және - 100 разрядты жәй сандар ... ... жуық ... және әр хат ... ... 200 ... жуық
болуға тиіс. Шифрленген хаты сол бұрынғы ... ... ... ... Шифрлеу формуласы келесідегідей:
(28)
Хатты расшифровка жасау үшін шифрленген блогының әр қайсысын
алып, есепте:
(29)
Бұл формула ... ... ... ... ... – p және q екі жәй ... туындысы (p және q ... ...... жай ... ... = e-1 mod ... сол сияқты хат d көмегімен шифрлене алады, ал кез келген таңдау е
көмегімен шифрлене алады.
Қысқаша мысал ... Егер p=47 және q=71 ... онда ... е ... ... ... керек.
(p-1)(q-1)=46*70=3220
-ні -ға тең деп алайық. Бұл жағдайда
Бұл санды ... ... ... ... ... ... сақтай e және n жариялаймыз. p және q мәндерін алып тастаймыз.
Хатты шифрлеу үшін
Алдымен оны ... ... ... ... ... үш ... ... Хат алты блогына бөлінеді.
Бірінші блок түрінде шифрленеді.
Келесі блоктарға да осындай операциялар орындалады, хаттың шифромәтіні
құрылады:
Дешифрлеу үшін ... ... ... ... ... тәрізді
дәрежеге шығару жасау керек.
Осыған ұқсас хаттың қалған бөлігі қалпына келеді.
4.5 RSA алгоритмінің жұмыс істеу жылдамдығы
RSA ... ... ... мен оны ... жасалу мен
тексеру үшін де көбейтулер қатары есебінде ... ... ... ашық ... қосымшалар үшін салыстырмалы түрде жоғары емес
көрсеткішті қолданады, көбінесе ... ... ... ашық ... Мұнда мәліметтерді шифрлеу шифрды бұзуға қарағанда, қолтаңбаны
тексеру қол қоюға қарағанда тез жүреді. Егер k – модульдегі ... ... онда RSA үшін ... ... ... орындау үшін
қолданылатын ашық кілтті пайдалану қадамы k ... ... ... болады, жеке кілттің қадам саны k-ның үшінші дәрежесіне, кілт
жасау үшін ... ... саны – k-ның ... дәрежесіне
пропорционал.
"Тез көбейту" әдістері – мысалы, Фурьені тез ... ... (FFT – Fast Fourier ... – аз ... санымен орындалады;
бағдарламалық қамтамсыздандыруының ... ... ... ... ... ... өлшемдерімен олар баяу жұмыс
істейді.Алайда RSA–ны қолданатын алгоритм құралдарының ... ... тез ... ... DES-ке және ... ... шифрларға қарағанда баяу. DES-
тің бағдарламалық қолданылуы аз ... 100 есе және 1,000 - ... ... Жүргізілініп жатқан істерге байланысты ... ... ... ... блоктық шифрлар жұмысы тездетіледі.
3-кесте. Биттік ашық кілтпен қолданатын әр түрлі модуль ұзындықтарына
арналған RSA жылдамдығы
| |512 бит |768 бит |1024 бит ... |0.03с |0.05с |0.08с ... |0.16с |0.48с |0.93с ... |0.16с |0.52с |0.97с ... |0.02с |0.07с |0.08с ... RSA қауіпсіздігі
RSA қауіпсіздігі толығымен үлкен сандарды көбейткіштерге ... ... ... ... бұл ... ... ... RSA қауіпсіздігі үлкен сандарды көбейткіштерге жіктеуге байланысты
деп айтылады. Математикалық тұрғыдан m бойынша c-ні және е-ні ... ... үшін n-ді ... ... керек екендігі әлі
дәлелденген емес. RSA криптоанализінің басқа әдісі ашылу ... ... бұл жаңа әдіс ... d-ні ... ... ... онда ол үлкен
сандарды көбейткіштерге жіктеуге мүмкіндік береді.
RSA-ны ( p-1)( q-1) мәндерін анықтау арқылы ... ... Бұл ... ... ... жіктеу әдісіне қарағанда әлдеқайда жеңіл.
Алайда, RSA-ның кейбір нұсқалары ... ... ... ... ... ... ... ең тиімді жолы – сандарды n көбейткіштерге
жіктеу әдісі. Кез-келген қарсылас е ашық кілтін және n ... ала ... ... ... табу үшін оны n ... ... ... Қазіргі таңда
бұл технологияның алдыңғысы болып 129 ондық саннан ... сан ... Олай ... n бұл ... ... болу ... криптоаналитик барлық мүмкін d-ларды дұрыс мән іздеп тапқанша
қарастыра алады. Бұл әдіс n ... ... ... әлдеқайда
күрделі және тиімсіз. Уақыт өте келе RSA-ны ... ... жолы ... ... ... ... ... бұлардың осы күнге дейін ешқайсысы да
дәлелдене қойған жоқ. Мысалы, 1993 жылы Вильям ... ... ... теоремасына негізделген әдіс ұсынылды. Өкінішке орай, бұл ... ... ... ... ұзақ ... шықты.
Сонымен қатар, р және q жай сандарын көптеген жалпы қабылданған
есептеу алгоритмдерінің көбісі ... ... ... ал егер олар ... ... ... ... Біріншіден, бұл оқиғаның болу ықтималын қажетті
минимумге төмендетуге болады. Оған ... ... мен ... ... анықталып отыр. Жай сандарды іздеудің ықтимал ... ... ... ... деп ... ... ... белгілі. Олар
қауіпсіз емес және сирек кездеседі.
RSA қарсы шифромәтіннің таңдалуымен ашу
Кейбір ... ... ... ... ... ... Олар ... алгоритмін емес, ал онымен өңделген протоколды ... ... өзі ... ... білген жөн.
1-сценарий: Алисаның әңгімелесу линиясын ақырын тыңдай алған Ева
Алисаның ашық кілтпен RSA ... ... с ... ала ... ... ... келеді. Математика тілінде оған m=c d анықтау үшін m-ді
табу керек. m-ді анықтау үшін ол n-нен кіші ... r ... ... ашық е ... ... ... кейін
x= re mod n
y= x c mod n
t= c mod n
есептелінеді.
Егер x= re mod n болса, онда r=x d mod n ... ... ... ... у-
ті жабық кілтпен жазуын сұрайды, осылайша у-тің ... ... ... ... ... ... U= yd mod n жібереді. Енді Ева,
t*u mod n= r -1 yd mod = r-1xdcd mod n= c d mod n=m ... ... бұл ... Егер ... ... келсе, онда ол оны трентке жібереді. Трент оны RSA-ның сандық
қолымен рәсімдеп, тездетіп қайтарады. ... ... ... ... қол ... құжатын рәсімдегенін қалайды. Бұл авторы басқа адам
хабарламасы ... ... ... ... болсын, бәрібір, Трент оған ешқашан
қолын қоймайды. Оны біз mr ... деп ... ... ... ... кез-
келген мәнің таңдайды және y= xе mod n ... е ... ол оңай ... ... ашық кілті. Енді Мэллори m= уmr mod n ... және ... ... қол қою үшін ... Трент md mod n қайтарады.Енді Мэллори (md mod ... mod n ... ол n d mod n ... және қолы mr болады.
Шындығына келгенде, Мэллори бұл есепті бірнеше тәсілмен шығара алады.
Мұндай анықтаулар жүргізудің ... ... ... ... ... кірудің мультипликативті құрылымның сақталуы болып ... (хm) d mod n =х d m d mod ... Ева ... оған m3 –ке қол ... ... Ол m1 және m2
екі хабарлама жасайды. Мұнда m3 =m1m2 (mod n) болады. Егер Ева ... ... m2 –ге қол ... ... ол m3-ті ... ... ... m 3d=(m1dmod
n)(m2 dmod n)
Демек, RSA алгоритмін ... ... ... қол қою ... ... ең ... бірбағытты хэш-функцияны қолданыңыз. ISO
9796 блок форматтары бұл ... ... ... ... бұзу тәсілдері
RSA-ны бұзудың бірнеше тәсілдері бар. Ең тиімді шабуылы: ашық ... ... ... ... ... Бұл ... ... оқуға мүмкіндік береді. Мұндай шабуылды n – p және q-дің
жалпы модулін анықтау ... ... ... ... p, q және e ... d ... оңай ... алады.Негізгі қиындық- n басты
көбейткіштерін табу. RSA ... ... ... ... ... ... ... көбейткіштерге жіктеумен
эквивалентті деуге болады: d-ны n көбейткіштерін іздеу үшін де, ... ... d ... ... үшін ... болады. Есептеу машиналарының
дамуы RSA криптожүйесінің тұрақтылығын азайтпайды, егер кілт ... ... ... ... бұзудың басқа амалы mod n-нен е дәрежесінің түбірлерін анықтау
әдістерін іздеуде. С=M(mod n) болса, онда mod n-нен е ... ... М ... ... ... соң шифрленген
хабарламаларды ашып, қолтаңбаны жалған қоюды жабық кілтті анықтамай-ақ
орындауға ... ... ... ... ... ... алайда
қазіргі уақытта RSA-ны бұл ... ... ... ... ... ерекше жағдайда осы хабарламаларды бұзуға болатын әдістер белгілі.
Хабарламаға жалғыз шабуыл - ұсынылған ашық ... ... ... ... арқылы бұл хабарламада белгілі бір ... бар ... ... кейін оны алынған шифрленген мәтінмен салыстырады. Мұндай
шабуылды мәтін соңына кездейсоқ биттер қосу арқылы ... ... ... басқа шабуылы егер бірдей М ... 3 ... оның ... ... e = 3 көрсеткішін пайдаланады. Мұны ... ... ... ... алып, М хабарламасын оқи алады. Мұндай
шабуылды әр шифрлеуде кездейсоқ ... қосу ... ... ... ... ... мәтін жасап, соған сәйкес ашық ... ... ... хабарлама шифрын анықтауға тырысатын тағы да бір ... ... ... да ... ... ... ... шабуылдар ретінде қарастырылмайды, себебі, ол ... ... оның ... ... ... мұнда оның таратылымының
әлсіздігі қарастырылынады.Мысалы, шабуылдаушы ... ... ... ете ... ... базасында қауіпсіздік ережелері дұрыс сақталмаса.
Тұрақты сандар және олардың RSA криптожүйесінде ... ... ... ... n ... ... үшін ... таңдау кезінде, алынған p және q сандары тұрақты болу керек. Тұрақты
сандардың ... ... ... n ... ... ... ... болады, мысалы, p - 1 және p + 1 үлкен еселіктерінің болуы.
Мұндай ... ... ... ... ... ... Pollard (p –
1) және Pollard (p + 1) әдістері p - 1 және p + 1 ... р тек ... ғана ... ... ... тек жеке ... шыдамды.
ANSI X9.31 стандартында ғана тұрақты сандар қолдану талабы қойылады.Алайда,
соңғы ... ... ... ... күшін жояды,
мысалыкөбейткіштерге жіктеудің ... ... ... ... жаңа ... p және q-дің әлсіз де, ... ... ... ... тұрақты сандар таңдауы қауіпсіздікті ... ... ету үшін ... ... қолдану қажет.
Кілттің ұсынылатын ұзындығы
RSA алгоритміндегі кілт өлшемі n модулінің өлшемімен байланысты. p және
q екі саны туындысы модуль болып ... ... ... ... ... ... бұл ... факторларын анықтау қиынға соғады. Мысалы,
егер 768-битті модуль қолдансақ, онда әр сан 384 ... болу ... = (p+q)/2 деп ... p < q ... онда 0 м – sqrt (n)
(q - ... = M*() ... p мен q ... p - q айырмасы өте
аз болса, оңай табуға болады.
Модульдің оптимальды өлшемі қауіпсіздік талаптарымен анықталады: ... ... ... қауіпсіздікпен қамтамасыз етеді, бірақ RSA
алгоритмінің жұмысын ... ... ... ең алдымен таңдалынады,
мұнда қорғалынатын ақпарат мәні ескеріледі.Қорғаудың жақсы сараптамасы
модуль ұзындығымен ... Rivest [Riv92a] ... ... ... RSA – мен ... ... ... факторинг арқылы талданады.
1997-жылы жүргізілген бағалау RSA 512-битті кілті факторингпен 1,000,000$
және 8 айда ... ... ... Бұл ... ... ... қамтамасыз ете алмайды деген сөз.
Қазіргі таңда RSA лабораториясы ... ... үшін 1024 ... ұсынады, ал маңызды есептер үшін - 2048 битті. Жақында орнатылған
стандарт бойынша кілт 1024 битті болу керек. Бағалығы ... ... ... ... бола ... ... ... кілтті осы күнге ... ... ... үшін Lenstra мен Verheul ... ... осы жеке ... ... мерзімі болады. Мерзімі өткен
соң тұтынушы жаңа кілт ... ... ... ... ... тексеру қажет. Кілтті алмастыру ... ... ... RSA ... ... ... ... мың модульге массивті шабуыл өте қысқа мерзімді жүзеге асады.
Кілтті ... ... ... ... ету ашық кілт ... 4 есе, жеке кілт ... уақытын 8 есе арттырады. Кілттерді екі
еселеу уақыты 16 есе артады, бірақ сирек ... бұл ... ... әсер ... RSA ... кілттер сенімділігі DES
блоктық шифр типінің өлшемінен жоғары, алайда RSA кілтінің сенімділігі ... ... үшін жай ... жиыны
Эвклидпен 2 мың жыл бұрын дәлелденгендей жай сандардың шексіз саны бар.
RSA алгоритмі белгілі бір өлшемді ... ... ... ... саны өте ... Жай ... ... теорема бойынша ... ... ... ... n = ... ... ... жылжиды. 512 битті
өлшемді кілттер ұзындығы шамамен 10150 болады. Бұл ... ... ... да ... шығарылған RSA
RSA криптожүйеісінің модулі жөніндегі дау жөнді- ... ... ... ... разрядын таңдау тиімділік пен ... ... ... (А. Shamir) ... ... жаңа ... ұсынды. Шамир
әдісімен құрылған модулі бар криптожүйе «Баланстан шығарылған RSA» атына
ие ... ... ... n = pq ... он есе ... р
бөліндісінің разрядтылығы 2 есе арттырылған. Сәйкесінше q ... ... ... ... ... ... Шамир бойынша он жылдап
сақталынатын криптотұрақтылықты әкеледі.
Негізгі мәселе оның қолданылуы 1000 есе ... ... ... бір минутқа кешіктіру секунд пенасымен өлшегенде 16 ... Ал. Ол ... ... ... ... синхронизм орнату кезінде в ... ... р ... ... ... ... үшөлшемді DES
шифрлеуін үш әртүрлі кілтке қолданатын болсақ та ... 168 ... ... ... шифрленетін блок [0,р-1] ... ... ... ... ... шифрлеу кезінде тиімділігн арттыру үшін қолданылатын
кең тараған әдіс с = me(mod n) және ол кіші е ... ... ... ... е < 10 ... бойынша келтіруді жүргізбейді,
себебі т хабарлама ұзындығы n модулінің оннан бір бөлігін ... е ≈ ... me ... ... n ... ... екі есе
асады. е-ні мұндай есептеуде тe (mod n) ... ... ... ... ... амал ғана ... болады. Осылайша, 20 < е < 100 ... тез әсер етуі ... ... бар ... ... т = ... n) ... шартын қарастырайық, егер с, n және d- 500- ... ... ... ... қытайлық теорема бойынша р-ның 500-биттік
модулі үшін т1= сd (mod р) , ... р мен d-ны (р-1) ... ... ... ... m2 = сd (mod q) ... ... үшін
есептеуінде q 93 = 729 есе көп ... ... ... ... барлық амалдарды қолдану міндетті емес ... ... ... ... да, анықтама бойынша m1(mod р)болады. m ашық мәтіні р-
дан кіші, олай ... m (mod p)= т. Бұл ... т1= т және т2 –ні ... ... ... дәл сол ... алып ... шығарылған RSA және стандартты криптожүйелер көп ... ... 10 есе ... ... жою үшін бірнеше әдістер ұсынылды.Әртүрлі
қосымшалар үшін еркін жадтық ... ... ... үшін жадтың артуы елеулі салдарға әкеледі. ... ... үшін (Smart Card) ... құны жадына тура
пропорционал болады.Оған ... ... ... ... 512-
битті модуль базасына маманданған ... ... Сол ... ... ... ... реакцияға әкеліп соғады. Практикалық
қосымшаларда интеллектуалды карталар ... ... ... ... ... ... мен ... амалдарын орындаудың
технологиялық базасын таңдауға мүмкіндік ... ... ... алғашқы шифрленген кілтті генерациялай алады және шифрлік мәтін
тізбекті интерфейс ... ... р ... ... беріледі. Есептеулер
барысында интеллектуалды ... ... ... ... ... тиімділігі модульды өзгертпей қазіргі заманғы
интеллектуалды карталардың есептеу ресурстарын пайдалана ... бір ... ашық ... ... 10 есе ... Алайда ашық
кілттерді баланстан шығарып, бұл мәселені шешуге болады. G ... ... ... ... ол ... ... 5000-битті ерекше көрсету үшін ... t ... ... G ... деп жорамалданады. Әр тұтынушы 500-
биттік р жай санын генерациялайды, q — [а, a+ 250] ... жай ... а ең кіші ... сан, ол t/р кіші ... тең ... Жай сандар өте
көп болғандықтан q әрқашан да болады. Нәтижесінде модуль ... n = pq және t 550 ... ... Әр и ... өзінің ашық
кілтінің s = n — t санын жариялай ... ... ... ... ... ашық кілтпен G(u)+s есептей алады. ... ... ... бұл әдіс ... сандарды орналастыру
заңы біртектіліктен ... ... сан ... ... деп саналады. Осындай әсерлерді қалыпқа келтіру үшін q м
шегінде таңдалынады, а + 250 түрінде беріледі
Баланстан ... RSA ... екі ... үшін ... Мұнда МА-
қолтаңбасы үшін р бөліндісі белгісіз. Сонымен қатар белгіленген қысқа ашық
кілт ұзын болып саналады.
Гилберт (Н.Gilbert), ... (D. Gupta), ... (А. Odlyzko) ... (J.J ... ... ... RSA ... алушы мен
діберушінің арасындағы қатынастың балансы орнатылғанда сәтті шабуылданады.
и мен е — Бобтың ашық ... ... ... — р мен q ашу. т
> р ... ... және Бобқа шифрлік мәтін me mod п ... ... ... ... m-ді алады. m > р болса, онда m # m.
Ал, енді что ... ... да бір ... т ... алды ... ... ол p|(m-m) ... алады. 0 < т, m < n және т # ... ... ... ... q † (т — т ... ... р-ні ... ... ... ... егер (m-m,n) ЕҮОЕ-н ... ... Боб ... m бере алады. Қосымша мүмкіндіктер
интеллектуалды карталарда ... ... (Smart Card), олар ... ... –ді ... кілт есебінде бере алады. Қарсы әсер ... ... ... идентификациялық тізбектің пайда болуына
байланысты.
Ал, енді ... ... ... тұратын мысалды қарастырайық «Боб
есебіне 101,74 ... ... ... ... 123 шотымнан
Замухрышина қ. Аударуыңыз ды сұраймын.». Егер m > р, т ... ... Егер m < р және m = ... ... ... ... ... туралы факт Алисаға m < р екендігін білдіреді.
Мұндай стратегия р ... ... ... Бір ... р ... ... егер 100 дол.сомадан аз болмаса. Алиса р шекарасын
анықтай алда деп ... ... 6×2k < р < 7×2k. ... ... ... ... шамамен m –ді 13 ×2k-1 ... ... ... ... ... ... тізбекті жылжу әдісі арқылы орындай алады. Әдіс 4 ... ... ... ... ... Әдіс көп ... талап ететіндігін
атап өтейік. Жоғарыда көрсетілген шабуыл ойластырылған болып көрінуі
мүмкін, алайда ол ... ... ... ... ... ... ... RSA-ның компрометациясына алып келмейді, бірақ хабар
алушы ешқашан дешифрленген хабарламаны алмайтындығына ... ... ... ... ... қолданылуы кезінде барлық тұтынушыларға бірдей n модулін
таратып, ... ... е мен d-ның ... ... беру ... ... бұл әдіс жұмыс істемейді.Бұның себебі, егер бір ... ... ... ... ... көрсеткіштерімен шифрленсе, және бұл екі
көрсеткіштер сыбайлас жай сандар болса, онда ашық ... ... ... ... та анықталуы мүмкін.
m – хабарламаның ашық мәтіні болсын. е1 және е2- шифрлеу кілттері. n-
жалпы модуль. ... ... ... ... mе1mod n
с2= mе2mod n
Криптоаналитик n, е1, е2, с1, с2 біледі. Енді m-ді табу ... е1 ... ... жай ... онда ... r мен s ... алгоритмі
бойынша
rе1 +sе2=1
r-ді теріс сан деп есептей ... с1-1 ... ... ... ... Содан соң:
(с1-1)-r* с2s= m mod n.
Бұл жүйелерді анықтаудың екі ... ... ... n-ді
көбейткіштерге жіктеудің ықтимал әдісін пайдаланса, екіншісі құпия ... ... ... көбейткіштерге жіктемей-ақ есептейді.
RSA-ның шифрлеуінің кіші көрсеткішін анықтау
RSA-ның шифрленуі мен оның ... ... е үшін кіші мән ... орындалады. Егер е(е+1)/2 ашық кілтті әртүрлі хабарламалармен сызықтық
қатынаста болса және е мәні тұрақты болса, бұл ... ... ... ... ... аз болса, онда ол аса қиын емес. Егер хабарламалар бірдей
болса, онда е ... ... ... ... ... ... mеmod n≠mе ... дәлелдейді. Хабарламаларды шифрлемес бұрын
кездейсоқ сандармен ... ... оның m мәні ... n – мен ... ... қолдану арқылы шифрлену мен қолын анықтау
Хабарламаларды шифрлемес бұрын оған қол ... ... зор, ... бұл әдісті ешкім қолданбайды. Алиса Бобқа хабарлама жібергісі
келеді.Алдымен ол оны Бобтың ашық ... ... ... соң ... ... қол қояды. Оның шифрленген және қол ... ... (mod nβ) dА mod ... ... оған m ... m’ жібергенін былай дәлелдей алады. Бобқа nβ
көбейткіштерге қалай ... ... ... ол nβ ... ... есептей алады. Олай болса, оған тек х мәнін табу ғана
қалды:
mα=m mod nβ
Сонда ол хеβ-ні жаңа ... ... ... ... алады, бұрынғы
nβ-ні сақтай отырып, Алиса оған m’ жібергенін дәлелдей алады.
4.7 RSA бағдарламалық жабдықтаманың сипаттамасы
Төменде бағдарлама ... ... ... Оған ... ... байқауға болады (x-сурет).
Бағдарлама жұмысының жалпы үлгісі
ҚОЛДАНЫЛҒАН ӘДЕБИЕТТЕР ТІЗІМІ
1. Саломаа А. ... с ... ... Пер. с ... – М.: Мир,
1995. – 318 с.
2. Баричев С.Г., Гончаров В.В., ... Р.Е. ... ... – М.: ... линия - Телеком, 2001.
3. Хоффман Л. Современные защиты информации. Пер. С англ.-М.: Сов. Радио,
1980
4. Ященко В.В. Введение в криптографию. – ... ... ... .В. ... ... в компьютерных системах.
М.:Электроинформ,1997
6. Брюс ... ... ...

Пән: Информатика
Жұмыс түрі: Курстық жұмыс
Көлемі: 45 бет
Бұл жұмыстың бағасы: 500 теңге









Ұқсас жұмыстар
Тақырыб Бет саны
Ақпараттық қауіпсіздік түрлері14 бет
Жадыны Windows NT,Unix операциялық жүйелерінде қорғау13 бет
Ақпаратты қорғау мәселесінің криптографиялық негіздері49 бет
Криптографиялық интерфейс23 бет
Криптожүйелер17 бет
Симметриялық шифрлау кері шифрлау. “Базарбай Бектас” мәтінін вижинер кестесі арқылы шифрлау6 бет
Эль-гамаль цифрлық қолтаңба программалық өнімін құрастыру38 бет
Криптографияның математикалық негіздері2 бет
DES (Data Encryption Standard) алгоритмін талдау21 бет
DES алгоритмі20 бет


Исходниктер
Пәндер
Көмек / Помощь
Арайлым
Біз міндетті түрде жауап береміз!
Мы обязательно ответим!
Жіберу / Отправить


Зарабатывайте вместе с нами

Рахмет!
Хабарлама жіберілді. / Сообщение отправлено.

Сіз үшін аптасына 5 күн жұмыс істейміз.
Жұмыс уақыты 09:00 - 18:00

Мы работаем для Вас 5 дней в неделю.
Время работы 09:00 - 18:00

Email: info@stud.kz

Phone: 777 614 50 20
Жабу / Закрыть

Көмек / Помощь