Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
1. Понятие сравнения целых чисел по данному модулю. Полная система вычетов по данному модулю. Приведенная система вычетов по данному модулю. Функция Эйлера.
Каждому модулю соот-ет бескон-ное множество полных систем вычетов, простейшие из кот полная система остатков. m=7 {0,1,2,3,4,5,6}
Система целых чисел т и тт является полной системой вычетов по модулю m, когда s=m для всех i, j и i≠j. Пр: 20,-4,22,18,-1 m=5 {0,1,2,3,4}, -4=-5*1+1, -1=-5*1+4
Пусть НОД (a,m)=1, x пробегает полную систему вычетов, тогда линейная форма ах+b будет пробегать полную систему вычетов. Пр: m=5, a=-3, -3x+1= {13,4,-53,-59,-65} => {3,4,2,1,0}
Система чисел, взятых по одному из каждого класса вычетов, взаимопростых с модулем, наз-ся приведенной системой вычетов по данному модулю {-4,-1,18,20,22}, m=5 => {-4,-1,18,22}
Из бесконечного множества приведенных систем вычетов по данному модулю простейшей явл система остатков. Пр: m=10, {0,1,2,3,4,5,6,7,8,9} => {1,3,7,9}
Каждая приведенная система вычетов содержит столько вычетов, сколько существует натуральных чисел, не превосходящих m и взаимопростых с m. Эту функцию от m наз-ют функцией Эйлера и обознач-т [фи]
Система чисел т и тт явл приведенной системой вычетов по модулю m, когда s=и и j≠i и НОД=1 для любых i и j.
Чтобы значения линейной формы ax, где НОД(a,m)=1, пробегали прив.сист вычетов по мод m, необходимо и достаточно, чтобы соот-щие значения х пробегали прив.сист вычетов по мод m.
Функция Эйлера выражает число натур.чисел, не превышающих m и взаимопростых с m.
Сущ-т классов вычетов, взаимнопростых с m. Условимся считать что =1; {1,3,7,9} => ; a=-4 => {-1,-3,-7,-9}.
. Если m=1 и , то – кол-во классов вычетов по модулю m.
или .
Пр.: m=10=2*5; или
2. Теорема Ферма, используемая при построении криптографических алгоритмов.
Пусть p-простое число и 0<a<p, тогда
Примет, p=17, a=3
1)
2) a mod 17
3 9 13 16 1
3)
4) y=
3. Теорема Эйлера, используемая при построении криптографических алгоритмов.
Пусть a и b – взаимно простые числа, тогда является частным случаем Th Ферма.
Пример,a=4, b=25 : ; ; ;
1)
2) a mod 25
4 16 6 11 21
3)
4)
4. Понятие простого числа и взаимно простых чисел. Алгоритм Эвклида поиска НОД двух целых чисел.
НОД(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
5. Обобщенный алгоритм Евклида.
Если 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)
Пример, a=28 b=19
U:()
V:()
q=1
T:()
U:() НОД=1
V:() х=-2
q=2 y=3
T:()
U:()
V:()
T:()
U:()
V:()
6. Понятие инверсии по данному модулю.
Инверсия числа С по модулю 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, т.е.
7. Система Диффи-Хеллмана построения секретного ключа.
У Диффи и М. Хелман изобрели метод открытого распределения ключей в 1976 г. Этот метод позволяет пользователям обмениваться ключами по незащищенным каналам связи. Суть метода Диффи-Хелмана заключается в следующем: Пользователи А и В, участвующие в обмене инф., генерируют независимо др. от др. свои случайные секретные ключи kА и kВ (ключи kА и kВ–случайные большие целые числа, кот. хранятся польз-ми А и В в секрете ). Затем польз-ль А вычисляет на основании своего секретного ключа kА открытый ключ КА= gkA(mod N), одновременно польз-ль В вычисляет на основании своего секретного ключа kB открытый ключ КB = gkB(mod N), где N и g-большие целые числа. Затем польз-ли А и В обмениваются своими открытыми ключами KA и KB по незащищенному каналу и исп. их для вычисления общего сессионного ключа: польз-ль А: К=(КB)kA(mod N)=(gkA)(mod N); польз-ль В: K’=(KA)kB(mod N)=(gkA)kB(mod N); при этом K=K’,так как (gkB)kA=(gkA)kB(mod N). Таким образом, результатом этих действий оказывается общий сессионный ключ, кот. явл. Функцией обоих секр ключей kA и kB. Уникальность метода Диффи-Хелмана заключ в том, что пара абонентов имеет возможность получить известное только им секретное число, предавая по открытой сети открытые ключи. После этого абоненты могут приступить к защите передаваемой инф. уже известным проверенным способом-применяя симметричное шифрование с исп. полученного разделяемого секрета.
8. Шифр Шамира.
1)
2)
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
Утверждение:
Док-во: любое число e: e=k*(p-1)+r, r=e mod (p-1)
mod p= mod p= mod p= mod p= mod p=m mod p=m
Пример, p=3, p-1=22 ,
U:()
V:()
T:(1) q=3
9. Шифр Эль-Гамаля.
1)для всей группы абонентов выбираются некоторое большое простое число p и число g: 1<g<p (g-есть такое число, что все числа из множества{1,..,p-1} смогут быть представлены как различные степени числа g по модулю p)
числа g и p передаются открытым способом всем абонентам.
каждый абонент выбирает < <p-1 (держится в секрете)
каждый абонент вычисляет свое (открытая информация для всех абонентов)
Пусть имеются 2 абонента A и B, A передает сообщение B, которое держит в секрете от остальных абонентов. Будем считать, что это цифровое сообщение m: m<p
B вычисляет число
Утверждение:
Доказательство:
Пример,m=15, p=23, g=5
B выбрал =13
Пусть A выбрал k=7
15 mod23=15
A передает B 17 и 12
mod 23
1)
2) a mod 23
17 13 8 18
3)
4)
10. Шифр RSA.
А хочет передать сообщ. m абоненту B. Будем считать, что m<
1)A шифрует сообщ. m по формуле:, которое передается абоненту B открыто.
2)В вычисляет
Утверждение!
Док-во: ====m
, след-но k : =*k+1 =(=, если p и q-простые числа, то
Для системы RSA важно, чтобы каждый абонент выбирал собственную пару p и q.Однако этого не требуется для пар-ра d-может быть одинаковым для всех абонентов. Рекомендуется d=3 (при соотв-м выборе p и q).
Если p и q не известны, то вычисляется обратной функции практически невозможны.
Пример, А передает В m=15
В выбирает
=(3
выбираем =3, ищем =
=1
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
a mod 33
9 15 27
4)
11. Понятие электронной подписи.
Свойства, которыми должна обладать любая, в частности электронная подпись:1)подписать док-т может только «законный владелец подписи (след-но никто не может подделать подпись); 2)автор подписи не может от нее отказаться; 3)в случае возникновения спора возможно участие третьих лиц(суда) для установления подлинности подписи.
Цифровая подпись должна обладать всеми 3мя свойствами.
12. Электронная подпись 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 0) C=-13 mod 40=27
VU(3 1)
TVU(1 -13) q=13
h(=13=y
a mod 55
13 4 16 36 31
A→B (, 7)
1) h(=13 w=13
h(=w, след-но S подлинная.
13. Электронная подпись на базе шифра Эль-Гамаля.
Пусть абонент А собирается подписывать док-т.
А выбирает большое простое число р и число 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 меняется от сообщ. К сообщ-ю, т.к. выбирается случайно, то и r-случайное число.
2)А не может отказаться от своей подписи, т.к. никто кроме него не знает х.
3)третье лицо может подтвердить, что она истинна; судья может проверить все вычисления, если ему предъявят числа х, само и r.
Пример, p=23 x=7 g=5
y=mod 23=17
h(=3
k=5 НОД(5,22)=1
r=mod 23=20
u=(3-7*20) mod 22=-137 mod 22=17 (-137=-154+17)
mod 22=1
u(22,1,0) TVU(2, ,-4) q=4
vu(5,0,1) TVU(1, ,9) q=2
S=9*17 mod 22=21
Отправляет (baaab, 20,21)
h(=3
* mod 23=15*16 mod 23=10
mod 23
a mod 23
20 9 12 6 13
mod 23=10, след-но верно.