TEORIA DOS NÚMEROS E CRIPTOGRAFIA - 2003/04
António Machiavelo


Segunda 29/09:

Exemplos de sistemas criptográficos (continuação):  a cifra de Vigenère (séc. XVI), a cifra de Hill (1929).
Sistemas monoalfabéticos e polialfabéticos.
Block ciphers ("cifras-bloco") e stream ciphers ("cifra-fluxo"(?!)).
Linear Feedback Shift Registers (LFSRs; registos lineares com deslocamento e retro-alimentação (??!!)) e cifras-fluxo dadas por LFSRs.

T.P.C. : Implementar numa calculadora a seguinte forma completa do algoritmo de Euclides (i.e. fornecendo os coeficientes de uma combinação linear inteira que exprime o mdc de dois inteiros positivos à custa desses inteiros) [Knuth, vol. I]:

(1)  a := 0; b:=1; a' := 1; b':=0; c := m; d:=n;
(2)  q:= quociente (c:d)r:= resto(c:d);
(3)  r = 0 ? Se sim, parar e escrever a e b;
(4)  c:=d; d:=r; t:=a'; a':=a; a:=t - q*a; t:=b'; b':=b; b:=t - q*b;
(5)  Ir para (2);

Perceber porque é que este algoritmo funciona.

Quinta 2/10:

Cifras-fluxo dadas por LFSRs (continuação). Cifras-fluxo sincrónicas (keystream independente do texto; gerada apenas a partir da chave). Um exemplo de uma cifra-fluxo não-sincrónica: a cifra auto-chave.

A aula terminou com a explicação do funcionamento do seguinte algoritmo, em Maple, para codificar mensagens com a cifra de Vigenère:

K:="pois": m:=nops(convert(K,bytes)):
M:="elesnaosabemnemsonhamqueosonhoeumaconstantedavidataoconcretaedefinidacomooutracoisaqualquer":
C:="":
for i from 1 while evalb(M[i]<>"") do
  j:=i mod m: if j=0 then j:=m:fi:
  c:=convert(M[i],bytes)[1]+convert(K[j],bytes)[1]-2*97 mod 26 +97:  #...97->minusculas;65->maiusculas
  C:=cat(C,convert([c],bytes)):
od:
printf("%A",C);

T.P.C. : Perceber todos os detalhes do funcionamento do programa dado na aula e brincar com ele...