Таырып №4. Апаратты орауды криптографиялы ралдарыны математикалы негіздері

Негізгі сратар: Модулярлы арифметикадаы есептеулер жне оларды криптографияда олданылуы

Модульді арифметикадаы есептеу орын жне оны криптографияда олданылуын арастырайы.

1. Жылдам дрежеге шыару алгоритмі.

Мысал арастырайы

Осылайша

3¹⁵mod7=(3*3¹⁴)mod7=(3*3⁶*3⁸)mod7=3*(3²*3)²*((3²)²)²mod7=(((3²*3)²)²*3²*3)mod7= 6.

3¹⁵6(mod 7)

 

Келесі тедеуді шешііздер:

(1) mod 17 (ответ 10)

(2) 2³⁰ mod 5 (ответ 4)

(3) 5¹⁶ mod 13 (ответ 1)

(4) 5³⁵ mod 33 (ответ 23)

(5) 7²³ mod 13 (ответ 2)

(6) 4³⁷ mod 26 (ответ 4)

2. Кері мнді табу.

(1), салыстырымы берілсін.

Мнда a, n- белгілі сандар. : - табу ажет, мндаы - а саныны кері маынасы. х- белгісізін ш жолмен табуа болады.

· Тура іріктеу дісімен.

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

· Евклид алгоритмі арылы.

 

Мысал:

: . Тріндегі салыстырым берілсін.

Тура іріктеу дісін олданайы.

 

Жауабы: 10

Тексерейік:

 

Эйлер функциясын олданып есептейік. - Эйлер функциясы деп аталады, оны маынасы n- кіші сандара те, ал арапайым сандар n-ге те.

 

Егер n жай сан болса онда

 

Егер , мндаы p,q- жай сандар, онда .

 

Егер , онда .

 

Онда тедеу (1) Эйлер функциясы арылы мына формуламен аныталады.

Онда алдыны мысал келесі трде шешіледі

тура іріктеу дісіндегідей 10 саны алынды.

лкейтілген Евклид алгоритмі. (1) тріндегі тедеу берілсін. лкен Евклид алгоритміні маынасы келесідей.

1. орнату.

2. Егер , алгоритм тедеуінде тотатылады, йтпесе 3 тарма орындалады.

3.

2 тармаа ораламыз.

 

-
				-3
	-3

Жауабы:

 

3. ax b mod n тедігіні шешімі.

 

ax в mod n, в 1 (2) тріндегі тедікті шешімі 2 кезеге блінеді.

1. ax₁ 1 mod n
2. x = x₁*в mod n

Мысал1: 3x 6 mod 17

1. 3x₁ 1 mod 17

x₁ = 6

1. x = 6*6 mod 17 = 2

Тексеру: 3*2 6 mod 17 = 6

 

Мысал2: 2x 7 mod 9

1. 2x₁ 1 mod 9

x₁ = 5

1. x = 5*7 mod 9 = 8

Тексеру: 2*8 7 mod 9 = 5

 

Мысал3: 4x 11 mod 33

1. 4x₁ 1 mod 17

x₁ = 4^(33)-1mod 33 = 4^20-1mod 33 = (4³)⁶ * 4 mod 33 = (31)⁶ * mod 33 = (31²)³ * 4 mod 33 = 4³ * 4 mod 33 = 31 * 4 mod 33 = 25

x₁ = 25

1. x = 25*11 mod 33 = 275 mod 33

x = 11

Тексеру: 25*11 11 mod 33 = 25

 

4. Салыстыру жйелерін шешу.

 

(3) жйе б.э. 1 асырында ытай математигі Сун Це- мен шешілген.

алды туралы ытай теоремасы: Шегеру модулі белгілі болатын модуліні туындысынан асып кетпейтін кез-келген теріс санды, алпына келтіруге болады. Бл тедік ежелгі ытайда белгілі болан жне «алдытар туралы ытай теоремасы» деген атпен белгілі. Бл теорема 1 асырда ытай математигі Сун Це- мен сынылан. алдытар туралы ытай теоремасы уатты криптографиялы рал болып табылады.

 

Шешім:

1) N = n₁* n₂ белгілейік, онда

N₁ = N/n₁ = n₂

N₂ = N/n₂ = n₁

2) Келесі тедікті шешейік:

Тедікті трлендірсек ол келесі трге келеді:

, онда

3) (3) жйесін шешуге болады:

x (a₁N₁y₁ + a₂N₂y₂) mod n₁ n₂

 

Мысал1:

1) N = 91

N₁ = 13

N₂ = 7

2) Тедікті шешейік:

3) Шешім:

x (3*13*6 + 8*7*2) mod 91 = (234+112) mod 91 = 346 mod 91 = 73

x = 73

Тексеру:

73 mod 7 = 3

73 mod 13 = 8

Мысал2:

1) N = 91

N₁ = 13

N₂ = 7

2) Тедікті шешейік:

3) Шешім:

x (5*13*6 + 8*7*2) mod 91 = (390+112) mod 91 = 502 mod 91 = 47

x = 47

Тексеру:

47 mod 7 = 5

47 mod 13 = 8

 

Мысал3:

 

1) N = 66

N₁ = 11

N₂ = 6

2) Тедікті шешейік:

3) Шешім:

x (4*11*5 + 3*6*2) mod 66 = (220+36) mod 66 = 256 mod 66 = 58

x = 58

Тексеру:

58 mod 6 = 4

58 mod 11 = 3