ретінде жалған кездейсоқ кодтардың генераторлары (ЖККГ) көмегімен кілттер ағынын

   АҚШ-тың ұлттық стандарттар бюросымен ұсынылған, алгоритм бойынша жұмыс жасайтын 

конгруэнтті  генераторлар  сонымен  қатар  бағдарламалау  жүйесінде  де  қолданылады.  Бұл 

генераторлар 2

24

  кезеңдік  ұзындығынан  тұрады  және  жақсы  статистикалық қасиеттерге  ие.  Бірақ 

мұндай  кезең  ұзындығы  криптографиялық  қолданулар  үшін  аз.  Сонымен  қатар  конгруэнтті 

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

Сызықты  рекурентті  арақатынастар  негізіндегі  жалған  кездейсоқ  сандар  тізбегін 

генерациялау тәсілін қарастырамыз: 

















1

k

a

j

j

i

i

1

k

i

a

h

a

                                (1) 

мұндағы,  h

0



0, h

k

=1 және әрбір h

i

 - GF(q)- өрісіне

 

жатады. 

 

Өріс – келесі қасиеттерден тұратын элементтер жиыны:  

1)

 

онда қосу, азайту, көбейту және бөлу операциялары орындалады; 

2)

 



, 



, 



 өрістегі кез келген элементтер үшін келесі қатынастар орындалады: 

 

а) 

 

 

 б) 

 

 

в) 

 

3)

 

өрісте мынадай элементтер болуы керек: 0, 1, -



 және (



0 үшін) 



-1

, сонда  

 

 

 

 

 

 

 

Соңғы өріс элементтердің соңғы санынан тұрады. L элементтерден тұратын өріс GF(L) деп 

белгіленеді және Галуа (1811-1832) өрісі деп аталады. Соңғы өрістің барлық ноль емес элементтері 

тұрпайы

 

элемент деп аталатын, W өрісінің кейбір бекітілген элементінің дәрежесі түрінде берілуі 

мүмкін.  

Қарапайым  өрістер  келесі  түрде  беріледі:  айталық  Р  –  жәй  сан.  Сонда  0,  1,  2,  …  (р-1)    бүтін 

сандары  GF(p)  өрісін  құрайды,  бұл  жағдайда  қосу,  азайту,  көбейту  және  бөлу  операциялары  р 

модулі бойынша орындалады.  

GF(p) – бұл р модулі бойынша шегерулер кластарының өрісі, яғни  

 

 

мұнда 0 арқылы р еселі барлық сандар белгіленеді;  1 арқылы  р-ге бөлгенде 1 қалдық қалатын 

барлық сандарды береді және т. б. Сонымен бірге, р-1-дің орнына –1 жазуға болады. 

GF(p)-та 



=



 бекітілуі 



-



 - р-ға бөлінеді дегенді немесе 



 р модулі бойынша 



–ға теңеседі 

дегенді білдіреді, яғни  

 

 

р

n

  өрісіндегі  элементтер  –  барлығы  GF(p)  өрісіндегі  коэффициенттері  (n-1)  дәрежеден  аспайтын 

көпмүшелер.  GF(p

n

)-де  қосу  көпмүшелерді  қосудың  қарапайым  ережесі  бойынша  орындалады, 

сонымен  қатар    ұқсас  мүшелерді  келтіру  операциялары  р  модулі  бойынша  жүзеге  асады.  Екі 

көпмүшенің туындысы болмайтын, GF(p)-да коэффициенттері бар көпмүше (яғни  GF(p) өрісіндегі 

көпмүше)    ең  аз  дегенде  келтірілмейтін  деп  аталады.  Тұрпайы  көпмүше  автоматты  түрде 

келтірілмеген болады.  

Айталық 



  (х)  –  n  дәрежелі  келтірілмеген  көпмүше  болсын.  Сонда  өрістің  екі  элементінің 

туындысы олардың 



(х)-ке бөлінгеннен кейінгі алынған қалдықты көбейту нәтижесінде алынады.  

тілігі

ассоциатив



































 



 



   

втілігі

дистрибути







































 





















 

0+



=



 



+(-



)=0 

0*



=0 

1*



=



 



*(



-1

)=1 

 









,

1

,...

2

,

1

,

0

)

(





p

p

GF

 





p

mod







 

Сонымен,  GF(p

n

)  өрісін  GF(p)  үстіндегі  көпмүшелердің  эквивалент  кластарының  өрісі 

түрінде  көруге  болады.  Екі  мұндай  көпмүше  эквивалентті,  егер  олардың  айырмалары 



  (х)-ке 

бөлінсе. 

 

Мысал.  Төмендегі есепті қарастырамыз: 

Бұл өрістің барлық ноль емес элементтерін 2 немесе 3 дәрежеде көруге болады, яғни 2 және 

3 – тұрпайы элементтер. 

 (1)-теңдеудің  шешімі  GF(q)  өрісінің  а

1

,а

2

,а

3

… элементтер тізбегі болып табылады. Мұндай 

қатардың тізбегі сызықты кері байланыспен жылжымалы регистр базасында тұрғызылған сандар 

тізбегінің генераторы көмегімен жеңіл іске асады (сонымен қатар сызықты тізбекті машина деп те 

атайды, СТМ). Егер СТМ полином туғызушы негізінде тұрғызылған болса, онда ол қайталаудың 

максималды кезеңінен тұратыны дәлелденген. 

n дәрежелі туғызушы полином деп мына өрнекті айтуға болады:  

қалғандары 0-ге немесе 1-ге тең. 

Туғызушы полиномдар 2 қасиеттен тұрады:  

1) басқа ешбір полиномға бөлінбейді; 

2)  х

n+1

 



 1 полиномының бөлгіші болады. 

 

СТМ-ның тұрғызылуы: 

1.

 

талап  етілетін  генерация  кезеңінен  шығатындай  сәйкес  дәрежелі  туғызушы  полином 

табылады.  (  Егер  2

n

-1  -  жай  сан  болса,  онда  тізбек  2

n

-1  кезеңінен  тұрады  (n  дәрежелі    h(x) 

келтірілмеген тұрпайы көпмүшесімен сәйкес жылжымалы регистр  құрылымын таңдау үшін). 

Мұндай  n=m  мәндеріне  негізінен  2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203  сандары 

жатады,  ал  олардың  ішінде    2

m

-1  формуласы  бойынша  алынған  жәй  сандар  Мерсеннің  жәй 

сандары деп аталады). 

2.

 

сәйкес  разрядты  жылжымалы  регистр  тұрғызылады  (қажет  жағдайда  бірнеше  жылжымалы 

регистрлер каскадты бірігеді). 

3.

 

жылжымалы регистрдің бастапқы толтырылуы кез келген мән болуы мүмкін (ол генерациялар 

базасы деп аталады). 

4.

 

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

шығуы 2 модул бойынша сумматорда болады. 

5.

 

қосымша 2 модулі бойынша сумматорға «1» константасы беріледі. 

6.

 

2 модулі бойынша сумматордың шығуы жылжымалы регистрдің кіруіне мүмкіндік береді. 

7.

 

жиналған сызбаны жүктегеннен кейін әр итерактивті қадамда регистр құрамы оңға ығысады, 

ал босаған сол жақ разряд сумматордың биттік шығуымен толтырылады. 

СТМ-да кездейсоқ сандар генераторының биттік шығуы деп жылжымалы регистр биттерінің 

кез келгені немесе сумматордың шығуы саналады. 

 

Мысал.  





















4

2

:

3

5

2

:

3

;

3

5

mod

8

2

*

4

;

2

3

5

3

4

1

;

1

5

mod

6

4

2

4

,

3

,

2

,

1

,

0

)

5

(































ńîíäŕ

GF

 

2

0

=1,   2

1

=2,   2

2

=4,   2

3

=3 

3

0

=1,   3

1

=3,   3

2

=4,   3

3

=2 



n



n

 



 A

n-1



n-1

 



 A

n-2



n-2

 



 … 



 A

1



1

 



 A

0

 

мұндағы  A

0

=A

n

=1,

 

СТМ сызбасы және онымен генерацияланатын туғызушы полином үшін кездейсоқ биттік тізбек.  

ТМ-да  кездейсоқ  сандар генераторының  маңызды  қасиеті  болып  n  разрядты  әр  түрлі  СТМ 

саны табылады, яғни  n дәрежелі әртүрлі көрінбейтін полиномдар саны.  

 

Негізгі әдебиет: 3нег[119-125], 4нег[39-83] 

Қосымша әдебиет:  

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

1.

 

Қандай есептерді шешу үшін ЖККГ қолданылады? 

2.

 

Жалған кездейсоқ сандар тізбегінің криптографиялық берік генераторына қойылатын 

негізгі талаптарды анықтаңыз. 

3.

 

ЭЕМ-да жалған кездейсоқ сандар генерациясының негізгі тәсілдерін көрсетіңіз. 

4.

 

Сызықты конгруэнтті генератор формуласын келтіріңіз. Формуладағы коэффициенттердің 

тағайындалуы қандай? 

 

Дәріс 6. Ақпараттық жүйелердің қәуіпсіздік модельдері. 

 Ашық кілтті криптожүйелер (асимметриялы жүйелер – АЖ).  

Сандар теориясына кіріспе  

Ашық  кілтті  криптожүйелер  классикалық  және  қазіргі  кездегі  алгебра  негізінде  өңделген 

(Диффи және Хеллман, 1975ж.) 

   Оның мәні: АЖ-ның әрбір адрес иесімен арнайы ереже бойынша өзара байланысқан екі кілт 

генерацияланады: 1-ші кілт – ашық, екіншісі – жабық.  

   Бір  кілт  ашық  болып  жарияланса,  екіншісі  жабық  болады.  Ашық  кілт  жарияланады  және 

адрес  иесіне  хабар  жібергісі  келген  кез  келген  адамға  ашық.  Жабық  кілт  адрес  иесімен  құпияда 

сақталады.  Бастапқы  мәтін  ашық  кілтпен  шифрленеді  және  адрес  иесіне  беріледі.  Хабардың 

шифрін ашу адрес иесінің өзіне ғана белгілі жабық кілтті қолдану арқылы жүзеге асуы мүмкін. 

 n дәреже 

Мүмкін болатын СТМ 

саны 

5 

6 

6 

8 

7 

18 

8 

16 

9 

48 

10 

60 

16 

2048 

 



3 



 



 



 1       (кезең тең 2

3

-1=7) 

+ 

X

3 

X

2 

X

1 

1

 

0

0

0

1

0

0

1

1

0

0

1

1

1

0

1

0

1

0

0

0

1

0

0

0

2

3

Х

Х

Х

 

 Ашық кілтті криптожүйелер келесі қасиеттерге ие біржақты функцияларды қолданады: 



 

Х-тің  берілген  мәнінде  біршама  f(x)  мәнін  есептеу  керек  және  y=f(x)  үшін  Х-ті  табу 

мүмкін емес.  

Келесі тұрақты өзгерулер қолданылады: 

1.

 

Үлкен сандарды жәй көбейткіштерге бөлу. 

2.

 

Шекті өрісте логарифмді есептеу. 

3.

 

Алгебралық теңдеулердің түбірлерін есептеу. 

1: Тікелей есеп – Р және Q екі өте үлкен бүтін сандардың туындысын есептеу, яғни   

 

 

мәндерін есептеу, ЭЕМ үшін біршама күрделі емес есеп.  

Кері есеп – көбейткіштерге үлкен бүтін санды бөлу, яғни үлкен N үшін шешілмейтін есеп 

N=P*Q үлкен санның Р және Q бөлгіштерін табу. 

    Сандар теориясының қазіргі бағалары бойынша N санын бөлуде бүтін N



2

664

 және P



Q үшін 

23

10

-не жуық операциялар қажет болады, яғни қазіргі ЭЕМ-дер үшін есептер мүлдем шешілмейді. 

2: Бірбағытты функциялардың келесі мысалы – бекітілген негізбен және модулі бар модульді 

экспонента. 

     Айталық А және N –  1 



 А < N болатын бүтін сандар. 

Z

N

 жиынын анықтаймыз: 

 

Сонда N модулі бойынша А негізі бар модульді экспонента мына функцияны береді:  

 

 

 

мұндағы х – бүтін сан, 1 



 х < N-1. 

   f

A,N

(x) функциясының мәнін жылдам есептейтін тиімді алгоритмдер бар.  

   Егер Y =A

x 

болса, онда былай жазуға болады: 

 

 

Сондықтан f

A,N

(x) функциясын айналдыру есебін дискретті логарифмдеу есебі деп атайды. 

Дискретті логарифмдеу есебі келесі түрде құралады: 

Белгілі А, N, Y үшін бүтін X санын табу керек: 

 

 

Дискретті  логарифмнің  алгоритмін  есептеу  әлі  табылған  жоқ.  Сондықтан  модульді  экспонента 

бірбағытты  функция  болып  саналады.  Бүтін  сандар  үшін  сандар  теориясының  қазіргі  бағалары 

бойынша: 

 

Дискретті логарифмдеу есебін шешу 10

26

 операцияларын қажет етеді. Бұл есеп көбейткішке 

бөлгендегі есепке қарағанда 10

3

-не көбірек есептеу күрделілігінен тұрады. 

Ашық кілтті криптожүйелерді тұрғызу үшін қолданылатын функциялардың екінші маңызды 

класы «жасырын кодты» бірбағытты функциялар болып табылады.  



  Ашық  кілтті  жүйелерге  (АКЖ)  сенімді  ақпаратты  қорғауды  кепілдік  ету  үшін  екі  талап 

қойылады: 

1.

 

Бастапқы  мәтіннің  өзгеруі  тұрақты  болуы  керек  және  оны  ашық  кілттің  негізінде 

қалпына келуін шығару. 

2.

 

Ашық  кілттің  негізінде  жабық  кілттің  анықталуы  қазіргі  кездегі  технологиялық 

деңгейде мүмкін емес. 



  Ашық  кілтті  криптожүйелер    (АКК)  алгоритмдерін  үш  тағайындалуда  қолдануға 

болады: 

1.

 

Берілетін және сақталатын мәліметтерді өзіндік қорғау құралдары ретінде. 

2.

 

Кілттерді  таратуға  арналған  құралдар  ретінде.  (АКК  алгоритмдері  дәстүрлі 

криптожүйелерге  қарағанда  қиындау.  Сондықтан  пратикада  АК-ның  көмегімен 

кілттерді тарату тиімдірек, содан кейін симметриялы алгоритмдердің көмегімен үлкен 

ақпаратты ағындарды ауыстыруды жүзеге асыру). 

3.

 

Аутентификациялар құралдары ретінде  (қолданушылар). 

Q

*

P

N



 

}

1

N

,...,

2

,

1

,

0

{

Z

N





 

N

N

N

,

A

Z

Z

:

f



 

),

N

(mod

A

)

x

(

f

x

N

,

A



 

).

y

(

log

x

A



 

.

y

N

mod

A

x



 

664

664

2

2





N

ěĺí

A

 

Сандар теориясына кіріспе. 

Конгруэнттілік және сандарды модуль бойынша алу. 

 N басқа санның модулі бойынша А санын алу операциясы нәтижелі В саны А санының N 

санына бөлгендегі қалдық болып табылады: 

 

 

 

 

 Бо                                                -   болатынын байқаймыз. 

 

  Модуль бойынша сандарды алу операциясы 3 негізгі қасиеттен тұрады: 

1.

 

аддитивтілігі: 

 

 

2.

 

мультипликативтілігі:  

 

 

 

3.

 

дәреженің сақталуы:  

 

 

  Модуль бойынша жұмыс істеу ыңғайлы, өйткені олар барлық аралық шамалар диапазоны мен 

нәтижелерді  шектейді.  n  модулі  бойынша  а  санының  дәрежесін  (a

x

  mod  n)  есептеуді  көбейтулер 

мен бөлулер қатары ретінде орындауға болады. Бұл операциялар дистрибутивті болғандықтан  әр 

кезде модуль бойынша келтіруді орындай отырып, көбейткіштер тізбегі қатары ретінде дәрежеге 

шығарады. Бұл ұзын сандармен жұмыс жасағанда белгілі болады (200 бит және одан көп). 

Мысал. 

a

8

 mod n есептеу керек. 

(а*а*а*а*а*а*а*а)  mod  n  орындауға  болмайды.  Мұның  орнына  модуль  бойынша  үш  кіші 

көбейту мен үш кіші келтіру орындалады: 

 

 

А және В сандарының  ең үлкен ортақ бөлгіші (ЕҮОБ)  – бұл осы екі сан да қалдықсыз     

бөлінетін  сандардың үлкені. 

Мысал. 

 

 

 

 

 

Ең  үлкен  ортақ  бөлгішті  Евклид  алгоритмінің  көмегімен  есептеуге  болады.  Евклид  бұл 

алгоритмді өзінің б.э.д. 300 жыл бұрын жазған «Начала» кітабында көрсеткен. 

ЕҮОБ (а,b) іздеу алгоритмі: 

Белгілеулер: 



 

qi – жеке; 



 

ri – қалдық. 



 

 

` 

 

 

 

 

 

 

 

Бөлуден  қалған  ri  қалдық  натурал  сандар  тізбегінің  қатаң  кемуін  құрайды.  Бұл  тізбектен 

алатынымыз, r

к

 - а және в сандарының ортақ бөлгіші, сонымен бірге  а мен в-ның ортақ бөлгіші r

к

 

B

N

mod

A



 

,

1

11

mod

100



 

)

7

(mod

9

)

7

(mod

2

)

7

(mod

5

)

7

(mod

12











 

N

mod

))

N

mod

B

)

N

mod

A

((

N

mod

)

B

A

(







 

 

 

 

 

N

mod

))

N

mod

B

*

)

N

mod

A

((

N

mod

)

B

*

A

(



 

)

N

mod

A

(

)

N

mod

)

N

mod

A

((

k

k



 

.

mod

)

mod

)

mod

((

2

2

2

n

n

n

a

 

1

)

19

,

150

(

38

)

190

,

76

(

14

)

98

,

56

(







҇О

҇О

҇О

 

1

1

1

2

3

3

2

1

2

2

1

1

1

*

*

......

..........

..........

*

*

*



























k

k

k

k

k

k

k

q

r

r

r

q

r

r

r

q

r

r

r

q

r

b

r

q

b

a

 

1

2

3

1

2

1

0

......

..........

..........

0

0

0



















k

k

r

r

r

r

r

r

b

r

 

 

болады:  r

к

=ЕҮОБ(а,b)  (Алгоритм  кепілдікпен  Log2(max)  итерациясынан  кейін  А  және  В-ның  ең 

үлкен ортақ бөлгішін табады, мұндағы max – А мен В сандарының үлкені). 

жүктеу/скачать 0,97 Mb.

Достарыңызбен бөлісу: