Регистрация
Центра прикладных криптографических исследований (CACR) университета Ватерлоо, являющимся совместным проектом университета, федерального правительства Канады и ряда других организаций и коммерческих корпораций © Douglas R. Stinson
Перевод © 2009 unknown
Полемика по поводу понятий криптографической безопасности
Дуглас Стинсон. Академия компьютерных наук университета Ватерлоо. Онтарио, Канада.
19 июля 2004 года
1. Введение
2. Что такое доказуемая безопасность?
Вычислительная безопасность (стойкость). Это мера определения вычислительных ресурсов, необходимых для взлома криптосистемы. Мы может определить систему как вычислительно стойкую, если лучший алгоритм взлома требует N операций, где N — некоторое определённое, очень большое число. Проблема в том, что никакая практическая криптосистема не может быть доказуемо стойкой согласно этому определению. На практике, люди часто изучают вычислительную стойкость криптосистемы по отношению к определённым видам атак. Например, имеет смысл следующее утверждение — AES безопасен против атаки простого перебора (взлома грубой силой) в настоящее время и в обозримом будущем. Разумеется, безопасность против одного определённого типа атак не гарантирует безопасности против какого-нибудь другого вида атак.
Доказуемая безопасность (стойкость). Другим способом предоставить доказательство стойкости является редуцирование безопасности криптосистемы к какой-нибудь положенной в её основу хорошо изученной математической проблеме, которая считается трудноразрешимой. Например, легко доказать утверждение типа "Криптосистема Рабина безопасна (по отношению к дешифрованию шифртекста) если модуль n не может быть факторизован". Криптосистемы такого типа часто называются доказуемо безопасными, но должно быть ясно, что такой подход обеспечивает только доказательство безопасности по отношению к другой проблеме, что не является абсолютным докзательством безопасности. Для вышеупомянутого примера нет никакого доказательства, что сама факторизация сложна, поэтому мы не можем давать заключение по поводу сложности криптосистемы. Фактически все результаты доказательств безопасности включают редукцию (в значении алгоритмов теории комплексности), так что иногда используется альтернативный термин редукционистская безопасность.
Безусловная безопасность (стойкость). Эта мера стойкости криптосистем используется, когда считают, что противник не ограничен в вычислительных ресурсах. Криптосистема считается безусловно стойкой даже с привлечением бесконечных вычислительных ресурсов. Например, хорошо известно, что одноразовый блокнот безусловно стойкий (то есть изучение отдельного шифртекста не даёт никакой информации о соответствующем открытом тексте). Доказательства безусловной стойкости не включает вычислительной сложности, а скорее зависит от комбинаторного и информационно-теоретического анализа. Точная формулировка безусловной стойкости обычно включает вычисление вероятности того, что противник способен достичь определённой цели.
Редуцирование криптографических алгоритмов до математических примитивов. Это значит, что криптографический алгоритм доказуемо безопасен, если лежащая в его основе вычислительная проблема труднорешаема. Например, криптосистема Рабина безопасна, если факторизация трудноосуществима.
Улучшение безопасности криптографических алгоритмов. Это отсылает нас к ситуации, когда мы доказываем, что "улучшенный" криптографический алгоритм предоставляет определённый (более высокий) уровень безопасности, по сравнению с "базовым" алгоритмом, предоставляющим определённый (более низкий) уровень безопасности. Например, OAEP стоек по отношению к атакам с подобранным шифртекстом, если базовый алгоритм RSA является односторонней функцией.
Редуцирование криптографических протоколов к алгоритмам более низкого уровня. Это значит, что криптографический протокол (например схема согласования ключей) доказуемо безопасен, если подразумевается, что криптографические алгоритмы, используемые в протоколе, безопасны. Например, определённые версии схемы согласования ключей "Станция-Станция" безопасны, если схема подписи и/или аутентификации сообщений, используемые в этом протоколе, являются стойкими.
3. Действительность доказательств доказуемой безопасности
If it's provably secure, it's probably not
Однако я верю, что такое восприятие доказуемой безопасности связано по большей части с дебатами вокруг важности доказательств, чем с их действительностью как таковых.
Давайте изучим структуру типичного доказательства безопасности, которое, как было вышеупомянуто, обычно принимает форму редукции. Обычно в основе лежат некоторые предположения, которые могут быть или не быть выражены в явном виде. Это включает в себя законы среды, в которой имеет место гипотетическая атака. В модели атаки перечисляются точная криптографическая информация, доступная противнику, осуществляющему атаку. Это включает определения следующего:
- криптографические данные, доступные атакующему (например атака с подобранным шифртекстом);
- какие определены аспекты криптографичеких алгоритмов (например определение хэш-функции, используемой в алгоритме может быть доступно атакующему или нет — это важно в модели случайного оракула);
- какие определены аспекты исполнения (белый ящик, серый ящик, чёрный ящик); и
- вычислительные ресурсы, доступные атакующему.
Атакующий пытается достигнуть предопределённых криптографических целей (которые будут составлять взлом системы). Взлом может включать вычисление неизвестного ключа или различение двух определённых открытых текстов.
Редукция, которая составляет доказательство — это доказательство того, что если атакующий может достигнуть цели взлома, то атакующий (с небольшим дополнительным объёмом работы) способен достичь и некоторой другой цели, дополнительного взлома, возможно связанным с "примитивом" более низкого уровня, на котором основана схема.
То, что на самом деле доказывается, имеет утверждение вида:"Если противник может сделать 'X', то он также должен уметь делать 'Y'".
Какое это имеет отношение к безопасности? Обычно мы конструируем такое доказательство, чтобы 'Y' являлось каким-либо видом вычислений, которое мы считаем трудноосуществимым. Если мы верим, что противник не может сделать 'Y', то следует логический вывод доказательства, что мы также должны верить в то, что противник не может сделать 'X' (по крайней мере если он действует в рамках данной модели атаки).
Ситуация становится несколько туманнее, если мы попытаемся интерпретировать доказательства из доказуемой безопасности в "реальном мире". Тогда мы должы задаться вопросом, является ли модель атаки разумной. Мы должны рассмотреть возможность, что противник будет "играть не по правилам", как они определены в модели атаки (например мы можем доказать безопасность в модели чёрного ящика, но противник попытается провести атаку на побочные каналы, если у него есть доступ к определённой реализации системы). Также у нас остаётся вопрос о том, что невозможность противника сделать 'Y' действительно обоснованна.
Исторически, фундаментальное допущение, известное как "принцип Кирхгофа", играло важную роль в создании реалистичных подходов к концепции криптографической безопасности. На языке современной криптографии этот принцип звучит как то, что не следует считать модель атаки "разумной", до тех пор пока описание криптографического алгоритма (безопасность которого изучена) не предоставлено противнику. Однако, в последние годы стало очевидно, что противник может иметь информацию о специфической реализации криптографического алгоритма, что даёт ему возможность осуществлять атаки по побочным каналам, таким как атаки на измерение времени исполнения. Так могут быть рассмотрены несколько моделей, в зависимости от уровня детальности сведений, которыми владеет противник о криптосистеме и как она выполнена в реальном воплощении.
Наконец, мы должны помнить, что не стоит уповать на то, что математические доказательства могут быть применены к "реальному миру". Мы не ожидаем, что инженер математически доказывает непотопляемость корабля (может быть Титаник?) или то, что мост не рухнет (первый подвесной мост Tacoma Narows рухнул 7 ноября 1940 года из-за вибраций, вызванных ветром). Аналогично, нам не следует ожидать, что мы можем доказать, что реализованный криптографический алгоритм не может быть взломан. Для этого слишком много неизвестных: криптографический алгоритм — компонент более сложного протокола. Протокол выполнен (в аппаратном или программном виде) на некоторой платформе, на которой запущена некоторая операционная система, которая может быть подключена к интернету. Как мы можем ещё надеяться на доказательство того, что конечная система будет безопасна?
В итоге, важно помнить, что валидность и релевантность (действительность и область применимости) доказательства в криптографии — это часто две соверешнно разные вещи:
- Валидность (действительность) доказательства отсылает нас к корректности этого доказательства, в пределах полностью конкретизированной и консистентной (непротиворечивой) математической модели. Если всему даны верные определения, то возможно (по крайней мере в принципе), определить, что данное доказателство является действительным.
- Релевантность (область применимости) доказательства намного более субъективна. Для вынесения оценки о релевантности доказательства, мы оцениваем потенциальное соответствие определений и математической модели, используемой в доказательстве, к тому что существует в реальном мире. В лучшем случае доказуемая безопасность предоставляет некоторые вероятные или правдоподобные свидетельства, а не доказательства (подчинённые некоторым правдоподобным или вероятным допущениям) того, что криптографическая схема будет безопасна при использовании в реальном мире.
4. Модель случайного оракула
Модель случайного оракула достигла высокого уровня известности. Крамер и Шуп написали, что любое доказательство, включающее модель случайного оракула должно рассматриваться как "эвристическое доказательство". Возможно даже более важно, что имелось некоторое количество опубликованых результатов, которые были доказанно стойкими в модели случайного оракула и становились нестойкими, как только случайного оракула заменяли любой реальной хэш-функцией (например SHA-1) (прим. перев.: эти результаты были получены когда SHA-1 и её аналоги считались криптостойкими функциями и для них не было известно никаких серьёзных уязвимостей, т.е. имеется ввиду, что даже если любая хэш-функция стойкая, она не могла заменить случайный оракул, по крайней мере на том этапе знаний в созданий хэшей). В любом случае, можно заметить существование широко распространённых мнений, что существует громадный "зазор" между доказательством, которое использует модель случайного оракула и доказательством, которое её не использует.
Дебаты показывают реальную обеспокоенность о роли модели случайного оракула как инструмента в криптографии. Другими словами, являются ли доказательства в модели случайного оракула релевантными по отношению к "реальному миру"? Точнее — являются ли доказательства в модели случайного оракула фундаментально или в значительной степени отличными, в терминах релевантности по отношению к реальному миру, если сравнивать их с доказательствами, не использующими модель случайного оракула?
Источник этой дискуссии уходит обратно к истокам работы 1993 года Беллэйра и Рогуэя в которой была представлена модель случайного оракула. Беллэйр и Рогуэй сформулировали следущее в реферативном предисловии к своей работе:
Мы утверждаем, что модель случайного оракула — где все стороны имеют доступ к публично доступному случайному оракулу — перебрасывает мост между криптографической теорией и криптографической практикой. В предложенной нами парадигме, практический протокол является продуктом разработки и доказательства корректности протокола в модели случайного оракула, а затем заменой доступа к оракулу на вычисление "соответствующим образом выбранной" функции.
Мы приводим аргументы в пользу того, что никакое доказательство доказуемой безопасности не является доказательством в реальном мире. Существуют различные модели атак, которые могут быть рассмотрены в контексте любого доказательства безопасности. В идеале мы должны искать наименее ограничивающую модель атаки, когда выводим результат из доказательства (это может быть самый "сильный" результат стойкости). Существует множество вариаций модели атаки от самой сильной до самой слабой, и по моему мнению, модель случайного оракула может рассматриваться только как один из множества вариантов.
Если мы принимаем модель случайного оракула, это значит, что атакующий ограничен атаками, в которых хэш-функция является случайным оракулом (независимо от того является она на самом деле случайным оракулом или нет). Такие атаки обоснованно называют атаками, свойственными для всех хэшей ("хэш-генериками"). Доказательство безопасности в модели случайного оракула означает, что рассматриваемая схема не может быть взломана (в предмете различных допущений) никакой хэш-генерик атакой. (Прим. автора статьи: Насколько мне известно такая интерпретация впервые была предложена Бэйк-Вилсоном, Джонсоном и Менезисем.). Другими словами мы завершаем рассмотрение тем, что данная схема не может быть взломана определённым типом атак — и это всё что мы можем сделать с помощью доказательств доказуемой безопасности, по-любому.
Разумеется, доказательство в модели случайного оракула как правило не исключает возможность успешной атаки, которая использует специфические свойства хэш-функции, выполненной в схеме. Однако, это и не даёт мне особенных причин для беспокойства, отчасти потому что крайне сложным является подход, основанный на атаке "реальной" схемы на хэш-функции, которая считается безопасной (Автор статьи приводит ссылки на работу, где этот вопрос освещается подробнее).
Чтобы добавить немного рациональности к моим вышеприведённым аргументам, возможно имеет смысл рассмотреть другой компонент многих криптографических схем, который обычно не рассматривают при выводе доказательств доказуемой безопасности. А именно: многие схемы шифрования, схемы подписи и др. используют генераторы случайных чисел. Хорошо известно, что использование слабого генератора случайных чисел может подвергнуть полному взлому схемы, которые в противном случае были бы безопасными. С другой стороны, часто остаётся несформулированным, включая утверждения в доказательствах доказуемой безопасности, что совершенные случайные числа доступны всегда, когда бы они не потребовались (например в схеме подписей Шнора). Разумеется, это не такой случай и на практике случайные числа часто генерируются генераторами псевдослучайных чисел. Генераторы псевдослучайных чисел не более совершенны, чем генераторы истинно случайных чисел, как и хэш-функции не более совершенны, чем случайный оракул. Однако, не видно, чтобы какие-либо споры в будущем шли вокруг легитимности оставшейся невысказанной "модели совершенного генератора случайных чисел", лежащей в основе многих доказательств доказуемой безопасности. (Прим. автора статьи: Я не утверждаю никакого типа "эквивалентности" между хэш-функциями, исполняющими роль случайного оракула в качестве противоположности генераторов псевдослучайных чисел, исполняющих роль генераторов совершенных случайных чисел. Есть один момент: генератор псевдослучаных чисел имеет неизвестное секретное значение, в то время как хэш-функции полностью открыты).
5. Культура публикаций материалов конференций
Часто можно услышать жалобы, что многие работы по доказуемой безопасности наполнены жаргоном, сложны для чтения, неточны и часто некорректны. Однако эти претензии могут быть применимы ко многим работам по криптографии и теоретической комьютерной науке в целом. Математические работы могут тоже быть такими, что читать их не легче, но очевидно имеется широкораспространённое мнение, что опубликованные доказательства в математике более корректны, чем опубликованные доказательства в криптографии. Если это и на самом деле так, то почему это является правдой?
Мне кажется, что большая разница между культурой публикаций в математике и компьютерных науках это то, что форумом для математических исследований служат впервую очередь журналы, в то время как исследования в области компьютерных наук гораздо чаще издаются в материалах конференций.
Публикации для конференций имеют преимущество в быстроте издания, так что исследования быстро распространяются. К сожалению, рассмотрение программным комитетом обычно представляет собой плохую замену рассмотрения квалифицированными экспертами в вопросах представленных статей в реферативных журналах (для более обстоятельных дискуссий смотрите вэб-страницу Голдрейха по программным комитетам).
Другие помехи в публикациях на конференциях включают следующее:
- Статьи для конференций часто подготавливаются в спешке (чтобы успеть к дате последнего приёма работ).
- Работы для конференций могут не подвергаться пересмотру или обновлениям после презентации на конференции (часто материалы конференции публикуются до начала её фактического проведения).
- Доказательства и разъяснения деталей часто отсутствуют (возможно всвязи с ограничением на количество страниц) .
- У авторов часто мало стимулов для того, чтобы проделать дополнительную работу и подготовить "журнальную версию" своей работы. Например, публикация в ведущей конференции может иметь больший вес в умах председателей комитетов, чем журнальные публикации.
Я верю в то, что разумным является заключение, что публикация материалов конференции не является эквивалентом публикации в архивном журнале. Статьи с конференций очень полезны для быстрого распространения материалов исследований среди широкой аудитории, но журнальные публикации играют важную и дополняющую роль в предоставлении полной, детальной и корректной трактовки результатов исследований (которые могут быть представлены на конференции в предварительной форме). Миру нужны журнальные статьи также как и материалы конференций!
6. Трудности с определениями
Эти типы трудностей с определениями по большей части не существуют в традиционной чистой математике. Мы не наблюдаем групп математиков, спорящих, является ли определение конечного поля "корректным" определением. Концепции и терминология в математике слишком стандартизированы и хорошо понятны тем, кто применяет их на практике. Может быть нелегко доказать, что теорема классификации конечных простых групп истинна, но по крайней мере нет неоднозначности в интерпретации того, о чём говорит эта теорема.
Причина такого контраста между математикой и криптографией может быть основана на ориентированности криптографии в сторону прикладных наук. Криптографы пытаются анализировать и доказывать вещи, которые имеют правдоподобное отношение к реальному миру. Изобилие различных моделей определений которые появляются в криптографических исследованиях — это отражение факта того, что не существует единственно "правильного" пути изучения криптографии. С другой стороны, математики и математические доказательства действуют внутри формальной модели и обычно это не имеет смысла, если модель "согласовывается" с реальным миром любым осмысленным способом. Полемика вокруг действительности доказательств в криптографии часто подогревается разницами в интерпретациях и непониманием, относящимся к положенным в основу определениям.
Для меня, попытка классифицировать определения является наиболее удивительным аспектом криптографии, особенно потому, что это так трудно сделать. Эта одна из особенностей исследований в области криптографии, которая очевидно фундаментально отличается от исследований в математике. В итоге криптографические исследования более плодотворны (и вызывают больше возражений, являются более сомнительными) по этой причине.
7. Итоги
- Доказательства доказуемой безопасности (стойкости) — это всего лишь доказательства определённого типа безопасности в определённой модели атаки. Никакое доказательство из области доказуемой безопасности не может быть интерпретировано как доказательство безопасности в реальном мире.
- Модель случайного оракула — всего лишь одна из множества моделей атак, которая может рассматриваться в контексте доказуемой безопасности. Она не является фундаментально "отличающейся" от многих других моделей атак.
- Необходимо сделать больший акцент на размещении публикаций в "журнальных версиях" публикаций из конференций в порядке неободимости иметь архивные записи полных и корректных версий важных исследовательских результатов.
- Точное определение концепций в криптографии является одной из ведущих задач в хороших криптографических исследованиях.
комментариев: 1515 документов: 44 редакций: 5786
А почему?! Не хорошо умалчивать и говорить недомёками. Ну, допустим, нет сейчас хорошей теории алгоритмов, не почему такая уверенность, что она не появится в будущем? Всего каких-то лет 100 назад не было, например, теории вероятности в непрерывном спектре, пока её не построил Колмогоров, введя аксиоматику Колмогорова, и дав толчок развитию новой строгой матдисциплины, активно использующей достижения в функциональном анализе, теории обобщёных функций и теории множеств: теории стохастических процессов.
Опять же неточность. Да, есть так называемый класс трудноразрешимых матпроблем. Если есть строгое доказательство, что взлом данной криптосистемы (при данном виде атак) эквивалентен решению какой-либо сложной задачи (зная одно, можно сделать другое и наоборот), то дело в шляпе: мы показали, что не выходим за рамки класса трудноразрешимых задач. Очень здравый подход. Здесь нужно не мешать в кучу котлет с мухами: сведение к трудноразрешимой задаче – хорошо, ограниченность модели атак – плохо, доказательством в матсмысле, в итоге, это – не является, однако, опять же, сведение к труднорешаемой задаче (эквивалентность) само по себе – хорошо.
По поводу сложности конкретно системы RSA: недавно наткнулся на вещь, называемую Проблема Гольдбаха. Если даже такая (как мне кажется тоже достаточно простая вещь) есть до сих пор проблема, значит самое интересное будущее теории чисел и криптографии ещё впереди, а пока в теории чисел ещё очень много непонятного и интересного: видимо, время строгого конструктивизма в криптографию ещё не пришло. Впрочем, не факт что это так уж страшно: все матдисциплины проходили эту стадию – матанализ тоже удалось формализовать сравнительно недавно.
Математические доказательства также обладают рядом серьёзных изъянов. Как минимум следует упомянуть о таких известных дискуссиях в среде математиков, как приемлемость аксиомы выбора, следствия из существования теоремы Гёделя о неполноте (см. также научно-популярную статью на эту тему), а также вопросы о конструктивности: из ряда матаксиом следует существование объектов, которые никто и никогда не видел, и которые не являются конструктивно построимыми, однако, утверждается, что они существуют. Емнип, из аксиомы выбора следует, что существует отношение порядка, позволяющее сделать так называемое "полное упорядочение" всех чисел из открытого интервала (0,1). В полном упорядочении множества всегда существует минимальный и максимальный элемент.
Мне кажется, что криптография в этом смысле по всем признакам является разделом физики, где дела обстоят точно так же :=) Говоря более точным языком, есть такая штука, тесно перекликающаяся с матфизикой, как "теория моделей", которая занимается изучением матмоделей, в которых важны качественные рассуждения. Физика, экономические и финансовые модели, в свою очередь, изучаются уже с помощью готовых моделей. Дело здесь даже не только в том, что изучать модели строго математично очень трудно, но и в том, что чем-то (какими-то эффектами) приходится пренебрегать в пользу остальных, более существенных. Аналогично и в криптографии: модели оракула – это просто удачная модель, где пренебрегается неидеальностью хэш-функции, и у этой модели есть своя "область применения". Даже если модель не описывает реальность, она всё равно не теряет смысл: логично сначала искать доказательство важных фактов в модели случайного оракула, и только если в её рамках безопасность подтверждается, искать доказательство при более точной модели. Главное отличие криптографии от физики здесь в том, что "небольшое отклонение" от истинного значения в физике всех устроит, в криптографии же оно иногда может обессмыслить всю работу. Почему иногда – потому что чаще удаётся показать, что лишь снижается оценка стойкости в результате вновь открывшихся обстоятельств/фактов, т.е. что хоть и есть дырка в дне лодки, но для Титаника криптографии не фатальна :) (айсберг ещё впереди).
Оно вообще странно, что не распространены публикации в открытых рецензируемых журналах. В обычной науке работа в трудах конференций "полноценной публикацией" вообще не считается, либо приравнивается к "публикации в нерецензируемом журнале", по оговоренным же в статье причинам (хотя никто не мешает ссылаться хоть на труды конференций, хоть сразу на архив). Как раз принятие статьи в журнал и рассматривается как условный аудит результата сообществом (и всё равно, существенный процент ошибочных статей, т.к. уровень реферирования даже в ведущих журналах достаточно слаб и чаще чисто формален).
На эту тему (она там более общая: "куда ведёт традиционный подход в математике") есть поучительная статья в элементах, так что не в одной только криптографии проблемы :-)
PS: спасибо за перевод, конечно. Очень поучительная статья, систематизирует.
комментариев: 1515 документов: 44 редакций: 5786
Пожалуй, даже процитирую:
http://ru.wikipedia.org/wiki/Аксиома_выбора
А ведь криптография тоже тоеорию множеств использует, или в ней только натуральные числа и поэтому проблемы нет?
[/offtop]
комментариев: 9796 документов: 488 редакций: 5664
все разделы математики вообще и абстрактной алгебры в частности.
как говорил Коблитц — глупо предсказывать, какой раздел математики не будет использован в криптографии.
криптография ещё в более сложном положении. Физика тоже изучает законы реального мира, накладывая на них идеальные математические модели с эмпирическими поправками (примерно так?), а криптография пытается смоделировать не природный или лабораторный процесс, а разумного атакующего, который может использовать закономерности реального мира как ему вздумается, причём нарочно так, чтобы разрушить построенную для него модель поведения.
Представляю, как соревновались бы две команды физиков. Одна например наконец смогла создать точную теорию плазмы, красивые уравнения написать и запустить термоядерный реактор. А вторая придумывает способы, как бы незаметно испортить плазму в реакторе, чтобы у первой команды ничего не получилось :)
И да, для науки криптография ещё очень молода.
комментариев: 1515 документов: 44 редакций: 5786
Смотря что понимать под законами реального мира. Например, основные законы уже давно известны, но когда надо определить что же произойдёт макроскопически, возникают проблемы, т.к. полная система всех уравнений практически не решаема. Вот как вытекает вода из карана? Что для неё важно? "Кладбище теорий турбулентности уже переполнено" ©. Или возьмите процессы разгерметизации в тепловыделяющих элементах реакторов, или взаимодействие веществ с фемтосекундными импульсами лазеров, или же просто взаимодействие плазмы с веществом: нет внятных моделей этих процессов, есть только эмпирические данные. Дело даже не в том, что нет решений: нет написанной самой системы дифференциальных уравнений, которые надо совместно решать. Микроскопика, т.е., известна, а макроскопика (статфизика) – уже нет, и под каждый случай её надо писать заново.
Думаю, здесь всё же надо разделять криптографию и "теорию информационной безопасности". Криптография – то, что работает с сравнительно идеальными алгоритмами, ИБ – с реальным окружением где они выполняются, поэтому в рамках крипто какого-нибудь tempest'а нет, а в рамках ИБ есть. Границы условные, может быть, в будущем будут модели, которые будут учитывать и экзотические, сугубо практические атаки (типа раскрытия атакующему половины всей оперативной памяти машины).
комментариев: 1515 документов: 44 редакций: 5786
Такие парадоксы как раз и возникают из-за отсутствия объективного фундамента фактов, которые "существуют вне зависимости от нас и наших мнений о них" как писалось в школьных учебниках. Тем не менее криптография всё же работает над выработкой и доказательством таких базовых положений, которые впоследствии внезапно не окажутся не верными. Доказательство отсутствия быстрых алгоритмов факторизации могло бы быть одним из таких фундаментов. Пока же такой теоремы нет, теория строится в предположении что она есть, и будет существовать до тех пор, пока не будет опровергнуто. Ещё можно сказать, что криптография чем-то напоминает постоянное решение задач, если даже не софизмов, та самая извечная борьба щита и меча.
комментариев: 9796 документов: 488 редакций: 5664
Обычно ещё и само доказательство неполное и асимптотическое.
это не проблема в математике: есть набор аксиом из них строится логически непротиворечивая теория с теоремами и доказательствами, если нужно — получаем новый раздел математики из нового вида абстракций.
Хочет это кто-то применить на практике и как — математиков-теоретиков не волнует.
В криптографии тоже можно настроить абстрактных систем. Только трудно смоделировать абстрактного противника и доказать, что противник в реальном мире не будет мощнее его, что модели настолько сильны, что он не выйдет за рамки этих ограниченных моделей.
Абсолютно верно! Random Oracle — это абстрактный суррогат нерешаемой задачи. Если автор может предоставить доказательство стойкости в модели RO, с ним уже можно дальше говорить серьёзно. Ну или говорить о недостаточной полноте доказательства, о необходимости улучшить, двигаться дальше. Если автор неспособен привести доказательство стойкости своей системы в модели RO или доказана нестойкость даже в модели RO — то до свидания, система безнадёжно взломана. Хороший способ первичного отсева.
комментариев: 1515 документов: 44 редакций: 5786
Логическое противоречие есть: в процессе доказательства мы осуществляем "некоторую операцию", которую на практике для произвольного множества не ясно как осуществить. А разумное доказательство должно поддерживать конкретизацию, сведение к более частному случаю, а то получается проблема в стиле "доказать коммутативность сложения любых простых чисел мы можем, а конкретно чисел 5 и 7 – нет, но мы надеемся что они тоже коммутативны, так как это вродебы следует из общего" (окольцовывание логики).
комментариев: 9796 документов: 488 редакций: 5664
Теорема: Существует рациональное число, представимое ввиде иррационального числа, возвендённого в иррациональную степень.
Доказательство: Поскольку √2 – иррационален, искомым рациональным числом явлется либо x=√2√2 либо 2=x√2.
Вопрос 1: Это разумное доказательство?
Вопрос 2: Как из него узнать, какое конкретно это число?
комментариев: 9796 документов: 488 редакций: 5664
Итак, предположим, что √2√2 – иррациональное число. Возведём это число в степень иррациональную степень √2:
(√2√2)√2 = √2(√2*√2) = (√2)2 = 2 – рациональное число.
Ну а если предположить, что √2√2 – рациональное число, тогда оно будет искомым. ;)
А в теореме Гельфонда речь идёт не обо всех числах, а только об алгебраических (корнях многочлена с рациональными коэффициентами). Из неё следует, что √2√2 таковым не является, а значит не является рациональным, а значит конструктивный ответ 2.
Но неужели без теоремы Гельфонда вышеприведённое доказательство неразумно?
комментариев: 11558 документов: 1036 редакций: 4118
Присоединяюсь. Осознание существующих проблем — суть залог движения вперёд. Автор — молодец, переводчик — тоже. :-)
ps
Да, я знаю, что лучше переводить, но как лучше? ;)
комментариев: 1515 документов: 44 редакций: 5786
Насколько всеобщ и разумен закон исключённого третьего? Там же и ваш пример рассмотрен, и критика его. По ссылке же:Красноречивый ответ там же:Т.е. перекликается с неполнотой формулировки. Другой канонический пример: http://ru.wikipedia.org/wiki/Парадокс_лжеца.
Никак. См. ответ выше.
Уточнение:Ошибся: на самом деле тот или другой, по конвенции – минимален. Возможность выбора минимального элемента нужна в доказательствах при использовании так называемой трансфинитной индукции. По аксиоме выбора минимальный элемент всегда есть. Однако, его никто и никогда не видел, и не известно, увидит ли (в произвольном подмножестве вещественных чисел). Т.о. доказательство оперирует с объектом, существование которого пока очень сомнительно.
e^ln(10)=10 – контрпример.