View
252
Download
0
Category
Preview:
Citation preview
MATEMATICA APLICADO A CRIPTOGRAFIA - CURSOS DE SEGURANÇA DA INFORMAÇÃOPROFº VALDIR ZIMBA
INSTITUTO CIENTÍFICO DE ENSINO SUPERIOR E PESQUISA – UNICESP
DEPARTAMENTO DE TECNOLOGIA
CURSO DE TECNOLOGIA SEGURANÇA DA INFORMAÇÃO – TSI
DISCIPLINA: MATEMÁTICA APLICADA A CRIPTOGRAFIA – MAC
PROFESSOR: VALDIR SILVA DOS SANTOS ZIMBA
MATEMÁTICA APLICADA A CRIPTOGRAFIA
FERRAMANTAL MATEMÁTICO VOLTADO AO ESTUDO DOS
ALGORITMOS CRIPTOGRÁFICOS
AGO 2008
1
MATEMATICA APLICADO A CRIPTOGRAFIA - CURSOS DE SEGURANÇA DA INFORMAÇÃOPROFº VALDIR ZIMBA
1- INTRODUÇÃO.
A teoria de conjuntos é estudada e aplicada em vários ramos da atividade
humana, qualquer atividade onde seja necessária a sistematização ou a
organização de idéias e procedimentos nela será utilizada conceitos da teoria
de conjuntos. Os conjuntos numéricos foram organizados conforme a
necessidade da aplicação das operações de adição, subtração multiplicação,
divisão e radiciação para representar situações do dia-a-dia.
A matemática para criptografia está contida dentro da teoria numérica e da
aritmética básica. É necessário retomar o estudo da aritmética básica e rever
conceitos básicos da formação numérica, tais como: divisor, múltiplo, primos,
compostos, par, ímpar etc.
Começamos estudando a formação dos conjuntos numéricos e a capacidade
que os mesmos apresentam para suportar as operações numéricas: adição,
subtração, multiplicação, divisão, potenciação e radiciação.
2- CONJUNTOS NUMÉRICOS
Os números foram organizados em conjuntos conforme suas propriedades e de
acordo com a capacidade de representar situações do dia-a-dia. O primeiro
conjunto numérico a ser apresentado é o conjunto dos números naturais (N)
em seguida aparece o conjunto dos números inteiros relativos (Z) , logo após,
temos o conjunto dos números racionais relativos (Q) e o conjunto dos
números irracionais (I), da união desses dois últimos surge o conjunto dos
números reais (R) e por fim, é apresentado o conjunto dos números complexos
(C) .
2.1 - CONJUNTO DOS NUMEROS NATURAIS (N)
Os números naturais aparecem na vida do cidadão desde muito cedo, surge da
capacidade natural do indivíduo de enumerar quantidades, relacionar
elementos de conjuntos distintos e fazer correspondência entre quantidades
para que suas necessidades básicas sejam satisfeitas. É comum a criança
2
MATEMATICA APLICADO A CRIPTOGRAFIA - CURSOS DE SEGURANÇA DA INFORMAÇÃOPROFº VALDIR ZIMBA
utilizar os números naturais para que seus desejos sejam escutados e
satisfeitos. A criança pede: “uma mamadeira”, “dois brinquedos”, “três balas”
etc. Essas quantificações são representadas no conjunto dos números naturais
N= { 0,1,2,3,4,...}.
O conjuntos dos números naturais, suporta e modela as situações que
envolvem a operação de adição, ou seja, sempre que forem utilizados números
naturais na adição é possível encontrar um número do conjunto N que seja o
resultado da operação realizada. Isso é conhecido como a propriedade do
“fechamento”, assim enunciada: “a soma de dois números naturais é um
números natural”. Dizemos então que o conjunto N é fechado em relação à
operação de adição.
Porém, quando se trata da operação de subtração não é possível dizer o
mesmo. Não é possível modelar problemas que envolvam subtração de
quantidades apenas com números naturais, pode acontecer da quantidade a
ser retirada (subtraendo) ser maior que a quantidade existente (minuendo) e o
resultado da operação extrapolar o conjunto dos números naturais.
(18 - 20 = -2) .
A quantificação, negativo dois (-2), é exógeno ao conjunto N. Logo, podemos
concluir que a subtração não é fechada no conjunto dos naturais. É necessário
organizar um outro conjunto numérico que dê suporte esse tipo de modelagem.
2.2 – CONJUNTO DOS NÚMEROS INTEIROS RELATIVOS (Z)
A necessidade de representar quantidades não positivas e não nula gerada,
em algumas situações, pela operação de subtração levou a uma ampliação do
conjunto dos naturais. Desta forma, cada número natural, não nulo, deu origem
a dois números inteiros e relativos: um positivo (+) e outro negativo (-). O zero
passou a ser o número referencial e conjunto Z foi gerado e organizado com
quantidades negativas a esquerda do zero e quantidades positivas a direita do
zero, -2, -. Z = { ...-31, 0, 1, 2, 3, ... } .
3
MATEMATICA APLICADO A CRIPTOGRAFIA - CURSOS DE SEGURANÇA DA INFORMAÇÃOPROFº VALDIR ZIMBA
A subtração de dois números inteiros sempre será um número inteiro.
Podendo, o resultado, ser positivo (crédito), negativo (débito) ou nulo. O
mesmo ocorre com a adição algébrica de números inteiros. O problema dos
números inteiros (Z) surge na operação de divisão porque nem sempre a
divisão de dois inteiros resulta em número inteiro. ( 25 : 2 = 12,5 ).
Logo, a divisão não é fechada em Z, o que obriga a organização de outro
conjunto numérico que suporte a operação de divisão.
2.3 - CONJUNTO DOS NÚMEROS RACIONAIS REALTIVOS (Q).
Os quocientes não exatos não podem ser representados dentro do conjunto
dos inteiros relativos, é necessário que o conjunto seja ampliado para que
essas quantidades possam ser incluídas e as modelagens que representem
situações de divisões com resto diferente de zero possam ser efetuadas.
A idéia principal é pensar que na vida real o espaço entre dois números inteiros
pode vir a ser dividido em quantas partes se queira, logo, para cada divisão
não exata existirá uma fração própria (denominador maior que o numerador)
associada. Ou seja, entre dois inteiros podem existir infinitos números não
inteiros. A reunião dos inteiros com todas as frações forma o conjunto dos
números racionais relativos. Q = {... -2, ... -1,.... 0, ... 1, .... 2, .... }.
Com a ampliação do conjunto dos inteiros para o conjunto dos racionais a
operação de divisão passou a ter fechamento válido. Ou seja,
},{ *
b
aZbZaQ ∈∈= , qualquer números que possa ser transformado em
fração será considerado números racional.
O conjunto dos números racionais é fechado para as operações: adição,
subtração, multiplicação e divisão. Porém, a radiciação nos racionais (Q) não é
fechada porque as raízes não exatas extrapolam a fronteira dos números
racionais, criando uma dicotomia numérica. Todos os números que poderem
ser colocados na forma de fração serão conhecidos como números irracionais.
4
MATEMATICA APLICADO A CRIPTOGRAFIA - CURSOS DE SEGURANÇA DA INFORMAÇÃOPROFº VALDIR ZIMBA
2.4 – CONJUNTO DOS NÚMEROS IRRACIONAIS ( I )
O fato de não se tornar fração nega a condição de racionalidade o que remete
o número, automaticamente, para o conjunto dos Irracionais. Dentro dessa
plêiade de números encontramos as raízes não exatas ( etc7 11,5,3 ) e
outros números tais como: 1415,3=π (razão entre o comprimento e o
diâmetro de uma circunferência), e = 1,71 ( base dos logaritmos naturais ) .
2.5 – CONJUNTO DOS NÚMEROS REAIS (R)
Como não é possível ampliar o conjunto dos racionais (Q) para que os
racionais ( I ) sejam incluídos os dois conjuntos foram reunidos gerando dessa
união o conjunto dos números reais (R) . R = Q U I.
Apesar da reunião desses dois conjuntos a operação de radiciação nos reais
(R) continua sendo não fechada. É possível aplicar a radiciação em números
reais e o resultado ser número não real. A raiz quadrada de -4 ( 4− ) é um
número não real. Seguindo essa mesma linha de raciocínio podemos concluir
que qualquer radiciação com índice par e radicando negativo não extrapolará o
conjunto dos reais.
Os conjuntos numéricos foram organizados e representados em retas
numeradas de forma que cada número ocupasse um lugar na reta numerada e
cada lugar na reta abrigasse um número. Desta forma, existe uma
correspondência biunívoca entre os espaços da reta e os números dos
conjuntos. A essa relação dá-se o nome de representação gráfica do conjunto
numérico.
5
MATEMATICA APLICADO A CRIPTOGRAFIA - CURSOS DE SEGURANÇA DA INFORMAÇÃOPROFº VALDIR ZIMBA
Figura 1: Reta dos números reais
2.6 – CONJUNTO DOS NÚMEROS COMPLEXOS (C)
A radiciação não é fechada no conjunto dos números reais e para solucionar
esse problema foi criado a unidade imaginária ( i ) . Essa unidade imaginária
foi definida como sendo igual a raiz quadrada de -1. Logo, 12 −=i , a idéia foi
considerar um número com duas partes, uma real e outra imaginaria. O
binômio ibaZ .+= , que representa o número complexo, pode ser
representado no plano cartesiano com a parte real representada no eixo das
abscissas, e a parte imaginária no eixo das ordenadas.
O número complexo (Z) representa um afixo do plano cartesiano conforme a
organização cartesiana ( plano Argand-Gauss).
Figura 2 : Plano Argand-Gauss
-3 0 -2 -1 ... +1 +2 +3 ...
R
eixo real
eixo imaginário
Z (a,b)
a
b
6
MATEMATICA APLICADO A CRIPTOGRAFIA - CURSOS DE SEGURANÇA DA INFORMAÇÃOPROFº VALDIR ZIMBA
3- INTERVALO NUMÉRICO
É um subconjunto do conjunto dos números reais e pode ser limitado
superiormente e inferiormente.
3.1-INTERVALO LIMITADO SUPERIORMENTE e MAOIR INTEIRO DO
INTERVALO
Intervalo de números reais que apresenta limite superior, ou seja, existe um
número maior que todos do conjunto (supremo). O intervalo limitado por cima
não apresenta limite inferior. Nos intervalos limitados por cima o supremo pode
ser inteiro ou não, quando o supremo é um número inteiro este supremo
assume o valor do maior inteiro do intervalo. No caso do supremo não ser
inteiro, existe um inteiro, imediatamente, a esquerda do supremo que será o
maior inteiro do intervalo limitado por cima. Conforme figura 3.
Figura 3: Intervalo limitado por cima
Exemplo:
a) 3145,13 = b) 2565,24 −=−
3.2 – INTERVALO LIMITADO INFERIORMENTE e MENOR INTEIRO DO
INTERVALO.
Intervalo de números reais que apresenta limite inferior, ou seja, existe um
número real que é menor que todos os números do conjunto (ínfimo). O
intervalo com limitado por baixo não apresenta limite superior. O ínfimo de um
intervalo limitado por baixo pode ser inteiro ou não, no caso de ser inteiro, o
ínfimo é o menor inteiro do intervalo. Quando o ínfimo não é um número inteiro,
Rx
a
, maior inteiro do intervalo termina em x é o intero “a” .
7
MATEMATICA APLICADO A CRIPTOGRAFIA - CURSOS DE SEGURANÇA DA INFORMAÇÃOPROFº VALDIR ZIMBA
o inteiro que está, imediatamente, a direita será o menor inteiro do intervalo
considerado.
Figura 4: intervalo limitado por baixo
Exemplo:
a) 1345,12 = b) 2337,23 −=−
4- ALGORITMOS FUNDAMENTAIS
Iniciamos o estudo da matemática básica para aplicação na criptografia
definido os algoritmos básicos, tais como: divisão simples, módulo resto,
máximo divisor comum (algoritmo de Euclides simples) e algoritmo estendido
de Euclides.
4.1 – ALGORITMO DA DIVISÃO
Sejam os números inteiros “a” (dividendo) e “b” (divisor) , com b ≠ 0, ao
dividirmos “a” pelo número “b” serão determinados os números inteiros “q”
(quociente) e “r” (resto) de tal forma que a = b.q + r , com 0 ≤ r < b –1 .
No caso do número “r” ser igual a zero, dizemos que o número “b” divide o
número “a”, o que implica dizer que “a” é múltiplo de “b”. ou seja, quando
existir um inteiro “q” cujo produto com “b” seja igual ao próprio “a” . (
Zqcomqba ∈= . ). Quando o resto (r) for um número que pertença ao
intervalo: 0 < r < b –1, consideramos que “b” não divide “a” , ou seja , “a” não
é múltiplo de “b”.
Rx
a
, menor inteiro do intervalo começa em x é o inteiro “a”.
8
MATEMATICA APLICADO A CRIPTOGRAFIA - CURSOS DE SEGURANÇA DA INFORMAÇÃOPROFº VALDIR ZIMBA
O resto da divisão de dois inteiros não pode ser negativo, seu valor é no
máximo igual ao antecessor do divisor (b). Da operação de divisão entre dois
números inteiros é possível extrair as definições de múltiplo e divisor.
Tabela-1 Algoritmo da divisão
4.2- ALGORITMO REDUÇÃO MODULAR ( MÓDULO RESTO )
Considerando os números inteiros “a” e “b” , com “b” positivo, a operação “a”
módulo “b” traz o resto da divisão entre “a” e “b” ou o seu equivalente modular.
Por definição temos: “a” módulo resto “b” igual ao número “a” subtraído do
produto do maior inteiro da divisão de “a” por “b” pelo próprio número “b” .
a ( mod b) = a – ( ba / . b )
Exemplo:
1-Determine:
a) 231 ( mod 7 ) = )7.7/231(231−
= )7.33(231−
= )7.33(231−
= )231(231−
= 0 .
Observação 1: Quando o resultado da operação, a ( mod b), for igual a
zero , temos que “a” é múltiplo de “b”. ou seja: a = k.b com k ∈Z.
).(,,0 adedivisorébabquetemosrPara =
adedivisorénãobquetemosbrPara ,10 −<<
ba
qr10. −<≤+= brcomrqba
9
MATEMATICA APLICADO A CRIPTOGRAFIA - CURSOS DE SEGURANÇA DA INFORMAÇÃOPROFº VALDIR ZIMBA
b) 123 ( mod 13) = )13.13/123(123 −
= )13.46,9(123 −
= )13.9(123 −
= )117(123 −
= 6
c) 17 ( mod 23 ) = )23.23/17(17 −
= )23.739,0(17 −
= )23.0(17 −
= )0(17 −
= 17
d)-23 ( mod 5 ) = )5.5/23(23 −−−
= )5.6,4(23 −−−
= )5.5(23 −−−
= )25(23 −−−
= 2523 +−
= 2
Observação 3: Quando o número “a” for menor zero, a operação, a ( mod b ),
traz o equivalente ao resta da divisão de “a” por “b”, levando em consideração
o conjunto Inteiro módulo b )( bZ . Será estudo nos próximos capítulos.
Tabela-2 Algoritmo da operação módulo resto
a ( mod b) = a – ( ba / . b ) , com *ZbeZa ∈∈
ba / - maior inteiro da divisão de a por b.0)mod(,"""" =baentãobdemúltiploforaSe
.)mod(, abaentãobaSe =<
10
MATEMATICA APLICADO A CRIPTOGRAFIA - CURSOS DE SEGURANÇA DA INFORMAÇÃOPROFº VALDIR ZIMBA
0 , ( mod )
" " " ".
[ (mod ) ] .
Se a então a b é equivalente ao resto
da divisão de a por b Podemos entrar oequivalente
positivo fazendo a b b
<
+
4.3 ALGORITMO SIMPLES DE EUCLIDES
Procedimento que utiliza o módulo resto para que seja determinado o maior
divisor comum (m.d.c) entre dois números inteiros. O algoritmo considera dois
números inteiros positivos “a” e “b” , com a > b e executa a operação: a
( mod b ). Se o resultado for zero, temos que m.d.c.( a ,b ) = b, se não; o
algoritmo faz “a” assumir o valor de “b” e “b” assumir o valor presente da
operação: a ( mod b ). O procedimento se repete até que o resultado da
operação: a (mod b) seja igual a zero, quando isso acontecer o m.d.c (a,b)
recebe o valor presente “b”.
O máximo divisor comum é importante na aritmética de frações porque
possibilita a simplificação imediata de uma fração, bastando dividir o
numerador e denominador da fração pelo máximo divisor comum a ambos o
que faz aparecer a fração irredutível.
Exemplo : 4
3
24
18
24
186
6
≅≅ ÷
÷
Para a criptografia de chaves assimétrica1, o maior divisor comum é importante
porque quando o mdc (a,b) for igual a 1, os números “a” e “b” são primos
relativos o que indica existe um número que é inverso multiplicativo de “b” no
conjunto Z módulo “a”. É possível dizer que o mdc é o embrião do que,
futuramente, chamaremos de par de chaves assimétricas.
Tabela-3 Algoritmo simples Euclides
1 A criptografia de chaves assimétricas, também conhecida de criptografia de chaves públicas, é aquela na qual, a codificação é realizada com uma chave, chamada de pública, e a decodificação é feita com outra chave, conhecida como particular. Existe uma relação de simetria entre as chaves, porém, sair de uma chave e chegar na outra é tarefa, na prática impossível.
11
MATEMATICA APLICADO A CRIPTOGRAFIA - CURSOS DE SEGURANÇA DA INFORMAÇÃOPROFº VALDIR ZIMBA
Início: mdc (a,b ) = mdc [ b, r ] , com r = a ( mod b)
Se r = 0, então mdc (a, b) = b ( fim)
Se r ≠ 0, então a ← b e b ← r (volta ao início) .
O inconveniente do algoritmo simples de Euclides, para aplicação em pesquisa
de chaves assimétricas, é o fato dos números “a” e “b” assumirem valores
muito grandes o que torna o inviável o tempo de processamento.
Exemplo:
Calcule o mdc entre os números e determine se são primos relativos:
a)248 e 110
mdc ( 248,110 ) = mdc [ 110 , 248 ( mod 110) ]
= mdc [ 110 , 28 ]
= mdc [ 28 , 110 ( mod 28) ]
= mdc [ 28 , 26 ]
= mdc [ 26 , 28 ( mod 26) ]
= mdc [ 26 , 2 ]
= mdc [ 2 , 26 ( mod 2 ) ]
= mdc [ 2 , 0 ]
mdc ( 248,110 ) = 2 .
Como mdc ( 248, 110) é diferente de 1, temos que os números 248 e
110 não são primos entre si.
a) 1175 e 381
mdc (1175, 381) = mdc [ 381 , 1175 ( mod 381) ]
= mdc [ 381, 32 ]
= mdc [ 32, 381 ( mod 32) ]
= mdc [ 32, 29 ]
= mdc [ 29, 32 ( mod 29) ]
= mdc [ 29, 3 ]
12
MATEMATICA APLICADO A CRIPTOGRAFIA - CURSOS DE SEGURANÇA DA INFORMAÇÃOPROFº VALDIR ZIMBA
= mdc [ 3, 29 ( mod 3 ) ]
= mdc [ 3 , 2 ]
= mdc [ 2, 3 ( mod 2 ) ]
= mdc [ 2, 1 ]
= mdc [ 1 , 2 ( mod 1) ]
= mdc [ 1, 0 ]
mdc ( 1175, 381 ) = 1.
Temos que 1175 e 381 são primos entre si.
4.4 - ALGORITMO ESTENDIDO DE EUCLIDES
Determinar o mdc entre dois números “a” e “b” não é suficiente para um
algoritmo ser utilizado na criptografia assimétrica, o método de Euclides apesar
de eficaz na determinação do mdc é inoportuno na prática porque quando os
números “a” e “b” assumirem valores grandes o tempo de processamento para
as divisões aumenta e o armazenamento dos resto na memória do computador
se torna oneroso. Ou seja, na prática, o algoritmo simples de Euclides é pouco
útil na aplicabilidade criptográfica.
Outra propriedade importante que precisava ser explorada era a equação de
coeficientes inteiros que é formada com o mdc entre “a” e ”b” e dois
parâmetros, que denominaremos: ""α e ""β . O grande matemático da
antiguidade, Diafante, apresentou a equação: bad .. βα += , onde ""α , ""β e
“d” são números inteiros sendo “d” o mdc entre os números “a” e ”b”.
Analisando a equação notamos que para que isso ocorra é necessária que ""α
ou ""β seja um número negativo. O fascinante e incrível, é que a definição de
número negativo não era conhecida na época que o matemático Diafante
viveu.
Segundo Coutinho (2000), foi o matemático D. E. Knuth que, em 1981,
apresentou a modificação no algoritmo de Euclides para que fosse possível o
cálculo, simultâneo, dos parâmetros ""α , ""β e “d”. Com isso, o novo algoritmo
passou a ser conhecido como algoritmo estendido de Euclides. Conforme visto
na tabela-4.
13
MATEMATICA APLICADO A CRIPTOGRAFIA - CURSOS DE SEGURANÇA DA INFORMAÇÃOPROFº VALDIR ZIMBA
Tabela-4 Algoritmo Estendido de Euclides
Resto Quociente Parâmetro ""α Parâmetro ""β
a * 1 0
b * 0 1
1r 1q 1 – ( 1q ).0 = 1α 0 – ( 1q ).1 = 1β
2r 2q 0 – ( 2q ).( 1α ) = 2α 1 – ( 2q ).( 1β ) = 2β3r 3q 1α – ( 3q ).( 2α ) = 3α 1β – ( 3q ).( 2β ) = 3β
),( bamdc nq 2−nα - ( nq ).( 1−nα ) =
nα2−nβ - ( nq ).( 1−nβ ) = nβ
0 1+nq 1+nα 1+nβ
Cada linha do algoritmo estendido de Euclides valida uma equação do Diafante
e na penúltima linha o resto representa o m.d.c. entre os números “a” e “b”.
Primeira linha a = a. (1) + b.(0) .
Segunda linha b = a.(0) + b.(1) .
Penúltima linha mdc (a,b) = a.( nα ) + b.( nβ )
Quando o máximo divisor comum entre “a” e “b” for igual a unidade , mdc(ab)
= 1 , é possível concluir que os números “a” e “b” são primos entre si
( primos relativos).
A conseqüência do fato do m.d.c.(a,b) = 1, é que o número “b” e o parâmetro
""β são inversos multiplicativos. Para fins criptográficos os números inversos
multiplicativos serão utilizados como parâmetros das chaves assimétricas no
algoritmo de chave pública.
Exemplo:
1) Determinar o mdc entre a e b e os parâmetros ""α e ""β . Sendo a
= 11243 e b = 643.
Resto Quociente Parâmetro ""α Parâmetro ""β11243
643
312
*
*
17
1
0
1 - 17. 0 = 1
0
1
0 – 17. 1 = -17
14
MATEMATICA APLICADO A CRIPTOGRAFIA - CURSOS DE SEGURANÇA DA INFORMAÇÃOPROFº VALDIR ZIMBA
19
8
3
2
1
2
16
2
2
1
0 - 2 .1 = -2
1 - 16 .(-2) = 33
-2 - 2 .( 33) = -68
33 - 2. (-68) = 169
- 68 – 1.( 169) = -237
1 – 2.(-17) = 35
-17 - 16.(35) = -577
35 - 2.(-577) = 1189
-577 – 2.(1189) = -2955
1189 – 1.(-2955) = 41440 2
Temos que mdc( 11243 , 643 ) = 1 , 237−=α e 4144=β .
Se o mdc (a,b) = 1 então os números a e b são primos entre si.
VALIDAÇÃO:
Aplicando a equação do Diafante na linha do M.D.C. é possível
efetuar a validação do processo: m.d.c (a,b) = a. α + b. β .
Ou seja: 1 = 11243. (-237) + 643.(4144), o que valida os resultados
encontrados.
4.5 -TAMANHO DE UM NÚMERO ( TAM X )
O tamanho ou ordem de um número é a quantidade de dígitos
utilizada para representá-lo. Sendo a potência nbX = , é possível determinar a
ordem do número por meio da fórmula: bnXTAM log.= . Ou seja: o
tamanho do número “x” é igual ao menor inteiro do produto do expoente “n”
pelo logaritmo da base “b”.
Graficamente:
Exemplo:
Calcule tamanho do número 1045123=X .
123log.1045=XTAM
08990,21045 ⋅=XTAM
455,3029=XTAM
3030=XTAM
n . log b TAM X
15
MATEMATICA APLICADO A CRIPTOGRAFIA - CURSOS DE SEGURANÇA DA INFORMAÇÃOPROFº VALDIR ZIMBA
O número tem 3030 posições (dígitos).
4.6 -TEOREMA DA FATORAÇÃO ÚNICA (TFU)
A operação de divisão entre números inteiros é uma resposta da
teoria numérica para expressar as situações do dia-a-dia que o homem
enfrenta na tentativa de analisar o que lhe cerca. Fazendo uma correção com a
Química e com a Biologia os números são os átomos ou os genes e em seu
D.N.A. aparecem sementes numéricas, os número primos.
Decompor um número em fatores é um processo investigativo que
busca encontrar as sementes que formam esse número, nesse processo é
utilizado os conceitos de múltiplos e divisores. Um número “a” é múltiplo de
outro “b” quando existir um “k” pertencente ao conjunto dos números inteiros tal
que, Zkcombka ∈= ,. . O número “b” é divisor número “a” quando
a (mod b) = 0, isso implica que o resto da divisão de “a” por “b” é zero.
Simbolicamente temos que: Zkcombkaab ∈=⇒ . .
Os números podem ser classificados em primos e não primos
(compostos). Os números primos têm em seu conjunto de divisores apenas
quatro números inteiros, sem dois desses números positivos e dois negativos.
Ou seja: sendo “n” um número inteiro e D(n) o conjunto dos
divisores primos de “n” . Se D(n) = {-1,+1,-n,+n} , então “n” é um número
primo. Quando o conjunto D(n) = {-1,+1, .,-p, +p, -q, +q,..., -n, +n} , com “p” e
“q” primos , então “n” é um número composto.
Coutinho (2000), traz o teorema da fatoração única mostrando que
todo número inteiro composto pode ser decomposto em fatores primos. Ou
seja: i
ippppn αααα ..... 321
321= , temos que "" p é primo, “ iα ” é a multiplicidade dos
primos (quantidade de vezes que o número primo apareceu na decomposição
do número “n”.
O conjunto dos números primos é infinito, com exceção do número
dois, todo primo é ímpar. No universo da criptografia assimétrica serão
considerados apenas os primos positivos. p: { 2, 3, 5, 7,11,13,17, ....} . O
número “1” não é considerado primo nem composto, porque não se encaixa
em nenhuma das duas definições.
16
MATEMATICA APLICADO A CRIPTOGRAFIA - CURSOS DE SEGURANÇA DA INFORMAÇÃOPROFº VALDIR ZIMBA
A criptografia assimétrica, baseada na fatoração de números primos,
tem sua segurança calcada no princípio de que é extremamente fácil obter um
número composto, sendo suficiente para isso, a multiplicação de dois ou mais
números primos, porém, paradoxalmente, é pouco trivial a obtenção dos
números primos que formaram um número composto. A fatoração, por
decomposição de primos, é o caminho natural para obtenção dos primos que
formaram um determinado número. Porém, a decomposição por primos, para
números grandes é tarefa, na prática, impossível devido a necessidade tempo
e capacidade computacional para efetuar a operação de divisão dos números.
O ataque por fatoração necessita que sejam efetuadas divisões
entre números muito grandes e em um vasto espaço de pesquisa. Como o
número “n” deve ser dividido por fatores primos, existe o agravante de não ser
fácil a escolha dos primos que vão participar da fatoração. O processo de
fatoração é eficaz, porém na prática não é eficiente, sobre tudo quando se
tratar de números com mais de cem posições., Como é o caso dos números
que compõe as chaves dos algoritmos de chaves públicas.
4.6.1- INEFICIENCIA PRÁTICA DA FATORAÇÃO.
Para viabilizar a construção de algoritmo de chaves assimétricas um
dos caminhos seguidos pelos pesquisadores foi gerar chaves por meio do
produto de primos. É possível notar que para ser gerado um número composto
basta que sejam multiplicados dois ou mais números primos, porém determinar
os números primos que geraram um número composto não é tarefa fácil e
dependendo do tamanho do número a tarefa é impossível.
Vamos supor que um número ímpar “n” de 256 posições,
aproximadamente, n = 25610 . Para atacar o número “n” por fatoração é
necessário que seja efetuada a fatoração até a raiz quadrada de “n” , desta
forma o número máximo de divisões é 25610 ou 12810 . É provável que a
capacidade computacional atual esteja na ordem de 1210 divisões por
segundo, com isso, é possível calcular o tempo necessário para que o ataque
por fatoração, a um número de 256 posições, seja efetivado.
O tempo para efetivação do ataque é determinado pelo quociente
entre o número máximo de divisões ( 12810 ) e a capacidade computacional
17
MATEMATICA APLICADO A CRIPTOGRAFIA - CURSOS DE SEGURANÇA DA INFORMAÇÃOPROFº VALDIR ZIMBA
para divisões ( 1210 ). segT 1161212812
128
101010
10 === − . Para que se tenha
a noção de quanto tempo esse valor representa, 3110 segundos equivale a um
Big-Bem2. Ou seja, atacar por força bruta um número de 256 posições requer
um espaço de tempo igual a quase quatro vezes o tempo decorrido do início da
formação do universo até agora. Isso na prática é impossível, o que torna
seguro um algoritmo baseado na dificuldade de fatoração de números primos.
4.7- FATORAÇÃO POR FERMAT
A formação dos números sempre fascinou e motivou pesquisa entre
os matemáticos ou entre os apaixonados pela teoria numérica. Fermat
(1601-1665) , apesar de ser advogado e jurista, deixou muitas contribuições no
campo da teoria numérica. O grande mérito de Fermat foi conceber um
processo de pesquisa onde não é necessário saber se o número é ou não
primo para que possa participar do processo de fatoração. O algoritmo de
fatoração idealizado por Fermat é uma busca exaustiva por dois números
inteiros que quando operados por adição e subtração determinam os primos
que formaram o número ímpar “n”. Caso os números inteiros não sejam
encontrados, é possível concluirmos que o número ímpar “n” é primo. Ou seja,
o algoritmo de Fermat é um gerador de números primos.
Tabela-5 Algoritmo de fatoração do Fermat
Sendo “n” um número Ímpar tal que n = (x + y) . (x – y), com x e y pertencentes aos inteiros .Temos: nxynxyyxn −=⇒−=⇒−= 22222
1 O algoritmo é iniciado com extração da raiz quadrada de “n”.
2
Se n for um número inteiro, então a fatoração é imediata nnn ⋅=
O algoritmo pára porque “n” é um número quadrado perfeito e sua fatoração é o produto das raízes. 3
Se n não for um número inteiro, então x = n
4 Enquanto nxy −= 2 , for um número não inteiro e
2
1+< nx , incrementa-se x em uma unidade
2 Big-Bem. Tempo transcorrido do inicio da formação do universo até hoje.
18
MATEMATICA APLICADO A CRIPTOGRAFIA - CURSOS DE SEGURANÇA DA INFORMAÇÃOPROFº VALDIR ZIMBA
5 Quando nxy −= 2 , for um Número inteiro, então a fatoração de “n” é igual ao produto de ( x + y ) por ( x – y ).
6 Caso aconteça de
2
1+= nx , então o algoritmo pára e informa que o número “n” é primo.
5 - ARITMÉTICA MODULAR
Os fenômenos cíclicos não são explicados pela aritmética linear. Quando
estamos somando as horas do dia (17 + 10) é equivalente à 3 horas, isso
porque o dia só tem 24 horas. A aritmética modular possibilita a comparação
entre dois ou mais números inteiros e seus respectivos lugares em uma espira
circular. A reta numérica quando comparada com uma circunferência repleta de
19
MATEMATICA APLICADO A CRIPTOGRAFIA - CURSOS DE SEGURANÇA DA INFORMAÇÃOPROFº VALDIR ZIMBA
números evidencia uma família de números que estão alocados sobre o
mesmo espaço na circunferência. Mais precisamente, para cada volta numérica
que a reta faz sobre a circunferência gera infinitos números equivalentes.
Portanto, a aritmética modular modela os fenômenos cíclicos e para o estudo
da criptografia assimétrica é fundamental o entendimento das divisões e das
relações de equivalentes geradas no estudo da aritmética modular. Para a
criptografia assimétrica a possibilidade de escolher pares de números inversos
mutiplicativos dentro de grupos modulares torna possível a codificação com
uma chave e a decodificação com outra chave inversa à primeira.
5.1- RELAÇÃO DE EQUIVALÊNCIA
Seja um conjunto K um conjunto finito ou infinito e uma “r” uma relação entre
os elementos do conjunto K . Para “r” ser uma relação de equivalência em K é
necessário que para quaisquer x, y e z pertencentes ao conjunto K as três
propriedades a seguir sejam satisfeitas :
1) propriedade reflexiva : x r x;
2) Propriedade simétrica: Se x r y , então y r x;
3) propriedade transitiva: Se x r y e y r z , então x r z.
Exemplo:
1) Considerando “Z” o conjunto dos números inteiros e a operação
“=” efetuada com os elementos de “Z” . Temos que x, y e z são
números do conjunto Z, portanto:
2) x = x , qualquer que seja “x” do conjunto Z;
3) Se x = y, então y = x para todo x e y inteiro.
4) Se x = y e y = z , então x = z ; para todo x, y e z que pertençam
aos inteiros.
Temos então que a operação “=” é uma relação de equivalência
dentro do conjunto Z.
Apesar de parecer obvio, nem toda operação é relação de equivalência dentro
do conjunto Z. Um exemplo disso é a operação “>” :
20
Recommended