Устройство для ремонта и тестирования персональных компьютеров (ПК) POST Card PCI применяется для диагностики неисправностей при ремонте и модернизации компьютеров, а также периферийных систем. Оно найдет широкое применение в любых электронных системах, работающих на основе компьютеров типа IBM PC (или совместимых с ними).
POST Card PCI (рис. 1) представляет собой плату расширения ПК, которая может быть установлена в любой свободный PCI-слот (33 МГц) и предназначена для отображения POST-кодов, генерируемых системой BIOS ПК, в удобном для пользователя виде.
Рис. 1. Внешний вид устройства
Благодаря применению ПЛИС (программируемая логическая интегральная схема) фирмы Altera стало возможным создание простого и доступного для повторения радиолюбителями устройства.
Кроме того, устройство можно использовать как тестер микросхем. Для этого в нем предусмотрена 44-выводная панель для микросхемы.
Устройство POST Card PCI имеет следующие технические характеристики:
- Напряжение питания, В +5
- Ток потребления, мА
- Частота шины PCI ПК, МГ ц 33
- Адрес диагностического порта 0080h
- Индикация POST кодов (в шестнадцатеричном виде) 1 байт
- Индикация сигналов PG шины RST (левая точка), CLК (правая точка индикатора)
- Индикаторы наличия напряжения источника питания, В +5, +12, -12, +3,3
- Совместимость с материнскими платами на чипсетах Intel, VIA, SIS
- Размер печатной платы, мм 112x90
Основой POST Card PCI является ПЛИС DD1 (рис. 1, 2), на которой реализовано упрощенное PCI Target-устройство, поддерживающее запись в порт вывода и автоматическое конфигурирование (Plug&Plug), достаточные для функционирования устройства. ПЛИС Altera EPM3064ALC44-10 входит в набор и запрограммирована компанией МАСТЕР КИТ специально для работы в POST Card PCI. На микросхеме DD2 собран стабилизатор напряжения +3,3 В для питания ПЛИС. Информация из ПЛИС выводится в последовательном виде и фиксируется в регистрах DD4, DD5. Их выходы через ограничительные резисторы подключены к сдвоенному 7-сегментному индикатору HL1, на котором отображаются POST-коды. Для того чтобы процесс индикации POST кодов не нарушался в случае срыва генерации PCI CLK на неисправной материнской плате, в состав POST Card PCI включен отдельный генератор на микросхеме DD3.
Рис. 2. Принципиальная электрическая схема устройства POST CARD PCI
Светодиоды, включенные через ограничивающие резисторы, индицируют наличие напряжений +3,3, +5, + 12 и -12 В на шине PCI.
Принцип работы
При каждом включении питания ПК, совместимого с IBM PC, и до начала загрузки операционной системы процессор компьютера выполняет процедуру BIOS под названием "Самотест по включению питания" - POST (Power On Self Test). Эта же процедура выполняется также при нажатии на кнопку RESET или при программной перезагрузке компьютера. В некоторых особых случаях с целью сокращения времени загрузки ПК процедура POST может быть несколько урезана по времени, например, в режиме "Quick Boot" или при выходе из режима "сна" (Hibernate).
Основной целью процедуры POST является проверка базовых функций и подсистем ПК (память, процессор, материнская плата, видеоконтроллер, клавиатура, гибкий и жесткий диски) перед загрузкой операционной системы. Это застраховывает пользователя от попытки работать на неисправной системе, что могло бы привести, например, к разрушению пользовательских данных на жестком диске. Перед началом каждого из тестов процедура POST генерирует POST-код, который выводится по определенному адресу в пространстве адресов устройств ввода/вывода ПК. В случае обнаружения неисправности в тестируемом устройстве процедура POST просто "зависает", а предварительно выведенный POST-код однозначно определяет, на каком из тестов произошло "зависание". Таким образом, глубина и точность диагностики при помощи POST-кодов полностью определяются глубиной и точностью тестов соответствующей процедуры POST-системы BIOS компьютера.
Некоторые коды неисправностей BIOS
В таблице приведены некоторые коды AMI BIOS, отражающие наиболее часто встречающиеся неисправности ПК.
Таблица
| Код | Неисправность |
| Ошибка конфигурации системной памяти (фатальная ошибка) |
|
| Ошибка конфигурации системной памяти (звуковой сигнал) |
|
| Ранняя инициализация контроллера клавиатуры |
|
| Ошибка инициализации VGA BIOS |
|
| Ошибка теста видеопамяти адаптера CGA |
|
| Ошибка теста схем формирования разверток адаптера CGA |
|
| Ошибка видеопамяти или схем формирования разверток |
|
| Отключение IRQ12, если PS/2 mouse отсутствует |
|
| Индикация сообщений об ошибках |
|
| Определение типа памяти, суммарного объем и размещение по строкам |
|
| Сообщение об ошибках на предыдущих этапах инициализации |
Кроме вышеуказанных POST-кодов в диагностический порт выводятся сообщения о событиях в процессе выполнения Device Initialization Manager (DIM). Существует несколько контрольных точек, в которых отображается состояние инициализации системных или локальных шин.
В случае если обнаружена ошибка конфигурации системной памяти (коды DE или DF), в порт 80h выводится последовательно в бесконечном цикле код DE, код DF, код ошибки конфигурации, который может принимать следующие значения:
00 - оперативная память не обнаружена;
01 - установлены модули DIMM различных типов (пример, EDO и SDRAM);
02 - чтение содержимого SPD закончилась неудачей;
03 - модуль не соответствует требованиям для работы на заданной частоте;
04 - модуль не может быть использован в данной системе;
05 - информация в SPD не позволяет использовать установленные модули;
06 - обнаружена ошибка в младшей странице памяти.
Практический поиск неисправностей с использованием тестера POST Card
Прежде всего, при включении питания перед началом работы процедуры POST должен произойти сброс системы сигналом RST (RESET), что индицируется на POST Card кратковременным миганием левой точки на индикаторе. Рассмотрим несколько наиболее популярных неисправностей ПК и способы их локализации.
POST-коды не отображаются
При неисправности компьютера в самом сложном случае сброс либо совсем не проходит, либо проходит, но никакие POST-коды на индикаторе не отображаются.
Рекомендуется немедленно выключить компьютер и вытащить все дополнительные платы и кабеля, а также память ОЗУ из слотов материнской платы, оставив подключенной к блоку питания только собственно материнскую плату с установленными процессором и POST Card. Если при последующем включении компьютера нормально проходит сброс системы и появляются первые POST-коды, очевидно, проблема заключается во временно извлеченных компонентах компьютера. Возможно, неправильно подключены шлейфы. Вставляя последовательно модули памяти, видеоадаптер, а затем и другие карты, и наблюдая за POST-кодами на индикаторе, обнаруживают неисправный модуль.
Не проходит даже начальный сброс системы (на индикаторе POST Card в самом начале теста кратковременно не загорается левая точка индикатора)
В этом случае либо неисправен блок питания компьютера, либо сама материнская плата (неисправны цепи формирования сигнала RESET). Точную причину можно установить, подсоединив к материнской плате заведомо исправный блок питания.
Сигнал сброса проходит, но никакие POST-коды на индикатор не выводятся (тестируется система, состоящая только из материнской платы, процессора, POST Card и блока питания)
Если материнская плата новая, то причина может быть в неправильно установленных переключателях на материнской плате. Если все переключатели и процессор установлены правильно, а материнская плата не запускается, следует заменить процессор заведомо исправным. Если же это не помогает, то можно сделать вывод о неисправности материнской платы либо ее компонентов (например, причиной неисправности может являться повреждение информация во Flash-BIOS).
Неисправности ПК, определяемые с помощью тестера pOsT Card
После включения питания компьютера (или нажатия на кнопку RESET) и до появления первого POST-кода на индикатор POST Card выводится специальный символ (см. рис 3), который свидетельствует об отсутствии вывода ПК каких-либо POST-кодов. Эта особенность работы данной POST Card облегчает диагностику и позволяет наглядно определить, стартует ли компьютер вообще. Кроме того, этот же символ выводится при программном сбросе PCI-шины для фиксации прохождения сигнала RST. Точки 7-сегментного индикатора POST Card отображают состояния сигналов RST и CLK шины PCI. Зажигание правой точки соответствует наличию активного сигнала синхронизации CLK шины PCI, зажигание левой точки - наличию активного сигнала RST
Рис. 3. Индикация на POST Card об отсутствии вывода ПК каких-либо POST-кодов
При исправном компьютере при включении питания вначале должен произойти сброс системы сигналом RESET (что индицируется на POST Card специальными символами), затем - запуск компьютера с последовательным прохождением всех POST кодов. При неисправности компьютера в самом сложном случае сброс либо совсем не проходит, либо проходит, но никакие другие POST-коды на индикаторе не отображаются.
В этом случае рекомендуется немедленно выключить компьютер, отключить все дополнительные платы и кабели, а также память из материнской платы, оставив подключенной к блоку питания только материнскую плату с установленными процессором и платой POST Card.
Если при последующем включении компьютера нормально проходит сброс системы и появляются первые POST-коды, то проблема заключается во временно извлеченных компонентах компьютера. Возможно неправильно подключены шлейфы (особенно часто вставляют "вверх ногами" шлейф IDE).
Последовательно устанавливают модуль памяти, видеоадаптер, другие карты и, наблюдая за POST-кодами, обнаруживают неисправный модуль.
Например, при неисправной памяти для компьютеров с AMI BIOS последовательность POST-кодов обычно фиксируется на коде d4; с AWARD BIOS - на кодах C1 или С6. Бывает, что при этом неисправен не сам модуль памяти, а материнская плата - причина заключается в плохом контакте в разъемах SIMM/DIMM (согнуты/замкнуты между собой контакты), либо не до конца вставлен модуль в разъем.
При неисправном видеоадаптере для компьютеров с AMI BIOS последовательность POST-кодов фиксируется на кодах 2C, 40 или 2A в зависимости от модификации BIOS либо эти коды отсутствуют, а на мониторе нет соответствующих строк инициализации видеокарты (с указанием типа, объема памяти и фирмы-производителя видеоадаптера).
Аналогично, для компьютеров с AWARD BIOS при неисправности видеоадаптера последовательность POST-кодов либо фиксируется на коде 0d, либо "проскакивает" этот код. Если инициализация памяти и видеоадаптера прошла нормально, устанавливают по одной остальные карты и, подключая шлейфы, на основании показаний индикатора POST Card определяют, какой из компонентов "подсаживает" системную шину, и не дает загрузиться компьютеру.
На рис. 4-6 показана индикация POST Card при возникновении различных ошибок.
Рис. 4. Код ошибки видеопамяти (во время тестирования карта видеопамяти была извлечена из системного блока)
Рис. 5. Код ошибки манипулятора "Мышь" (при тестировании манипулятор был отключен)
Рис. 6. Код ошибки оперативной памяти (при тестировании модуль памяти был удален из материнской платы)
Последовательность действий по реанимации ПК с помощью тестера POST Card PCI
1. Выключают питание неисправного компьютера.
2. Устанавливают POST Card в любой свободный слот материнской платы.
3. Включают питание ПК и считывают с индикатора POST-Card соответствующий POST-код, на котором прерывается ("зависает") загрузка компьютера.
4. По таблицам POST кодов при необходимости определяют, на каком из тестов возникли проблемы и их вероятные причины.
5. При выключенном питании переставляют шлейфы, модули памяти ОЗУ и другие компоненты, имеющие разъемы с целью устранения неисправности.
6. Повторяют пункты 3, 4, 5 для устойчивого прохождения процедуры POST и нормальной загрузки операционной системы.
7. При помощи программных утилит осуществляют окончательное тестирование аппаратных компонентов, а в случае "плавающих" (нестабильных) ошибок - длительный прогон соответствующих программных тестов.
В начале транзакции активное устройство активизирует линию FRAME#. По шине AD передает адрес, а по линиям C/BE# – команду. Адресованное пассивное устройство отзывается сигналом DEVSEL#.
Активное устройство показывает готовность к обмену сигналом IRDY#. Данные передаются только при одновременной активации сигналов IRDY# и TRDY#, причем TRDY# формируется тогда, когда пассивное устройство готово к обмену.
За адресной частью следует фаза пересылки данных. Количество передаваемых слов в пакете не указывается, но перед последним словом данных устройство снимает сигнал FRAME#. В частном случае передается одно слово.
Каждое ведомое устройство должно довольно быстро отвечать на транзакцию. Ожидание может составлять несколько тактов, но не может превышать 8 тактов.
Если устройство не успевает, то формируется сигнал STOP#.
8. Команды шины pci.
PCI поддерживает 16 различных операций на шине; из них реализовано только 12, а остальные зарезервированы. Тип операции зависит от команды, передается по линиям C/BE# (количество линий – 4). Тип операции передается в течение фазы адреса.
Используются следующие операции:
0000 – подтверждение прерывания;
0001 – специальный цикл (в данном цикле ЭВМ передает устройствам различные сообщения);
0010 – чтение порта ввода-вывода;
0011 – запись в порт ввода-вывода;
0100 – резерв;
0101 – резерв;
0110 – чтение памяти;
0111 – запись в память;
1000 – резерв;
1001 – резерв;
1010 – чтение конфигурации;
1011 – запись конфигурации;32
1100 – циклическое (многократное) чтение памяти (используется при обращении к строкам кэш памяти);
1101 – цикл с 64-разрядным адресом (двухадресный цикл, позволяет по 32-битной шине обращаться к устройствам с 64-битной адресацией);
1110 – чтение строк памяти (чтение до конца строки кэша);
1111 – запись в память с инвалидацией (отменой достоверности).
В фазе данных линии C/BE# указывают на информационные байты.
При этом линии выбирают следующие байты:
C/BE# 0 -> AD7 – AD0,
C/BE# 1 -> AD15 – AD8,
C/BE# 2 ->AD23 – AD16,
C/BE# 3 -> AD31 – AD24
Количество адресуемых байт может быть 1, 2, 3 или 4.
9 Прерывание и захват шины pci, конфигурация устройств.
Прерывание организуется с помощью линий подачей сигнала низкого уровня на одну из линий INTA#,INTB#,INTC#,INTD#. Этот сигнал должен удерживаться до тех пор, пока драйвер, вызванный по прерыванию, не сбросит запрос прерывания, обратившись по шине к данному устройству. Драйвер определяет адрес устройства чтением конфигурационного регистра. Это происходит, когда на шинеC/BE# выставлена команда 0000. Приоритеты устройств определяются программированием арбитра
процессора ЭВМ. Подтверждение прерываний надо снимать с линий C/BE. Драйвер, работающий с устройствомPCI, определяет вектор прерывания, доставшийся устройству, чтением конфигурационного регистра.
Захват шины осуществляется с подачей сигнала запроса захвата на линию REQ#. Ответный сигнал подтверждения захвата передается арбитром процессора по линииGNT#. В режиме захвата устройство становится активным и управляет шиной по своему усмотрению. В частном случае
реализуется режим прямого доступа в память (DMA).
Шина PCIимеют возможность электронной конфигурации, подключенных к ней устройств. Это позволяет автоматически перераспределять ресурсы компьютера (диапазоны адресов памяти и портов ввода-вывода, линии прерывания и др.) между устройствами. Эта технология называетсяPlug&Play.33
Координационные средства по распределению ресурсов между устройствами выполняют специальные конфигурационные программы.
В шине PCIдля осуществления конфигурации устройств есть две команды: чтение и запись конфигурации. С их помощью происходит определение типа устройств с их шиной, потребности ресурсов и предоставление им этих ресурсов.
Информация о конфигурации записывается и хранится в 256 байтах. Доступ к ним производится при активации сигнала на линии IDSEL, подключенной индивидуально к каждому устройству (слоту расширения). Конфигурационное обращение идет поочередно. Всем устройствамPCIприсваивается индивидуальный адрес, который определяется схемотехникой системы.
Так, если в слот-расширение вставлена видеокарта, то ее конфигурационное пространство доступно по адресу этого слота. При переустановке его в другой слот она будет иметь уже другой адрес.
Формат данных конфигурации включает следующие сведения: идентификатор производителя; идентификатор устройства; статус; идентификатор версии; класс, код; размер кэш-линии; максимальное время захвата шины; регистры базовых адресов; базовый адрес ПЗУ; регистр команды;
Спецификацией определены несколько механизмов доступа к конфигурационному пространству, но в простых системах он осуществляется через специальные регистры моста центрального процессора – регистры адреса и данных конфигурации.
Zero-knowledge proof ) - это интерактивный протокол, позволяющий одной из сторон (проверяющему, verifier) убедиться в достоверности какого-либо утверждения (обычно математического), не получив при этом никакой другой информации от второй стороны (доказывающего, prover).Доказательство с нулевым разглашением должно обладать тремя свойствами:
- Полнота : если утверждение действительно верно, то доказывающий убедит в этом проверяющего.
- Корректность : если утверждение неверно, то даже нечестный доказывающий не сможет убедить проверяющего за исключением пренебрежимо малой вероятности.
- Нулевое разглашение : если утверждение верно, то любой даже нечестный проверяющий не узнает ничего кроме самого факта, что утверждение верно.
Общая структура доказательств с нулевым разглашением
Каждый раунд или аккредитация доказательства состоит из трёх этапов. Схематично их можно изобразить следующим образом:
Сначала A выбирает из заранее определенного множества некоторый элемент, который становится её секретом (закрытый ключ). На основе этого элемента вычисляется, а затем публикуется открытый ключ. Знание секрета определяет множество вопросов, на которые А всегда сможет дать правильные ответы. Затем A выбирает случайный элемент из множества, по определенным правилам (в зависимости от конкретного алгоритма) вычисляет доказательство и затем отсылает его B . После этого B выбирает из всего множества вопросов один и просит A ответить на него (вызов ). В зависимости от вопроса, А посылает B ответ . Полученной информации B достаточно, чтобы проверить действительно ли А владеет секретом. Раунды можно повторять сколько угодно раз, пока вероятность того, что A «угадывает» ответы не станет достаточно низкой.
Такая техника называется также «разрезать и выбрать» (cut-and-choose).
Пример
Назовем проверяющую сторону Петей, а доказывающую сторону Димой (в англоязычной литературе обычно используются пары Peggy (от prover ) и Victor (от verifier ). Допустим Диме известен Гамильтонов цикл в большом графе G . Пете известен граф G , но он не знает гамильтонова цикла в нём. Дима хочет доказать Пете, что он знает гамильтонов цикл, не выдавая при этом ни самого цикла, ни какой-либо информации о нём (возможно Петя хочет купить этот гамильтонов цикл у Димы, но перед этим удостовериться, что он у Димы действительно есть).
Для этого Петя и Дима совместно выполняют несколько раундов протокола:
В каждом раунде Петя выбирает новый случайный бит, который неизвестен Диме, поэтому чтобы Дима мог ответить на оба вопроса, нужно чтобы H был в самом деле изоморфен G и Дима должен знать гамильтонов цикл в H (а значит также и в G ). Поэтому после достаточного числа раундов, Петя может быть уверен в том, что у Димы действительно есть гамильтонов цикл в G . С другой стороны, Дима не раскрывает никакой информации о гамильтоновом цикле в G . Более того, Пете сложно будет доказать кому-либо ещё, что он сам или Дима знает гамильтонов цикл в G .
Предположим, что у Димы нет гамильтонова цикла в G и он хочет обмануть Петю. Тогда Диме необходим неизоморфный G граф G" , в котором он всё-таки знает гамильтонов цикл. В каждом раунде он может передавать Пете либо H" - изоморфный G" , либо H - изоморфный G . Если Петя попросит доказать изоморфизм и был передан H , то обман не вскроется. Аналогично, если он просит показать гамильтонов цикл и был передан H" . В таком случае вероятность того, что Дима все-таки обманет Петю после n раундов, равна 1/2 n , что может быть меньше любой заранее заданной величы при достаточном числе раундов.
Предположим, что Петя не узнал гамильтонов цикл, но хочет доказать Васе, что Дима его знает. Если Петя, например, заснял на видео все раунды протокола, Вася едва ли ему поверит. Вася может предположить, что Петя и Дима в сговоре и в каждом раунде Петя заранее сообщал Диме свой выбор случайного бита, чтобы Дима мог передавать ему H для проверок изоморфизма и H" для проверок гамильтонова цикла. Таким образом без участия Димы доказать, что он знает гамильтонов цикл, можно лишь доказав, что во всех раундах протокола выбирались действительно случайные биты.
Злоупотребления
Предложено несколько способов злоупотребления доказательством с нулевым разглашением:
См. также
- Протокол Гиллу-Кискатра
Литература
- A. Menezes, P.van Oorschot, S. Vanstone. Handbook of Applied Cryptography. - CRC Press, 1996. - 816 с. - ISBN 0-8493-8523-7
- Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. - М .: Триумф, 2002. - 816 с. - 3000 экз. - ISBN 5-89392-055-4
Wikimedia Foundation . 2010 .
- Фонвизина, Наталья Дмитриевна
- Чужумово
Смотреть что такое "Доказательство с нулевым разглашением" в других словарях:
доказательство с нулевым разглашением конфиденциальной информации - Непроницаемое доказательство знания; доказательство обладания какой либо информацией, без разглашения этой информации. Тематики защита информации EN zero knowledge proof …
итеративное доказательство с нулевым разглашением конфиденциальной информации - — Тематики защита информации EN zero knowledge iterative proofZKIP … Справочник технического переводчика
не итеративное доказательство с нулевым разглашением конфиденциальной информации - НДНР — [] Тематики защита информации Синонимы НДНР EN non iterative zero knowledge proofNIZK … Справочник технического переводчика
Криптография - Немецкая криптомашина Lorenz использовалась во время Второй мировой войны для шифрования самых секретных сообщений Криптография (от др. греч … Википедия
Список алгоритмов - Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия
Криптограф - Немецкая криптомашина Lorenz, использовалась во время Второй мировой войны для шифрования самых секретных сообщений Криптография (от греч. κρυπτός скрытый и γράφω пишу) наука о математических методах обеспечения конфиденциальности… … Википедия
Программируемые алгоритмы - Служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавл … Википедия
SRP - Secure Remote Password Protocol (SRPP) протокол парольной аутентификации, устойчивый к прослушиванию и MITM атаке и не требующий третьей доверенной стороны. SRP содержит некоторые элементы из других протоколов обмена ключами и идентификации … Википедия
Протокол Фиата - Протокол Фиата Шамира это один из наиболее известных протоколов идентификации с нулевым разглашением (Zero knowledge protocol). Протокол был предложен Амосом Фиатом (англ. Amos Fiat) и Ади Шамиром (англ. Adi Shamir) Пусть А… … Википедия
Протокол Фиата-Шамира - Протокол Фиата Шамира это один из наиболее известных протоколов идентификации с нулевым разглашением (Zero knowledge protocol). Протокол был предложен Амосом Фиатом(англ. Amos Fiat) и Ади Шамиром(англ. Adi Shamir) Пусть А знает некоторый… … Википедия
Одна из лучших сторон современной криптографии - это ее прекрасная терминология. Можно создать сколько угодно панк-групп с названиями вроде Hardcore Predicate, Trapdoor Function или Impossible Differential Cryptanalysis. Однако есть термин, который превосходит все остальные. Это Zero Knowledge Proof - «доказательство с нулевым разглашением» .
Термин «с нулевым разглашением» настолько привлекателен, что это приводит к проблемам. Люди используют его неправильно, предполагая, что нулевое разглашение - это синоним «очень-очень надежной безопасности» . Из-за этого его используют с чем угодно - в том числе с системами шифрования и сетями анонимизации - которые на самом деле не имеют никакого отношения к протоколам с нулевым разглашением.
Я пишу это, чтобы подчеркнуть, что доказательства с нулевым разглашением входят в число самых мощных инструментов, когда-либо придуманных криптографами. К сожалению, понимают их настолько же плохо. В этой серии записей я попытаюсь доступно описать, что такое доказательства с нулевым разглашением и что делает их такими особенными. Мы также рассмотрим некоторые протоколы с нулевым разглашением, используемые в реальном мире.
История нулевого разглашения
Концепцию «нулевого разглашения» впервые предложили в 1980-х исследователи из MIT Шафи Гольдвассер (Shafi Goldwasser), Сильвио Микали (Silvio Micali) и Чарльз Рекофф (Charles Rackoff). Они изучали проблемы, связанные с интерактивными системами доказательства - теоретическими системами, в которых одна сторона («Prover» - Доказывающий), обменивающаяся сообщениями со второй стороной («Verifier» - Проверяющий), пытается убедить ее в истинности какого-либо математического утверждения.*
До Гольдвассер и ее коллег работы в этой области в основном фокусировались на корректности системы доказательства. Иначе говоря, ученые рассматривали ситуации, в которых злой Доказывающий пытался «обманным путем убедить» Проверяющего поверить в ложное утверждение. Гольдвассер, Микали и Рекофф перевернули проблему с ног на голову. Вместо того чтобы беспокоиться только о Доказывающем, они решили рассмотреть, что происходит, если вы не доверяете Проверяющему.
Конкретной проблемой, которую они поставили, была утечка информации. Ученые задались вопросом, сколько дополнительной информации Проверяющий узнает в ходе доказательства помимо того факта, что утверждение истинно.
Важно отметить, что это было сделано не просто из теоретического интереса - у таких задач есть реальные сферы применения. Вот один из таких сценариев: представьте, что пользователь в реальном мире хочет войти на веб-сервер с помощью пароля. Стандартный «реалистичный» подход к этой проблеме включает сохранение хешированной версии пароля на сервере. Таким образом, вход на сервер можно рассматривать как своеобразное «доказательство» того, что хеш пароля является результатом применения хеш-функции к какому-то паролю и что клиент на самом деле знает пароль.
Большинство реальных систем реализуют это «доказательство» наихудшим способом из возможных: клиент просто передает оригинальный пароль серверу, который вычисляет хеш пароля и сравнивает его с сохраненным значением. Недостаток такого подхода очевиден: сервер узнал незашифрованный пароль клиента. Таким образом, современная парольная гигиена во многом основана на предположении, что сервер не скомпрометирован.
То, что предложили Гольдвассер, Микали и Рекофф, возродило надежду на реализацию доказательств с нулевым разглашением, доказуемо не сообщающих никакой информации, кроме одного бита, означающего «это утверждение истинно».
Пример из «реального мира»
Пока наше обсуждение довольно абстрактно, так что давайте рассмотрим «реальный» пример (немного безумного) протокола с нулевым разглашением.
Представьте, что я - телекоммуникационный магнат, развертывающий новую сотовую сеть. Структура моей сети показана на приведенном ниже рисунке. Каждая вершина в этом графе представляет радиовышку, а ребра графа указывают места, где соты перекрываются , то есть где прием сигналов может быть затруднен. К счастью, для предотвращения помех я могу назначить каждой вышке один из трех разных частотных диапазонов.
Таким образом, проблема развертывания сети заключается в том, как назначить частотные диапазоны вышкам так, чтобы никакие две перекрывающиеся соты не использовали одну частоту. Представив частотные диапазоны разными цветами, мы можем быстро предложить одно из решений проблемы:
Конечно, многие из вас уже поняли, что это просто один из экземпляров знаменитой теоретической проблемы раскраски графа тремя цветами . Эта проблема интересна тем, что для некоторых графов сложно найти решение или даже узнать, существует ли оно. На самом деле, раскраска тремя цветами - точнее говоря, выяснение того, возможно ли раскрасить конкретный граф тремя цветами - относится к классу сложности NP .
Очевидно, что наш игрушечный пример легко решить вручную, но что если это не так? Представьте, например, что моя сотовая сеть очень велика и сложна - настолько, что вычислительных ресурсов, имеющихся в моем распоряжении, недостаточно для нахождения решения. В этом случае было бы желательно отдать проблему на аутсорсинг кому-нибудь другому, у кого вычислительных ресурсов больше. Например, я могу попросить своих друзей из Google, чтобы они решили ее для меня по спецификации.
Но это приводит к проблеме.
Предположим, что Google выделит значительную долю своей вычислительной инфраструктуры на поиск способа раскраски моего графа. Разумеется, я не собираюсь платить им, пока не узнаю, что они на самом деле нашли такой способ, но в то же время Google не собирается предоставлять мне копию решения, пока я им не заплачу. Мы оказались в тупике.
Вероятно, в реальной жизни есть житейский выход из этого тупика, включающий привлечение юристов и использование эскроу-счетов, но это блог не о реальной жизни, а о криптографии. Если вы когда-либо читали какие-либо криптоисследования, то понимаете, что правильный способ решить эту проблему - это выдумать абсолютно сумасшедшее техническое решение .
Сумасшедшее техническое решение (с шляпами!)
Заметьте, что я никогда не буду абсолютно уверен в честности Google - всегда будет хотя бы крошечная вероятность того, что Google меня обманывает. Однако после большого количества итераций (а именно E ^2 ) моя уверенность вырастет до точки, в которой вероятность обмана Google пренебрежимо мала - достаточно мала, чтобы во всех практических задачах ей можно было пренебречь. В таком случае я могу безопасно отдать Google мои деньги.
Нам необходимо знать, что Google также в безопасности. Даже если я пытаюсь узнать что-то о решении Google, сохраняя заметки между запусками протокола, это не должно иметь значения. Я в тупике из-за того, что Google рандомизирует выбор цветов в разных итерациях протокола. Ограниченная информация, которую я получаю, бесполезна, и у меня нет никакого способа связать данные разных итераций.
Что делает это «нулевым разглашением»?
Ранее я заявил, что этот протокол не допускает утечки информации о решении Google, но не позволяйте мне отделаться так легко! Первое правило современной криптографии - никогда не доверять людям , которые делают такие утверждения без доказательства.
Гольдвассер, Микали и Рекофф предложили три свойства, которым должен удовлетворять любой протокол с нулевым разглашением. Неформально их можно выразить так:
- Полнота (completeness ). Если Google говорит правду, то в итоге сможет убедить меня (по крайней мере, с высокой вероятностью).
- Корректность (soundness ). Google может убедить меня в правильности решения только в том случае, если на самом деле говорит правду.
- Нулевое разглашение (zero — knowledgeness ) . Я больше ничего не узнаю о решении Google.
Аргумент в пользу полноты мы уже обсудили. Протокол таков, что после достаточного количества повторений Google в итоге убедит меня (с пренебрежимо малой вероятностью ошибки). Продемонстрировать корректность этого протокола тоже довольно легко. Если Google когда-либо попытается обмануть меня, я почти наверняка обнаружу предательство.
Затруднения здесь вызывает третье свойство, но чтобы понять это, нам нужно провести очень странный мысленный эксперимент.
Мысленный эксперимент (с машинами времени)
Давайте начнем с сумасшедшей гипотезы. Представьте, что инженеры Google не настолько искусны, насколько кажется. Они работают над моей проблемой неделями и месяцами, но никак не могут найти решение . Когда до проверки остается 12 часов, гуглеры приходят в отчаяние. Они решают обмануть меня, чтобы я думал, что у них есть раскраска графа, хотя на самом деле ее у них нет.
Их идея состоит в том, чтобы проникнуть на семинар GoogleX и позаимствовать у Google прототип машины времени . Первоначально они планируют отправиться во времени назад на несколько лет, чтобы использовать для решения проблемы дополнительное рабочее время. К сожалению, как и большинство прототипов Google, машина времени имеет некоторые ограничения: она позволяет перемещаться во времени назад только на четыре с половиной минуты.
Таким образом, вариант с использованием машины времени для получения дополнительного рабочего времени отпадает. Тем не менее, оказывается, что даже эта очень ограниченная технология все же может быть использована с тем, чтобы обмануть меня.
Понятия не имею, что здесь происходит, но мне показалось, что картинка вполне подходит.
План чертовски прост. Поскольку Google на самом деле не знает действительной раскраски графа, Google просто раскрашивает бумагу случайными цветами, а затем поднимает шляпы. Если по чистой случайности нам попадется пара разноцветных вершин, каждый облегченно вздохнет и мы продолжим выполнять протокол. Пока все хорошо.
Однако я неизбежно рано или поздно подниму пару шляп, обнаружу две вершины одного цвета и поймаю Google на обмане. И именно здесь появляется машина времени. Когда Google находит себя в этой странной ситуации, то просто устраняет ее. Иначе говоря, специальный «гуглер» поворачивает тумблер, «перематывает» время примерно на четыре минуты и команда Google полностью перекрашивает граф новым случайным решением. После этого они снова запускают время, позволяя мне сделать новую попытку.
По сути, машина времени позволяет Google «восстанавливаться» от любых неприятностей, которые происходят во время выполнения их фальшивого протокола, из-за чего мне все кажется нормальным. Поскольку удачная попытка оспорить протокол происходит лишь примерно в 1/3 попыток, ожидаемое время выполнения протокола (с точки зрения Google) лишь умеренно больше, чем время выполнения честного протокола. Что касается меня, то я даже не подозреваю, что происходят путешествия во времени.
Последний момент наиболее важен. На самом деле с моей точки зрения незнание того, что задействована машина времени, приводит к точно такому же взаимодействию, что и реальность. Статистически они идентичны. И все же, снова стоит отметить, что в версии с машиной времени у Google совершенно нет информации о том, как раскрасить граф.
К чему это все?
То, что мы только что рассмотрели - это пример симуляции . Заметьте, что в мире, где время движется только вперед и никто не может обмануть меня с помощью машины времени, протокол со шляпами корректен , то есть после E ^2 раундов я должен быть убежден (за вычетом пренебрежимо малой вероятности), что граф на самом деле можно раскрасить и что Google располагает действительным решением.
Мы только что показали, что если время течет не только вперед - точнее говоря, если Google может «перематывать» мое представление о времени - то Google может подделать действительный запуск протокола даже без информации о фактической раскраск e графа.
Какова с моей точки зрения разница между двумя вариантами протокола? Если рассматривать их статистическое распределение, разницы нет никакой - оба сообщают примерно одинаковый объем полезной информации.
Хотите - верьте, хотите - нет, но это доказывает кое-что очень важное.
Предположим, что у меня (Проверяющего) есть некая стратегия, которая «извлекает» полезную информацию о раскраске Google после наблюдения за выполнением честного протокола. Тогда моя стратегия должна одинаково хорошо работать и в тех случаях, когда меня обманывают с помощью машины времени. С моей точки зрения запуски протокола статистически идентичны - я физически не могу определить разницу.
Таким образом, если объем информации, который я могу извлечь, в «реальном эксперименте» и «эксперименте с машиной времени» идентичен, но объем информации, которую предоставляет Google в эксперименте с «машиной времени», в точности нулевой, это предполагает, что даже в реальном мире протокол должен не выдавать никакой полезной информации. Остается только показать, что у информатиков есть машины времени. Да, у нас они есть! (Это тщательно скрываемый секрет.)
Избавляемся от шляп (и машин времени)
Конечно, на самом деле мы не хотим выполнять протокол с шляпами и даже у Google нет настоящей машины времени (наверное).
Чтобы связать все вместе, нам сначала нужно перенести наш протокол в цифровой мир. Это требует, чтобы мы сконструировали цифровой эквивалент «шляпы» - что-то, что одновременно скрывает цифровое значение и при этом «привязывает» создателя к нему («обязывает»), чтобы он не мог передумать постфактум.
К счастью, у нас есть идеальный инструмент для этого, который называется цифровой схемой обязательства . Схема обязательства позволяет одной стороне «выразить обязательство» для конкретного сообщения, сохранив его при этом в «секретном конверте», а затем позднее «раскрыть» конверт с обязательством, чтобы показать, что внутри. Обязательства можно создавать из раличных ингредиентов, включая (надежные) криптографические хеш-функции.***
Со схемой обязательства у нас есть все, что нужно для электронного выполнения протокола с нулевым разглашением. Доказывающий сначала кодирует расцветку вершин как набор цифровых сообщений (например, с помощью чисел 0, 1, 2), а затем генерирует для каждого из них цифровые обязательства. Эти обязательства пересылаются Проверяющему. Когда Проверяющий оспаривает решение для какого-то ребра, Доказывающий просто обнародует значения для обязательств, соответствующих двум вершинам.
Так мы устранили шляпы, но как доказать, что это протокол с нулевым разглашением?
К счастью, теперь мы в цифровом мире, и нам не нужна реальная машина времени для доказательства утверждений об этом протоколе. Главная хитрость в том, чтобы указать, что протокол будет работать не между людьми , а между двумя разными компьютерными программами (или, выражаясь более формальным языком, вероятностными машинами Тьюринга).
Теперь мы можем доказать следующую теорему. Если бы удалось создать компьютерную программу (для Проверяющего), извлекающую полезную информацию после участия в запуске протокола, можно было бы использовать с этой программой «машину времени», чтобы программа извлекла тот же объем полезной информации из «поддельного» запуска протокола, когда Доказывающий не предоставляет никакой информации.
И, поскольку мы теперь говорим о компьютерных программах , очевидно, что перемотка времени вовсе не является экстраординарной возможностью. На самом деле, мы перематываем компьютерные программы все время. Возьмем для примера ПО для виртуальных машин с функцией создания снимков.
Пример перемотки снимков виртуальных машин. Первоначальная виртуальная машина воспроизводится вперед, возвращается к первоначальному снимку, а затем выполняется другая ветвь.
Даже если у вас нет хитрого ПО для виртуальных машин, любую компьютерную программу можно «перемотать» к более раннему состоянию, просто снова запустив ее с начала и передав ей в точности тот же ввод. Если ввод - включая все случайные числа - фиксирован, программа всегда будет следовать по одному и тому же пути выполнения. Вы можете перемотать программу, просто запустив ее с начала и «форкнув» ее выполнение по достижении некоторой желаемой точки.
В конечном итоге мы получаем следующую теорему. Если существует какая-либо компьютерная программа Проверяющего, которая успешно извлекает информацию, интерактивно выполняя этот протокол с некоторым Доказывающим, мы можем просто использовать хитрость с перемоткой, чтобы выразить обязательство для случайного решения, а затем «обмануть» Проверяющего, перематывая программу, пока не пройдем испытание. Имеет место та же логика, что и выше: если бы такой Проверяющий преуспел в извлечении информации после выполнения реального протокола, то он мог бы извлечь тот же объем информации из симулированного протокола с перемоткой. Но поскольку симулированному протоколу не передается никакая информация, то и извлечь нечего. Следовательно, объем информации, которую Проверяющий может извлечь, равен нулю.
Хорошо, и что же все это означает?
Итак, по приведенному выше анализу мы знаем, что протокол полон и корректен. Аргумент в пользу корректности выстаивает всегда, когда мы знаем, что никто не манипулирует временем - т. е. что программа Проверяющего выполняется нормально и никто не перематывает его выполнение.
В то же время протокол обеспечивает и нулевое разглашение. Чтобы доказать это, мы показали, что любая программа Проверяющего, успешно извлекающая информацию, должна также быть способна извлечь информацию из запуска протокола с перемоткой, когда никакая информация изначально недоступна. Это приводит к очевидному противоречию и говорит нам, что утечка информации при выполнении такого протокола невозможна в обеих ситуациях.
У всего этого есть важное преимущество. Поскольку любой легко может «подделать» запись протокола даже после того как система Google докажет мне, что у нее есть решение, я не могу заново воспроизвести запись протокола, чтобы доказать что-либо кому-либо другому (скажем, судье). Это объясняется тем, что у судьи не было бы никакой гарантии, что видео было записано честно и что я не отредактировал его так же, как могла сделать система Google с помощью машины времени. Это означает, что сама запись протокола не содержит информации. Протокол имеет смысл только в том случае, если я сам участвовал в нем и уверен, что это происходило в реальном времени.
Доказательства для всех NP!
Если вы дочитали до этого места, я уверен, что вы готовы к большим новостям. А именно, вы готовы узнать, что трехцветные сотовые сети не такая уж интересная проблема - по крайней мере, сама по себе.
Проблема 3-х цветов интересна в первую очередь тем, что она относится к классу NP-полных . Выражаясь неформально, в этих проблемах удивительно то, что любую другую проблему из класса NP можно преобразовать в экземпляр этой проблемы.
Этот результат одним махом - благодаря Голдрайху , Микали и Видждерсону - доказывает, что «эффективные» доказательства с нулевым разглашением существуют для широкого класса полезных утверждений, многие из которых гораздо более интересны, чем назначение частот сотовым сетям. Вы просто находите утверждение (в классе NP), которое хотите доказать, такое как наш приведенный выше пример хеш-функции, а затем преобразуете его в экземпляр проблемы 3-х цветов. После этого вы просто запускаете цифровую версию протокола с шляпами.
Подведем итоги
Конечно, на самом деле запускать этот протокол для интересных утверждений было бы очень странно и глупо, потому что это требовало бы выполнения огромного объема работы. Теоретически это «эффективно», потому что общие затраты на доказательства росли бы полиномиально в зависимости от размера входных данных, но на практике они были бы совершенно другими.
Таким образом, мы пока показали лишь, что такие доказательства возможны . Сам же поиск доказательств, достаточно практичных для использования в реальном мире, остается на нашу долю.
В других сообщениях я расскажу о некоторых из них - а именно эффективных доказательствах разных полезных утверждений. Я приведу некоторые примеры (из реальных приложений), где такие приемы были использованы. Также по запросу одного из читателей я расскажу, почему мне так не нравится протокол SRP (Secure Remote Password).
Примечания
* Формально цель интерактивного доказательства - убедить Проверяющего, что конкретная строка принадлежит некоторому языку. Обычно Доказывающий очень (неограниченно) могуществен, а Проверяющий ограничен в вычислительных ресурсах.
** Этот пример основан на оригинальном решении Гольдвассер, Микали и Рекоффа, а обучающий пример со шляпами - на объяснении, которое дал Сильвио Микали. Я отвечаю только за ошибки, если таковые найдутся.
*** Простой пример обязательства можно построить с использованием хеш-функции. Чтобы создать обязательство для значения «x», просто сгенерируйте некоторую (достаточно длинную) строку случайных чисел, которую мы будем называть «солью» (salt), и выведите обязательство C = Hash (salt || x ) . Чтобы обнародовать обязательство, вы просто демонстрируете «x» и соль. Любой может убедиться, что оригинальное обязательство действительно, пересчитав хеш. Это безопасно, если выполнены некоторые (умеренно строгие) требования к самой функции.
Мэтью Грин (Matthew Green)
Доказательство с нулевым разглашением (знанием) (Zero-knowledge proof) представляет собой криптографический протокол, позволяющий одной из сторон (проверяющему, стороне B) убедиться в том, что вторая сторона (доказывающая, сторона A) знает какое-либо утверждение, при этом проверяющий не получает никакой другой информации о самом утверждении. Другими словами, А доказывает знание секрета, не разглашая самого секрета.
Использовать доказательства с нулевым знанием для доказательства идентичности было впервые предложено Уриелем Файгом, Амосом Фиатом и Ади Шамиром. В данном случае пользователь доказывает знание своего закрытого ключа, который в данном случае выступает в роли секрета, не раскрывая его. Таким образом, он доказывает свою идентичность.
Доказательство с нулевым разглашением обладает тремя основными свойствами:
1. Полнота. Если доказывающий знает утверждение, то он сможет убедить в этом проверяющего.
2. Корректность. Если доказывающий не знает утверждение, то он может обмануть проверяющего только с пренебрежимо малой вероятности.
3. Нулевое разглашение. Проверяющий, даже если он ведет себя нечестно, не узнает ничего кроме самого факта, что утверждение известно доказывающему.
Доказательство имеет форму интерактивного протокола. Это означает, что сторона B задает ряд вопросов доказывающему, которые если знает секрет, то ответит на все вопросы правильно. Если секрет стороне A неизвестен, но она хочет убедить в обратном проверяющего, у нее есть некоторая вероятность (может быть 50 %, как в примерах в данном топике) ответить правильно на вопрос. Однако, после некоторого количества вопросов (10 - 20) проверяющий с достаточно высокой вероятностью убеждается в том, что доказывающий не знает секрет. При этом, ни один из ответов не дает никаких сведений о самом секрете.
Пещера нулевого знания
Хорошо поясняют доказательство с нулевым знанием Жан-Жак Кискатер и Луи Гиллу с помощью истории о пещере Али-Бабы (см. рисунок). Чтобы пройти сквозь пещеру, необходимо открыть дверь между C и D. Дверь открывается только тогда, когда кто-нибудь произносит волшебные слова. Пусть Пегги знает волшебные слова и хочет доказать это Виктору, не раскрывая самих слов.Вот как происходит доказательство с нулевым знанием в данном случае:
1. Виктор находится в точке А.
2. Пегги проходит весь путь по пещере до двери либо по проходу C, либо по проходу D. Виктор не видит в какую сторону пошла Пегги. После того, как Пегги исчезнет в пещере, Виктор переходит в точку В.
3. Виктор кричит Пегги, чтобы она вышла из пещеры либо из левого прохода, либо из правого прохода.
4. Пегги, при необходимости используя волшебные слова, чтобы отпереть дверь, выходит из пещеры из того прохода, из которого просил ее выйти Виктор.
5. Пегги и Виктор повторяют этапы 1-4 некоторое количество раз.
В случае когда Пегги не знает секрета, то она не сможет обмануть Виктора, если этапы доказательства (аккредитации) повторяются несколько раз подряд. Так как она может выйти только из того прохода, в который она зашла, в каждом раунде протокола вероятность угадать, с какой стороны Виктор попросит ее выйти, составляет 50 %. Соответственно, ее вероятность обмануть Виктора также равна 50 %. Однако, вероятность обмануть его в двух раундах составит уже 25 %, а в n раундах у нее есть только один шанс из 2^n. Виктор может уверенно предположить, что если все n (n=10-20) раундов доказательства Пегги правильны, то она действительно знает тайные слова, открывающие дверь между точками С и D.
Если Виктор записывает все, что происходит на видеокамеру, то данная видеозапись не является доказательством для третьей стороны. Пегги и Виктор могли заранее договориться о том, откуда Виктор будет просить ее выйти. Тогда она будет каждый раз выходить из указанного Виктором места, не зная волшебных слов. С другой стороны, Виктор может подделать видеозапись, оставив в ней только удачные попытки Пегги, вырезав все остальное.
Следует отметить, что аналогия с пещерой не совсем верна. Так как для доказательства знания слов Пегги может просто входить с одной стороны, при этом Виктор видит в какую сторону она пошла, и выходить с другой. Однако, это протокол отлично описывает доказательство с нулевым знанием с математической точки зрения.
Протокол Фиата-Шамира
Одним из наиболее известных протоколов идентификации личности с помощью доказательства с нулевым знанием является протокол, предложенный Амосом Фиатом и Ади Шамиром, стойкость которого основывается на сложности извлечения квадратного корня по модулю достаточно большого составного числа n, факторизация которого неизвестна.Предварительно, перед самим доказательством доверенный центр T выбирает и публикует модуль достаточно большого числа n = p*q, разложить на множители которое трудно. При этом p, q – простые числа и держатся в секрете. Каждый пользователь A выбирает секретное s из интервала (1, n−1) взаимно простое с n. Затем вычисляется открытый ключ v = s^2 (mod n).
Полученное v регистрируется центром доверия в качестве открытого ключа пользователя A, а значение s является секретом A. Именно знание этого секрета s необходимо доказать A стороне В без его разглашение за t раундов. Каждая аккредитация состоит из следующих этапов:
1. А выбирает случайное r из интервала (1, n−1) и отсылает x = r^2 (mod n) стороне B.
2. B случайно выбирает бит e (0 или 1) и отсылает его A.
3. А вычисляет y = r*s^e (mod n) и отправляет его обратно к B.
4. Сторона B проверяет равенство y^2 ≡ x*v^e (mod n). Если оно верно, то происходит переход к следующему раунду протокола, иначе доказательство не принимается.
Выбор е из множества предполагает, что если сторона А действительно знает секрет, то она всегда сможет правильно ответить, вне зависимости от выбранного e. Допустим, что А хочет обмануть B, выбирает случайное r и отсылает x = r^2 / v, тогда если е=0, то А удачно возвращает B y = r, в случае же е=1, А не сможет правильно ответить, т.к. не знает s, а извлечь квадратный корень из v по модулю n достаточно сложно.
Вероятность того, что пользователь А не знает секрета s, но убеждает в обратном проверяющего B будет оцениваться вероятностью равной p = =2^(–t), где t – число аккредитаций. Для достижения высокой достоверности его выбирают достаточно большим (t = 20 − 40). Таким образом, B удостоверяется в знании А тогда и только тогда, когда все t раундов прошли успешно.
Для того чтобы этот протокол корректно выполнялся, сторона А никогда не должна повторно использовать значение x. Если бы А поступил таким образом, а B во время другого цикла отправил бы А на шаге 2 другой случайный бит r, то B бы имел оба ответа А. После этого B может вычислить значение s, и ему будет известен секретный ключ Алисы.
