2.3. Betydningen av bevisstgjøring av utviklingsmuligheter
2.3.1. Positive mestringserfaringer og motivasjon
Nos processos Fuzzy Commitment (como visto na seção 3.1.2) e Fuzzy Vault (como visto na seção 3.1.1), são utilizada algumas técnicas específicas para cada processo. Dentre as mais variadas técnicas utilizadas nestes métodos, pode-se relacionar um algoritmo de recuperação de erros, ou mais precisamente, um Código Detector e Corretor de Erros utilizado para gerar um codeword (ver seção 3.1.2) no processo Fuzzy Commitment. Neste caso, o algoritmo de detecção e correção de erros utilizado é Reed Solomon (RS) [Reed e Solomon 1960]. A seguir será descrito brevemente o processo de geração de palavra código, capacidade de correção, tamanho de símbolos do RS.
5.2.2.1 Reed Solomon
O código corretor e detector de erros Reed Solomon (RS) [Reed e Solomon 1960], foi desenvolvido por Irving Reed e Gus Solomon em 1960. A principal característica deste código está relacionada ao poder de detecção e correção em função da baixa complexidade no processo de geração de códigos RS. Outra característica do RS, está relacionada a solução de problemas quanto a escolha da distância entre os códigos. Este problema, reflete no desempenho do código. Escolher uma distância mínima é possível através de um polinômio gerador1
. Quanto maior o grau deste polinômio, maior será o seu poder de correção. No entanto, maior será a mensagem de redundância inserida na mensagem original. Isto é a forma mais adequada para encontrar e corrigir erros em determinada palavra recebida. A seguir será descrito um resumo sobre o processo de codificação e decodificação do RS.
Codificação
O RS pode ser definido por RS(n,k,t), onde o n informa o total de símbolos (caracteres originais mais dados de paridade) de uma sequência de entrada (texto a ser enviado juntamente com o código gerado). A variável k corresponde a quantidade de símbolos do texto que serão enviados, e por último, t representa a capacidade de correção do código, ou seja, até quantos caracteres errados, o código consegue corrigir. No entanto, a paridade é dada por 2t.
Para definir os parâmetros de entrada para um RS, faz-se necessário satisfazer as seguintes equações:
n = 2m− 1 (5.1)
k = 2m− 1 − 2t (5.2)
n − k = 2t (5.3)
Por exemplo, para um RS(255,239,8) e adotando-se m = 8 bits, ou seja, cada símbolo é representado com 8 bits, é possível representar 255 bytes, ou seja, 255 símbolos de acordo com a equação 5.1. Neste caso, k = 239, de acordo com a equação 5.2. Desta forma, existem 16 símbolos de paridade na mensagem, ou seja para esta paridade, tem-se t = 8, que satisfaz a equação 5.3. Os modos codificação e de decodificação do RS baseiam-se na utilização de Campos Finitos, também conhecidos como Campos de Galois (GF). Segundo
1
Um polinômio Gerador G(x) é um polinômio de grau n utilizado pelo emissor e pelo destinatário na detecção e correção de erro.
[Huffman e Pless 2003], campos finitos podem ser definidos como conjuntos fechados F para operações pré-definidas. Exemplo, a soma e a multiplicação representam campos finitos, pois os símbolos são "+"e ".", como pode ser verificado através dos seguintes axiomas:
• Um Campo Finito deve ser um grupo comutativo para +. Para a adição o elemento identidade é chamado de elemento neutro ou identidade aditiva deste campo finito, denotada por 0.
• Existe um conjunto de elementos diferentes de zero, comutativo para multiplicação e o elemento 1 é o elemento o identidade para a multiplicação.
• A operação de Multiplicação é distributiva sobre a adição para qualquer elemento. Cada campo finito (GF) deve atender as seguintes propriedades:
• Um campo F é finito quando tem-se um número finito de elementos. • O número de elementos no campo finito é chamado de ordem.
Uma denotação para a variação de ordem em conjuntos finitos é GF (p), onde p representa a ordem do campo finito. Por exemplo, seja p um número primo, existe um campo de Galois GF (p) com exatamente p elementos. Desta forma GF (2) = {0, 1} é um campo de Galois. Isso decorre pois existem dois elementos e, realizando a adição e multiplicação de módulo 2, o conjunto é fechado. De modo similar, para p primo, GF (p) pode ser representado pelo conjunto 0, 1, 2, ..., p, e as operações aritméticas são realizadas em módulo p.
Esse campo pode ser estendido para pm elementos, onde m é um inteiro positivo,
resultando no campo estendido GF (pm). Por exemplo, pode-se estender o campo
finito primário GF (2), igual a 0, 1, utilizando m = 3, para um campo GF (23) para
000, 001, 010, ..., 111. Sendo assim, pode-se utilizar estes campos estendidos para gerar um conjunto fechado, cujo cada elemento deste conjunto pode ser representado por um polinômio de grau m. Por exemplo ax0+ax1+ax2+axm−1, onde a pode assumir valores do
conjunto 0, 1. Neste caso, pode-se representar valores em decimal em função dos polinômios e valores de a para cada GF (pm).
Estes campos estendidos são utilizados pelo RS para gerar seus respectivos polinômios geradores. Para construir um código RS(255,239) é necessário construir um polinômio gerador de código representado por G(x). Este polinômio, possui grau m = p(n + 1),
onde n representa a quantidade de símbolos de uma mensagem. Neste caso, tem-se m = 16, logo necessita-se gerar um GF (28), onde cada elemento deste campo finito consiste em
uma palavra de 8 bits. Portanto, para GF (28), tem-se um polinômio G(x) = (x + α0).(x +
α1).(x + α2).(x + α3).(x + α4).(x + α5).(x + α6).(x + α7)...(x + αm−1). Para codificar os
elementos da mensagem, estes elementos podem ser representados através de polinômios. Por exemplo. Uma mensagem M(x) = (1, 2, 3, 4, 5, 6, 7, 8, 9, ...239), pode ser representada por Mp(x) = 1x239+ 2x238+ ... + 239x0. A partir deste ponto é necessário fazer a operação
de deslocamento do Polinômio M(x) com xm, onde neste caso, m = 16, é denotado por
MM4
x(x). A partir do polinômio gerado, aplica-se uma divisão de MMx4(x) por G(x) para
gerar o R(x) denominado o resto da divisão grau (m − 1), este resto será adicionado a mensagem original, estes valores são denominados dados de paridade.
Decodificação
O processo de decodificação do RS, importante na implementação dos métodos Fuzzy, é necessário para "corrigir"e encontrar o valor correto em função do valor da biometria de entrada, desde modo, em virtude da relevância da decodificação no processo dos métodos FC e FV, a mesma será descrita a seguir.
O processo de decodificação do RS, pode ser resumido em 3 etapas, o cálculo da síndrome, o cálculo dos coeficientes do polinômio localizador de erro e o cálculo das localizações de erros e dos valores dos erros. Para a realização do cálculo da síndrome faz-se necessário verificar as raízes do polinômio de entrada. Por exemplo, um polinômio de entrada P (x), caso não apresente erros na sequência, o mesmo deve apresentar síndrome igual a 0, caso contrário, a sequência devera conter erros. Cada síndrome é composta por n − k símbolos, neste caso, para o exemplo anterior, RS(255,239), tem-se 16 símbolos para cada síndrome. Como a sequência P (x) dever ser múltipla do polinômio gerador, a divisão de P (x) pelo polinômio gerador deve retornar 0, o que representa que a mensagem não contem erros, caso contrário, apresentam-se valores diferentes de 0. Neste caso, o cálculo de cada síndrome é realizada utilizando a seguinte equação:
Si = r(X)|X=αi = r(αi) (5.4)
onde i = 1, 2, 3, . . . , n−k, α representa o coeficiente da sequência P (x). No que diz respeito a localização de erros, supõe-se que exista uma quantidade v de erros na sequência P (x). Desta forma, as localizações de cada erro podem ser definidas por Xj1, Xj2, . . . , Xjv. Desta
+ . . . + Ejv Xjv.
Assim, para corrigir uma sequência que contenha erros, faz-se necessário encontrar os valores dos erros, que são denotados por denotados por Ejl, e as localizações dos erros,
denotadas por Xjl, onde l = 1, 2, ..., v.
Uma abordagem utilizada para encontrar erros é definir uma variável correspondente a localização do erro, neste caso βl = αjl. Assim, tem-se 2t símbolos da síndrome
substituindo αi no polinômio de erro E(X), para i = 1, 2, ..., 2t, denominado β(X).
Por se tratarem de equações não-lineares (algumas incógnitas possuem expoentes), faz-se necessário utilizar outras técnicas que resolvem este sistema de equações e neste caso, se um vetor de síndromes diferente de zero for calculado, afirma-se que a sequência recebida possui erros. Se esta sequência possui erros, deve-se encontrar os respectivos valores de erros. Neste caso, se um erro for definido como Ej1, onde o índice j se refere a localização
e o índice l identifica a ordem do erro, é possível verificar a relação entre o valor e a localização do erro.
Para calcular os valores dos erros, utiliza-se β(X). Por exemplo, para encontrar as raízes de β(X), utiliza-se testes do polinômio gerador com todos os elementos do campo, onde qualquer elemento W que resultar em β(W ) = 0 será uma raiz e correspondente a uma localização de erro. Neste caso, pode-se utilizar qualquer uma das síndromes encontradas (equação 5.4) e utilizando a equação S1 = E(α) com os valores das
localizações dos erros αv, geram-se equações que devem ser resolvidas utilizando matrizes,
e desta forma, aplica-las na forma de polinômios, denominados (X).
Com o conhecimento dos polinômios (X) e r(X), onde r(X) representa a sequência recebida, pode-se construir o polinômio que representa a sequência completa da mensagem e comparar com o resultado r(X) + (X), indicando se a mensagem foi decodificada corretamente, ou seja, corrigindo a mensagem recebida com erros. Para mais detalhes e exemplos sobre a decodificação do RS, aconselha-se a leitura de [Reed e Solomon 1960]. Nesta tese, o RS foi utilizado no Fuzzy Commitment para verificar a possibilidade de recuperar uma informação armazenada em função da variação inerente da coleta de dados de determinadas características biométricas, como por exemplo, a voz. Esta característica biométrica permite que as coletas de um mesmo usuário possuam pequenas e aceitáveis diferenças. Estas diferenças podem ser calculadas e extraídas, ou seja, dados de voz semelhantes devem ser reconhecidos, e esta diferença pode ser interpretada pelo RS com um erro passível de correção, e em virtude da viabilidade de correção destes dados, é possível autenticar ou não um determinado indivíduo.
5.2.2.2 Lagrange
No que diz respeito ao Fuzzy Vault, no processo intrínseco ao FV, utilizou-se de conceitos de interpolação para reconstruir polinômios a partir de um conjunto de dados. A interpolação polinomial utilizada nesta tese, trata-se de uma técnica que reconstrói um polinômio através de um conjunto de pares ordenados na forma de Conjunto = (x0, y0), (x1, y1), ..., (xn, yn), onde n representa a quantidade de pares ordenados em um
conjunto. Diante destes valores, é possível encontrar valores intermediários, assim como reconstruir o polinômio utilizado para os valores de yn, através da relação existente entre
x e y, onde y = f (x), onde f (x) é a função que resulta na imagem de x. O Fuzzy Vault utiliza uma específica técnica de Interpolação chamada Lagrange. (Ver [Filho 2007] para mais detalhes sobre Lagrange).
De acordo com uma função F e suas respectivas imagens para valores de x, em um conjunto X = x0, x1, x2, x3, ..., xn, ou seja, um conjunto A =
{(x0, f (x0), (x1, f (x1), (x2, f (x2) , .., (xn, f (xn)}, é necessário encontrar um polinômio
g(x) que se aproxime de f (x). Pode-se denominar este polinômio interpolador como g(xn) = anxmi + ... + a1xi + a0, onde xi são denominados pontos de interpolação.
De acordo [Filho 2007], deve-se existir um único polinômio f(x) que gere o conjunto A, logo ao encontrar um polinômio que construa integralmente o valores em A, este polinômio interpolador g(x) será igual f(x). Admitindo-se um polinômio g(x) na forma de G(x) = f(x0)Ln,0(x)+...+f (xn)Ln,k(x), onde n representa quantidade de elementos no
conjunto, e k representa os valores no intervalo crescente 0, 1, 2, ..., n, é possível calcular cada coeficiente de G(x) através da expressão 5.5:
Ln,k(x) =
(x − x0)(x − x1)...(x − xk−1)(x − xk+1)...(x − xn)
(xk− x0)(xk− x1)...(xk− xk−1)(xk− xk+1)...(xk− xn)
(5.5) O resultado do método de Lagrange retorna um polinômio P (x) que se aproxima da função utilizada na geração das respectivas imagens de cada elemento numérico. Devido ao alto grau do polinômio utilizado no método Fuzzy Vault, promove-se a existência de um único polinômio capaz de gerar resultados próximos função original f(x), logo, o polinômio encontrado pela utilização da técnica de Lagrange deve estritamente igual em número e valores de cada coeficiente do polinômio utilizado, ou seja, f(x) = P (x). Por exemplo, seja, f (x) = x2+x1+10, logo tem-se para x = 2, 3, 4, um conjunto imagem f (x
0), f (x1), f (x2) =
16, 22, 30. Desta forma, calculando-se cada coeficiente, L0(x0), L0(x1), L0(x2) utilizando a
L2(x) = (x−2)(x−3)2 . P (x) = n X k=0 f (xk)Lk(x) (5.6)
Utilizando como coeficientes os valores para cada f(x0),f (x1) ef (x2) na equação 5.6,
tem-se 16((x−3)(x−4)
2 ), 22(−(x − 2)(x − 4)) e 30
(x−2)(x−3)
2 . Aplicando uma simplificação
sobre cada coeficiente, tem-se 8((x − 3)(x − 4)), 22(−(x − 2)(x − 4)) e 15((x − 2)(x − 3)). Após a realização do produto das equações, o resultado éP (x) = 8x2− 56x + 96 − 22x2+
132 − 176 + 15x2 − 75x + 90. Continuando com as resoluções das operações aritméticas
(adição e subtração), tem-se como resultado final o polinômio P (x) = x2+ x + 10, ou seja,
foi possível recuperar o polinômio utilizado f(x).
As técnicas descritas nas próximas subseções tratam dos métodos de transformação aplicados sobre as bases de Voz e Impressão digital utilizadas nesta tese.