Система и способ кодирования произвольно распределенных признаков в объекте

Система и способ кодирования произвольно распределенных признаков в объекте

Иллюстрации

Показать все

Реферат

Область техники, к которой относится изобретение

Описанные здесь системы и способы, в целом, относятся к ярлыкам, защищенным от подделки и/или защищенным от незаконного изменения, и, в частности, для использования произвольно распределенных признаков объекта (внедренных или собственных) для ограничения несанкционированных попыток подделки или подлога с помощью ярлыка.

Уровень техники

Подделка и незаконное изменение ярлыков стоят торговцам и товаропроизводителям миллиардов долларов ежегодной потери прибыли и потери потребителей. С распространением компьютерной технологии изготовление ярлыков, похожих на оригинальное изделие, упростилось. Например, можно использовать сканер для сканирования изображения оригинального ярлыка с высоким разрешением, после чего можно неоднократно воспроизводить его с минимальными затратами. Кроме того, купоны можно сканировать, изменять (например, в сторону увеличения ценности), повторно печатать и погашать.

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

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

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

Соответственно, современные решения не могут обеспечивать ярлыки, которые относительно трудно скопировать и недорого производить.

Раскрытие изобретения

Описанные здесь системы и способы направлены на кодирование произвольно распределенных признаков в объекте. Согласно одному аспекту, определяют произвольно распределенные признаки в объекте аутентификации. Данные, представляющие произвольно распределенные признаки, сжимают и кодируют с помощью подписи. Создают ярлык, содержащий объект аутентификации и кодированные данные.

Согласно другому аспекту, данные сжимают, определяя функцию плотности вероятности, связанную с объектом аутентификации. Векторы, связанные с произвольно распределенными атрибутами, определяют на основании, по меньшей мере частично, функции плотности вероятности. Векторы кодируют с использованием алгоритма арифметического кодирования.

Краткое описание чертежей

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

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

Фиг.3А - схема иллюстративной системы сканирования для восприятия произвольно распределенных признаков объекта аутентификации, связанного с сертификатом подлинности.

Фиг.3В - вид сверху объекта аутентификации, показанного на фиг.3А.

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

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

Фиг.6 - графическое представление областей, которые соответствуют четырем различным зонам в иллюстративном объекте аутентификации.

Фиг.7 - графическое представление девятнадцати разных зон иллюстративного объекта аутентификации.

Фиг.8 - график иллюстративной функции плотности вероятности для квадратного объекта аутентификации.

Фиг.9 - графическое представление областей в объекте аутентификации.

Фиг.10 - графическое представление, иллюстрирующее, как арифметический кодер кодирует строку "aba".

Фиг.11 - пример экземпляра объекта аутентификации, показанного с помощью узлов.

Фиг.12 - графическое представление сертификата подлинности, предназначенного для оптимизации эффективности затрат.

Фиг.13 - схема иллюстративного вычислительного устройства, которое можно полностью или частично реализовать посредством описанных систем и способов.

Осуществление изобретения

I. Введение

Описанные здесь системы и способы направлены на кодирование информации о произвольно распределенных признаках объекта, используемого в качестве ярлыка. Ярлыки могут включать в себя средства идентификации любого типа, присоединяемые к изделию или встраиваемые в него. Ярлык, который можно аутентифицировать, называется здесь сертификатом подлинности. Объект с произвольно распределенными признаками, используемый в сертификате подлинности, называется здесь объектом аутентификации. Чтобы обеспечить самоаутентификацию, сертификат подлинности может включать в себя как объект аутентификации, так и информацию о произвольно распределенных признаках. Метод сжатия можно использовать для увеличения объема информации о произвольно распределенных признаках, которую можно кодировать и включать в сертификат подлинности. Согласно одному вычислению, стоимость горячей штамповки сертификата подлинности экспоненциально возрастает пропорционально повышению степени сжатия информации. Это существенное увеличение стоимости горячей штамповки обеспечивает надежный сертификат подлинности, который относительно дешево изготовить, но трудно фальсифицировать.

На фиг.1 показан пример объекта 100 аутентификации для использования как части ярлыка, например, сертификата подлинности. Для эффективного использования в сертификате подлинности объект 100 аутентификации обычно содержит произвольно распределенные признаки, которые являются уникальными и которые трудно копировать. Пример объекта 100 аутентификации, показанный на фиг.1, является частью сертификата подлинности на основе волокон и содержит волокна 110, внедренные в объект произвольным образом. Волокна 110 выступают в качестве произвольно распределенных признаков объекта 100 аутентификации. Волокна 110 могут быть включены в объект 100 аутентификации любыми средствами. Например, волокна 110 можно распылять на объект 100 аутентификации. Волокна 110 можно также внедрять в объект 100 аутентификации в процессе изготовления. Согласно одному варианту осуществления, волокна 110 являются оптическими волокнами, способными пропускать свет между своими концами. Таким образом, облучая светом определенную зону 120 объекта 100 аутентификации, освещают концы волокон 131-133, по меньшей мере, один конец которых находится в освещенной зоне.

Согласно фиг.1, объект 100 аутентификации содержит κ произвольно распределенных волокон. Объект 100 аутентификации можно сканировать с разрешением L×L пикселей. Каждое волокно имеет фиксированную длину R. Хотя иллюстративный объект 100 аутентификации, показанный на фиг.1, содержит волокна, следует понимать, что в сертификате подлинности аналогично можно использовать объекты аутентификации с другими произвольно распределенными признаками.

Произвольно распределенные признаки объекта 100 аутентификации можно использовать в сертификате подлинности для защиты доказательства подлинности произвольного объекта, например изделия. Например, определенные труднодублируемые данные вокруг произвольно распределенных признаков сертификата подлинности могут быть оцифрованы, подписаны личным ключом блока издания, и подпись может быть отпечатана на сертификате подлинности в машиносчитываемом виде для подтверждения подлинности изготовленного экземпляра. Каждый экземпляр сертификата подлинности связан с объектом, подлинность которого хочет проверить блок издания. Согласно одному варианту осуществления, проверка подлинности производится, осуществляется путем извлечения подписанных данных (данных о произвольно распределенных признаках) с использованием общего ключа блока издания и проверки совпадения извлеченных данных с данными соответствующего экземпляра сертификата подлинности. Чтобы подделать защищенные объекты, противнику необходимо по выбору: (i) вычислить личный ключ блока издания, (ii) разработать процесс изготовления, который может точно дублировать уже подписанный экземпляр сертификата подлинности, и (iii) завладеть подписанными экземплярами сертификата подлинности. С этой точки зрения сертификат подлинности можно использовать для защиты изделий, ценность которых, в целом, не превышает стоимость горячей штамповки одного экземпляра сертификата подлинности, включая накопленное развитие успешного процесса соперничающего изготовления.

Цель системы сертификата подлинности состоит в том, чтобы гарантировать подлинность изделий или определенной информации, связанной с изделием. Сфера применения очень широка, от борьбы с пиратством программного обеспечения и мультимедиа (например, DVD, CD) до негорячештампованных купонов и разработки оборудования, защищенного от подделки. Например, создание чипа, защищенного от подделки, требует покрытия его корпуса сертификатом подлинности. Перед каждым использованием следует проверить целостность сертификата подлинности, чтобы проверить подлинность защищенной микросхемы.

Ниже будут рассмотрены иллюстративные аппаратные платформы для недорогого, но эффективного считывания произвольно распределенных признаков сертификата подлинности на основе волокон. Аппаратные платформы могут включать в себя штрих-код. Поскольку емкость штрих-кода для недорогих устройств считывания ограничивается примерно 3 кбитами, сообщение, подписанное личным ключом, ограничивается той же длиной. Кроме того, поскольку одной из целей сертификата подлинности является максимизация усилий противника, нацеленных на горячую штамповку конкретного экземпляра и сертификата подлинности, будет рассмотрена проблема, связанная с сохранением в подписанном сообщении фиксированной длины как можно большего объема информации об уникальных и произвольно распределенных признаках сертификата подлинности на основе волокон. Будет предоставлен пример аналитической модели сертификата подлинности на основе волокон. Затем в нижеследующем рассмотрении проблема сжатия множества точек будет также формализована и будет показано, что оптимальное сжатие позиций волокон в экземпляре сертификата подлинности является NP-полной задачей. Для эвристического решения этой задачи будет обеспечен алгоритм, который значительно повышает отношения сжатия по сравнению с традиционными методами сжатия.

II. Издание и проверка сертификата подлинности

На фиг.2 показана схема, демонстрирующая иллюстративную систему 200 сертификата подлинности и иллюстративные процедуры, используемые системой для издания и проверки сертификата подлинности. Система 200 сертификата подлинности включает в себя сертификат 210 подлинности, блок 320 издания и блок 250 проверки. Согласно фиг.2, сертификат 210 подлинности может содержать объект 100 аутентификации, показанный на фиг.1, штрих-код 213 и текст 215.

Информация, которую нужно защищать на сертификате подлинности, включает в себя: (а) представление труднодублируемых произвольно распределенных признаков объекта 100 аутентификации и (b) связанные с ним произвольные текстовые данные. Сначала произвольно распределенные признаки объекта 100 аутентификации, например позиции волокон, сканируют с использованием аппаратного устройства. Ниже со ссылкой на фиг.3 мы подробно рассмотрим, как собирают и представляют эту информацию.

В целях рассмотрения предположим, что результирующая информация f является случайной строкой из n_F битов. Параметр n_F является фиксированным и равен n_F =k·n_RSA, k∈N, где n_RSA - это длина общего ключа RSA (например, n_RSA = 1024), и k обычно задано как k ∈ [1,3]. При данном n_F собрание f данных 231, представляющее произвольно распределенные признаки объекта 100 аутентификации, может статистически максимизировать расстояние между двумя различными экземплярами сертификата подлинности. Эта задача непосредственно сводится к минимизированному правдоподобию ложного отрицательного результата и ложного положительного результата на этапе проверки.

Текстовые данные f являются произвольной строкой символов, которая зависит от приложения (например, срока годности, гарантии производителя). Текстовые данные извлекаются из текста 215, напечатанного на сертификате 210 подлинности, как показано на фиг.2.

Текстовые данные можно хэшировать с использованием криптографически защищенного алгоритма 237 хэширования, например SHA1. Выход хэш-функции обозначается как сообщение t, состоящее из n_T битов. Блок 230 издания создает сообщение m, которое может быть подписано RSA. Например, сообщения f и t сливаются в сообщение m длиной n_M = n_F с использованием обратимого оператора ⊗, который гарантирует, что каждый бит из m зависит от всех битов из f и t. Этот этап может максимизировать число битов, которыми нужно манипулировать в данных 231, а также в тексте 215 для создания определенного сообщения m. Примером такого оператора является симметричное шифрование m = t ⊗ f = E_t(f) для f с использованием t или определенного подмножества битов из t в качестве ключа. Сообщение m подписывается подписью 235 RSA с использованием личного ключа 233 блока 230 издания. Каждые n_RSA битов из m подписываются по отдельности. Результирующая подпись s имеет n_S = n_M = n_F битов. Это сообщение кодируется и печатается как штрих-код 213 (например, штрих-код по стандарту PDF417) на сертификате 210 подлинности.

Проверка сертификата 210 подлинности производится в несколько этапов. Блок 250 проверки сначала сканирует отпечатанные компоненты: текст 215 и штрих-код 213. Штрих-код 213 декодируют в первоначально отпечатанную подпись s. Текст 215 сканируют и хэшируют для создания сообщения t. Заметим, что для этой задачи не требуется общий процесс оптического распознавания символов (OCR), поскольку шрифт, используемый для печати текста, известен блоку 250 проверки и оптимизирован для усовершенствованного OCR. Для успешной проверки сертификата подлинности текст 215 и штрих-код 213 должны быть считаны без ошибок; современные технологии сканирования позволяют легко выполнить эту задачу.

Блок 250 проверки осуществляет проверку 255 подписи RSA на s с использованием общего ключа 253 блока издания и получает подписанное сообщение m. Затем блок 250 проверки может вычислить f=m(⊗)^-1t. В примере использования шифрования в качестве ⊗ это достигается дешифрованием f=E_t ^-1(m). Затем блок 250 проверки сканирует данные 251, представляющие произвольно распределенные признаки в объекте 100 аутентификации, и создает их представление f'. Блок 250 проверки сравнивает f' с извлеченным f. Блоку 250 проверки нужно определить величину корреляции между двумя множествами данных: одним - присоединенным к сертификату, и другим - используемым для создания подписи на сертификате подлинности. На блоке 259 принятия решения, если уровень подобия двух множеств данных превосходит некоторый порог, то блок 250 проверки объявляет, что этот сертификат 210 подлинности подлинный, и наоборот.

На фиг.3А показана схема иллюстративной системы 300 сканирования для восприятия произвольно распределенных признаков объекта 310 аутентификации, связанных с сертификатом подлинности. Система 300 сканирования содержит оптический датчик 322 и источник 324 света. Оптический датчик 322 способен сканировать объект 310 аутентификации и может содержать матрицу устройств с зарядовой связью (ПЗС) с конкретным разрешением. Согласно одному варианту осуществления, оптический датчик 322 имеет разрешение 128×128 пикселей. Источник 324 света способен обеспечивать свет определенной длины волны для освещения зоны аутентификации объекта 310. Источник 324 света может включать в себя, например, светодиод (СИД). Согласно фиг.3А, один конец волокна 326 объекта 310 аутентификации освещается источником 324 света. Свет проходит к другому концу волокна 326 и воспринимается оптическим датчиком 322.

На фиг.3В показан вид сверху объекта 310 аутентификации, показанного на фиг.3А. В ходе работы система 300 сканирования делит объект 310 аутентификации на зоны, например зоны 311-314. Согласно фиг.3В, источник 324 света системы 300 сканирования излучает свет на зону 314, тогда как зоны 311-313 изолированы от источника 324 света. Благодаря освещению зоны 314 оптический датчик 322 может определить местоположение концевых точек в зонах 311-313 объекта 310 аутентификации. Таким образом, считывание произвольно распределенных признаков в объекте 310 аутентификации включает в себя четыре цифровых изображения, которые содержат четыре разных множеств точек. Каждое множество точек связано с конкретной зоной и определяется путем освещения этой зоны.

Возможно, что развитие технологии, например нанотехнологии, позволяет с помощью электронного устройства декодировать произвольно распределенные признаки из сертификата подлинности и создать световую картину, соответствующую этим признакам. Такое устройство может иметь возможность осуществлять горячую штамповку сертификата подлинности. Согласно одному варианту осуществления, система 300 сканирования может иметь возможность препятствовать этому способу горячей штамповки путем изменения длины волны (т.е. цвета) света, используемого источником 324 света. Например, длину волны света можно случайным образом выбирать каждый раз при сканировании объекта аутентификации системой 300 сканирования. Оптический датчик 322 может иметь возможность обнаруживать длину волны света, излучаемого волокнами объекта аутентификации, и определять, соответствует ли эта длина волны длине волны света, излучаемой источником 324 света. Если длины волны излученного и обнаруженного света не совпадают, то сертификат подлинности, скорее всего, является поддельным.

На фиг.4 показана логическая блок-схема иллюстративного процесса 400, который можно использовать для создания сертификата подлинности. В блоке 405 сканируют объект аутентификации в сертификате подлинности. Объект аутентификации можно сканировать с использованием системы 300, показанной на фиг.3А.

В блоке 410 определяют данные, представляющие произвольно распределенные атрибуты объекта аутентификации. В объекте аутентификации на основе волокон данные могут включать в себя позиции концевых точек освещенных волокон, например концевых точек, показанных на фиг.3В.

В блоке 415 данные сжимают, чтобы повысить уровень защиты сертификата подлинности. Сжатие данных будет подробно рассмотрено со ссылкой на фиг.5. В общих чертах можно определить путь для сжатия части данных, представляющих произвольно распределенные атрибуты объекта аутентификации.

В блоке 420 кодируют сжатые данные. Например, сжатые данные можно подписывать с использованием личного ключа 233, показанного на фиг.2. В блоке 425 кодированные данные включают в сертификат подлинности. Например, кодированные данные можно напечатать в сертификат подлинности в виде штрих-кода, например штрих-кода 213, показанного на фиг.2.

На фиг.5 показана логическая блок-схема иллюстративного процесса 500, который можно использовать для сжатия данных, которые представляют произвольно распределенные атрибуты объекта аутентификации. В целях рассмотрения процесс 500 будет описан применительно к сертификату подлинности на основе волокон. Однако процесс 500 можно применять к сертификату подлинности любого типа.

В блоке 505 определяют функцию плотности вероятности, связанную с объектом аутентификации. Функция плотности вероятности будет рассмотрена в разделе III-A. Функция плотности вероятности показана в уравнении 11. На фиг.8 показано графическое представление иллюстративной функции плотности вероятности. В общих чертах функция плотности вероятности выражает вероятность того, что единица произвольно распределенных атрибутов находится в определенном месте объекта аутентификации. Применительно к сертификату подлинности на основе волокон функция распределения вероятности может выражать вероятность того, что конкретная точка в зоне объекта аутентификации освещена. Функцию плотности вероятности также можно использовать для вычисления количества волокон, освещаемых в конкретной зоне.

В блоке 510 определяют векторы, связанные с произвольно распределенными атрибутами. Применительно к сертификату подлинности на основе волокон используются двухточечные векторы, и это будет рассмотрено в разделе IV-A. В частности, уравнение 16 можно использовать для вычисления двухточечных векторов для выражения произвольно распределенных атрибутов в сертификате подлинности на основе волокон.

В блоке 515 векторы кодируют с использованием алгоритма арифметического кодирования. Алгоритм арифметического кодирования будет рассмотрен в разделе IV-A. Иллюстративный алгоритм показан в таблице 2.

В блоке 520 определяют путь для сжатия части векторов в фиксированном объеме данных. Способ вычисления пути рассмотрен в разделе IV-B. Иллюстративный путь можно вычислить с использованием уравнения 20. В блоке 525 возвращают путь сжатых данных, выражающий часть произвольно распределенных атрибутов.

III. Модель сертификата подлинности

В этом разделе рассматривается аналитическая модель сертификата подлинности на основе волокон. Смоделированы два признака сертификата подлинности S. Исходя из того, что освещена конкретная зона S_i сертификата подлинности, вычисляют функцию плотности вероятности освещения конкретной точки в S-S_i. Кроме того, исходя из того, что в S находится К волокон, вычисляют ожидаемое количество волокон, освещаемых в S-S_i.

А. Распределение освещенных концевых точек волокон

Объект (L,R,K) аутентификации моделируется как квадрат со стороной L единиц и К волокнами фиксированной длины R ≤ L/2, произвольно разбросанных по объекту. Из этой модели можно вывести другие варианты модели, например объект с переменной длиной волокна или объект произвольной формы. Объекты аутентификации располагаются в положительном квадранте двухмерной прямоугольной системы координат, как показано на фиг.1. Кроме того, объект аутентификации делят на четыре равных квадрата S={S₁,S₂,S₃,S₄}. Затем каждый из них используют для записи трехмерной структуры волокон, как описано выше со ссылкой на фиг. 3А и 3В. Затем волокно обозначают как упорядоченную пару f={A,B} точек A,B⊂S, причем расстояние между ними .

Определение 1. Распределение освещенных концевых точек волокон

Пусть один из квадратов S_i освещен, тогда функция плотности вероятности (ФПВ) φ(i,Q(x,y)) определяется для любой точки Q(x,y) ⊂ S-S_i через вероятность ξ(i,P) того, что область P⊂S-S_i содержит освещенную концевую точку А волокна f={A,B} при условии, что другая концевая точка В располагается в освещенной зоне S_i. Более формально для любой P ⊂ S - S_i

Предположим, что бросание волокна f={A,B} в объект аутентификации состоит из двух зависимых событий: (i) первая концевая точка А попадает в объект аутентификации, и (ii) вторая концевая точка В достигает объекта аутентификации. Хотя А может попасть в любое место СП (сертификата подлинности), позиция В зависит от местоположения А. Концевая точка В должна попасть на часть периметра круга с центром в А и радиусом R и содержащегося в объекте аутентификации. В оставшейся части этой подобласти функцию φ(i,Q(x,y)) аналитически вычисляют на основании анализа событий (i-ii). Для краткости для случая, когда освещена зона S₁, вычисляется только φ(1,Q(x,y)). φ(1,Q(x,y)) вычисляется в два этапа.

Определение 2. Ограничение периметра

Во-первых, для данной точки A ⊂ S определяют функцию ρ(A), которая выражает длину части периметра (дуги) круга с центром в А и радиусом R, который целиком заключен в объекте S аутентификации. В объекте аутентификации имеется четыре разных зоны (обозначенные P1-P4 на фиг.6), где ρ(A) однородно вычисляется.

На фиг.6 изображено графическое представление областей P1-P4, соответствующих четырем различным зонам в иллюстративном объекте 600 аутентификации. Для каждой точки в определенной области Рх вычисляют функцию ограничения периметра с использованием замкнутой аналитической формы, характерной для этой области, с использованием уравнений 7-10, которые рассмотрены ниже.

Область Р1

Это центральная область объекта аутентификации, где для любой точки Q ⊂ P1 окружность радиуса R с центром в Q не пересекается ни с какими сторонами объекта аутентификации. Границы области заданы следующим образом: R ≤ x ≤ L-R, R ≤ y ≤L-R.

ρ(Q(x,y))=2Rπ.

(7)

Область Р2

Имеется четыре разных зоны Р2, где окружность радиуса R с центром в любой точке Q ⊂ P2 дважды пересекается с одной и той же стороной объекта аутентификации. Для краткости рассмотрим только следующий случай:

R ≤x ≤ L-R, 0 ≤ y<R. Уравнения для трех других зон можно вычислить симметрично.

(8)

Область Р3

Имеется четыре разных зоны Р3, где окружность радиуса R с центром в любой точке Q ⊂ P3 дважды пересекается с двумя разными сторонами объекта аутентификации. Рассмотрим только следующий случай: 0 ≤ x < R, 0 ≤ y < R,

x² + y² ≥ R².

Область Р4

Имеется четыре разных зоны Р3, где окружность радиуса R с центром в любой точке Q ⊂ P4 по одному разу пересекается с двумя краями СП. Рассмотрим только следующий случай: x² +y² < R².

Во всех уравнениях 8-10 фактическая φ(1,Q(x,y)) вычисляется исходя из того, что освещенная концевая точка А волокна f={A,B} находится в позиции A=Q(x,y), только если В находится на части(ях) окружности C(Q,R) с центром в Q(x,y) с диаметром R и содержащейся в S₁.

Лемма 3. Зависимость φ(i,Q(x,y)) от ρ(Q(x,y)).

Используя функцию ρ(Q(x,y)), вычисляют ФПВ φ(i,Q(x, y)) с использованием следующего интеграла:

где ϑ описывает периметр C(Q,R)⊂S и α является константой, так что:

(12)

Точка Q⊂S-S_i может быть освещена только благодаря волокну f={Q,B}, так что

B⊂S_i. Отсюда следует, что В расположена где-то на периметре круга C(Q, R), содержащегося в S_i. Для данного волокна f={A,B} вероятность того, что А лежит на конкретной бесконечно малой дуге длиной dl⊂S, равна dl/ρ(B). Следовательно:

где функция area(S-S_i) вычисляет площадь под S-S_i. Таким образом, ФПВ φ(1,Q(x,y)) в точке Q⊂S-S₁ пропорциональна интегралу от величины, обратной ρ(•), по C(Q,R)⊂S₁.

На фиг.7 показано графическое представление девятнадцати различных зон иллюстративного объекта 700 аутентификации, которые имеют характерные аналитические формулы в качестве решения интеграла, приведенного в уравнении 11. Для простоты φ(1,Q(x,y)) приблизительно решается с использованием простого численного расчета. Результаты приведены на фиг.8.

На фиг.8 показан график иллюстративной функции плотности вероятности для квадратного объекта аутентификации с параметрами L=64 и R=28, дискретизированной в единичных точках. На фиг.8 показано, что вероятность того, что концевая точка волокна лежит в определенной малой области P⊂S-S_i, значительно изменяется в зависимости от конкретного положения Р в S-S_i. Используя информацию об изменении φ(i,Q(x,y)) в пределах S-S_i, можно значительно усовершенствовать алгоритмы сжатия подмножества точек, что представлено в разделе IV. Изготовление объекта аутентификации, характеризуемого φ(i,Q(x,y))=const по всей области S-S_i, является нетривиальной задачей, вероятно, столь же сложной, как и горячая штамповка оригинального объекта аутентификации.

В. Отношение освещенности концевых точек волокна

Определение 3. Отношение освещенности концевых точек волокна

Для объекта аутентификации (L,R,K) и его освещенной зоны S_i отношение освещенности λ определяется как вероятность того, что волокно f={A,B} легло так, что одна из его концевых точек находится в B⊂S-S_i, при том условии, что другая его концевая точка находится в A⊂S_i:

λ=Pr[B⊂S-S i |f={A,B},A⊂S i ]

(14)

Определение 4. Возможно освещенная дуга

Для любой точки A⊂S_i определяют функцию ψ(i,A(x,y)), которая измеряет длину части периметра C(A,R), содержащегося в S-S_i.

На фиг.9 показано графическое представление областей T0-T8, где ψ(i,Q(x,y)) вычисляется с использованием характерных замкнутых аналитических форм. ψ(i,Q(x,y)) аналитически вычисляют на основании анализа событий (i-ii) из раздела III-A. По аналогии с разделом III-A вычисление производится только в случае, когда зона S_i освещена. В СП имеется девять различных зон (обозначенных Т0-Т8 на фиг.9), где ψ(1,Q) вычисляется однородно. Аналитические замкнутые формы для ψ(1,Q), зависящие от местоположения Q в S_i, приведены в таблице 1.

Лемма 4. Зависимость ψ(1,Q(x,y)), ρ(Q(x,y)) и λ.

Отношение освещенности, определенное в определении 3, можно вычислить следующим образом:

(15)

Круг с центром в точке A⊂S и радиусом R обозначен C(A,R). Для каждой точки Q⊂S_i вероятность того, что другая концевая точка В волокна f={Q,B} лежит в S-S_i, равна отношению длин частей периметра C(Q,R), содержащихся в S-S_i и S соответственно. Интегрируя это отношение по всем точкам в S_i, получаем уравнение 15.

С учетом того, что объект аутентификации (L,R,K) с использованием λ вычислен путем численной аппроксимации уравнения 15 и замкнутых форм для ψ(1,Q) и таблицы 1, можно вычислить ожидаемое число освещенных точек в S-S_i, когда S_i освещена как λK/2. Например, для объекта аутентификации (64,28,100) результирующее λ ≈ 0.74, и это значит, что в среднем число освещенных концевых точек в случае, когда S_i освещена, составляет примерно 0.74×50 = 37.

IV. Сжатие подмножества точек в СП

Цель системы сертификата подлинности состоит в том, чтобы задача изготовления (т.е. горячей штамповки) конкретного экземпляра объекта аутентификации была как можно труднее. Эта цель количественно выражается в необходимости записи позиций как можно большего количества волокон объекта аутентификации. В иллюстративном алгоритме сжатия количество зон объекта аутентификации равно четырем; поэтому для каждой зоны S_i четверть n_M/4 битов подписанного сообщения m выделяется для сохранения как можно большего количества концевых точек волокон, освещенных в S-S_i, когда свет падает на S_i. Заметим, что в общем случае не все освещенные точки нужно сохранять; кодировать с использованием n_M/4 битов можно только наибольшее подмножество этих точек.

В этом разделе мы опишем механизм, способный кодировать расстояние между двумя освещенными точками в объекте аутентификации. Механизм основан на арифметическом кодировании. Затем мы формализуем задачу сжатия как можно большего количества концевых точек с использованием постоянного числа битов. Наконец, мы покажем, что эта задача является NP-полной, и представим конструктивную эвристику в качестве субоптимального решения.

А. Кодирование двухточечных векторов

В этом подразделе мы опишем, как вектор, заданный своими начальной и конечной точками, кодируется с использованием количества битов, близкого к минимальному. Дополнительное ограничение состоит в том, что точки в рассматриваемой области появляются в соответствии с данной ФПВ.

1) Арифметическое кодирование

Арифметический кодер (АК) преобразует входной поток произвольной длины в единичное рациональное число в [0,1}. Главная сила АК в том, что он может сжимать как угодно близко к энтропии. Ниже мы покажем, как слово "aba" кодируется с использованием алфавита с неизвестной ФПВ появления символов.

На фиг.10 показано графическое представление примера того, как арифметический кодер кодирует строку "aba" с использованием алфавита L={a,b} с неизвестной ФПВ появления символов. Пример показан на фиг.10.

Первоначально диапазон АК сбрасывают на [0,1} и каждому символу в L назначают равную вероятность появления Pr[a]=Pr[b]=1/2. Таким образом, АК делит свой диапазон на два поддиапазона [0,0.5} и [0.5,1}, каждый из которых представляет "b" и "a" соответственно. Символ “а” кодируется сужением диапазона АК до диапазона, соответствующего этому символу, т.е. [0.5,1}. Кроме того, АК обновляет счетчик появления символа “а” и повторно вычисляет Pr[a]=2/3 и Pr[b]=1/3. В следующей итерации, согласно обновленным Pr[a], Pr[b], АК делит свой диапазон на [0.5,0.6667} и [0.6667,1}, каждый из которых представляет "b" и "a" соответственно. При следующем появлении "b" АК сужает свой диапазон до соответствующего [0.5,0.6667}, обновляет Pr[a]=Pr[b]=2/4 и делит новый диапазон на [0.5,0.5833} и [0.5833,0.6667}, каждый из которых представляет "b" и "a" соответственно. Поскольку последним символом является "a", АК кодирует этот символ, выбирая в качестве выходного значения любое число в [0.5833,0.6667}. Выбирая число, которое кодируется минимальным числом битов (в нашем примере, цифр), 0.6, АК создает свое окончательное выходное значение. Декодер воспринимает длину сообщения либо явно в заголовке сжатого сообщения, либо в особом символе “конец файла”.

АК итеративно сужает свой рабочий диапазон вплоть до момента, когда его диапазон становится таким, что старшие цифры верхней и нижней границ оказываются одинаковыми. Тогда старшую цифру можно передавать. Этот процесс, именуемый перенормировкой, позволяет сжимать файлы любой длины на арифметических модулях ограниченной точности. Усовершенствования в работе классического АК сосредоточены на: использовании заранее вычисленных аппроксимаций арифметических расчетов, замене деления и умножения сдвигом и сложением.

АК кодирует последовательность входящих символов s=s₁,s₂,... с использованием количества битов, равного энтропии источника, . Поэтому для полубесконечного потока независимых и одинаково распределенных символов на компьютере с арифметикой бесконечной точности АК является оптимальным энтропийным кодером.

Арифметическое кодирование двухточечного вектора с минимальным расстоянием

Пусть свет падает на один из квадрантов S_i объекта аутентификации (L,R,K). Затем предположим, что объект аутентификации разделен на сетку из L×L единичных квадратов U=u(i,j), i=1...L, j=1...L, где каждый u(i,j) покрывает квадратную область в x∈{i-1,i], y∈{j-1,j]. Единичные области моделируют пиксели цифрового сканирования объекта аутентификации. Разрешение сканирования равно L×L. Затем главную точку единицы u(x,y) задают как точку Q_u с координатами (x,y).

Лемма 5. Вероятность освещения единицы.

Если предположить, что имеется κ волокон, имеющих в точности одну концевую точку в S-S_i, вероятность того, что единичная область u(x,y)⊂S-S_i содержит, по меньшей мере, одну освещенную концевую точку волокна, равна:

r(u)=Pr