Mais um blog inútil.

Pois é, meus amigos.

Há alguns dias deparei-me com isto: http://forum.kaspersky.com/index.php?showtopic=71652

Aparentemente, os bons senhores da Kaspersky acham boa ideia factorizar um módulo de 1024 bits para de alguma forma combater o ransomware gpcode. Boa sorte com os vossos 100 anos de factorização.

E que tal obterem o utilitário que faz a decriptação (paguem ao gajo se for preciso, nós também temos de vos pagar), e extrairem de lá a chave? Sim, já que não percebem de criptografia, ao menos de reverse engineering devem ter umas luzes.

Enfim.

As putas e a crise

As putas e a inflacção

As putas e as condições laborais

As putas e os seus preços

Há cerca de 2 dias, estava eu a me actualizar acerca dos preços dos bens de consumo corrente, descobri que 20 minutos de sexo com uma meretriz custam a módica quantia de 20€, preservativo (Colocado com a boca) e alojamento incluídos, sendo o broche uns meros 5€.

Mas o que é isto caralho?!!?!?

Ataum, lá por elas serem dos Palops da América do Sul, ou dos Palops da Ucrânia, fazem uma desfeita a estas gajas que ganham a vida a irem prá cama ( ou de encontro à parede) com gajos das obras a cheirar a cavalo e a falarem axim?!

VINTE EUROS SEUS SOMÍTICOS?! POR UMAS BOMBADAS CONAIS?!

Preço de “calle” em Madrid… 30 euros, com puta **** estrelas.

Preço de rua aqui em Faro, ali ao pé do Modelo, numa vivenda lá por trás, que tem uma cortina vermelha na janela, 3 putas em serviço rotativo e uma “Madama”… 20 euros.

Eu passo a explicar porque é que estes preços me revoltam:

Há cerca de 20 anos atrás, dar uma foda a uma puta de ar maternal e 90kgs de peso, custava  ao servente de obras nortenho , 4 contos. Nada de coisas “fancies”,era entrar bombar, sair,bidé… PRÓXIMO!

E sim minhas senhoras, ao fim do mês eles faziam fila!!! Indiana! Com as 4 notas de MIL na mão, ali à parte de baixo do cemitério de Portimão.

Agora a parte da conclusão/questão/tesão/dá cá 20 euros que eu pago-te prá semana sem falta.

Como é possível, uma gaja, estrangeira, logo producto importado, descer tão baixo ???

Pagar o mesmo que se pagava quando o Soares era 1º ministro??

Pagar o mesmo a uma gaja que nem é gorda, que se rapa na zona da cona e partes adjacentes, tem sotaque sem ser do bagaço, deixa ir ao cú e tal e assim?

4 contos pra foder a nossa avó ou 20 euros pra foder a prima emigrante?

Ainda há avós a 4 contos? Um bom dum broche numa boca que ainda tem a maior parte dos dentes de origem, 5€!??!?!?!

Eu sou um reles tuguinha de ordenado médio e dava de bom grado 20€ por semana pra me aliviar, e olha, que se foda, fumava menos, só comprava o correio da manhã dia sim dia não, e o record à 2ª feira.

Agora vou ver dos gajos que se protiputem por aqui, se é que os há, mas, a estes valores, só uma mulher pra fazer estes trabalhos mal remunerados, afinal o homem ainda ganha mais que a sua congénere feminina.

Mandem-me notas de 20€ tá bem?

Há quase 3 anos, bloguei sobre este assunto, e dei uma lista mais ou menos completa sobre as aplicações de factorização existentes.

O que mudou de há 3 anos para cá? Não muito.

A única aplicação que sofreu alterações significativas foi o msieve. Muito pela positiva. Foi-lhe acrescentado um módulo para SNFS/GNFS; embora a escolha de polinómios e o ‘siever’ não se comparem com os do Franke/Kleinjung (incluídos no GGNFS), o pós-processamento das relações é de longe superior ao do GGNFS. Note-se, no entanto, que para a raiz quadrada final o algoritmo utilizado pelo GGNFS (Montgomery/Nguyen) é bastante superior ao quase brute-forcing do msieve. Na prática não faz grande diferença excepto para números demasiado grandes para factorizar sem ter altos clusters.

A codebase do msieve também foi recentemente integrada no GGNFS; provavelmente daqui a algum tempo vamos ter apenas uma ferramenta para factorizar números, a partir destas duas.

Quero também mencionar as ferramentas “profissionais” para factorizar números. Completas só temos 2, talvez 3:

- Franke/Kleinjung

- CWI Suite

- Aoki et al.

A primeira é, tanto quanto sabemos, a melhor. Foi com ela que foram batidos todos os últimos recordes, e usa os truques todos da moda algorítmicos e tem código MPI especializado para correr em sistemas _grandes_.

A suite da CWI foi durante muito tempo a melhor, e tem código original de muitos dos gajos que desenvolveram a NFS, mas está montes de desactualizada em termos de código.

Nunca consegui olhar para as sores da suite do Aoki, mas supostamente estaria ao nível da primeira; ninguém sabe. Japs…

Para concluir, as aplicações opensores têm evoluído muito recentemente e estão ao nível das melhores neste momento. Excepto quando estamos a trabalhar com clusters/grids, onde não existe quase paralelização nenhuma (o msieve torna a solução da matriz threaded, mas podia ser muito melhor…)

Note-se que estou aqui a tratar de factorização de números “difíceis”, isto é, que só têm 2 factores e ambos grandes. Para factorizar números “normais” recomendo o GMP-ECM, que para números com múltiplos factores pequenos é muito superior (o tempo médio do ECM depende do tamanho dos factores e não do número, ao contrário do NFS).

Finalmente saiu a nova versão, com muitas cenas novas. Vejam o changelog.

http://www.truecrypt.org/

Alguns pontos dignos de nota:

- Substituição de SHA-1 por SHA-512;

- Outro modo de operação  (XTS) para além do LRW (http://eprint.iacr.org/2007/362.pdf);

- Pre-boot auth (finalmente!).

Poisé caros amigos, ando a tentar cultivar-me no mundo das telecomunicações já que sinto que tenho uma grande falha de conhecimentos nesta área e já que trabalho nela de momento, comprei um livrinho para me por a estudar.

Data and Computer Communications é o nome do livro, William Stallings o do autor (belo site web 0.5, hein?).

O livro aborda desde a parte fisica das telecomunicações (cheio de matematicas, ondas sinusoidais, algoritmos de compressao para audio e video para streaming), passando pela explicação do algoritmo de routing do Dijkstra (usado no OSPF) até ao layer 7 do modelo OSI, entre outras mil coisas que ainda nao me dei ao trabalho de ver.

O Livro tem uma capinha rijinha pelo que anda bem dentro da mala sem medo de se estragar.

AH, no prefácio o livro tem uma frase do “Alice no pais das maravilhas” do Lewis Carroll e passo a citar:

Begin at the beginning and go on till you come to the end; then stop.

Profundo, hein ?

Hoje quando cheguei ao trabalho de manhã vi este emailzinho e fiquei a chorar. Pus logo o kernel do OpenBSD a compilar com as opções:

option DRM_DEBUG
mgadrm* at vga? # Matrox G[24]00, G[45]50 DRM driver

Para poder experimentar com a minha über poderosa Matrox MGA G200 AGP :-D

Já adicionei o “XENOCARA_BUILD_DRI=yes” ao /etc/mk.conf, e ja tou a buildar as userland tools. E mais logo pra tarde quando isso acabar, vai ser o xorg!

Amanha até ligo um monitor à maquina para sentir a verdadeira beleza do FUTURO DO BSD NO DESKTOP! 2008 THE YEAR OF THE BSD DESKTOP!.

                                     _
                                    (_)
              |    .
          .   |L  /|   .          _
      _ . |\ _| \--+._/| .       (_)
     / ||\| Y J  )   / |/| ./
    J  |)'( |        ` F`.'/        _
  -< |  F         __     .-<        (_)
    | /       .-'. `.  /-. L___
    J \      <    \  | | O\|.-'  _
  _J \  .-    \/ O | | \  |F    (_)
 '-F  -<_.     \   .-'  `-' L__
__J  _   _.     >-'  )._.   |-'
`-|.'   /_.           \_|   F
  /.-   .                _.< 
 /'    /.'             .'  `\
  /L  /'   |/      _.-'-\
 /'J       ___.---'\|
   |\  .--' V  | `. `   IS DYING
   |/`. `-.     `._)
      / .-.\
      \ (  `\
       `.\

Ois. No Liber Abbaci aparece o seguinte problema:

Um homem colocou um par de coelhos num recinto cercado por todos os lados por uma parede. Quantos pares de coelhos podem ser gerados a partir desse par ao fim de um ano , sabendo que, por mês, cada par gera um novo par, que se torna produtivo no segundo mês de vida?

Reparem  na resolução: no primeiro mês de vida existe apenas o par inicial. No segundo mês continua a existir o par inicial que ficou mais maduro. No terceiro mês, nasceu outro par. No quarto mês o par inicial teve outro par, enquanto os seus filhos cresciam. No quinto mês, o par inicial e os seus filhos tiveram um par cada um. Etc…

A sucessão que se origina é 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, etc… Ok, já perceberam o que é. Fiquei a saber que está relacionada com estudos de crescimentos populacionais de várias espécies da natureza, mais precisamente abelhas, galhos nas plantas, etc.  E sabiam que o nome verdadeiro dele era Leonardo de Pisa ? Mais conhecido como Fibonacci (Filho de Bonacci). Adeus.

Ora estava aqui eu a navegar pelas Internetes quando me deparo com um documento recente relativo à geração de primos aleatórios para quer RSA quer DSS. Ei-lo aqui.

Rapidamente se reparam nos ataques óbvios relativos especialmente ao RSA: factorização por P-1 ou P+1 (Pollard e Williams, respectivamente), o expoente público tem de estar compreendido entre 2^16 e 2^256 (evitam-se assim os imensos ataques relativos a expoentes baixos, e.g. E=3 ou E=7, etc e também os ataques que permitem obter D quando E é demasiado grande (Weger)).

Uma coisa que achei interessante e que nunca tinha visto aplicada é a distinção clara feita entre os parâmetros dos primos prováveis e os provados. Talvez alguém se pergunte porque não simplesmente aumentar a probabilidade dos testes M-R (Miller-Rabin) e pronto?

A resposta reside no facto de o teste de M-R ser baseado no teorema de Fermat (sim, o mesmo utilizado na base do RSA). Existe uma classe de inteiros, chamados números de Carmichael, que passam sempre nos testes baseados no teorema de Fermat. Assim, no pior cenário temos de contar com p1,p2,q1,q2 terem factores trivialmente factorizáveis indetectáveis por M-R. Daí os parâmetros serem maiores.

É também interessante notar que os módulos de 1024 bits já não podem ser gerados aleatoriamente (tabela B.2). Isto talvez indique qualquer coisa em relação à segurança (ou os medos de quem define os standards) do problema da factorização de inteiros.

Contra toda a lógica, isto é possível. Isto é possível pelo teorema da convolução (uma vez que uma multiplicação também pode ser considerada uma convolução).

OK. Como é que isto se faz?

1 - Transformar os números a multiplicar num polinómio, escolhendo uma base apropriada (e.g. 10, 16, 2^32, etc).

2 - Calcular a DFT de ambos, através do uso de uma FFT. (Não é necessário ser estritamente a FFT, qualquer convolução em teoria dá.)

3 - Multiplicar ponto a ponto ao longo do array obtido (multiplicação diádica).

4 - Calcular a DFT inversa do resultado.

5 - Avaliar o polinómio para obter o número final.

Tanto passo para uma mísera multiplicação. Qual é a vantagem?

A vantagem reside no facto de uma FFT ter complexidade logarítmica O(N log N), assim como os outros passos. A multiplicação clássica tem complexidade O(log N^2), e outros métodos recursivos como Karatsuba ou Toom-Cook têm complexidades inferiores, mas nunca completamente logarítmicos (geralmente na forma O(log N^1+e), 1.4 < e < 2 aproximadamente).

Portanto este método é útil para multiplicar números gigantescos (para ai 10000+ bits), uma vez que a overhead só compensa a esse nível de grandeza.

Aqui está um exemplo de uma multiplicação recorrendo à FFT.