Ақпаратты қорғау мәселесінің криптографиялық негіздері

МАЗМҰНЫ

КІРІСПЕ 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
КІРІСПЕ
Қазіргі кезде ақпаратты қорғау жалпы ұлттық мәселеге айналып отыр. Информациялық технологияның қарқынды дамуы және Интернеттің тез таралуы конфиденциалды ақпаратты қорғаудың әдістерін дамытуға, әсіресе криптографияның дамуына көп әсер етті.
Мемлекеттің барлық салаларына қатысты ақпарат нақты саяси, материалдық және бағалылығы жағынан да құнды болып саналады. Ақпаратты қорғау мемлекеттің көзқарасымен алғанда қазіргі кезде өзекті мәселеге айналды және мемлекет алдындағы бірден-бір шешілуі қажет, ұлттық қауіпсіздіктің негізгі элементі ретінде қарастырылып отыр.
Жаңа қуатты компьютерлердің, желілік технологиялардың пайда болуы мен ақпараттың компьютерде шоғырлануы мүлдем ашылмайды деп саналған криптография жүйесін пайдалануға мүмкіндік береді.
Криптография термині ежелгі гректердің «cryptos – құпия» және «grapho – жазу» сөздерінен құралған.
Бітіру жұмысымның мақсаты:
1) ақпараттық ресурстардың сыртқа кетуін, ұрлануын, жоғалуын, бұрлануын, қолдан жасалуын, оларға рұқсатсыз қол жеткізуді пайдалануды және таратуды, зиян, залал келтіруді болғызбау;
2) тұлғаның, мемлекеттің және қоғамның ақпараттық қауіпсіздігі;
3) ақпаратты қорғаудың математикалық жолдарын (яғни, математикалық әдістерін немесе қулықтарын) және ақпаратты қорғаудың математикалық мәселелерін шешу;
4) математиканы және жалпы білімді дәріптеу.
Бітіру жұмысымның өзектілігі. Криптография қоғам өмірінің ажырымас бөлігіне айналып келеді. Мыңдаған жылдар бойы криптография әскери және дипломатикалық байланыстарды қорғау үшін қолданылып келеді. Информациялық ғасырдың басталуымен бірге криптографияның жеке секторлары да қоғамға жедел қажет екендігін байқалтты.
Ақпаратты қорғаудың әртүрлі жолдары (мысалы, механикалық немесе физикалық), әртүрлі мәселелері бар (мысалы, қоғамдық немесе әскери). Мен ақпаратты қорғаудың математикалық жолдарын (яғни, математикалық әдістерін немесе қулықтарын) және ақпаратты қорғаудың математикалық мәселелерін қарастырамын.
Бітіру жұмысымның міндеттері. Ақпаратты қорғау әдістері мен ақпаратты шифрлеу жүйелері жайлы мағлұмат беру. Сонымен қатар криптографияның математикалық негіздері болып табылатын симметриялық және ашық кілтті криптожүйелер туралы ашып айту. Ашық кілтті криптожүйеде кілт басқару қалай жүзеге асатынын көрсету. 1 КРИПТОГРАФИЯНЫҢ МАТЕМАТИКАЛЫҚ НЕГІЗДЕРІ
ҚОЛДАНЫЛҒАН ӘДЕБИЕТТЕР
1 Ященко В.В. Введение в криптографию : 3-е издание /В. В. Ященко.– Москва : МЦНМО-ЧеРо, 2000.- 288 с.
2 Анин Б. Защита компьютерной информации /Б. Анин.– Санкт-Петербург : 2000.- 384 с.
3 Романьков В.А. Введение в криптографию : Методическое указание /В. А. Романьков.– Усть – Каменогорск : ВКГУ, 2003.- 43 с.
4 Молдовян Н.А. Введение в криптосистемы с открытом ключом/ Н. А. Молдовян, А. А. Молдовян.– Санкт–Петербург : БХВ–Петербург, 2005.- 286 с.
5 Молдовян А.А. Криптография: Учебник для вузов/ А. А. Молдовян.– Санкт-Петербург : Лань, 2001.– 224 с.
6 Байсалов Е.Р. Криптографияның математикалық негіздері : Оқу құралы/ Е. Р. Байсалов.– Алматы : Қазақ университеті, 2003.
7 Өтелбаев М. Ақпарат қорғау мен криптография негіздері : Оқу құралы/ М. Өтелбаев, С. Зәуірбеков.- Астана : Нұржол, 2003.- 128 б.
8 Қажиакпарова Ж.С. Есептеу техникасы және бағдарламалық қамтамасыз ету мамандығы студенттеріне криптография негіздерін оқыту әдістемесі/ Ж. С. Қажиакпарова.– Алматы, 2007.– 22 б.
9 Баричев С.В. Криптография без секретов/ С. В. Баричев.– Москва : Наука, 1998.– 120 с.
10 Турецкий В.Я. Математика и информатика : 3-е издание/ В. Я. Турецкий. – Москва : Инфра-М, 2000.
11 Мүсірәлиева Ш.Ж. Қолданбалы криптография/ Ш. Ж. Мүсірәлиева.– Алматы : Prints, 2004.- 68 б.
12 Касперски К. Техника защиты компакт-дисков от копирования/ К.Касперски.- Санкт–Петербург : БХВ–Петербург, 2004.- 455 с.
13 Задирака В.К. Элементы современной криптологии и методы защиты банковской информации/ В. К. Задирака, К. А. Абдикаликов.– Алматы, 1999.
14 Романец Ю.В. Защита информации в компьютерных системах и сетях/ Ю. В. Романец.– Москва : Радио и связь, 1999.
15 Алексеев А.П. Изучение криптографии на уроках информатики/ А. П.Алексеев// Информатика и образование.– 2003.- №4.– С. 33-42.
16 Картье. Защита информации: криптография без границ/ Картье // Деловой мир Астана.– 2001.- №3.– С. 44-45.
17 Ларин Д.А. Электронный задачник по основам криптографии/ Д. А.Ларин // Дистанционное образование.– 1998.- №6.– С. 19-22.
18 Нестеров С. Криптография в устройствах защиты информации: Назови хоть горшком/ С.Нестеров // Мир Internet http://www.iworld.ru.- 1999. - №12.– С. 74-78.
19 Нурбекова Ж. Программные средства обучения криптографическим методом/ Ж.Нурбекова// Ұлт тағылымы.- 2006.- №3.– С. 92-95.
20 Остроумов Г. Тайнопись-от пирамид до компьютеров: О некоторых осбенностях шифров и методах шифрования/ Г.Остроумов//Наука и жизнь- 1996.- №1.– С. 144-150.
        
        АҚПАРАТТЫ ҚОРҒАУ МӘСЕЛЕСІНІҢ КРИПТОГРАФИЯЛЫҚ НЕГІЗДЕРІ
МАЗМҰНЫ
КІРІСПЕ 3
1 ... ... ... 4
1.1 Модулярлық арифметиканы есептеу ... ... ... ... ... ... ... ... ... ... кері ... ... ... Тура ... әдісі
12
1.4.2 Эйлер ... ... кері ... ... ... ... кеңейтілген алгоритмі көмегімен кері шамаларды есептеу 13
2 ШИФРЛЕУ АЛГОРИТМДЕРІ ... ... ... ... ... ... ... Ағындық шифрлар ... ... ... ... ... алгоритмдер ... RSA ... ... ...... ... ... Эль-Гамаль алгоритмі 40
3 АШЫҚ ... ... КІЛТ ... ... ... ... PGP қауіпсіз электрондық поштасы 44
4 ... ... ... ... ... ... А ... кезде ақпаратты қорғау жалпы ұлттық мәселеге айналып отыр.
Информациялық ... ... ... және ... тез ... ... қорғаудың әдістерін дамытуға, әсіресе
криптографияның дамуына көп әсер ... ... ... ... ақпарат нақты саяси,
материалдық және ... ... да ... ... ... ... ... көзқарасымен алғанда қазіргі кезде өзекті мәселеге
айналды және мемлекет ... ... ... ... ... негізгі элементі ретінде қарастырылып отыр.
Жаңа қуатты компьютерлердің, ... ... ... ... ... компьютерде шоғырлануы мүлдем ашылмайды деп саналған
криптография жүйесін ... ... ... термині ежелгі гректердің «cryptos – ... ...... ... ... ... мақсаты:
1) ақпараттық ресурстардың сыртқа кетуін, ұрлануын, жоғалуын, бұрлануын,
қолдан жасалуын, оларға ... қол ... ... ... ... залал келтіруді болғызбау;
2) тұлғаның, мемлекеттің және қоғамның ақпараттық қауіпсіздігі;
3) ... ... ... ... ... ... ... қулықтарын) және ақпаратты қорғаудың математикалық
мәселелерін шешу;
4) математиканы және жалпы білімді дәріптеу.
Бітіру жұмысымның ... ... ... өмірінің ажырымас
бөлігіне айналып келеді. Мыңдаған жылдар бойы криптография әскери және
дипломатикалық байланыстарды ... үшін ... ... ... басталуымен бірге криптографияның жеке секторлары да қоғамға
жедел қажет екендігін байқалтты.
Ақпаратты қорғаудың ... ... ... механикалық немесе
физикалық), әртүрлі мәселелері бар (мысалы, қоғамдық немесе әскери). Мен
ақпаратты ... ... ... ... ... ... ... және ақпаратты қорғаудың математикалық мәселелерін
қарастырамын.
Бітіру жұмысымның міндеттері. Ақпаратты ... ... мен ... ... ... ... беру. Сонымен қатар криптографияның
математикалық негіздері болып табылатын ... және ашық ... ... ашып ... Ашық кілтті криптожүйеде кілт басқару қалай
жүзеге асатынын көрсету. 1 ... ... ... ... ... ... ... көбінде жай ... ... ... ... ... ... айтатын болсақ, қосу
мен көбейту операцияларын қолданатын n модулі бойынша ... ... ... ... ... ... отырып,
коммутативтік сақина құрайды.
Негізінен модулярлық арифметиканың жазылуы төмендегідей түрде:
а ≡ b (mod n), бұл «n ... ... а және b ... салыстырмалы»
деп оқылады.
Бұл ара қатынас бүтін мәндер а,b және n ≠ 0, егер а = b + k*n ... ... ... үшін тура.
Бұдан шығатыны n‌‌‌‌ ‌| (a-b), бұл «n (a-b)-ға бөлінеді» деп оқылады.
Егер бұл қатынас орындалса, онда b ... n ... ... ... саны деп аталады. Шегеру санын табу операциясын модуль бойынша
келтіру деп аталады.
Анықтама 1 Егер a-b ... n-ге ... ... ... а және ... ... n ... бойынша салыстырмалы деп аталады.
0-ден n - 1-ге дейінгі бүтін сандардың жиынтығын n ... ... ... жиынтығы деп атайды.
n = 7, { 0, 1, … , 6 }
n = 100, { 0, 1, … , 99 ... біз ... n ... ... ... ... ... операцияны
орындауымызға болады немесе алдымен операцияны, ... ... n ... ... мүмкін болады:
(a+b) mod n = ((a mod n) + (b mod n)) mod ... mod n = ((a mod n) - (b mod n)) mod ... mod n = ((a mod n) * (b mod n)) mod ... mod n = (((a*b) mod n) + ((a*c) mod n)) mod ... ... және түбiр квадратын есептеу қиын болғандықтан,
криптография n ... ... ... ... қолданылады. Сонымен қатар,
модуль бойынша есептеулермен жұмыс iстеу тиiмдiрек, ... олар ... ... мен ... ... шектейдi.
Анықтама 2 Модулі бойынша ... бір а ... ... ... ... деп аталады. Ол деп белгіленеді.
Мысал: 6 модулі бойынша сыныбы:
Модулярлық арифметиканы компьютерлік есептеулерге ... үшін ... қана ... ... ... ... ... Сондықтан
негізінен сыныбындағы ең кіші оң санымен жұмыс істейді. ... ... ... бар ... және де ол а-ны n-ге ... тең ... дәлелденген.
Ескерту. Программалау тілдерінде mod функциясы басқаша анықталуы
мүмкін.
Модулярлық арифметиканың артықшылығы:
1) Бүтін сандармен жұмыс істейміз;
2) ... ... ... супер өрісте орналасқан.
Мысалы. 13 mod 7 = 6, 0≤n≤n-1
7 mod 7 = 0, 4 mod 7 = 4, -1 mod 7 = ... ... ... ... ... ... n ... қосу, алу немесе көбейту сияқты аралық
нәтижелері 2к биттен ұзын болмайды. Сондықтан ... ... ... өте ... ... ... ... орындауға
болады.
n модулi бойынша а санының дәрежесiн ... ax mod n ... ... ... ... орындауға болады. Бұны тездету үшiн неше түрлi
әдiстерi бар. Бұл операциялар дистрибутивтi ... ... ... ... ... отырып, көбейту қатары ретiнде дәрежеге шығаруды
тездетiп ... Егер ұзын ... (200 бит және одан да көп) ... бұл ерекше белгiлi болады.
Мысалы, егер a8 mod n –дi есептеу керек болса, жетi рет қайта көбейту
мен модуль бойынша үлкен ... ... ... ... mod ... ... ... керегi жоқ.
Бұның орнына 3 кiшi көбейту мен 3 кiшi модуль ... ... mod n)2 mod n)2 mod ... ... a16 mod n = (((a2 mod n)2 mod n)2 mod n)2 mod ... бiраз ғана қиынырақ: ax mod n (4), мұндағы x 2-дәрежелі болып
табылмайды. x cанының екiлiк ... x ... ... қосындысы ретiнде
келтiрудi қолдайды:
x = 25(10) → 1 1 0 0 1(2), сондықтан 25 = 24 + 23 + 20 ... a25 mod n = (a*a24) mod n = ... mod n ... mod n = ((((a2*a)2)2)2*a) mod n деп аламыз.
Аралық нәтижелерде алты ғана көбейту амалы ... ... mod n)*a) mod n)2 mod n)2 mod n)2 mod n)*a) mod ... әдiс 1,5хк ... ... есептеуде қиындықты жеңiлдетедi,
мұндағы к – бит негiзiндегі ... ... ... ... n модулi бойынша дәрежеге шығаруға
негiзделген болғандықтан, тез ... ... ... қолдану орынды.
S = aW mod n мағынасын есептеу керек ... W ... 2 ... ... ... келтіреміз:
W = wg-12g-1 + wg-22g-2 + … + w222 + w121 + ... wi 0 ... ... = aW mod n – ді ... ... келтірейік:
S = aw mod n = aWg-12 + Wg-22 + … + W22 ... + W0 mod n = ... + Wg-22 + … + W22 ... mod n = ((a2)2) Wg-12 + Wg-22 + … ... mod n = ( ... … )2)Wg-1* ... mod ... 437 mod 26 = ((42)19 – 4) mod 26 = [(16 mod 26)19 - 4] mod 26 ... mod 26 - 4 = (256 mod 26)9*4 mod 26 - 4 = 229*4 mod 26 - ... mod 26 – 4 = (484 mod ... mod 26 = (16)4*22*4 mod 26 ... mod 26 = 222*22*4 mod 26 = 16*22*4 mod 26 = 16*88 mod 26 ... mod 26 = 160 mod 26 = ... [(223 mod 11)39 + (411 mod 7)19] mod ... (223 mod 11)39 = ... mod 11)39 = (55*23 mod 11)39 = ... 11)39 = (32*5*23 mod 11)39 = (45*23 mod 11)39 = 839
b) (411 mod 7)19 = ((42)5*4 mod 7)19 = (25*4 mod 7)19 = (23*22*4 mod ... (16 mod 7)19 = ... 839 mod 11 + 219 mod 11 = (82)19*8 mod 11 + (24)4*23 mod 11 = ... 11 + 54*23 mod 11 = ... mod 11 + (52)2*23 mod 11 = 49*9*8
mod 11 + 32*23 mod 11 = ... mod 11 + 32*23 mod 11 ... mod 11 + 6 = 32*4*9*8 mod 11 + 6 = 3*9*8 mod 11 + 6 = ... 11 + 6 = 7+6 = 13
d) 13 mod 11 = ... ... ... m = p1α 1 p2α 2 … ptα t , m>1 ... ... ... ... (m) = p1α 1-1(p1-1) p2α 2-1(p2-1) … ptα t -1(pt-1) және φ(1) = 1
болсын.
Сонымен натурал аргументті φ ... ... 1 ... ... әдіспен анықталған φ функциясы Эйлер
функциясы деп аталады.
Анықтама 2 Эйлер функциясы n-нан кіші және n-мен ... жай оң ... ... тең ... атайды. Функция φ(n) деп белгіленеді.
Мысалға, φ (10) = 4. Эйлер функциясының келесі тамаша қасиеті бар:
егер n = pq, ... p және q – жай ... онда φ(n) = ... тең
болады.
Теорема 1 (Эйлер) Кез-келген n модулі мен n-мен өзара жай а саны үшін
келесі салыстыру ақиқат
aφ(n)-1 ≡ 1(mod ... 3 ... үш ... ... θ ... деп атаймыз:
1) θ кез келген натурал сан үшін анықталған;
2) θ(1) = ... егер (a,b) = 1 ... онда θ(ab) = ... 2 ... ... – мултипликативті функция.
Дәлелдеуі. Айталық, p1α 1 … ptα t және q1β1 … qsβs ... жай ... m1>1 және m2>1 ... жай ... канондық жіктеулері
болсын. Онда p1, …, pt ... ... q1, …, qs ... ... ... m1m2 канондық жіктеуі p1α 1 … ptα t q1β1 ... φ (m1m2) = φ (m1) φ (m2) ... ... ... ... шығады. m1 = 1 немесе m2 = 1 үшін берілген теңдеу ... ... 3 φ (m) саны 1, 2, …, m ... ... m-мен ... ... ... санына тең.
Дәлелдеуі. Дәлелдеме m>1 санының канондық жіктеуіндегі жай көбейткіш
сандардың саны n бойынша математикалық ... ... ... жүргізіледі.
Теорема n = 0 (m = 1) және n = 1 (m = p) үшін орындалады, мұндағы p – ... Айта ... ... i натурал саны mp–мен өзара жай болу үшін ол бір
мезгілде m мен p ... ... жай ... ... және ... 1, 2, ... тізбегін талдау үшін ұзындығы m-ге тең p тізбекшелеріне mk+1, mk+2, …,
mk+m-бөлеміз, мұнда k = 0, 1, …, p-1. ... 3-тен (mk + i,m) = (i, ... Осы ... пен осы ... ... mk+1, mk+2, …, ... ... өзара жай φ (m) сан бар. Осыдан 1, 2, …, mp тізбегінде
m–мен өзара жай φ (m)p сан бар. M p-ға ... ... бұл ... ... жай, ... ... mp санымен де өзара жай. Соңғы ескерту мен айқын
теңдік φ (mp) = φ (m)p ... ... ... ... p-ға ... жағдайын қарастыру қалды. m-мен өзара жай ... ... ... ... p-ға ... санын алып
тастасақ, іздеген φ (mp) санын табамыз. Ол ... тек p, 2p, 3p, …, ... ... ғана болуы мүмкін. Сондықтан, m-мен өзара жай сандардың
арасындағы p-ға бөлінетіндерінің саны p, 2p, 3p, …, mp ... m-мен ... жай ... ... тең ... Егер i≤m және (m,p)
= 1 болғанда (ip,m) = (i,m) болатынын ескерсек, онда p, 2p, 3p, …, ... ... m-мен ... жай ... ... 1, 2, …, m ... m-мен өзара жай сандар санына тең, яғни индукция ... φ ... ... ... φ (mp) = φ (m)p - φ (m) = φ ... ... функциясының осы ... ... ... ... ... n ... саны жай сан деп саналады, егер де ол
тек өзіне ғана және 1-ге бөлінетін жағдайда a, n 2 ... ... ... ... деп ... егер ... ортақ бөлгіштері болмаса.
1. n = 7
1 2 3 4 5 6 ((7) = 6.
2. n = p*q, p,q ... ... ((n) = ... = 33 = 11*3, ((33) = ... = ... n = kr
((n) = (k-1)*kr-1, n = 8 = 23
((8) = ... = 1*4 = ... ... ... кері ... ... сандарды арифметикада а-1 мультипликативтi керi шаманы есептеу
қиынға түспейдi. Нөлдiк емес а үшiн: a-1 = ... а*а-1 = 1 ... ... керi шама 4 ... ¼-ке тең, ... = 1-ге тең ... модулярлық арифметикада керi шаманы есептеу қиын есеп болып
табылады. Мысалы, салыстыруды есептеу 4*x ≡ 1 (mod 7) х және к ... ... бұл 4*х ≡ 7*к + 1-ге тең, ... х және к - ... ... жалпы тұжырымы – х бүтiн санын табу, бұл дегенiмiз a*x
(mod n) = 1, ... ... a-1 ≡ x (mod n) деп ... ... ... шешiмi кейде болады, кейде болмайды. Мысалы, 14 модулi
бойынша 5 саны үшiн керi шама 3-ке тең, ... = 15 ≡ 1 (mod ... ... ... 14 ... ... 2 санында керi шама жоқ.
Егер а және n - өзара жай ... ... ... a-1 ≡ x (mod ... бiр ғана ... ... а және n сандары өзара жай сандар болмаса, онда салыстыру a-1 ≡
x (mod n) тең ... жоқ керi ... ... ... әдiсiн тұжырымдаймыз. a
{0, 1, 2, …, n-1} бүтiн сандар болсын. Егер ЕҮОБ(a, n) = 1, онда ... n), ... i = 0, 1, 2, …, n-1, {0, 1, 2, …, n - ... болып табылады.
Мысалы, егер a = 3 және n = 7 ... 7) = 1), онда 3*i (mod ... i = 0, 1, 2, …, n-1; 0, 3, 6, 2, 5, 1, 4 ... болып табылады.,
яғни {0, 1, 2, …, 6}жиынтығын алмастыру болып табылады.
Егер ЕҮОБ(a, n) ≠ 1 болса, ... ... ... ... емес
болып шығады. Мысалы, егер a = 2 және n = 6 болса, онда 2*i (mod 6) ≡ 0, ... 0, 2, 4 ... i = 0, 1, 2, …, 5 ... ... n) = 1, онда a-1 керi сан бар ... және де дәл осындай
түрде болады:
a*a-1 ≡ 1 (mod n)
Шындығында да, a*i (mod n) 0, 1, …, n-1 ... ... ... i бар ... және ... ... болады:
a*i ≡ 1 (mod n)
Мысалы, n = 11-жай сан ... 11 ... ... ... ... {0, 1, 2, …, ... шегеру жиынын тұжырымдаған кезде олардың iшiнен бiр ғана
элемент – 0 өшiрiледi. Келтiрiлген ... ... 11 ... ... 11-1 = ... бар болады.
Жалпы келтiрiлген шегеру жиынында n модуль бойынша жай ... ... бар ... функциясы φ(n) шегеру жиынтығында келтірілген элементтер санын
мінездейді. Төмендегі кестеден көруге болады.
Кесте 1 Эйлер функциясы
|Модуль n ... φ(n) |
|N – жай сан |n-1 ... |n(n-1) ............ ... ... (p, q – жай ... ... ............ жай сан) | ... ... ... ... ... егер ... және ЕҮОБ(a,
n) = 1, онда an-1 ≡ 1 (mod n) болады.
Эйлердiң қортуына сәйкес Ферманың кiшене теоремасынан: eгер ... = 1, онда aφ(n) ≡ 1 (mod n)-ге ... ... ... негiзгi 3 әдiсі бар. Олар: тура іріктеу әдісі,
евклидтің кеңейтілген алгоритмі көмегімен кері шамаларды ... ... ... ... кері шамаларды есептеу әдісі. Соларға тоқталайық.
1.4.1 Тура іріктеу әдісі
a-1 ≡ 1 (mod n) ... ... ... a*a-1 (mod n) ≡ 1
теңдікті 1, 2, …, n-1 кезектi мәндерiн қою ... ... x = a-1 (mod n) ... дейiн, 1, 2, …, n-1 кезектi
мәндерiн тексеру, осындай a*x ≡ 1 (mod n) ... ... = 7, ал a = 5 ... x = a-1 (mod n)–дi табу ... ≡ 1 (mod n) ... 5*х ≡ 1 (mod 7).
n - 1 = 7 - 1 = 6
x = 5-1 (mod 7) = 3 - тi ... 1 Тура ... ... ... |5*x |5*x (mod 7) |
|1 |5 |5 |
|2 |10 |3 |
|3 |15 |1 |
|4 |20 |6 |
|5 |25 |4 |
|6 |30 |2 ... ... ... көмегімен кері шамаларды есептеу
Eгер Эйлер φ(n) функциясы белгiлi болса, онда ... тез ... ... ... a-1 (mod n) ≡ aφ(n) – 1 (mod n) ... ... 1 Эйлер функциясы көмегімен кері шамаларды есептеу
|Модуль n ... φ(n) |
|n |n-1 ... |r(n-1) ... ... |
|n = p*q ... ... а және n ... жай ... ... a-1 x(mod ... бір ғана ... қажет етеді. Егер а және n өзара жай
сандар болмаса, онда бұл ... ... ... ... Эйлер функциясы белгілі болса, онда кері ... ... (mod n) = aφ(n-1) (mod ... a-1 (mod n) –дi табу ... егер Эйлер φ(n) функциясы белгiлi
болса.
n = 7, ал a= 5 болсын. x = a-1 (mod n) = 5-1 (mod 7 )–нi табу ... = 7 ... – жай сан. ... Эйлер функциясы φ(n) = φ(7) = ... шама 5-тен 7 – ге ... ... ... (mod n) = aφ(n) – 1 (mod n) = 56-1 mod 7 = 55 mod 7 = (52 ... mod 7) mod 7 = (25 mod 7)(125 mod 7) mod 7 = (4*6) mod 7 = 24 mod 7 ... x = 5-1 (mod 7) = 3-ке ... Евклидтің кеңейтілген алгоритмі көмегімен кері ... ... φ(n) ... ... болмаса, кеңейтiлген Евклид
алгоритмiн қолдануға болады.
Евклид алгоритмнің алгебрада, тіпті ... ... ... өте ... Оң ... r0>r1>0 сандары берілсін. Олардың ең үлкен ортақ
бөлгішін (ЕҮОБ) табу үшін төмендегі қалдықпен бөлу тізбегін іске асырамыз:
r0 = q1r1 + r2, 0

Пән: Информатика
Жұмыс түрі: Дипломдық жұмыс
Көлемі: 49 бет
Бұл жұмыстың бағасы: 900 теңге









Ұқсас жұмыстар
Тақырыб Бет саны
Ақпараттық қауіпсіздік түрлері14 бет
Жадыны Windows NT,Unix операциялық жүйелерінде қорғау13 бет
АЖ-ді қорғаудың криптографиялық құралдары5 бет
Ақпаратты қорғау және криптографияның математикалық негіздері28 бет
Ақпаратты қорғаудың криптографиялық әдісі5 бет
Ақпараттық криптографиялық қорғалуы21 бет
Криптографиялық қорғау26 бет
Адам өмірінің мәні21 бет
Орыс, қазақ ғалымдарының қазақ этногинезін зерттеу тарихы11 бет
«Ана тілі» газетінде термин мәселесінің жазылуы64 бет


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


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

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

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

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

Email: info@stud.kz

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

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