O bom, o mal e o feio

Neste artigo vou tentar mostrar 3 coisas: O algoritmo mais óbvio raramente é o melhor possível, um bom algoritmo pode ser sempre melhorado e que essa melhoria nem sempre vem sem custos. A ideia é usar um algoritmo custoso, em termos de processamento e, para isso, aqui vão os famosos testes para determinação se um valor inteiro positivo é ou não um número primo.

Nesses testes usarei o tipo unsigned int porque ele tem 32 bits de tamanho em ambas as plataformas Linux (e na SysV ABI) e Windows, tanto para o modo de operação do processador, x86-64 e i386. É bom reparar nisso, porque a determinação desse tipo de parentesco (se é primo!) em valores inteiros com mais bits pode ser muito demorada. Por exemplo, quando lidamos com o esquema de criptografia assimétrica, é comum o uso de chaves de 2048 bits de tamanho, o que torna uma das otimizações inviável (veremos adiante).

O feio

O algoritmo clássico é varrer toda a faixa de valores menores que o valor sob teste e verificar se existe algum divisor exato. Algo assim:

// Método tradicional: Tenta dividir todos os valores 
// inferiores a 'n' e conta quantos o dividem...
NOINLINE
int ugly_is_prime ( unsigned int n )
{
  unsigned int count, i;

  // caso especial.
  if ( !n ) 
    return 0;

  count = 1;
  for ( i = 2; i < n; i++ )
    if ( ! ( n % i ) )
      count++;

  return (count == 1);
}

Por que chamei essa rotina de “o feio”? Ela testa por todos os valores inferiores a n, começando por 2, se n for diferente de zero! Suponha que n=4294967291. Esse valor é primo, mas para a rotina determinar isso terá que percorrer todos os valores entre 2 e 4294967290. Veremos que, para isso, a rotina gasta cerca de 47 bilhões de ciclos de clock!

O mau

É claro que não precisamos verificar todos os valores! Por exemplo, 2 é o único valor par que também é primo. De cara podemos testar se n é par e diferente de 2. Se for, com certeza não é primo. Isso nos deixa os valores ímpares para teste, o que diminui pela metade o esforço computacional.

Outra melhoria que podemos fazer é a de que, de acordo com o Princípio fundamental da aritmética, todo número pode ser fatorado em números primos… Por exemplo, 9=3\cdot3, 10=2\cdot5, 76=2\cdot\cdot2\cdot19 e assim por diante (voltaremos a isso no algoritmo “bom”). Ainda, “lembre-se que a ordem dos fatores não altera o produto”. Tome 10 como exemplo… Ele pode ser escrito como 10=2\cdot5=5\cdot2.

Não é evidente, mas graças a isso só precisamos testar por divisores ímpares menores ou iguais a raiz quadrada de n:

// Método "ruim" (mas, melhor que o acima).
// Faz a mesma coisa, mas só verifica os valores inferiores a 'n' 
// que sejam ímpares e menores ou iquais a raiz quadrada de 'n'.
int bad_is_prime ( unsigned int n )
{
  unsigned int sr;
  unsigned int i;

  // casos especiais.
  switch ( n )
  {
    case 1:
    case 2:
      return 1;
  };

  // O único par primo é 2.
  if ( ! ( n & 1 ) )
    return 0;

  // Obtém o valor ímpar menor ou igual
  // à raíz quadrada de n.
  sr = sqrt(n);
  if ( ! ( sr & 1 ) ) 
    sr--;

  // Só precisamos testar os valores ímpares
  for ( i = 3; i <= sr; i += 2 )
    if ( ! ( n % i ) )
      return 0;

  return 1;
}

Aqui tomo um atalho para os 2 primeiros primos (1 e 2) para simplificar a rotina.

Mas, porque essa rotina é ? O problema aqui é que, mesmo eliminando testes, estamos testando muitos valores mais de uma vez… Por exemplo, se n não for divisível por 3 ele também não será para nenhum múltiplo de 3, como 9, 12, 15, 18, 21, 24, 27… No entanto, estamos testando esses valores também, se n for grande!

O bom

A solução, é claro, é eliminar todos os valores múltiplos dos anteriores, ou seja, usar apenas divisores primos. O problema é óbvio: Ora, bolas! Como é que eu vou fazer uma rotina que testa se um valor é primo usando como critério o teste se um divisor também o é?!

O método de Erastótenes (276 AEC ~ 194 AEC) mantém uma sequência onde marcamos os valores primos, percorrendo a lista do início ao fim, e verificando se os próximos valores são múltiplos. Se forem, marcamos como “não primo”. Na próxima interação, o próximo valor é, com certeza, primo e repetimos o processo, até que todo o array contenha apenas os primos “não marcados”. Isso exige que toda a faixa de valores seja colocada no array, mas os valores usados como base de testes podem ser limitados à valores menores ou iguais a raíz quadrada de n, como fizemos anteriormente.

O ponto negativo desse método, é claro, é o consumo excessivo de memória para conter todo o array, mas, e se mantivéssemos apenas um array com os valores primos ímpares inferiores ou iguais à raiz quadrada da faixa do tipo unsigned int? Isso não consumirá tanta memória quanto você pode imaginar: Em primeiro lugar, no pior caso, teríamos um array com \frac{\sqrt{2^{32}-1}}{2}\approx32767 itens. Se cada item tem 4 bytes de tamanho, aproximadamente 128 KiB serão usados para o array. No caso mais prático, vários valores desses 32767 são eliminados, porque não serão primos.

O programinha abaixo, que usa o bad_is_prime(), acima, monta esse array:

// gentable.c
//
// Cria tabela contendo os inteiros, primos, menores ou iguais ao
// valor ímpar mais pŕoximo (porém menor) que a raiz quadrada de 2³²-1.
//
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

extern int bad_is_prime ( unsigned int );

#define ITEMS_PER_LINE 16

void main ( int argc, char *argv[] )
{
  FILE *f;
  unsigned int i, sr;
  unsigned int count = 0, cnt2 = 0;

  if ( ! *++argv )
  {
    fputs ( "Usage: gentable <cfile>\n", stderr );
    exit ( 1 );
  }

  if ( ! ( f = fopen ( *argv, "wt" ) ) )
  {
    fprintf ( stderr, 
              "ERROR opening file %s for writing.\n", 
              *argv );
    exit ( 1 );
  }

  fputs ( "// *** criado por gentable.c ***\n\n"
          "// tabela começa de 3...\n"
          "const unsigned int primes_table[] = {\n", f );

  // ~0U é o máximo valor de unsigned int.
  // Obtém a raiz quadrada ímpar...
  sr = sqrt(~0U);
  if (!(sr & 1)) 
    sr--;

  // Só precisamos dos inteiros ímpares e primos.
  for ( i = 3; i <= sr; i += 2 )
    if ( bad_is_prime ( i ) )
    {
      if ( count ) 
      {
        fputc( ',', f );

        if (++cnt2 == ITEMS_PER_LINE)
        {
          fputc ( '\n', f );
          cnt2 = 0;
        }
        else
          fputc ( ' ', f );
      }

      fprintf ( f, "%uU", i );
      count++;
    }

  fprintf ( f, "\n};\n\n"
            "// tabela ocupa %zu bytes.\n"
            "const unsigned int primes_table_items = %u;\n",
            sizeof ( unsigned int ) * count, 
            count );

  fclose ( f );
}

Basta compilar e executar o programinha para gerar um arquivo texto contendo o código fonte de uma tabela com apenas as raízes quadradas desejadas! No caso, gerarei table.c que, como pode ser observado, contém 6541 valores, ocupando apenas 25.5 KiB:

// *** criado por gentable.c ***

// tabela começa de 3...
const unsigned int primes_table[] = {
3U, 5U, 7U, 11U, 13U, 17U, 19U, 23U,
29U, 31U, 37U, 41U, 43U, 47U, 53U, 59U, 
61U, 67U, 71U, 73U, 79U, 83U, 89U, 97U,
...
... 65447U, 65449U, 65479U, 65497U, 65519U, 65521U
}; 

// tabela ocupa 26164 bytes.
const unsigned int primes_table_items = 6541;

Para essa tabela de raízes o processamento é rápido. Considere o caso de valores de 64 bits. A máxima raiz quadrada é 4294967295. Como verificar se um valor é primo é relativamente lento, pré-calcular toda a tabela pode demorar um bocado… Existe ainda o fator espaço, que explico abaixo.

Usando essa tabela, a nossa rotina de teste good_is_prime fica assim:

extern const unsigned int primes_table[];
extern const unsigned int primes_table_items;

// Método "melhor": Faz quase a mesma coisa que acima, mas
// usa uma tabela pré calculada.
int good_is_prime ( unsigned int n )
{
  unsigned int i, sr, *p;

  switch ( n )
  {
    case 1:
    case 2:
      return 1;
  }

  if ( ! ( n & 1 ) )
    return 0;

  sr = sqrt(n);

  for ( i = 0, p = (unsigned int *)primes_table; 
        i < primes_table_items && *p <= sr; 
        i++, p++ )
  {
    if ( ! ( n % *p ) )
      return 0;
  }

  return 1;
}

Ela é bem parecida com bad_is_prime, mas usa uma tabela contendo apenas valores primos para os testes!

Nem sempre usar tabelas pré-calculadas é uma boa ideia

Em primeiro lugar, poderíamos usar uma tabela pré-calculada com todos os valores primos na faixa e a rotina final poderia ser uma simples busca binária, daí a performance da rotina seria proporcional a \log_2{n}, mas é claro que a tabela final seria enorme. Daí, escolhi armazenar apenas os valores que serão usados para verificar o divisor, eliminando os múltiplos…

A quantidade de valores primos, dado um valor máximo, pode ser aproximado (de longe!) por:

\displaystyle \Pi(x)\sim\frac{x}{\log{x}-1}

Assim, se quisermos montar uma tabela com todos os primos inferiores ou iguais à raiz quadrada do maior valor possível para um tipo, como no exemplo de unsigned int (que assume o valor máximo de 2^{32}-1), temos que o maior valor para a tabela é r_{max}=\lfloor\sqrt{2^{32}-1}\rfloor e, portanto, usando a aproximação acima, teríamos uma tabela com cerca de 17171 itens. Cada item cabe em 2 bytes (unsigned short), já que r_{max}=65535. O que nos daria um array de, no máximo, 33.5 KiB. Se usarmos unsigned int (como fiz) o array estimado ficaria com 67 KiB.

Observe o contraste com o que encontramos através de gentable.c… Temos menos da metade dessa quantidade! Mas isso não é garantido! Temos que assumir que a aproximação acima é uma quantidade média e usarmos como critério para estimar o custo da rotina.

Considere agora, 64 bits. Usando o mesmo critério, r_{max}=\lfloor\sqrt{2^{64}-1}\rfloor=4294967295, que cabe num unsigned int. Daí \Pi(r_{max})\approx497508081 itens com 4 bytes cada, ou seja, quase 2 GiB de array. Repare que dobramos o número de bits da faixa sob teste, mas o tamanho da tabela aumentou quase de 29 mil vezes.

Isso é esperado porque a estimativa é exponencial (proporcional a \frac{1}{\log{x}-1})… Então, não recomendo o método good_is_prime para valores com mais de 32 bits.

O quão bom é o “bom”?

No pior caso bad_is_prime é 10 milhões de vezes mais rápida que ugly_is_prime e good_is_prime é quase 4 vezes mais rápida que bad_is_prime (o que faz dela quase 40 milhões de vezes mais rápida que ugle_is_prime).

Estou informando esses valores, mas os medi, usando meu “contador de ciclos do homem pobre” em alguns casos:

  • Melhor caso: Um valor não primo pequeno;
  • Pior caso: Um valor primo muito grande: 4294967291
  • Um valor não primo grande cujos fatores sejam primos grandes: 144795733, por exemplo, pode ser fatorado em 12343 e 11731.

Em alguns casos, no “melhor caso” e somente às vezes, bad_is_prime ganha de good_is_prime, mas isso ocorre, provavelmente, por causa dos efeitos do cache L1 (que só tem 32 KiB!). Isso, talvez, possa ser compensado fazendo um prefetch da tabela antes de executar a rotina… Esse é especialmente o problema quando o valor não é primo! Quando a rotina precisa varrer grande parte do o array os efeitos do cache L1 entram em ação e ela fica um pouco mais lenta que a “má” rotina…

O problema das pizzas – Ou, o problema da ignorância da matemática elementar!?

Bem… não foi surpresa nenhuma pra mim perceber que algumas pessoas não conseguem aplicar conhecimentos fundamentais no dia a dia. Eis um problema (bem simples, que um estudando ensino fundamental deveria saber resolver, e um adulto também!) que propus, recentemente:

“Você resolveu comprar pizza para a família toda. Uma pizzaria oferece pizzas “médias” com raio de 30 cm e “grandes” com raio de 45 cm, ao preço de R$ 40,00 e R$ 50,00 cada uma, respectivamente. Você compraria duas pizzas médias ou uma grande?”

O detalhe é que o preço é irrelevante no problema. O que se quer saber é qual das duas configurações vai te dar mais pizza para comer: Duas médias ou uma grande?

Como disse, não é surpresa ver que a maioria das pessoas escolhe as duas pizzas médias, achando que terá mais pizza do que uma grande. Infelizmente a geometria plana elementar desmente isso, já que a “quantidade” de pizza é medida pela área da circunferência… Quanto a isso, obviamente o problema considera que uma pizza seja isto:

ISSO é uma pizza!

Fazendo um cálculo rápido, qualquer um pode observar que uma pizza grande, do problema proposto, é 12,5% maior que duas pizzas médias (área da pizza média. 900\pi, área da pizza grande, 2025\pi)! Isso levanta a questão: Será que estou perdendo dinheiro toda vez que compro pizzas? Quando é vantajoso comprar duas médias ao invés de uma grande? Well…

Considere r como sendo o raio da pizza média e R como sendo o raio da pizza grande. Valerá a pena comprar duas pizzas médias ao invés de uma grande se:

\displaystyle 2\pi r^2 > \pi R^2

Ou seja, \frac{R^2}{r^2} < 2 \Rightarrow R < r\sqrt{2} (estou ignorando o valor negativo que satisfaz a inequação por motivos óbvios!) . Isso quer dizer que o raio R tem que exceder menos que 41% do radio r para ser vantajoso comprar duas médias… No exemplo do problema, se a pizza grande tiver menos que 42 cm (30\sqrt{2}\approx42,4), vale à pena comprar duas médias…

Ahhh… Esse tipo de racionalização também deveria ser óbvio para qualquer pessoa que passou por uma escola…

Arredondamento. Qual é o “correto”?

O último artigo gerou alguma controvérsia… Alguns leitores perguntam: “Qual é o jeito certo?” e não se satisfazem com a resposta de que ambos os métodos, de truncamento e de arredondamento para baixo, estão certos, dependendo da aplicação. Aqui quero provocá-los mostrando algo similar…

Já mostrei antes que operações em ponto flutuante dependem de algum método de arredondamento bem definido. O padrão IEEE 754 define quatro deles:

  • No sentido de +\infty;
  • No sentido de -\infty;
  • No sentido de 0;
  • O valor “mais próximo”;

Ao calcular f=1.0/10.0, o valor 0.1, que não pode ser representado numa variável do tipo ponto flutuante, já que, em binário, será uma dízima periódica:

\displaystyle (0.1)_{10} = (0.0110011001100110011001100...)_{2}

Portanto, precisa ser arredondado. Se estivermos lidando com o tipo float esse valor será (1.1001100110011001100110?)_{2}\cdot 2^{-2}, onde ‘?’ é o algarismo impreciso… Ou seja, se ele for zero, termos um valor levemente inferior a 0.1, se ele for 1, teremos um valor levemente superior a 0.1. Qual deles devemos escolher?

Por default, o padrão IEEE 754 escolhe o método do “mais próximo”. Repare:

/* test.c */
#include <stdio.h>

extern float _mydiv(float, float);

void main(void)
{
  float f;
  unsigned int d = 0x3dcccccc;
  float *g = (float *)&d;
  unsigned int *p = (unsigned int *)&f;

  f = _mydiv(1.0f, 10.0f);

  printf("O valor '%.2f' é codificado como '0x%08X'.\n\n", 
    f, *p);

  printf("Mas, na verdade:\n"
         "0x%08X -> %.18f\n"
         "0x%08X -> %.18f\n",
    *p, f,
    d, *g);
}

O motivo de criar a função _mydiv é para evitar que o compilador otimize a operação de divisão entre duas constantes e não faça divisão alguma. Neste caso, o arredondamento será feito pelo compilador, não pelo nosso programa. A função _mydiv é, simplesmente:

/* mydiv.c */
float _mydiv(float a, float b) 
{ return a/b; }

Compilando e linkando tudo e depois executando, temos:

$ gcc -o test test.c mydiv.c
$ ./test
O valor '0.10' é codificado como '0x3DCCCCCD'.

Mas, na verdade:
0x3DCCCCCD -> 0.100000001490116119
0x3DCCCCCC -> 0.099999994039535522

É fácil perceber que o primeiro caso está mais próximo de 0.1 do que o segundo e é este que o processador escolherá (como isso é feito não interessa agora!). Mas, isso não significa que os outros métodos de arredondamento não sejam “corretos”. De fato, se mandarmos o processador arredondar de outra maneira ele o fará, Eis um exemplo:

/* test.c */
#include <stdio.h>
#include <fenv.h>

extern float _mydiv(float, float);

void main(void)
{
  float f;
  int oldround;

  oldround = fegetround();
  fesetround(FE_TOWARDZERO);
  f = _mydiv(1.0f, 10.0f);
  fesetround(oldround);

  printf("%.18f\n", f);
}

Ao compilar e executar esse código (será preciso especificar a libm com -lm, no gcc) você verá que a divisão de 1 por 10 será arredondada para o MENOR valor, ou melhor, em direção ao zero. Esse será o valor mais distante do verdadeiro, neste caso. Troque 1.0f por -1.0f e veja o que acontece…

Depois, modifique o método para FE_DOWNWARD (arredondamenteo no sentido de -\infty) e teste os dois casos (com 1.0f e -1.0f)… Note que o truncamento citado no artigo anterior é equivalente a FE_TOWARDZERO…

O que quero dizer aqui é que, tanto na programação quanto na matemática, às vezes existe mais de um jeito “correto” de fazer alguma coisa. Depende apenas da aplicação.

Cuidado com o que você pensa que sabe…

Recentemente topei com um exemplo que deveria ser absolutamente simples e já estar “no sangue” de qualquer estudante do ensino básico (note bem: básico!). Por exemplo, o resto da divisão de 2 por 3 (2\mod 3) é 2, certo? Parece lógico extrapolar e dizermos que -2\mod 3=-2. Surpresa! A resposta pode estar errada, dependendo de qual definição de resto você usa! O problema está na definição de resto. Usando o método do truncamento do quociente, temos:

\displaystyle x\mod y=x - y\cdot trunc\left(\frac{x}{y}\right)

Mas, também existe a definição de Knuth:

\displaystyle x\mod y=x - y\left\lfloor\frac{x}{y}\right\rfloor

Ao usarmos essa definição teremos:

\displaystyle \begin{matrix}  -2\mod 3 &= (-2)-3\left\lfloor-\frac{2}{3}\right\rfloor \\  &= (-2)-3(-1) \\  &= -2+3 = 1 \\  \end{matrix}

Isso parece estranho até você lembrar da regrinha sobre o resto: Ele precisa ser sempre menor que o divisor. Mas qualquer valor negativo é menor que 3, certo? Portanto a restrição de que o quociente seja calculado através do operador floor, faz todo sentido…

Ainda, é interessante notar que, de acordo com a definição acima, o resto tem valor absoluto diferente nas expressões abaixo. Ele segue o sinal do divisor:

\displaystyle \begin{matrix}  -2\mod -3 = (-2)-(-3)\left\lfloor\frac{2}{3}\right\rfloor = -2 \\  2\mod -3 = 2-(-3)\left\lfloor-\frac{2}{3}\right\rfloor = -1 \\  -2\mod 3 = (-2)-3\left\lfloor-\frac{2}{3}\right\rfloor = 1 \\  2\mod 3 = 2-3\left\lfloor\frac{2}{3}\right\rfloor = 2 \\  \end{matrix}

Uma interpretação geométrica para o método de Knuth pode ser a de que a operação mod restringe o co-domínio da função para valores no intervalo entre 0 e o valor mais próximo (porém, absolutamente menor) que o do divisor, formando um “loop”. No caso de divisores positivos, o loop ficaria assim:

loop

Partindo de zero, uma vez que o dividendo (numerador) tem sinal contrário ao divisor (denominador), o ponteiro do “relógio” tem que ser “girado” duas casas no sentido “anti-horário” e obtemos o valor 1, como mostrado acima. No caso de um divisor negativo, a graduação é feita no sentido anti-horário usando 0, -1 e -2 e, se o dividendo tiver sinal contrário (positivo) o ponteiro girará no sentido horário, obtendo -1 (como pode ser visto na lista acima)… No caso de a=-2 e b=-3, a operação a\mod b graduará o loop no sentido anti-horário com 0, -1 e -2, já que o divisor é negativo, e o ponteiro será girado no mesmo sentido, já que o dividendo (numerador) também é negativo e, por isso, obtemos -2.

Essa é uma forma interessante de se entender o chamado complemento 2, usado na aritmética binária com sinais… Considere um conjunto com 16 valores possíveis (ou, 4 bits). O valor -2 deverá ser representado pelo valor positivo 14, já que -2\mod 16=14, segundo a definição. Isso também fica simples de representar geometricamente, graduando o loop no sentido horário e deslocando o ponteiro do “relógio” duas posições no sentido anti-horário:

loop2

Para maior quantidade de bits, mais graduações teremos no loop…

O problema é que a maioria das linguagens de programação lidam com o resto através do truncamento do quociente. Eis dois exemplos, o primeiro em Java:

/* test.java */
class test {
  public static void main(String[] args)
  { 
    int x = -2;
    int y = 3;
    int r = x % y;
    System.out.println(r); 
  }
}

Compilando e executando, obtemos:

$ javac test.java
$ java test
-2

A mesma coisa ocorre em C, C++ e Pascal (embora o Pascal padrão sempre resulte num resto positivo!), por exemplo… Quanto aos processadores, os compatíveis com a arquitetura Intel x86 possuem a instrução IDIV, que é definida como (quando a divisão é feita com valores de 32 bits):

Signed divide EDX:EAX by r/m32, with result stored in EAX ← Quotient, EDX ← Remainder

Assim, para obter o resto de uma divisão inteira temos que colocar o numerador no par de registradores EDX:EAX, o denominador em um outro lugar, executar IDIV e obter o resto em EDX. A função, para ser usada em C fica assim:

; mymod.asm
bits 64
section .text
global mymod
; Retorna A mod B.
; Entrada: EDI = A; ESI = B
; Saída: EAX = resto
mymod:
  mov  eax,edi
  cdq          ; estende o sinal de 'A' em EDX.
  idiv esi
  mov  eax,edx ; queremos só o resto.
  ret

Usarei a função da seguinte maneira:

/* test.c */
#include <stdio.h>

extern int mymod(int, int);

void main(void)
{ printf("%d\n", mymod(-2,3)); }

Compilando tudo, linkando e executando, temos:

$ nasm -felf64 mymod.asm -o mymod.o
$ gcc -c -o test.o test.c
$ gcc -o test test.o mymod.o
$ ./test
-2

Ou seja, o processador também calcula o resto de maneira “tradicional”, truncando…

O outro método é o de Euclides e pode ser equacionado assim:

\displaystyle x\mod y = x - \left|y\right|\left\lfloor\frac{x}{\left|y\right|}\right\rfloor

Que, é claro, é bem mais complicado e tem como resultado o mesmo valor obtido pelo método de Knuth, exceto que o sinal do resto não é sempre o mesmo do divisor…

ATENÇÃO: Os 3 métodos são “corretos”, depende somente como uma divisão é definida!!

O alerta aqui é que, se você está adaptando uma equação que use aritmética modular (mod) na implementação que usa valores negativos, pode ser que tenha problemas com os resultados se não estiver certo sobre o método que o compilador/linguagem está lidando.

Como falei antes, a maioria das linguagens usa o método do truncamento do quociente, mas nem todas. Uma exceção interessante: Python calcula o resto usando o método de Knuth

$ python
Python 2.7.12 (default, Nov 19 2016, 06:48:10) 
[GCC 5.4.0 20160609] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> -2 % 3
1
>>>^D
$

A mesma coisa acontece com a aplicação gnome-calculator

Criptografia assimétrica e usando GnuPG

Criptografia é a “arte” de esconder algo mediante o uso de uma chave, conhecida pelos intelocutores da mensagem apenas. A “mensagem” será ininteligível para qualquer outro participante da conversa. O promeiro exemplo de criptografia “formal” que se tem notícia (pelo menos a que posso pensar agora) é o método usado por Julio Cesar: A idéia é atribuir valores aos caracteres da mensagem e deslocar esses valores em algum outro valor fixo. Atualmente, existe o método chamado ROT13, onde a cada caracter é somado o número 13. Neste caso, a mensagem “MENSAGEM SECRETA” ficará assim: “ZRAFNTRZ FRPERGN”.

Com ROT13 os interlocutores têm apenas que saber o quanto devem deslocar o valor de cada um dos caracteres e essa é a chave para a decodificação. No entanto, perceber o artifício é algo muito fácil… Outro método é usar a operação lógica XOR para “codificar” a mensagem através de uma string “chave”. Por exemplo, se quiséssemos codificar a mensagem “MENSAGEM SECRETA” com a chave “SEGREDO”, poderíamos fazer algo assim:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

char msg[] = "MENSAGEM SECRETA";
char key[] = "SEGREDO";

static size_t encode(char *, char *);

void main(void)
{
  size_t i, size;

  printf("Megsagem: \"%s\"\n"
         "Chave: \"%s\"\n",
         msg, key);

  size = encode(msg, key);

  for (i = 0; i < size; i++)
    printf("%02X ", msg[i]);
  puts("");
}

size_t encode(char *msg, char *key)
{
  size_t size = 0;
  char *p = key;

  while (*msg)
  {
    *msg++ ^= *p++;
    if (!*p) p = key;
    size++;
  }

  return size;
}

O resultado:

Megsagem: "MENSAGEM SECRETA"
Chave: "SEGREDO"
1E 00 09 01 04 03 0A 1E 65 14 17 06 16 0A 07 04

O problema, em C, é que a string resultante teria apenas 1 byte de tamanho (o “E” de “MENSAGEM” é zerado pelo XOR com o “E” de “SEGREDO”). Mas, é mais difícil decodificar esse stream de bytes e obter a “MENSAGEM SECRETA” sem o conhecimento da chave “SEGREDO” por ambos os interlocutores.

Esse tipo de criptografia, onde as duas partes têm que conhecer o segredo, é chamada de “simétrica” e apresenta o problema de que a chave, usada para desvendar a mensagem, deve ser transmitida em segredo para os participantes. Qualquer um com o segredo em mãos pode decodificar a mensagem… Imagine o cenário em que vocẽ transmite para um amigo, via e-mail, a chave e EU, sendo o sacana que sou, consigo interceptar sua mensagem contendo a chave! Ou seja, eu sou o “homem no meio” (man in the middle). Daqui para frente, todas sa mensagens criptografadas com essa chave que você passar para seu amigo eu também conseguirei ler!

O problema é que vocẽ precisa de um meio seguro de enviar a chave para o destinatário e, aparentemente, não há maneira de fazer isso: Você pode fazer uma ligação telefônica para seu amigo e eu posso ter “grampeado” seu telefone… Você pode escrever um bilhete para seu amigo e enviá-lo pelo correio, mas eu posso ter acesso à sua correspondência de algum modo… e por ai vai… E não adianta pensar em telepatia, porque você não conhece meus poderes! :)

Mas, não tema… em meados dos anos 70 um par de sujeitos barbudos (Whitfield Diffie e Martin Hellman) publicaram um trabalho contendo o conceito de criptografia “assimétrica”. A coisa funciona mais ou menos assim: Os interlocutores têm duas chaves, ao invés de uma só. Uma chave “pública” que é distribuída para quer quer que seja, e uma “privada” que pertence apenas à pessoa e ninguém mais… A criptografia da mensagem é então feita de forma tal que apenas minha chave “privada” consegue decodificar o que foi codificado por minha chave “pública” e vice versa… Como eu tenho a chave pública do meu interlocutor e ele tem a minha, eu trancafio a mensagem usando minha chave privada e, depois, trancafio essa nova mensagem com a chave pública dele. Somente meu interlocutor será capaz de abrir a mensagem com sua própria chave “privada” e, depois, usar minha chave pública para decodificá-la em sua forma final.

Isso tem alguns pontos interessantes:

  1. O “homem do meio” jamais conseguirá decodificar a mensagem, pois precisa da chave privada do destinatário;
  2. O “homem do meio” jamais poderá se passar pelo enviador da mensagem, pois não tem sua chave privada;
  3. Apenas parte das “chaves” são passadas à diante (metade delas é “privada”);
  4. Não é necessário um “meio seguro” para o trânsito das chaves “públicas” e da mensagem criptografada!

O algorítmo RSA:

Para alcançar esse intento, três outros sujeitos, criaram um algoritmo baseado num teorema chamado de “o pequeno teorema de Fermat”. Ele diz, quando a e p são primos entre si:

\displaystyle a^{p-1} \equiv\,1\,(\mod p)

Essa notação significa algo assim: a^{p-1} - 1 é múltiplo de p… A matemática por trás desse teorema pode ser estudada neste link. E o seu uso no RSA, aqui. Em resumo, chega-se ao fato de que:

\displaystyle {m^e}^d \equiv\,m\,(\mod n)

Onde e, d e n são partes da chave privada (no par (e,n)) e pública (no par (d,n)). Ainda, a equação acima também é verdadeira para {m^d}^e \equiv\,m\,(\mod n), já que {a^b}^c = a^{b\cdot c}. E essas relações tem ainda uma característica prática interessante para a criptografia: Mesmo que o “homem do meio” saiba os valores de d e n (a chave pública), encontrar os valores de m e e originais é muito difícil! Especialmente porque n é um valor muito grande (atualmente os certificados usam 2048 ou 4096 bits) e o expoente pode ter uns 512 bits de tamanho. Observe os dados do certificado contido no wordpress, para este blog:

$ openssl s_client -connect bitismyth.wordpress.com:443 -showcerts | \
  openssl x509 -noout -text
...
Subject Public Key Info:
  Public Key Algorithm: rsaEncryption
    Public-Key: (2048 bit)
      Modulus:
        00:c3:8b:a8:b1:25:40:89:b0:40:52:8c:ab:75:28:
        ff:76:24:f5:2b:95:7a:e5:58:90:35:53:66:90:79:
        f0:f8:99:09:ee:aa:d9:ff:24:68:84:e6:85:0a:05:
        7c:53:2f:e3:8e:16:ab:42:bd:93:bd:9a:1c:ad:58:
        86:a1:29:53:b7:0d:bc:46:71:7d:3a:d6:fa:e6:ee:
        52:be:77:89:99:1f:61:2e:e3:39:11:d8:76:41:ae:
        28:16:69:ca:c2:c9:f3:f9:3e:0e:6e:13:b8:e4:30:
        18:dc:c4:29:a9:6e:02:e5:9d:59:dd:97:98:81:21:
        78:3d:a4:ce:56:1e:cb:b2:73:be:a5:e1:a7:ac:26:
        8c:25:61:28:3f:7a:e8:02:81:35:ca:0b:f1:63:ad:
        31:d5:4f:21:19:91:d4:8d:85:20:dd:5d:15:31:b8:
        bc:a7:b8:60:f9:bb:4a:24:4d:43:e9:1e:32:e0:5f:
        1d:bf:25:fd:9d:c7:1d:d1:8e:ae:86:67:7d:1e:9d:
        25:67:66:b7:c6:7c:26:89:c0:80:0d:81:50:e1:82:
        07:db:01:e8:18:49:bc:c6:81:5d:07:f6:ac:18:9c:
        44:ef:8d:13:a4:0e:78:46:1e:b3:04:8e:12:a3:dc:
        55:1f:55:4b:18:60:ab:41:c8:1c:d5:e8:82:0e:8e:
        da:f9
      Exponent: 65537 (0x10001)
...

Assim, para criptografar uma mensagem, a equação c \equiv\,m^e\,(\mod n) é usada, mas para decodificá-la, usamos a equação c^d \equiv\,{m^e}^d \equiv\,m\,(\mod n), onde os expoentes e e d são cuidadosamente escolhidos, bem como o módulo n… Em primeiro lugar, os expoentes são calculados com base em dois valores primos. Depois, n é calculado como a multiplicação desses dois valores primos iniciais. Além da aritmética modular exponencial nos dar a vantagem da dificuldade de encontrar expoentes corretos, o fato desses cálculos envolverem valores primos dificulta mais um bocado, já que fatorar valores primos a partir de um módulo enorme não é tarefa computacionalmente fácil. Especialmente porque, no caso da chave privada, o expoente também é grande!

A coisa é ainda um pouco mais complicada que isso!

Pode parecer simples, afinal temos apenas 3 “constantes” para nos preocuparmos, certo? Acontece que RSA conta com 8 fatores (não apenas 3). A escolha das chaves, por exemplo, depende da escolha de dois valores primos, entre si, de forma aleatória confiável e atendendo a condições específicas que não vale a pena esmiuçar aqui. Afinal, não queremos nem os expoentes e nem o módulo com valores pequenos previsíveis.

Outra coisa a se levar em conta é que as equações são de execução lenta, em comparação à criptografia simétrica. Não que isso faça muita diferença hoje em dia, mas os padrões de transporte de dados criptografados, por exemplo SSL e TLS, usam a criptografia assimétrica apenas para criptografar uma chave simétrica gerada “on the fly”. Isso quer dizer que os dados mesmos são transmitidos por criptografia simétrica (agradeço aos amigos Henrique Manoel e Vitalino Victor por terem me chamado a atenção para esse ponto!).

Certificados Digitais?

Um certificado é uma estrutura de dados que contém sua identidade (quem é o dono da coisa?), sua chave pública, a assinatura de alguém mais confiável do que você (no caso de certificados x509, da “autoridade certificadora”), dando autentificade à chave pública, e outros pequenos detalhes como, por exemplo, as datas onde estas informações possam ser consideradas válidas e um “número de série”. Clique no cadeado, lá em cima, antes da editbox contendo a URL deste site e veja essas informações sobre o certificado deste site. No caso deste certificado específico, ele foi gerado pelo “wordpress.com” (Subject) e assinado pelo “Go Daddy” (Issuer – que é a autoridade certificadora).

Mas, pera ai… E quanto a autenticicade do “Go Daddy”? Bem… Seu browser já vem com o certificado contendo a chave pública do “Go Daddy” para a validação… Ou seja, um certificado é validado contra a chave pública contida em outro certificado de nível superior, comumente nomeados de root certificates ou “certificados raiz”.

Certificado deste blog
Certificado deste blog

Se preferir, use o comando openssl que usei anteriormente e obtenha todas as informações do certificado…

Mas, atenção: Um certificado não contém quaisquer informações sobre a chave privada. Sua chave privada é sua e de mais ninguém… Assim, como a chave privada do wordpress é dele e ninguém deve ter acesso a ela.

Usando GPG

O mesmo ocorre quando usamos algum utilitário de criptografia assimétrica como o GnuPG ou PGP. Tudo o que você distribui para os outros é o certificado contendo a chave pública… Sua chave privada deve ficar protegida e ninguém, a não ser você, tem acesso a ela… De fato, no Linux, é comum que o keystore contendo as chaves privadas não tenham permissões para outros usuários que não o owner:

$ ls -go ~/.gnupg/secring.gpg
-rw------- 1 7513 Out 6 20:27 secring.gpg

Além disso, no caso do keystore contendo as chaves públicas (~/.gnupg/pubring.gpg), os certificados são assinados (quando o são!) por outros usuários que você considere confiáveis… Assim como você também pode assinar os certificados de outros usuários que você considere confiáveis!… O princípio é o mesmo dos certificados x509, mas sem a figura de uma “autoridade certificadora”… Para determinar a confiabilidade desses certificados você deve conferir as informações por algum canal que considere “seguro”… Mas, note… Você não está trocando as chaves, só conferindo dados com base em alguma matemática arcana. É o caso do fingerprint, por exemplo.

Deixe-me estressar isso, antes de mais nada: O GnuPG e o PGP foram criados para criptografar e decriptografar informações usando o esquema de assimétrico mas, em essência, ele não está nem ai para a confiabilidade das chaves. É tarefa do usuário garantir que tenha chaves confiáveis e existem meios para que isso seja garantido, usando alguma inteligência…

Suponha que você coloque as mãos em um certificado contendo minha chave pública (pode obtê-la facilmente usando o GnuPG, como mostrado abaixo):

$ gpg --recv-keys fredericopissarra@gmail.com

Como o GnuPG não liga para a autenticidade da chave, se você me conhece, basta fazer uma ligação telefônica pra mim e me perguntar se o fingerprint de meu certificado é o que você obtém na linha de comando abaixo:

$ gpg --fingerprint --list-keys fredericopissarra@gmail.com
pub   4096R/C09C2054 2016-10-06 [expires: 2019-10-06]
      Key fingerprint = 11A5 2C9C E02A 24AA EBFC  046B 20AA 0246 C09C 2054
uid                  Frederico Lamberti Pissarra <fredericopissarra@gmail.com>
sub   4096R/F9AA8B75 2016-10-06 [expires: 2019-10-06]

Se você está satisfeito com minha resposta, basta assinar minha chave e mandar de volta para a internet (por favor, não faça isso sem uma confirmação do fingerprint… você só estará colocando a si mesmo em risco se essa chave não for a minha!):

$ gpg --sign-key fredericopissarra@gmail.com
$ gpg --send-keys fredericopissarra@gmail.com

O ponto aqui é que você tem que encontrar algum canal de comunicação comigo que seja seguro. Pode ser até por linguagem de sinais ou mensagens de fumaça, não importa… Desde que você e eu tenhamos certeza que seja seguro o suficiente para que ninguém possa se passar por mim…

É claro que, antes que você possa fazer isso, terá que ter gerado seu próprio par de chaves (usando a linha de comando “$ gpg --gen-key“)… E antes que a sua assinatura chegue a constar no meu keystore tenho que ter confiado na sua chave e, para isso, preciso de sua chave pública e precisarei ligar pra você para conferir o fingerprint

Para exportar seu certificado existem duas opções: Usar a linha de comando abaixo e obter um arquivo texto chamado pubkey.asc, contendo o certificado… Ou enviá-lo para um diretórios de chaves e me enviar a sua identificação (e-mail, por exemplo):

$ gpg -o pubkey.asc -a --export <seu-email-aqui>

Sobre a confirmação de confiabilidade, note que o fingerprint não é a única informação… Sua chave tem um hash. O hash “simplificado” da chave pública acima é C09C2054. Você pode obter o hash “completo” com:

$ gpg --keyid-format long --fingerprint \
  --list-keys fredericopissarra@gmail.com
pub   4096R/20AA0246C09C2054 2016-10-06 [expires: 2019-10-06]
      Key fingerprint = 11A5 2C9C E02A 24AA EBFC  046B 20AA 0246 C09C 2054
uid                          Frederico Lamberti Pissarra <fredericopissarra@gmail.com>
sub   4096R/DFF95257F9AA8B75 2016-10-06 [expires: 2019-10-06]

O hash “longo” é 20AA0246C09C2054. Há também as datas de validade, e meu nome e endereços completos, bem como o tamanho da chave e o algoritmo (4096 bits, RSA)…
Esse “hash” é, na verdade, o verdadeiro identificador “único” do certificado e pode ser usado no lugar do meu e-mail, nas linhas de comando.

Usando GPG para enviar e-mails criptografados e/ou assinados

O plugin mais famoso para usar GPG em clientes de e-mail como Thunderbird é o Enigmail. No caso do Outlook, o GnuPG para Windows (aqui) distribuí um módulo para ele e o instala automaticamente.

Usando GPG para assinar commits e tags no Github

O GIT permite que você assine commits e tags e o Github valida esses objetos desde que sua chave pública esteja cadastrada lá. No caso de commits, basta adicionar a opção -S na linha de comando. No caso de tags, a opção -s. Se você possuir apenas um par de chaves nos seus keystores, elas serão as default, caso contrário, você pode editar o arquivo ~/.gnupg/gpg.conf e alterar a linha contendo default-key, alterando o id da chave para a sua preferida.

Outros sistemas de controle de versão parecem ter suporte para o GPG também. Acredito, mas não estou certo, que o subversion e o Maven o tenham…

Usando GnuPG para criptografar simétricamente:

Vocẽ também pode fazer uma criptografia simétrica usando, por exemplo, AES. Para saber quais os algoritmos estão disponíveis na sua instalação do GnuPG basta pedir a versão:

$ gpg --version
gpg (GnuPG) 1.4.20
Copyright (C) 2015 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later 
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Home: ~/.gnupg
Supported algorithms:
Pubkey: RSA, RSA-E, RSA-S, ELG-E, DSA
Cipher: IDEA, 3DES, CAST5, BLOWFISH, AES, AES192, AES256, TWOFISH,
        CAMELLIA128, CAMELLIA192, CAMELLIA256
Hash: MD5, SHA1, RIPEMD160, SHA256, SHA384, SHA512, SHA224
Compression: Uncompressed, ZIP, ZLIB, BZIP2

Pode default o GnuPG usa AES128 (ou, simplesmente AES). Para criptografar simetricamente com o GnuPG você pode fazer:

$ gpg -o <arquivo criptografado> -c \ 
  -e <arquivo original>

A seguir uma chave será pedida duas vezes… Se quiser mudar o algoritmo use a opção --cipher-algo e informe uma das opções de cifras acima. O GnuPG automaticamente usa ZLIB para comprimir os dados criptografados, é claro que você também pode mudar isso usando a opção --compress-algo (eu não recomendo. ZLIB é padrão e muitas vezes dá resultado melhor que o ZIP).

Encontrando o EPSILON

Pelo que foi dito anteriormente pelo Fred, só nos resta caçar o tal do EPSILON.

Eis uma idéia:

#include <float.h>
#include <stdio.h>

int main(void)
{
    /* Programa Epsilon
     * Objetivo:
     *      Determinar a precisão da máquina
     */

    int i;
    double eps, eps1;

    /* A variável eps irá conter a precisão da máquina */

    i = 0;
    eps = 1.0;
    eps1 = 0.0;
    do  {
        eps /= 2.0;
        eps1 = eps + 1.0;
        printf(""%3dª reduzida eps = %-10.10g \n"", ++i, eps);
    } while ( eps1 > 1.0);

    printf("A máquina pensa que '%10.10g' é igual a zero\n", eps);

    return 0;
}

Aqui, depois da

53ª reduzida eps = 1.110223025e-16 
A máquina pensa que '1.110223025e-16' é igual a zero

{}’s
MaRZ

Fonte: converti este código, originalmente em Fortran, do velho e empoeirado livro de cálculo numérico.

Curiosidade que pode virar bug

zero nove nove noveHoje meu filho me veio da escola com esta: – pai a professora disse que 1 = 0.9999999…, pois não se consegue a fração geratriz do número, ela não existe, daí ele me mostra o que é; e eu, com a maior cara de babaca, não entendi imediatamente, mas tudo bem. Fomos para o computador e depois de uns bc’s e dc’s (sim, eu mostro estas coisas e ensino c pro meu filho de 13 anos) eu aprendi mais esta. Devo ter matado aula neste dia.

Na wikipedia encontra-se isto:

In mathematics, the repeating decimal0.999… which may also be written as 0.9, 0.9 with dot over the 9 or 0.(9), denotes a real number that can be shown to be the number one. In other words, the symbols 0.999… and 1 represent the same number. Proofs of this equality have been formulated with varying degrees of mathematical rigour, taking into account preferred development of the real numbers, background assumptions, historical context, and target audience.

Logo eu pensei, quantas comparações em código fonte se esquecem, assim como eu deste detalhe, portanto que fique anotado aqui: cuidado com o 0.9999…!

{}’s

MaRZ