КАТЕГОРИЯ:


Астрономия- (809) Биология- (7483) Биотехнологии- (1457) Военное дело- (14632) Высокие технологии- (1363) География- (913) Геология- (1438) Государство- (451) Демография- (1065) Дом- (47672) Журналистика и СМИ- (912) Изобретательство- (14524) Иностранные языки- (4268) Информатика- (17799) Искусство- (1338) История- (13644) Компьютеры- (11121) Косметика- (55) Кулинария- (373) Культура- (8427) Лингвистика- (374) Литература- (1642) Маркетинг- (23702) Математика- (16968) Машиностроение- (1700) Медицина- (12668) Менеджмент- (24684) Механика- (15423) Науковедение- (506) Образование- (11852) Охрана труда- (3308) Педагогика- (5571) Полиграфия- (1312) Политика- (7869) Право- (5454) Приборостроение- (1369) Программирование- (2801) Производство- (97182) Промышленность- (8706) Психология- (18388) Религия- (3217) Связь- (10668) Сельское хозяйство- (299) Социология- (6455) Спорт- (42831) Строительство- (4793) Торговля- (5050) Транспорт- (2929) Туризм- (1568) Физика- (3942) Философия- (17015) Финансы- (26596) Химия- (22929) Экология- (12095) Экономика- (9961) Электроника- (8441) Электротехника- (4623) Энергетика- (12629) Юриспруденция- (1492) Ядерная техника- (1748) Arhitektura- (3434) Astronomiya- (809) Biologiya- (7483) Biotehnologii- (1457) Военни бизнесмен (14632) Висока technologies- (1363) Geografiya- (913) Geologiya- (1438) на държавата (451) Demografiya- ( 1065) Къща- (47672) журналистика и смирен (912) Izobretatelstvo- (14524) външен >(4268) Informatika- (17799) Iskusstvo- (1338) историята е (13644) Компютри- (11,121) Kosmetika- (55) Kulinariya- (373) културата е (8427) Lingvistika- (374) Literatura- (1642) маркетинг-(23702) математиците на (16968) Механична инженерно (1700) медицина-(12668) Management- (24684) Mehanika- (15423) Naukovedenie- (506) образователна (11852) truda- сигурност (3308) Pedagogika- (5571) Poligrafiya- (1312) Politika- (7869) Лево- (5454) Priborostroenie- (1369) Programmirovanie- (2801) производствено (97 182 ) индустрия- (8706) Psihologiya- (18388) Religiya- (3217) Svyaz (10668) Agriculture- (299) Sotsiologiya- (6455) на (42831) спортист строително (4793) Torgovlya- (5050) транспорт ( 2929) Turizm- (1568) физик (3942) Filosofiya- (17015) Finansy- (26596) химия (22929) Ekologiya- (12095) Ekonomika- (9961) Electronics- (8441) Elektrotehnika- (4623) Мощност инженерно ( 12629) Yurisprudentsiya- (1492) ядрена technics- (1748)

Encryption алгоритъм за Шамир

157, 163, 167, 173, 179, 181, 191, 193, 197, 199.

Разширяването на броя на простите числа

Всеки съставно число може да бъде еднозначно представени като продукт на основните фактори. Например,

48 = 2 · 2 · 2 · 2 · 3, 225 = 3 5 · 3 · 5 · 1050 · ​​2 = 3 х 5 х 5 х 7.

За малки числа тази експанзия е лесно да се направи въз основа на таблицата за умножение. За по-големи числа предлагаме следния метод, който ние считаме конкретен пример. Ние разшири броя на простите фактори на 1463. За да направите това, използвайте таблицата на простите числа:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,

47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,

103, 107, 109, 113, 127, 131, 137, 139, 149, 151,

Loop чрез цифрите на масата и спирка на този номер, който е делител на дадено число. В този пример, 1463 7. Разделя се на 7 и да получите 209. Сега повторете процеса за сортиране прости числа 209 и спира в брой 11, който е нейната подгрупа (вж. Раздел "Признаци на делимост"). Разделя се на 11 и 209 се получи 19, които в съответствие със същата таблица е просто число. По този начин, ние имаме: 1463 = 7 ∙ 11 ∙ 19, т.е. прости делители на 1463 са 7, 11 и 19. Описаният процес може да се запише, както следва:

делител на дивидент
----------------------------
1463 7
209 11
19 19
----------------------------

1.1 Shifrosistema RSA

В момента RSA система е най-честата публичен ключ система за криптиране.

Способността да се направи оценка на гарантирана сигурността на алгоритъма RSA се превърна в една от причините за популярността на този сок, на фона на десетки други схеми. Следователно алгоритъма RSA се използва в компютърните мрежи банкови, особено за отдалечени клиенти (услуга на кредитна карта).

Помислете за резултатите от математически основи на този алгоритъм.

1. Теорема (Ферма Little теорема.)

Ако р - председател,

х р -1 = 1 (мод п) (1)

за всички х, просто в сравнение с п и

х р = х (мод п) ( 2)

за всяко х.

Доказателство. Достатъчно е да се докаже валидността на уравненията (1) и (2) за х р. Доказателство за това е чрез индукция.

Очевидно е, че уравнение (3) е изпълнено, тъй като х = 0 и 1. След това,

X р = (X -1 + 1) р = C (р, J ) (х 1) J = (х 1) р + 1 (Mod 2),

тъй като C (р, й) = 0 (мод р) за 0 <к <п. С оглед на това неравенство и на предложения за метода на индукцията на доказване теорема.

Определение. Euler функция φ (п) е броят на положителните числа по-малки от п и сравнително премиер п.



п
φ (п)

Теорема 2. Ако п = PQ (р и р - различни прости числа), а след това

φ (N) = (р-1), (р-1)

Теорема 3. Ако п = PQ (р и на Q - различни прости числа) и х - простата уважението към р и р, след това

х φ (п) = 1 (мод п)

Следствие. Ако п = PQ (р и р - различни прости числа) и д сравнително лесно (н), а след това на картата

Е д, п: хх д (мод п)

Това е едно към едно на Z п.

Очевидно е, че ако - сравнително проста е (п), съществува цяло число D, така че

изд ≡ 1 (МО φ (п)) (3)

Тези математически факти и основана на популярния алгоритъм RSA.

Нека N = PQ, където р и р - са различни прости числа. Ако г и д удовлетворяват уравнението, на екрана E д, н е и D, N са инверсии Z п. Както Е е N, и Е г, п е лесно изчислява, както е известно например, D, Р, Q. Ако са известни д и н, р и р а неизвестен, тогава Е д, п е еднопосочна функция; намери Ед, N за даден п е еквивалентно на разлагането на п. Ако Р и Q - просто достатъчно голям, след разширяването на п не е практично. Така се поставя основата за система RSA криптиране.

1.1 Shifrosistema RSA

В момента RSA система е най-честата публичен ключ система за криптиране.

Нека N = PQ - число се представя като продукт на две големи прости числа р, р. The номера Е и D, за определяне на криптиране и декриптиране, съответно, трябва да отговарят на условието

изд ≡ (МО φ (п) ), ( 1)

където φ (N) = (р-1), (р-1), - стойност на Euler функция на броя N. Нека к = (N, P, Q , E, D) - избраният ключ се състои от публичен ключ К1 = (N, д) и на таен ключ К2 = (N, P, Q , г). Нека M - прав текст блок, и C - съответния блок на ciphertext. След това, правилата за криптиране и декриптиране определят по формулите:

С = Е К (M) = М д (МО N), D К (C) = C г (МО N) ( 2)

Имайте предвид, че съгласно (2) D К (C) = М

При подреждането на стойностите на Г и Д, отговаря на условието (1), е стойност, обикновено се определя така, че да vzaimnoprostym с φ (N), и стойността на г се определя от уравнението

φ (N) х + Ед = 1 (3)

В общия случай, уравнение (3) е с форма на брадва + с = С (тук = φ (N), б = д, у = г) и се нарича диофантово уравнение.

Разтворът на това уравнение

Y = (-1) μ · A μ -1 · х = ( -1) μ 1 · б μ -1 ( 4)

може да бъде получен чрез разлагане на отношението А / Б в продължение фракция:

където μ - за да продължи фракция, т.е. Фракции индекс коефициент, който остатък е нула,

(5)
и за всички членове, като се започне с трети същински

(6)

По този начин, за да се реши уравнението (3), че е необходимо да се въведе отношението А / Б под формата на верижна дроб, за да се определи стойността на R 0, R 1 ... R μ и μ. След това, в съответствие с (4) - (6) определяне на стойностите на един аз, б аз, и х и у.

Тези математически факти и основана на популярния алгоритъм RSA.

Нека N = PQ, където р и р - са различни прости числа. Ако г и д удовлетворяват уравнението (8.2.3), дисплей Ее на п и Ед, п са инверсии Zn. Както Ее, N, и Ед, п е лесно изчислява, както е известно например, D, Р, Q. Ако са известни д и н, р и р а неизвестен, Ее, п е еднопосочна функция; намери Ед, N за даден п е еквивалентно на разлагането на п. Ако Р и Q - просто достатъчно голям, след разширяването на п не е практично. Така се поставя основата за система RSA криптиране.

Аз Потребителят избира един чифт обособен премиер пи и чи, и изчислява двойка числа (EI, ди), които са сравнително премиер р (NI), където пи п = чи. Контролен лист съдържа публични ключове {(EI, Ni)}.

Да приемем, че изходния текст

X = (Х0, X1, ..., Xn-1), xZn, 0 I <N,

представен за първи път в основата на Ni:

N = c0 + CI Ni + ....

Потребителят аз криптира текста, когато го изпратите на потребителския Й прилагане на п картографиране Еди, Ni:

N Еди, Ni п = п ".

Потребителят извършва декриптиране J N ', използвайки Еи, Ni:

N "Еи, Ni п '= Еи, Ni Еди, Ni п = п.

Очевидно, за да открие най-инверсия Еди, Ni към Еи, Ni, изисква познаване на факторите, п = пи Ци. Водещ време е най-добре познатите на разпадане алгоритмите за п = 10 ^ 100 към днешна дата, се простира отвъд съвременни технологични възможности.

Да разгледаме малък пример, който илюстрира използването на алгоритъма RSA.

Пример криптиране на съобщение "CAB". За простота, ние ще използваме малки номера (на практика се използват много повече).

1. Нека р = 3 и Q = 11.

2. Определяне на п = 3 * 11 = 33.

3. Намерено (р-1), (р-1) = 20. Следователно, тъй като г, е относително прости до 20, например, D = 3.

4. Изберете номер д. Като такъв номер може да се приема всеки номер, за който отговаря (е * 3) (мод 20) = 1, например 7.

5. Ние сме кодираната съобщението като последователност от числа с помощта на дисплея: А1, В2, С3. След съобщението приема формата (3,1,2). Шифроване на съобщението с помощта {7.33} ключ.

6. дешифрира криптирани съобщения (9,1,29), въз основа на частния ключ {3,33}:

По този начин, в действителните системи RSA алгоритъм се прилага както следва: Всеки потребител избира две големи прости числа, и в съответствие с алгоритъм, описани по-горе, избира две прости числа Е и г. Като резултат от умножението на първите две цифри (р и р) е настроено п.

{E, N} образува публичен ключ, и {D, N} - затворен (въпреки че можете да вземете и обратно).

Публичният ключ е публикуван и достъпен за всеки, който желае да изпрати съобщение до ключ собственик, който криптира определен алгоритъм. След криптиране, съобщението не може да бъде отворен с публичния ключ. Собственикът на частния ключ, може лесно да декриптира полученото съобщение.

Шифроване на съобщение с помощта на алгоритъм Шамир три абонатите, като стойността на M за съобщения и р-стойност от таблицата №3. По брой и (предпоследен цифра) студентът избира, за да кодира съобщението, според й - необходимо за прилагане на този алгоритъм, числото р. Избор на данни към други абонати съгласно процедурата циклично генерира (I + 1) и (G + 1). Например, последните цифри на запис-книга - (26). Изберете три абонати (съобщения, п) - (16,49), (18,51), (20,53).

Таблица №3 - сурови данни

аз
съобщение
G
р

аз
съобщение
G
р

Това шифър, предложен от Самир (Adi Shamir), е първият, който позволява да се организира обмен на секретни съобщения по открита линия за комуникация за физически лица, които нямат сигурни канали и секретни ключове и никога не могат да се виждат един друг. (Спомнете си, че системата за Diffie-Hellman може да се образува само една тайна дума, и прехвърлянето на съобщение ще изисква използването на шифър, където думата се използва като ключ.)

Ние се пристъпи към описанието на системата. Да предположим, че има два абонати А и В, свързани с линк. А иска да изпрати съобщение м до абонатната B, така че никой не знаеше за неговото съдържание. A избира произволно големи прости числа р и я предава открито Б. И след това избира две числа A и г A, така че

с A г мод (р - 1) = 1 (2,1)

Тези числа A пазят в тайна и няма да се прехвърлят. В същото Избира две тайни номера и по такъв начин, че г

г в в Министерството на отбраната (р - 1) = 1 (2.2)

След това, A предава своето послание м, с помощта на три стъпки протокол. Ако М <P (m се счита за номер), съобщението се предава незабавно т.е. ако М р, тогава съобщението се представя като М 1, м 2, ..., М Т, където всички М I <р и м след това се предава последователно 1, т 2, ..., т т. По този начин за кодиране на всеки М и е по-добре да се избере произволно нова двойка (C A, D А) и В, D B) - друго надеждността на системата намалява. В момента шифър, като обикновено се използва за пренос на номера, като секретни ключове, стойности по-малко от стр. По този начин, ние считаме, само м <р случай.

Описание протокол.

Етап 1. И изчислява броя на

х 1 = m CA modp (2.3),

където m - оригиналното съобщение и изпраща х до 1 V.

Етап 2. В получаване х 1, изчислява броя на

х 1 х 2 = CB мод р (2.4)

х 2 и предава на А.

Етап 3. И изчислява броя на

х 3 = х 2 Da мод р (2.5)

и я предава към B.

Етап 4. Получаващият х 3, изчислява броя на

х 4 = х 3 db мод р (2.6)

Движеща сила на клавиша за обмен алгоритъм Шамир е показан на фигура 2.

Фигура 2 - споделяне на схема в ключов система Шамир

Пример 2.1. Да предположим, че иска да изпрати съобщение до м = 10. избира р = 23, с A = 7 (НОД (7,22) = 1), и изчислява г A = 19. По същия начин, избира настройките в B = 5 (сравнително премиер да 22) и г B = 9. Отидете на Шамир протокол.

Стъпка 1. х = 1 на 10 юли Министерството на отбраната 23 = 14.

Стъпка 2 х 2 = 14 май мод 23 = 15.

ShagZ. 3 х 15 = 19 мод 23 = 19.

Стъпка 4 х 4 = 19 мод 23 септември = 10.

По този начин, предава съобщение, получена в т = 10.

<== Предишна лекция | На следващата лекция ==>
| Encryption алгоритъм за Шамир

; Дата: 03.01.2014; ; Прегледи: 1264; Нарушаването на авторските права? ;


Ние ценим Вашето мнение! Беше ли полезна публикуван материал? Да | не



ТЪРСЕНЕ:


Вижте също:



ailback.ru - Edu Doc (2013 - 2017) на година. Тя не е автор на материали, и дава на студентите с безплатно образование и използва! Най-новото допълнение , Al IP: 11.45.9.24
Page генерирана за: 0.062 сек.