Реферат: Длина ключа и его полный перебор - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

Длина ключа и его полный перебор

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 25 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

Длина ключа и его полный перебор Оглавление · 1. Введение o 1.1. Что такое бит ? o 1.2. Что такое криптог рафический ключ ? o 1.3. Что такое полный перебор ? o 1.4. Является ли полны й перебор единственно возможным методом крипт оанализа ? o 1.5. 128-битный ключ в два раза устойчивее к взлому , чем 64-битн ый ? o 1.6. PGP должно быть очен ь устойчив , так как использует ключи 1024 бит а . · 2. Текущее полож ение дел · 2.1. Какова максим альная длина ключа для симметричных криптосис тем , которая поддается программному взлому ме тодом полного перебора ? · 2.2. То же , с исп ользованием специальной аппаратуры ? · 2.3. А для несимметри чных криптосистем ? · 2.4. Что относительно "кофейника " Шамира ? я 3. То , что будет возможным в будущем · 3.1. Что такое закон Мура ? · 3.2. Какова предполагаема я стоимость полного перебора с ис поль зованием специализированного оборудования ? · 3.3. А с использовани ем квантовых компьютеров ? я 4. Ра зличные слухи · 4.1. NSA/DST/другие могу т ломать ключи до 128 бит . · 4.2. NSA/DST/другие обладают квантовыми компьютерами . · 4.3. NSA/DST/другие до с тигли методов криптоанализа , недоступных другим . · 4.4. Я работаю на NSA/DST/других и поэтому пытаюсь убедить обществен ность , что 128-битное шифрование надежно . 1. Введение 1.1. Что так ое бит ? Бит является фу ндаментальной единицей информации . Он может п ринимать значения 0 или 1. В течение сорока п оследних лет компьютеры работают с бинарными данными , то есть с наборами битов (а не с цифрами от 0 до 9, как это прин ято у людей ; можно сказат ь , что ком пьютеры имеют только два пальца ). Биты поз воляют кодировать целые числа , символы , и т.д .. Вся информация , проходящая через компьютер , превращается в биты . 8 бит образуют байт ; это дает 256 комбин аций и позволяет кодировать числа от 0 до 255 или символы (включая разницу между прописными и строчными буквами , символы с надстрочными знаками и другие ). 1024 байта образуют один килобайт (кБ ). 1024 используется вместо 1000 так как 1024 является сте пенью числа 2, то есть "круглым " числом , если работать по основанию 2. 1024 килобайта обра зуют мегабайт (МБ ), или 1048576 байт . 1024 мегабайта о бразуют гигабайт (ГБ ), или 1073741824 байта . 1024 ГБ обр азуют терабайт (ТБ ). Дальнейшее умножение малоу потребительно , т.к . дорогостояще со всех точек зрения . Типичная емкость жестких дисков широко распространенных в настоящее вр емя компьютеров составляет десять гигабайт . Р азвитая сеть может пропускать десять мегабайт в секунду между двумя машинами . 1.2. Что такое криптографический ключ ? Криптографические о перации , таки е как шифрование и подпис ание данных электронной цифровой подписью , мо гут быть осуществлены только определенными ли цами , располагающими некоторыми секретами . В п рошлые века этим секретом был сам способ преобразования данных . Однако более рационал ьно и бол е е эффективно концентрир овать этот секрет в виде набора битов , а сам алгоритм делать общедоступным . Действительно , сохранять в тайне алгоритм проблематично , и , кроме того , необходима ч исленная оценка его безопасности . Сам факт публикации алгоритма позволяе т "бесплатно " получить признание его надежности криптогра фическим сообществом . Ключ , таким образом , является концентрацие й секрета , этот набор битов является "эссе нцией " конфиденциальности . 1.3. Что такое полный перебор ? Взломать криптосист ему , значит су меть осуществить некоторые операции , требующие (в теории ) знания секр ета (ключа ), не имея информации о последнем . Наиболее полным взломом является взлом , в результате которого становится известен клю ч , что дает взломщику те же полномочия , что и законному в ладельцу ключа . Полный перебор является наиболее простым методом этой точки зрения : он состоит в том , чтобы пробовать все ключи один за другим до тех пор , пока не найде тся правильный . Этот метод является наиболее общим , и может быть распараллелен (вычисл е ния могут быть распределены на много машин ). Кроме того , он наиболее реалистиче н : если рассматривать случай симметричной сис темы шифрования (которая ставит в соответстви е блоку , состоящему из нескольких байтов , другой блок той же длины , но преобразованн ый к "нечитаемому " виду при помощи ключа ), достаточно перехватить пару открытый текст /зашифрованный текст , то есть блок из несколько байтов и соответствующих им зашифрованных . Например , если передается карт инка в формате JPG, то начало сообщения предс тавляет собой стандартный заголовок JPG, формат которого всем хорошо известен . С точки зрения статистики , надо перебр ать примерно половину возможных ключей , прежд е чем найдется правильный . Если длина ключ а составляет 56 битов , это означает , что в среднем необходи мо провести 2^55 итераций , что составит 36028797018963968. 1.4. Является ли полный перебор единственно возможным методом криптоанализа ? Нет . Но другие методы сильно зависят от конкретного алг оритма . Некоторые , такие как линейный или дифференциальный крипт оанализ , требуют огромн ого числа пар открытый /зашифрованный текст , представляя , таким образом , чисто теоретический интерес . Кроме того , существуют криптосистемы (в частности , системы асимметричные , называемые ещ е "системами с открытым ключом "), для которы х все сочетания битов не образуют правильного ключа . Типичный пример - RSA, где кл юч представлен большим числом , полученным из двух больших простых чисел . Совокупность наборов из 1024 бит , которые являются двоичной записью этих чисел , гораздо меньше 2^102 4 . Полный перебор абсурден в этом слу чае . 1.5. 128-битный ключ в два раза устойчивее к взлому , чем 64-битный ? НЕТ ! Это распрос траненная ошибка . Каждый дополнительный бит у дваивает количество возможных ключей и затрат ы на полный перебор . Ключ длиной 128 бит является в 18446744073709551616 раз более сложным для подбора , по сравнению с ключом длиной 64 бита (который уже не назовешь совсем легким ). 1.6. PGP должно быть очень устойчив , так как использует ключи 1024 бита. Стоп ! Давайте ра зберемся ! "1024 бит " в P GP - это ключ RSA или DSS, то есть ключ асимметричного алгоритма . Атака методом полного перебора не самый лучший вариант в этом случае . Кроме того , асимметричные алгоритмы относ ительно медленны , и "внутри " PGP использует симмет ричный алгоритм (исторически IDEA, затем CAST) размер ключа которого составляет 128 бит. 2. Текущее поло жение дел 2.1. Какова макси мальная длина ключа для симметричных криптоси стем , которая поддается программному взлому м етодом полного перебора ? Известно , что дв а ключа по 56 бит был и подобраны по лным перебором на обычных компьютерах типа PC. Специализированная машина (построенная EFF) помогла для второго ключа , выполнив приблизительно треть общего объема вычислений . Ключи были для алгоритма DES. Качественный ПК или рабочая станция м огут переб ирать с максимальной скоростью нескольких мил лионов ключей в секунду . Если принять сред нюю скорость один миллион ключей в секунд у на машину , то легко видеть , что для подбора ключа 10000 машин должны в среднем затратить 42 дня. Полный перебор ключ а длиной 64 бита для RC5 (для которого сложность полного пере бора несколько выше , чем для DES) в настоящее время продолжается , и будет длиться , по крайней мере , еще нескольких лет . Напоминаем , что подбор ключа размером 64 бита , является в 256 раз более тр у доемким , чем подбор ключа длиной 56 бит. 2.2. То же , с использованием специальной аппаратуры ? Американская группа EFF, инвестировала 250000$ в создание специализированной машины под названием "Deep crack" ("глубокий взлом "), которая в состоянии перебрать в се кл ючи алгоритма DES приблизительно за три дня . В ней использованы специализированные процессоры , которые невозможно применить для целей , отличных от взлома DES (в частности , они ниче го "не знают " о RC5). Все остальные машины того же рода - из области с лухов . DES используется уже более 20 лет , и можно предположить , что , ве роятно , машине EFF предшествовали другие прототипы , разрабатываемые секретными службами . В любом случае , скоро уже 15 лет периодически упомина ются принципы построения такой машины . 2.3. А для не симметричных криптосистем ? В принципе , суще ствуют две математические задачи , используемые в асимметричных шифрах : факторизация и диск ретное логарифмирование . RSA использует первую , DSS втор ую . Другие упоминаемые задачи (вариации двух предыдущи х , использование эллиптических кри вых , задача об укладке ранца , минимизация сети (задача коммивояжера ), обратное распознавание (permuted perceptrons problem - см . примечания ) относительно редко ис пользуются в настоящее время . Рекорд факторизации датируетс я 22-ым августа 1999: число размером 155 десятичных цифр (512 бит ) было факторизовано за шесть месяцев вычислений на парке приблизительно из 600 маш ин , некоторые из которых могут быть квалиф ицированны как "быки " (в частности Cray с 2 ГБ памяти ). Примененн ы е алгоритмы гораз до более сложны , чем полный перебор , и требуют большого количества оперативной памяти с хорошей скоростью доступа . Дискретное логарифмирование менее исследован о , на его взлом осуществлено меньше инвест иций , чем на факторизацию . Рекорд - п оря дка 95 десятичных цифр. 2.4. Что относите льно "кофейника " Шамира ? Представленный на Eurocrypt'99 в Праге (в начале мая 1999), этот аппар ат ускоряет физическими средствами исследование гладких чисел (то есть полученных произве дением только маленьких прос тых чисел ), которые получают обычно методом решета . Эт и числа являются основой нескольких алгоритмо в факторизации и решений задачи дискретного логарифмирования . Сам аппарат еще не построен , описаны только его принципы . Существуют технические проблемы для реализации прототипа (Arjen Lenstra высказал некоторые возражения , с которыми Adi Shamir с огласился ). По общему мнению , этот метод позволил бы факторизовать число приблизительно в 600 бит , со средствами , которые позволили установ ить рекорд в 465 бит (в фе врале 1999), есл и все проблемы с реализацией будут решены . Отмечено , что решето заняло приблизительно 60% времени для рекорда в 512 бит . Все же шоу было очень увлекательным . Phil Zimmerman, автор PGP, заметил , что очень доволен тем , что исследователи инте ресуются , как обстоят дела в этих проблемах , так как это увеличивает степень доверия к такого рода системам . 3. То , что б удет возможным в будущем 3.1. Что такое закон Мура ? Закон Мура (Moore) яв ляется оценкой развития вычислительной техники во времени . В базовом варианте он гласит , что для заданной стоимости (в широ ком смысле , включая энергопотребление , производств о оборудования , износ , стоимость хранения , и т.д .) вычислительная мощность увеличивается в 8 раз каждые 3 года . Говоря более точно , мо жно сказ а ть , что через каждые три года , технологические достижения позволяют разместить в 4 раза больше логических элемен тов в микросхеме заданной стоимости , одноврем енно ускоряя ее быстродействие в 2 раза . Этот закон замечательно подтверждался в течение последних 15 лет . Следует отметит ь , что центральные микропроцессоры компьютеров общего назначения не полностью следуют это му закону , потому что они не могут так же быстро увеличить размер шины данных (по соображениям обратной совместимости кода , а также потому , чт о вычисления , которые эти процессоры обычно производят , и меют дополнительные ограничения , делающие бесполе зным использование слишком больших регистров ). Это касается , таким образом , систем , оп исываемых в терминах логических элементов , сп ециализированных на конкретном алгоритме . Та ким образом , это по сути ASIC (Application Specific Integrated Circuit - специали зированные микросхемы ) и FPGA (Field Programmable Gate Arrays - программируемые логические интегральные схемы ); то есть пере программируемые цепи , вып о лняющие те же задачи , что и ASIC, но вдвое более дорогие при заданной мощности , однако являющи еся многоцелевыми ). 3.2. Какова предп олагаемая стоимость полного перебора с исполь зованием специализированного оборудования ? Если закон Мура будет продолжать вып олняться (и не имеется веских оснований для обратного , так как он учитывает качественные достижения , а не только увеличение точности обработки кремния ), можно достичь машины EFF (четверть миллиона долларов , для 56 бит за 3 дня ) и добавлять 3 бита каждые 3 года (3 бита = 2^3 = 8; что дает в 8 раз больше возможных вар иантов ключей ). Заметим , что для сохранения закон Мура , качественные достижения должны происходить достаточно быстро , так как имеются пределы в увеличении плотности элементов на криста лле кремни я (замедление вследствие туннел ьного эффекта ). В ряде разрабатываемых методов предполагается осуществить замену кремния на арсенид галлия , что позволит достичь боле е высокой плотности элементов , замену алюмини я медью , которая позволяет работать гораздо бо л ее быстро , построение оптической логики (оптический элемент переключается при близительно в 100 раз быстрее электронного , но его стоимость выше более чем в 100 раз ). Таким образом , можно считать , подобрать полным перебором 128-битный ключ так же "л егко ", к ак сейчас 56-битный , станет возмо жным через 72 года . Эта оценка является "наил учшей ", в то время как многие исследовател и этой тематики полагают , что закон Мура будет выполняться в лучшем случае еще несколько лет (действительно , все качественные изменения, привнесенные за последних 15 л ет , были просто нереализованными , известными с 1975 года , и их запас почти исчерпан в настоящее время ). 3.3. А с испо льзованием квантовых компьютеров ? Квантовые компьютер ы , реализуемые через суперпозицию состояний о дной част ицы , являются более мощной вы числительной моделью , чем машина Тьюринга и позволяют осуществить многие операции (среди которых полный перебор ключей такого "безгр аничного " алгоритма , как DES) за субэкспоненциальное время . Квантовые компьютеры очень соблазн ите льны , но они не существуют . Был построен двухбитовый квантовый регистр , но имеются д остаточно мощные препятствия для построения м ашины , способной сломать DES (главным образом , ини циализация этого монстра , которая не может быть распараллелена , и занимае т , т аким образом , 2^n операций для ключа n битов ). Это не имеет большого значения для другого типа квантовой криптографии , который служит для "неперехватываемой " передачи данных по оптоволокну (используя принцип неопределе нности Гейзенберга ). 4. Различны е слухи 4.1. NSA/DST/другие мог ут ломать ключи до 128 бит. Имеются очень с ильные возражения против такого рода высказыв аний . Среди классических можно выделить одно , предполагающее наличие процессора с энергоп отреблением в 10 раз меньше , чем у классичес ких (таким могли бы располагать секрет ные службы , имеющие преимущество ). Энергетические затраты на полный перебор 128-битного ключа , если их перевести в тепловую форму , з аставили бы исчезнуть под водой Нидерланды в результате таяния полярных льдов . Что касает ся 256-битных ключей , то если предположить , что затраты на анализ одного ключа равны энергии перехода электр она с одной орбиты атома на другую , то количества великодушно предоставляемой Солнцем энергии недостаточно для осуществления таког о перебора за раз у мное время . Некоторые легко манипулируют количеством битов , легко относя 20 бит на использование сверхпроводников или оптических элементов , 20 други х на применение суперэффективных алгоритмов , и 30 последних потому что "это уже немного " (да , просто помнож им на 1 миллиард , эт о действительно "немного "). Напомню , что число битов экспоненциально . Это означает , что затраты на перебор каждых n битов пропорциональны 2^n. Чтобы это было легче представить , напомним , что : · 64 бита : 18446744073709551616 возможных ключей · 128 бит : 340282366920938463463374607431768211456 возмож ных ключей · 256 бит : 115792089237316195423570985008687907853269984665640564039457584007913129639936 возможных ключей 4.2. NSA/DST/другие обл адают квантовыми компьютерами. Очень маловероятн о . Если это правда , то технологические достижения опережают всех как минимум ле т на 10. Другими словами , они располагали бы тогда такой продвинутой технологией , что сама идея дальнейшей борьбы была бы абсур дом . Некоторые упоминают возможность получения вн еземной технологии , либо через Людей в Черном , либо непосредственно через Phil Zimmerman, их посла на этой планете . Как считают другие источники , квантовым компьютером располага ла цивилизация Атлантов (конечно , Атлантида бы ла затоплена именно в результате п еребора ключа "классическими " методами , см . выше ). Сталкиваясь с проявлениями абсурда и дилетантства в этой области , хочется посовето вать держаться подальше от подобного рода спекуляций , чтобы не выглядеть клоуном . Если хочется оценить что в состоянии сд елать NSA, надо дать ему 3 года времени в соответствии с законом Мура и хороши й бюджет . Это позволит сделать задачу с 64 битами решаемой . 80 бит останутся недостижимыми . 4.3. NSA/DST/другие дос тигли методов криптоанализа , недоступных другим. NSA (в лице D on Coppersmith) объявил в 1987 году , что знали уже в 1977 о дифференциальном криптоанализе , обнарод ованном Бихамом и Шамиром (E. Biham, A. Shamir) именно в этом 1987 году . Алгоритм DES, разработанный в 1977, специ ально защищен от такой атаки. Тем не менее, уточним , что такая атака требует огромного количества пар о ткрытый /зашифрованный текст , и , в любом сл учае , нереальна . Кроме того , DES не был защище н против линейного криптоанализа , открытого в 1993 Matsui, что ограничивает научное превосходство NSA 15 го д ами . Наконец , этот последний сп особ криптоанализа также нереален , т.к . требует 64 ТБ известного открытого текста , что в несколько десятков миллионов раз превышает объем Библии . Подобные слухи ходили также про факто ризацию , дискретное логарифмирование и ср едства от прыщей . Легко можно встретить та кие слухи в упоминаниях о международных з аговорах злодеев , которые хотят знать все обо всех в этом мире . В любом случае , с определенного момент а , гораздо дешевле установить видеокамеру в вашем офисе , чем заставлят ь "молотить " квантовый компьютер . Знаете ли Вы , что в осстановление изображения Вашего монитора возмож но с дистанции 100 метров ? То же самое ка сается и сигналов клавиатуры , когда Вы печ атаете . Необходимо иметь хорошо спроектированную сетку Фарадея , чтобы з а щищаться от этого . Шифрование позволяет установить защищенный канал между двумя точками , но не защищает сами точки . 4.4. Я работаю на NSA/DST/других и поэтому пытаюсь убедить общественность , что 128-битное шифрование надежно. Niark niark niark. Я обманщик , не так ли ? © Автор : Thomas Pornin (thomas.pornin@ens.fr); оригинал : http://www.dmi.ens.fr/~pornin/faq-cle.html ©Владислав Мяснянкин , перевод на русский язык. Примечания перевод чика. 1. Пожалуйста , не присылайте мне замеча ния /комментарии по содержанию документа . Я только перевел его . Пишите непосредственн о автору (на французском или английском яз ыке ) - адрес в заголовке . 2. EFF - Electronic Frontier Foundation http://www.eff.org/ 3. NSA - National Security Agency http://www.nsa.gov/ 4. DST - Directio n de la S й curit й du Territoire http://www.chez.com/icebreaker/dst/ 5. Я не нашел русского термина для "Permuted Perceptrons Problem" и перевел к ак "задача обратного распознавания ". Если есть более правильный перевод - буду рад услыш ать . Что это такое можн о посмотреть например на http://cgi.dmi.ens.fr/cgi-bin/pointche/papers.html?Po95a (на английском ). 6. Если вы найдете нето чности в употреблении терминов или предложите более "благозвучный " вариант их перевода , это будет воспринято с благодарностью . Неконс труктивная критика и флейм пойдут на /dev/null.
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
В ремейке "Броненосец Потемкин" матросы взбунтовались из-за отсутствия в меню пармезана и фуагры.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по программированию "Длина ключа и его полный перебор", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru