Обеспечение авторификации [14]
Как дополнительное расширение будущей сети предлагается усовершенствовать её при помощи возможности авторификации пользователей сети, из-за аппаратной сложности реализации подобных алгоритмов предлагается использовать специальное программное обеспечение, а именно, алгоритма “доказательств с нулевым знанием”(ZKP)
Метод ZKP основан на том, что проверяющий знает всегда только половину информации. Конечно, при таком условии нельзя быть уверенным в том, что человек тот за кого он себя выдает. Но проверяющий каждый раз может спросить любую часть информации, причем несколько раз.
Рассмотрим данный метод на примере графов. Граф – конечная совокупность точек, называемых вершинами; некоторые из них соединены друг с другом линиями, называемыми ребрами графа. Простейший вид графа – это города соединенные дорогами на карте.
У некоторых графов есть гамильтонов цикл – это способ соединения всех вершин графа одной кривой, проходящий по его ребрам и не проходящий через одну вершину дважды. Допустим, проверяющему показали гамильтонов цикл графа, но он не знает от какой точки к какой идти, если проверяющий убедился в том, что у проверяемого нужный граф, то он не видит гамильтонов цикл, так как у графа изменились координаты точек.
Каждый вопрос будет понижать шансы на случайный ответ. Сначала, вероятность угадать, равна 1/2, потом 1/4 и через сто вопросов вероятность упадет до 1/2100. Если человек не знает правильного графа и гамильтонова цикла, то ему будет практически невозможно ответить на все вопросы ни разу не ошибавшись, а проверка заканчивается при первой же ошибке.
Как происходит проверка? Допустим, некоторый компьютер (А) устанавливает подлинность представления удалённого компьютера (Б). У компьютера Б есть граф, для которого ему известен гамильтонов цикл.
Сначала компьютер Б посылает граф, который получился из проверочного случайным переименованием вершин. Компьютер А случайным образом выбирает, какую информацию он хочет проверить, совпадение этого графа с тем, что у него есть, или известность компьютеру Б гамильтонова цикла для этого графа. Предположим, что компьютер б хочет убедиться в совпадении этого графа с тем, что есть у него и посылает об этом сообщение компьютеру Б, компьютер Б в свою очередь посылает компьютеру А информацию о том, каким образом надо переименовать вершины графа, чтобы получился исходный. Если подобное преобразование действительно переведет граф в исходный, то компьютер А считает, что на этот вопрос он получил правильный ответ и продолжает проверку.
Далее компьютер Б снова посылает граф, на этот раз, переименовав вершины по-другому (случайным образом). Пусть в этот раз компьютер А выбрал, что хочет узнать гамильтонов цикл, тогда компьютер Б посылает последовательность имен вершин, которая в измененном графе действительно является гамильтоновым циклом. Таким образом, после некоторого числа подобных шагов, компьютер А убеждается, что компьютер Б действительно тот, за которого себя выдаёт, отметим, что при этом компьютер А не сможет сам представится компьютером Б, ведь он так и не узнал гамильтонова цикла для исходного графа, а гамильтонов цикл найти для граф с десятью вершинами уже не просто, а если у графа 100 вершин то это уже почти невозможно. А если вершин 1000, то подбор гамильтонова цикла на современном компьютере займет несколько сотен лет.
Как же генерируются проверочные графы? Пусть в начале есть граф на 1000 вершин, где n-ая вершина соединена с n+1, а 1000 с 1, теперь случайным образом переименуем вершины, и запомним теперь для этого графа гамильтонов цикл далее для каждой пары вершин с вероятностью 34% будем соединять ребром, в конце данной процедуры получим граф, для которого мы знаем цикл и в то же время, найти его кем-то другим не представляется возможным.
Чтобы показать вам всю сложность нахождения гамильтонова цикла рассмотрим граф из семи точек, приведенный на рисунке ниже. Если попытаться самому придумать гамильтонов цикл, то на это уйдет от 30 минут до нескольких часов.