Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Сибирский Государственный Университет Телекоммуникаций и Информатики

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

gosy_otvety.docx

Скачиваний:

Добавлен:

30.04.2019

Размер:

1.15 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 56 / 106 7 8 9 10 > Следующая >>>

Раздел 6 Криптографические метод защиты информации.

65) Понятие сравнения целых чисел по данному модулю. Полная система вычетов по данному модулю. Приведенная система вычетов по данному модулю. Функция Эйлера.

Полная система вычетов называется простейшей при фиксированном модуле m, если остатки пробегают след значения: 0, 1, 2, 3… m-1.

Система чисел, взятых по 1му из каждого класса вычетов, взаимно-простых с модулем называется приведенной системой вычетов по данному модулю.

Приведенная система mod=10 [1,3,7,9,}

M=15 {1,2,4,7,8,11.13,14}

НОД (24325, 1024) НОД(13325,841)

{1,5,7,11}

Из бесконечного мн-ва приведенных систем вычетов по данному модулю простейшей является приведенная система остатков. Каждая приведенная система вычетов содержит столько вычетов, сколько существует нат чисел, не превосходящих m и взаимно-простых с m.

Пусть НОД А и m=1. Пусть Х пробегает полную систему вычетов, тогда линейная форма ax+b – будет пробегать полную систему вычетов.

Пример: m=5

{0,1,2,3,4} простая полная система вычетов

А=2; b=10

Ax+b, xЄ{0,1,2,3,4}

2x+10 {10,12,14,16,18}

0 2 4 1 3

Пусть НОД (a,m)=1. Чтобы значение формы ax пробегали приведенную систему вычетов по модулю m, необходимо и достаточно, чтобы x пробегала приведенную систему вычетов.

Пример: m=6

{0,1,2,3,4,5}

a=5

ax=5x 1,5

{5,25}

m=7

{0,1,2,3,4,5,6}

a=8 НОД {7,8}=1

8x+3, XЄ{0,1,2,3,4,5,6},

{3,11,19,27,35,43,51}

3, 4, 5, 6, 0, 1, 2

M=10{0,1,2,3,4,5,6,7,8,9}

{1,3,7,9}

a=11 НОД(10,11)=1

11x {11,33,77,99}

Ф-я Эйлера f(m) выражает число натуральных чисел, не превышающих m и взаимно-простых с модулем m. Существует f(m) классов вычетов, взаимно-простых с модулем m. Условились считать, что f(i) =1

Пусть m>1, и m= , тогда f(m) =m

f(m)=

Пример:

m8 8=2³

f(m)=8(1- )=4

f(m)=2²(2-1)=4

m=10 10=2

f(m)=10(1- )=4 P₁=2 α₁=1

f(m)=2⁰ 5⁰(2-1)(5-1)=4 P₂=5 α₂=1

m=24 24=2³ 3

P₂=3 α₂=1

f(m)=24(1- )(1- )=8 P₁=2 α₁=3

f(m)=2² 3⁰(2-1)(3-1)=8

Приведенная система вычетов по модулю P ( где P простое число) состоит из (P-1) вычетов

m=p

f(m)=p(1- )= p=p-1

f(m)=p^i-1(p-1)=p-1

66) Теорема Ферма, используемая при построении криптографических алгоритмов.

Пусть p-простое число и 0<a<p, тогда , тогда f(p)=p-1

A^f(p)=p-1

a^p-1mod p=1

0<a<p

3¹²mod 13=1

3¹² 1 mod 13

3¹³ 3 mod 13

3¹³mod 13=3

5²²mod11

5¹⁰mod11=1

5²² 22mod 11

5¹⁰ 5¹⁰-11 mod 11

5²⁰ 1 mod 11

5²² 25mod 11

25 3 mod 11

25 mod 11 =3

3¹⁷ mod 5

3¹¹ mod 5=1

3¹⁶ 1 mod 5

3¹⁷ 3 mod 5

67) Теорема Эйлера, используемая при построении криптографических алгоритмов.

Пусть a и b – взаимно простые числа, НОД (a,b)=1 тогда .

Пример:

a=2, b=4

f(b)=2’(2-1)=2

3³ mod 4=1

Используя теорему эйлера найти

f(b)=2 4=8³

3⁸mod 20 =1

3⁸ 1 mod 20

3⁹ 3 mod 20

3⁹ mod 20=3

2¹⁴mod 21

f(b)=3 (3-1)(7-1)=12

2¹² 1 mod 21

2¹⁴ 4 mod 21

2¹⁴mod 21=4

2¹⁰⁷mod159

68) Понятие простого числа и взаимно простых чисел. Алгоритм Эвклида поиска НОД двух целых чисел.

НОД(25,36)=1 –взаимно простые числа.

Сравнимые по данному модулю числа имеют с ним один и тот же НОД. Обратное не верно.

Пример, 1)НОД(1173, 323)

1173=323*3+204

323=204*1+119

204=119*1+85

119=85*1+34

85=34*2+17

34=17*2+0

Ответ: 17.

2)НОД(529, 1541, 1817)

1541=529*2+483 1817=529*3+230 1817=1541*1+276

529=483*1+46 529=230*2+69 1541=276*5+161

483=46*10+23 230=69*3+23 276=161*1+115

46=23*2+0 69=23*3+0 115=46*2+23

46=23*2+0

Целые числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме ±1

Простое число́ — это натуральное число, которое имеет ровно два различных натуральных делителя: единицу и самого себя.

69) Обобщенный алгоритм Евклида.

Если a и b -2 целых «+» числа, тогда сущ-ют целые (необязательно «+») числа x и y : ax+by=НОД(a,b)

Введем 3 строки:

U=( )

V=( )

T=( )

Вход: a b>0; a

Выход: НОД(a,b); x и y : ax+by= НОД(a,b)

U( ), V( )
WHILE do
q div =[
T -q -q )
U V, V
RETERN U(НОД, x, y)

Пример, a=28 b=19

U:( )

V:( )

q=1

T:( )

U:( ) НОД=1

V:( ) х=-2

q=2 y=3

T:( )

U:( )

V:( )

T:( )

U:( )

V:( )

70) Понятие инверсии по данному модулю.

Инверсия числа С по модулю m

Дано: с,m

Найти: d<m : c*d mod m=1

Такое число d существует тогда и только тогда, когда c и m- взаимно простые числа.

Число d, удовлетворяющее соотношение c*d mod m=1 называется инверсией числа с по m и обозначается: d= , т.е. c* mod m=1

Пример: 3*4 mod 11=1 след-но3-инверсия числа 4 по модулю 11, т.е. 3=

7*d mod 12=1 d=7 инверсия числа 7 mod 12=7,

т.е.

mod 11= =4
mod 11= =81 mod 11=4

71) Система Диффи-Хеллмана построения секретного ключа.

У Диффи и М. Хелман изобрели метод открытого распределения ключей в 1976 г. Этот метод позволяет пользователям обмениваться ключами по незащищенным каналам связи. Суть метода Диффи-Хелмана заключается в следующем: Пользователи А и В, участвующие в обмене инф., генерируют независимо др. от др. свои случайные секретные ключи k_Аи k_В(ключи k_Аи k_В–случайные большие целые числа, кот. хранятся польз-ми А и В в секрете ). Затем польз-ль А вычисляет на основании своего секретного ключа k_Аоткрытый ключ К_А= g^kA(mod N), одновременно польз-ль В вычисляет на основании своего секретного ключа k_B открытый ключ К_B = g^kB(mod N), где N и g-большие целые числа. Затем польз-ли А и В обмениваются своими открытыми ключами K_Aи K_B по незащищенному каналу и исп. их для вычисления общего сессионного ключа: польз-ль А: К=(К_B)^kA(mod N)=(g^kA)(mod N); польз-ль В: K’=(K_A)^kB(mod N)=(g^kA)^kB(mod N); при этом K=K’,так как (g^kB)^kA=(g^kA)^kB(mod N). Таким образом, результатом этих действий оказывается общий сессионный ключ, кот. явл. Функцией обоих секр ключей k_Aи k_B. Уникальность метода Диффи-Хелмана заключ в том, что пара абонентов имеет возможность получить известное только им секретное число, предавая по открытой сети открытые ключи. После этого абоненты могут приступить к защите передаваемой инф. уже известным проверенным способом-применяя симметричное шифрование с исп. полученного разделяемого секрета.

72) Шифр Шамира.

1)А выбирает случайное, большое число Р и открыто передаёт его В

2)А выбирает 2 числа С_А и d_A, такие, что С_А d_Amod(P-1)=1

Числа С_А и d_А абонент А держит в секрете.

3) B выбирает 2 числа , такие что: mod(p-1)=1 . Держит в секрете.

После этого А передает свое сообщ. m исп трехступенчатый протокол (m рассм.<p). Если оно велоко-разбивается на кусочки

В наст.время исп. Для передачи чисел.

1)А вычисляет число mod p

A пересылает(открыто) к В

2) В вычисляет число mod p

B передает абоненту А (открыто)

3)А вычисляет число mod p

A передает к В (открыто)

4)В вычисляет mod p

Утверждение:

Пример, p=23, p-1=22 , m=10

U:( )

V:( )

q=3

T:(1 )

U=(7,0,1)

V=(1,1,-3)

q=7

Т=0…

U=(1,1,-3)

V=0…

-k= 1 d_A=19 (22-3)

X₁=10⁷mod 23=14

X₂; X₃;X₄

1) X=Y mod A=g

2) y/a=b (целое)

3) B A=c

4) Y-C=g

73) Шифр Эль-Гамаля.

1)для всей группы абонентов выбираются некоторое большое простое число p и число g такое что 1<g<p-1 числа g и p передаются открытым способом/

каждый абонент выбирает < <p-1 (держится в секрете)

каждый абонент вычисляет свое (открытая информация для всех абонентов)

Пусть имеются 2 абонента A и B, A передает сообщение B, которое держит в секрете от остальных абонентов. Будем считать, что это цифровое сообщение m: m<p

А выбирает случайное число k: 1≤k≤p-2 (секретная инф)

А вычисляет: r=g^kmod p; =m mod p

А передает числа r, b аб-ту B

2. В получив (r,b) вычисляет

Пример,m=15, p=23, g=5

B выбрал =13

Пусть A выбрал k=7

A передает B 17 и 12

74) Шифр RSA.

А хочет передать сообщ. m абоненту B, причем m число, удовлетворяющее след требованию m<N_B

1)A шифрует сообщ. m по формуле: , которое передается абоненту B открыто.

2)В вычисляет

Для системы RSA важно, чтобы каждый абонент выбирал собственную пару p и q.Однако этого не требуется для пар-ра d-может быть одинаковым для всех абонентов. Рекомендуется d=3 (при соотв-м выборе p и q).

Если p и q не известны, то вычисляется обратной функции практически невозможно.

Пример: А передает В m=15

В выбирает

=(P_B-1)(Q_B-1)=(3

выбираем =3, ищем =

U(20, 0) (-k)*20+

VU(3, 1)

TVU(2, ,-6) q=6

TVU(1, ,7) q=1

7*3 mod 20 =1

Выполняем e= mod 33=9 передаем e к В.

В вычисляет mod 33=15

1) X=Y mod A=g

2) y/a=b (целое)

3) B A=c

4) Y-C=g

75) Понятие электронной подписи.

Свойства, которыми должна обладать любая, в частности электронная подпись:1)подписать док-т может только «законный владелец подписи (след-но никто не может подделать подпись); 2)автор подписи не может от нее отказаться; 3)в случае возникновения спора возможно участие третьих лиц(суда) для установления подлинности подписи.

Цифровая подпись должна обладать всеми 3мя свойствами.

76) Электронная подпись RSA.

Если абонент A планирует подписывать документ, то A должен выбрать параметры протокола RSA, т.е: 2 больших простых числа p и q -вычислить N) и ;- выбрать d, такое что d< и взаимно простое с ;-вычислить c: mod .

A публикует числа N и d, например помещает их на своем сайте, ассоциировав со своим именем, и хранит в секрете число C (p, q, -можно забыть, больше не понадобиться). Теперь A готов ставить свои подписи на док-тах или сообщениях.

Пусть A хочет подписать сообщение . Абонент A вычисляет хеш-функцию такую, что y=h( , которая ставит в соответствие сообщению число y.

Главное свойство хеш-функции заключается в невозможности изменить основной текст , не изменив y. Поэтому на след. шаге A достаточно снабдить подписью только число y и эта подпись будет относиться ко всему сообщению . Абонент А вычисляет число : S= – это и есть цифровая подпись – ( , S).она и передается. Каждый кто знает открытые параметры абонента А (N,d) может проверить подлинность его подписи, для этого необходимо взять подпис. сообщ. и вычислить:

1)хеш ф-ю h( ; 2) и число w= ; 3)проверить w=h(

Утверждение: если подпись подлинная, то w=h(

Док-во: w= = dc=k

Описанная ЭП удовл.всем требованиям, предъявл. К подписи:1)никто не может разложить N,кот. занимает 1024 бита по сост.на 1005г. на простые множители. Поэтому зная N и d невозможно найти с и не может подписать сообщ.;2)автор подписи не может отказаться от нее,т.к. никто другой её сфабриковать не может от имени абонента А;3)в случае спора заинтер. сторона может обратиться в суд.

Пример, Q=11 N=55 p=5

d=3 C*d mod 40=1; -k*40+C*3=1

U(40 1 0) C=-13 mod 40=27

VU(3 0 1)

TVU(1 1 -13) q=13

h( =13=y

A формирует сообщение след вида (a b b b a a, 7)

1) h( =13 w= = 13

h( =w, след-но S подлинная.

1) X=Y mod A=g

2) y/a=b (целое)

3) B A=c

4) Y-C=g

77) Электронная подпись на базе шифра Эль-Гамаля.

Пусть аб А собирается подписывать док-т. А выбирает большое простое число р и число g: 1<g<p-1 и : различные степени числа g суть различные числа по mod p. Числа p и g хранятся в открытом виде и могут быть общими для нескольких пользователей.

Абонент А выбирает случайное число х: 1<х<p-1, кот. держит в секрете (секретный ключ). А вычисляет y:y= , и публикует на сайте в качестве своего открытого ключа. На данный момент при больших р, зная y, задача вычисл. числа х неразрешима.

Пусть А хочет передать сообщ. = , подписанное своей ЭП.

1) А вычисляет хеш-функцию h= h( , кот.должна удовлетворять условию: 1<h<p

2) А выбирает случайное число k: (1<k<p-1), взаимно простое с (p-1) и держится в секрете. Вычисляет число

3) A вычисляет числа: U=(h-xr) mod(p-1) S= , где под подразумевают инверсию числа k, т.е. *k mod (p-1)=1 такое существует, т.к. k и (p-1) взаимно простые.

4) А формирует подписан.сообщение( ,r,S).

5) Получатель заново вычисляет значение h= h( .

6) Получатель проверяет подпись используя равенство

Утверждение: если подпись верна, то условие выполняется.

Требования к ЭП: (док-во)

1)никто, кроме А не может подписаться его подписью, т.к. при формировании её исп. секр. число х, более того сомножитель xr меняется от сообщения к сообщению, т.к. выбирается случайно.

2)абонент А не может отказаться от своей подписи, т.к. никто кроме него не знает х.

3)третье лицо может подтвердить, что она истинна; судья может проверить все вычисления, если ему предъявят числа х, само и r.

Пример: p=23 x=7 g=5

y= mod 23=17