С развитием информационных технологий биометрию стали применять во многих областях человеческой деятельности. Биометрические системы защиты информации обладают значительными преимуществами перед традиционными системами, так как однозначно идентифицируют человека. Среди преимуществ биометрических систем выделяют легкость предъявления биометрических данных (отпечаток пальцев или радужной оболочки глаза), неотчуждаемость биометрических характеристик, а также легкость встраивания в системы многофакторной аутентификации. Наибольшее распространение в настоящее время получили системы, которые в качестве биометрической информации используют отпечатки пальцев [1].
В настоящее время существует несколько концепций построения биометрических систем. Отличаются они местом хранения и сравнения отпечатков пальцев.
– Концепция Match-On-Server. В данном подходе ОП хранятся и сопоставляются на централизованном сервере. Сервер сравнивает отпечатки и выдает разрешение на дальнейшее действие. Недостатками данной концепции являются необходимость гарантировать постоянный доступ к серверу, а также обеспечение высоких требований безопасности.
– Концепция Match-On-PC. В данном подходе ОП хранятся на компьютерах пользователей. Сравнение отпечатка-кандидата с эталоном также происходит на компьютере пользователя.
– Концепция Match-On-Card. В данном подходе хранение и сравнение отпечатков пальцев происходит на интеллектуальном карточном устройстве (далее смарт-карта).
Безопасное хранение отпечатков пальцев является важной задачей, так как в отличие от приватных ключей их сложно изменить, если отпечаток пальца будет украден. Биометрические системы, основанные на концепции Match-On-Card (рис. 1), обладают рядом преимуществ перед остальными, а именно: на смарт-карте не хранится изображение отпечатка пальца, а только шаблон отпечатка пальца, который практически невозможно преобразовать обратно в изображение [2]; шаблон отпечатка пальца никогда не возвращается, верификация происходит на смарт-карте, а следовательно, нет необходимости строить централизованное хранилище эталонов отпечатков пальцев пользователей системы.
Вычислительные возможности смарт-карт несоизмеримо малы по сравнению с персональными компьютерами. Поэтому при разработке новых алгоритмов сравнения отпечатков пальцев особое внимание следует уделять скорости сравнения отпечатков пальцев, размерам памяти, необходимой для проведения вычислений и для хранения эталонов отпечатков пальцев.
Алгоритмы регистрации и верификации не используют изображения отпечатков пальцев, а работают с их шаблонами, сформированными в формате стандарта ISO/IEC 19794-2 [4]. Шаблон отпечатка пальца представляет собой набор особых точек, который является математическим представлением изображения отпечатка пальца. Каждая точка характеризуется тремя параметрами: координаты местоположения внутри изображения отпечатка пальца, тип особой точки (точка обрыва и точка разветвления (рис. 2, а) и ориентация хребта θ (в градусах), на котором была найдена точка (рис. 2, б и в).
В качестве показателей эффективности алгоритмов регистрации и верификации используются следующие параметры:
– вероятность ложного принятия решения (False Accept Rate, FAR) – вероятность того, что система некорректно сравнит шаблоны разных отпечатков пальцев;
– вероятность ложного отказа (False Reject Rate, FRR) – вероятность того, что система не сопоставит шаблоны отпечатков пальцев, принадлежащих одному и тому же пальцу;
– размер шаблона-эталона отпечатка пальца, который хранится на смарт-карте.
Рис. 1. Распределение задач в системе Match-on-Card
а б в
Рис. 2. Особые точки: а – точка обрыва выделена кругом, точка разветвления выделена квадратом; б – расположение и угол ориентации точки обрыва; в – расположение и угол ориентации точки разветвления
На основании указанных параметров можно проводить сравнения существующих современных алгоритмов. В статье [1] приводится алгоритм верификации отпечатков пальцев для Java Card. Алгоритм имеет асимметричное время сравнения отпечатков пальцев, которое составляет от 0,3 (для сопоставимых отпечатков) до 8 (для несопоставимых) секунд. Авторы приводят следующие параметры эффективности алгоритмов: FAR составляет около 0,1 % и FRR – около 6 %. В статье [3] описан алгоритм аутентификации для системы Match-On-Card на основе отпечатков пальцев. В предложенном алгоритме сравниваются отпечатки пальцев, представленных в формате [4], с помощью матрицы аффинных преобразований (трансляций и поворотов), размер которой составляет от 512 байт до 32 Кбайт. Время сравнения отпечатков пальцев составляет от 66 до 303 миллисекунд, которое достигается благодаря дополнительному аппаратному модулю. Показатели эффективности алгоритмов (FAR и FRR) в статье [3] явно не указываются.
Существующие решения не совсем подходят для реализации на смарт-карте, так как предъявляются относительно высокие требования к производительности вычислительного устройства и к размерам памяти. В данной статье предлагаются алгоритмы регистрации и верификации шаблонов отпечатков пальцев с низкими требованиями к производительности и памяти вычислительных устройств.
Целью работы является разработка методик и алгоритмов обработки биометрической информации для систем принятия решения в составе интеллектуальных карточных устройств с малыми вычислительными ресурсами для решения задач идентификации и верификации личности.
Алгоритм регистрации отпечатков пальцев
В данной статье предлагается алгоритм регистрации шаблонов отпечатков пальцев, представленных в формате ISO 19794-2 [4], который является математическим представлением информации об особых точках отпечатка пальца. Извлечение данных об особых точках и формирование шаблона производится внешним программным обеспечением и не рассматривается в данной статье.
Для описания алгоритма регистрации отпечатков пальцев введем некоторые обозначения. Пусть изображению отпечатка пальца A функцией вычисления шаблона f поставлен в соответствие шаблон T = f(A) в виде множества (1):
T = {mi}; (1)
mi = {xi, yi, θi}, (2)
где i ∈ I = 1...n; n – количество особых точек; mi – особые точки отпечатка пальца (2), а xi, yi – координаты особых точек; θi – углы направлений особых точек (рис. 2, б и в).
Регистрация шаблона сводится к поиску группы G = {(mi, Ci)}, где Ci – центральная область, которая представляет собой информацию о взаимном расположении центральной точки и соседних особых точек. Центральные области вычисляются на основе особых точек. Каждая особая точка mi из шаблона T принимается в качестве центральной особой точки. Для этих точек строится центральная область Ci по формулам (3)–(7).
Ci = {ti}, (3)
i, j ∈ 1...n; (4)
(5)
Δθij = θi – θj; (6)
(7)
где центральные области Ci представлены в виде множества связей ti; ti характеризует взаимное расположение центральной особой точки mi и соседней особой точки mj; dij – расстояние между особыми точками; k1 характеризует порог приемлемого расстояния; Δαij – угол поворота направления центральной особой точки до направления прямой, соединяющей эту точку с соседней; Δθij – разность углов направлений особых точек (рис. 3).
Рис. 3. Расстояния и углы между двумя особыми точками
Для добавления центральных областей Ci вместе с соответствующими им особыми точками mi в группу G необходимо соблюдение выполнения равенства (8):
i ∈ I = 1...n, (8)
где k2 характеризует порог минимального количества связей.
Количество элементов в группе G ограничено двумя параметрами k3 и k4, что показано неравенством
(9)
где k3, k4 – пороги, характеризующие минимальное и максимальное (соответственно) количество центральных областей в зарегистрированном шаблоне отпечатка пальца.
Если неравенство (9) не выполняется, то шаблон не регистрируется. Особенность данного алгоритма заключается в том, что шаблон отпечатков пальцев в процессе регистрации преобразуется к внутреннему представлению, что позволяет ускорить процесс верификации отпечатков пальцев, так как информация о взаимном расположении особых точек шаблона-эталона отпечатка пальца заранее вычисляется данным алгоритмом и сохраняется в энергонезависимой памяти устройства.
Алгоритм верификации отпечатков пальцев
Аналогично алгоритму регистрации, алгоритм верификации отпечатков пальцев работает с шаблонами отпечатков пальцев, представленными в формате ISO 19794-2 [3]. Решение о степени сходства двух шаблонов отпечатков пальцев лежит в диапазоне 0–100 % (чем больше %, тем выше совпадение).
Введем некоторые обозначения. Пусть каждому изображению отпечатка пальца A1 и A2 функцией вычисления шаблона f поставлены в соответствие шаблоны T1 = f(A1) и T2 = f(A2) в виде множеств (10) и (11)
T1 = {mi}; mi = {xi, yi, θi}; (10)
T2 = {mj}; mj = {xj, yj, θj}. (11)
Предполагается, что шаблон T1 зарегистрирован на смарт-карте по алгоритму, схема которого представлена на рис. 4, поэтому для него существует группа G1 = {(mi, Ci)}, где i ∈ I, количество элементов в которой ограниченно неравенством (9).
Для шаблона T2 происходит формирование центральных областей согласно формулам (3)–(7) и находится группа G2, которая соответствует выражению (12).
G2 = {(mj, Cj)}, j ∈ 1...r; (12)
k5 ≤ r ≤ k6, (13)
где r – количество центральных областей для шаблона T2 и ограничено неравенством (13); k5 и k6 – пороги, ограничивающие количество связей в центральной области Cj.
В процессе верификации каждая центральная область зарегистрированного шаблона (mi, Ci) ∈ G1 сравнивается с каждой центральной областью шаблона верифицируемого отпечатка пальца (mj, Cj) ∈ G2, i ∈ I, j ∈ J. Для этого находится группа L, которая описывается равенством (14) и отображает наилучшие сопоставления связей двух сравниваемых центральных областей. Размер группы L ограничен неравенством (15).
L = {la}, a ∈ I; (14)
(15)
где la отображает степень различия связей центральных областей и представляет собой расстояние Хэмминга связей центральных областей, а порог k7 ограничивает размер группы L. Каждый элемент lr вычисляется согласно формуле (16) и удовлетворяет неравенству (17) при условии, что выполняются неравенства (18)–(20).
la = Δdij + Δαij + Δθij; (16)
la < k11; (17)
Δdij < k8; (18)
Δαij < k9; (19)
Δθij < k10, (20)
где 
– разница между расстояниями связей, 
– разница между углами α связей, 
– разница между углами θ связей, для 
; k8–k11 – пороги, ограничивающие Δdij, Δαij, Δθij, la, и обозначают допустимые отклонения при сравнении связей.
Степень расхождения сравниваемых центральных областей определяется группой N согласно равенству (21), каждый элемент которой вычисляется согласно формуле (23) и удовлетворяет неравенству (24). Размер группы N ограничен неравенством (22).
N = {ni}, i ∈ I; (21)
(22)
(23)
ni < k13, (24)
где ni отражает среднее отклонение по всем связям сравниваемых центральных областей, k12 – порог, ограничивающий максимальный размер группы N; k13 – порог, характеризующий допустимое отклонение ni.
Степень сходства двух шаблонов отпечатков пальца рассчитывается по формулам.
(25)
где
(26)
(27)
(28)
где H – среднее отклонение сопоставимых центральных областей; W и 
– порог, характеризующий допустимое отклонение центральных областей; k14 – порог принятия решения о сходстве отпечатков пальцев.
S(T1, T2) ≥ k14. (29)
Шаблоны отпечатков пальцев T1 и T2 сопоставимы, если неравенство (29) выполняется.
Заключение
В данной статье рассмотрены основные концепции построения биометрических систем и предложены быстрые алгоритмы регистрации и верификации отпечатков пальцев для систем принятия решения на основе интеллектуальных карточных устройств. Системы, основанные на концепции Match-On-Card, являются более защищенными по сравнению с системами, основанными на других концепциях. Ключевым элементом систем Match-On-Card является высокозащищенное интеллектуальное карточное устройство (смарт-карта). В данной статье рассмотрена и решена проблема сравнения отпечатков пальцев на высокозащищенном интеллектуальном карточном устройстве (смарт-карте).
Предложенные алгоритмы регистрации и верификации отпечатков пальцев предъявляют низкие требования к производительности вычислительных устройств, поэтому предназначены для внедрения на смарт-карты. Хранение эталона отпечатка пальца требует от 1100 до 1900 байт. Время верификации отпечатков пальцев не превышает двух секунд, значения FAR и FRR равны 0,00452 и 2,23 % соответственно, что в несколько раз лучше существующих аналогов [1–3]. Предложенные алгоритмы не учитывают влияния других характеристик особых точек на процесс сравнения отпечатков пальцев и возможность хранения нескольких эталонов шаблонов отпечатков пальцев на смарт-карте, что может быть результатом дальнейшего исследования.