criptografia

5/13/2018 criptografia - slidepdf.com

http://slidepdf.com/reader/full/criptografia-55a756f2b1f88 1/4

XX Encontro Anual de IniciaçãoCientífica – EAIC

X Encontro de Pesquisa - EPUEPG

ESTUDO E IMPLEMENTAÇÃO DE CRIPTOGRAFIA UTILIZANDOPROGRAMAÇÃO PARALELA

Alessandro Dias Batista, Richard A. Gonçalves (Orientador)e-mail: [email protected]

Universidade Estadual do Centro-Oeste, Setor de Ciências exatas eTecnologia, Departamento de Ciência da Computação, Guarapuava-PR.

Área: 1.03.00.00-7 Ciência da Computação Sub-área: 1.03.03.00-6

Metodologia e Técnicas da ComputaçãoPalavras-chave: Criptografia, OpenMP, Programação Paralela, RSA.

Resumo: Algoritmos para criptografia podem demorar tempos excessivos para

codificar/decodificar grandes volumes de dados. A fim de diminuir o tempogasto nessas operações será analisada uma melhor forma de seimplementar um algoritmo de criptografia utilizando programação paralela. Oalgoritmo RSA será implementado de maneira sequencial e paralela -utilizando OpenMP. Os resultados obtidos demonstram ganhos significativos

de desempenho com a paralelização do algoritmo.

Introdução

A criptografia é o estudo dos princípios e técnicas pelas quais ainformação pode ser transformada da sua forma original para outra ilegível,de maneira que possa ser conhecida apenas por seus destinatários,tornando-a difícil de ser lida por alguém não autorizado (KNUDSEN, 1998). A criptografia envolve algoritmos de encriptação (codificação da mensagemoriginal) e descriptação (decodificação da mensagem encriptada) (HOOK,2005; SCHNEIER, 1996). A criptografia é utilizada em empresas, bancos,

sistemas web para manter a segurança de dados sigilosos principalmente seos dados necessitem transitar por meios de comunicação. Algumasaplicações de criptografia exigem respostas em tempo real, o quenormalmente não é possível sem o uso de computação paralela.

Computação paralela corresponde ao uso simultâneo de múltiplosrecursos computacionais (unidades de processamento, unidades funcionais,computadores, etc.) para a solução de um problema (ANSHUL.; KARYPIS.;KUMAR, 2003). A programação paralela trata do desenvolvimento dealgoritmos que exploram de maneira eficiente a computação paralela(BARNEY, 2010b; PARHAMI, 1999). Existem diversar maneiras de seprogramar paralelamente, dentre elas destaca-se a biblioteca OpenMP. OOpenMP é uma API padrão para escrever aplicações paralelas em memória

Anais do XX EAIC – 20 a 22 de outubro de 2011, UEPG, Ponta Grossa –PR.ISSN:1676-0018 http://eventos.uepg.br/eaic/portal/





compartilhada nas linguagens C, C++ e Fortran (CHAPMAN; JOST; PAS,2008; QUINN, 2004). Consiste de diretivas para o compilador, rotinas emtempo de execução e variáveis de ambiente. A especificação é mantida peloOpenMP Architecture Review Board (www.openmp.org). O OpenMP é opadrão de fato para o desenvolvimento de aplicações paralelas emarquiteturas de memória compartilhada.

O objetivo da pesquisa é que com a implementação de um algoritmode criptografia utilizando computação paralela o processo paracodificar/decodificar um grande conjunto de dados seja feito em um temposignificativamente menor se comparado ao tempo que seria gasto se o

conjunto de dados fosse tratado utilizando um algoritmo de criptografiasequencial.

Materiais e métodos

O algoritmo de criptografia a ser paralelizado é o RSA (RIVEST,SHAMIR e ADLEMAN, 1977), utilizando a linguagem programação C em conjunto coma API OpenMP. O algoritmo RSA, cujo nome é uma homenagem aos seuscriadores, foi uma das primeiras soluções para a criptografia de chavepública e continua sendo utilizado até hoje. O RSA envolve duas chaves:uma pública e uma privada. A chave pública é compartilhada por todos os

usuários enquanto a chave privada deve ser mantida em sigilo. Todamensagem codificada utilizando uma chave pública só pode ser decodificadautilizando a chave privada correspondente. A criptografia RSA ainda é muitoutilizada em aplicações web, em particular em e-mails e sistemas de compra(SECURITY Inc., 2002).

Algoritmo RSA

O primeiro passo do algoritmo RSA é a geração do par de chaves. Para issoescolhe-se dois números primos relativamente grandes (p e q, da ordem decentenas de dígitos). Computa-se então o valor de n (que é o produto de p

por q). Então calcula-se a função totiente em n (que é igual a (p – 1)*(q –1)). Escolhe-se então um inteiro e positivo menor que o valor da funçãototiente de tal forma que e e o valor da função sejam primos entre si.Finalmente, computa-se o valor d que é o inverso multiplicativo de e emaritmética modular (onde o módulo utilizado é o valor da função totiente). Achave pública é composta pelo par n e e e a chave privada é composta pelopar n e d.

A codificação da mensagem c se dá através do cálculo m = ce mod ne a decodificação acontece pela fórmula c = md mod n. Para fins práticos,como a exponenciação é muito custosa, utilizam-se técnicas que aceleram oprocessamento (MENEZES; van OORSCHOT e VANSTONE, 1996).


http://www.openmp.org/

http://www.openmp.org/





Ferramentas

As ferramentas utilizadas para o desenvolvimento do código são descritasabaixo:

• C (linguagem de programação): É uma linguagem de programaçãocompilada baseada na linguagem B, inventada por Dennis Ritchiepara desenvolver o sistema operacional Unix (KERNIGHAN;RITCHIE, 1988).

• OpenMP: É uma API para programação paralela em memóriacompartilhada. O OpenMP não é uma nova linguagem de

programação. Em vez disso, é a notação que pode ser adicionado aum programa sequencial em Fortran, C ou C++ para descrever comoo trabalho deve ser compartilhado entre os segmentos que serãoexecutados em diferentes processadores ou núcleos e ordenar osacessos aos dados compartilhados, conforme necessário(BRESHEARS, 2009; CHAPMAN; JOST; PAS, 2008).

Resultados e Discussão (Arial 12, Negrito, alinhado à esquerda)

Para se testar a eficiência da paralelização foram codificados edecodificados 5 vetores de mensagens aleatórias, cada um com o tamanha

descrito na Tabela 1. Os testes foram realizados em um AMD Dual Core. Ospeedup médio alcançado foi de 1,79 e a eficiência média de 89,59 %, oque são valores bastante expressivos. Cabe destacar que tanto o speedupquanto a eficiência tenderam a aumentar com o tamanho da mensagem.

Tabela 1 – Resultado dos testes executados.

Unidades deprocessamentoutilizadas

1 2 2 2

tamanho da

mensagem

tempo serial

(segundos)

tempo paralelo

(segundos)

speedup Eficiência (%)

21 92,64 52,25 1,7730540836 88,6527041794100 445,87 258,67 1,7236925527 86,1846276365200 895,70 499,79 1,7921591225 89,6079561257400 1792,69 976,18 1,8364338544 91,8216927206

800 3575,47 1949,83 1,8337342230 91,6867111492

Média 1360,48 747,34 1,7918147672 89,5907383623

Conclusões (Arial 12, Negrito, alinhado à esquerda)

Os algoritmos de criptografia são importantes para garantir a segurança desistemas computacionais. Eles costumam ser custosos do ponto de vista do






consumo de recursos computacionais, portanto a paralelização dos mesmosé interessante. Este trabalho apresentou uma paralelização para o algoritmoRSA. Os resultados obtidos incentivam trabalhos futuros em outrosalgoritmos.

Agradecimentos (Arial 12, Negrito, alinhado à esquerda)

Referências BRESHEARS, C. The Art of Concurrency . Ed. O'Reilly. 2009.

CHAPMAN, B.; JOST, G.; PAS, V. R. Using OpenMP - Portable SharedMemory Parallel Programming. Ed. MIT Press. 2008.

Gimenez, J. R. B. Implementação do Algoritmo RSA,http://www.unesp.br/~jroberto/rsa.pdf . Acessado em: 11/07/2011.

HOOK, D. Beginning Cryptography with Java, Wrox, 2005.

Katz J.; Lindell Y. Introduction to Modern Cryptography. Ed. Chapman &

Hall/CRC Press. 2008.

Kernighan, B. W.; Ritchie, D. M. The C Programming Language. 2 Edição,Prentice Hall, 1988.

KNUDSEN, J. Java Cryptography, O'Reilly, 1998.

Menezes, A. J.; van Oorschot, P. C. e Vanstone, S. A. Handbook of AppliedCryptography. CRC Press, 1996.

QUINN, M. J. Parallel Programming in C with MPI and OpenMP . [S.l.]: Mc-Graw-Hill Science/Engineering/Math, 2004.

Rivest, R.; Shamir, A. e Adleman, L. On Digital Signatures and Public KeyCriptosystems, MIT – Laboratory for Computer Science Technical Memoran-dum 82, 1977.

SECURITY Inc., RSA RSA Security Inc. Public-Key Cryptography Standards(PKCS), 2002.

Schildt H. C Completo e Total 3ª Edição. Ed. Makron Books. 1997

SCHNEIER, B. Applied Cryptography, John Wiley and Sons, 1996.


http://www.unesp.br/~jroberto/rsa.pdf

http://www.unesp.br/~jroberto/rsa.pdf

Documents

criptografia