Защита информации в корпоративных ГИС

[believer]

Посмотрев статью http://www.ict.nsc.ru/ws/YM2002/4415/ , остались неясными следующие её части:

1. «Все точки искаженной карты, задающие положение объектов на ней, попадающие в некоторый треугольник искаженной триангуляции, ЛИНЕЙНОЙ ИНТЕРПОЛЯЦИЕЙ переносятся в соответствующий треугольник исходной триангуляции.»
2. «…процесс искажения карты отличается от процесса её восстановления заменой исходной триангуляции на искаженную и вектора смещения на противоположный. Это возможно потому что используемое преобразование является КУСОЧНО-ЛИНЕЙНЫМ. Даже если несанкционированному пользователю известен алгоритм искажения и истинные координаты некоторых искажённых точек, он не сможет восстановить все параметры кусочно-линейного преобразования, т.к. их нельзя однозначно определить по множеству примеров приемлемого размера.»

Кто-нибудь может детально прокомментировать эти части статьи и рассказать несколько слов о триангуляции Делона применительно к данной статье? Заранее благодарен.

[Максим Дубинин]

Почему автор называет это линейной интерполяцией не очень понятно, ведь речь явно идет о той или иной модели геометрической трансформации.

1. есть исходный треугольник, есть конечный, по упомянутым "свойствами триангуляции", как я понимаю например по площади, периметру, еще чему-нибудь, вычисляется набор параметров и аффинной трансформацией узлы в исходном треугольнике переносятся в новый треугольник.

2. Так как все исходные треугольники в триангуляции Делоне разные, то и получается, что двигаются данные на разные величины (кусочная-линейность). Если треугольников достаточно много, то зная десяток истинных точек, вычислить обратную трансформацию и перенести можно их окрестности, но для всей карты это не поможет.

[believer]

1. есть исходный треугольник, есть конечный, по упомянутым "свойствами триангуляции", как я понимаю например по площади, периметру, еще чему-нибудь, вычисляется набор параметров и аффинной трансформацией узлы в исходном треугольнике переносятся в новый треугольник.

Интересен момент, как определяется новое место точечного объекта карты в конечном треугольнике, зная его расположение в исходном треугольнике, ведь исходный и конечный треугольники получаются разными? Если они одинаковы, то вопрос отпадает.

2. Так как все исходные треугольники в триангуляции Делоне разные, то и получается, что сдвигаются данные на разные величины (кусочная-линейность). Если треугольников достаточно много, то зная десяток истинных точек, вычислить обратную трансформацию и перенести можно их окрестности, но для всей карты это не поможет.

Полагаю, что при внесении искажений в метрику на третьем шаге алгоритма в каждой вершине триангуляции вычисляется псевдослучайный вектор смещения на основе пароля, задающий генератор псевдослучайной последовательности (ГПСЧ). Правильно ли я понял?
С учетом ответа Sim соглашусь с тем, что «если несанкционированному пользователю известен алгоритм искажения и истинные координаты некоторых искажённых точек, он не сможет восстановить все параметры кусочно-линейного преобразования». Но автор не учел следующего. Если несанкционированному пользователю известен алгоритм искажения и истинные координаты некоторых искажённых точек, то он сможет восстановить некоторую часть псевдослучайной последовательности, попытаться по ней вычислить начальный вектор состояния ГПСЧ и сгенерировать нужную псевдослучайную последовательность, что практически равнозначно выявлению правильного пароля. Согласны с этим?

[Максим Дубинин]

не думаю что одинаковы, говорит же автор, что:

В каждой вершине триангуляции вычисляется псевдослучайный вектор смещения

Если каждую вершину трансформировать по разному, получится другой треугольник. Коэффициенты определяются "свойствами триангуляции в данной точке", какими именно надо смотреть. После того как новый треугольник получен, по старым и новым 3 точкам можно легко рассчитать коэф-ты для аффинной трансформации и пересчитать все точки попадающие в старый треугольник.

Насчет того где там пароль, я из текста понял, что он при генерации случайных точек используется, на основе которых потом триангуляция строится, но наверное резонно и для этих "псевдослучайных векторов смещения" его использовать, хотя это не написано.

[believer]

То есть точечные объекты картографии внутри старого треугольника переносятся внутрь нового треугольника на основе коэффициентов аффинной трансформации. Верно?

[Максим Дубинин]

да, это то как я понял, только не точечные объекты, а узлы, которые могут принадлежать и точкам и линиям и полигонам.

[andreichernov]

Почему автор называет это линейной интерполяцией не очень понятно, ведь речь явно идет о той или иной модели геометрической трансформации

1. есть исходный треугольник, есть конечный, по упомянутым "свойствами триангуляции", как я понимаю например по площади, периметру, еще чему-нибудь, вычисляется набор параметров и аффинной трансформацией узлы в исходном треугольнике переносятся в новый треугольник.

Автор правильно говорит, что локальное преобразование треугольника в треугольник является линейным.
А все преобразование - соответственно кусочно-линейным

Если заданы три точки с координатами исходные и три точки с координатами результирующие (полученные псевдослучайным смещением), то можно подобрать параметры линефного преобразования, переводящего одни в другие (6 параметров аффинного преобразования - 6 уравнений, по 2 на каждую точку).
То есть параметры вычисляются не по площади-периметру, а непосредственно по координатам. Мы делали такую штуку.

Но автор не учел следующего. Если несанкционированному пользователю известен алгоритм искажения и истинные координаты некоторых искажённых точек, то он сможет восстановить некоторую часть псевдослучайной последовательности, попытаться по ней вычислить начальный вектор состояния ГПСЧ и сгенерировать нужную псевдослучайную последовательность, что практически равнозначно выявлению правильного пароля. Согласны с этим?

Нет, не согласен. По фрагменту псевдослучайной последовательности вычислить ее генератор вычислительно невозможно за приемлемое время, если генератор хороший. На этом стоит вся криптография.

да, это то как я понял, только не точечные объекты, а узлы, которые могут принадлежать и точкам и линиям и полигонам.

Вот именно. Из-за этого прямоугольный дом после такой трансформации может стать непрямоугольным и вообще появиться "изломы" на ребрах триангуляции.

[Максим Дубинин]

автор назвал это "линейной интерполяцией", а не трансформацией, я этому удивился, странное применение термину интерполяция.

[believer]

Andreichernov, спасибо за ответ. А какой конкретно из криптостойких ГПСЧ посоветуете для такого механизма защиты? И как считаете, какими недостатками обладает данный подход к защите?

[andreichernov]

Andreichernov, спасибо за ответ. А какой конкретно из криптостойких ГПСЧ посоветуете для такого механизма защиты? И как считаете, какими недостатками обладает данный подход к защите?

ГПСЧ - я сам не занимался этим. Если очень надо - спрошу. У меня отец профессионально этим занимается, но там они какие-то свои хитрые ГПСЧ делают. Но подозреваю, что можно любой.

Недостатки метода
а) координаты объектов сильно меняются. Если менять их несильно, то и такая карта пойдет.
ну условно случайные смещения должны быть около 1 мм в масштабе плана по амплитуде.
б) если уж использовать, то я бы не разбрасывал исходные точки псевдослучайно.
Они могут организовать маленькие или узкие треугольники, а значит после смещений - дать большие искажения или вообще вывернуть треугольники наизнанку.
я бы эти точки взял "по одной на ячейку крупной сетки" и между ячейками сетки оставил бы пространство , куда точки не падали б.

P.S. Я недавно написал на блоге http://blog.geosamara.ru/?p=103 - там про стеганографию - это немного не то (Вам надо исказить карту глобально, а там вводятся точечные метки), но может Вам будет интересно.

Sim, про линейную интерполяцию - да я не заметил.

[believer]

Андрей, не могли бы Вы попросить отца выслать мне на почту landwatersun@mail.ru программно реализованные (на языках C/C++) криптостойкие ГПСЧ (например, основанные на блочных шифрах). Заранее благодарен.

[andreichernov]

Он в отпуске не здесь. Я тоже уезжаю. Так что даже спросить не смогу в ближ время.