Тақырып №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