2. 1 Дәрістік сабақтардың конспектісі Дәріс Кіріспе. Аж-де ақпаратты қорғаудың жалпы талдау мәселесі
жүктеу/скачать 0,97 Mb. Pdf көрінісі
|
Жай сан – бұл 1-ге және өзіне ғана бөлінетін, басқа ешқандай санға қалдықсыз бөлінбейтін сан.
Өзара жай сандар – бұл А мен В-ның мүмкін жай сандар болмайтын, бірақ екеуі де қалдықсыз бөлінетін ортақ бөлгіші жоқ сандар (әрине 1 санынан басқа). N модулі бойынша А санын шегеру – бұл А санын N санына бөлгендегі бүтін санды қалдық.
N модулі бойынша А санын шегеру жиыны N модуліне А*L сандарын бөлудегі әр түрлі қалдықтар жиынтығы, мұндағы L - 1-ден N-1-ге дейін барлық мәндерді қабылдайды. Мысалы, 5 модулі бойынша 3 санын шегеру жиыны мынадай болады: {3,1,4,2}. Шегеру векторының ұзындығы максимальды және А мен N өзара жай сандар болғанда N-1-ге тең. Мультипликативті-кері сандарды есептеу Нақты сандар арифметикасында 0-ге тең емес а үшін 1
мультипликативті кері шаманы есептеу қиын емес: 1
=1/a немесе а* 1 а =1.
Мысалы, 4 санынан мультипликативті кері шама 4*1/4=1 болғандықтан ¼-ке тең. Модулярлы арифметикада кері шамаларды есептеу күрделі есеп болып табылады. Мысалы, 4*х
7*k+1 үшін х және k мәндерін табуға эквивалентті, мұндағы х және k – бүтін сандар. Бұл есептің жалпы қалыптасуы – х бүтін санды табу: а*х(mod n)=1 немесе 1 а х(mod n). Бұл есептің шешімі кейде болады, кейде болмайды. Мысалы, 14 модулі бойынша 5 саны үшін 5*3=15 1(mod 14) болғандықтан кері шама 3-ке тең. Екінші жағынан, 2 саны 14 модулі бойынша кері шамадан тұрмайды. Жалпы,
1
сандар болса. Егер а және n өзара жәй сандар болмаса, онда 1 а х(mod n) салыстырмасының шешімі болмайды. Кері шамаларды табудың негізгі тәсілдерін құрастырамыз: Айталық, бүтін сан а {0,1,2,…,n-1}. Егер ЕҮОБ(а, n)=1 болса, онда i=0,1,2,…,n-1 үшін а*i (mod n) - {0,1,2,…,n-1} жиынын алмастыру болып табылады. Мысалы, егер а=3 және n=7 (ЕҮОБ(3,7)=1) болса, онда i=0,1,…,6 үшін 3*i(mod 7) - {0,1,2,…,6} жиынының тізбегі болады. ЕҮОБ(а,n) 1 жағдайда ол дұрыс емес болады. Мысалы, егер а=2 және n=6 болса, онда 2*i(mod6) 0,1,2,4,0,2,4, i=0,1,2,…,5 үшін. Егер ЕҮОБ(а,n)=1 болса, онда 1 а , 0<
1
а* 1 а
Шынымен де, а*i(mod n) - 0,1,…, n-1 алмасуы болады, сондықтан а*i 1(mod n) үшін i бар болады. Жоғарыда келтірілгеннен, 0-ден n-1-ге дейінгі бүтін сандар жиынын n модулі бойынша шегерулердің толық жиыны деп айтамыз. Бұл кез келген а (а>0) бүтін сан үшін оның шегеруі: r =a(mod n) білдіреді, бұл 0-ден n-1-ге дейін интервалдағы кейбір бүтін сандар. Келтірілген шегерулер жиыны – бұл n-мен өзара жәй шегерулердің ішкі жиыны. k жәй санның модулі бойынша келтірілген шегерулер жиыны n-1 элементтерден тұрады. Мысал. Айталық n=11 модулі – жәй сан. 11: {0,1,2,…,10} модулі бойынша шегерудің толық жиыны. Келтірілген шегерулер жиынын құастыруда олардан бір элемент қана (0) өшіріледі. 11 модулі бойынша келтірілген шегерулер жиыны 11-1=10 элементтен тұрады. Мысал. Айталық модуль n=10 болсын. n=10: {0,1,2,…,9} модулі бойынша шегерулердің толық жиыны. Олардан тек 1,3,7,9 ғана 10-мен ортақ көбейткіші жоқ. Сондықтан 10 модулі бойынша шегерудің келтірілген жиыны {0,1,2,…,9}-ға тең. Бұл келтірілген жиынның қалыптасуында мына элементтер алынып тасталған:
0 (1 элемент);
2 еселілер (4 элемент);
5 еселілер (1 элемент). p*q=n жәй сандардың туындысы үшін келтірілген шегерулер жиыны (p-1)(q-1) элементтерден тұрады. n=p*q=2*5=10 үшін келтірілген жиындағы элементтер саны (p-1)(q-1)=(2-1)(5-1)=4
27=
3 3 модулі бойынша келтірілген шегерулер жиыны
18 элементтен {1,2,4,5,7,8,10,11,13,14,16,17,19,20,22,23,25,26} тұрады. Шегерулердің толық жиынынан 3 еселі элементтер алынып тасталады (барлығы тоғыз элемент). Модуль үшін n=3, r=3 болғанда
(n-1) элементтердің жәй дәрежесі түрінде аламыз: 1 3
(3-1)=
2 3 *2=18. Эйлер функциясы
функциясы
санын сипаттайды.
n – жәй сан 2
… r n
n-1 n(n-1) … ) 1 ( 1
n r
р*q (p,q – жәй сандар) (p-1)(q-1)
Егер n – жәй сан және ЕҮОБ(а,n)=1 болса, онда 1 n а mod n=1
1
а
1.
а* 1 а (mod n)
1 (а*х=1(mod n) болатын х= 1
(mod n) табылмайынша) болатын 1 а
1(mod n) табылмайынша 1,2,…,n-1 мәндерін кезекпен тексеру. Мысал. Айталық n=7, a=5 болсын. Табу керек: х = 1
(mod n). а*х
1(mod n) немесе 5*х =1(mod 7) n-1=7-1=6, Алатынымыз, x=5 -1 (mod 7)=3 Тексеру нәтижелері: х 5*х 5*х(mod 7) 1 2 3 4 5 6 5 10 15 20
25 30
5 3 1 6 4 2 2.
Эйлера функциясы (n) белгілі болса, 1
(mod n) табамыз:
1
(mod n)
1 ) n ( а (mod n) Мысал. Айталық n=7, a=5 болсын. Табу керек: х= 1
(mod n). х= 1 5 (mod 7). n=7 модулі – жәй сан. Сондықтан Эйлер функциясы (n)=
(7)=n-1=6 болады. Кері шама 5-тен mod7-ге дейін: 1 а (mod n)= 1 )
n а (mod n)= 1 6 5 mod 7=
5 5 mod 7 =( 2 5 mod 7) ( 3 5 mod 7) mod 7= (25 mod 7)(125 mod 7) mod 7=(4*6) mod 7=24 mod 7. Сонымен, х = 1 5
(mod 7)=3. 3.
Евклидтің кеңейтілген алгоритмінің көмегімен 1 а (mod n) кері шамасын табу. Евклидтің кеңейтілген алгоритмі: Берілген а және b теріс емес бүтін сандар үшін бұл алгоритм (U1,U2,U3) векторын анықтайды: a* U1+b*U2=U3=ЕҮОБ(a,b). Есептеу кезінде (V1,V2,V3), (t1,t2,t3) қосымша векторлар қолданылады. Туынды векторлармен әрекет барлық есептеу кезеңінде мына арақатынастар орындалады: а* t1+b* t2= t3, a* U1+b* U2= U3, a* V1+b* V2= V3. 1 а (mod n) кері шаманы есептеу үшін b=n, ЕҮОБ(a,n)=1 болғанда Евклидтің кеңейтілген алгоритмінің жеке жұмыс режимі қолданылады және бұл алгоритм (U1,U2,U3) векторын анықтайды: U3=1, a* U1+n*U2=ЕҮОБ(a,n)=1, (a* U1+n*U2) mod n a* U1(mod n) 1,
1
(mod n) U1(mod n). Алгоритм қадамдары: 1.
Бастапқы орнату. (U1,U2,U3):=(0,1,n) (V1,V2,V3):=(1,0,а) орнату. 2.
3.
Бөлу, шегеру. q:=[ U3/ V3] орнату керек. Одан кейін орнату керек (t1,t2,t3):= (U1,U2,U3)- (V1,V2,V3) * q; (U1,U2,U3):= (V1,V2,V3); (V1,V2,V3):= (t1,t2,t3). 2-ші қадамға ораламыз.
n=23 модулі және a=5 саны берілген. 1
(mod 23) кері санын табу керек, яғни х= 1 5 (mod 23). Евклидтің кеңейтілген алгоритмінің жеке қадамдарының нәтижесі:
- 4 1 1 - 0 1 -4 5 -9
1 0 1 -1 2 n=23 5 3 2 1 1 -4 5 -9
0 1 -1 2 а=5
3 2 1 U3=1, U1=-9, U2=2 үшін (a* U1+n*U2)mod n=(5*(-9)+23*2)mod 23=5*(-9)mod 23 1 1
(mod n) = 1 5 (mod 23) = (-9)mod 23=(-9+23)mod 23=14. Сонымен, х= 1 5 (mod 23) = 14(mod 23)=14.
Модуль туындысынан асып түспейтін кез келген теріс емес бүтін санды бір мәнді қалпына келтіруге болады, егер оның осы модуль бойынша шегерулері белгілі болса. Айталық m1,m2,…,mt – жұптасқан өзара жәй модульдер (1-ден үлкен бүтін сандар), яғни ЕҮОБ(mi,mj) =1, i j үшін. Айталық а1,а2,…,аt – бүтін сандар, 0 аi mi.
Айталық М=m1*m2*…*mt – барлық mi-дің туындысы. Мi=M/mi деп белгілейміз. Және Ni - Mi(mod mi)-ға кері болсын, i=1,2,…,t үшін, яғни Mi*Ni 1(mod mi) болады. ЕҮОБ (Mi, mi)=1 болса, онда кері элемент бар болады және Евклид алгоритмінен төмендегі арақатынас жеңіл табылады: Mi*Ni + mi*ni, i=1,2,…,t. х ai(mod mi), i=1,2,…,t салыстырмасы [0,M-1] интервалында жалғыз ортақ шешім болады
Қосымша әдебиет: 11қос[0-109], 20қос[86-115] Бақылау сұрақтары: 1.
Ашық кілтті криптожүйелер неге негізделген? 2.
Ашық кілтті криптожүйелерде қандай тұрақты өзгерулер қолданылатынын анықтаңыз. 3.
Ашық кілтті криптожүйелер алгоритмдерін қандай мақсаттарда қолдануға болады? 4.
Ферма теоремасын құрастырыңыз. 5.
Мультипликативті кері шаманы табу тәсілдерін көрсетіңіз.
Диффи-Хеллман алгоритмі. RSA алгоритмі Диффи мен Хелман біржақты функциялардың көмегімен құпия кілттің берілуін мүлдем талап етпейтін берік құпия жүйенің тұрғызылуы мүмкін екендігін дәлелдеген. Дискретті логарифмдер функцияларын қолдану арқылы қолданушылар арасында құпия кілттерді ауыстыру мысалы:
Айталық, барлық қолданушыларға және Р белгілі болсын. Қолданушы i кездейсоқ жағдайда хi, 1 xi p-1, бүтін санын таңдайды және бұл санды құпияда сақтайды, бірақ yi-ге хабарлайды:
(анықтамада құпия мәліметтерді айырбастау жүйесінің абоненті болғысы келетін барлық қолданушылардың yi мәндері тіркеледі, бірақ бұдан кейін олардың біреуі де өзінің yi-нен бас тарта алмайды). Егер енді қолданушылар i және j құпия байланыс орнатқылары келсе, онда оны мынадай тізбекпен іске асыруға болады: 1.
Қолданушы i анықтамадан yj мәнін таңдайды және өзінің құпия xi көмегімен z ij мәнін
есептейді:
Қолданушы j дәл осындай тәсілмен z ji мәнін есептейді:
болғандықтан, бұл мән екі қолданушыға ғана белгілі болады, өйткені оны есептеу үшін құпия хi мен хj қолданылған. 2.
Қолданушылар i мен j қандай да бір шифрлеу тәсілін қолдану жайлы келіседі, ал z ij= z ji мәндерін түйінді орнату ретінде қолданады. Ешбір қаскүнем yi және yj мәндері бойынша f(x)=a x (mod p) функциясы біржақты болғандықтан z ij= z ji есептей алмайды.
1.
Қолданушы өзінің yi мәнін есептеуде қате жіберуі мүмкін. 2.
Қаскүнем, торап абоненті болып және анықтамаға yi-ді орналастырып, анықтаманы қолданып, жоғарыда көрсетілген сызба бойынша олармен байланыс орната отырып басқа қолданушылардан құпия ақпарат алу мақсатымен басқа кез келген абоненттің атынан бүркемеленуі мүмкін. ) (mod
* * 1 M M N a x i i t i i
) P (mod
) x ( f x
) P (mod x y i i
). (mod ) mod ) mod
(( p p p z i j i j x x x x ij
). (mod
) (mod
) (
p y z j i j x x x i ji
)) (mod ) (mod ( ,
p z z i j j i x x x x ij ji
3.
Уақыт ағымына қарай хi қолданушылардың құпия мәндері қаскүнемге белгілі болуы мүмкін, онда ол берілген қолданушының барлық құпия жазбаларын оқуға мүмкіндік береді. Қауіп-қатердің алдын-алу үшін ақпаратты ашуға келесі шараларды өткізу талап етіледі: 1.
Лицензиялық қауіпсіздік қызметін құру. 2.
Ашық кілттер тарату жүйесінің абоненттер аутентификациясы құжаттарын құру. 3.
Абоненттердің алғашқы кіруін қауіпсіздік қызметінің араласуы арқылы құпия мәліметтерге айырбастау. 4.
кілттердің өзгеруі, абоненттердің жүйеден шығуы, абонентпен өзінің кілтін өзгерту жайлы қауіпсіздік қызметімен хабарлау. Алгоритмнің негізгі жетіспеушілігі – кілтті ашу қиындығының кепілденген төменгі бағасының болмауы. RSA алгоритмі (1978ж. – Р.Райвест, А. Шамир, А. Адлеман) RSA алгоритмі мәліметтерді шифрлеу режиміндегідей, сандық қолтаңба режимінде де жұмыс жасайды. Оның қорғалғандығын кепілдікпен бағалауға болады: (RSA-ны ашу екі үлкен жай сандардың туындыларының көбейтінділеріне бөлумен эквивалентті екендігі дәлелденген). RSA алгоритмі банктік компьютерлік тораптарда, әсіресе өшірілген клиенттермен жұмыс жасауда қолданылады (кредиттік карточкаларға қызмет ету). Қазіргі уақытта көптеген стандарттарда қолданылады (SSL, S-HHTP, S-MINE, S/WAN, STT және PCT). Алгоритмнің сенімділігі үлкен сандар факторизацияларының қиындықтарына және дискретті логарифмдерді есептеу қиындықтарына негізделеді. Криптожүйеде ашық кілт Кв, құпия кілт kв, хабар М және криптожүйе С бүтін сандар жиынына жатады:
N=P*Q P және Q – кездейсоқ үлкен жәй сандар. Максимальды қауіпсіздікті қамтамасыз ету үшін тең ұзындықтағы P мен Q-ді таңдайды да құпияда сақтайды. N модулі бойынша көбейту мен қосу операциялары бар Z N жиыны N модулі бойынша арифметика құрайды. Ашық кілт Кв-ны келесі шарттар орындалу үшін кездейсоқ таңдайды: 1 < Кв
(N),
ЕҮОБ(Кв, (N))=1 (N)=(P-1)(Q-1) мұндағы (N) – Эйлер функциясы. Эйлер функциясы
санын көрсетеді. Егер ЕҮОБ(а,b)=1 болса, онда а және b бүтін сандары – өзара жәй сандар. Жоғарыда көрсетілген шарттардың екіншісі ашық кілт Кв және Эйлер функциясы
болуы керек дегенді білдіреді. Ары қарай, Евклидтің кеңейтілген алгоритмін қолдана отырып, құпия кілт kв-ны есептейді: kв*Кв
1(mod
(N))
немесе kв=
1
(mod (Р-1)(Q-1)) kв мен N өзара жәй екенін байқаймыз. Ашық кілтті мәліметтерді шифрлеу үшін, ал құпия кілт kв-ны – мағынасын ашу үшін қолданады. Шифрлеудің өзгеруі жұптасу арқылы (ашық кілт Кв, хабар М) келесі формулаға сәйкес С криптограммасын анықтайды:
С мәнін жылдам есептеу алгоритмі негізінде N модулі бойынша келтірілген М-ге көбейту және бүтін М-ді квадраттаудың тізбектер қатары қолданылады. }, 1 ,..., 2 , 1 , 0 { N z N
) N (mod
К М ) М ( Ев ) М ( Е С В Кв
(1) (2) (3)
(4) (5)
(6)
функциясын айналдыру, яғни С-ның белгілі мәндері бойынша М мән анықтау, Кв және N N= 512
2
болғанда іске аспайды. С криптограммасының мағынасын ашу есебін жұпты (құпия кілт, С криптограммасы) қолдана отырып, келесі формула бойынша шешуге болады:
(7) мен (6)-ның мәндерін (8)-ге қоя отырып мынаны аламыз:
(N) шамасы Эйлер теоремасында маңызды қызмет атқарады (Ферманың кіші теоремасының кеңейтілуі), онда, егер ЕҮОБ(х,N)=1 болса, онда
немесе жалпы түрде:
(9) бен (10)-ды салыстыра отырып, Кв*kв=N* (N)+1
аламыз, немесе дәл солай Кв*kв
1(mod
(N)).
Сондықтан да құпия кілтті есептеу үшін (5) қолданылады. Сонымен, егер ) N (mod М С Кв
криптограммасын kв дәрежесіне шығарса, онда алатынымыз:
) (mod
) ( 1 ) ( * N Ě Ě Ě Ě N n Ęâk k Ęâ B â болғандықтан, М бастапқы мәтін қалпына келеді. Демек, криптожүйені құратын В алушы екі параметрді қорғайды: 1.
құпия кілт kв; 2.
N модулінің мәнін беретін (Р,Q) жұп сандарының туындысы. Басқа жағынан, В алушы N модулінің мәнін және Кв ашық кілттің мәнін ашады. Қарсыласқа тек Кв мен N-нің мәндері белгілі. Егер ол N санын Р және Q көбейткіштеріне бөлсе, онда ол үш санның {P, Q, Кв} «құпия кодын» біліп алар еді де, Эйлер функциясының мәндерін есептеп:
және kв құпия кілттің мәнін анықтар еді. Өте үлкен N-ді көбейткіштерге бөлу есептеуші негізінде жүзеге асырылмайды (таңдалған Р және Q ұзындықтары кем дегенде 100 мың белгілерден құралу керек, деген шартпен).
жүктеу/скачать 0,97 Mb. Достарыңызбен бөлісу:
|