Модулярлық арифметикада кері шамаларды есептеу
АҚПАРАТТЫ ҚОРҒАУ МӘСЕЛЕСІНІҢ КРИПТОГРАФИЯЛЫҚ НЕГІЗДЕРІ
МАЗМҰНЫ
КІРІСПЕ
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
Ақпаратты қорғау мәселесінің криптографиялық негіздері
Бөлшек ұғымы
Аралас сандарды көбейту
Жай бөлшектерге амалдар қолдану
Жай бөлшектер
Математика ғылымының тарихы
Теріс Сандар арифмет
Шапшаң есептеудің кейбір әдістері
Сандар әлемінің сырлары
Мектеп математикасының тарихи мағлұматтары