terça-feira, 24 de abril de 2007

Desafio de criptoanálise

Baal Certa vez um jornalista (esqueci o nome dele) dito especialista em criptoanálise e espionagem escreveu um livro (romance, se não me engano) onde tentava provar que não existe algoritmo criptográfico seguro (inquebrável).

Segundo ele, o que há são algoritmos virtualmente inquebráveis, ou seja, não possuímos ainda ferramentas para quebrá-los, mas no futuro os computadores quânticos poderão quebrar criptogramas de quaisquer tipos numa fração de segundos.

No entanto ele está errado.

Existem algoritmos matematicamente inquebráveis.

Para que um computador atual não consiga quebrar um criptograma basta que a probabilidade de quebra tenda a zero, mas um computador quântico (hipotético) poderia quebrar qualquer criptograma em fração de segundos não importando quão ínfima seja a probabilidade de quebra, a não ser que…

A não ser que a probabilidade seja zero. Agora a quebra de paradigmas: existem algoritmos criptográficos onde a probabilidade de quebra é exatamente zero.


Dito isso tudo, segue aqui o desafio:

Tenho um criptograma aqui (MD5), cifrado usando um algoritmo seguro.

Porém «cometi um erro» propositalmente que permite a quebra do criptograma.

A brincadeira é responder às seguintes perguntas:

  1. A mensagem é na verdade uma pergunta. Qual a pergunta?

  2. Qual a resposta à pergunta?

  3. Qual o algoritmo criptográfico usado?

  4. Qual o erro cometido?



Podem ser usadas quaisquer linguagens de programação (gostaria de ver a solução em Python).

Divirtam-se! E por favor usem os comentários do Kodumaro para discutir o assunto.

[]'s
Rodrigo Cacilhas

PS: Alguém poderia por favor calcular a entropia do criptograma?

sábado, 14 de abril de 2007

Processando XML com Lua

Lua O Projeto Kepler oferece um módulo de interface com Expat, um processador XML. O módulo se chama LuaExpat.

Na verdade o módulo oferece diretamente apenas uma função: lxp.new(), que retorna um objeto processador de XML (parser). Esta função recebe como parâmetro uma tabela especial de callbacks, que são as funções responsáveis por tratar os elementos XML.

Se for passado como parâmetro uma tabela vazia, o parser apenas verificará a integridade do código XML.

Portanto, para usar LuaExpat para tratar XML, é preciso conhecer duas coisas: os callbacks e o parser.

Callbacks


Na tabela de callbacks, as chaves devem possuir nomes específicos que indicam em que caso cada callback será usado. Os valores são funções: os callbacks.

Há toda uma lista de callbacks (neste momento em que escrevo há quinze callbacks). Vamos dar uma olhadinha apenas em três principais: StartElement, EndElement e CharacterData.


StartElement é chamado quando é encontrada a abertura de um elemento (tag), por exemplo <xhtml:div id="main">. A função possui três argumentos: parser, elementName (nome do elemento) e attributes (atributos).

O primeiro argumento recebe o próprio parser.

O segundo, elementName, recebe o nome do elemento (no exemplo, xhtml:div).

O terceiro, attributes, recebe uma tabela com os atributos, tanto de forma indexada quanto associativa. Assim, no exemplo (<xhtml:div id="main">):
{
[1] = "main";
id = "main"
}



EndElement é chamado quando é encontrado o fechamento de um elemento, por exemplo </xhtml:div>. A função possui dois argumentos: parser e elementName (nome do elemento).


Quando é encontrado um elemento simples (<elem></elem> ou <elem/>), é chamado o callback StartElement e imediatamente o callback EndElement.


CharacterData é chamado quando é encontrada uma string CDATA (conteúdo de um elemento). A função recebe dois argumentos: parser e string (o texto).

Parser


O parser é criado pela função lxp.new(), que recebe a tabela de callbacks como parâmetro.

O parser possui diversos métodos, sendo os principais parse() (que processa uma string como parte do documento XML) e close() (método de chamada obrigatória que fecha o parser).

O método parse() deve ser chamado sem parâmetros para indicar o fim do documento.

A cada chamada de parse() são retornados cinco valores:
  1. true se correu bem ou nil se ocorreu algum erro;
  2. nil se correu bem ou uma mensagem de erro no caso de erro;
  3. número da linha ou nil;
  4. número da coluna ou nil;
  5. posição absoluta ou nil;


A última chamada (sem parâmetros) retornará true se a estrutura XML estiver bem formada ou nil e uma mensagem de erro se tiver ocorrido algum erro em algum momento.


Vamos a um exemplo:
require "lxp"

local fd, l, st, erro
local contador = 0
local p = lxp.new {
StartElement = function (self, nome, atributos)
io.write("+ ", (" "):rep(contador), nome, "\n")
contador = contador + 1
end,

EndElement = function (self, nome)
contador = contador - 1
io.write("- ", (" "):rep(contador), nome, "\n")
end,

CharacterData = function (self, texto)
io.write("* ", (" "):rep(contador + 1), texto, "\n")
end,
}

-- O Leonardo percebeu um erro meu aqui: é arg, não argv
fd = io.input(arg[1])

for l in fd:lines() do
p:parse(l .. "\n")
end

fd:close()
st, erro = p:parse()
p:close()

if not st then
print("Ocorreu o seguinte erro:", erro)
end


Salve este código no arquivo xmlparser.lua. Pegue um arquivo XML qualquer e execute:
bash$ lua xmlparser.lua nome-do-arquivo.xml


Se não houver nenhum disponível, use este:
<?xml version="1.0"?>
<elem1>
texto
<elem2/>
mais texto
</elem1>


Para saber mais: LuaExpat.

[]'s
Rodrigo Cacilhas

segunda-feira, 9 de abril de 2007

Beautiful Soup e HTML Scrapping em Python

Fazer o parsing de uma página HTML que está corretamente formatada como XHTML em Python é fácil: podemos usar o módulo minidom ou, dependendo da situação, o (c)ElementTree.

Mas, e se a página não está tão corretamente formatada assim? Aí entra em cena um módulo muito interessante: o Beautiful Soup. Segundo a definição no site:O Beautiful Soup é um parser de HTML/XML para Python que pode transformar até mesmo marcação inválida em uma árvore analítica. Ele provê um modo idiomático de navegar, procurar e modificar a árvore de elementos. Ele normalmente salva o programador de horas ou dias de trabalho. Existe também um porte para Ruby chamado Rubyful Soup. (Embora o parser de HTML mal-formatado mais conhecido em Ruby seja o Hipcrot).

Um pequeno exemplo prático: vamos obter a lista das 20 linguagens de programação listadas no tiobe. Se você observar, verá que quase todo o documento está dentro de uma tabela, mesmo que isso não faça muito sentido.

Tentar fazer o parsing dessa HTML com o minidom gera uma bela exceção:

>>> dom3 = parseString(html)
Traceback (most recent call last):
File "", line 1, in ?
File "/usr/lib/python2.4/site-packages/_xmlplus/dom/minidom.py", line 1925, in parseString
return expatbuilder.parseString(string)
File "/usr/lib/python2.4/site-packages/_xmlplus/dom/expatbuilder.py", line 942, in parseString
return builder.parseString(string)
File "/usr/lib/python2.4/site-packages/_xmlplus/dom/expatbuilder.py", line 223, in parseString
parser.Parse(string, True)
xml.parsers.expat.ExpatError: mismatched tag: line 11, column 2


Ao invés disso, vamos usar o Beautiful Soup:


import urllib2
from BeautifulSoup import BeautifulSoup

tiobe = urllib2.urlopen('http://www.tiobe.com/tiobe_index/index.htm')

soup = BeautifulSoup(tiobe.read())
table = soup.findAll(id='Table2') #encontramos a tabela com o id 'Table2'
trs = soup.findAll('tr')
for tr in trs: #navegando pelos trs
tds = tr.findAll('td')
# Por causa da bagunça da página do tiobe, é necessário verificar se existem 7 dentro do tr. São esses que nos interessam.
if len(tds) == 7:
link = tds[3].find('a')
print(link.contents[0])


Em época em que se fala muito de web semântica, muitos sites oferecem conteúdo de forma razoavelmente mal formatada.Nesse mar de informação não semântica, o Beautiful Soup pode ser uma boa saída pra obter informações desses sites!

sexta-feira, 6 de abril de 2007

Alterando o comportamento de strings em Lua on-the-fly

Lua Um recurso legal de Lua é permitir a alteração do comportamento de strings «on-the-fly».

Por exemplo, strings em Lua não possuem métodos para «capitalizar» e «normalizar», mas podemos criar.

Por exemplo:
> var = "la batalema pitonisto"
> print(var:normalize())
stdin:1: attempt to call method 'normalize' (a nil value)
stack traceback:
stdin:1: in main chunk
[C]: ?


Pois é… não existe. Mas podemos criar!

Nem precisa reiniciar o interpetador. Vamos continuar daí e criar nosso normalize():
> function string:normalize()
>> local t = {}
>> local naocapitular = { "da", "das", "de", "do", "dos", "e" }
>> self:gsub("(%S+)", function (e)
>> e = e:lower()
>> local alterar, lig = true
>> for _, lig in ipairs(naocapitular) do
>> if e == lig then alterar = false end
>> end
>> if alterar then
>> e = e:sub(1, 1):upper() .. e:sub(2)
>> end
>> table.insert(t, e)
>> end)
>> return table.concat(t, " ")
>> end


Vamos analisar…

A tabela naocapitular contém uma lista dos elementos que não queremos capitular. Se quiser, você pode acrescentar outros termos de ligação, como "el", "von", "van", "and", "du", etc..

A chamada do método gsub() de self seleciona cada palavra ("(%S+)") e executa a função passada como segundo parâmetro para cada ocorrência.

A função transforma todas letras de cada palavra para minúsculas (e:lower()), depois corre um for para verificar se a palavra atual devem ou não ser capituladas.

Se a palavra deve ser capitulada, transforma a primeira letra em maiúscula (e:sub(1, 1):upper()), mantendo as demais (e:sub(2)).

Finalmente a palavra é inserida na tabela temporária.

Já no final de normalize(), o return retorna uma string, concatenando os elementos de t usando um espaço (" ") como separador.

Bem, feito isso, é só pegar o mesmo comando anterior:
> print(var:normalize())
La Batalema Pitonisto


Olha só! A string que já existia passou a ter o método normalize()!

Isso aconteceu devido à forma como Lua trata os objetos: metatabelas!

Toda string possui como metatabela uma tabela cuja chave __index aponta para o módulo string:
> print(getmetatable("").__index == string)
true


Então quando a função normalize() foi acrescentada ao módulo string, esta passou a ser método de todas as strings, mesmo as já criadas!

Com isso em mãos, as possibilidades são enormes. =)

[]'s
Rodrigo Cacilhas

PS: Veja este artigo também nas Reflexões de Monte Gasppa e Giulia C..

segunda-feira, 2 de abril de 2007

Classes singleton

Semestre passado estávamos conversando sobre singleton (veja também a página em inglês), que é quando queremos que uma determinada classe tenha somente uma instância, e esta instância seja retornada na tentativa de se criar novas instâncias.

Na época escrevi um artigo sobre o assunto e agora resolvi atualizá-lo aqui.

A idéia inicial era demonstrar como é implementado singleton em algumas linguagens e vou seguir novamente o mesmo princípio.

Java


Em Java singleton é feito «bloqueando» o construtor da classe e usando um método para intermediar esta requisição (aliás esta é a abordagem da maioria das linguagens):
class Conexao {
//Atributos

private static Conexao inst = null;

//Metodos
private Conexao() {
// O construtor é privado!

}

public static Conexao nova() {
// Este método fará as vezes do construtor
if (inst == null)
inst = new Conexao();
return inst;
}

}


Então, para criar uma conexão, não será usado new, mas o método nova():
Conexao conn = Conexao.nova();


Funciona. =)

O grande problema é que singleton não é transparente em Java. É preciso estar atento e não tentar usar new, que é a forma natural de se obter uma instância de classe. =P

Ruby


É extremamente simples fazer singleton em Ruby:
requires 'singleton'

class Conexao
include Singleton

end


Bastou um include! Isto é incrivelmente simples, prático. Quem me explicou seu funcionamento foi o Walter:

A solução de Ruby é parecida com Java e Python.

A inclusão do módulo singleton torna o construtor da classe privado. A instância é criada no momento de instanciação. Os métodos clone e dup retornam erro.

E isso tudo escondidinho, em 343 linhas de código invísiveis ao usuário :)


Python (usando herança)


Uma forma de fazer singleton em Python é usando herança. Assim podemos criar uma classe Singleton que implemente a funcionalidade (feature) desejada e herdar as demais classes dela.

Bem, em Python o construtor é __init__(), mas há um método que é chamado antes do construtor, que é __new__(), e funciona de forma muito parecida com new de Perl. Ele cria a nova instância e a retorna.

Na verdade, em Python quando fazemos:
a = X(b, c)


Por trás o que está acontecendo é:
a = X.__new__(X, b, c)
a.__init__(b, c)


Então podemos sobrescrever este método para termos singleton. A idéia é que, se já houver uma instância, o __new__() retorne esta instância em vez de uma nova:
class Singleton(object):

__inst = None

def __new__(cls, *args, **kw):
if cls.__inst is None:
cls.__inst = object.__new__(cls)
return cls.__inst

def __copy__(self):
return self

def __deepcopy__(self, memo=None):
return self


Então temos o atributo de classe privado __inst que contém nada (None) na criação da classe, mas depois será uma referência à instância única.

O método __new__() está preparado para receber argumentos genéricos (*args, **kw), mas não fará nada com eles – é problema do __init__(). A função do __new__() é verificar se já existe a instância única, se não existe, cria, depois retorna ela.

Podemos usar a herança desta forma:
class Conexao(Singleton):


Ou seja, funciona exatamente como em Ruby.

Agora vamos à crítica!

O grande problema aqui é justamente a sobrescrita um método geralmente esquecido…

Isso pode gerar uma série de problemas quando surge a herança múltipla ou quando o método é novamente sobrescrito – ou foi também sobrescrito por outra classe pai.

Para contornar estes problemas uma boa saída é o uso de metaclasses.

Python usando metaclasse


Em Python classes são objetos! São instâncias de type. Metaclasses são classes filhas de type, portanto suas instâncias também são classes.

Podemos criar uma metaclasse que tenha procedimentos que precedam o construtor e o chamem só se for preciso.

Assim as classes instância da metaclasse podem ser filhas de outras classes e possuir até herança múltipla sem problemas com sobrescrita de métodos – pois todo tratamento é realizado num escopo ainda mais protegido.

Numa metaclasse o método que precede o construtor das classes instância é – por motivos óbvios para programadores Python – __call__().

Vamos criar então a metaclasse! Vou chamar de unique em vez de singleton (Por quê? Porque eu gosto, ora pois!):
class unique(type):

def __init__(cls, name, base, dict):
super(unique, cls).__init__(name, base, dict)
cls.__inst = None
cls.__copy__ = lambda self: self
cls.__deepcopy__ = lambda self, memo=None: self

def __call__(cls, *args, **kw):
if cls.__inst is None:
cls.__inst = super(unique, cls).__call__(*args, **kw)
return cls.__inst


O construtor chama o construtor da classe pai (super) e então a única coisa diferente que ele faz é a criação de um atributo privado de classe __inst e de duas funções para tratar as cópias. Só que este atributo __inst é «mais privado» do que os normais. =)

Aqui o escopo para o atributo privado não é a classe, mas unique (a metaclasse). Podem imaginar o nível de proteção disso? É como em C++, só que funciona. =)

Bem, o método __call__() faz exatamente o mesmo que __new__() no exemplo que usa herança, só que de forma mais eficiente. A implementação disso poderia ser:
class Conexao(object):

__metaclass__ = unique



Simples! E sem os problemas que poderiam vir com o uso de herança.

Mas aí vem um espírito de porco qualquer e pergunta:

Peraí! E se eu quiser usar também outra metaclasse, como autoprop?

Ahá! Não é tão complicado assim! Veja só:
class Conexao(object):

class __metaclass__(autoprop, unique):
pass



Lua


Em Lua, assim como em Perl, o construtor é um método de classe, o que facilita muito nosso trabalho, pois cada instância deve ser criada nele.

Uma classe é uma metatabela cuja chave __index referencia a si mesma:
local Conexao = {}
Conexao.__index = Conexao


O construtor padrão (nu e cru) costuma ser:
function Conexao:new(o)
o = o or {}
return setmetatable(o, self)
end


Vamos então criar uma função unique (porque eu gosto!) que retorne uma classe cujo construtor retorne sempre a mesma instância (usando closure para isso):
local function unique()
local inst
local cmt = {}
cmt.__index = cmt

cmt.new = function(self, o)
if not inst then
o = o or {}
inst = setmetatable(o, self)
if self.__init then
inst.__init()
end
end
return inst
end

return cmt
end


Então podemos criar nossa classe Conexao assim:
local Conexao = unique()


Os demais métodos podem ser implementados normalmente e, caso seja necessário implementar alguma coisa no construtor, é possível implementando o método de instância __init().

[]'s
Rodrigo Cacilhas

Instalando Haskell no Slackware

haskell Se você é usuário de Slackware e, como eu, sofreu para tentar instalar o ghc sem sucesso, aqui segue o passo-a-passo para sair da miséria!

Estes procedimentos foram testados no Slackware 11.0.

Primeiro vamos baixar o maldito RPM. Se quiser procurar por outros pacotes, veja aqui.

Baixado o monstro, vamos convertê-lo em algo mais decente com rpm2tgz:
bash$ rpm2tgz ghc66-6.6-1.i386.rpm


Agora é possível manipular este pacote. Vamos descompactá-lo:
bash$ mkdir raiz
bash$ tar xzvf ghc66-6.6-1.i386.tgz -C raiz/


Pronto! Já podemos criar uma descrição do pacote:
bash$ cd raiz/
bash$ mkdir install/
bash$ vim install/slack-desc


Eu uso o Vim, mas use o editor que lhe convier. Escreva o seguinte conteúdo:
ghc: The Glasgow Haskell Compiler v. 6.6
ghc:
ghc: GHC is a state-of-the-art, open source, compiler and interactive
ghc: environment for the functional language Haskell.
ghc:
ghc: This package was generated by rpm2tgz
ghc:
ghc: http://haskell.org/ghc/
ghc:


Salve e já temos nossa apresentação! Agora vamos criar um instalador que publique as bibliotecas no sistema e crie alguns links simbólicos amigos do peito:
bash$ vim install/doinst.sh


O conteúdo do arquivo:
#!/bin/sh

sed -i '/\/ghc/ d' /etc/ld.so.conf
echo '/usr/lib/ghc-6.6' >> /etc/ld.so.conf

( cd /usr/bin/ ; rm -rf ghc )
( cd /usr/bin/ ; ln -sf ghc-6.6 ghc )
( cd /usr/bin/ ; rm -rf ghci )
( cd /usr/bin/ ; ln -sf ghci-6.6 ghci )

ldconfig


Não é necessário, mas gosto de ter este arquivo executável:
bash$ chmod +x install/doinst.sh


O pacote RPM tem umas maluquices, como chamar o diretório de documentação de ghc66-6.6/ (versão 6.6 da versão 6.6? Redundâncias de Fedora Core…). Vamos acertar isso:
bash$ mv usr/share/doc/ghc{66,}-6.6


Para terminar vamos criar e instalar o pacote!

Para evitar possíveis dores de cabeça, vamos fazer isso como superusuário:
bash$ su -l
bash# chown -R root:root .
bash# makepkg -c y -l y ../ghc-6.6-i386-1.tgz
bash# cd ../
bash# installpkg ghc-6.6-i386-1.tgz


E pronto! Já é possível executar ghci e testar os exemplos do Torcato.

Ah! Não esqueça de guardar bem o pacote (ghc-6.6-i386-1.tgz) e limpar a sujeira (ghc66-6.6-1.i386.rpm, ghc66-6.6-1.i386.tgz e raiz/) que deixamos para trás!

[]'s
Rodrigo Cacilhas

PS: Veja este artigo também nas Reflexões de Monte Gasppa e Giulia C..