Ақпаратты қорғау мәселесінің криптографиялық негіздері диплом жұмысы
АҚПАРАТТЫ ҚОРҒАУ МӘСЕЛЕСІНІҢ КРИПТОГРАФИЯЛЫҚ НЕГІЗДЕРІ
МАЗМҰНЫ - www.topreferat.com.kz
КІРІСПЕ 3
1 КРИПТОГРАФИЯНЫҢ МАТЕМАТИКАЛЫҚ НЕГІЗДЕРІ 4
1.1 Модулярлық арифметиканы есептеу 4
1.2 Дәрежеге шығару алгоритмі 5
1.3 Эйлер функциясы 7
1.4 Модулярлық арифметикада кері шамаларды есептеу 10
1.4.1 Тура іріктеу әдісі 12
1.4.2 Эйлер функциясы көмегімен кері шамаларды есептеу 12
1.4.3 Евклидтің кеңейтілген алгоритмі көмегімен кері шамаларды есептеу 13
2 ШИФРЛЕУ АЛГОРИТМДЕРІ 17
2.1 Симметриялық алгоритмдер 17
2.1.1 Блоктық шифрлар 18
2.1.2 Ағындық шифрлар 31
2.1.3 Құрама шифрлар 32
2.2 Ассиметриялық алгоритмдер 32
2.2.1 RSA алгоритмі 33
2.2.2 Диффи – Хеллман алгоритмі 36
2.2.3 Эль-Гамаль алгоритмі 40
3 АШЫҚ КІЛТТІ КРИПТОЖҮЙЕДЕ КІЛТ БАСҚАРУ 42
3.1 Сертификация 42
3.2 PGP қауіпсіз электрондық поштасы 44
4 ПРАКТИКАЛЫҚ ЖҰМЫС 47
ҚОРЫТЫНДЫ 51
ӘДЕБИЕТТЕР ТІЗІМІ 52
ҚОСЫМША А 54
Жұмыс түрі: Дипломдық жұмыс
Жұмыс көлемі: 58 бет
Пәні: Соңғы қосылған дипломдық жұмыстар
-----------------------------------------------------------------------------------
ДИПЛОМДЫҚ ЖҰМЫСТЫҢ ҚЫСҚАРТЫЛҒАН МӘТІНІ
АҚПАРАТТЫ ҚОРҒАУ МӘСЕЛЕСІНІҢ КРИПТОГРАФИЯЛЫҚ НЕГІЗДЕРІ
МАЗМҰНЫ
КІРІСПЕ
1 КРИПТОГРАФИЯНЫҢ МАТЕМАТИКАЛЫҚ НЕГІЗДЕРІ 4
1.1 Модулярлық арифметиканы есептеу
1.2 Дәрежеге шығару алгоритмі
1.3 Эйлер функциясы
1.4 Модулярлық арифметикада кері шамаларды есептеу
1.4.1 Тура іріктеу әдісі
1.4.2 Эйлер функциясы көмегімен кері шамаларды есептеу
1.4.3 Евклидтің кеңейтілген алгоритмі көмегімен кері шамаларды есептеу
2 ШИФРЛЕУ АЛГОРИТМДЕРІ
2.1 Симметриялық алгоритмдер
2.1.1 Блоктық шифрлар
2.1.2 Ағындық шифрлар
2.1.3 Құрама шифрлар
2.2 Ассиметриялық алгоритмдер
2.2.1 RSA алгоритмі
2.2.2 Диффи – Хеллман алгоритмі
2.2.3 Эль-Гамаль алгоритмі
3 АШЫҚ КІЛТТІ КРИПТОЖҮЙЕДЕ КІЛТ БАСҚАРУ
3.1 Сертификация
3.2 PGP қауіпсіз электрондық поштасы
4 ПРАКТИКАЛЫҚ ЖҰМЫС
ҚОРЫТЫНДЫ
ӘДЕБИЕТТЕР ТІЗІМІ
ҚОСЫМША А
Кіріспе
Қазіргі кезде ақпаратты қорғау жалпы ұлттық мәселеге айналып отыр.
Мемлекеттің барлық салаларына қатысты ақпарат нақты саяси, материалдық және
Жаңа қуатты компьютерлердің, желілік технологиялардың пайда болуы мен ақпараттың
Криптография термині ежелгі гректердің «cryptos – құпия» және «grapho
Бітіру жұмысымның мақсаты:
ақпараттық ресурстардың сыртқа кетуін, ұрлануын, жоғалуын, бұрлануын, қолдан жасалуын,
тұлғаның, мемлекеттің және қоғамның ақпараттық қауіпсіздігі;
ақпаратты қорғаудың математикалық жолдарын (яғни, математикалық әдістерін немесе қулықтарын)
математиканы және жалпы білімді дәріптеу.
Бітіру жұмысымның өзектілігі. Криптография қоғам өмірінің ажырымас бөлігіне айналып
Ақпаратты қорғаудың әртүрлі жолдары (мысалы, механикалық немесе физикалық), әртүрлі
Бітіру жұмысымның міндеттері. Ақпаратты қорғау әдістері мен ақпаратты шифрлеу
1.1 Модулярлық арифметиканы есептеу
Модулярлық арифметика көбінде жай арифметикаға ұқсас: ол коммутативті, қауымдастықты,
Негізінен модулярлық арифметиканың жазылуы төмендегідей түрде:
а ≡ b (mod n), бұл «n модулі бойынша
Бұл ара қатынас бүтін мәндер а,b және n ≠
Бұдан шығатыны n | (a-b), бұл «n (a-b)-ға бөлінеді»
Егер бұл қатынас орындалса, онда b санын n модулі
Анықтама 1 Егер a-b айырымы n-ге қалдықсыз бөлінетін болса
0-ден n - 1-ге дейінгі бүтін сандардың жиынтығын n
n = 7, { 0, 1, … , 6
n = 100, { 0, 1, … , 99
Дұрысы біз алдымен n модулі бойынша шығарып алып, содан
(a+b) mod n = ((a mod n) + (b
(a-b) mod n = ((a mod n) - (b
(a*b) mod n = ((a mod n) * (b
(a*(b+c)) mod n = (((a*b) mod n) + ((a*c)
Дискреттiк логарифм және түбiр квадратын есептеу қиын болғандықтан,
Анықтама 2 Модулі бойынша белгілі бір а санымен салыстырмалы
Мысал: 6 модулі бойынша сыныбы:
Модулярлық арифметиканы компьютерлік есептеулерге қолдану үшін біз тек қана
Ескерту. Программалау тілдерінде mod функциясы басқаша анықталуы мүмкін.
Модулярлық арифметиканың артықшылығы:
Бүтін сандармен жұмыс істейміз;
Есептердің барлық нәтижелері супер өрісте орналасқан.
Мысалы. 13 mod 7 = 6, 0≤n≤n-1
7 mod 7 = 0, 4 mod 7
1.2 Дәрежеге шығару алгоритмі
К биттi ұзындықты n модулiнiң қосу, алу немесе
n модулi бойынша а санының дәрежесiн есептеудi ax mod
Мысалы, егер a8 mod n –дi есептеу керек болса,
Бұның орнына 3 кiшi көбейту мен 3 кiшi модуль
((a2 mod n)2 mod n)2 mod n
Осы әдiспен a16 mod n = (((a2 mod
Есептеу бiраз ғана қиынырақ: ax mod n (4), мұндағы
x = 25(10) → 1 1 0
Онда a25 mod n = (a*a24) mod n =
Аралық нәтижелерде алты ғана көбейту амалы керек болады:
(((((((a2 mod n)*a) mod n)2 mod n)2 mod n)2
Бұл әдiс 1,5хк операциясына дейiн есептеуде қиындықты жеңiлдетедi, мұндағы
Көптеген шифрлеу алгоритмi n модулi бойынша дәрежеге шығаруға негiзделген
S = aW mod n мағынасын есептеу керек болсын.
W = wg-12g-1 + wg-22g-2 + … + w222
мұндағы wi 0 немесе 1сандары.
S = aW mod n – ді келесі
S = aw mod n = aWg-12
Мысалдар:
1) 437 mod 26 = ((42)19 – 4) mod
2) [(223 mod 11)39 + (411 mod 7)19]
(223 mod 11)39 = ((24)5*23 mod 11)39 = (55*23
(411 mod 7)19 = ((42)5*4 mod 7)19 = (25*4
839 mod 11 + 219 mod 11 = (82)19*8
13 mod 11 = 2.
1.3 Эйлер функциясы
Айталық, m = p1α 1 p2α 2 …
φ (m) = p1α 1-1(p1-1) p2α 2-1(p2-1)
Сонымен натурал аргументті φ функциясын анықтаймыз.
Анықтама 1 Жоғарыда көрсетілген әдіспен анықталған φ функциясы Эйлер
Анықтама 2 Эйлер функциясы n-нан кіші және n-мен өзара
Мысалға, φ (10) = 4. Эйлер функциясының келесі тамаша
Теорема 1 (Эйлер) Кез-келген n модулі мен n-мен өзара
aφ(n)-1 ≡ 1(mod n)
Анықтама 3 Келесі үш шартты қанағаттандыратын θ функциясын мультипликативті
θ кез келген натурал сан үшін анықталған;
θ(1) = 1;
егер (a,b) = 1 болса, онда θ(ab) = θ(a)θ(b).
Теорема 2 Эйлер функциясы – мултипликативті функция.
Дәлелдеуі. Айталық, p1α 1 … ptα t
Теорема 3 φ (m) саны 1, 2, …, m
Дәлелдеуі. Дәлелдеме m>1 санының канондық жіктеуіндегі жай көбейткіш сандардың
m-нің p-ға бөлінбейтін жағдайын қарастыру қалды. m-мен өзара жай
Эйлер функциясының осы қасиетінің берілген дәлелдемесін Р.А.Сүйіндіков ұсынды.
Мысалдар: Берілген n натурал саны жай сан деп саналады,
1. n = 7
1 2 3 4 5 6
2. n = p*q, p,q –жай сандар, ((n) =
n = 33 = 11*3, ((33) = (11-1)(3-1)
3. n = kr
((n) = (k-1)*kr-1, n = 8 = 23
((8) = (2-1)*23-1 = 1*4 = 4.
1.4 Модулярлық арифметикада кері шамаларды есептеу
Нақты сандарды арифметикада а-1 мультипликативтi керi шаманы есептеу қиынға
Мысалы, мультипликативтi керi шама 4 санынан ¼-ке тең, өйткенi
Ал модулярлық арифметикада керi шаманы есептеу қиын есеп болып
Бұл есептiң жалпы тұжырымы – х бүтiн санын табу,
Бұл есептiң шешiмi кейде болады, кейде болмайды. Мысалы, 14
5*3 = 15 ≡ 1 (mod 14)
Келесi жақтан қарасақ, 14 модулi бойынша 2 санында керi
Егер а және n - өзара жай сандар болса,
Егер а және n сандары өзара жай сандар болмаса,
Нәтижесi жоқ керi шаманы табудың негiзгi әдiсiн тұжырымдаймыз. a
Мысалы, егер a = 3 және n = 7
Егер ЕҮОБ(a, n) ≠ 1 болса, жоғарыда келтірілген мысал
Егер ЕҮОБ(a, n) = 1, онда a-1 керi сан
a*a-1 ≡ 1 (mod n)
Шындығында да, a*i (mod n) 0, 1, …, n-1
a*i ≡ 1 (mod n)
Мысалы, n = 11-жай сан болсын. 11 модуль бойынша
Келтiрiлген шегеру жиынын тұжырымдаған кезде олардың iшiнен бiр ғана
Жалпы келтiрiлген шегеру жиынында n модуль бойынша жай санының
Эйлер функциясы φ(n) шегеру жиынтығында келтірілген элементтер санын мінездейді.
Кесте 1 Эйлер функциясы
Модуль n Функция φ(n)
N – жай сан
n2
·
·
·
nr n-1
n(n-1)
·
·
·
nr-1(n-1)
P*q (p, q – жай сандар)
·
·
·
(p– жай сан) (p-1)(q-1)
·
·
·
Басқаша айтқанда, Ферманың кiшкене теоремасы: егер n–жай және ЕҮОБ(a,
Эйлердiң қортуына сәйкес Ферманың кiшене теоремасынан: eгер ЕҮОБ(a, n)
Керi шаманы табудың негiзгi 3 әдiсі бар. Олар: тура
1.4.1 Тура іріктеу әдісі
a-1 ≡ 1 (mod n) табылмағанға дейiн, осындай a*a-1
Мысалға, x = a-1 (mod n) табылмағанға дейiн, 1,
n = 7, ал a = 5 болсын. x
а*x ≡ 1 (mod n) немесе 5*х ≡ 1
n - 1 = 7 - 1 = 6
x = 5-1 (mod 7) = 3 - тi
Кесте 1 Тура іріктеу әдісінің мысалы
x 5*x 5*x (mod 7)
1
2
3
4
5
6 5
10
15
20
25
30 5
3
1
6
4
2
1.4.2 Эйлер функциясы көмегімен кері шамаларды есептеу
Eгер Эйлер φ(n) функциясы белгiлi болса, онда дәрежеге тез
Кесте 1 Эйлер функциясы көмегімен кері шамаларды есептеу
Модуль n Функция φ(n)
n
n2
nr n-1
r(n-1)
nr-1(n-1)
n = p*q (p-1)(q-1)
Егер а және n өзара жай сандар болса,
Егер Эйлер функциясы белгілі болса, онда кері шаманы есептеуге
а-1 (mod n) = aφ(n-1) (mod n)
Мысалдар:
a-1 (mod n) –дi табу керек, егер Эйлер φ(n)
n = 7, ал a= 5 болсын. x =
n = 7 модулi – жай сан. Сондықтан Эйлер
Керi шама 5-тен 7 – ге дейiнгі аралықты қамтиды.
a-1 (mod n) = aφ(n) – 1 (mod n)
Нәтижесі x = 5-1 (mod 7) = 3-ке тең.
1.4.3 Евклидтің кеңейтілген алгоритмі көмегімен кері шамаларды есептеу
Егер Эйлер φ(n) функциясы белгiлi болмаса, кеңейтiлген Евклид алгоритмiн
Евклид алгоритмнің алгебрада, тіпті жалпы математикада атқаратын ролі өте
r0 = q1r1 + r2, 0
.
.
rm-2 = qm-1rm-1 + rm, 0
Енді негізгі нәтижені дәлелдеу қиын емес:
ЕҮОБ(r0, r1) = ЕҮОБ(r1, r2) = … = ЕҮОБ(rm-1,
яғни, Евклид алгоритмін орындау нәтижесінде берілген сандардың ең үлкен
ЕҮОБ(r0, r1) = rm
Енді бұл алгоритмді былай кеңейтейік. Рекурренттік әдіспен төмендегідей t0,
t0 = 0,
t1 = 1, және j≥2 үшін tj = tj-2
Бұл тізбектің пайдасын келесі леммадан көреміз. Алдымен бір белгілеу
Лемма 1 Жоғарыда іске асырылған кеңейтілген Евклид алгоритмінде
Дәлелдеуі: j бойынша индукция қолданамыз. Біріншіден, бастапқы мәндер j
Сонымен, индукцияның ұйғарымы бойынша ri-2 ≡ ti-2r1 (mod r0)
Ал енді ri –ді есептесек, алатынымыз:
ri = ri-2 – qi-1ri-1 ≡ ti-2r1 – qi-1ti-1r1
Лемма дәлелденді.
Егер ab ≡ 1(mod n) болса, онда a,b сандары
Салдар 1 Егер ЕҮОБ(r0, r1) = 1 болса (бұл
Бұл алгоритм бойынша берілген теріс емес а, b бүтін
aU1 + bU2 = U3 = EYOБ (a, b)
Есептеу барысында қосымша (V1, V2, V3), (t1, t2, t3)
Есептеу үрдісінде келесі қатынастар орындалып отырады.
аt1+bt2 = t3
aU1 + bU2 = U3
aV1 + bV2 = V3
a-1 (mod n) а санының n бойынша кері саның
b = n, ЕҮОБ (a, n) = 1 тиіс
Алгоритмнің негізгі қадамдары:
Бастапқы қойылым (U1, U2, U3) векторы анықталады;
(U1, U2, U3) = (0, 1, n)
(V1, V2, V3) = (1, 0, a)
U3 = 1 орындалса, алгоритмнің соңы;
q анықталады. q = div бөлгендегі
Қосалқы векторларды есептейді (t1, t2, t3).
(t1, t2, t3) = (U1, U2, U3) - q(V1,
(U1, U2, U3) = (V1, V2, V3)
(V1, V2, V3) = (t1, t2, t3).
Алгоритм аяқталды.
Мысал. n = 23, a = 5
5-1 (mod 23)
Кесте 1 Евклидтің кеңейтілген алгоритмі көмегімен кері шамаларды
q U1 U2 U3 V1 V2 V3
- 0 1 23 1 0 5
4 1 0 5 -4 1 3
1 -4 1 3 5 -1 2
1 5 -1 2 -9 2 1
2 -9 2 1
a-1 (mod n) ≡ U1 (mod n)
5-1 (mod 23) ≡ -9 (mod 23) = 14
Тексеру: (5*14) mod 23 = 70 mod 23 =
Нәтижені қорытатын болсақ: Евклид алгоритмі бүтін сандардың ең үлкен
Керi a-1 (mod n) шамасын кеңейтiлген Евкид алгоритiмiнiн көмегiмен
Евклид алгоритмiн үлкен практикалық мәнi бар әдiспен қорытуға болады.
a* u1 + b* u2 = ЕҮОБ(a, b)
Бұл кеңейтiлген Евклид алгоритмiнiнiң қорытуын тиiмдi болады, егер векторлық
2 ШИФРЛЕУ АЛГОРИТМДЕРІ
2.1 Симметриялық алгоритмдер
Симметриялы криптографиялық жүйелер ақпаратты қорғау саласында классикалық жүйелер болып
Сурет 1 Симметриялық криптографиялық жүйедегі шифрлау тәсілдерінің классификациясы
Ақпаратты қорғаудағы криптографиялық өзгерту әдістері арнайы алгоритмдердің немесе аппараттық
Криптографияны қолдану - көп таралған және ЭВМ желілерінде мәліметтерді
Осы кезде кейбір шифрлеу әдістері жақсы сыналған және классикалық
Орын алмастыру және ауыстыру әдістері әдетте кілттің қысқа ұзындығымен
Барлық айтылған әдістер симметриялы шифрлеуге жатады. Симметриялы криптографиялық алгоритмдерде
Ақпаратты криптографиялық қорғауда шифрлеу негізгі рөл атқарады. Шифрлеудің келесі
2.1.1 Блоктық шифрлар
Блоктық шифрлеу кезінде бастапқы мәтін ұзындығы тұрақты бекітілген блоктарға
Ауыстыру шифрі белгілі бір ереженің көмегімен бастапқы мәтін символдарын
Қазақ алфавитіне пробел символын қосып, сәйкес келетін ретпен жазып
“ А Ә Б В Г Ғ Д Е
0 1 2 3 4 5 6
Ү Ф Х Һ Ц
28 29 30 31 32 33 34 35 36
Цезарь хаттарды келесі формуланың көмегімен шифрлеген:
(әріп)= ( (әріп)+N) mod 43
N – шифрлеу кілті.
Цезарь шифрімен түрлендірілген хабарламаға мысал:
Б М С Б Т Б Ұ Ә Б
А Қ П А Р А Т
Әйгілі Вижинер шифры да көп әліпбилі ауыстыру шифріне жатады.
Хабарды шифрлеу үшін:
Түйінді сөз таңдайды. Мысалға «ақпарат» сөзін таңдайық.
Ашық мәтін символдарының астына кілт символдарын жазады. Егер кілт
О Р Ы Н А Л М А С
А қ п а р
3) Шифрмәтін символы Вижинер кестесі көмегімен ізделінеді. Ол үшін
Сонда келесі шифрмәтін аламыз: оылн рлюа івыб ули аәі
Кесте 1 Вижинер кестесі
Мәтінді шифрлеуде сенімділік жоғары болуы үшін Вижинердің жетілдірілген кесте
Алфавит әріптері барлық (біріншісінен басқа) кесте жолдарында өз еркімен
0-ден 9-ға дейінгі натурал сандармен нөмірленген он (біріншісін есептемегенде)
Кілт ретінде шамалар қолданылады.
Ақпаратты сенімді шифрлеуді қамтамасыз ететін ауыстыру әдісінің жеке жағдайы
Осы ережеге сәйкес A={aij} матрицасын шифрлеуге арналған негіз ретінде
Әріптік ақпаратты шифрлеу үшін ең алдымен алфавитте әріптің реттік
Дешифрлеу үшін векторға матрицаны көбейту ережесі қолданылады, тек қана
Шифрлау және шифрді ашу процедуралары қатал формализацияланған, бұл автоматты
Орын алмастыру шифрлері символдардың орналасу позицияларын ған өзгертеді. Ең
Шифрдің бұл түрінде мәтін ұзындығы біркелкі блоктарға алдын ала
Мысал. Ашық мәтін ретінде келесі сөйлемді алайық:
СИММЕТРИЯЛЫ ЖҮЙЕНІ ШИФРЛЕУ
Сөйлемді алты жолы, төрт бағанасы бар кесте түрінде жазайық:
С И М М Е Т
Р И Я Л Ы Ж
Ү Й Е Н І Ш
И Ф Р Л Е У
Шифрмәтін алу үшін кестедегі символдарды бағана бойымен (жоғарыдан
Сонда шифрмәтін аламыз: срүии ийфмя ермлн леыіе тжшу.
Орын алмастыру шифры хабарлаудың шифрлауына арналған символдардың n ұзындығымен
мұндағы i1 – шифрмәтінінің нөмірі, i2 – екінші
Келесі бағдарлама кодының (Object Pascal тілінде) үзіндісі негізгі хабарлауды
const Lmax=100;
type TArr=array[1..Lmax] of integer;
{процедура-мәтінді шифрлеу функциясы
Кіру параметрі: txt - негізгі мәтін, password - кілт
Функцияның нәтижесі – шифрленген мәтіннің жолы}
function SH_TO(txt:string;password:TArr):string;
var i,l:integer;
shifr:array[1..Lmax] of char;
s:string;
begin
l:=length(txt);
for i:=1 to l do
shifr[password[i]]:=txt[i];
for i:=1 to l do
s:=s+shifr[i];
result:=s;
end;
{процедура-шифрді ашу функциясы
Кіру параметрі: txt – шифрленген текст, password – кілт
Функцияның нәтижесі – шифрі бұзылған мәтіннің жолы }
function SH_FROM(txt:string;password:TArr):string;
var i,l:integer;
s:string;
begin
l:=length(txt);
for i:=1 to l do
s:=s+txt[Password[i]];
result:=s;
end.
Құрастырма шифрлар.Бұл шифрдің негізінде, сенімді криптожүйе құрастыру үшін ауыстыру
Құрастырма шифрларына мінездеме 2-кестеде көрсетілген.
Кесте 2 Құрастырма алгоритмдері
Алгоритмдердің аты Кілттің өлшемі, бит Блоктың өлшемі, бит Инициализация
Lucipher 128 128
DES 56 64 64 16
FEAL-1 64 64 4
B-Crypt 56 64 64
IDEA 128 64
ГОСТ 28147-89 256 64 64 32
Соның ішінде DES алгоритіміне кеңінен тоқталайық.
1972 жылы NBS (National Bureau of Standards, АҚШ) стандартты
Енді DES-ті сипаттауға көшейік. DES блоктық алгоритм болып табылады.
Бастапқы орын алмастыру.
Алгоритм басталмас бұрын ашық текст биттері үшін орын алмастыру
Р8i+1 = Р1 + Р8i , i=0,3
Бесінші байттың бірінші битінің позициясы былай есептеледі:
Р8i+1 = Р1– 1, i = 4
i=5,6,7 болғандағы 8i+1 позицияларына орналасар бит нөмірлері (1) формуласы
Р8i+j+1 = Р8i+1 -8j, i=0,7, j=1,8
Ақыры мынандай орын алмастыру кестесін аламыз.
Кесте 3 Бастапқы орын алмастыру
58 50 42
62 54 46
57 49 41
61 53 45
Кілт түрлендіру
а) 64-биттік кілттің әрбір сегізінші биті ескерілмейді. Олар тақтық
б) 56 биттік кілт екі тең бөлікке бөлінеді. Раунд
в) 56 биттің 48 таңдап алынады. Бит орналасу реті
Кесте 4 Шифрлау алгортмінің сүлбесі
32
32
Сонымен әрқайсысының ұзындығы 48 бит 16 бөлімдік кілт жасалады.
Кесте 5 Сығылатын орын алмастыру
14 17
23 19
41 52
44 49
Кесте 6 Кілт түрлендіру алгоритмі
64 бит
56 бит
48 бит
Хабарды шифрлау.
Демек сіз ұзындығы 64 бит бастапқы мәтін және ұзындығы
Кесте 7 Кеңейтетін орын алмастыру
32 1
8
16 17
24 25
Деректердің оң жағы Ri және бөлімдік кілт Ki
48 бит сегіз 6 биттік блокшаға бөлінеді. Әрқайсысына S-блок
Кесте 8 S-блоктар
1-ші S-блок:
14 4
0 15
4 1
15 12
2-ші S-блок:
15 1
3 13
0 14
13 8
3-ші S-блок:
10 0
13 7
13 6
1 10
4-ші S-блок:
7 13
13 8
10 6
3 15
5-ші S-блок:
2 12
14 11 2
4 2
11 8 12
6-шы S-блок:
12 1
10 15 4
9 14
4 3
7-ші S-блок:
4 14
13 0
1 4
6 11
8-ші S-блок :
13 2
1 15
7 11
2 1
Енді 32 биттік блок үшін Р блогының көмегімен
Кесте 9 Р блок
16 7
2 8
Алынған нәтиже блоктың сол бөлігімен қосылады.
Оң және сол бөліктер алмастырылып, келесі соңғы орын ауыстыруға
Кесте 10 Соңғы орын ауыстыру
40 8
38 6
36 4
34 2
Дешифрлау. Бұл алгоритмде шифрлау және дешифрлау процедуралары бірдей. Дешифрлау
Диффи мен Хеллман 1976-1977 жылдары DES алгоритмінің кілтін бір
Electronic Frontier Foundation (EFF) ұйымы 1998 жылы осындай есептеуіш
Бүгін DES стандарты келесі себептерге байланысты қолайсыз деп табылды:
1) Кілттің ұзындығы – 56 бит бүгін қауіпсіздік үшін
2) Алгоритм құрастырылғанда ол программалық емес, аппараттық қолдану үшін
Қазір DES-пен қатар 3DES алгоритмі көп қолданылады. Ол DES
Егер блоктық алгоритмдерді мәтінді блоктарға бөліп оларды бір бірден
Кілт тізбегі
Ашық мәтін Шифрланған мәтін Дешифрланған мәтін
Сурет 1 Вернам шифрының сүлбесі
Синхрондық шифр. Синхрондық шифрда кілт тізбегі ақпарат ағынына байланыссыз
Өзіндік синхронданатын шифры. Шифрдің бұл түрінде ашық мәтін символдары
Құрама шифрлар
Құрама шифр алгоритімінде блоктық және ағындық шифрлау тәсілдері бірге
Идеал шифр талабы. Клод Шеннон егер:
Біркелкі таралу заңдылығымен шын мәнінде кездейсоқ екілік тізбек болып
Кілт ұзындығы бастапқы хабардың ұзындығына тең болса
Кілт бір ғана рет қолданса
Шифр абсолют сенімді болады деп дәлелдеді.
Бұл үш талаптын бірден орындалуы әрине қиынға түседі. Дегенмен
2.2 Ассиметриялық алгоритмдер
Ашық кілтті криптографияның негізін қалаған Уитфилдом Диффи және Мартином
Бүгінгі таңда ашық кілтті криптография негізінен келесі түрлендірулердің бірін
Үлкен сандарды көбейткішке жіктеу
Ақырлы өрістерде логарифм есептеу
Алгебралық теңдеулердің түбірлерін табу.
Ашық кілтті криптожүйені келесі 3 бағытта қолдануға болады:
Деректердің қауіпсіздігін қамтамасыз ету үшін
Кілт тарату тәсілі ретінде
Аутентификация үшін.
2.2.1 RSA алгоритмі
RSA криптожүйесін Рон Ривест (Ron Rivest), Ади Шамир (Adi
Алгоритмнің беріктілігі дискреттік логарифмді есептеудің қиындығы мен үлкен сандардың
Сиппатамасы:
Екі үлкен кездейсоқ жай p және q сандары таңдап
de ≡ 1(mod(p-1)(q-1))
m хабарды шифрлау үшін оны алдын ала n-нен кіші
ci = mie mod n
Дешифрлау үшін mi = cid mod n есептелінеді.
Расында, (1), (2) және (3) формулаларын қолдана отырып алатынымыз
cid mod n = (mie mod n)d mod n
Ең алдымен осы криптожүйедегі шифрлау жылдамдығын қарастырайық. Егер біз
Тұтынушы n,e кілттерін ашық деп (Public key) жариялайды, ал
RSA aвторлары криптожүйенің жұмысын түсіндіру үшін келесі тестілік мысал
ITS ALL GREEC TO ME
Әр символға 5 разряд арнап, бос орынды – 0,
09201900011212000718050511002015001305.
Ашық кілттердің мәні ретінде е = 9007, n =
11438162575788886766923577997614661201021829672124236256265184293570693524573389783059712363958705058989075147599290026879543541
деп алынған.
Сонда шифрланған санның түрі келесідей болып шықты:
с=1999351314978051004523171227402606474232040170589146310370371740625997160894892750439920962672582675012893554461353823769748026.
Енді біз есептеу алгоритімін толық сипаттайтын мысал келтірейік.
Мысал. Жай сандар ретінде p = 11, q =
Кез-келген φ(n)-мен өзара жай e санын таңдайық, яғни (e,
7d = 1 mod 160
Алдында келтірілген кеңейтілген Евклид алгоритмін қолданамыз. Енді Евклид алгоритміне
160 = 22*7+6, 7 =1*6+1, 6 = 6*1.
Ақыры алатынымыз:
q1 = 22; q2 = 1; q3 = 6
t0 = 0; t1 = 1; t2 = 0-22*1
d = t3 = 23.
Ашық кілттер е = 7, n = 187 жариялап,
C = 97 mod 187 = ((92)3*9) mod 187
Шифрлау кезінде өте үлкен сандармен жұмыс істемеу үшін сандарды
Хабарды алушы оны дешифрлау үшін d жабық кілтін қолданады:
7023 mod 187 = ((702)11*70) mod 187 = 9.
Алгоритм RSA – ді шифрлау үшін ғана емес қолтаңба
A: Public nA, eA, Private dA
B: Public nB, eB, Private dB.
Арман алдымен m хабарын өзінің жабық кілтімен шифрлайды: c
Алынған α мәнін Болатқа жібереді. Болат хабарды алдымен өзінің
Бұл есептеулерді орындай отырып, Болат жіберілген хабардың иесі шынымен
2.2.2 Диффи – Хеллман алгоритмі
Тарихи Диффи-Хеллман алгоритмі бірінші ашық кілтті алгоритм болды. Оның
Яғни, егер y = ax mod n мәнін берілген
Төменде Диффи-Хеллманнің кілт ауыстыру протоколы көрсетілген. Арман мен Марат
Протокол:
Арман кездейсоқ үлкен бүтін х санын таңдап алып, α
Болат кездейсоқ үлкен бүтін у санын таңдап алып, β
Арман k = βx mod p мәнін есептейді.
Болат k’ = αy mod p мәнін есептейді.
Табылған к және к’ мәндері gxy mod p санына
Екі А және В қолданушылары қорғалған коммуникациялық канал ұйымдастырғысы
Екі жақты алдын-ала n модулі ( n жай сан
Одан А және В қолданушылары бір-біріне тәуелсіз меншікті құпия
Содан А қолданушысы yA = gKA (mod n) ашық
Содан кейін А және В қорғалмаған канал бойымен уА
Ары қарай А және В қолданушылары келесі салыстыруды қолдана
Қолданушы А: K = (yB)KA = (gKB)KA (mod n);
Қолданушы В: К’ = (yA)KB = (gKA)KB (mod n).
(gKB)KA = (gKA)KB (mod n) болғандықтан, K = K’
Диффи-Хеллман алгоритмін жүзеге асыру 1-суреттегі сызбанұсқада көрсетілген. Симметриялық криптожүйеде
Қолданушы А
Сурет 1 Диффи-Хеллман алгоритмін жүзеге асыру сызбанұсқасы
Қолданушы шифрді ашуды орындау үшін, алдымен салыстыру арқылы, К*
K·K* ≡ 1 (mod n-1)
oдан кейін төмендегі қатынасты қалпына келтіреді.
M = DK (C) = CK* (mod n)
Мысалы: модуль n = 47 және қарапайым элемент g
Ортақ К құпия кілті бар болу үшін, алдымен ашық
YA = gKA = 2312 = 27 (mod 47)
YB = gKB= 2333 = 33 (mod 47)
А және В қолданушылар өздерінің уА және уВ мәндерімен
K = (yB)KA = (yA)KB = 3312 = 2733
Сонымен қатар, келесі салыстыруды қолдана отырып, олар құпия кілттің
Егер қатынас М = 16, онда криптограмма
С = MK = 1625 = 21 (mod 47)
тең болады.
Қабылдап алушы қатынасты осылайша қалпына келтіреді:
M = CK* = 2135 = 16 (mod 47)
Бұл кілт ауыстыру процедурасының криптологиядағы маңызы зор болды, ол
Бұл жаңалықтың тағы бір жақсы жағы – ол процедураның
Модулі бойынша DiscLog мәселесі қиын болатын жай сандар криптографияның
Диффи-Хеллман әдісі берілгендерді жаңа кілттерде әрбір байланыс сеансында шифрлеу
Диффи-Хеллман әдісін, RSA әдісімен салыстырғанда артықшылығы мынада, ортақ құпия
2.2.3 Эль-Гамаль алгоритмі
Бұл қолтаңбаны реттеу үшін р жай саны және бинарлы
Эль-Гамаль алгоритмінің протоколын көрсетейік.
1) Кілтті генерациялау;
Кездейсоқ үлкен р жай санын генерациялаймыз және Zp мультипликативті
Кездейсоқ а (1табамыз;
Ашық кілт болып – p,g,y табылады, ал құпия кілт
2) Қолтаңба алгоритмі.
Қолтаңбамен қамтамасыз етуге қажет m – туынды ұзындықты бинарлы
Кез келген ең үлкен ортақ бөлгіші 1-ге тең болатын
к санына кері 1 саны есептелінеді. .
формуласынан r саны табылады;
формуласынан s саны табылады;
m үшін қол болып r және s жұбы табылады.
3) Қолтаңба тексеру алгоритмі.
табылады;
және табылады;
теңдігі орындалған жағдайда ғана қолтаңба қабылданады.
Бұл қолтаңбаға мысал келтірейік. p = 2357 саны және
Жай сан үшін деп алайық. к =
Дұрыстығын тексереміз: = 11851490 14901777 =
3 АШЫҚ КІЛТТІ КРИПТОЖҮЙЕДЕ КІЛТ БАСҚАРУ
Ашық кілтті криптография қолданушылар арасында кілт басқару проблемасын жеңілдетті.
Мынандай сұрақ туады: бұл мәселені шешу үшін не істеуіміз
Мүмкін, ашық кілтті өзіңіздің сайтыңыздағы мәліметтер базасына орналастыру керек?
Бірақ мұндай мәлімет көзіне сенуге бола ма? Ашық кілтке
3.1 Сертификация
Алдында аталған есептің шешімі үшінші жақпен сертификациаланған ашық кілт
Х.509 протоколдары тор бойынша мәліметтің шынайылығын тексеру үшін қолданылады.
1) Версиясы
2) Сертификат нөмірі
3) Қол қою алгоритмі
4) Берген ұйым аты
5) Басталу уақыты
6) Аяқталу уақыты
7) Субъект
8) Қолданушының ашық кілті, алгоритмдер және параметрлер.
9) Қолы
Егер жіберуші алушының ашық кілтінің шынайылығын тексергісі келсе, онда
САЕ
САD
САВ
САС
САА
Жіберуші
Сурет 1 Сертификация иерархиясы
3.2 PGP қауіпсіз электрондық поштасы
PGP (Pretty Good Privacy – құпиялылықтың ең жоғарғы
PGP қолданбалы деңгейде жұмыс істейді, сондықтан файлдар мен хаттарды,
Криптографиялық кілттердің жұмысы үшін ассиметриялық криптожүйелер қолданылады. Мұндай жүйе
Мәліметті шифрлау үшін мұнда 3DES, IDEA, CAST және басқа
Қол қою мен кілт басқару үшін RSA, Diffie-Hellman алгоритмдері
PGP программасында сертификация органы жоқ, оның есесіне сенімділік торы
Ашық кілттер сақинасына кілттерді басқа тұтынушылардан тікелей алып, web
PGP шифрлеу мен дешифрлеу үрдістерін күрделі математика негізінде қазіргі
Кілттің разрядтылығы өскен сайын криптографиялық жүйеге шабуыл жасаудағы есептеу
Ашық кілтті криптографияның ең бір нашар жағы – кілттің
PGP және де қолтаңбаға деген сенімділік деңгейін орната алады.
Сіздің өз кілтіңіз толық сенімді болып саналады. PGP құпиялы
PGP хабарды шифрлеу үшін IDEA (International Data Encryption Algoritm)
IDEA 64 биттік ашық мәтін блоктарымен және ұзындығы 128
Барлық операциялар 16 биттік блоктармен жұмыс істейді. IDEA 128
Кілт 16 биттік кілтшелерге бөлінеді. Солға қарай 25 битке
Шифрді алу үшін тура осы алгоритм қайталанады, бірақ кілт
Кездейсоқ кілттерді өндіру үшін IDEA ANSI X9.17 стандартында анықталған
Ti Encryption
Decryption Vi+1
Vi Encryp- R
tion
Сурет1 ANSI X9.17 стандарты бойынша кездейсоқ кілт өндіру
ANSI X9.17 - сеанстық кілт өндіру үшін қолайлы.
– 3DES алгоритмінің көмегімен К кілтімен шифрленген х хабары
PGP бағдарламасының қолайсыздығы – кілт қайтару операциясы болып табылады.
4 ПРАКТИКАЛЫҚ ЖҰМЫС
Ең бірінші қолданушының кілті деп аталатын кілттің ақырғы кезектілігін
k = (k0 ,k1 ,...,kn)
тізбекті қайталай отыра, шегі жоқ кезектілікке созамыз. Сонымен, жұмысшы
k = (k0 ,k1 ,...,kn), kj = k(j mod
Анықтама 1 Вижинер ауыстыруы VIGk төмендегідей анықталады
VIGk : (x0, x1, ..., xn-1) ( (y0, y1,
Бұдан шығатыны:
1) x алғашқы мәтіні r фрагменттерге бөлінеді:
xi = (xi , xi+r , ..., xi+r(n-1)), 0
2) xi алғашқы мәтінінің i-ші фрагменті Цезаря Ck ауыстыруының
(xi , xi+r , ..., xi+r(n-1)) ( (yi ,
m=2 болғандағы Вижинер ауыстыруының жүйе нұсқасы Вернам жүйесі (1917
k=(k0 ,k1 ,...,kк-1) кілтін ойда жақсы сақтау үшін кілт
Әйгілі Вижинер шифры көпалфавитті ауыстыру шифріне жатады. Шифрлеу өлшемі
Хабарды шифрлеу үшін:
Түйінді сөз таңдайды.
Ашық мәтін символдарының астына кілт символдарын жазады. Егер кілт
Шифрмәтін символы Вижинер кестесі көмегімен ізделінеді.
Практикалық тапсырма: Вижинер ауыстыруы көмегімен мәтінді түрлендіру. Мәтінді шифрлеуде
Алфавит әріптері барлық (біріншісінен басқа) кесте жолдарында өз еркімен
0-ден 9-ға дейінгі натурал сандармен нөмірленген он (біріншісін есептемегенде)
Кілт ретінде шамалар қолданылады.
Алғашқы мәтін: INFORMATIKA
Кездейсоқ кілттер генерациясын қолданғанда кілт сандар арқылы беріліп, өзгереді
Кесте 1 Бағдарлама терезесі
Мәтінді енгізген кейін «алфавит» батырмасын басамыз, содан кестені толтырамыз,
Кесте 2 Вижинер кестесі
Кілт батырмасын басқан кезде, кездейсоқ (randomize) кілттер генерациясы арқылы
Шифрленген мәтін: LNKSXODCPPF шығады.
Шифрді ашқанда қайтадан INFORMATIKA сөзі шығады.
Кесте 3 Шифрді ашу
Вижинер жүйесі (x0, x1 ,..., xn-1) алғашқы мәтінін (y0
Криптоаналитикалық зерттеуде көпалфавитті ауыстырулар қолайлы болып келеді екенін аңғару
Вижинер шифрі секілді жүйесі аппаратық немесе бағдарламалық жүзеге асыруларды
Қорытынды
Бүгінгі күні конфеденциялдық хабарламалардың көпшілігі компьютер арқылы беріледі. Ал
Сондықтан қарастырылған тақырыбыма байланысты бітіру
Криптографияның математикалық негіздерін теория тұрғысынан қарастырып, мысалдармен бекіттім.
Дискреттік математиканың криптографияның салаларына қолдануларының қарапайым мысалдары қарастырылды.
Модулярлық арифметика толығымен сипатталды.
Криптографиялық алгоритмдерді сызбанұсқа түрінде қарастырып, артықшылығы мен кемшілігін салыстыра
симметриялы криптографиялық жүйенің шифрлеу тәсілін қарастырып, көптеген мысалдар келтірдім.
Вижинер кестесін қолдана отырып, мәтінді шифрлеуді және қайта ашуды
Қолданылған әдебиеттер
Ященко В.В. Введение в криптографию : 3-е издание /В.
Анин Б. Защита компьютерной информации /Б. Анин.– Санкт-Петербург :
Романьков В.А. Введение в криптографию : Методическое указание /В.
Молдовян Н.А. Введение в криптосистемы с открытом ключом/ Н.
Молдовян А.А. Криптография: Учебник для вузов/ А. А. Молдовян.–
Байсалов Е.Р. Криптографияның математикалық негіздері : Оқу құралы/ Е.
Өтелбаев М. Ақпарат қорғау мен криптография негіздері : Оқу
Қажиакпарова Ж.С. Есептеу техникасы және бағдарламалық қамтамасыз ету мамандығы
Баричев С.В. Криптография без секретов/ С. В. Баричев.– Москва
Турецкий В.Я. Математика и информатика : 3-е издание/
Мүсірәлиева Ш.Ж. Қолданбалы криптография/ Ш. Ж. Мүсірәлиева.– Алматы :
Касперски К. Техника защиты компакт-дисков от копирования/ К.Касперски.- Санкт–Петербург
Задирака В.К. Элементы современной криптологии и методы защиты банковской
Романец Ю.В. Защита информации в компьютерных системах и сетях/
Алексеев А.П. Изучение криптографии на уроках информатики/ А. П.Алексеев//
Картье. Защита информации: криптография без границ/ Картье // Деловой
Ларин Д.А. Электронный задачник по основам криптографии/ Д. А.Ларин
Нестеров С. Криптография в устройствах защиты информации: Назови хоть
Нурбекова Ж. Программные средства обучения криптографическим методом/ Ж.Нурбекова// Ұлт
Остроумов Г. Тайнопись-от пирамид до компьютеров: О некоторых осбенностях
ҚОСЫМША А
Unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs,
Type
TForm1 = class(TForm)
StringGrid1: TStringGrid;
Button1: TButton;
Button2: TButton;
Edit1: TEdit;
Button3: TButton;
Edit2: TEdit;
Label1: TLabel;
Edit3: TEdit;
Edit4: TEdit;
Edit5: TEdit;
Label2: TLabel;
Edit6: TEdit;
Label3: TLabel;
Button4: TButton;
Button5: TButton;
Label4: TLabel;
Label5: TLabel;
Button6: TButton;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
procedure Edit2Change(Sender: TObject);
procedure Button4Click(Sender: TObject);
procedure Button5Click(Sender: TObject);
procedure Button6Click(Sender: TObject);
procedure FromClose(Sender: TObject; var Action: TCloseAction);
procedure FromShow(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
massiv=array[1..255] of integer;
const LMax=100;
type Tarr=array[1..Lmax] of integer;
var
Form1: TForm1;
key:massiv;
txt,R:string;
password:massiv;
F,j:integer;
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject); //Алфавитті толтыру
var
g:array [1..26] of char;
j,i:integer;
begin
g:='ABCDEFJHIGKLMNOPQRSTUVWXYZ';
i:=1;
for j:=1 to 26 do begin
Edit1.Text:=Edit1.Text+g[j];
form1.StringGrid1.Cells[i,0]:=g[j];
form1.StringGrid1.ColCount:=form1.StringGrid1.ColCount+1;
i:=i+1;
end;
j:=1;
for i:=0 to 9 do begin
form1.StringGrid1.Cells[0,j]:=inttostr(i);
form1.StringGrid1.RowCount:=form1.StringGrid1.RowCount+1;
j:=j+1;end;
end;
procedure TForm1.Button2Click(Sender: TObject);
var m,i,k:integer;a:Tarr; b:Tarr;
begin
randomize;
for i:=1 to F do begin
m:=random(10)+0;
b[i]:=m;
end;
for i:=1 to F do begin
Edit3.Text:=Edit3.Text+inttostr(b[i]);end;
end;
procedure TForm1.Button3Click(Sender: TObject);
var i,j,n,p,q,d:integer;
b:array[1..100] of string;
begin
D:=0;
for i:=1 to 10 do begin
EDIT4.TEXT:=EDIT4.TEXT+COPY(EDIT1.Text,I,27-I);
for j:=D+1 to 26-D do begin
Stringgrid1.Cells[J,i]:=Edit4.text[J];
end;
EDIT4.CLEAR;
end;
for i:=2 to 10 do begin
p:=28-i; n:=1;
for j:=p to 26 do begin
stringgrid1.Cells[j,i]:=edit1.Text[n];
n:=n+1;
end;
end;
end;
procedure TForm1.Edit2Change(Sender: TObject);
begin
R:=Edit2.Text;
F:=length(R);
end;
procedure TForm1.Button4Click(Sender: TObject);
var m,i,t,j:integer; //Шифрлеу процедурасы
begin
for j:=1 to F do begin
for i:=1 to 26 do begin
if Edit2.Text[j]=stringgrid1.Cells[i,0] then
for m:=1 to 10 do begin
if Edit3.Text[J]=stringgrid1.Cells[0,m] then
Edit5.Text:=Edit5.Text+Stringgrid1.Cells[i,m]; end; end; end;
end;
procedure TForm1.Button5Click(Sender: TObject);
var m,i,t,j:integer;
begin
for j:=1 to F do begin
for i:=1 to 10 do begin
if Edit3.Text[j]=stringgrid1.Cells[0,i] then
for m:=1 to 26 do begin
if Edit5.Text[j]=stringgrid1.Cells[m,i] then
Edit6.Text:=Edit6.Text+Stringgrid1.Cells[m,0]; end; end; end;
end;
procedure TForm1.FromClose(Sender: TObject; var Action: TCloseAction);
begin
AnimateWindow(Handle, 500, AW_BLEND or AW_Hide);
end;
procedure TForm1.FromShow(Sender: TObject);
begin
AnimateWindow(Handle, 500, AW_CENTER or AW_Slide);
end;
procedure TForm1.Button6Click(Sender: TObject);
begin
close;
end;
end.
58
Симметриялық алгоритмдер
Блоктық шифр
Ағындық шифр
Құрама шифр
Ауыстыру
Құрастырма шифр
Орын алмастыру
Синхрондық
Өзіндік синхронданатын
Кіріс блогі (64 бит)
Бастапқы орын алмастыру
Li-1
Ri-1
Кеңейту проц
S-блок ауыстыру
Орын алмастыру (Р-блок)
Li
Ri
Ki
Соңғы орын алмастыру (64 бит)
Кілт
әр 8-ші битті алып тастау
жылжыту
Бастапқы орын алмастыру
Бөлімдік кілт Ki,, i=1..16
жылжыту
Сығылатын орын алмастыру
K’ = yAKB (mod n)
K = yBKA (mod n)
yA = gKD (mod n)
yA = gKA (mod n)
КВ құпия кілті
КА құпия кілті
g, n
g, n
Кілт тізбегінің генераторы
