O número perdido e o número escondido

European Article Number; EAN-13

O EAN é um código de barras para identificação de produtos.

Está dividido em 4 partes:

• identificação da origem
• identificação da empresa
• identificação do produto
• dígito de controlo

560−1493−11550−6

Algoritmo the Luhn

5∗2,1∗2,3∗2,5∗2,7∗2,9∗2,1∗2,3∗2

1,2,6,1,5,9,2,6

 

1+4+2+2+6+4+1+6+5+8+9+0+2+2+6+4

Cartão de Cidadão

$$DDDDDDDDD\, d_1 \, LL\, d_2$$ $d_1$ segue o algoritmo ISBN

$LL$ indica a versão. $ZZ$, $ZY$, etc.

$A \sim 10$, $B\sim 11$, ..., $Z\sim 35$.

Número de Identificação na Segurança Social - NISS

11 algarismos, sendo o último o de controlo. NISS de Pessoa Singular começa por 1. NISS de Pessoa Colectiva começa por 2.

Por exemplo, $$12265870939$$.

Brincando aos espiões (ou a arte de esconder mensagens)

A necessidade de transmissão de informação entre dois agentes, de forma a que um terceiro não possa compreender a mensagem, leva a que, de alguma forma, esta esteja ou dissimulada ou cifrada. O primeiro método é denominado por esteganografia, e foi usado por várias civilizações antigas. Por exemplo, uma mensagem poderia ser tatuada numa cabeça rapada de um escravo, ficando escondida assim que o cabelo crescesse, é um exemplo de esteganografia usada pelos gregos antes da nossa era. Outros exemplos incluem o uso de tinta invisível, ou na era actual a inserção de ruído em fotografias digitais.

Nesta figura, está escondida a seguinte:

Figura: Apenas mantendo os últimos 2 bits da componente de cor, e aumentado o brilho. (fonte: wikipedia)

Corre o rumor que a al-Qaeda fez uso da esteganografia para comunicar com os seus membros, nomeadamente no planeamento dos ataques do 11 de Setembro.

No segundo método é aplicado, de alguma forma, um algoritmo que transforme a mensagem numa outra de tal maneira que uma terceira pessoa não a consiga interpretar. De uma forma mais ampla, a criptologia (do gregos cryptos+logos, ou esconder+ciência) divide-se em dois ramos: a criptografia, que estuda a forma de cifrar textos de forma eficiente, e a criptanálise que tenta, por seu turno, quebrar as cifras.

Um sistema criptográfico é um 5-uplo $(P,C,K,E,D)$ onde$P,C$ conjuntos finitos de símbolos

• $K$ conjunto finito de chaves
• $E,D$ conjuntos de funções de cifração/decifração, onde $$e_k:P\rightarrow C,\, d_k:C\rightarrow P$$ com $d_k(e_k(x))=x$.

Ou seja, se decifrarmos e que foi cifrado, obtemos a mensagem original.

Por exemplo, considere-se
$P=C={\cal{A}}=\left\{ A,B,C,\dots ,J,K,L,\dots V,W,X,Y,Z\right\}$, $e(\star)=$ letra que sucede a $\star$. Aplicando a função de cifração a cada letra da palavra que queremos ``esconder'',
$$BIBABRAGA\mapsto CJCBCSBHB$$

Como é óbvio, a (única) função de decifração para esta chave está definida por $d(\star)=$ letra que antecede a $\star$.

A cifra por substituição

Neste caso, consideramos $P=C= \cal{A}$. O conjunto $K$ das chaves é constituído por \textbf{todas} as trocas possíveis (permutações) de letras do alfabeto.

$$\# K=26!=403291461126605635584000000 > 4 \times 10^{26}$$


Como o número de chaves cresce de forma desmesurada em relação ao número de caracteres do alfabeto, a busca, por uma terceira pessoa, de uma função de decifração por ``força bruta'' é inviável. No entando, existem outras formas de quebrar esta cifra, fazendo uso da análise frequencista do texto cifrado. Como exemplo, considere-se a seguinte permutação $\pi \in K$:

Para cifrar ``zacarias'' basta-nos procurar a correspondência de cada letra na tabela apresentada. O resultado final é ``IXYXCZXV''.

Uma técnica criptanalítica aplicável é a do estudo  frequencista das letras. Por exemplo, em ``IXYXCZXV'' a letra ``X'' surge 3 vezes, pelo que ``X'' deve ser a correspondência das letras mais usadas em português. Torna-se, portanto, essencial  a existência de uma tabela com as frequências das letras. Essa tabela existe: a tabela de Beker e Piper.

 

O gráfico seguinte apresenta a frequência relativa das letras em português. Provavelmente ``X'' é a letra ``a'' cifrada. 

Além do estudo de frequência de letras isoladas, poder-se-ia também estudar os digramas e trigramas. Por exemplo, o digrama ``qu'' surge com mais frequência (seguramente!) que o digrama ``hn'', e a letra ``q'' surge mais vezes sucedida de ``u'' do que de outra letra. Os trigramas ``sim'' e ``nao'' são garantidamente mais frequentes que ``dsa'' e ``pot''. Estes exemplos mostram como um criptanalista pode quebrar uma cifra que tem um número demasiado alto de chaves fazendo uso da análise frequencista.

O filósofo árabe do século VIII, Abu'Abd Al-Rahman al-Khalil ibn Ahmad ibn'Amr ibn Tammam al Farahidi al Zadi al Yahmadi cuja obra Kitab al-muamma - O livro da linguagem secreta - foi inspirada pela decifração que Al-Khali l fez de um criptograma grego que o imperador bizantino lhe tinha enviado. Nessa decifração ele utilizou um método criptanalítico que se baseava na suposição do início do texto original ser ``Em nome de Deus'' ou algo semelhante (era comum na época iniciarem-se as mensagens dessa forma), demorando um mês para solucionar o problema.

Mais tarde, este método tornou-se padrão e chegou a ser utilizado na Segunda Guerra Mundial para decifrar mensagens da máquina Enigma (a que faremos referência mais adiante). A descrição mais antiga de análise de frequências explorada para quebrar cifras deve-se a Abu Yusuf Ya'qub ibn Is-haq ibn as-Sabba h ibn 'omran ibn Ismail Al-Kindi, referenciada no seu tratado, redescoberto em 1987, intitulado Risalah fi Istikhraj al Mu'amma - Um Manuscrito sobre a Decifração de Mensagens Criptográficas.

Apesar dos gregos terem escrito vários trabalhos teóricos realacionados com cifras de transposição (as letras da mensagem são reordenadas segundo um certo algoritmo) e de de substituição (as letras mantêm as sua posição mas perdem a sua identidade segundo um certo algoritmo), não se conhecem referências que as tivessem aplicado para fins militares. A primeira alusão à utilização de cifras com esses fins deve-se aos romanos - a Cifra de César. Foi esta a primeira cifra de substituição documentada, utilizada para fins militares, que surgiu na obra De Bello Gallico (Guerras Gálicas), de Júlio César (101 a.C. - 44 a.C.).

Para melhor explicarmos o funcionamento desta (e de outras) cifra, façamos uma curta referência à aritmética modular.

Em primeiro lugar, considere-se o conjunto $\mathbb{Z}_{26}=\{0,1,\dots 25\}$ identificado com $\cal{A}$, onde definimos as operação de soma e multiplicação como as operações usuais, após as quais tomamos o resto da divisão inteira por 26. Por exemplo,

$$4+7 = 11; \, \, 13+15  = 2;$$
$$25+1 =0$$

Como exemplo,
$$BIBABRAGA \equiv 01  \,08  \,01 \, 00  \,01  \,17 \, 00  \,06  \,00$$

Cifra shift

Nesta cifra, a chave $k$ é um elemento de $Z_{26}$, conhecido pelo emissor e pelo receptor.

$$e_k(x)=x+k \mod 26; \, \, \, d_k(y)=y-k\mod 26$$

O símbolo $\mod 26$ indica se que tomou o resto da divisão por 26 (para sermos mais correctos, dever-se-ia dizer que indica qualquer número que tenha o mesmo resto na divisão inteira por 26, mas preferimos cometer esta incorrecção a forçar a apresentação de mais noções modulares).


Para $k=3$ obtemos a cifra de César. Ou seja, a cada letra da mensagem fazemos corresponder, no alfabeto, aquela que está 3 posições depois.

Cifra afim

Nesta cifra, a função de cifração é dada por
$$e_k(x)=ax+b \mod 26$$
A chave, neste caso, é o par $(a,b)$.

Claro que quando $a=1$ obtemos cifra Shift. Para a implementação desta cifra, precisamos de ter algumas cautelas. Vejamos o seguinte exemplo:

$e(x)=13x+7 \mod 26$.

$e(5)=13*5+7\mod 26=20 \mod 16=13*7+7\mod 26=e(7)$.
Ou seja ``f'' e ``h'' são cifrados no mesmo caracter: o ``U''.
Para que a função de cifração seja injectiva (e, portanto, bijectiva), é necessário e suficiente que $$mdc(a,26)=1$$

Este facto permite garantir a existência de um certo elemento $a^{-1}$ tal que $aa^{-1}=1\mod 26$.

O conjunto das chaves é $\left\{ (a,b)\in Z_{26}\times  Z_{26}: mdc(a,26)=1 \right\}$, e são em número $12\cdot 26=312$.

As função de cifração e decifração são, respectivamente,

$$\begin{array}{l} e(x) = ax+b \\ d(x) = a^{-1} (x-b)\end{array}$$

Por exemplo,
$$e(x)=7x+10 \mod 26,\, mdc(7,26)=1,\, a^{-1}=15,$$
$$d(x)=15x+6 \mod 26$$

 Cifra de Vigenère

Nas cifras descritas atrás, uma vez escolhida a chave de cifração cada letra do alfabeto é aplicada numa outra única letra do alfabeto. Daí chamarem-se monoalfabéticas. Apresentamos, de seguida, uma cifra que não é monoalfabética: por exemplo, a letra ``a'' não é garantidamente aplicada numa mesma letra.

Esta cifra foi criada por Blaise Vigenère (1523-1596), usando as ideias de Leon Battista Alberti (1404-1472), Johannes Trithemius (1462-1516) e Giambattista Della Porta (1535-1615). Deve-se, aliás, a Alberti a idealização da primeira cifra polialfabética. Alberti propunha a utilização de dois ou mais alfabetos de cifra e a alternância entre eles durante a cifragem, com o objectivo de confundir os potenciais criptanalistas. Não conseguiu, contudo, transformar a sua ideia num sistema de cifra plenamente elaborado.

Façamos a descrição da cifra de Vigenère. A mensagem é cifrada por blocos e não letra a letra. Suponha que cada bloco tem comprimento $m$. Dada uma chave $k=k_,k_2,\dots,k_m)$,

$$e_k(x_1, x_2, \dots x_m)=(x_1+k_1,x_2+k_2,\dots x_m+k_m)$$
$$d_k(x_1, x_2, \dots x_m)=(x_1-k_1,x_2-k_2,\dots x_m-k_m)$$

Como exemplo, suponha que a chave é "BLAISE", i.e., $k=(1,11,0,8,18,4)$, e portanto $m=6$. repare que o número total de chaves possíveis de comprimento 6 é $26^6=308915776$ (ou seja, mais de 300 milhões de chaves)

$$\begin{array}{lll} bibabraga & \equiv & 01 \,08 \,01 \, 00 \,01 \,17 \, 00 \,06 \,00\\ & \mapsto& 01+1,08+11,01+0,00+8 ,01+18,17+4, 00+1 ,06+11 ,00+0 \\ & = & 02 \,19 \,01 \, 08 \,19 \,21 \, 01 \,17 \,00\\ & \equiv & CTBITVBRA \end{array}$$

 

Para comunicações militares e governamentais, onde a segurança era fundamental, a cifra monoalfabética simples era obviamente inadequada e existia alguma relutância em adoptar a cifra polialfabética, dada a sua complexidade de implementação. Por conseguinte, os criptógrafos da época sentiram necessidade de criar uma cifra intermédia. Um exemplo marcante de uma cifra monoalfabética melhorada, bastante segura, foi a denominada Grande Cifra de Luís XIV(1638-1715), elaborada por Antoine e Bonaventure Rossignol. Após a morte dos seus criadores, ela caiu em desuso e os seus pormenores exactos perderam-se rapidamente. A Grande Cifra de Luís XIV era tão forte que só no século XIX foi decifrada pelo comandante do exértico francês Etienne Bazeries.

Entretanto, a cifra polialfabética de Vigenére continuava a ser, incontestavelmente, a melhor maneira de garantir as comunicações importantes sigilosas. Essa era considerada inquebrável e tornou-se conhecida como "Le Chiffre Indéchiffrable". Porém, por volta de 1854, o matemático Charles Babbage (1791-1871) foi o autor da maior descoberta no domínio da Criptanálise desde o século IX, altura em que os árabes fizeram uso da análise frequencista. Babbage conseguiu quebrar cifras polialfabéticas, e em particular "Le Chiffre Indéchiffrable". Por acasos do destino, acabou por ser o prussiano Friedrich Wilhelm Kasiski (1805-1881) a receber os créditos da quebra da cifra de Vigenère, sendo a técnica por ele desenvolvida conhecida por Teste de Kasiski.

RSA com 8 Bits

1. Alice escolhe dois primos p = 11 e q = 7, e calcula

   n = p*q = 77.

   Calcula ainda

   m = (p-1)*(q-1) = 60 e escolhe a = 13 primo relativo com

   m = 60.

   Calcula b = a^-1 mod m = 37.

   Publica n = 77 e a = 13 (chave publica de Alice)

2. Bob pretende enviar a mensagem mens = 28 a Alice. Com a chave publica de Alice, calcula

   cifrado = mens^a mod n = 7.

3. Alice recebe o texto cifrado = 7 de Bob. Usando o inverso b = 37 = a^-1 mod m, calcula

   decifrado = cifrado^b mod n = 28.

Questões práticas:

• como encontrar primos?
• onde está a segurança?
• como calcular $a^b \mod n$?

A divisão trivial...

O teste de Miller-Rabin

RSA: um exemplo "mais real"

Factorização de Fermat

Teorema dos Números Primos

$\pi(n)$ indica o número de primos não superiores a $n$.

Primos GRAAAANDEEEEES

Se $M_p=2^p-1$ é primo então $M_p$ chama-se um primo de Mersènne.

Coisas inúteis...

Conjectura de Goldbach

Todo o número par maior que 4 é soma de dois primos

Conjectura dos primos gémeos

Existe uma infinidade de primos gémeos.

O problema de Siracusa

http://en.wikipedia.org/wiki/Collatz_conjecture

$n\in \mathbb{N}$

$$u_{n+1}= \frac{u_n}{2}$$  se $u_n$ é par, e $$u_{n+1}=3u_n + 1$$ se $u_n$ é ímpar.

Conjectura: existe um $k$ tal que $u_k=1$, independentemente da condição inicial.