1  Consultar  Anexos   1  

  CRIPTOLOGIA:  Álgebra  Linear  aplicada  às  cifras  de  substituição     Projeto  desenvolvido  para  apresentação  na  prova  oral  de  Álgebra  Linear  

  Gonçalo  Aguiar     Instituto  Superior  Técnico  

  Mestrado  Integrado  em  Engenharia  Aeroespacial  

  Semestre  1,  2012/2013  

A   primeira   utilização   de   criptografia   de   que   se   tem   conhecimento   remonta   a   1900   AC,   no   Egito,   e   até   ao   século   XIX  

manteve  um  caráter  bastante  simplista,  com  o  papel  e  o  lápis  no  pedestal  dos  mecanismos  de  encriptação.  Foi  só  no  século  

XX  que  se   tornou  vulgar  a   invenção  e  utilização  de  aparelhos  eletromecânicos  complexos,  capazes  de   fornecer  meios  de  

codificação  bastante  mais  sofisticados  e  eficientes.  Tem-­‐se  como  exemplo  de  renome  a  Enigma,  a  famosa  máquina  utilizada  

pelos   Nazis   durante   a   2ª   Guerra   Mundial.   Recentemente   a   criptografia   tornou-­‐se   mais   abrangente:   deixou   de   estar  

estritamente   relacionada   com   a   confidencialidade   e   passou   a   ter   aplicações   muito   importantes   a   nível   eletrónico   e  

computacional,  tais  como  a  verificação  da  integridade  de  mensagens.  

O  método  de  criptologia  aqui  tratado  é  aplicável  a  cifras  de  substituição,  em  que  cada  letra  do  alfabeto  é  substituída  por  

outra,   sem  ambiguidade.  Para   facilitar   a   compreensão  dos  procedimentos,   será  utilizada   a   título  de   exemplo   a   seguinte  

mensagem  codificada:  

NENIQNEODEMNIDOENEEPJNXNZDERSOZNDAPZOJVNXWINPNXSEPVNJNWDIQNIOEJSJANNJVOEJNHOBNZDEWNEENIN

QNPJZNNXOQZNVINWIDMNJNOQWOIPBDEOBSOIINEOElDIANZDEQNPEZDRSOWIDQOVPNNLDIANYSQNJNOOJVIOBOJVO

IOQDVNOZPLPANINQJDHDIOPJDRSOVNJVDESMXPQNINQ.  

A  primeira  fase  consiste  em  categorizar  as  letras  da  mensagem  em  vogais  e  consoantes.  Para  isso,  é  necessário  construir  

uma  matriz  com  a  frequência  absoluta  de  todos  os  pares  de  letras,  ou  seja,  uma  matriz  quadrada,  26x26,  em  que  a  entrada  

aij  corresponde  ao  número  de  vezes  que  a  letra  associada  à  linha  i  e  a  letra  associada  da  coluna  j  aparecem  seguidas  e  por  

esta  ordem.1  

O  facto  crucial  para  que  seja  possível   fazer  a  categorização  é  o  chamado  princípio  vfc:  na  grande  maioria  das   línguas,  os  

pares  consoante-­‐vogal  são  mais  frequentes  que  os  pares  vogal-­‐vogal.  Se  pensarmos  no  alfabeto  como  um  conjunto  de  dois  

vetores  coluna,  v  e  c,  em  que  as  entradas  de  v  são  1  para  linhas  que  representam  vogais,  e  0  para  linhas  que  representam  

consoantes    (o  oposto  para  c),  é  possível  escrever  o  princípio  vfc  matematicamente:  

nº  pares  vogal-­‐vogalnº  vogais

<nº  pares  consoante-­‐vogal

nº  consoantes⇔  

!!!"!!! ! + !

<!!!"

!!! ! + !⇔ !!!" !!!" − !!!" !!!" < 0      (1)  

A  decomposição  dos  valores  singulares  é  útil  nesta  fase  para  que  A  possa  ser  aproximada  por  uma  soma  finita.  Tendo  em  

conta  que  A  é  quadrada,  e  sendo  !! , !! ,∀  ! ∈ 1,… , 26  os  vetores  próprios  à  esquerda  e  à  direita,  respetivamente:    

! = !Σ!! =  !! … !!"| … |

!! ⋯ 0⋮ ⋱ ⋮0 ⋯ !!"

!!! —⋮ ⋮!!"! —

= !!!!!!! +⋯+  !!"!!"!!"!                    (2)  

Se   os   primeiros   dois   valores   singulares   de   A   forem   significativamente   maiores   que   os   restantes,   então   A   pode   ser  

aproximada  por  !!!!!!! +  !!!!!!! .  Substituindo  na  equação  (1)  tem-­‐se  

1  Consultar  Anexos   2  

!! !!!!!!! +  !!!!!!! !!! !!!!!!! +  !!!!!!! ! − !! !!!!!!! +  !!!!!!! !!! !!!!!!! +  !!!!!!! ! < 0⇔                                                    

⇔ !!!! !!!! !!!! !!!! !!!! + !!!! !!!! !!!! !!!! − !!!! !!!! !!!! !!!! − !!!! !!!! !!!! !!!! < 0  

Pelo  Teorema  de  Perron-­‐Frobenius,  se  as  entradas  de  A  são  não-­‐negativas  então  as  entradas  de  x1  e  y1  são  simultaneamente  

todas  negativas  ou  todas  positivas.  Neste  caso  x1  e  y1  têm  ambos  entradas  negativas,  pelo  que  os  fatores  a  vermelho  serão  

necessariamente  negativos.  Resta-­‐nos  agora  definir  os  vetores  v  e  c  de  modo  que  a  condição  acima  seja  verdadeira,  ou  seja,  

que  se  verifique  o  princípio  vfc.  Se  definirmos  

!! =1, !!! < 0   ∧  !!! > 00, !"#$  !"#$%á!"#                      !! =

1, !!! > 0   ∧  !!! < 00, !"#$  !"#$%á!"#                      !! =

1, !"#$%(!!!) = !"#$%(!!!)0, !"#$  !"#$%á!"#                                

tornamos  os   fatores   a   verde  positivos   e   os   fatores   a   azul   negativos,   fazendo   com  que  o   lado   esquerdo  da   inequação   se  

torne  menor  que  0,   tal  como  pretendido.  Os  vetores  c  e  v  resultantes  da  definição  agrupam  a  grande  parte  das   letras  da  

mensagem  em  vogais  ou  consoantes.1  O  vetor  n  indica  as  letras  a  que  não  é  possível  atribuir  categoria.  

A  segunda  fase  consiste  na  análise  da  frequência  relativa  de  cada  letra  na  mensagem  e  na  comparação  destes  valores  com  

os  valores   tabelados,  referentes  àquilo  que  se  verifica  em  muitos  dos   textos  escritos  em  Português.  Para   isso  recorre-­‐se  

aos  vetores  próprios  x1   e  y1,   a  partir  dos  quais  é  possível   construir  vetores  x’1   e  y’1   cujas  entradas  são  aproximações  da  

frequência  relativa  das  diferentes  letras.1  

!!! =!!!!!!"

!!!×100%                                        !!! =

!!!!!!"

!!!×100%  

Por   fim,   é   útil   recorrer   a   um   destes   vetores   para   traçar   gráficos,   pois   são   estes   que   nos   permitem   tirar   as   conclusões  

fulcrais  à  resolução  do  problema.1  Em  primeiro  lugar,  verificamos  que  só  foi  atribuída  a  categoria  de  vogal  a  quatro  letras.  

Sabendo  que  o  alfabeto  português  tem  cinco  vogais  e  que  as  mesmas  são  bastante  frequentes  num  texto,  podemos  assumir  

que  a  letra  do  vetor  n  com  maior  frequência  corresponde  à  vogal  não  identificada.  De  seguida,  colocando  as  vogais,  as  seis  

consoantes   mais   frequentes   e   as   seis   letras   inexistentes   na   mensagem   por   ordem   decrescente   de   frequência,   e  

comparando  com  a  ordem  tabelada,  obtém-­‐se  o  seguinte  resultado:  

 

 

Se  substituirmos  a   letra  no   texto  pela   letra  correspondente  na   língua  portuguesa  obtemos,   infelizmente,  um  texto  ainda  

codificado.  A  subtileza  final  está  em  reparar  que  a  frequência  das  letras  e  e  i  na  mensagem  é  bastante  semelhante,  apesar  

de   a   frequência   das   letras   s   e   r   nos   textos   em   português   ser   significativamente   diferente.1   Se   assumirmos   que   esta  

correspondência  está  trocada,  corrigirmos  o  erro  e  aplicarmos  espaços  onde  nos  parecer  indicado:  

 

 

 AS  ARMAS  E  OS  ☐AROES  ASSINA☐ADOS  ☐UE  DA  O☐IDENTA☐  ☐RAIA  ☐USITANA  ☐OR  MARES  NUN☐A  ANTES  NA☐E☐ADOS  

☐ASSARAM  AINDA  A☐EM  DA  TRA☐RO☐ANA  EM  ☐ERI☐OS  E  ☐UERRAS  ES☐OR☐ADOS  MAIS  DO  ☐UE  ☐ROMETIA  A  ☐OR☐A  

☐UMANA  E  ENTRE  ☐ENTE  REMOTA  EDI☐I☐ARAM  NO☐O  REINO  ☐UE  TANTO  SU☐☐IMARAM.  

  Vogais   Consoantes   Não  categorizadas  Na  mensagem   n   o   d   p   s   e   i   j   q   z   v   g   k   u   c   f   t  No  português   a   e   o   i   u   s   r   n   m   d   t   z   j   x   k   w   y  

  Vogais   Consoantes   Não  categorizadas  Na  mensagem   n   o   d   p   s   i   e   j   q   z   v   g   k   u   c   f   t  No  português   a   e   o   i   u   s   r   n   m   d   t   z   j   x   k   w   y  

1  Consultar  Anexos   3  

Resta  agora  um  simples  exercício  de  coerência:  substituir  as  letras  em  falta  pelas  apropriadas,  acrescentar  acentos  gráficos  

e  dar  ao  texto  o  aspeto  que  lhe  é  característico:  

As  armas  e  os  barões  assinalados  

Que,  da  ocidental  praia  lusitana,  

Por  mares  nunca  antes  navegados  

Passaram  ainda  além  da  Traprobana,  

Em  perigos  e  guerras  esforçados,  

Mais  do  que  prometia  a  forca  humana,  

E  entre  gente  remota  edificaram  

Novo  reino  que  tanto  sublimaram.  

 

 

 

BIBLIOGRAFIA  

Honn,  T.,  Stone,  S.  (13  de  Dezembro  de  2002).  SVD  and  Cryptograms.  Obtido  a  14  de  Janeiro  de  2013,  de  

http://online.redwoods.cc.ca.us/instruct/darnold/laproj/Fall2002/TimSeth/paper.pdf  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  4  

 

ANEXOS  

Nota:  os  valores  de  ordem  igual  ou  inferior  a  10-­‐16  devem  ser  tratados  como  iguais  a  0,  pois  resultam  de  erros  de  aproximação.  

   

 

 

 

 

 

 

 

       A  =  

 

 

 

 

 

 

 

                   

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  x1                                                    y1                                                                                                                                              x2                                                                                              y2          

(a. b. c. d. e. f. g. h. i. j. k. l. m. n. o. p. q. r. s. t. u. v. w. x. y. z.)

  5  

 

                                             Nota:  os  gráficos  foram  traçados  unicamente  a  partir  das  entradas  do  vetor  y’1.                                                          

   v                      c                      n                                                                                                          x'1                                                  y’1                                                                                                                                

0  2  4  6  8  10  12  14  16  18  

n   o   d   p   s  Frequência  relativa  (%

)  

Vogal  

0  

2  

4  

6  

8  

10  

12  

i   e   j   q   z   v   x  w  a  b   l   h   r   s  m  y   g  k  u   c   f   t  Frequência  relativa  (%

)  

Consoante  

0  

1  

2  

3  

4  

5  

6  

p   v   w   a   g   k   u   c   f   t  Frequência  relativa  (%

)  

Letra  não  categorizada  

Letras  no  Português