Эллиптикалық криптография

     Криптография ақпаратты түрлендіруде  математикалық әдістерді іздеу және зерттеумен айналысады. Криптоанализдің айналысатын сфералар жүйесі – ақпараттың кілтін білмей шифрын анықтау.

     Қазіргі  криптография өзіне 4 үлкен бөлімді  қосады:

• Симметриялық криптожүйелер.
• Ашық кілтті криптожүйелер.
• Электрондық қолтаңба жүйелері.
• Кілттерді басқару.

     Криптографиялық әдістерді қолданудың негізгі мақсаты – байланыс каналдары арқылы жасырын ақпаратты тарату (мысалы, электрондық пошта), жіберілген хабарламалардың ақиқаттығы, шифрлі тұрде ақпаратты сақтау.

     Криптографиялық  жүйелер қаншалықты қиын және сенімді  болғанымен олардың практикалық  қолданылуының әлсіз жағы – кілттерді үлестіру мәселесі. Ол үшін ақпараттық жүйелер екі субьекті арасында жасырын ақпарат алмасу мүмкін және кілт солардың біреуімен генерациялану керек, жасырын түрде әрі қарай басқасына жіберілуі керек. Яғни, кілтті тарату үшін криптожүйені қолдану керек. Бұл мәселені классикалық және қазіргі алгебрадан алынған нәтижелер негізінде шешу үшін ашық кілтті жүйелер ұсынылды.  Олардың  мәні ақпараттық жүйенің әр хабар алушысымен екі кілт генерацияланады, олар бір-бірімен белгілі ережеге сәйкес байланысады. Бір кілт ашық, екіншісі жабық болып жарияланады.  Ашық кілт жарияланады және кез-келген хабарлама жібергісі келетін адам үшін белгілі болады. Құпия кілт жарияланбайды.

     Бастапқы  мәтін хабар алушының ашық кілтімен шифрленіп, оған жіберіледі. Шифрленген мәтіннің негізінен ашық кілтпен  шифры анықталу мүмкін емес. Хабарламаны  дешифрлеу тек хабар алушыға  ғана белгілі болатын жабық кілтті қолдану арқылы ғана мүмкін. Ашық кілтті криптографиялық жүйелер қайта оралмайтын немесе біржақты функциялар деп аталатын ортақ қасиеті бар қызмет атқарады. Берілген х үшін f(x) мәнін есептеу оңай, алайда тек y=f(x) болса, х есептеудің оңай тәсілі жоқ.

     Біржақты  функциялардың көптеген кластары ашық кілтті жүйенің көптүрлілігін тудырады. Алайда біржақты функциялардың барлығы  ақпараттық жүйесінде қолдануға  жарай бермейді. Қайта оралмайтын деген түсінікте теориялық қайта  ораламсыздығы емес, белгіленген уақыт интервалында қазіргі заманғы есептеу құралдарын қолдану арқылы кері мәнін практикалық тұрғыдан есептей алмау айтылады. Сондықтан, ақпаратты тиімді сақтау үшін ашық кілтті жүйелерге екі айқын әрі маңызды талап қойылады:

1. Бастапқы мәтіннің түрленуі қайтымсыз болу керек және ашық кілт негізінде қайта қалпына келмеу керек.
2. Ашық кілт негізінде жабық кілтті анықтау жаңа технологиялық тұрғыдан  мүмкін емес болу керек. Мұнда шифрды анықтауда күрделіліктің төменгі бағасы көрсетілуі керек.

Ашық  кілтті шифрлеу алгоритмдері кең қолданысқа ие болды. RSA алгоритмі ашық жүйелер үшін әлемдік де-факто стандарты болды. Қазіргі таңда ұсынылатын ашық кілтті криптожүйелер қайтымсыз түрленудің төмендегідей топтарына жіктеледі:

1. Үлкен сандарды көбейткіштерге жіктеу;
2. Соңғы өрісте логарифмді есептеу;
3. Алгебралық теңдеулердің түбірлерін анықтау.

Ашық  кілтті криптожүйелерді 3 түрлі мақсатта қолдануға болады:

1. Жіберілген және сақтаудағы мәліметтерді өзіндік қорғау құралы ретінде.
2. Кілттерді үлестіру құралы ретінде. Ашық кілтті жүйелер алгоритмдері дәстүрлі криптожүйелермен салыстырғанда аса көп еңбекті қажет етеді.
3. Тұтынушыларды аутентификациялау құралы ретінде.

      2 Математикалық негіздемелер

     2.1 Күрделілік теориясы

     Күрделілік  теориясы криптографиялық әдістер  мен алгоритмдердің әр түрлі есептеу  күрделіліктеріне қарай әдістемелік  талдау жасауға мүмкіндік береді. Ол криптографиялық әдістері мен  алгоритмдерін салыстыра отырып, оның қаншалықты қауіпсіз екендігін анықтайды. 

     Алгоритмнің күрделілігі

     Алгоритмнің күрделілігі оның орындалуға керекті  есептеулік қуаттарымен есептеледі. Есептемелік алгоритмнің күрделілігі  мынадай екі параметрмен өлшенеді: T(уақытқа байланысты туындайтын күрделілік) және S(кеңістікке байланысты туындайтын күрделілік немесе жадыға қойылатын талап). Негізінде, T мен S, n айнымалысына тәуелді функция ретінде қарастырады. Мұндағы, n – бұл қабылданған ақпараттардың шамасы. 

     Негізінде, есептемелік алгоритмнің күрделілігін О() функциясы арқылы жазады. Бұл күрделілік функциясының жай бөлшектерге жіктеу түрі болып табылады. Мысалы, егер 4n²+7n+12 алгоритмінің уақытқа байланысты туындайтын күрделілігі болса, есептеулік күрделілігі n² болып келеді, оны О(n²) деп белгілейді. 

     Алгоритмдерді олардың уақыттық немесе кеңістіктік күрделілігіне байланысты жіктейді. Егер алгоритм n-ға тәуелді болмаса, онда ондай алгоритмдерді тұрақты деп атап, О(1) деп белгілейді. Егер уақыттық күрделілігі О(n) болса, онда алгоритмді сызықтық деп атайды. Алгоритмдердің квадраттық, кубтық және тағы да басқа түрлері болады. Бұл алгоритмдердің барлығы – полиноминалды болып келеді, ал олардың күрделілігі О(n^m), мұндағы m – тұрақты шама. Уақыттық күрделілігі бар полиноминалды алгоритмдерді полиноминалды уақыттық алгоритмдер деп атайды.

     Күрделілігі О(t^f(n)) есептелетін алгоритмдерді экспоненциалдық алгоритмдер деп атайды, мұндағы t – бірден үлкен тұрақты шама, ал f(n) – белгілі бір полиноминалды функция. Күрделілігі О(с^f(n)) есептелетін экспоненциалдық алгоритмдердің жиынын суперполиноминалды деп атайды, мұндағы с – тұрақты шама, ал f(n) тұрақтыдан қарағанда тездетіп өсетін, бірақ сызықтыдан баяу болатын функция. 
 

3-кесте.  n=10⁶ шамасындағы әр түрлі алгоритмдердің уақыт күрделілігіне тәуелділігі

     Компьютер үшін уақыттың өлшем бірлігі микросекунд  болғандықтан, компьютер тұрақты  алгоритмдерді – 1 микросекундта, сызықты алгоритмдерді – 1 секундта, ал квадратты алгоритмді – 11.6 күнде есептей алады екен. Кубтық алгоритмдерді 32000 жылда есептейтін болғандықтан, экспоненциалдық алгоритмдер туралы айтудың қажеті де жоқ.

     Шифрленген  алгоритмдерді күшпен ашу проблемасын қарастыратып көрейік. Мұндай ашудың уақыттық күрделілігі мүмкін болатын кілттердің санына тура пропорционал. Демек, кілттің ұзындығынан тәуелді деген сөз. Егер n – кілттің ұзындығы болатын болса, онда күшпен салып ашудың күрделілігі О(2ⁿ)-ге тең. 

     Проблеманың күрделілігі

     Күрделілік  теориясы белгілі бір алгоритмді шешудің проблемасын ғана қарастырмайды, сонымен қатар, проблеманың қаншалықты күрделі екенін де анықтайды. Атап айтқанда, сол проблеманы шешуге керекті минималды  уақытты және жадының көлемін қарастырады. Оны Тьюринг машинасы деп атайды. Тьюринг машинасы шекзіз жадымен жабдықталған, алгоритмді оқу және жазу үшін арналған есептеудің наңыз моделі болып табылады. 

     Полиноминалды уақыттық алгоритмдер арқылы шешілетін  проблемаларды шешілетін проблемалар деп атайды. Яғни, белгілі ақпарат үшін белгілі уақыт бөлініп, сол уақытта шешіледі. Полиноминалды уақыт ішінде шешілмейтін проблемаларды шешілмейтін деп атайды. Кей жағдайларда, шешілмейтін проблемаларды қиын (ауыр) проблемалар деп те атайды. Алан Тьюринг кейбір проблемаларды шешудің алгоритмін табу мүмкін еместігін дәлелдеді.

Барлық  проблемаларды олардың шешілуіне  байланысты сәйкесінше кластарға бөлуге болады. Ең маңызды кластар төменде  көрсетілген. 
 

     Шешілетін проблемалар класы 

3-сурет 
 

     Ең  төменде орналасқан Р класы полиномиальды уақытта шешуге болатын барлық мәселелерден тұрады. NP-класы – полиномиальды уақытта тек Тьюрингтің детерминацияланбаған машинасында шешуге болатын барлық мәселелер: жорамал жасай алатын Тьюрингтің қарапайым машинасының нұсқасы. Машина мәселенің шешуін жорамалдай алады- не «сәтті» табу арқылы, не болмаса барлық жорамалдарды параллельды таңдап, барлық жорамалдарды полиномиальды уақытта тексереді.

     NP-ның криптографиядағы маңызы: көптеген симметриялық алгоритмдер және ашық кілті бар алгоритмдер детерминацияланбаған полиномиальды  уақытта бұзылуы мүмкін. Берілген С шифрлік мәтін үшін криптоаналитик Х ашық мәтінді және к кілтін талғайды және полиномиальды  уақытта Х және к арқылы шифрлеу алгоритмін тексере отырып, оның нәтижесі С –ға тең болу мәселесін тексереді. Бұның теориялық маңызы зор, себебі осы алгоритмдердің криптоанализінің күрделілігінің жоғарғы шегін анықтайды. Тәжірибеде бұл әрине полиномиальды уақытта орындалатын детерминацияланған алгоритм, дәл осыны криптоаналитик іздеу тиіс. Бұл алгоритм шифрлердің барлық класстарына бірдей қолданыла алмайды, ол бір қолдануға жарайтын блокноттар үшін жарамайды – кез келген С үшін Х, к көптеген жұптары шифрлеу алгоритмін орындау кезінде С-ны береді, бірақ Х-тің көбісі мәнсіз, мүмкін бола алмайтын ашық мәтіндер болады.

     NP-класына Р класы кіреді, себебі полиномиальды уақытта орындалатын Тьюрингтің детерминацияланған машинасында орындалатын кез-келген мәселе полиномиальды уақытта Тьюрингтің детерминацияланбаған машинасында орындала алады, тек жорамалдау сатысы болмайды.

     Егер  барлық NP мәселелер Тьюрингтің детерминацияланған машинасында полиномиальды  уақытта орындалатын  болса, онда Р = NP болады. Алайда, кейбір NP мәселелер басқаларымен салыстырғанда аса күрделі және ешқашанда Р-ның NP-ға тең еместігі дәлелденбеген. Алайда, күрделілік теориясы саласында жұмыс жасайтын адамдардың көбісі бұл класстар тең бола алмайды деген пікірді ұстанады.

     Ең  қызығы нақты NP-мәселелер осы класстың басқа мәселелері секілді өте қиын екендігін дәлелдеуге болады. Стивен Кук Орындалушылық мәселесінің NP-толық болатынын дәлелдеді. Бұл дегеніміз – егер Орындалушылық мәселесі полиномиальды уақытта шешілсе, онда Р = NP. Керісінше, егер NP класының кез-келген мәселесі үшін шешімнің полиномиальды уақыты бар детерминацияланған алгоритмі болмайтындығы дәлелденсе, Орындалушылық  мәселесі үшін де полиномиальды уақыты бар детерминацияланған  алгоритмі болмайтындығын дәлелдеу көрсетеді. NP-да Орындалушылық  мәселесінен ауыр мәселе жоқ.

     Куктың  негізқалаушылық жұмысы басылғаннан соң, Орындалушылық мәселесіне эквивалентті мәселелер бар екендігі анықталды. Эквиваленттілікке байланысты бұл мәселелер де NP-толық болып, NP класына кіретін барлық мәселелер тәрізді қиын мәселе болып табылады деп ойлаймын. Егер олардың детерминацияланған полиномиальды уақытта шешілетіндігі дәлелденсе, онда Р сұрағының NP-ға қарсы сұрағы шешімін табар еді. Р = NP сұрағы рас па екендігі  күрделі есептеу теориясының негізгі шешілмеген сұрағы болып табылады және жақын арада өз шешімін табады деп күтіледі. Егер Р = NP болатындығын біреу көрсете алса, онда осы кітаптың біраз бөлігі қажетсіз болады: шифрлардың  көптеген класстары детерминацияланбаған полиномиальды  уақытта  бұзылады. Егер Р = NP болса, онда олар әлсіз детерминацияланған әлсіз алгоритмдермен бұзылады.

       Келесі болып күрделілік иерархиясында  PSPACE класы жүреді. PSPACE класының мәселесі полиномиальды кеңістікте шешілуі мүмкін және полиномиальды уақыт ішінде шешілуі міндетті емес болып келеді. PSPACE өзіне NP –ны қосады, бірақ PSPACE мәселелері NP-ға қарағанда аса күрделі. Әрине, бұл әлі дәлелденбеген. Сонымен қатар, PSPACE-толық деп аталатын келесі қасиетке ие мәселелер класы бар: егер олардың кез-келгені NP-мәселе болса, онда PSPACE = NP, және егер олардың кез-келгені Р-мәселе болса, онда PSPACE = P болады.