Современные писав криптографічні методы

року міністерство освіти Російської Федерации.

САМАРСЬКИЙ ДЕРЖАВНИЙ ТЕХНИЧЕСКИЙ.

УНИВЕРСИТЕТ.

Кафедра прикладної математики информатики.

До У Р З Про У, А Я Р, А Б Про Т А.

Сучасні писав криптографічні методы.

Студент IV-ИЭ-8 Альперт У. В.

Науковий керівник Пономарьов У. П.

З, а м, а р а.

З Про Д Є Р Ж, А М І Е.

Стр.

Введення у криптографію 3.

Симетричні криптосистемы 5.

Стандарт шифрування даних ГОСТ 28 147–89 6.

Міжнародний алгоритм шифрування даних IDEA 10.

Алгоритм RSA 12.

Оцінка надійності криптосистем 14.

ВИСНОВОК 19.

ЛІТЕРАТУРА 20.

Введення у криптографию.

Бурхливий розвиток писав криптографічні системи отримали роки першою і другий світових війн. Починаючи з повоєнного часу й по сьогодення, поява обчислювальних коштів прискорило розробку й вдосконалення криптографічних методов.

Проблема використання криптографічних методів у інформаційних системах стала зараз особливо актуальна що з однієї боку, розширилося використання комп’ютерних мереж, зокрема глобальної Інтернету, якими передаються більше об'ємів інформації державного, військового, комерційного та приватного характеру, не допускає можливість доступу до неї сторонніх лиц.

З іншого боку, поява нових потужних комп’ютерів, технологій мережевих і нейронних обчислень прискорило дискредитацію криптографічних систем не так давно вважалися мало раскрываемыми.

Проблемою захисту шляхом її перетворення займається криптология (kryptos — таємний, logos — наука). Криптология поділяється на два напрями — криптографію і криптоанализ. Цілі цих напрямів прямо противоположны.

Криптографія займається пошуком і дослідженням математичних методів перетворення информации.

Сфера інтересів криптоанализа — дослідження можливості расшифровывания інформації не повідомляючи ключей.

Шифрування — преосвітній процес: вихідний текст, що має також назва відкритого тексту, замінюється шифрованим текстом.

Дешифрування — зворотний шифруванню процес. За підсумками ключа шифрований текст перетворюється на исходный.

Ключ — інформація, необхідна для безперешкодного шифрування і дешифрування текстов.

Криптосистемы поділяються на симетричні і системи з відкритою ключем. У симетричних криптосистемах й у шифрування, й у дешифрування використовується і той ж ключ.

У системах з відкритою ключем використовуються два ключа — відкритий і закритий, які математично пов’язані один з одним. Інформація шифрується з допомогою відкритого ключа, що доступний всім бажаючим, а розшифровується з допомогою закритого ключа, відомого лише одержувачу сообщения.

Електронної (цифровий) підписом називається присоединяемое до тексту його криптографічне перетворення, що дозволяє і при отриманні тексту іншим користувачем перевірити авторство та істинність сообщения.

Криптостойкостью називається характеристика шифру, що його стійкість до дешифрованию не повідомляючи ключа (тобто. криптоанализу). Є кілька показників криптостойкости, серед яких: кількість всіх можливих ключів; середнє час, необхідне криптоанализа.

Криптографія у минулому використовувалася лише військових цілях. Проте зараз, з становленням інформаційного суспільства, вона стає центральним інструментом задля забезпечення конфіденційності. Принаймні освіти інформаційного суспільства, великих держав стають доступні технологічні кошти тотального нагляду над мільйонами людей. Тому криптографія стає однією з основних інструментів які забезпечують конфіденційність, довіру, авторизацію, електронні платежі, корпоративну безпека продукції та незліченну кількість інших важливих вещей.

Симетричні криптосистемы.

Усі розмаїття існуючих криптографічних методів можна зводити до наступним класам преобразований:

Моноі полиалфавитные подстановки.

Найпростіший вид перетворень, що полягає в заміні символів вихідного тексту інші (тієї самої алфавіту) за більш менш складного правилу. Задля більшої високої криптостойкости потрібно використання великих ключей.

Перестановки.

Також нескладний метод криптографічного перетворення. Використовується, зазвичай, разом із іншими методами.

Гаммирование.

Цей метод залежить від накладення на вихідний текст деякою псевдослучайной послідовності, генерованою з урахуванням ключа.

Блочні шифры.

Представляють собою послідовність (із можливим повторенням і чергуванням) основних методів перетворення, застосовується до блоку (частини) шифруемого тексту. Блочні шифри практично зустрічаються частіше, ніж «чисті» перетворення тієї чи іншої класу з їх понад високої криптостойкости. Російський і американський стандарти шифрування засновані на цьому класі шифров.

Стандарт шифрування даних ГОСТ 28 147–89.

Російський стандарт шифрування є блоковим, т. е. перетворення ведеться за блокам. Він містить у собі режим заміни і двоє режиму гаммирования. Стандарт ГОСТ 28 147–89 формувався з урахуванням світового досвіду, і зокрема, було прийнято до уваги вади суспільства і нереалізовані можливості алгоритму DES, тому використання стандарту ГОСТ краще. Ефективність даного стандарту досить висока. Системи, засновані на ГОСТ 28 147–89, дозволяють зашифрувати в секунду до кілька десятків Кбайт даних. До нього закладено метод, з допомогою якого можна зафіксувати необнаруженную випадкову чи навмисну модифікацію зашифрованої информации.

Введемо асоціативну операцію конкатенації. Якщо L і R — послідовність біт, то LR позначає конкатенацію послідовностей, тобто LR — послідовність біт з размерностью рівної сумі розмірностей L і R, причому біти R йдуть за бітами L. З іншого боку, будемо використовувати такі операції складання: A^B — побітове складання по модулю 2; якщо A+B=>2, то A^B=А+B-2 якщо A+B232, то A[+]B=A+B-232 якщо A+B232−1, то A{+}B=A+B-232+1 якщо A+B2, то A^B=А+B-2 якщо A+B d2 p3 (+) s3 —> d3 p4 (*) s4 —> d4 d1 ^ d3 —> d5 d2 ^ d4 —> d6 d5 (*) s5 —> d7 d6 (+) d7 —> d8 d8 (*) s6 —> d9 d7 (+) d9 —> d10 d1 ^ d9 —> d11 d3 ^ d9 —> d12 d2 ^ d10 —> d13 d4 ^ d10 —> d14 p1, p2, p3, p4 — чотири 16 бітних блоку, куди розбиваються один блок вихідного тексту s1, s2, s3, s4, s5, s6 — шість 16 бітних подключей.

На наступному кроці як p1, p2, p3, p4 використовують d11, d13, d12, d14 й побудувати нові шість подключей. Отримані чотири останні 16 бітних блоки і є зашифрований текст. Процес дешифрування здійснюється аналогично.

Шифрування і дешифрування відрізняються лише подключами. Перші вісім подключей визначаються з допомогою 128 бітного ключа, який поділяється на вісім частин. Нові вісім подключей визначаються так: початковий ключ зміщується на 25 біт, і поділяється на вісім частей.

Підключи для дешифрування визначаються таблицей:

1 крок s49* s50# s51# s52* s47 s48.

2 крок s43* s45# s44# s46* s41 s42.

3 крок s37* s39# s38# s39* s35 s36.

4 крок s31* s33# s32# s34* s29 s30.

5 крок s25* s27# s26# s28* s23 s24.

6 крок s19* s21# s20# s22* s17 s18.

7 крок s13* s15# s14# s16* s11 s12.

8 крок s7* s9# s8# s10* s5 s6.

Останнє перетворення s1* s2# s3# s4*.

sXX* = мультипликативная інверсія sXX по модулю 216+1 sXX# = аддитивная інверсія sXX по модулю 216.

Алгоритм RSA.

Хоч би як були складні, і надійні писав криптографічні системи — їх слабке місце при практичної реалізації - проблема розподілу ключів. А щоб було може бути обмін конфіденційної інформацією між двома суб'єктами ІВ, ключ може бути сгенерирован них, та був, в конфіденційному порядку, переданий іншому. Тобто. у випадку передачі ключа знов-таки потрібно використання якийсь криптосистемы.

Аби вирішити цієї проблеми з урахуванням результатів, отриманих класичну і сучасну алгеброю, було запропоновано системи з відкритою ключом.

Суть їх у тому, що кожним адресатом ІВ генеруються два ключа, пов’язані між собою за певним правилу. Один ключ оголошується відкритим, а інший закритим. Відкритий ключ публікується і доступний кожному, хто хоче послати повідомлення адресата. Таємний ключ зберігається у тайне.

Вихідний текст шифрується відкритим ключем адресата і передається йому. Зашифрований текст у принципі може бути розшифровано тим самим відкритим ключем. Дешифрування повідомлення можливе лише використанням закритого ключа, що лише самому адресату.

Асиметричні писав криптографічні системи використовують звані необоротні чи односторонні функції, які мають наступним властивістю: при заданому значенні x щодо просто обчислити значення f (x), та якщо y=f (x), то немає простого шляхи до обчислення значення x.

Алгоритми шифрування з відкритою ключем отримали широке поширення сучасних інформаційних системах. Так, алгоритм RSA став світовим стандартом де-факто для відкритих систем.

Алгоритми криптосистем з відкритою ключем можна залучити до 3 назначениях.

1. Як самостійні засоби захисту переданих і збережених данных.

2. Як кошти на розподілу ключей.

3. Кошти аутентифікації пользователей.

Алгоритми криптосистем з відкритою ключем більш трудомісткі, ніж традиційні криптосистемы, тому використання їх як самостійних засобів захисту нерационально.

Тому на згадуваній практиці раціонально з допомогою криптосистем з відкритою ключем розподіляти ключі, обсяг яких інформації незначний. А потім і з допомогою звичайних алгоритмів здійснювати обмін великими інформаційними потоками.

Попри досить велику число різних криптосистем з відкритою ключем, найпопулярніша — криптосистема RSA, розроблена в 1977 року і названа на честь творців: Ривеста, Шаміра і Эйдельмана.

Ривест, Шамир і Эйдельман скористалися тим, що перебування великих простих чисел в обчислювальному відношенні здійснюється легко, але розкладання на множники твори дві такі чисел практично невиконуваним. Доведено (теорема Рабина), розкриття шифру RSA еквівалентно такому розкладанню. Тож будь-який довжини ключа можна надати нижню оцінку числа операцій на розкриття шифру, і з урахуванням продуктивності сучасних комп’ютерів оцінити й необхідне цього время.

Нехай n=p*q, де p і q — різні прості числа, і e і d задовольняють рівнянню e*d (mod (p-1)*(q-1))= 1.

Якщо p і q — досить великі прості числа, то розкладання n мало можна здійснити. І це закладено у основу системи шифрування RSA.

{e, n} утворює відкритий ключ, а {d, n} - закритий (можна взяти й наоборот).

Відкритий ключ публікується і доступний кожному, хто хоче послати власнику ключа повідомлення, яке зашифровується зазначеним алгоритмом. Після шифрування, повідомлення неможливо розкрити з допомогою відкритого ключа. Власник ж закритого ключа легко може розшифрувати прийняте сообщение.

Шифрування здійснюється за формулі: Sшифр = Se mod N.

Шифрування здійснюється за формулі: P. S = Sdшифр mod N.

Де P. S — вихідний текст, Sшифр — перетворений текст, у своїй P. S < N.

Оцінка надійності криптосистем.

Група відомих специалистов-криптографов, створена під егідою Альянсу виробників програмного забезпечення бізнесу (промислової організації, котра перешкоджає незаконному використанню програмного забезпечення), доходить висновку, що необхідна довжина ключа на цей час мусить бути щонайменше 75 бітов з подальшим збільшенням протягом наступних 20 років до 90 бітов. Перевіримо дане утверждение.

Проблема пошуку ключів симетричній криптосистемы шляхом перебору всіх можливих ключів належить до класу завдань, припускають розпаралелювання. Застосування розподілених обчислень в організацію перебору таких ключів дозволяє ефективно вирішувати трудомісткі завдання у цій галузі. Экспоненциальная динаміка зростання дитячих з часом продуктивності обчислювальних систем (10 разів на 5 років) надає ще більше істотне впливом геть зростання продуктивності системи загалом. Отже, прогрес у цій галузі може бути з допомогою: 1) використання досягнень науково-технічного прогресу застосування технологічних новинок збільшення продуктивності окремого устройства;

2) збільшення кількості таких пристроїв в системе.

З фізичної погляду той тип транзистора, що є основою сучасної інтегральної схеми, то, можливо зменшений приблизно в 10 раз, до розміру 0,03 км. Поза межами цієї межею процес включения/выключения мікроскопічних перемикачів стане практично неможливим. Таким чином максимальне швидкодія становитиме — 1016 операций/секунду, а межа зростання настане приблизно 2030 г.

Інших способів підвищення обчислювальної потужності немає. Отже, з погляду захисту криптографічними методами, аналіз потенційні можливості методу розподілених обчислень представляє як криптоаналитиков, так розробників криптографічних систем значний інтерес. Спробуємо, тому, проаналізувати граничні значення двох зазначених тенденций.

Із списку, появи влітку 1999 року, слід, що у швидкодії суперкомп’ютери розподілилися так: з потужністю порядку 1012 FLOPS 3 прим.; з потужністю порядку 1011 FLOPS 54 прим.; з потужністю порядку 1010 FLOPS 428 прим.; з потужністю порядку 109 FLOPS 251 экз.

Десять найпотужніших суперкомп’ютерів у світі з стану в липні 1999 р. |Рейтин|Наименование |Страна-обладат|Фирма-произво|Количество|Мощность| |р |машини |ялина |дитель |процессоро|(GFLOPS)| | | | | |в | | |1 |Intel ASCI Red |США |Intel (США) |9125 |1333 | |2 |Hitachi/Tsukuba|Япония |Hitachi/Tsuku|2048 |368 | | | | |ba (Японія) | | | | |CP-PACS | | | | | |3 |SGI/Cray T3E |Великобритания|Cray (США) |696 |265 | |4 |Fujitsu |Японія |Fujitsu |167 |230 | | |Numerical Wind | |(Японія) | | | | |Tunnel | | | | | |5 |Hitachi SR2201 |Японія |Hitachi |1024 |220 | | | | |(Японія) | | | |6 |SGI/Cray T3E |Німеччина |Cray (США) |512 |176 | |7 |SGI/Cray T3E |США |Cray (США) |512 |176 | |8 |SGI/Cray T3E |Німеччина |Cray (США) |512 |176 | |9 |SGI/Cray T3E |США |Cray (США) |512 |176 | |10 |SGI/Cray T3E |США |Cray (США) |512 |176 |.

На першому місці у світі за кількості суперкомп’ютерів займають США 254 (51%). Їх йдуть Японія 87 (17,5%), Німеччина 45 (9%), Великобританія 24 (4,8%), Франція 18 (3,6%), Корея 8 (1,6%), Канада 7 (1,4%), Швеція, Швейцарія і Норвегія по 6 (1,2%). Росію згадано у списку лише одне раз: на 156-ом місці комп’ютер HPC Ultra 10 000 (пікова продуктивність 16 600 MFLOPS), вироблений фірмою SUN і встановлений у Національному Резервному Банку Росії. Цікава деталь: США відсутні комп’ютери іноземного виробництва американці працюють лише з вітчизняних машинах і при цьому постачають ними весь іншої мир.

Кількість установок суперкомп’ютерів зростає рік у рік в геометричній прогресії, причому основного обсягу знов-таки посідає США. Статистика за літами склалася следующая:

1999 786 установок.

1998 638 установок.

1997 207 установок.

1996 168 установок.

1995 52 установки.

1994 45 установок.

1993 16 установок.

1992 10 установок.

Припустимо, що аналізовані нами алгоритми шифрування ідеальні, то є оптимальним методом їх зламування буде прямий перебір всіх можливих ключів даного алгоритму. Вочевидь, у цьому разі стійкість криптосистем визначатиметься довжиною ключа. Під час проведення даного дослідження передбачалося, що криптоаналитик противника має всієї інформацією щодо алгоритму шифрування, крім даних про секретному ключі, і його доступний аналізу шифрований текст повідомлення. По визначенню передбачається, що ідеальний алгоритм позбавлений будь-яких недоліків, знижують його криптостойкость. Для шифрів ГОСТ-28 147−89 і IDEA суттєвих недоліків нині не выявленно.

Припустимо також, що генерація ключа комп’ютером відбувається поза один такт його роботи, а операція дешифрування миттєво. Визначивши ставлення кількості ключів до швидкодії найпотужнішого комп’ютера, ми матимемо нижню оцінку складності дешифрування повідомлення для ідеального алгоритма.

Час, необхідне зараз найпотужнішим суперкомпьютерам до повного перебору ключів |Найменування |Мощность|56 біт |64 |70 біт |75 біт |128 бит|256 біт| |машини |(FLOPS) |7.2*Е16|бита |1.18*Е2|3.78*Е2| | | | | | |1.8*E1|1 |2 |3.4*E38|1.15*Е7| | | | |9 | | | |7 | |Intel ASCI Red|1.333*Е1|14 |5 мес.|28 років |899 |8.09*Е1|2.72*Е5| | |2 |годин | | |року |8 |7 | |Hitachi/Tsukub|3.68*Е11|52 часа|18 |102 |3257 |2.93*Е1|9.9*Е57| |a CP-PACS | | |міс. |року |років |9 | | |SGI/Cray T3E |2.65*Е11|69 |51 |141 |4523 |4.07*Е1|1.37*Е5| | | |годин |міс. |року |року |9 |8 | |Fujitsu |2.3*Е11 |171 час|60 |162 |5211 |4.69*Е1|1.58*Е5| |Numerical Wind| | |міс. |року |року |9 |8 | |Tunnel | | | | | | | | |Hitachi SR2201|2.2*Е11 |178 |61 |170 лет|5448 |4.9*Е19|1.66*Е5| | | |годин |міс. | |років | |8 |.

Отже з допомогою зазначеної робочої моделі можна розцінювати надійність проектованих і експлуатованих систем шифрування. Алгоритм ГОСТ 28 147–89 використовує таблицю підстановок розміром 512 біт. Загальна кількість можливих таблиць становить 1.33*Е36 і повний час перебору становить 3.162*Е16 років. Для алгоритму IDEA довжина ключа становить 128 біт і повний час перебору становить 8.09*Е18 років. Навіть якщо взяти буде використано суперкомп’ютер що з тисяч процесорів з максимально можливої швидкістю 1016 операций/секунду для розшифровки Держстандарту знадобиться 4.21*Е7 років, а IDEA — 1.08*Е10 років. Вочевидь, що навіть застосування кількох сотень суперкомп’ютерів Intel ASCI Red, вартістю по 55 мільйонів кожен, над стоянні кардинально поліпшити ситуацію. алгоритм RSA.

Оцінки трудомісткості розкладання простих чисел (1994 рік) |N |Кількість операций|Длина |Примітки | |E50 |1.4*1010 |166 біт |Розкриваємо на суперкомп’ютерах | |E100 |2.3*1015 |332 біт |На межі сучасних технологій | |E200 |1.2*1023 |664 біт |За межами сучасних технологій | |E300 |2.7*1034 |996 біт |Потребує суттєвих змін у | | | | |технології | |E500 |1.3*1051 |1660 бит|Не розкриваємо |.

Оцінки трудомісткості розкладання простих чисел (2000 рік) |N |Кількість операций|Длина |Максимальне час дешифрування | | | | |на суперкомп’ютері Intel ASCI | | | | |Red | |E50 |1.4*1010 |166 біт |0.01 сек. | |E100 |2.3*1015 |332 біт |29 сек. | |E200 |1.2*1023 |664 біт |2854 року | |E300 |2.7*1034 |996 біт |6.425*Е14 років | |E500 |1.3*1051 |1660 бит|3.092*Е31 років |.

Наприкінці 1995 року не пощастило практично реалізувати розкриття шифру RSA для 500-значного ключа. І тому з допомогою Інтернету було задіяно 1600 комп’ютерів. Самі автори RSA рекомендують використовувати такі розміри модуля N: 512 біт — приватних осіб; 1024 біт — для комерційної інформації; 2048 біт — для особливо таємної інформації. Досить важливий аспект реалізації RSA — обчислювальний. Адже доводиться використовувати апарат довгою арифметики. Якщо використовується ключ довжиною k біт, то тут для операцій із відкритого ключу потрібно О (k2) операцій, по закритому ключу — О (k3) операцій, а генерації нових ключів потрібно О (k4) операцій. У зв’язку з розвитком обчислювальної техніки оцінки, дані Шроппелем, застаріли, так шифр RSA довжиною 100 знаків дешифровывается в протягом кількох секунд на суперкомп’ютері Intel ASCI Red. На відміну від симетричних криптосистем, надійність яких зі збільшенням довжина ключа зростає експоненціально, для методу RSA надійність зростає лише логарифмически. Перетворення інформації з методу RSA здійснюється значно повільніше. Нещодавно розроблений новим типом атак, заснований на послідовному вимірі часів, витрачених виконання операції спорудження до рівня по модулю цілого числа. До неї схильні по крайнього заходу такі шифри: RSA, Диффи-Хеллман (обчислення дискретного логарифма) і метод еліптичних кривих. Також RSA піддається атаці з заданим текстом (Для відомого тексту, зашифрованого відомим відкритим ключем, підбираються закриті ключи).

Отже метод RSA найближчим часом перестане вживатись і буде замінений надійнішими криптосистемами.

Припустимо, що розмір процесора дорівнює розміру атома. Тоді, у наших позначеннях швидкодія гіпотетичного процесора виявиться формулою F = Vc/Ra = 3 * 1018 операцій на секунду, де Vc = 3 * 10 8 м/с швидкість світла у вакуумі, а Ra = 10−10 м — розміри атомів. Стільки разів на 1 секунду світло пройде розміри атома. Оскільки період обертання Землі навколо Сонця становить 365,2564 діб чи 31 558 153 секунд, то «за рік такий процесор виконає 94 674 459 * 1018 (1026 операций.

Цьому процесору знадобиться 1.15*Е51 років на перебору 256 бітного ключа. Більше швидкий процесор з нашого всесвіту неможливий у принципі, тому швидше виробляти дешифрування методом тотального перебору ключів принципово неможливо. Отже, прогноз майбутнього силовий атаки з урахуванням розподілених обчислень невтішний. Cиловая атака й на криптосистемы безперспективна. Проте, недоліки алгоритмів можуть істотно скоротити кількість варіантів перебору. Використання як ключів осмислених слів дозволяє застосовувати атаку по словника. Отже, в подальше розвиток криптографії відбуватиметься в області криптоанализа.

ЗАКЛЮЧЕНИЕ

.

Хотілося б відзначити, що шифрування і дешифрування затребувані в суспільстві не власними силами, а тільки тому, що можуть принести прибуток або дозволяють уникнути збитків, тому треба знати яка ж вартість одного знака шифрованою і дешифрованной інформації та у що це обходиться? Чи є рентабельними ті організації, займаються перехопленням і дешифруванням інформації, або їх явно збиткові? Найбільш цікавий з порівняльного аналізу даних із метою на наукове обґрунтування частки витрат за захист інформації. У цьому також потрібен враховувати, що дуже багато атак здійснюється зсередини співробітниками установ, від яких захиститься набагато складніше. Зокрема, проблема зберігання ключів в час найгострішою і, коли використання відкритих ключів дозволяє покінчити з проблемою розподілу ключів і аутентифікації користувачів, то ефективнішого способу зберігання ключів, ніж запам’ятовування, не знайдено, а використання пам’ятних паролів дозволяє застосувати атаку по словника. З іншого боку, використання надійних криптографічних методів не гарантує захисту від програмних атак. Отже, під час створення комп’ютерних криптосистем необхідно забезпечити безпеку лише на рівні ОС, що складнішою завданням, ніж створення самої криптосистемы.

1. Баричев З. Криптографія без секретів. М., 1998 2. Брассар Дж. Сучасна криптология. 1988 3. Жельников У. Криптографія від папірусу до комп’ютера. М., 1996 4. Йолнен Тату. Введення ЄІАС у криптографію. 1999 5. Спесивцев А. У. Захист інформацією персональних ЕОМ. М., 1992 6. Шнайер Брюс. Прикладна криптографія. 1994.

———————————;

Криптографічна система.

вихідний текст.

шифрований текст.

КЛЮЧ.

шифрований текст.

вихідний текст.

Криптографічна система.

КЛЮЧ.

Гаммирование.

Подстановки.

Симетричні криптосистемы.

Блочні шифры.

Перестановки.

Адресат.

Отправитель.

Система з відкритою ключом.

Система з відкритою ключом.

Шифрований текст.

вихідний текст.

вихідний текст.

Відкритий ключ.

Закритий ключ.