O Algoritmo usado no programa de criptografia PASME

This work present the main encryption's algorithm of the PASME tool. This software allows encrypt and hide an information in various types of files. The algorithm uses the fact that factoring large numbers is a difficult issue in terms of
of 2

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Tags
Transcript
    a  r   X   i  v  :   1   1   0   1 .   0   8   2   7  v   1   [  c  s .   C   R   ]   4   J  a  n   2   0   1   1 1 O Algoritmo Usado No Programa de Criptografia PASME P´ericles Lopes Machado  Abstract —This work will present the main encryption algo-rithm of the PASME tool, PASME allows encrypt and hideinformation in various types of files. The algorithm uses thefact that factoring large numbers is a difficult issue in termsof computational performing to make the main steps of theencryption.  Resumo —Neste trabalho ser´a apresentado o principal algo-ritmo de criptografia da ferramenta PASME, a qual permiteencriptac¸ ˜ ao e ocultamento de informac¸ ˜ oes em diversos tipos de arquivos. O algoritmo utiliza o fato da fatorac¸ ˜ ao de n´umerosgrandes ser um problema dif´ıcil do ponto de vista computacional,efetuando assim, os principais passos da encriptac¸ ˜ ao.  Palavras-chave —Criptografia, Teoria dos n´umeros, Teoria dainformac¸ ˜ ao I. I NTRODUC ¸ ˜ AO A ideia fundamental de qualquer algoritmo de criptografia´e modificar a representac¸˜ao de uma informac¸˜ao para garantir protec¸˜ao contra acesso indevidos.No decorrer dos anos, muitos algoritmos de criptogra-fia foram desenvolvidos. Um dos mais antigos realiza umapermutac¸˜ao no alfabeto que cont´em todos os s´ımbolos damensagem que ser´a encriptada. Contudo, este algoritmo apre-senta grande vulnerabilidade a uma an´alise da frequˆencia deocorrˆencia de determinados s´ımbolos, principalmente quandoaplicados `a textos escritos.Outro m´etodo cl´assico, usado em mensagens bin´arias, con- siste em inverter certos bits e armazenar a posic¸˜ao dos bitsque foram invertidos em outra palavra, a folha-chave, como mesmo tamanho da mensagem que foi encriptada. Umproblema desse m´etodo ´e que o tamanho da folha-chave podeser muito grande, inviabilizando o processo de encriptac¸˜ao.Muitos algoritmos modernos utilizam estrat´egias envol-vendo teoria dos n´umeros atrav´es da utilizac¸˜ao de problemas que atualmente s˜ao intrat´aveis do ponto de vista computacio-nal. Um exemplo cl´assico desta classe de algoritmo ´e o RSA[2] [3].A ideia do presente trabalho ´e utilizar a intratabilidade dafatorac¸˜ao de inteiros grandes para realizar os passos-chavede sua encriptac¸˜ao. Nas pr´oximas sec¸˜oes, ser˜ao descritos os passos realizados pelo algoritmo de encriptac¸˜ao PASME, al´emde serem comentados alguns detalhes de sua implementac¸˜ao[1].II. A LGUMAS FUNC ¸ ˜ OES FUNDAMENTAIS  A. A func¸˜ ao  ∓  (inflar) A ideia fundamental do algoritmo PASME ´e a mudanc¸ana base de representac¸˜ao de um n´umero. Mudar a base de Laborat´orio de An´alises Num´ericas em Eletromagnetismo (LANE), Uni- versidade Federal do Par´a, caixa postal 8619, CEP 66073-900, Brasil; e-mail:pericles.machado@itec.ufpa.br representac¸˜ao de um n´umero inteiro  n  =  a 0 a 1 a 2 ...a k  para abase  b  consiste em realizar a operac¸˜ao descrita na equac¸˜ao 1 T  ( n,b ) =  a 0 b k +  a 1 b k − 1 +  ...  +  a k b 0 (1)A func¸˜ao  ∓  descrita em 2 ´e uma mudanc¸a de base onde a cada digito ´e adicionado um ”lixo”. ∓ ( n,b,v ) = ( a 0 + c 0 ) b 1 +( a 1 + c 1 ) b 2 + ... +( a k + c k ) b k +1 (2)Onde  c i  ´e descrito na equac¸˜ao 3. c i  =   ⊲ ( v )  ,se i  = 0 ⊲ ( c i − 1 )  ,se i >  0  (3)Nas equac¸˜oes 2 e 3,  ⊲ ( x )  ´e o pr´oximo primo depois de  x ,  v ´e um inteiro qualquer,  n  ´e a informac¸˜ao representada na formade um inteiro,  a k  ´e um digito de  n  na base srcinal e  b  ´e abase alvo.  B. A func¸˜ ao  ±  (sujar) ±  ´e semelhante a func¸˜ao  ∓ , s´o que o ”lixo” v  usado ´e omesmo em todos d´ıgitos, conforme pode ser visto na equac¸˜ao4. ± ( n,b,v ) = ( a 0  + v ) b 0 +( a 1  + v ) b 1 + ... +( a k  + v ) b k (4)III. O  ALGORITMO DE ENCRIPTAC ¸ ˜ AO  PASMEA seguir, ser˜ao descritos os procedimentos para encriptarou desencriptar uma mensagem usando o algoritmo PASME.O algoritmo  PASME  ( n,key )  encripta uma mensagem  n usando a frase-chave  key .  A. Encriptando uma mensagem O processo de encriptac¸˜ao inicia com a gerac¸˜ao de 7n´umeros aleat´orios (de preferˆencia, grandes)  r i ,i  = 1 ... 7 . Emseguida, s˜ao definidos 4 n´umeros  K  i  =  ⊲ ( r i ) , para  i  = 1 ... 5 e  i  = 3 ,  K  3  =  ⊲ ( K  5  + d max  + r 3  +1) ,  d max  ´e o maior digitoda base em que a informac¸˜ao srcinalmente est´a representada.Para continuar o processo de encriptac¸˜ao, uma frase-chave key  tem de ser fornecida. Usando-se a frase-chave, s˜aogerados os n´umeros  W   =  ∓ ( key,K  3 ,K  2 ) +  K  1 ,  Q  = ⊲ ( ± ( n,K  3 ,K  5 )+ r 7 ) ,  P   =  WQ + K  4 , e  X   = ± ( n,K  3 ,K  5 ) xor  Q .  X   ´e a mensagem  n  encriptada.As informac¸˜oes divulgadas s˜ao os n´umeros  K  i ( i  = 1 ... 5) , P   e  X  .  2  B. Desencriptando uma mensagem Para desencriptar uma mensagem, ´e preciso que sejamfornecidos os n´umeros  K  i ( i  = 1 ... 5) ,  P   e  X  , al´em da frase-chave  key .O primeiro passo da desencriptac¸˜ao ´e a validac¸˜ao da chave, para realizar essa operac¸˜ao, gera-se o n´umero  W  ′ = ∓ ( key,K  3 ,K  2 ) +  K  1  e ´e verificado se  P   mod  W  ′ =  K  4 .Efetuada a validac¸˜ao, pode-se recuperar  Q  = ( P   − K  4 ) /W  ′ .Com  Q  recuperado, a mensagem  n  ocultada em  X   poder´aser revelada. Para revelar a mensagem  n , gera-se o n´umero Y   =  X   xor  Q  e o procedimento descrito a seguir tem de serefetuado.1)  X  ′ = ∅ ,  X  ′ ´e uma palavra vazia2) Enquanto Y   =  0:a)  a ← Y   mod  K  3 b)  Y   ← Y   − a c)  Y   ←  Y/K  3 , efetua-se a divis˜ao inteira de  Y   por K  3 .d)  a ← a − K  5 e)  X  ′ ← X  ′ ⊕ a , ⊕  ´e a operac¸˜ao de concatenac¸˜ao, ou seja, a uni˜ao de duas palavras (por exemplo, 33 ⊕ 5 = 335 ).3)  X  ′ ´e a mensagem desencriptadaIV. C OMENT ´ ARIOS SOBRE A IMPLEMENTAC ¸ ˜ AO DE  PASME DISPON ´ IVEL EM  [1]Em [1] est´a dispon´ıvel uma implementac¸˜ao do algoritmode criptografia descrito na sec¸˜ao III. Essa implementac¸˜ao utiliza a biblioteca GMP [4] para realizar as operac¸˜oesenvolvendo inteiros presentes no algoritmo PASME. Comoa ferramenta [1] permite encriptar arquivos com tamanhovari´aveis, usar o algoritmo PASME nem sempre ´e uma boaescolha, j´a que dependendo do tamanho da mensagem o tempode execuc¸˜ao pode ser alto. Ent˜ao, por quest˜oes de eficiˆencia, a implementac¸˜ao [1] utiliza o processo de encriptac¸˜ao de doispassos descrito a seguir para encriptar uma mensagem  n .1) Gera-se uma folha-chave  fc  com um tamanho de  L ( fc ) bytes.2) Cria-se aleatoriamente uma frase-chave key  com  L ( key ) bytes de tamanho.3) Utiliza-se o algoritmo descrito em III para encriptar afolha-chave  fc .4) Quebra-se a mensagem  n  em  L ( n )  bytes,5)  i ← 0 6)  k  ← 0 7)  X   ←∅ 8) Enquanto  i ≤ L ( n ) :a)  X   ←  X   ⊕  ( n i  xor  fc k ) ,  n i  ´e i-´esimo byte damensagem  n  e  fc k  ´e o k-´esimo byte da folha-chave fc .b)  i ← i  + 1 c)  k  ← ( k  + 1)  mod  L ( fc ) Para desencriptar, o passo (1) do algoritmo anterior n˜ao´e executado, no passo (2) ´e fornecido a frase-chave que”abre”a mensagem e no passo (3) ´e chamado o algoritmo dedesencriptac¸˜ao descrito em III. Na implementac¸˜ao [1], cada simbolo (digito num n´umero)tem 1 byte (8 bits) de comprimento.A implementac¸˜ao [1] armazena em um arquivo-alvo asinformac¸˜oes p´ublicas geradas pelo algoritmo III e a mensagem X   gerada pelo procedimento anterior.Para ocultar informac¸˜oes em arquivos, [1] primeiramenteverifica o tamanho, em bytes, da informac¸˜ao que ser´a ocultada.Ap´os isso, a informac¸˜ao ´e concatenada ao arquivo e, por fim, concatena-se o tamanho da informac¸˜ao (em [1], um inteirocom 4 bytes de comprimento). O procedimento para recuperara informac¸˜ao ´e semelhante, s´o que, primeiramente, recupera- se o tamanho  L  (em [1], os 4 ´ultimos bytes do arquivo) dainformac¸˜ao que est´a oculta, depois recua-se  L − 4  bytes a partirdo fim do arquivo, no caso de [1], e armazena-se os  L  bytesseguintes em um arquivo-alvo.A interface gr´afica da implementac¸˜ao [1] foi criadautilizando-se o framework QT4 [5].V. C ONCLUS ˜ OES Este trabalho apresentou um algoritmo de encriptac¸˜ao queusa o fato da mesma informac¸˜ao ter significados distintosdependendoda base em que est´a representadae de, atualmente,certos problemas em teoria dos n´umeros serem intrat´aveis.Tal algoritmo faz parte da ferramenta PASME que permitea encriptac¸˜ao e ocultamento da informac¸˜ao em arquivos nosmais diversos formatos.VI. A GRADECIMENTOS O autor agradece a Diego Aranha por apontar uma falhano algoritmo inicial, a Jo˜ao Augusto Palmitesta Neto porsugest˜oes e testes na implemtentac¸˜ao [1] do algoritmo e FabioLobato por revisar o artigo.R EFERENCES[1] “Projeto pasme,”  http://sourceforge.net/projects/pasme/  .[2] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,  Algoritmos .Editora Campus, 2002.[3] L. Lov´asz, J. Pelik´an, and K. Vesztergombi,  Matem´ atica Discreta . So-ciedade Brasileira de Matem´atica, 2003.[4] “The gnu multiple precision arithmetic library,”  http://gmplib.org/  .[5] “qt - cross platform and ui framework,”  http://qt.nokia.com/  .
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks