Ақпаратты қорғау мәселесінің криптографиялық негіздері
МАЗМҰНЫ
КІРІСПЕ 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
КІРІСПЕ 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 КРИПТОГРАФИЯНЫҢ МАТЕМАТИКАЛЫҚ НЕГІЗДЕРІ
Қазіргі кезде ақпаратты қорғау жалпы ұлттық мәселеге айналып отыр. Информациялық технологияның қарқынды дамуы және Интернеттің тез таралуы конфиденциалды ақпаратты қорғаудың әдістерін дамытуға, әсіресе криптографияның дамуына көп әсер етті.
Мемлекеттің барлық салаларына қатысты ақпарат нақты саяси, материалдық және бағалылығы жағынан да құнды болып саналады. Ақпаратты қорғау мемлекеттің көзқарасымен алғанда қазіргі кезде өзекті мәселеге айналды және мемлекет алдындағы бірден-бір шешілуі қажет, ұлттық қауіпсіздіктің негізгі элементі ретінде қарастырылып отыр.
Жаңа қуатты компьютерлердің, желілік технологиялардың пайда болуы мен ақпараттың компьютерде шоғырлануы мүлдем ашылмайды деп саналған криптография жүйесін пайдалануға мүмкіндік береді.
Криптография термині ежелгі гректердің «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.
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.
Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Дипломдық жұмыс
Тегін: Антиплагиат
Көлемі: 54 бет
Таңдаулыға:
Жұмыс түрі: Дипломдық жұмыс
Тегін: Антиплагиат
Көлемі: 54 бет
Таңдаулыға:
АҚПАРАТТЫ ҚОРҒАУ МӘСЕЛЕСІНІҢ КРИПТОГРАФИЯЛЫҚ НЕГІЗДЕРІ
МАЗМҰНЫ
КІРІСПЕ 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.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-ге қалдықсыз бөлінетін болса а және b
бүтін сандарын 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 n
(a-b) mod n = ((a mod n) - (b mod n)) mod n
(a*b) mod n = ((a mod n) * (b mod n)) mod n
(a*(b+c)) mod n = (((a*b) mod n) + ((a*c) mod n)) mod n
Дискреттiк логарифм және түбiр квадратын есептеу қиын болғандықтан,
криптография n модулi бойынша көптеген есептер қолданылады. Сонымен қатар,
модуль бойынша есептеулермен жұмыс iстеу тиiмд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 = 6.
1.2 Дәрежеге шығару алгоритмі
К биттi ұзындықты n модулiнiң қосу, алу немесе көбейту сияқты аралық
нәтижелері 2к биттен ұзын болмайды. Сондықтан модулярлық арифметикада
дәрежеге шығаруды өте үлкен аралық нәтижелердің генерациясынсыз орындауға
болады.
n модулi бойынша а санының дәрежесiн есептеудi ax mod n kөбейту мен
бөлудiң қатары ретiнде орындауға болады. Бұны тездету үшiн неше түрлi
әдiстерi бар. Бұл операциялар дистрибутивтi болғандықтан, модуль бойынша
келтiрудi әркез орындай отырып, көбейту қатары ретiнде дәрежеге шығаруды
тездетiп орындау. Егер ұзын сандармен (200 бит және одан да көп) жұмыс
жасаса, бұл ерекше белгiлi болады.
Мысалы, егер a8 mod n –дi есептеу керек болса, жетi рет қайта көбейту
мен модуль бойынша үлкен санды бiреуге келтiруге (a*a*a*a*a*a*a) mod n
примитивтi жақындау қолданып керегi жоқ.
Бұның орнына 3 кiшi көбейту мен 3 кiшi модуль бойынша келтiру
орындалады:
((a2 mod n)2 mod n)2 mod n
Осы әдiспен a16 mod n = (((a2 mod n)2 mod n)2 mod n)2 mod n
есептелiнедi.
Есептеу бiраз ғана қиынырақ: ax mod n (4), мұндағы x 2-дәрежелі болып
табылмайды. x cанының екiлiк жазуы x санын 2-дәрежелердiң қосындысы ретiнде
келтiрудi қолдайды:
x = 25(10) → 1 1 0 0 1(2), сондықтан 25 = 24 + 23 + 20 тең
болады.
Онда a25 mod n = (a*a24) mod n = (a*a8*a16) mod n =
a*((a2)2)2*(((a2)2)2)2 mod n = ((((a2*a)2)2)2*a) mod n деп аламыз.
Аралық нәтижелерде алты ғана көбейту амалы керек болады:
(((((((a2 mod n)*a) mod n)2 mod n)2 mod n)2 mod n)*a) mod n
Бұл әдiс 1,5хк операциясына дейiн есептеуде қиындықты жеңiлдетедi,
мұндағы к – бит негiзiндегі сандар ұзындығы.
Көптеген шифрлеу алгоритмi n модулi бойынша дәрежеге шығаруға
негiзделген болғандықтан, тез дәрежеге шығару алгоритмiн қолдану орынды.
S = aW mod n мағынасын есептеу керек болсын. W дәрежесін 2 санын
дәрежеге үлестіру түрінде келтіреміз:
W = wg-12g-1 + wg-22g-2 + ... + w222 + w121 + w0
мұндағы wi 0 немесе 1сандары.
S = aW mod n – ді келесі түрде келтірейік:
S = aw mod n = aWg-12 + Wg-22 + ... + W22 +
W12 + W0 mod n = (a2)Wg-12 + Wg-22 + ... + W22 +
W12*aw0 mod n = ((a2)2) Wg-12 + Wg-22 + ... +
W22*(a2)W1*aW0 mod n = ( ...((a2)2 ... )2)Wg-1* ...
*(a8)W3*(a4)W2*(a2)W1*aW0 mod n.
Мысалдар:
1) 437 mod 26 = ((42)19 – 4) mod 26 = [(16 mod 26)19 - 4] mod 26 =
(162)9*4 mod 26 - 4 = (256 mod 26)9*4 mod 26 - 4 = 229*4 mod 26 - 4=
(222)4*22*4 mod 26 – 4 = (484 mod 26)4*22*4 mod 26 = (16)4*22*4 mod 26 =
(162)2*22*4 mod 26 = 222*22*4 mod 26 = 16*22*4 mod 26 = 16*88 mod 26 =
16*10 mod 26 = 160 mod 26 = 4.
2) [(223 mod 11)39 + (411 mod 7)19] mod 11
a) (223 mod 11)39 = ((24)5*23 mod 11)39 = (55*23 mod 11)39 = ((52)2*5*23
mod 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 7)19
= (16 mod 7)19 = 219
c) 839 mod 11 + 219 mod 11 = (82)19*8 mod 11 + (24)4*23 mod 11 = (9)19*8
mod 11 + 54*23 mod 11 = (92)9*9*8 mod 11 + (52)2*23 mod 11 = 49*9*8
mod 11 + 32*23 mod 11 = (42)4*4*9*8 mod 11 + 32*23 mod 11 =
(52)2*4*9*8 mod 11 + 6 = 32*4*9*8 mod 11 + 6 = 3*9*8 mod 11 + 6 = 5*8
mod 11 + 6 = 7+6 = 13
d) 13 mod 11 = 2.
1.3 Эйлер функциясы
Айталық, m = p1α 1 p2α 2 ... ptα t , m1 натурал санының Канондық
жіктелуі болсын.
φ (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) = (p-1)(q-1)-ге тең
болады.
Теорема 1 (Эйлер) Кез-келген n модулі мен n-мен өзара жай а саны үшін
келесі салыстыру ақиқат
aφ(n)-1 ≡ 1(mod n)
Анықтама 3 Келесі үш шартты қанағаттандыратын θ функциясын
мультипликативті деп атаймыз:
1) θ кез келген натурал сан үшін анықталған;
2) θ(1) = 1;
3) егер (a,b) = 1 болса, онда θ(ab) = θ(a)θ(b).
Теорема 2 Эйлер функциясы – мултипликативті функция.
Дәлелдеуі. Айталық, p1α 1 ... ptα t және q1β1 ... qsβs сәйкесінше
өзара жай натурал m11 және m21 өзара жай сандарының канондық жіктеулері
болсын. Онда p1, ..., pt сандарының әрқайсысы q1, ..., qs сандарының
әрқайсысына өзгеше. Бұдан m1m2 канондық жіктеуі p1α 1 ... ptα t q1β1 ...
qsβs. φ (m1m2) = φ (m1) φ (m2) теңдеуі, Эйлер функциясының анықтамасынан
тікелей шығады. m1 = 1 немесе m2 = 1 үшін берілген теңдеу айқын. Теорема
дәлелденді.
Теорема 3 φ (m) саны 1, 2, ..., m сандық тізбегіндегі m-мен өзара жай
болатын сандардың санына тең.
Дәлелдеуі. Дәлелдеме m1 санының канондық жіктеуіндегі жай көбейткіш
сандардың саны n бойынша математикалық индукция әдісі бойынша жүргізіледі.
Теорема n = 0 (m = 1) және n = 1 (m = p) үшін орындалады, мұндағы p – жай
сан. Айта кетерлік жайт, i натурал саны mp–мен өзара жай болу үшін ол бір
мезгілде m мен p сандарымен өзара жай болуы қажет және жеткілікті. 1, 2, ...,
mp тізбегін талдау үшін ұзындығы m-ге тең p тізбекшелеріне mk+1, mk+2, ...,
mk+m-бөлеміз, мұнда k = 0, 1, ..., p-1. Теорема 3-тен (mk + i,m) = (i, m)
шығады. Осы теңдік пен осы индуктивті ұйғарымнан mk+1, mk+2, ..., mk+m
тізбекшесінде m–мен өзара жай φ (m) сан бар. Осыдан 1, 2, ..., mp тізбегінде
m–мен өзара жай φ (m)p сан бар. M p-ға бөлінетін жағдайда, бұл сандар p-мен
өзара жай, сонымен қатар mp санымен де өзара жай. Соңғы ескерту мен айқын
теңдік φ (mp) = φ (m)p қарастырылған жағдайдағы теореманың ұйғарымын
дәлелдейді.
m-нің p-ға бөлінбейтін жағдайын қарастыру қалды. m-мен өзара жай φ
(m)p сандарының санынан осылардың p-ға бөлінетіндерінің санын алып
тастасақ, іздеген φ (mp) санын табамыз. Ол сандар тек p, 2p, 3p, ..., mp
сандарының арасында ғана болуы мүмкін. Сондықтан, m-мен өзара жай сандардың
арасындағы p-ға бөлінетіндерінің саны p, 2p, 3p, ..., mp сандарының
арасындағы m-мен өзара жай сандардың санына тең болады. Егер i≤m және (m,p)
= 1 болғанда (ip,m) = (i,m) болатынын ескерсек, онда p, 2p, 3p, ..., mp
сандарының арасындағы m-мен өзара жай сандар саны. 1, 2, ..., m сандарының
арасындағы m-мен өзара жай сандар санына тең, яғни индукция бойынша φ (m).
Қорыта келе, ізделінді φ (mp) = φ (m)p - φ (m) = φ (m)(p-1). Теорема
дәлелденді.
Эйлер функциясының осы қасиетінің берілген дәлелдемесін
Р.А.Сүйіндіков ұсынды.
Мысалдар: Берілген n натурал саны жай сан деп саналады, егер де ол
тек өзіне ғана және 1-ге бөлінетін жағдайда a, n 2 натурал сандар өзара
жай сандар деп саналады, егер олардың ортақ бөлгіштері болмаса.
1. n = 7
1 2 3 4 5 6 ((7) = 6.
2. n = p*q, p,q –жай сандар, ((n) = (p-1)*(q-1)
n = 33 = 11*3, ((33) = (11-1)(3-1) = 20.
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к емес а үшiн: a-1 = немесе а*а-1 = 1 деп
есептейміз.
Мысалы, мультипликативтi керi шама 4 санынан ¼-ке тең, өйткенi
4* = 1-ге тең болғандықтан.
Ал модулярлық арифметикада керi шаманы есептеу қиын есеп болып
табылады. Мысалы, салыстыруды есептеу 4*x ≡ 1 (mod 7) х және к мәндерiн
табумен эквиваленттi, бұл 4*х ≡ 7*к + 1-ге тең, мұндағы х және к - бүтiн
сандар.
Бұл есептiң жалпы тұжырымы – х бүтiн санын табу, бұл дегенiмiз a*x
(mod n) = 1, басқаша осылай a-1 ≡ x (mod n) деп жазуға болады.
Бұл есептiң шешiмi кейде болады, кейде болмайды. Мысалы, 14 модулi
бойынша 5 саны үшiн керi шама 3-ке тең, өйткенi
5*3 = 15 ≡ 1 (mod 14)
Келесi жақтан қарасақ, 14 модулi бойынша 2 санында керi шама жоқ.
Егер а және n - өзара жай сандар болса, жалпы a-1 ≡ x (mod n)
салыстыруында бiр ғана нәтиже бар,.
Егер а және n сандары өзара жай сандар болмаса, онда салыстыру a-1 ≡
x (mod n) тең болады.
Нәтижесi жоқ керi шаманы табудың негiзгi әдiсiн тұжырымдаймыз. a
{0, 1, 2, ..., n-1} бүтiн сандар болсын. Егер ЕҮОБ(a, n) = 1, онда a*i
(mod n), мұндағы i = 0, 1, 2, ..., n-1, {0, 1, 2, ..., n - 1}жиынтығын
алмастыру болып табылады.
Мысалы, егер a = 3 және n = 7 (ЕҮОБ(3, 7) = 1), онда 3*i (mod 7),
мұндағы i = 0, 1, 2, ..., n-1; 0, 3, 6, 2, 5, 1, 4 жүйелiк болып табылады.,
яғни {0, 1, 2, ..., 6}жиынтығын алмастыру болып табылады.
Егер ЕҮОБ(a, n) ≠ 1 болса, жоғарыда келтірілген мысал дұрыс емес
болып шығады. Мысалы, егер a = 2 және n = 6 болса, онда 2*i (mod 6) ≡ 0, 2,
4, 0, 2, 4 мұндағы i = 0, 1, 2, ..., 5 болады.
Егер ЕҮОБ(a, 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 модуль бойынша шегерудiң толық
жиыны {0, 1, 2, ..., 10}.
Келтiрiлген шегеру жиынын тұжырымдаған кезде олардың iшiнен бiр ғана
элемент – 0 өшiрiледi. Келтiрiлген шегеру жиыны 11 модулi бойынша 11-1 = 10
элементi бар болады.
Жалпы келтiрiлген шегеру жиынында n модуль бойынша жай санының n-1
элементi бар болады.
Эйлер функциясы φ(n) шегеру жиынтығында келтірілген элементтер санын
мінездейді. Төмендегі кестеден көруге болады.
Кесте 1 Эйлер функциясы
Модуль n Функция φ(n)
N – жай сан n-1
n2 n(n-1)
· ·
· ·
· ·
nr nr-1(n-1)
P*q (p, q – жай сандар) (p-1)(q-1)
· ·
· ·
· ·
(p– жай сан)
Басқаша айтқанда, Ферманың кiшкене теоремасы: егер n–жай және ЕҮОБ(a,
n) = 1, онда an-1 ≡ 1 (mod n) болады.
Эйлердiң қортуына сәйкес Ферманың кiшене теоремасынан: eгер ЕҮОБ(a,
n) = 1, онда aφ(n) ≡ 1 (mod n)-ге тең.
Керi шаманы табудың негiзгi 3 әдiсі бар. Олар: тура іріктеу әдісі,
евклидтің кеңейтілген алгоритмі көмегімен кері шамаларды есептеу әдісі,
Эйлер функциясы көмегімен кері шамаларды есептеу әдісі. Соларға тоқталайық.
1.4.1 Тура іріктеу әдісі
a-1 ≡ 1 (mod n) табылмағанға дейiн, осындай 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) түрде болады.
n = 7, ал a = 5 болсын. x = a-1 (mod n)–дi табу керек.
а*x ≡ 1 (mod n) немесе 5*х ≡ 1 (mod 7).
n - 1 = 7 - 1 = 6
x = 5-1 (mod 7) = 3 - тi аламыз.
Кесте 1 Тура іріктеу әдісінің мысалы
x 5*x 5*x (mod 7)
1 5 5
2 10 3
3 15 1
4 20 6
5 25 4
6 30 2
1.4.2 Эйлер функциясы көмегімен кері шамаларды есептеу
Eгер Эйлер φ(n) функциясы белгiлi болса, онда дәрежеге тез шығару
алгоритмiн қолдана отырып a-1 (mod n) ≡ aφ(n) – 1 (mod n) табуға болады.
Кесте 1 Эйлер функциясы көмегімен кері шамаларды есептеу
Модуль n Функция φ(n)
n n-1
n2 r(n-1)
nr nr-1(n-1)
n = p*q (p-1)(q-1)
Егер а және n өзара жай сандар болса, a-1 x(mod n)
салыстырылуы бір ғана есептеуін қажет етеді. Егер а және n өзара жай
сандар болмаса, онда бұл салыстыру есептеуді қажет етпейді.
Егер Эйлер функциясы белгілі болса, онда кері шаманы есептеуге
болады:
а-1 (mod n) = aφ(n-1) (mod n)
Мысалдар:
1. a-1 (mod n) –дi табу керек, егер Эйлер φ(n) функциясы белгiлi
болса.
n = 7, ал a= 5 болсын. x = a-1 (mod n) = 5-1 (mod 7 )–нi табу керек.
n = 7 модулi – жай сан. Сондықтан Эйлер функциясы φ(n) = φ(7) = n-1
=6.
Керi шама 5-тен 7 – ге дейiнгі аралықты қамтиды.
a-1 (mod n) = aφ(n) – 1 (mod n) = 56-1 mod 7 = 55 mod 7 = (52 mod
7)(53 mod 7) mod 7 = (25 mod 7)(125 mod 7) mod 7 = (4*6) mod 7 = 24 mod 7 =
3.
Нәтижесі x = 5-1 (mod 7) = 3-ке тең.
1.4.3 Евклидтің кеңейтілген алгоритмі көмегімен кері шамаларды
есептеу
Егер Эйлер φ(n) функциясы белгiлi болмаса, кеңейтiлген Евклид
алгоритмiн қолдануға болады.
Евклид алгоритмнің алгебрада, тіпті жалпы математикада атқаратын
ролі өте үлкен. Оң бүтін r0r10 сандары берілсін. Олардың ең үлкен ортақ
бөлгішін (ЕҮОБ) табу үшін төмендегі қалдықпен бөлу тізбегін іске асырамыз:
r0 = q1r1 + r2, 0r2r1
r1 = q2r2 + r3, 0r3r2
.
.
.
rm-2 = qm-1rm-1 + rm, 0rmrm-1
rm-1 = qmrm.
Енді негізгі нәтижені дәлелдеу қиын емес:
ЕҮОБ(r0, r1) = ЕҮОБ(r1, r2) = ... = ЕҮОБ(rm-1, rm) = rm
яғни, Евклид алгоритмін орындау нәтижесінде берілген сандардың ең
үлкен ортақ бөлгішін табамыз:
ЕҮОБ(r0, r1) = rm
Енді бұл алгоритмді былай кеңейтейік. Рекурренттік әдіспен
төмендегідей t0, t1, ..., tm сандар тізбегін анықтаймыз:
t0 = 0,
t1 = 1, және j≥2 үшін tj = tj-2 – qj-1tj-1 деп ұйғарамыз.
Бұл тізбектің пайдасын келесі леммадан көреміз. Алдымен бір белгілеу
енгізейік: егер а, b сандары n-ге бөлгенде бірдей қалдық берсе, онда а, b
сандары n модулі бойынша тең дейміз және бұл қатынасты а ≡ b (mod n) деп
жазып көрсетеміз.
Лемма 1 Жоғарыда іске асырылған кеңейтілген Евклид алгоритмінде
пайда болатын сандар әрбір 0≤j≤m үшін ri ≡ tjr1 (mod r0) қатынасын
қанағаттандырады.
Дәлелдеуі: j бойынша индукция қолданамыз. Біріншіден, бастапқы мәндер
j = 0 және j = 1 үшін лемманың дұрыстығы айдан анық. Леммадағы қатынас j =
i - 1 және j = i – 2 үшін дұрыс деп ұйғарып (мұнда, әрине 2 ≤ i), оны і
үшін дәлелдейік.
Сонымен, индукцияның ұйғарымы бойынша ri-2 ≡ ti-2r1 (mod r0) және ri-
1 ≡ ti-1r1 (mod r0) болады.
Ал енді ri –ді есептесек, алатынымыз:
ri = ri-2 – qi-1ri-1 ≡ ti-2r1 – qi-1ti-1r1 (mod r0) ≡ (ti-2 – qi-1ti-
1)r1 (mod r0) ≡ tir1 (mod r0).
Лемма дәлелденді.
Егер ab ≡ 1(mod n) болса, онда a,b сандары n модулі бойынша біріне-
бірі кері дейміз және a ≡ b-1 (mod n) немесе b ≡ a-1 (mod n) деп жазамыз.
Салдар 1 Егер ЕҮОБ(r0, r1) = 1 болса (бұл жағдайда r0, r1 сандары
өзара жай деп аталады), онда tm ≡ r1-1 (mod r0) деп аламыз.
Бұл алгоритм бойынша берілген теріс емес а, b бүтін сандары (U1, U2,
U3) векторларын анықтайды, ол келесі теңдікті қанағаттандыру тиіс.
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 тиіс және U3 = 1 егер aU1 + nU2 = ЕҮОБ (a, n)
= 1, басқаша айтқанда а теріс шамасы: a-1 (mod n) ≡ U1 (mod n)-ге тең.
Алгоритмнің негізгі қадамдары:
1) Бастапқы қойылым (U1, U2, U3) векторы анықталады;
(U1, U2, U3) = (0, 1, n)
(V1, V2, V3) = (1, 0, a)
2) U3 = 1 орындалса, алгоритмнің соңы;
3) q анықталады. q = div бөлгендегі бүтін бөлігі;
4) Қосалқы векторларды есептейді (t1, t2, t3).
(t1, t2, t3) = (U1, U2, U3) - q(V1, V2, V3)
(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 = 1.
Нәтижені қорытатын болсақ: Евклид алгоритмі бүтін сандардың ең үлкен
ортақ бөлгішін табуға қолданылады, ал кеңейтілген Евклид алгоритмі модуль
бойынша кері элеметті есептеп табуға (бар болса!) қолданылады
Керi a-1 (mod n) шамасын кеңейтiлген Евкид алгоритiмiнiн көмегiмен
табамыз.
Евклид алгоритмiн үлкен практикалық мәнi бар әдiспен қорытуға
болады. Бұл әдiсте ЕҮОБ(a, b) есептеуi кезiнде жолай u1 және u2 бүтiн
сандарын есептеуге болады, бұл
a* u1 + b* u2 = ЕҮОБ(a, b)
Бұл кеңейтiлген Евклид алгоритмiнiнiң қорытуын тиiмдi болады, егер
векторлық белгiлеулер қолданса.
2 ШИФРЛЕУ АЛГОРИТМДЕРІ
2.1 Симметриялық алгоритмдер
Симметриялы криптографиялық жүйелер ақпаратты қорғау саласында
классикалық жүйелер болып табылады. Мәліметті шифрлау және дешифрлау үшін
бір құпия кілт қолданылады. Симметриялық криптографиялық жүйедегі шифрлау
тәсілдерінің классификациясы 1 – суретте ұсынылады.
Сурет 1 Симметриялық криптографиялық жүйедегі шифрлау тәсілдерінің
классификациясы
Ақпаратты қорғаудағы криптографиялық өзгерту әдістері арнайы
алгоритмдердің немесе аппараттық шешімдердің және кілттердің кодтары
көмегімен оның құрама бөліктерінің (сөздердің, әріптердің, буындардың,
цифрлардың) өзгеруімен қортындыланады. Шифрленген ақпаратпен танысу үшін
кері үрдіс – дешифрлеу қолданылады.
Криптографияны қолдану - көп таралған және ЭВМ желілерінде
мәліметтерді тасымалдау қауіпсіздігін жоғарылатушы әдістерінің бірі.
Осы кезде кейбір шифрлеу әдістері жақсы сыналған және классикалық
болып есептеледі. Көптеген қорғалған өзгертулердің қазіргі әдістерін төрт
үлкен топқа топтастыруға болады: орын алмастыру, ауыстыру, аддитивтік және
қиыстырылған әдістер .
Орын алмастыру және ауыстыру әдістері әдетте кілттің қысқа
ұзындығымен сипатталады, ал оларды қорғану сенімділігі өзгерту
алгоритмдерінің қиындығымен анықталады. Аддитивтік әдістерге қарапайым
өзгерту алгоритмдері тән, ал олардың криптографиялық тұрақтылығы кілт
ұзындықтарының артуына негізделген.
Барлық айтылған әдістер симметриялы шифрлеуге жатады. Симметриялы
криптографиялық алгоритмдерде хабарлауды шифрлауға және шифрді ашуларға
арналған бірдей ақпарат қолданылады.
Ақпаратты криптографиялық қорғауда шифрлеу негізгі рөл атқарады.
Шифрлеудің келесі түрлері белгілі: ассиметриялық (RSA, Diffie-Hellman, El-
Gamal), симметриялық (DES, IDEA, ГОСТ).
2.1.1 Блоктық шифрлар
Блоктық шифрлеу кезінде бастапқы мәтін ұзындығы тұрақты бекітілген
блоктарға бөлінеді. Блок мәтіндері бір-біріне қатыссыз бөлек шифрленеді.
Шифрлеу үшін барлық блоктарға бір ғана кілт қолданылады. Шифрлеу тәсілдері
ауыстыру, алмастыру, құрастырма шифрлар болып бөлінеді.
Ауыстыру шифрі белгілі бір ереженің көмегімен бастапқы мәтін
символдарын басқа символдармен ауыстыру арқылы анықталады. Егер шифрлеу
үшін бір әліпби қолданылса, онда шифр бір әліпбилі немесе моноәліпбилік деп
аталады. Егер бірнеше әліпби қолданылса, онда ол көп әлипбилі немесе
полиәліпбилі деп аталады. Бір әліпбилі шифрдің ең қарапайым мысалы Цезарь
шифры.
Қазақ алфавитіне пробел символын қосып, сәйкес келетін ретпен жазып
шығайық.
“ А Ә Б В Г Ғ Д Е Е Ж З И Й К Қ Л М Н Ң О Ө П Р С Т
У Ұ
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
25 26 27
Ү Ф Х Һ Ц Ч Ш Щ Ъ Ы І Ь Э Ю Я
28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
Цезарь хаттарды келесі формуланың көмегімен шифрлеген:
(әріп)= ((әріп)+N) mod 43 Мұндағы 1=N43
N – шифрлеу кілті.
Цезарь шифрімен түрлендірілген хабарламаға мысал:
Б М С Б Т Б Ұ Ә Б Н Ң Б У Ү N=0,2
А Қ П А Р А Т А Л М А С У
Әйгілі Вижинер шифры да көп әліпбилі ауыстыру шифріне жатады. Шифрлеу
өлшемі n*n матрицасының көмегімен жүргізіледі. Кестенің бірінші жолында
әліпбидің символдары түгелдей жазылады. Келесі жолдары алдыңғы жолды бір
символға солға жылжыту арқылы табылады.
Хабарды шифрлеу үшін:
1) Түйінді сөз таңдайды. Мысалға ақпарат сөзін таңдайық.
2) Ашық мәтін символдарының астына кілт символдарын жазады. Егер кілт
хабардан қысқа болса, оны бірнеше рет қайталайды.
О Р Ы Н А Л М А С Т Ы Р У Ш И Ф Р І (*)
А қ п а р а т а қ п а р а т а қ п а (**)
3) Шифрмәтін символы Вижинер кестесі көмегімен ізделінеді. Ол үшін
(*) тізбегіндегі символды кесте жолынан, ал (**) тізбегіндегі символды
кесте бағанынан іздейсіз. Шифрланған символ сол бағана мен жолдың
қиылысында орналасқан.
Сонда келесі шифрмәтін аламыз: оылн рлюа івыб ули аәі
Кесте 1 Вижинер кестесі
Мәтінді шифрлеуде сенімділік жоғары болуы үшін Вижинердің
жетілдірілген кесте түрі ұсынылады, ол келесіде :
1) Алфавит әріптері барлық (біріншісінен басқа) кесте жолдарында өз
еркімен орналасады;
2) 0-ден 9-ға дейінгі натурал сандармен нөмірленген он (біріншісін
есептемегенде) жол таңдалады;
3) Кілт ретінде шамалар қолданылады.
Ақпаратты сенімді шифрлеуді қамтамасыз ететін ауыстыру әдісінің жеке
жағдайы матрицалардың алгебрада (мысалы, векторға матрицаны көбейту)
қолдануы болып табылады:
Осы ережеге сәйкес A={aij} матрицасын шифрлеуге арналған негіз
ретінде пайдалануға болады, B={bi} вектор белгілері шифрленген мәтін
символдары бола алады, ал вектор белгілерінің нәтижесі C={сi} шифрланген
мәтін символдары болып табылады.
Әріптік ақпаратты шифрлеу үшін ең алдымен алфавитте әріптің реттік
нөмірі бола алатын цифрлік эквиваленттерін алфавит белгілеріне ауыстыру
керек.
Дешифрлеу үшін векторға матрицаны көбейту ережесі қолданылады, тек
қана негіз ретінде кері матрица алынады, ал көбейткішті вектор ретінде
шифрленген мәтіннің лайықты сандар жиынынан алады.
Шифрлау және шифрді ашу процедуралары қатал формализацияланған, бұл
автоматты орындаулар үшін салыстырмалы жеңіл бағдарламмалауға рұқсат етеді.
Осы әдістің кемшілігі әрбір әріпті шифрлау және шифрді ашу үшін бірнеше
арифметикалық әрекеттер орындау керек, бұл ақпаратты өңдеу уақытын
үлкейтеді.
Орын алмастыру шифрлері символдардың орналасу позицияларын ған
өзгертеді. Ең қарапайым шифр – жай бағаналық орын алмастыру шифрын
келтірейік.
Шифрдің бұл түрінде мәтін ұзындығы біркелкі блоктарға алдын ала
бөлініп горизантал бағытта бірнеше рет жазылады. Шифрмәтінді алу үшін
мәтінді вертикал бағытта оқу керек. Дешифрлеу үшін шифрмәтін вертикал
бағытта жазылып, ашық мәтін горизонтал бағытта оқылады.
Мысал. Ашық мәтін ретінде келесі сөйлемді алайық:
СИММЕТРИЯЛЫ ЖҮЙЕНІ ШИФРЛЕУ
Сөйлемді алты жолы, төрт бағанасы бар кесте түрінде жазайық:
С И М М Е Т
Р И Я Л Ы Ж
Ү Й Е Н І Ш
И Ф Р Л Е У
Шифрмәтін алу үшін кестедегі символдарды бағана бойымен (жоғарыдан
төменге) оқып мысалға бес-бестен топқа бөліп жазамыз.
Сонда шифрмәтін аламыз: срүии ийфмя ермлн леыіе тжшу.
Орын алмастыру шифры хабарлаудың шифрлауына арналған символдардың n
ұзындығымен өзгеруін қарастырамыз. Оны кесте көмегімен көрсетуге болады
мұндағы i1 – шифрмәтінінің нөмірі, i2 – екінші әріп үшін орын нөмірі
және т.с.с. Кестенің жоғарғы жолында 1-ден n-ге дейінгі сандар ретпен
жазылған, ал төменгі жолында сол сандар, тек сандар өз бетінше орналасқан.
Осындай кесте n дәрежесінің ауыстырылуы деп аталады.
Келесі бағдарлама кодының (Object Pascal тілінде) үзіндісі негізгі
хабарлауды шифрлеу және шифрді ашуда оның орын алмастыру шифрын қолдануды
демонстрациялайды:
const Lmax=100;
type TArr=array[1..Lmax] of integer;
{процедура-мәтінді шифрлеу функциясы
Кіру параметрі: txt - негізгі мәтін, password - кілт
Функцияның нәтижесі – шифрленген мәтіннің жолы}
function SH_TO(txt:string;password:TArr):str ing;
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):s tring;
var i,l:integer;
s:string;
begin
l:=length(txt);
for i:=1 to l do
s:=s+txt[Password[i]];
result:=s;
end.
Құрастырма шифрлар.Бұл шифрдің негізінде, сенімді криптожүйе
құрастыру үшін ауыстыру және орын алмастыру сияқты қарапайым шифрларды алма
– кезек бірнеше рет қолдану идеясы жатыр. DES (Data Encryption Standard,
АҚШ), FEAL-1 (Fast Enciphering Algoritm, Жапония), IDEAIPES (International
Data Encryption AlgorithmImproved Proposed Encryption Standard, Ascom-Tech
AG фирмасы, Швейцария), B-Crypt (British Telecom фирмасы, Ұлыбритания), АES
(АҚШ), ГОСТ 28147-89, Skipjack (АҚШ) және басқа көптеген алгоритмдер
шифрдің осы түріне жатады.
Құрастырма шифрларына мінездеме 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, АҚШ) стандартты
криптографиялық алгоритм құрастыруға сынақ жариялады. Бірақ келіп түскен
бір де бір ұсыныс қойылып отырған талаптарға сай келмеді. Тек 1974 жылы
Lucifer атты алгоритм IBM корпорациясында жұмыс істеуші криптографтар
атынан ұсынылды. Олар – Рой Адлер, Дон Копперсмит, Хорст Файстель, Эдна
Кроссман және басқалары. NBS бюросы NSA ұйымынан алгоритмді бағалауда көмек
сұрады. 1976 жылы DES федералдық стандарт ретінде бекітілді.
Енді DES-ті сипаттауға көшейік. DES блоктық алгоритм болып табылады.
Ашық мәтін ұзындығы – 64 бит. Кілт ұзындығы – 56 бит. Алгоритмде 16 бөлім
орындалады, яғни бірдей тәсілдердің комбинациясы ашық мәтінге 16 рет
қолданылады. Алгоритмнің негізгі қадамдарын қарастырайық.
Бастапқы орын алмастыру.
Алгоритм басталмас бұрын ашық текст биттері үшін орын алмастыру
процедурасы орындалады. Pk деп к-ші жаңа позицияға орналасатын ашық текст
битінің нөмірін белгілейік. Р0 = 0, Р1 = 58 болсын. Алдыңғы төрт байттың
құрамындағы бірінші бит позициясына келесі бит орналасады.
Р8i+1 = Р1 + Р8i , i=0,3 (1)
Бесінші байттың бірінші битінің позициясы былай есептеледі:
Р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 34 26 18 10 2 60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1 59 51 43 35 27 19 11
3
61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7
Кілт түрлендіру
а) 64-биттік кілттің әрбір сегізінші биті ескерілмейді. Олар тақтық
қасиетін тексеру үшін қолданылады. Сонымен кілттің ұзындығы 56 битке шейін
қысқарылады.
б) 56 биттік кілт екі тең бөлікке бөлінеді. Раунд нөміріне байланысты
кілт бөліктері бір немесе екі битке солға жылжытылады. 1, 2, 9, 16-шы
бөлімдерде кілт 1 битке жылжиды. Қалған жағдайларда 2 битке жылжиды.
в) 56 биттің 48 таңдап алынады. Бит орналасу реті де өзгертіледі. Бұл
операция сығылатын орын алмастыру деп аталады.
Кесте 4 Шифрлау алгортмінің сүлбесі
32
32
Сонымен әрқайсысының ұзындығы 48 бит 16 бөлімдік кілт жасалады.
Кесте 5 Сығылатын орын алмастыру
14 17 11 24 1 5 3 28 15 6
21 10
23 19 12 4 26 8 16 7 27 20
13 2
41 52 31 37 47 55 30 40 51 45 33
48
44 49 39 56 34 53 46 42 50 36 29
32
Кесте 6 Кілт түрлендіру алгоритмі
64 бит
56 бит
48 бит
Хабарды шифрлау.
Демек сіз ұзындығы 64 бит бастапқы мәтін және ұзындығы 48 бит кілтке
иесіз. Бастапқы хабар іспеттес тең екі бөлікке бөлінеді. Оң бөлік кілт
ұзындығына дейін кеңейтіледі. Биттердің орын алу реті де өзгереді. Бұл
қадамның негізгі мақсаты – әр шифрмәтін битінің әрбір шифрмәтін және кілт
биттеріне тәуелділігін арттыру.
Кесте 7 Кеңейтетін орын алмастыру
32 1 2 3 ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
МАЗМҰНЫ
КІРІСПЕ 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.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-ге қалдықсыз бөлінетін болса а және b
бүтін сандарын 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 n
(a-b) mod n = ((a mod n) - (b mod n)) mod n
(a*b) mod n = ((a mod n) * (b mod n)) mod n
(a*(b+c)) mod n = (((a*b) mod n) + ((a*c) mod n)) mod n
Дискреттiк логарифм және түбiр квадратын есептеу қиын болғандықтан,
криптография n модулi бойынша көптеген есептер қолданылады. Сонымен қатар,
модуль бойынша есептеулермен жұмыс iстеу тиiмд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 = 6.
1.2 Дәрежеге шығару алгоритмі
К биттi ұзындықты n модулiнiң қосу, алу немесе көбейту сияқты аралық
нәтижелері 2к биттен ұзын болмайды. Сондықтан модулярлық арифметикада
дәрежеге шығаруды өте үлкен аралық нәтижелердің генерациясынсыз орындауға
болады.
n модулi бойынша а санының дәрежесiн есептеудi ax mod n kөбейту мен
бөлудiң қатары ретiнде орындауға болады. Бұны тездету үшiн неше түрлi
әдiстерi бар. Бұл операциялар дистрибутивтi болғандықтан, модуль бойынша
келтiрудi әркез орындай отырып, көбейту қатары ретiнде дәрежеге шығаруды
тездетiп орындау. Егер ұзын сандармен (200 бит және одан да көп) жұмыс
жасаса, бұл ерекше белгiлi болады.
Мысалы, егер a8 mod n –дi есептеу керек болса, жетi рет қайта көбейту
мен модуль бойынша үлкен санды бiреуге келтiруге (a*a*a*a*a*a*a) mod n
примитивтi жақындау қолданып керегi жоқ.
Бұның орнына 3 кiшi көбейту мен 3 кiшi модуль бойынша келтiру
орындалады:
((a2 mod n)2 mod n)2 mod n
Осы әдiспен a16 mod n = (((a2 mod n)2 mod n)2 mod n)2 mod n
есептелiнедi.
Есептеу бiраз ғана қиынырақ: ax mod n (4), мұндағы x 2-дәрежелі болып
табылмайды. x cанының екiлiк жазуы x санын 2-дәрежелердiң қосындысы ретiнде
келтiрудi қолдайды:
x = 25(10) → 1 1 0 0 1(2), сондықтан 25 = 24 + 23 + 20 тең
болады.
Онда a25 mod n = (a*a24) mod n = (a*a8*a16) mod n =
a*((a2)2)2*(((a2)2)2)2 mod n = ((((a2*a)2)2)2*a) mod n деп аламыз.
Аралық нәтижелерде алты ғана көбейту амалы керек болады:
(((((((a2 mod n)*a) mod n)2 mod n)2 mod n)2 mod n)*a) mod n
Бұл әдiс 1,5хк операциясына дейiн есептеуде қиындықты жеңiлдетедi,
мұндағы к – бит негiзiндегі сандар ұзындығы.
Көптеген шифрлеу алгоритмi n модулi бойынша дәрежеге шығаруға
негiзделген болғандықтан, тез дәрежеге шығару алгоритмiн қолдану орынды.
S = aW mod n мағынасын есептеу керек болсын. W дәрежесін 2 санын
дәрежеге үлестіру түрінде келтіреміз:
W = wg-12g-1 + wg-22g-2 + ... + w222 + w121 + w0
мұндағы wi 0 немесе 1сандары.
S = aW mod n – ді келесі түрде келтірейік:
S = aw mod n = aWg-12 + Wg-22 + ... + W22 +
W12 + W0 mod n = (a2)Wg-12 + Wg-22 + ... + W22 +
W12*aw0 mod n = ((a2)2) Wg-12 + Wg-22 + ... +
W22*(a2)W1*aW0 mod n = ( ...((a2)2 ... )2)Wg-1* ...
*(a8)W3*(a4)W2*(a2)W1*aW0 mod n.
Мысалдар:
1) 437 mod 26 = ((42)19 – 4) mod 26 = [(16 mod 26)19 - 4] mod 26 =
(162)9*4 mod 26 - 4 = (256 mod 26)9*4 mod 26 - 4 = 229*4 mod 26 - 4=
(222)4*22*4 mod 26 – 4 = (484 mod 26)4*22*4 mod 26 = (16)4*22*4 mod 26 =
(162)2*22*4 mod 26 = 222*22*4 mod 26 = 16*22*4 mod 26 = 16*88 mod 26 =
16*10 mod 26 = 160 mod 26 = 4.
2) [(223 mod 11)39 + (411 mod 7)19] mod 11
a) (223 mod 11)39 = ((24)5*23 mod 11)39 = (55*23 mod 11)39 = ((52)2*5*23
mod 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 7)19
= (16 mod 7)19 = 219
c) 839 mod 11 + 219 mod 11 = (82)19*8 mod 11 + (24)4*23 mod 11 = (9)19*8
mod 11 + 54*23 mod 11 = (92)9*9*8 mod 11 + (52)2*23 mod 11 = 49*9*8
mod 11 + 32*23 mod 11 = (42)4*4*9*8 mod 11 + 32*23 mod 11 =
(52)2*4*9*8 mod 11 + 6 = 32*4*9*8 mod 11 + 6 = 3*9*8 mod 11 + 6 = 5*8
mod 11 + 6 = 7+6 = 13
d) 13 mod 11 = 2.
1.3 Эйлер функциясы
Айталық, m = p1α 1 p2α 2 ... ptα t , m1 натурал санының Канондық
жіктелуі болсын.
φ (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) = (p-1)(q-1)-ге тең
болады.
Теорема 1 (Эйлер) Кез-келген n модулі мен n-мен өзара жай а саны үшін
келесі салыстыру ақиқат
aφ(n)-1 ≡ 1(mod n)
Анықтама 3 Келесі үш шартты қанағаттандыратын θ функциясын
мультипликативті деп атаймыз:
1) θ кез келген натурал сан үшін анықталған;
2) θ(1) = 1;
3) егер (a,b) = 1 болса, онда θ(ab) = θ(a)θ(b).
Теорема 2 Эйлер функциясы – мултипликативті функция.
Дәлелдеуі. Айталық, p1α 1 ... ptα t және q1β1 ... qsβs сәйкесінше
өзара жай натурал m11 және m21 өзара жай сандарының канондық жіктеулері
болсын. Онда p1, ..., pt сандарының әрқайсысы q1, ..., qs сандарының
әрқайсысына өзгеше. Бұдан m1m2 канондық жіктеуі p1α 1 ... ptα t q1β1 ...
qsβs. φ (m1m2) = φ (m1) φ (m2) теңдеуі, Эйлер функциясының анықтамасынан
тікелей шығады. m1 = 1 немесе m2 = 1 үшін берілген теңдеу айқын. Теорема
дәлелденді.
Теорема 3 φ (m) саны 1, 2, ..., m сандық тізбегіндегі m-мен өзара жай
болатын сандардың санына тең.
Дәлелдеуі. Дәлелдеме m1 санының канондық жіктеуіндегі жай көбейткіш
сандардың саны n бойынша математикалық индукция әдісі бойынша жүргізіледі.
Теорема n = 0 (m = 1) және n = 1 (m = p) үшін орындалады, мұндағы p – жай
сан. Айта кетерлік жайт, i натурал саны mp–мен өзара жай болу үшін ол бір
мезгілде m мен p сандарымен өзара жай болуы қажет және жеткілікті. 1, 2, ...,
mp тізбегін талдау үшін ұзындығы m-ге тең p тізбекшелеріне mk+1, mk+2, ...,
mk+m-бөлеміз, мұнда k = 0, 1, ..., p-1. Теорема 3-тен (mk + i,m) = (i, m)
шығады. Осы теңдік пен осы индуктивті ұйғарымнан mk+1, mk+2, ..., mk+m
тізбекшесінде m–мен өзара жай φ (m) сан бар. Осыдан 1, 2, ..., mp тізбегінде
m–мен өзара жай φ (m)p сан бар. M p-ға бөлінетін жағдайда, бұл сандар p-мен
өзара жай, сонымен қатар mp санымен де өзара жай. Соңғы ескерту мен айқын
теңдік φ (mp) = φ (m)p қарастырылған жағдайдағы теореманың ұйғарымын
дәлелдейді.
m-нің p-ға бөлінбейтін жағдайын қарастыру қалды. m-мен өзара жай φ
(m)p сандарының санынан осылардың p-ға бөлінетіндерінің санын алып
тастасақ, іздеген φ (mp) санын табамыз. Ол сандар тек p, 2p, 3p, ..., mp
сандарының арасында ғана болуы мүмкін. Сондықтан, m-мен өзара жай сандардың
арасындағы p-ға бөлінетіндерінің саны p, 2p, 3p, ..., mp сандарының
арасындағы m-мен өзара жай сандардың санына тең болады. Егер i≤m және (m,p)
= 1 болғанда (ip,m) = (i,m) болатынын ескерсек, онда p, 2p, 3p, ..., mp
сандарының арасындағы m-мен өзара жай сандар саны. 1, 2, ..., m сандарының
арасындағы m-мен өзара жай сандар санына тең, яғни индукция бойынша φ (m).
Қорыта келе, ізделінді φ (mp) = φ (m)p - φ (m) = φ (m)(p-1). Теорема
дәлелденді.
Эйлер функциясының осы қасиетінің берілген дәлелдемесін
Р.А.Сүйіндіков ұсынды.
Мысалдар: Берілген n натурал саны жай сан деп саналады, егер де ол
тек өзіне ғана және 1-ге бөлінетін жағдайда a, n 2 натурал сандар өзара
жай сандар деп саналады, егер олардың ортақ бөлгіштері болмаса.
1. n = 7
1 2 3 4 5 6 ((7) = 6.
2. n = p*q, p,q –жай сандар, ((n) = (p-1)*(q-1)
n = 33 = 11*3, ((33) = (11-1)(3-1) = 20.
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к емес а үшiн: a-1 = немесе а*а-1 = 1 деп
есептейміз.
Мысалы, мультипликативтi керi шама 4 санынан ¼-ке тең, өйткенi
4* = 1-ге тең болғандықтан.
Ал модулярлық арифметикада керi шаманы есептеу қиын есеп болып
табылады. Мысалы, салыстыруды есептеу 4*x ≡ 1 (mod 7) х және к мәндерiн
табумен эквиваленттi, бұл 4*х ≡ 7*к + 1-ге тең, мұндағы х және к - бүтiн
сандар.
Бұл есептiң жалпы тұжырымы – х бүтiн санын табу, бұл дегенiмiз a*x
(mod n) = 1, басқаша осылай a-1 ≡ x (mod n) деп жазуға болады.
Бұл есептiң шешiмi кейде болады, кейде болмайды. Мысалы, 14 модулi
бойынша 5 саны үшiн керi шама 3-ке тең, өйткенi
5*3 = 15 ≡ 1 (mod 14)
Келесi жақтан қарасақ, 14 модулi бойынша 2 санында керi шама жоқ.
Егер а және n - өзара жай сандар болса, жалпы a-1 ≡ x (mod n)
салыстыруында бiр ғана нәтиже бар,.
Егер а және n сандары өзара жай сандар болмаса, онда салыстыру a-1 ≡
x (mod n) тең болады.
Нәтижесi жоқ керi шаманы табудың негiзгi әдiсiн тұжырымдаймыз. a
{0, 1, 2, ..., n-1} бүтiн сандар болсын. Егер ЕҮОБ(a, n) = 1, онда a*i
(mod n), мұндағы i = 0, 1, 2, ..., n-1, {0, 1, 2, ..., n - 1}жиынтығын
алмастыру болып табылады.
Мысалы, егер a = 3 және n = 7 (ЕҮОБ(3, 7) = 1), онда 3*i (mod 7),
мұндағы i = 0, 1, 2, ..., n-1; 0, 3, 6, 2, 5, 1, 4 жүйелiк болып табылады.,
яғни {0, 1, 2, ..., 6}жиынтығын алмастыру болып табылады.
Егер ЕҮОБ(a, n) ≠ 1 болса, жоғарыда келтірілген мысал дұрыс емес
болып шығады. Мысалы, егер a = 2 және n = 6 болса, онда 2*i (mod 6) ≡ 0, 2,
4, 0, 2, 4 мұндағы i = 0, 1, 2, ..., 5 болады.
Егер ЕҮОБ(a, 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 модуль бойынша шегерудiң толық
жиыны {0, 1, 2, ..., 10}.
Келтiрiлген шегеру жиынын тұжырымдаған кезде олардың iшiнен бiр ғана
элемент – 0 өшiрiледi. Келтiрiлген шегеру жиыны 11 модулi бойынша 11-1 = 10
элементi бар болады.
Жалпы келтiрiлген шегеру жиынында n модуль бойынша жай санының n-1
элементi бар болады.
Эйлер функциясы φ(n) шегеру жиынтығында келтірілген элементтер санын
мінездейді. Төмендегі кестеден көруге болады.
Кесте 1 Эйлер функциясы
Модуль n Функция φ(n)
N – жай сан n-1
n2 n(n-1)
· ·
· ·
· ·
nr nr-1(n-1)
P*q (p, q – жай сандар) (p-1)(q-1)
· ·
· ·
· ·
(p– жай сан)
Басқаша айтқанда, Ферманың кiшкене теоремасы: егер n–жай және ЕҮОБ(a,
n) = 1, онда an-1 ≡ 1 (mod n) болады.
Эйлердiң қортуына сәйкес Ферманың кiшене теоремасынан: eгер ЕҮОБ(a,
n) = 1, онда aφ(n) ≡ 1 (mod n)-ге тең.
Керi шаманы табудың негiзгi 3 әдiсі бар. Олар: тура іріктеу әдісі,
евклидтің кеңейтілген алгоритмі көмегімен кері шамаларды есептеу әдісі,
Эйлер функциясы көмегімен кері шамаларды есептеу әдісі. Соларға тоқталайық.
1.4.1 Тура іріктеу әдісі
a-1 ≡ 1 (mod n) табылмағанға дейiн, осындай 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) түрде болады.
n = 7, ал a = 5 болсын. x = a-1 (mod n)–дi табу керек.
а*x ≡ 1 (mod n) немесе 5*х ≡ 1 (mod 7).
n - 1 = 7 - 1 = 6
x = 5-1 (mod 7) = 3 - тi аламыз.
Кесте 1 Тура іріктеу әдісінің мысалы
x 5*x 5*x (mod 7)
1 5 5
2 10 3
3 15 1
4 20 6
5 25 4
6 30 2
1.4.2 Эйлер функциясы көмегімен кері шамаларды есептеу
Eгер Эйлер φ(n) функциясы белгiлi болса, онда дәрежеге тез шығару
алгоритмiн қолдана отырып a-1 (mod n) ≡ aφ(n) – 1 (mod n) табуға болады.
Кесте 1 Эйлер функциясы көмегімен кері шамаларды есептеу
Модуль n Функция φ(n)
n n-1
n2 r(n-1)
nr nr-1(n-1)
n = p*q (p-1)(q-1)
Егер а және n өзара жай сандар болса, a-1 x(mod n)
салыстырылуы бір ғана есептеуін қажет етеді. Егер а және n өзара жай
сандар болмаса, онда бұл салыстыру есептеуді қажет етпейді.
Егер Эйлер функциясы белгілі болса, онда кері шаманы есептеуге
болады:
а-1 (mod n) = aφ(n-1) (mod n)
Мысалдар:
1. a-1 (mod n) –дi табу керек, егер Эйлер φ(n) функциясы белгiлi
болса.
n = 7, ал a= 5 болсын. x = a-1 (mod n) = 5-1 (mod 7 )–нi табу керек.
n = 7 модулi – жай сан. Сондықтан Эйлер функциясы φ(n) = φ(7) = n-1
=6.
Керi шама 5-тен 7 – ге дейiнгі аралықты қамтиды.
a-1 (mod n) = aφ(n) – 1 (mod n) = 56-1 mod 7 = 55 mod 7 = (52 mod
7)(53 mod 7) mod 7 = (25 mod 7)(125 mod 7) mod 7 = (4*6) mod 7 = 24 mod 7 =
3.
Нәтижесі x = 5-1 (mod 7) = 3-ке тең.
1.4.3 Евклидтің кеңейтілген алгоритмі көмегімен кері шамаларды
есептеу
Егер Эйлер φ(n) функциясы белгiлi болмаса, кеңейтiлген Евклид
алгоритмiн қолдануға болады.
Евклид алгоритмнің алгебрада, тіпті жалпы математикада атқаратын
ролі өте үлкен. Оң бүтін r0r10 сандары берілсін. Олардың ең үлкен ортақ
бөлгішін (ЕҮОБ) табу үшін төмендегі қалдықпен бөлу тізбегін іске асырамыз:
r0 = q1r1 + r2, 0r2r1
r1 = q2r2 + r3, 0r3r2
.
.
.
rm-2 = qm-1rm-1 + rm, 0rmrm-1
rm-1 = qmrm.
Енді негізгі нәтижені дәлелдеу қиын емес:
ЕҮОБ(r0, r1) = ЕҮОБ(r1, r2) = ... = ЕҮОБ(rm-1, rm) = rm
яғни, Евклид алгоритмін орындау нәтижесінде берілген сандардың ең
үлкен ортақ бөлгішін табамыз:
ЕҮОБ(r0, r1) = rm
Енді бұл алгоритмді былай кеңейтейік. Рекурренттік әдіспен
төмендегідей t0, t1, ..., tm сандар тізбегін анықтаймыз:
t0 = 0,
t1 = 1, және j≥2 үшін tj = tj-2 – qj-1tj-1 деп ұйғарамыз.
Бұл тізбектің пайдасын келесі леммадан көреміз. Алдымен бір белгілеу
енгізейік: егер а, b сандары n-ге бөлгенде бірдей қалдық берсе, онда а, b
сандары n модулі бойынша тең дейміз және бұл қатынасты а ≡ b (mod n) деп
жазып көрсетеміз.
Лемма 1 Жоғарыда іске асырылған кеңейтілген Евклид алгоритмінде
пайда болатын сандар әрбір 0≤j≤m үшін ri ≡ tjr1 (mod r0) қатынасын
қанағаттандырады.
Дәлелдеуі: j бойынша индукция қолданамыз. Біріншіден, бастапқы мәндер
j = 0 және j = 1 үшін лемманың дұрыстығы айдан анық. Леммадағы қатынас j =
i - 1 және j = i – 2 үшін дұрыс деп ұйғарып (мұнда, әрине 2 ≤ i), оны і
үшін дәлелдейік.
Сонымен, индукцияның ұйғарымы бойынша ri-2 ≡ ti-2r1 (mod r0) және ri-
1 ≡ ti-1r1 (mod r0) болады.
Ал енді ri –ді есептесек, алатынымыз:
ri = ri-2 – qi-1ri-1 ≡ ti-2r1 – qi-1ti-1r1 (mod r0) ≡ (ti-2 – qi-1ti-
1)r1 (mod r0) ≡ tir1 (mod r0).
Лемма дәлелденді.
Егер ab ≡ 1(mod n) болса, онда a,b сандары n модулі бойынша біріне-
бірі кері дейміз және a ≡ b-1 (mod n) немесе b ≡ a-1 (mod n) деп жазамыз.
Салдар 1 Егер ЕҮОБ(r0, r1) = 1 болса (бұл жағдайда r0, r1 сандары
өзара жай деп аталады), онда tm ≡ r1-1 (mod r0) деп аламыз.
Бұл алгоритм бойынша берілген теріс емес а, b бүтін сандары (U1, U2,
U3) векторларын анықтайды, ол келесі теңдікті қанағаттандыру тиіс.
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 тиіс және U3 = 1 егер aU1 + nU2 = ЕҮОБ (a, n)
= 1, басқаша айтқанда а теріс шамасы: a-1 (mod n) ≡ U1 (mod n)-ге тең.
Алгоритмнің негізгі қадамдары:
1) Бастапқы қойылым (U1, U2, U3) векторы анықталады;
(U1, U2, U3) = (0, 1, n)
(V1, V2, V3) = (1, 0, a)
2) U3 = 1 орындалса, алгоритмнің соңы;
3) q анықталады. q = div бөлгендегі бүтін бөлігі;
4) Қосалқы векторларды есептейді (t1, t2, t3).
(t1, t2, t3) = (U1, U2, U3) - q(V1, V2, V3)
(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 = 1.
Нәтижені қорытатын болсақ: Евклид алгоритмі бүтін сандардың ең үлкен
ортақ бөлгішін табуға қолданылады, ал кеңейтілген Евклид алгоритмі модуль
бойынша кері элеметті есептеп табуға (бар болса!) қолданылады
Керi a-1 (mod n) шамасын кеңейтiлген Евкид алгоритiмiнiн көмегiмен
табамыз.
Евклид алгоритмiн үлкен практикалық мәнi бар әдiспен қорытуға
болады. Бұл әдiсте ЕҮОБ(a, b) есептеуi кезiнде жолай u1 және u2 бүтiн
сандарын есептеуге болады, бұл
a* u1 + b* u2 = ЕҮОБ(a, b)
Бұл кеңейтiлген Евклид алгоритмiнiнiң қорытуын тиiмдi болады, егер
векторлық белгiлеулер қолданса.
2 ШИФРЛЕУ АЛГОРИТМДЕРІ
2.1 Симметриялық алгоритмдер
Симметриялы криптографиялық жүйелер ақпаратты қорғау саласында
классикалық жүйелер болып табылады. Мәліметті шифрлау және дешифрлау үшін
бір құпия кілт қолданылады. Симметриялық криптографиялық жүйедегі шифрлау
тәсілдерінің классификациясы 1 – суретте ұсынылады.
Сурет 1 Симметриялық криптографиялық жүйедегі шифрлау тәсілдерінің
классификациясы
Ақпаратты қорғаудағы криптографиялық өзгерту әдістері арнайы
алгоритмдердің немесе аппараттық шешімдердің және кілттердің кодтары
көмегімен оның құрама бөліктерінің (сөздердің, әріптердің, буындардың,
цифрлардың) өзгеруімен қортындыланады. Шифрленген ақпаратпен танысу үшін
кері үрдіс – дешифрлеу қолданылады.
Криптографияны қолдану - көп таралған және ЭВМ желілерінде
мәліметтерді тасымалдау қауіпсіздігін жоғарылатушы әдістерінің бірі.
Осы кезде кейбір шифрлеу әдістері жақсы сыналған және классикалық
болып есептеледі. Көптеген қорғалған өзгертулердің қазіргі әдістерін төрт
үлкен топқа топтастыруға болады: орын алмастыру, ауыстыру, аддитивтік және
қиыстырылған әдістер .
Орын алмастыру және ауыстыру әдістері әдетте кілттің қысқа
ұзындығымен сипатталады, ал оларды қорғану сенімділігі өзгерту
алгоритмдерінің қиындығымен анықталады. Аддитивтік әдістерге қарапайым
өзгерту алгоритмдері тән, ал олардың криптографиялық тұрақтылығы кілт
ұзындықтарының артуына негізделген.
Барлық айтылған әдістер симметриялы шифрлеуге жатады. Симметриялы
криптографиялық алгоритмдерде хабарлауды шифрлауға және шифрді ашуларға
арналған бірдей ақпарат қолданылады.
Ақпаратты криптографиялық қорғауда шифрлеу негізгі рөл атқарады.
Шифрлеудің келесі түрлері белгілі: ассиметриялық (RSA, Diffie-Hellman, El-
Gamal), симметриялық (DES, IDEA, ГОСТ).
2.1.1 Блоктық шифрлар
Блоктық шифрлеу кезінде бастапқы мәтін ұзындығы тұрақты бекітілген
блоктарға бөлінеді. Блок мәтіндері бір-біріне қатыссыз бөлек шифрленеді.
Шифрлеу үшін барлық блоктарға бір ғана кілт қолданылады. Шифрлеу тәсілдері
ауыстыру, алмастыру, құрастырма шифрлар болып бөлінеді.
Ауыстыру шифрі белгілі бір ереженің көмегімен бастапқы мәтін
символдарын басқа символдармен ауыстыру арқылы анықталады. Егер шифрлеу
үшін бір әліпби қолданылса, онда шифр бір әліпбилі немесе моноәліпбилік деп
аталады. Егер бірнеше әліпби қолданылса, онда ол көп әлипбилі немесе
полиәліпбилі деп аталады. Бір әліпбилі шифрдің ең қарапайым мысалы Цезарь
шифры.
Қазақ алфавитіне пробел символын қосып, сәйкес келетін ретпен жазып
шығайық.
“ А Ә Б В Г Ғ Д Е Е Ж З И Й К Қ Л М Н Ң О Ө П Р С Т
У Ұ
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
25 26 27
Ү Ф Х Һ Ц Ч Ш Щ Ъ Ы І Ь Э Ю Я
28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
Цезарь хаттарды келесі формуланың көмегімен шифрлеген:
(әріп)= ((әріп)+N) mod 43 Мұндағы 1=N43
N – шифрлеу кілті.
Цезарь шифрімен түрлендірілген хабарламаға мысал:
Б М С Б Т Б Ұ Ә Б Н Ң Б У Ү N=0,2
А Қ П А Р А Т А Л М А С У
Әйгілі Вижинер шифры да көп әліпбилі ауыстыру шифріне жатады. Шифрлеу
өлшемі n*n матрицасының көмегімен жүргізіледі. Кестенің бірінші жолында
әліпбидің символдары түгелдей жазылады. Келесі жолдары алдыңғы жолды бір
символға солға жылжыту арқылы табылады.
Хабарды шифрлеу үшін:
1) Түйінді сөз таңдайды. Мысалға ақпарат сөзін таңдайық.
2) Ашық мәтін символдарының астына кілт символдарын жазады. Егер кілт
хабардан қысқа болса, оны бірнеше рет қайталайды.
О Р Ы Н А Л М А С Т Ы Р У Ш И Ф Р І (*)
А қ п а р а т а қ п а р а т а қ п а (**)
3) Шифрмәтін символы Вижинер кестесі көмегімен ізделінеді. Ол үшін
(*) тізбегіндегі символды кесте жолынан, ал (**) тізбегіндегі символды
кесте бағанынан іздейсіз. Шифрланған символ сол бағана мен жолдың
қиылысында орналасқан.
Сонда келесі шифрмәтін аламыз: оылн рлюа івыб ули аәі
Кесте 1 Вижинер кестесі
Мәтінді шифрлеуде сенімділік жоғары болуы үшін Вижинердің
жетілдірілген кесте түрі ұсынылады, ол келесіде :
1) Алфавит әріптері барлық (біріншісінен басқа) кесте жолдарында өз
еркімен орналасады;
2) 0-ден 9-ға дейінгі натурал сандармен нөмірленген он (біріншісін
есептемегенде) жол таңдалады;
3) Кілт ретінде шамалар қолданылады.
Ақпаратты сенімді шифрлеуді қамтамасыз ететін ауыстыру әдісінің жеке
жағдайы матрицалардың алгебрада (мысалы, векторға матрицаны көбейту)
қолдануы болып табылады:
Осы ережеге сәйкес A={aij} матрицасын шифрлеуге арналған негіз
ретінде пайдалануға болады, B={bi} вектор белгілері шифрленген мәтін
символдары бола алады, ал вектор белгілерінің нәтижесі C={сi} шифрланген
мәтін символдары болып табылады.
Әріптік ақпаратты шифрлеу үшін ең алдымен алфавитте әріптің реттік
нөмірі бола алатын цифрлік эквиваленттерін алфавит белгілеріне ауыстыру
керек.
Дешифрлеу үшін векторға матрицаны көбейту ережесі қолданылады, тек
қана негіз ретінде кері матрица алынады, ал көбейткішті вектор ретінде
шифрленген мәтіннің лайықты сандар жиынынан алады.
Шифрлау және шифрді ашу процедуралары қатал формализацияланған, бұл
автоматты орындаулар үшін салыстырмалы жеңіл бағдарламмалауға рұқсат етеді.
Осы әдістің кемшілігі әрбір әріпті шифрлау және шифрді ашу үшін бірнеше
арифметикалық әрекеттер орындау керек, бұл ақпаратты өңдеу уақытын
үлкейтеді.
Орын алмастыру шифрлері символдардың орналасу позицияларын ған
өзгертеді. Ең қарапайым шифр – жай бағаналық орын алмастыру шифрын
келтірейік.
Шифрдің бұл түрінде мәтін ұзындығы біркелкі блоктарға алдын ала
бөлініп горизантал бағытта бірнеше рет жазылады. Шифрмәтінді алу үшін
мәтінді вертикал бағытта оқу керек. Дешифрлеу үшін шифрмәтін вертикал
бағытта жазылып, ашық мәтін горизонтал бағытта оқылады.
Мысал. Ашық мәтін ретінде келесі сөйлемді алайық:
СИММЕТРИЯЛЫ ЖҮЙЕНІ ШИФРЛЕУ
Сөйлемді алты жолы, төрт бағанасы бар кесте түрінде жазайық:
С И М М Е Т
Р И Я Л Ы Ж
Ү Й Е Н І Ш
И Ф Р Л Е У
Шифрмәтін алу үшін кестедегі символдарды бағана бойымен (жоғарыдан
төменге) оқып мысалға бес-бестен топқа бөліп жазамыз.
Сонда шифрмәтін аламыз: срүии ийфмя ермлн леыіе тжшу.
Орын алмастыру шифры хабарлаудың шифрлауына арналған символдардың n
ұзындығымен өзгеруін қарастырамыз. Оны кесте көмегімен көрсетуге болады
мұндағы i1 – шифрмәтінінің нөмірі, i2 – екінші әріп үшін орын нөмірі
және т.с.с. Кестенің жоғарғы жолында 1-ден n-ге дейінгі сандар ретпен
жазылған, ал төменгі жолында сол сандар, тек сандар өз бетінше орналасқан.
Осындай кесте n дәрежесінің ауыстырылуы деп аталады.
Келесі бағдарлама кодының (Object Pascal тілінде) үзіндісі негізгі
хабарлауды шифрлеу және шифрді ашуда оның орын алмастыру шифрын қолдануды
демонстрациялайды:
const Lmax=100;
type TArr=array[1..Lmax] of integer;
{процедура-мәтінді шифрлеу функциясы
Кіру параметрі: txt - негізгі мәтін, password - кілт
Функцияның нәтижесі – шифрленген мәтіннің жолы}
function SH_TO(txt:string;password:TArr):str ing;
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):s tring;
var i,l:integer;
s:string;
begin
l:=length(txt);
for i:=1 to l do
s:=s+txt[Password[i]];
result:=s;
end.
Құрастырма шифрлар.Бұл шифрдің негізінде, сенімді криптожүйе
құрастыру үшін ауыстыру және орын алмастыру сияқты қарапайым шифрларды алма
– кезек бірнеше рет қолдану идеясы жатыр. DES (Data Encryption Standard,
АҚШ), FEAL-1 (Fast Enciphering Algoritm, Жапония), IDEAIPES (International
Data Encryption AlgorithmImproved Proposed Encryption Standard, Ascom-Tech
AG фирмасы, Швейцария), B-Crypt (British Telecom фирмасы, Ұлыбритания), АES
(АҚШ), ГОСТ 28147-89, Skipjack (АҚШ) және басқа көптеген алгоритмдер
шифрдің осы түріне жатады.
Құрастырма шифрларына мінездеме 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, АҚШ) стандартты
криптографиялық алгоритм құрастыруға сынақ жариялады. Бірақ келіп түскен
бір де бір ұсыныс қойылып отырған талаптарға сай келмеді. Тек 1974 жылы
Lucifer атты алгоритм IBM корпорациясында жұмыс істеуші криптографтар
атынан ұсынылды. Олар – Рой Адлер, Дон Копперсмит, Хорст Файстель, Эдна
Кроссман және басқалары. NBS бюросы NSA ұйымынан алгоритмді бағалауда көмек
сұрады. 1976 жылы DES федералдық стандарт ретінде бекітілді.
Енді DES-ті сипаттауға көшейік. DES блоктық алгоритм болып табылады.
Ашық мәтін ұзындығы – 64 бит. Кілт ұзындығы – 56 бит. Алгоритмде 16 бөлім
орындалады, яғни бірдей тәсілдердің комбинациясы ашық мәтінге 16 рет
қолданылады. Алгоритмнің негізгі қадамдарын қарастырайық.
Бастапқы орын алмастыру.
Алгоритм басталмас бұрын ашық текст биттері үшін орын алмастыру
процедурасы орындалады. Pk деп к-ші жаңа позицияға орналасатын ашық текст
битінің нөмірін белгілейік. Р0 = 0, Р1 = 58 болсын. Алдыңғы төрт байттың
құрамындағы бірінші бит позициясына келесі бит орналасады.
Р8i+1 = Р1 + Р8i , i=0,3 (1)
Бесінші байттың бірінші битінің позициясы былай есептеледі:
Р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 34 26 18 10 2 60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1 59 51 43 35 27 19 11
3
61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7
Кілт түрлендіру
а) 64-биттік кілттің әрбір сегізінші биті ескерілмейді. Олар тақтық
қасиетін тексеру үшін қолданылады. Сонымен кілттің ұзындығы 56 битке шейін
қысқарылады.
б) 56 биттік кілт екі тең бөлікке бөлінеді. Раунд нөміріне байланысты
кілт бөліктері бір немесе екі битке солға жылжытылады. 1, 2, 9, 16-шы
бөлімдерде кілт 1 битке жылжиды. Қалған жағдайларда 2 битке жылжиды.
в) 56 биттің 48 таңдап алынады. Бит орналасу реті де өзгертіледі. Бұл
операция сығылатын орын алмастыру деп аталады.
Кесте 4 Шифрлау алгортмінің сүлбесі
32
32
Сонымен әрқайсысының ұзындығы 48 бит 16 бөлімдік кілт жасалады.
Кесте 5 Сығылатын орын алмастыру
14 17 11 24 1 5 3 28 15 6
21 10
23 19 12 4 26 8 16 7 27 20
13 2
41 52 31 37 47 55 30 40 51 45 33
48
44 49 39 56 34 53 46 42 50 36 29
32
Кесте 6 Кілт түрлендіру алгоритмі
64 бит
56 бит
48 бит
Хабарды шифрлау.
Демек сіз ұзындығы 64 бит бастапқы мәтін және ұзындығы 48 бит кілтке
иесіз. Бастапқы хабар іспеттес тең екі бөлікке бөлінеді. Оң бөлік кілт
ұзындығына дейін кеңейтіледі. Биттердің орын алу реті де өзгереді. Бұл
қадамның негізгі мақсаты – әр шифрмәтін битінің әрбір шифрмәтін және кілт
биттеріне тәуелділігін арттыру.
Кесте 7 Кеңейтетін орын алмастыру
32 1 2 3 ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Ұқсас жұмыстар
Пәндер
- Іс жүргізу
- Автоматтандыру, Техника
- Алғашқы әскери дайындық
- Астрономия
- Ауыл шаруашылығы
- Банк ісі
- Бизнесті бағалау
- Биология
- Бухгалтерлік іс
- Валеология
- Ветеринария
- География
- Геология, Геофизика, Геодезия
- Дін
- Ет, сүт, шарап өнімдері
- Жалпы тарих
- Жер кадастрі, Жылжымайтын мүлік
- Журналистика
- Информатика
- Кеден ісі
- Маркетинг
- Математика, Геометрия
- Медицина
- Мемлекеттік басқару
- Менеджмент
- Мұнай, Газ
- Мұрағат ісі
- Мәдениеттану
- ОБЖ (Основы безопасности жизнедеятельности)
- Педагогика
- Полиграфия
- Психология
- Салық
- Саясаттану
- Сақтандыру
- Сертификаттау, стандарттау
- Социология, Демография
- Спорт
- Статистика
- Тілтану, Филология
- Тарихи тұлғалар
- Тау-кен ісі
- Транспорт
- Туризм
- Физика
- Философия
- Халықаралық қатынастар
- Химия
- Экология, Қоршаған ортаны қорғау
- Экономика
- Экономикалық география
- Электротехника
- Қазақстан тарихы
- Қаржы
- Құрылыс
- Құқық, Криминалистика
- Әдебиет
- Өнер, музыка
- Өнеркәсіп, Өндіріс
Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.
Ақпарат
Қосымша
Email: info@stud.kz