Thursday, March 21, 2013

Working with OpenSSL

Recently I had an assignment for my Computer Security course which required me to create server and client. I was asked to make them communicate through SSL with the use of OpenSSL. The professor warned us in advance that OpenSSL's documentation was pretty bad, but I didn't know it was that bad!

So what was supposed to be a simple program with a few lines of code (create the socket, load certificates and keys, do the handshake, check certificates, send messages and close sockets) became a huge torment. There are a few guides of how to create programs which use OpenSSL, but they don't usually explain in details what the lines of code do and are quite focused on a specific objective, so if you need a feature which is a little different it can become quite hard to adapt the examples to fulfil your needs.

I found a good site from HP explaining how create a basic program using OpenSSL, the link is: http://h71000.www7.hp.com/doc/83final/ba554_90007/ch04s03.html . I believe the explanations given suffice for most needs, but they don't explain how to use more elaborate features, and I needed some.

It was not so hard to discover how to implement some of the features, namely disabling SSLv2 (http://www.openssl.org/docs/ssl/SSL_CTX_set_options.html should be enough for most) and disabling ciphers which don't use SHA1 (SSL_CTX_set_cipher_list and the list can be found by using "openssl ciphers" at the terminal). But discovering how to access certain elements of the X509 certificate was really hard.

I was able to to find some code in the internet showing how access the Common Name in a given certificate, but was unable to find how to access other fields of the certificate. The documentation page does not mention how to access it (or at least I was unable to find anything after searching for hours) and I was unable to find any example or tutorial in the internet mentioning this. And I think I wouldn't find anything if my partner didn't have the idea of searching the headers of OpenSSL for some clues.

The function we discovered for getting the Common Name in a given certificate was

X509_NAME_get_text_by_NID(X509_get_subject_name(peer), NID_commonName, peer_CN, 256);

and so he searched for NID in the headers and was able to pinpoint them to "openssl/objects.h". There, hiding among lots of other definitions, apparently undocumented, were the definitions of the certificate fields.

So if you need to get the value of some field of the certificate, I recommend searching at objects.h and them substituting NID_commonName by the definition of the desired field, to get the email address the function call would be:

X509_NAME_get_text_by_NID(X509_get_subject_name(peer), NID_pkcs9_emailAddress, email, 256);

I hope this post might be useful for other people who might be lost trying to access the fields of a X509 certificate through OpenSSL, as it was really frustrating searching and being unable to find useful information anywhere in the internet.

Sunday, December 9, 2012

BIT - Binary Indexed Tree e Interval Product (Latin America 2012)

Eu decidi criar esse post para falar sobre as famosas Binary Indexed Trees (BITs) e explicar sua aplicação em um problema que apareceu na final brasileira da Maratona de Programação de 2012. A BIT é uma estrutura bem interessante que armazena a soma acumulada em um vetor de maneira eficiente. Seu tamanho é estático (isto é, definido ao criar a estrutura) e tem 2 operações: update(idx, val) e read(idx). update é uma função que soma val na posição idx e read é uma operação que lê a soma acumulada até a posição idx. Ambas operações são executadas em O(lgN).

Sabendo isso eu recomendo a leitura do artigo do Topcoder sobre BITs (em inglês). Não considero que seja necessário saber com detalhes por que ela funciona, o importante é saber como usá-la e quando usá-la, por isso eu não vou entrar nesse mérito. Mas se você tiver interesse em entender exatamente o funcionamento é importante saber como inteiros são representados em binário (complemento de 2).

Quem costuma usar árvores de intervalos completas deve se perguntar qual a vantagem de usar uma BIT, já que uma árvore pode fazer muito mais operações e que não dependem de começar do início. A resposta é basicamente uma: tamanho do código, o código inteiro da BIT tem umas 10 linhas, enquanto o código de uma árvore de intervalos tem bem mais do que isso. O código inteiro dela é (copiado do artigo do Topcoder):

int read(int idx){
 int sum = 0;
 while (idx > 0){
  sum += tree[idx];
  idx -= (idx & -idx);
 }
 return sum;
}
 
void update(int idx ,int val){
 while (idx <= MaxVal){
  tree[idx] += val;
  idx += (idx & -idx);
 }
}
 

Começou a achar interessante a BIT agora? Acho que a maneira mais fácil de se pensar em uma BIT quando você está trabalhando com soma acumulada é imaginar realmente que ela é um vetor de soma acumulada. Ou seja, suponha que você tenha o seguinte vetor v={0, -1, 4, 2, 1, 2}, o vetor de soma acumulada seria sum={0, -1, 3, 5, 6, 8}.

Para inicializar a BIT é preciso zerar todas posições do vetor tree. Importante: Você não pode usar a posição 0 da BIT, pois ela não é capaz de lidar com esse valor (0 & -0 = 0, ou seja, ela entra em loop infinito).

Depois, é preciso adicionar cada elemento no vetor, chamando update(i, v[i]) para assim criar o vetor de soma acumulada. Depois disso, para saber a soma acumulada até um determinado ponto basta chamar read(i), ou então, se você quiser saber a soma de um intervalo[i,j] basta fazer read(j)-read(i-1).

Se você quiser trocar o valor de uma dada posição i de a para b basta chamar update(i, -a) e update(i, b), assim o valor anterior que estava naquela posição é removido e o novo valor é inserido.

Acredito que esse é o essencial. Vamos ver a aplicação dela no problema Interval Product da final brasileira da Maratona de 2012 então? O enunciado está aqui. Recomendo a leitura com calma para entender exatamente o que o problema pede.

A solução do problema começa com a identificação de que propriedade é interessante de ser usada: não é preciso saber o valor dos números para saber se o produto é positivo ou negativo, basta saber o sinal deles, se houver um número par de números ímpares no produto então o resultado vai ser positivo, caso contrário ele vai ser negativo. Além de perceber que o produto vai ser zero se algum dos valores multiplicados for zero.

Sendo assim a ideia é usar 2 BITs, uma para guardar o número acumulado de números ímpares e outra para guardar o número acumulado de zeros.

Para cada consulta deve-se então pegar o número de ímpares no intervalo e o número de zeros, usando a ideia explicada anteriormente, e fazer a verificação se o número é positivo, negativo ou zero.

Para atualizar também é bem simples, basta manter armazenado o valor de cada posição e quando uma posição é atualizada seguir a ideia explicada para mudar o valor de um elemento na BIT. Ou seja, se o valor anterior naquela posição tinha o mesmo sinal do novo então nada muda, mas se o valor mudou de negativo pra positivo é necessário subtrair 1 na BIT de negativos, se o valor mudar de positivo pra negativo então deve ser adicionado 1 na mesma BIT. Para atualizar a BIT de zeros uma ideia similar deve ser adotada.

Bom, espero que essa breve explicação da funcionalidade da BIT possa ajudar alguém, não ficou tão bom quanto eu queria que tivesse ficado, mas serve como mais um texto a respeito.

Tuesday, September 25, 2012

Solving Altera DE1 Quartus Recognition issues

Today I received my Altera DE1 Development and Education board I had ordered. I had some trouble to get it recognized by Quartus, and below I have written what the problem was and how to solve it.

I happily unboxed the FPGA at home and followed the instructions to install the drivers, as I already had Quartus 11.1 Service Pack 2 installed in my computer, which runs Windows 7 Home Premium 64-bit. I still have to install Quartus under Linux to see how well it works.

The driver installation ran just fine, I just told Windows to search for the appropriate drivers in the C:\altera\11.1sp2\quartus\drivers folder and it did. The Operating System promptly recognized the USB-Blaster device, all was well, except for one thing.

When I ran Quartus to test the board, it didn't find any device hardware, restarting the program or the computer did no good. After that I started searching the internet for answers, as one problem hardly happens to a single person and many times the fix is already available somewhere. A long period of searching later, I finally managed to find a fix that actually worked.

The fix is quite simple in fact. First you need to uninstall the driver installed from Quartus 11. To uninstall the driver you need to go to "Devices and Printers", select USB Blaster and select Properties, then you need to select Properties again and "Change Settings", then just click Uninstall Driver. After that you should download an (far) older version of the Quartus Programmer, available at:

ftp://ftp.altera.com/outgoing/release/72sp3_quartus_programmer.exe

Then it is just a matter of installing the programmer and then doing the same driver installation procedure as described above, but this time pointing the drivers at the 7.2  version folder. For some reason the more recent versions of the drivers don't seem to work properly, go figure...

I hope to have lots of fun with this awesome FPGA from now on, if I manage to do something interesting I will try to remember to post here (even though I don't think many people read this blog anyway).

Monday, September 10, 2012

O caminho para o Canadá

Como vocês já devem saber, eu estou fazendo intercâmbio aqui no Canadá, na Universidade de Toronto, através do programa Ciência sem Fronteiras (CsF). Muita gente tem me perguntado como funciona o processo de seleção do Ciência sem Fronteiras e como fazer pra poder concorrer a uma bolsa disponível no programa.

Para ajudar possíveis interessados e aumentar a literatura a respeito do assunto eu decidi escrever alguns posts (espero escrever outros posts em breve) descrevendo como é o processo seletivo e como é a experiência de estudar e morar no Canadá.

Nesse post eu vou começar do começo, descrevendo o processo seletivo e o caminho que eu trilhei para chegar até aqui. Espero conseguir sanar as dúvidas de algumas pessoas a respeito do assunto. Posts sobre como é a vida por aqui e como é a University of Toronto ficam para depois, já que eu ainda não tenho realmente experiência para dar um relato embasado.

O edital

Bom, tudo começa com os editais do Ciência sem Fronteiras (por sinal existem editais abertos agora mesmo), os editais ficam no site do programa www.cienciasemfronteiras.gov.br . Lá é possível conferir os requerimentos dos editais atuais e ver quais editais já foram encerrados. O mais importante de se conferir em um edital é o calendário e os requerimentos para participação no programa (países de língua inglesa costumam pedir Toefl ou IELTS, mas é sempre bom ler o que o edital diz).

Depois de ver o edital é preciso analisar os prazos para fazer o exame de proeficiência e achar uma data que se encaixe no limite estabelecido. No meu caso, o edital foi lançado e o único teste que tinha provas que liberassem o resultado dentro do prazo era o IELTS, que foi o que eu fiz. Recomendo que a inscrição para TOEFL/IELTS seja feita o mais rápido possível, pois as melhores datas costumam ficar sem vagas rápido depois do edital ser lançado, e recomendo também que se você tem interesse em participar do programa você já comece a se preparar para o exame de proeficiência.

É importante lembrar também que a sua faculdade precisa te homologar para permitir que você participe do programa, esse processo varia de faculdade pra faculdade (no caso da USP é preciso se inscrever no Mundus: https://uspdigital.usp.br/mundus/editalintercambiopublicoListar?nivpbcavo=G&codmnu=2070).

O exame de proeficiência

Uma vez confirmado o interesse em participar do programa é preciso (em geral) fazer o exame de proeficiência, o ideal é se planejar e pegar uma data conveniente para você e lembrar que se ela é conveniente pra você então ela também é boa para a maioria dos interessados do CsF, então é bom se inscrever rápido. O preço do exame é carinho: U$210 para o TOEFL e R$440 para o IELTS.

As datas dos exames são: TOEFL e IELTS. Para se preparar para as provas eu recomendo procurar material direcionado para o exame que você vai fazer, é fácil achá-los na internet.

Inscrição no site

É preciso também fazer a inscrição no site do Ciência sem Fronteiras (que eu passei o link ali em cima), na inscrição você precisa enviar, se não me engano, seu histórico escolar e comprovante de proeficiência. Essa etapa deve ser bem direta e sem segredos.

O valor da bolsa

O valor da bolsa para o Canadá é de CAD984,00 mensais. Fora isso no primeiro pagamento eu também recebi CAD1400,00 de auxílio-instalação, CAD1000,00 para auxílio-bancada (notebook e livros), CAD1600,00 para passagem e CAD1200,00 para seguro-saúde. Esses pagamentos são efetuados só uma vez e em uma conta no Brasil ainda, o pagamento das 3 primeiras parcelas da bolsa é feito ainda no Brasil. Foi informado para quem enviou email perguntando que quem vai estudar em Toronto vai receber um aumento de CAD450 mensais na bolsa, espero que isso seja verdade, mas ainda não recebi nenhum pagamento depois dessa informação para poder ter certeza.

Etapas posteriores

Agora vou começar a falar mais especificamente do processo seletivo que eu participei (Canadá - CBIE), que pode ter similaridades com os outros, mas o ideal é procurar informações específicas do edital em que se está participando.

Depois de enviada a inscrição para o site do Ciência sem Fronteiras é preciso esperar o prazo para que o resultado de quem foi pré-selecionado seja divulgado. No meu caso eu recebi um email do CBIE pedindo para que eu preenchesse um formulário com algumas informações e alguns documentos. O que eu lembro que tinha de importante no formulário era:
  • Escolher 3 cursos em 3 universidades participantes em ordem de preferência
  • Histórico escolar oficial
  • Histórico escolar traduzido (tradução juramentada ou com carimbo oficial da sua Universidade)
  • Cópia da segunda folha do passaporte
  • Nota no exame de proeficiência
Depois de preenchido esse formulário foi preciso esperar de novo por novo contato, dessa vez de alguma das universidades que você escolheu, pedindo mais informações ou documentos adicionais, as informações poderiam incluir as matérias de interesse dependendo da instituição. No caso da University of Toronto eu recebi um email pedindo para que eu listasse as matérias que eu queria fazer em cada um dos períodos letivos e um professor para fazer pesquisa junto (ainda não sei se vou de fato fazer pesquisa com o professor que eu escolhi).

Depois disso foi preciso esperar de novo, agora pela confirmação se eu seria selecionado pela UofT ou não. Felizmente a resposta foi positiva. Recebi então a carta de aceite da Universidade. Depois de ter sido selecionado por uma universidade foi a vez do CNPq ratificar que eu ia ser agraciado com uma bolsa e enviar termo de concessão e os últimos documentos para poder dar entrada no visto canadense.

Feito isso, de posse do termo de concessão e carta de aceite e comprovante de pagamento do visto (R$240,00) eu dei entrada no visto, processo que pode ser feito através do VAC ou diretamente no consulado canadense. Depois disso, alguns dias depois eu recebi o pedido de exame (todos que vão estudar por mais de 6 meses no Canadá precisa fazer os exames) e marquei a consulta em um médico credenciado pelo consulado (lista de médicos). A consulta custou R$280,00 e o médico pediu 3 exames (raio-x do tórax, exame de sangue e exame de urina), fiz esses exames pelo convênio. O médico enviou então esses exames para Ottawa (paguei R$120,00 pelo envio, que foi feito por Fedex).

Pouco depois de dar entrada no visto foi a vez de ir atrás de passagens, pois esperar o visto sair para comprá-las acabaria ficando muito caro.

Feito todo o processo do visto e com passagens compradas restou esperar o visto chegar, o que aconteceu apenas uma semana antes da data da viagem, mas felizmente tudo deu certo e não foi preciso remarcar as passagens.

Esse post ficou gigante, dizer que ficou grande seria bondade, mas descrever todo o processo do CsF com um mínimo de detalhes realmente é uma tarefa longa. Espero que esse post possa ajudar alguém que esteja com dúvidas. Minha ideia é escrever em breve um relato de como foram minhas primeiras semanas aqui no Canadá e como é a vida por aqui.

Wednesday, July 11, 2012

Lista de exercícios para a OBI

Quem já está acompanhando aqui no blog os comentários sobre os problemas da lista de exercícios para a OBI já está sabendo, mas como a ideia é que todos possam treinar para a OBI com esses problemas, explicarei do que ela se trata.

A lista que está disponível aqui já está com os problemas da primeira semana de treinamento disponível, ela tem 3 níveis, P1, para aqueles que fizeram esse ano PJ e ano que vem farão a prova de P1; P2, para quem fez P1 esse ano; e P2++, problemas mais difíceis e voltados para aqueles interessados em se preparar para a seletiva para a IOI do ano que vem.

O objetivo não é competir para ver quem resolve mais problemas da lista, o intuito desse placar é apenas permitir que exista uma referência de comparação para saber como está seu andamento. Por favor, levem a lista a sério e não fiquem fazendo brincadeiras com os nomes dos colegas, e sejam honestos, marquem apenas os problemas que vocês realmente fizeram.

Mesmo que você não tenha participado da OBI esse ano ou então nem mesmo participe da OBI, você é bem vindo a resolver os problemas propostos, o foco principal é OBI, mas os problemas mais difíceis devem ser interessantes até para quem participa da Maratona de Programação.

A ideia é soltar também sempre comentários sobre os problemas propostos, com códigos da solução depois de um tempo, de forma a auxiliar aqueles que estão com mais dificuldades na resolução ou que querem apenas descobrir se existe outra maneira de resolver o problema. Contribuições de comentários e códigos são, é claro, sempre muito bem vindas.

Ainda não resolvi os problemas Garota Hiperativa (na verdade eu resolvi esse durante a própria prova da Maratona em 2010, mas preciso relembrar e pensar novamente) e Metrô Engenhoso, então, se alguém quiser contribuir com comentários ou soluções, por favor, é só me falar.

Passando a limpo os problemas propostos para a primeira semana:


P1:
Burning Midnight Oil - Comentários
Binary and octal - Comentários
Summation - Comentários
Aeroporto - Comentários
Plug-in - Comentários (outro)
P2:
Regular Bracket Sequence - Comentários
Investindo no mercado de ações 1 - Comentários
Matrizes - Comentários
Bitmap - Comentários
P2++:
Os doces da Candy - Comentários e solução
Cerca do jardim - Comentários e solução
Garota hiperativa
Metrô engenhoso - Resolução do Marcos

Espero colocar os códigos de todos problemas que já têm comentários em breve, mas sintam-se livres pra contribuir com códigos também. Os comentários e solução dos problemas Os doces da Candy e Cerca do Jardim estão em inglês pois eu tinha feito eles no começo do ano e a ideia era atingir o maior público possível com a solução.

Update: O Marcos Kawakami postou comentários da solução para o problema Metrô engenhoso, muito bem feitos por sinal, o link foi adicionado

Update2: Todos problemas das listas da P1 e P2 estão com códigos da solução já disponíveis, só falta agora o problema Garota Hiperativa, que eu espero postar em breve

Matrizes - OBI 2010 e Bitmap - Spoj

E para finalizar os comentários sobre os problemas selecionados para a primeira lista de treinos para OBI, vou falar em um mesmo post do problema Matrizes, da OBI 2010 e disponível no SpojBR (link) e do problema Bitmap, do Spoj (link).

Começando pelo problema Matrizes, o enunciado dá uma fórmula para gerar os valores das matrizes quadradas A e B e pede o valor de uma célula da matriz C = A x B. O tamanho máximo das matrizes é 105 e o valor máximo de cada célula é 104. Ou seja, cada matriz tem 105 x 105 elementos, o que já mostra que é inviável gerar as matrizes para calcular a matriz C resultante.

Pensando com calma em como é feita uma multiplicação de matrizes você consegue perceber que para calcular o valor de uma determinada célula apenas uma linha de A e uma coluna de B importam. Dessa forma basta fazer a soma das multiplicações da linha pela coluna e o valor da posição pedida na matriz C é obtido. É importante lembrar que a soma pode estourar um inteiro comum, já que 105 x 104 x 104 é maior do que 231.

Agora sobre o problema Bitmap, do Spoj (link). O enunciado começa definindo a distância entre dois pontos de uma imagem preto e branco como a distância de Manhattan delas (ou seja, a soma das diferenças absolutas entre x e y) e a partir daí ele pede a distância de cada ponto da imagem para o ponto branco mais próximo.

Observando como é feita a distância entre dois pontos (cada ponto fica a distância 1 de seus vizinhos que dividem um lado com eles) é possível pensar em uma BFS, já que ela é capaz de encontrar o menor caminho entre dois pontos em um grafo no qual as arestas têm todas o mesmo custo.

Mas essa BFS tem uma sacada, você não tem apenas um ponto de partida, pois você quer saber qual a distância mínima de um dos pontos brancos para cada um dos pontos pretos, dessa forma, é como se você estivesse começando sua busca em cada um dos pontos brancos existentes e a partir daí você vai marcando as células encontradas e ainda não visitadas com a distância mínima.

Códigos do Andrei para os problemas Matrizes: http://ideone.com/O5nVk e Bitmap: http://ideone.com/vdliv

Investindo no mercado de ações 1 - SpojBR

Olá a todos, o problema da noite será o Investindo no mercado de ações 1 (link), problema que foi apresentado Maratona Mineira de 2012 e que está disponível no SpojBR.

O que ele pede, sem a história, é o seguinte: qual o número de partes mínimo em que é preciso dividir um número sendo que cada parte é dividida em duas novas enquanto ela for maior do que K? Cada parte é dividida da seguinte forma: N -> teto(N/2) e chão(N/2) (teto arredonda a divisão pra cima e chão arredonda pra baixo).

Para resolver esse problema é simples, basta simular as divisões, armazenando em quantas partes cada número é dividido para evitar ficar recalculando o mesmo estado diversas vezes.

Código do Andrei para o problema (o ideal seria ter armazenado os valores, mas não é necessário nesse caso): http://ideone.com/A7Sk6