2. 1 Дәрістік сабақтардың конспектісі Дәріс Кіріспе. Аж-де ақпаратты қорғаудың жалпы талдау мәселесі



жүктеу 0.93 Mb.
Pdf просмотр
бет4/9
Дата26.04.2017
өлшемі0.93 Mb.
1   2   3   4   5   6   7   8   9

Жай сан – бұл 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*х 

 

1(mod 7) салыстырмасын шешу 4*х 



 7*k+1 үшін х және мәндерін табуға эквивалентті, мұндағы 

х және k – бүтін сандар. 

Бұл есептің жалпы қалыптасуы  –  х бүтін санды табу: 

а*х(mod n)=1 немесе 

1



а

 х(mod n). 



Бұл  есептің  шешімі  кейде  болады,  кейде  болмайды.  Мысалы,  14  модулі  бойынша  5  саны 

үшін  5*3=15

1(mod  14)  болғандықтан  кері  шама  3-ке  тең.  Екінші  жағынан,  2  саны  14  модулі 



бойынша кері шамадан тұрмайды. 

Жалпы, 


1



а



 х(mod n) салыстырмасы жалғыз шешімнен тұрады, егер а және n – өзара жай 

сандар болса. 

Егер  а  және  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



а



(mod n). 

Шынымен де, а*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 болғанда 

r

n

(n-1) элементтердің жәй дәрежесі түрінде аламыз: 

1

3

3



(3-1)= 


2

3

*2=18. 



Эйлер    функциясы 



(n)  –  n-мен  өзара  жәй,    n-нен  кіші    оң  бүтін  сандар  саны.  Эйлер 

функциясы 



(n)  келтірілген  шегерулер  жиынында  элементтер 

санын сипаттайды. 

 

n модулі 



(n) функциясы 

n – жәй сан 

2

n

 

… 



r

n

 

n-1 



n(n-1) 

… 

)



1

(

1





n



n

r

 

р*q (p,q – жәй сандар) 



(p-1)(q-1) 

 

Ферманың кіші теориясы: 

Егер n – жәй сан және ЕҮОБ(а,n)=1 болса, онда 

1



n

а

mod n=1 



  

1



n



а



1(mod n) болады

 

Кері шамаларды табудың негізгі тәсілдері 

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) 





10 



15 

20 


25 

30 






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.

 

U3=1?. Егер U3=1 болса, онда алгоритм аяқталады. 



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). 

Евклидтің кеңейтілген алгоритмінің жеке қадамдарының нәтижесі: 

 



U1 

U2 

U3 

V1 

V2 

V3 





-4 



-9 




-1 

n=23 





-4 



-9 


-1 



а=5 




 

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] интервалында жалғыз ортақ шешім болады 

 

Негізгі әдебиет: 5нег[301-319] 



Қосымша әдебиет: 11қос[0-109], 20қос[86-115] 

Бақылау сұрақтары

1.

 



Ашық кілтті криптожүйелер неге негізделген? 

2.

 



Ашық кілтті криптожүйелерде қандай тұрақты өзгерулер қолданылатынын анықтаңыз. 

3.

 



Ашық кілтті криптожүйелер алгоритмдерін қандай мақсаттарда қолдануға болады? 

4.

 



Ферма теоремасын құрастырыңыз. 

5.

 



Мультипликативті кері шаманы табу тәсілдерін көрсетіңіз. 

 

Дәріс 7. Қорғау және қауіпсіздендіру жүйелерін практикалық іске асырудың мысалдары.  



Диффи-Хеллман алгоритмі. 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



p

y

z

j

i

j

x

x

x

i

ji



 

))



(mod

)

(mod



(

,

p



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). 

Алгоритмнің  сенімділігі  үлкен  сандар  факторизацияларының  қиындықтарына  және 

дискретті логарифмдерді есептеу қиындықтарына негізделеді. 

Криптожүйеде  ашық  кілт  Кв,  құпия  кілт  ,  хабар  М  және  криптожүйе  С  бүтін  сандар 

жиынына жатады: 

 

 

мұндағы N – модуль: 



                                                                    N=P*Q 

P және Q – кездейсоқ үлкен жәй сандар. 

Максимальды қауіпсіздікті қамтамасыз ету үшін тең ұзындықтағы  P мен Q-ді таңдайды да 

құпияда  сақтайды.  N  модулі  бойынша  көбейту  мен  қосу  операциялары  бар  Z



N

  жиыны  N  модулі 

бойынша арифметика құрайды. 

Ашық кілт Кв-ны келесі шарттар орындалу үшін кездейсоқ таңдайды: 

1 < Кв 



 



(N), 


ЕҮОБ(Кв, 

(N))=1 



(N)=(P-1)(Q-1) 

мұндағы 

(N) – Эйлер функциясы. 



Эйлер функциясы 



(N) N-мен өзара жәй, 1-ден  N-ге дейін интервалдағы оң бүтін сандардың 

санын  көрсетеді.  Егер  ЕҮОБ(а,b)=1  болса,  онда  а  және  b  бүтін  сандары  –  өзара  жәй  сандар. 

Жоғарыда көрсетілген шарттардың екіншісі ашық кілт Кв және Эйлер функциясы 



(N) өзара жәй 

болуы керек дегенді білдіреді. 

Ары қарай, Евклидтің кеңейтілген алгоритмін қолдана отырып, құпия кілт -ны есептейді: 

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

М

С



Кв

 



криптограммасын  дәрежесіне шығарса, онда алатынымыз:    

                             

)

(mod


)

(

1



)

(

*



N

Ě

Ě

Ě

Ě

N

n

Ęâk

k

Ęâ

B

â





 

болғандықтан,  М  бастапқы  мәтін  қалпына  келеді.  Демек,  криптожүйені  құратын  В  алушы  екі 

параметрді қорғайды: 

1.

 



құпия кілт kв; 

2.

 



N модулінің мәнін беретін (Р,Q) жұп сандарының  туындысы.  

Басқа жағынан, В алушы  N модулінің мәнін және Кв ашық кілттің мәнін ашады. 

Қарсыласқа тек Кв мен N-нің мәндері белгілі. Егер ол N санын Р және Q көбейткіштеріне бөлсе, 

онда ол үш санның  {P, Q, Кв} «құпия кодын» біліп алар еді де, Эйлер функциясының  мәндерін 

есептеп: 

 

және  құпия кілттің мәнін анықтар еді. 



Өте үлкен N-ді көбейткіштерге бөлу есептеуші негізінде жүзеге асырылмайды (таңдалған Р 

және Q ұзындықтары кем дегенде 100 мың белгілерден құралу керек, деген шартпен). 

 


Каталог: wp-content -> uploads
uploads -> Лекция: 20 Семинар 10 СӨЖ 30 соөЖ 30 Аралық бақылау 4 Консультация 2 Емтихан: 3
uploads -> МазМұны. Содержание жоғары білім. Высшее образование
uploads -> Қазақстан республикасы білім және ғылым министрлігі
uploads -> Л т т ы о а м д ы – с а я с и ж у р н а л журнал 1976 жылы Халықтар Достығы орденімен, 2002 жылы Қазақстан Журналистика Академиясының «Алтын Жұлдыз», 2008 жылы Қазақстан Журналистер Одағының сыйлығымен марапатталды
uploads -> Өмірбаяны Ол қазіргі Шығыс Қазақстан облысының Абай ауданы жерінде 1897
uploads -> Филология кафедрасы
uploads -> 46-ғылыми-әдiстемелiк конференция материалдары
uploads -> Ғылыми-танымдық конференция Қалмақтөбе көрінісі
uploads -> Қазақстан республикасы білім және ғылым министрлігі

жүктеу 0.93 Mb.

Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7   8   9




©emirb.org 2020
әкімшілігінің қараңыз

    Басты бет