gildot

Topo
Sobre
FAQ
Tópicos
Autores
Preferências
Artigos
Sondagens
Propor artigo


8/3
gildicas
9/30
jobs
10/9
perguntas
10/25
press

 
Descoberta revolucionária
Contribuído por scorpio em 26-02-02 18:25
do departamento matemática
Cifragem Segundo este email enviado para a Criptography Mailing-list, foi descoberta uma nova forma bastante mais rápida de factorizar números primos. O autor é o conhecido Dan Bernstein (autor do qmail, publicfile et al), que publicou um paper disponível neste URL (está slashdotted ou gildotted, o que preferirem). Uma das implicações indicadas é o grau de confiança que podemos ter nas chaves de 2048 bits do PGP. Sigam a discussão no grande irmão.

Banda Larga nas escolas portuguesas ?? | Direitos Digitais na Europa  >

 

gildot Login
Login:

Password:

Referências
  • gildot
  • este email
  • neste URL
  • no grande irmão
  • Mais acerca Cifragem
  • Também por scorpio
  • Esta discussão foi arquivada. Não se pode acrescentar nenhum comentário.
    slashdotted ou gildotted? (Pontos:3, Engraçado)
    por RaTao em 26-02-02 19:21 GMT (#2)
    (Utilizador Info)
    um pouco de humor:

    no meu dicionario estas palavras têm significados diferentes. slashdotted é quando um site tem mais pedidos do que consegue suportar, por isso está inacessivel. gildotted é quando um site tem tanta a gente a falar mal dele que o próprio sysadm o coloca offline :>

    mais, vamos ter uma thread na ml do openbsd se o site estiver realmente slashdotted (e n~ao gildotted). isto porque o DJB vai atribuir o facto da maqina nao estar acessivel ao openbsd e nao ao publicfile. o Theo, quando souber da novidade vai mandar 20 ou 30 insultos para a ml e pronto... mais um efeito gildot na ml do openbsd.

    ehehehehhe


    Regards,
    Nuno Silva aka RaTao
    Fácil... (Pontos:3, Interessante)
    por pmsac em 26-02-02 19:32 GMT (#3)
    (Utilizador Info) http://2130706433/
    Factorizar primos é fácil: os únicos factores são o próprio número e 1. Decompor um número nos seus factores primos é que poderá ser complicado ;)
    -- pmsac.oO(Cogito sumere potum alterum)
    Resumo (Pontos:2, Esclarecedor)
    por js em 26-02-02 19:49 GMT (#4)
    (Utilizador Info)

    Dois servidores que ainda conseguem servir: um, outro

    O resumo da coisa é este: Com o novo método (que se baseia em comparações de custos de factorização), é tão dispendioso factorizar um número como antes era factorizar outro número três vezes menor (de facto, 3.009... vezes menor). Ou seja, para manter o mesmo nível de segurança, as chaves públicas têm que ter três vezes mais digitos.

    A coisa baseia-se em custos, pois envolve cálculos relativos à construção de hardware específico para reslover o problema. Pelo menos, foi o que eu entendi...

    Actualização: Don't panic (yet) (Pontos:2, Esclarecedor)
    por js em 26-02-02 19:58 GMT (#5)
    (Utilizador Info)

    A redução de custos que implica factorizar com a nova técnica um número três vezes maior é assimptótica, ou seja, é válida para grandes números apenas.

    Não se sabe se tem alguma utilidade para números do tamanho dos habitualmente usados nas chaves públicas (1024 bits, 2048 bits...)

    Informação publicada na usenet.

    Alguma informação dobre factorização (Pontos:2, Informativo)
    por Anonimo Cobarde em 26-02-02 20:14 GMT (#6)
    Uma técnica assimétrica (o RSA á apenas uma delas) baseada na factorização de inteiros que use um par de chaves com um módulo de 1k bits tem cerca de 80 bits de segurança.

    Esta segurança mede-se em relação aos melhores métodos actuais para factorização (o "quadratic sieve", o "number filed sieve" e o "EC sieve")

    Faça-mos algumas contas!

    Sopunhamos que temos um ataque comp'letamente paralelizável usando 1 milhão de processadores e fazendo, cada um, 1 milhão de ataques por segundo. Dou de barato de não existe qualquer overhead ligado à comunicação. Então o ataque leva cerca de 2^40 segundos. Dado que 1 ano são cerca de 2^25 segundos, o ataque leva cerca de 2^15 anos.

    Segundo o que percebio paper fala de um ganho de um factor 3. Assim, em vez de levar 2^15 anos, leva 1/3 disso.

    Estou preocupadissimo. jmv

    Não é uma redução dum factor no tempo! (Pontos:3, Esclarecedor)
    por js em 26-02-02 20:23 GMT (#7)
    (Utilizador Info)

    Não é o tempo que reduz para 1/3, mas o tamanho do número que aumenta 3 vezes. Como a factorização cresce exponencialmente com o tamanho do número, isto representa uma redução para 1/3 do expoente do tempo.

    Pegando no teu exemplo, o tempo não passa de 2^15 para 1/3; o que passa para 1/3 é o "15", ou seja, o tempo passa de 2^15 para 2^5.

    É certo que 2^5 ainda são bastantes anos, mas...

    Re:Não é uma redução dum factor no tempo! (Pontos:0)
    por Anonimo Cobarde em 27-02-02 23:56 GMT (#15)
    É preciso ver qual foi a máquina tomada como referencia. De facto a maquina sugerida seria capaz de quebrar uma chave DES ou inverter uma chave RSA de 512 bits em 1seg.

    Se fosse possivel construir tal maquina e se fosse completamente evidente a afirmação do JS então teriamos realmente um ataque em 32 anos.

    Porem ambos os "Se" são muito duvidosos.

    Em primeiro lugar, que eu saiba, ainda estamos muito longe de construir tal máquina. Por muito fraco que o DES seja, ainda não é realista quebra-lo com recursos razoaveis, e muito menos em 1 segundo.

    Quanto a observação do JS ela não é completamente justa. O que o Daniel Bernestein propõe é investigar a possibilidade de uma maquina formal (e não hardware especifico) que faça uma paralelização realista sobre algoritmos conhecidos.

    A maquina que apresentei anteriormente e completamente ficticia e é apresentada com paralelização irrealista. Não é possivel, por isso, aplicar a essa maquina uma nova paralelização como o DB propõe.

    jmv

    Pergunta a propósito (Pontos:3, Esclarecedor)
    por js em 27-02-02 11:01 GMT (#9)
    (Utilizador Info)

    Há uma coisa que me intriga nos algoritmos assimétricos. Suponhamos que a chave pública é um número grande, produto de dois primos também grandes, enquanto que a chave privada é formada pelos dois primos arranjados de forma a serem facilmente separáveis. Argumenta-se que não é praticável descobrir a chave privada a partir da pública por ser demasiado complicado factorizar esta.

    No entanto, a chave pública teve que ser construída.

    Seja {P<Nmax} o conjunto dos primos menores que Nmax, e suponha-se que o algoritmo escolhe aleatoriamente dois números do conjunto {P<Nmax}. Neste caso, a única maneira de determinar os primos é efectivamente factorizar a chave pública. No entanto, suponho (e esta é a primeira dúvida) que o algoritmo que constrói a chave não tem acesso ao conjunto {P<Nmax}, mas apenas a um subconjunto deste. Baseio esta suposição na crença de que calcular números primos grandes é complicado, e de que não existe nenhuma expressão simples que permita calcular o n-ésimo primo, mesmo com a restrição de nos limitarmos a primos do conjunto {P<Nmax}, ao passo que acredito que existam expressões que permitem calcular primos do conjunto {P<Nmax} pertencentes a certas classes (por exemplo, primos da forma (2^n)-1). Suponho serem expressões desse tipo que o algoritmo usa para fazer a sua escolha "aleatória" de números primos. É uma escolha aleatória limitada a certas classes de números.

    A ser assim, o algoritmo apenas usa primos de certas classes, que formam um subconjunto de {P<Nmax}. Levantam-se então duas questões.

    Questão simples:
    Quantos elementos tem esse subconjunto? Um ataque brute-force à chave pública tem que correr todos os números do subconjunto (e não todos os primos). São muitos?

    Questão complicada:
    É sabido que factorizar um número em primos é um problema complicado, cuja dificuldade cresce exponencialmente com o tamanho do número a factorizar. Mas aqui estamos a falar do problema, diferente, de factorizar um número sabendo de antemão que os seus factores primos se limitam a certas classes! Será que este problema, mais limitado e com mais informação à partida, é igualmente um problema de complexidade exponencial?

    É que, à partida, não me espantava nada que da mesma matemática que torna possível deduzir expressões simples para obtenção de primos grandes de certas classes, torne também mais fácil a factorização de números compostos por primos dessas mesmas classes...

    Re:Pergunta a propósito (Pontos:1)
    por ptome em 27-02-02 13:02 GMT (#11)
    (Utilizador Info)
    Espero que esta resposta esclareça a tua dúvida. Os meus conhecimentos nesta área não me permitem mais do que citar o "Applied Cryptography" (os bolds são meus):
    But if factoring numbers is so hard, how can generating prime numbers be easy? The trick is that the yes/no question, "Is n prime" is a much easier question to answer than the more complicated question, "What are the factors of n?".

    The wrong way to find primes is to generate random numbers and then try to factor them. The right way is to generate random numbers and test if they are prime. There are several probabilistic primality tests; tests that determine whether a number is prime with a given degree of confidence. Assuming this "degree of confidence" is large enough, these sort os tests are good enough. I've heard primes generated in this manner called "industrial-grade primes": These are numbers that are probably prime with a controllably small chance of error.

    Resumindo: factorizar um numero é difícil, encontrar um numero primo é dificil (excepto para alguns subconjuntos), mas encontrar um número que provavelmente é primo (sem as restrições desses subconjuntos) é mais fácil. Depois o livro indica alguns algoritmos para realizar estes testes.
    Re:Pergunta a propósito (Pontos:4, Informativo)
    por cgd em 27-02-02 14:51 GMT (#12)
    (Utilizador Info)

    o que propoes nunca poderia funcionar, porque os programas de break, iriam usar o mesmo subconjunto. nem os primos usados sao os de mersenne, senao far-se-ia um "run" por esses primos, para se quebrar as chaves.

    o truque, como foi dito em cima, é que é dificil factorizar numeros (porque é sempre algo deterministico, ou seja, tem de haver um produto de primos exactamente igual ao valor inicial), mas arranjar numeros pseudo-primos, é muito mais facil (computacionalmente). é nesta diferenca que reside a seguranca da criptografia. os algoritmos para arranjar numeros quase primos, normalmente sao aleatorios.

    este problema (o que descreves, dos subconjuntos), é muito semelhante às passwords. existem alguns administradores de sistemas que usam geradores aleatorios , para fornecer a primeira password aos novos users. eles ficam todos contentes, porque têm passwords construidas com alguma logica (letras, numeros, alguns simbolos, whatever), e sao o suficientemente aleatorias para serem dificeis de quebrar. o problema, é que ao limitarem o universo de passwds aleatorios, tb estao a limitar o numero de tentativas para quebra-las. qualquer crack que gere (brute force) todas as combinacoes (bom, para ser mais exacto, sao as permutacoes) feitos com os simbolos que os geradores usam, ou que, analisando a logica do gerador, gere todos os valores possiveis a partir do padrao, consegue em muito menos tentativas quebrar passwds. isto vinha descrito no famoso Crack do alex muffet, se bem me lembro.

    ainda em relacao aos primos, repara neste algoritmo:
    a = uniform(2,n-1)
    if n is even: return false
    return abs( a ^ (n-1)/2 % n ) == 1

    num teste que eu fiz, fazendo n de 10..32000 os 3428 primos existentes foram correctamente detectados (nenhum ficou por detectar) e 59 foram falsamente detectados. ou seja, a probabilidade de dizer se n é primo, é bastante elevada, e nao se fazem muitas operacoes, tendo em conta que "a" e "n" serao grandes e as funcoes de random (a uniform() de cima), podem ser feitas com uma multiplicacao e uma soma.

    o algoritmo de cima, é o de Rabin (rabin prime test). é dito se o teste for repetido k=log2(n) para o mesmo n, se essas k vezes retornarem true, entao n é primo com cerca de 100% de certeza.

    quem se quiser divertir, tem aqui um prog em C que implementa a coisa.


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

    #define MAXPTEST 32000

    #define init_uni() srand(time(0))
    static int uniform(int a, int b)
    {
      int k = rand();
      return k == RAND_MAX ? b : k / (RAND_MAX / (b - a + 1)) + a;
    }

    static unsigned long dexp(unsigned long g, unsigned long A, unsigned long p)
    {
      unsigned long n = A;
      unsigned long y = g;
      unsigned long a = 1;

      while (n > 0) {
        if ((n & 1) == 1)
          a = (a * y) % p;
        y = (y * y) % p;
        n /= 2;
      }
      return a;
    }

    static int ptest(unsigned long n)
    {
      unsigned long res;
      if ((n & 1) == 0)
        return 0;
      res = dexp(uniform(2, n - 1), (n - 1) / 2, n);
      return (res == 1) || (res == (n - 1));
    }

    static int rep_ptest(unsigned long n, int reps)
    {
      while (reps--) {
        if (ptest(n) == 0)
          return 0;
      }
      return 1;
    }

    int main(int argc, char **argv)
    {
      unsigned long i;
      int reps;

      init_uni();
      reps = 0;
      if (argc == 2)
        reps = atoi(argv[1]);
      if (!reps)
        reps = 1;

      for (i = 10; i <= MAXPTEST; i++) {
        if (rep_ptest(i, reps)) {
          printf("%lu\n", i);
        }
      }
      return 0;
    }


    -- carlos

    Re:Pergunta a propósito (Pontos:2)
    por Tintim em 27-02-02 22:31 GMT (#13)
    (Utilizador Info) http://paulo.trezentos.gul.pt
    Apenas mais algumas achegas :-))

    As duas respostas anteriores focaram na ideia de que, na verdade, os números primos seleccionados e cujo produto resulta na chave pública, não pertencem a um lote (conjunto) especifico mas que são números que na altura da criação da chave são encontrados (pseudo-)aleatoriamente e depois testada a sua primalidade.
    Se "parecem" ser primos, servem para produzir a chave. Se não, tem de ser encontrados outros.
    De qualquer forma, o teu raciocínio está intimamente relacionado com os modernos algoritmos de factorização... mas na lógica inversa.
    Imaginemos que realmente os primos encontrados não pertencem a um conjunto de números com propriedades específicas e que os diferenciem.
    Será um problema de "brute-force attack"?
    Não...isto se em vez de testarmos todos os elementos de Z (inteiros), encontrarmos um grupo (um "anel") de números que se verifique que contêm elementos potencialmente com mais possibilidades de serem primos.
    Assim, e voltando à questão inicial, usamos o conhecimento sobre conjuntos de números não porque eles tenham sido à partida utilizados para gerar a chave, mas porque é mais provavel que os números primos originais pertençam a esse sub-conjunto de números do que ao grupo mais abrangente de todos os números inteiros (Z).

    Arriscando uma simplificacao exagerada, pode-se dizer que a factorização pela curva elíptica consiste em achar uma curva em cujos pontos por onde ela passa, estão possíveis primos. Os pontos na curva pertencem a um anel, que tem por ex. a operação + e que permite ir somando pontos, para achar outros pontos.
    No NFS - Number Field Sieve (e tb no MPQS) o que é utilizado são propriedades das congruências que nos indicam que se acharmos raízes de X^2=Y^2 mod N (onde N é a chave pública), essas raízes têm 50% hipótese de ser os primos originais.

    Ainda não vi o algoritmo indicado, mas estou curioso.
    Re:Pergunta a propósito (Pontos:2)
    por Gamito em 28-02-02 0:40 GMT (#16)
    (Utilizador Info) http://gamito.freezope.org/
    Viva!

    Só por curiosidade...

    Se bem percebi tens um subconjunto de Z (chamemos-lhe Z'), que é "representável" por uma elipse.

    Ora este Z' não é a uma dimensão ?
    Se não, quais são as grandezas representáveis nos eixos ? Ou reformulando, em que tipo de plano é "desenhada" essa elipse ?

    Por outro lado e já agora, só por curiosidade novamente, como é que defines nesse anel a operação "+" por forma a manteres a integridade (i. e., respeitares as propriedades de...) desse mesmo anel e a certeza de que sendo x primo, x "+" y é também primo? E como saber de antemão este y ?
    Responder-me-ás: "vem do conhecimento da forma da elise". Certo. Mas então como conhecer a forma da elipse de antemão ?
    Parece-me que temos uma pescadinha de rabo na boca, ou que partimos da solução para chegar ao problema...

    Mário Gamito
    Re:Pergunta a propósito (Pontos:0, Interessante)
    por Anonimo Cobarde em 27-02-02 23:40 GMT (#14)
    Numa tecnica baseada na factorização não são as chaves que são produtos de dois primos mas sim o módulo. A geração de chaves funciona do seguinte modo:

    1- Dados primos P e Q grandes e da mesma ordem de grandeza (com P-Q também da mesma ordem), calcula-se o módulo M = P * Q e o número F = (P-1)*(Q-1)

    2- Escolhe-se agora um qualquer A invertivel módulo F e calcula-se a sua inversa B; isto é, B é tal que que A*B - 1 é um múltiplo de F. A chave publica é o par (A,M) e a chave privada é o par (B,M).

    Note-se que, para calcular B a partir de A, é preciso calcular primeiro F e isso só é possivel se forem conhecidos P e Q e para isso é preciso factorizar M.

    Normalmente A e escolhido de forma a facilitar a operação criptográfica que usa a chave pública; por vezes é um pequeno primo (3 é muito usado), outras vezes é um número da forma 2^N-1 que facilita operações de exponenciação. A chave privada é o número que calhar já que é a inversa de A.

    Primos da forma 2^N-1 nunca são usados em criptografia porque geram varias falhas de segurança. Por exemplo, um módulo com um factor desta forma é facilmente factorizável.

    A geração de primos probabilisticamente seguros não é muito complicada. Normalmente usa-se um gerador pseudo-aleatorio ao qual se aplica um teste de primabilidade até acertar (a menos de um erro arbitrariamente pequeno) num numero que satisfaz o criterio.

    Ainda a proposito da proposta do Daniel Bernstein que motivou este thread. Não é absolutamente verdade que ele apresente, para um custo fixo, um aumento de 3 vezes no tamanho do número a factorizar.

    De facto lendo o documento (que é um anexo a um pedido de bolsa) o que ele se propõe é investigar a possibilidade de construir um tipo de máquina paralizável que apresente esse ganho em relação a um computador de uso geral. Ele não avança com nenhuma melhoria de ordem numérica; apenas sugere melhorias na forma de paralelizar o processamento.

    jmv

    P.S: desculpem o Anonimo Cobarde mas perdi a minha password.

     

     

    [ Topo | FAQ | Editores | Contacto ]