Дәріс №1 Кіріспе. Жиындар теориясының негізгі ұғымдары. Жиындарға амалдар қолдану



жүктеу/скачать 1,12 Mb.
бет15/15
Дата12.09.2020
өлшемі1,12 Mb.
#78187
1   ...   7   8   9   10   11   12   13   14   15
Байланысты:
Лекция дискретка каз

i

B*






















.













Мұндай




әріптеп




кодтау

K







әріптерінің







түрінде белгіленеді.

i




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

Мысал.
Төмендегі алфавиттер берілсін делік:


  1. = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} В = {0, 1}.

Онда кодтау кестесі орналастыру түрінде бола алады:
0

1

2

3

4

5

6

7

8

9




















































0000 00010010 0011 0100 0101 0110 0111 1000 1001







.

Бұл екілік-ондық кодтау, ол өзара бірмәнді болып табылады, сондықтан

декодтау орындала алады.































Дегенмен схема





































0

1

2

3

4

5

6

7

8

9




















































0

1

10

11

100

101

110

111 1000 1001



















өзара бірмәнді болып табылмайды. Мысалы, алты бірліктен 111111 тұратын жиын 333, 77, сонымен қатар 111111, 137, 3311 немесе 7111сөздеріне сәйкес келуі мүмкін, онымен қоса кез-келген орыналмастыру.
Алфавиттік кодтак схемасы префиксті деп аталады, егер бір әріптің элементар коды басқа әріптің элементар кодының префиксі болып табылмаса.
2.Макмиллан теңсіздігі
Алфавиттік кодтау схемасы бөлінгішті деп аталады, егер кез-келген элементар кодтардан құралған сөз элементар кодтарға жалғыз әдіспен жіктелетін болса.
Бөлінгішті схемалы алфавиттік кодтау декодтауға рұқсат етеді.
Префиксті схема бөлінгішті болатынын дәлелдеуге болады.
Алфавиттік кодтау схемасы бөлінгішті болуы үшін элементар кодтардың ұзындығы Макмиллан теңсіздігі деп аталатын қатынасты қанағаттандыруы керек.
Макмиллан теңсіздігі

Егер алфавиттік кодтау схемасы

1 2... n 1 2... n
бөлінгішті болса, онда





1







1




...




1

1

2




1

2




2




2

n
















теңсіздігі орындалады.


Мысал

Алфавиттік кодтау схемасы



А={ а, b}и В={0, 1},


a

b













0







01

бөлінгішті болып табылады, себебі

1 1, 2 2,

демек, Макмиллан теңсіздігі орындалады:
211 212341

Берілген схема префиксті болып табылмайды, себебіа әрпінің элементар коды b әрпінің элементар кодының префиксі болып табылады.



Бақылау сұрақтары:

  1. Кодтау дегеніміз не?

  2. Декодтау қалай жүзеге асырылады?

  3. Бөлінгіштік дегеніміз не?Префиксті код деген қандай код?

  4. Макмиллан теңсіздігі.


Дәріс №14. Мәліметтерді сығу
Дәріс мақсаты:Мәліметтердің көлемін азайту мақсатында қолданылатынсығу алгоритмдерімен таныстыру.
Кілттік сөздер:Мәліметтерді сығу,сөздік,Лемпель–Зив алгоритмі.

Жоспары:


  1. Мәліметтерді сығу

  2. Қайталамалы серияларды кодтау

  3. Лемпель –Зив алгоритмі

1.Мәліметтерді сығу


Мәліметтерді сығу (ағылш.data compression) —олардың көлемін азайтумақсатында орындалатын мәліметтерді алгоритмдік түрлендіру. Мәліметтерді жіберу және сақтау үшін қолданылады. Кері процедура мәліметтерді қалпына келтіру деп аталады.
Кез-келген сығу негізінде мәліметтердің шығу тегінің моделі тұрады. Басқаша айтқанда қандай типті мәлімет сығылуы қажеттігін білу керек. Сығылатын материал туралы мәліметіңіз болмай тұрып, оның көлемін азайту үшін ешқандай әрекет ете алмайсыз.
Барлық сығу алгоритмдері екі негізгі класқа бөлінеді:
Шығынсыз сығу; Шығынмен сығу.
Шығынсыз сығуды қолданғанда мәліметтерді толығымен қалпына келтіруге болады, ал шығынмен сығуды қолданғанда мәліметтер елеусіз ақаулықтармен қалпына келтіріледі. Мәліметтерді шығынсыз сығу мәтіндік құжаттарды, компьютерлік программаларды, сирек жағдайда аудио-бейне мәліметтердің, цифрлық бейнелердің көлемін азайту мақсатында, яғни мәлімет ақаулықсыз қалпына келтірілу қажет болғанда қолданылады. Шығынмен сығу әдетте аудио-бейне файлдардың, цифрлық бейнелердің көлемін азайту үшін, яғни бастапқы мәлімет пен қалпына келтірілген мәліметтің толық сәйкестігі талап етілмеген жағдайда қолданылады.



  1. Қайталамалы серияларды кодтау

Мәліметтерді сығудың ең танымал қарапайым шешімі және ақпаратты қайтымды жолмен сығу – бұл қайталамалы серияларды кодтау (Run Length Encoding - RLE). Бұл әдістің мәні қайталамалы байттар сериясын немесе шынжырларды немесе олардың тізбегін бәір кодтаушы байтпен және қайталану санының есептегішіне алмастыру болып табылады.


Мысалы:
44 44 44 11 11 11 11 11 01 33 FF 22 22 – бастапқы берілген тізбек , 03 44 04 11 00 03 01 03 FF 02 22 сығылған тізбек. Бірінші байт келесі байтты неше рет қайталау керектігін көрсетеді. Егер бірінші байт 00-ге тең болса, онда оның артынан қанша қайталанбайтын мәлімет бар екендігін көрсететін есептегіш тұрады. Бұл әдістер растрлы графикалық бейнелерді (BMP, PCX, TIF, GIF) сығуға өте тиімді болып келеді, себебі олар қайталанатын ұзын сериялы байттар тізбегінен тұрады. RLE әдісінің кемшілігі сығу дәрежесінің төмендігі болып табылады.
3. Лемпель –Зив алгоритмі
1977 жылы Абрахам Лемпель және Якоб Зив кейін LZ77 аталған мәліметтерді сығу алгоритмін ұсынды. Бұл алгоритм мәтінді сығу compress,

lha, pkzip және arj программаларында қолданылады.LZ78өзгертілгеналгоритмі екілік мәліметтерді сығу үшін қолданылады. Бұл өзгертілген алгоритмдер АҚШ патентімен қорғалған. Алгоритм биттер тізбегін фразаларға бөлу арқылы кодтап, кейін осы фразаларды кодтауды ұсынады. Алгоритмнің мәні келесіден болады:
Егер мәтінде қайталанатын символдар жолы кездесетін болса, онда олар сол жолға сілтемелермен алмастырылады. Сілтеме форматы <префикс, арақашықтығы, ұзындығы>түрінде болады. Префикс бұл жағдайда 1-ге тең. Арақашықтық өрісі жолдар сөздігіндегі сөзді идентификациялайды.Егер жолсөздікте болмаса, онда <префикс, символ> түріндегі символ коды генерацияланады, мұндағы префикс өрісі=0, ал символ өрісі бастапқы мәтіннің ағымдық символына сәйкес келеді. Осыдан префикстің көрсеткіштер кодын символдар кодынан бөліп тұратынын көруге болады. <Символ> кодтарын кірістіру сөздікті тиімді етуге және сығу тиімділігін арттыруға мүмкіндік береді. Мұндағы негізгі алгоритмдік мәселе тиімді жолды таңдауда болып тұр, себебі мұнда біршама артық алынуы мүмкін.
Мысал қарастырайық. U = 0010001101 бастапқы берілген тізбек.

Белгілеулер енгізейік:


P[n] —n нөмірлі фраза; C — сығу нәтижесі.
Бастапқы берілген биттер тізбегін фраза түрінде жазу 1-кестеде көрсетілген.
P[0] — бос жол. "." (нүкте) символымен біріктіру операциясы белгіленеді (конкатенация).











1-кесте

N фраза

Мәні

Формула

Бастапқы берілген тізбек U

0




P[0]

0010001101

1

0

P[1] = P[0].0

0.010001101

2

01

P[2] = P[1].1

0.01.0001101

3

010

P[3] = P[1].0

0.01.00.01101

4

00

P[4] = P[2].1

0.01.00.011.01

5

011

P[5] = P[1].1

0.01.00.011.01

Әрқайсысы(A.B) түрінде болатын жолдар жұбын қалыптастырайық. Әрбір жұп жаңа фразаны құрады және осы фразаға қосылатын алдыңғы фразаның идентификаторы мен биттен тұрады. Барлық осы жұптарды біріктіру С соңғы нәтижесін береді. P[1]=P[0].0 (00.0)-ді береді, P[2] = P[1].0 (01.0)-ді береді және т.с.с. түрлендіру схемасы 2-кестеде көрсетілген.















2-кесте

Формулалар

P[1]=

P[2]=

P[3]

=

P[4] = P[2].1

P[5]= P[1].1




P[0].0

P[1].1

P[1].0










Жұптар

00.0 = 000

01.1 = 011

01.0 = 010

10.1 =

01.1 =
















101

011

С

000.011.010.101.011 = 000011010101011




Құрамында P[0] бар барлық формулалар сығуды бермейді. Көріп тұрғанымыздай С U-ға қарағанда ұзынырақ, бірақ бұл бастапқы берілгені қысқа тізбек үшін. Мәлімет үлкен көлемді болғанда бастапқы берілгенді сығу өте жақсы жүзеге асады. Келтірілген мысалдан сығу амалдарының барлығы мәліметтердің көлемін қысқартпайтынын көруге болады.



Бақылау сұрақтары:

  1. Мәліметтерді сығу дегеніміз не?

2.Сығу алгоритмдерінің неше түрі бар?

3.Қандай мақсатта мәліметтер сығылады?

4.Сығудың қандай алгоритмдері бар?
Дәріс №15. Криптография. Шифрлау
Дәріс мақсаты:Мәліметтерді қорғау мақсатында криптография,шифрлауәдістерімен таныстыру.
Кілттік сөздер:криптография,шифрлау,Цезарь алгоритмі,ашық кілттішифрлау, криптожүйелер.
Жоспары:


  1. Криптография

  2. Криптоалгоритмдер классификациясы

  3. Ашық кілтті криптожүйенің концепциясы




  1. Криптография

Криптографиялық әдістер ақпаратты қорғаудағы ең тиімді әдістердің бірі болып табылады.


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

  1. Криптоалгоритмнің классификациясы

Барлық криптоалгоритмнің классификациясының басты схемасы келесілер болып табылады:




  1. Құпия жазу

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




  1. Кілттік криптография.

Жіберілетін мәліметтерге әсер ету алгоритмі басқаларға да белгілі, кілттің кейбір жіберуші мен алушыға ғана белгілі параметрлерге қатысьты.


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

Абсолютті нақтылықты қажет ететін мәліметтердің басқа түрінен өзгеше өзінің функционалдығын жоғалтпай қандай да бір сатыда бейне өзгеріс болатын нөмірленген сурет немесе дыбыс;


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









1кілт







1кілт













(құпия)







(құпия)




























Мәтін







Шифрограмма













Мәтін


































Шифрлеуші










Керішифрлеуші
















Канал байланысы






































































Жіберуші




























Алушы










(тапсырушы)




























(қабылдаушы)































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


Ақпаратық блоктың өлшеміне қарай криптоалгоритм мыналарға бөлінеді:

  1. Потокті шифрлеу, онда кодтау бірлігі бір бит болып табылады.

2.блоктік шифр, кодтау бірлігі бірнеше байттан тұратын блок болып табылады.


Айырбастау әдісімен шифрлеу.Бұл шифрлеу әдісінің ең оңай түрі.Шифрленген мәтіннің символдары бір алфавиттен немесе көп алфавиттен алынған басқа символдармен айырбасталады.
Біралфавитті қою. Ең оңай қою–шифрленген хабардың символдары солалфавиттің басқа әріптерімен тікелей айырбастау.
Кестені айырбастау мысалы:

    1. БВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ

  1. ЛДОТВАЧКЕЖХЩФЦЭГБЯЪШЫЗИЬНЮУПСРЙ




  1. БВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ

QWERTYUIOP[]ASDFGHJKLZXCVBNM<>@%

Жай айырбастаудың беріктік әдісі төмен.



Цезарь шифрлеуі. Юлий Цезардің(б.з.д.100-44ж.ж..)Цицерономен(б.з.д
106-43 ж.ж. ) хат алмасу шифрлесу факті анықталды. Цезардің шифрлау әдісі осы алфавиттің әріптерінің ауысуымен жүзеге ауысады, ол алфовиттегі
берілген әріптен берілген сандағы әріпке ауысады. Цезарь өз шифрлау әдісінде ол ауыстырылатын әріпті , сол әріптен кейінгі үш позицияға алға жүретін әріппен алмастырған.
Мысалы «ГДЕ АББА» хабарламасын шифрлау керек..
Цезарь шифрлауы айналымды деп аталады, ауыстыру кезінде, алфовит әріптері айналым бойынша орналасқан деп алынады: соңғы әріптің артынан ең алғашқы алфовиттің әріпі жүреді.. Цезарь шифрлауы қалай шифрланатының көрсетейік:
АБВГДЕЁЖЗ

АБВГДЕЁЖЗИ

Ауыстыру нәтижесінде ЁЖЗ ГДДГ шифрограммасы пайда болады.


  1. Ашық кілтті криптожүйенің концепциясы

Ашық кілтті криптожүйенің барлық айқындамасы бірбағыттағы функцияны қолдануда негізделген (one way functions). Бірақта бұл функция класын нақты математикалық көзқарас жақтан анықтама беру қиын болып табылады. Бірбағытты функцияны келесі әдістермен анықтауға болады.

X және Y – еркін көптік . Функция
f(X) -> Y,
бірбағытты болып табылады, если для всех егерде барлық х-ке, Х кіруші, f(x) функциясын шешу өте оңай, және сол уақыттағы y-тің көпшілігі , Y-ке кіруші, x санының кез-келген мәнің қабылдайды, X-ке кіруші, онда f(x) = y
өте қиын.болып келеді
Диффи-Хеллмана кілтінің таралу жүйесінің әдісі. Криптографиялық жүйелерде әрбір қолданушы қосағы хабарламаны шифрлеу және кері шифрлеу үшін жасырын кілтті қолдану. Осындай тектес жүйелердің ең алғашқысы Диффи-Хеллмана жүйесі болып табылады. Ол 1976 жылы өнделген, ол дискреттік тапсырмалар логарифімінде құрылған.
Қадам бойынша кілттерді алмастыру процедурасын қарастырайық.


    1. Алғашқыда алекс және Юстас N және G мәндері жайлы келісімге келеді (ережеге сай осы мән барлық жүйе қолданушыларына үлгілі болып келеді.)




    1. Содан кейін Алекс үлкен X бүтін санын таңдап және XX = G^X MOD N есептейді. Сәйкесінше Юстас Y санын таңдайды, ол




  1. = G^Y MOD N есептейді.

Осыдан кейін Алекс және Юстас XX және YY мәліметтерімен алмасады.(Бұл канал бойынша берілетін барлық мәліметтер қакүнем-Мюллермен алынуы мүмкін) X және Y сандарын Алекс және Юстасқұпияда сақтайды




  1. Юстастан YY санын алып, Алекс есептейді

K(1) = YY^X MOD N, а Юстас

K(2) = XX^Y MOD N.


Но (!)
YY^X MOD N = G^(X*Y) MOD N = XX^Y MOD N, аследовательно, K(1) = K(2) = K.
Осы К саны хабарламаларды шифрлеуге арналған кілт болып табылады. Ашық кілтті жүйелердің қалай қолданылатынын қарастырайық. Пайдаланушы Алексте екі алгоритм бар: Е шифрлеу үшін және D
хабарламаларды кері шифрлеу үшін. Бұл жағдайда Е алгоритмі көпшілікке қол жетерлік етіп жасалынады, мысалы, кілттер каталогын қолдану арқылы, ал D алгоритмін Алекс жасырын сақтайды. Егер Юстас немесе Мюллер қарияның өзі Алекске хабарлама жібергісі келсе, ол кілттер каталогында Е алгоритмін іздейді және оны жіберілетін ақпаратты шифрлеу үшін қолданады. Ал хабарламаны тек Алекс қана кері шифрлей алады, себебі D алгоритмі тек онда ғана бар. Шамасы, E және D мына шартты қанағаттандыруы керек:
D(E(M)) = M, кез келген M хабарламасы үшін.
Қайтадан, дәстүрлі криптожүйелер үшін сияқты E және D нәтижелі алгоритмдерді алу қажет. Бұл жадайда E алгоритмі өз бойында қара жүрісті функцияны білдіруі керек, яғни E алгоритмін білу D алгоритмін жүзеге асыру үшін жеткілікті болмауы керек.

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



Бақылау сұрақтары:

  1. Криптография дегеніміз не?

  2. Ақпаратты шифрлау қалай жүзеге асырылады?

  3. Шифрлаудың қандай түрлері бар?

  4. Ашық кілтті шифрлау қалай орныдалады?




  1. Цезарь алгоритмі.

жүктеу/скачать 1,12 Mb.

Достарыңызбен бөлісу:
1   ...   7   8   9   10   11   12   13   14   15



©engime.org 2024
әкімшілігінің қараңыз
    Басты бет