Neste trabalho é apresentado um pouco da história da criptografia, assim como sua importância nos dias atuais, a base da teoria dos números e de congruência modular necessárias para compreender a criptografia RSA, que é o foco deste trabalho. A criptografia RSA é a mais usada atualmente por causa da dificuldade em ser decodificada. Foi elaborada e apresentada uma aula aos alunos do ensino fundamental e médio participantes do Programa de Iniciação Científica Júnior da OBMEP, sendo mostrado o porquê ela funciona, os métodos de codificação e decodificação. / In this work some of the history of cryptography is presented, as well as its nowadays applications. The RSA encryption is the most widely used because of the difficulty to being decoded. In order to understand the RSA encryption, which is the focus of this work, we recall some basis of number theory and modular congruence. Also, it was prepared and presented a lecture to the students of middle and high school participants in the Program of Junior Scientific Initiation of OBMEP, being shown why it works, methods of encoding and decoding.

Submitted by Jean Medeiros (jeanletras@uepb.edu.br) on 2016-03-08T12:22:19Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) PDF - Uelder Alves Galdino.pdf: 2990739 bytes, checksum: 2d1c78fa9140b6729d1026a52998782f (MD5) / Approved for entry into archive by Secta BC (secta.csu.bc@uepb.edu.br) on 2016-03-23T16:18:15Z (GMT) No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) PDF - Uelder Alves Galdino.pdf: 2990739 bytes, checksum: 2d1c78fa9140b6729d1026a52998782f (MD5) / Made available in DSpace on 2016-03-23T16:18:37Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) PDF - Uelder Alves Galdino.pdf: 2990739 bytes, checksum: 2d1c78fa9140b6729d1026a52998782f (MD5) Previous issue date: 2014-09-26 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work is a guiding approach consists of examples of practical applications and presentation of important concepts related to number theory, confronting the current way of inserting these in basic education which often are considered boring and devoid of practicality. For this reason, it has been Cryptography as a science of great practical applicability of these, especially nowadays due to the flow of important transactions by electronic means, subject to interception by third parties. On occasion some subjective methods of cryptography, with emphasis on the RSA method, a major public-key cryptosystem was presented. Thus, from the earliest historical accounts the chapters theoretical foundation was always possible to realize the importance of these issues, in particular the cryptographic processes studied, a significant contribution to the teaching that demystifies and provides a constructivist learning, as we believe that students can make great discoveries as creating subject of his ideas, especially in problem solving. / Este trabalho consiste numa abordagem norteadora constituída por exemplos de aplicações práticas e apresentação de importantes conceitos relativos à Teoria dos Números, confrontando a maneira atual de inserção destes no ensino básico que por muitas vezes são considerados enfadonhos e desprovidos de praticidade. Por essa razão, tem-se a Criptografia como uma ciência de grande aplicabilidade prática destes, principalmente na atualidade devido ao fluxo de importantes transações efetuadas por meio eletrônico, passíveis de interceptação por terceiros. Na ocasião foram apresentados alguns subjetivos métodos de Criptografia, com ênfase ao método RSA, um relevante sistema criptográfico de chave pública. Assim, desde os relatos históricos iniciais aos capítulos referentes à fundamentação teórica foi sempre possível perceber a importância destes temas, em particular aos processos criptográficos estudados, para uma contribuição significativa que desmistifica o ensino e proporciona um aprendizado construtivista, pois acreditamos que o aluno poderá fazer grandes descobertas como sujeito criador de suas ideias, especialmente na resolução de problemas.

CoordenaÃÃo de AperfeÃoamento de Pessoal de NÃvel Superior / Desde o advento da escrita, o envio de mensagens secretas tem sido uma importante maneira de guardar sigilo de informaÃÃes confidenciais. A arte de elaborar mensagens a partir de cÃdigos secretos surge na figura da criptografia que, com o passar do tempo, estende os seus serviÃos Ãs transaÃÃes comerciais realizadas pela internet. O principal algoritmo utilizado pela internet recebe o nome de RSA. Assim, a criptografia RSA codifica nÃmeros de cartÃes de crÃditos, senhas de bancos, nÃmeros de contas e utiliza para isso elementos de uma importante Ãrea da MatemÃtica: a Teoria dos NÃmeros. / Since the advent of writing, sending secret messages has been an important way to maintain confidentiality of sensitive information. The art of crafting messages from secret codes appears in the figure of encryption that over time extends its services to commercial transactions over the Internet. The main algorithm used by the internet is called RSA. Thus, the RSA Encryption encodes credit card numbers, bank passwords, account numbers and uses for that elements of an important area of mathematics: number theory.

Les ELISA (Enzyme-Linked ImmunoSorbent Assay) sont une des technologies analytiques les plus utilisées dans la recherche et les applications biomédicales. Leur production nécessite la construction de films d’anticorps sur des surfaces constituées le plus souvent de polystyrène. La haute hydrophobie du polystyrène assure une adhésion forte et spontanée des anticorps permettant ainsi d’y construire facilement une monocouche d’anticorps. L’amélioration des ELISA passe certainement par l’amélioration et la compréhension des mécanismes physico-chimiques à l’œuvre lors de l’immobilisation des anticorps sur le polystyrène. Dans ce but, ce travail présente un essai de théorisation appuyé par des simulations numériques et des estimations expérimentales par microscopie à force atomique (AFM) et ELISA. En faisant référence à l’effet hydrophobe, la thermodynamique des processus irréversibles permet premièrement d’expliciter les raisons de l’adhésion des anticorps sur le polystyrène. Deuxièmement, des simulations numériques dans le cadre du modèle des additions séquentielles aléatoires (RSA) montrent la façon dont peuvent se saturer les surfaces en favorisant certaines orientations d’anticorps recherchées dans le cadre de l’ELISA. Finalement, l’amélioration du modèle RSA en un modèle RSA+R tenant compte des changements d’orientations par relaxation des anticorps illustre le lien entre les conditions de dépôt et la structure de la monocouche obtenue. Ces éléments semblent corroborés par l’expérience / ELISA (Enzyme-Linked ImmunoSorbent Assay) are widely used analytical technologies in research and biomedical fields. Their implementation require to build antibodies thin films onto predominantly composed polystyrene surfaces. The high hydrophobicity of polystyrene ensures spontaneous and strong antibodies adhesion allowing to easily build antibodies monolayers. ELISA improvements lie most probably throughout improvements and comprehension of physico-chemical mecanisms on which antibodies immobilization on polystyrene are relied. In this way, our work explains a therozation essay emphasized by numerical modelling and experimental estimations by atomic force microscopy (AFM) and ELISA. Keeping in mind the so-called hydrophobic effect, thermodynamics of irrversible processes allows in a first time explaining reasons of antibodies adhesion on polystyrene. In a second time, numerical modelling in the field of random sequential additions model (RSA) show a way of surfaces saturation involving a strong trend to favor some antibodies orientations expected for ELISA. Finally, a RSA improvement in a RSA+R model taking into account orientational changes by the way of relaxation shows a link between deposition conditions and obtained monolayer structure. Such results seem to be strongly correlated with experimental facts

Com o surgimento da criptografia de chave pública, muito esforço foi feito para a criação de protocolos de criptografia e de assinatura que fossem comprovadamente seguros contra indivíduos maliciosos. Existem várias definições de segurança, tanto para protocolos de criptografia como para protocolos de assinatura, e também existem vários modelos de adversários, que simulam um indivíduo malicioso tentando corromper o protocolo. A família de protocolos de assinatura Rabin possui os recordes de velocidade de vericação da assinatura, chegando a ser até 100 vezes mais rápida do que o RSA. Este trabalho apresenta uma redução eficiente de segurança no modelo do oráculo aleatório para uma variante do protocolo de assinatura Rabin descrito por Bernstein, onde não é necessário o uso de nenhuma função para geração de bits pseudo-aleatórios, o que torna o protocolo mais robusto. A redução apresentada é uma redução polinomial e eficiente do problema da fatoração de inteiros para o problema de quebrar o protocolo Principal Rabin-Williams B = 0. / With the development of public-key cryptography, many efforts were made to build encryption and signature protocols that were provably secure against malicious adversaries. There are many definitions of security for encryption and signature protocols, and there are many adversary models to simulate the behaviour of a malicious adversary against a given protocol. The Rabin family of signature protocols has the speed records for verification of signature, being up to 100 times faster than RSA. This work presents a tight security proof in the random oracle model for a variant of the Rabin signature protocol presented by Bernstein, that does not require the use of pseudo-random bits, making the protocol more robust. The proof presented here is a polynomially tight reduction for the problem of integer factorization to the problem of breaking the Principal Rabin-Williams B = 0 protocol.

Neste trabalho é apresentado um pouco da história da criptografia, assim como sua importância nos dias atuais, a base da teoria dos números e de congruência modular necessárias para compreender a criptografia RSA, que é o foco deste trabalho. A criptografia RSA é a mais usada atualmente por causa da dificuldade em ser decodificada. Foi elaborada e apresentada uma aula aos alunos do ensino fundamental e médio participantes do Programa de Iniciação Científica Júnior da OBMEP, sendo mostrado o porquê ela funciona, os métodos de codificação e decodificação. / In this work some of the history of cryptography is presented, as well as its nowadays applications. The RSA encryption is the most widely used because of the difficulty to being decoded. In order to understand the RSA encryption, which is the focus of this work, we recall some basis of number theory and modular congruence. Also, it was prepared and presented a lecture to the students of middle and high school participants in the Program of Junior Scientific Initiation of OBMEP, being shown why it works, methods of encoding and decoding.

La transmission de données multimédia sur les réseaux sécurisés a une croissance exponentielle grâce aux progrès scientifique dans les technologies de l'information et de la communication. La sécurité des données dans certaines applications comme le stockage sécurisé, l'authentification, la protection des droits d'auteurs, la communication militaire ou la visioconférence confidentielles, nécessitent de nouvelles stratégies en matière de transmission sécurisée. Deux techniques sont couramment utilisées pour la transmission sécurisée de données visuelles, à savoir : la cryptographie et la stéganographie. La cryptographie sécurise les données en utilisant des clés secrètes afin de rendre les données illisibles, la stéganographie, elle, vise à insérer des données cruciales dans des signaux porteurs anodins.De plus, pour la confiance mutuelle et les systèmes distribués, le partage sécurisé de ressources est souvent une garantie suffisante pour les applications de communication. L'objectif principal de cette thèse est de réaliser une protection des données visuelles, en particulier les images numériques, par le biais des techniques modernes de cryptographie. Dans ce contexte, deux objectifs de recherche ont été développés durant ces travaux de thèse.La première partie de notre travail se concentre sur la sécurité des images numériques dans un environnement partagé. Ensuite, la deuxième partie porte sur l'intégrité des données visuelles pendant une transmission sécurisée.Nous avons proposé un nouveau schéma de partage des images qui exploite les propriétés d'addition et de multiplication homomorphique de deux crypto systèmes à clé publique largement utilisés : les algorithmes RSA et Paillier. Dans les schémas traditionnels de partage sécurisé, le ``dealer'' partitionne le secret en parties et le distribue à chacun des autres acteurs. Ainsi, aucun des acteurs impliqués ne participe à la création du partage sécurisé, mais il est toujours possible que le ``dealer'' transmette des données malveillantes. Au contraire, l'approche proposée utilise le système de partage de secret d'une manière qui limite l'influence du ‘‘dealer'' sur le protocole en permettant à chaque acteur de participer.La deuxième partie de ces travaux de thèse met l'accent sur l'intégrité des données visuelles lors de la transmission. L'intégrité des données signifie que les données gardent leurs structures complètes au cours d'une opération numérique comme le stockage, le transfert ou la récupération. Le changement d'un seul bit de données cryptées peut avoir un impact catastrophique sur les données décryptées. Nous abordons le problème de correction d'erreurs dans les images cryptées en utilisant le chiffrement à clé symétrique AES (Advanced Encryptions Standard) suivant différents modes. Trois mesures sont proposées afin d'exploiter les statistiques locales des données visuelles et l'algorithme de chiffrement, dans l'objectif de corriger les erreurs efficacement. / Due to the advancements in the information and communication technologies, the transmission of multimedia data over secure or insecure communication channels has increased exponentially. The security of data in applications like safe storage, authentications, copyright protection,remote military image communication or confidential video-conferencing require new strategies for secure transmission. Two techniques are commonly used for the secure transmission of visual data, i.e. cryptography and steganography. Cryptography achieves security by using secret keysto make the data illegible while steganography aims to hide the data in some innocent carrier signal. For shared trust and distributed environment, secret sharing schemes provide sufficient security in various communication applications. The principal objective of this thesis is to achieveprotection of visual data especially images through modern cryptographic techniques. In this context, the focus of the work in perspective, is twofolded. The first part of our work focuses on the security of image data in shared environment while the second part focuses on the integrity ofimage data in the encrypted domain during transmission.We proposed a new sharing scheme for images which exploits the additive and multiplicative homomorphic properties of two well known public key cryptosystems, namely, the RSA and the Paillier. In traditional secret sharing schemes, the dealer partitions the secret into shares and distributethe shares to each of the player. Thus, none of the involved players participate in the creation of the shared secret and there is always a possibilitythat the dealer can cheat some player. On the contrary, the proposed approach employs the secret sharing scheme in a way that limits the influence of the dealer over the protocol by allowing each player to participate. The second part of our thesis emphasizes on the integrity of visual data during transmission. Data integrity means that the data have its complete structure during any operation like storage, transfer or retrieval. A single bit change in encrypted data can have catastrophic impact over the decrypted data. We address the problem of error correction in images encrypted using symmetric key cryptosystem of the Advanced Encryption Standard (AES) algorithm. Three methods are proposed to exploit the local statistics of the visual data and the encryption algorithm to successfully correct the errors.

Les petits ARN (ARNS) sont impliqués dans la régulation post-transcriptionnelle des voies métaboliques et dans les réponses aux stress et la virulence. Chez Staphyloccus Aureus, RNAIII, l’effecteur principal du système AGR, agit comme un ARN antisens pour réguler l’expression de protéines de parois cellulaires et de nombreux cytotoxines en fin de phase de croissance exponentielle. Une série de petits ARN-RSA, ont été découverts par notre équipe en 2009. Les objectifs de cette étude sont : 1) Construire des outils génétiques pour étudier leurs fonctions, II) Analyser leur expression dans diverses conditions in Vitro et in Vivo. Ainsi, nous avons déterminé le niveau d’expression de 4 ARNS (RSAA, RSAE, RASG et RSAH) et ARNIII, lorsque la bactérie a été exposée à divers antibiotiques ou en contact avec d’autres bactéries comme Pseudomonas. Des concentrations sub-inhibitrices (1/16 et 1/8 MIC) de la lévofloxacine augmentent l’expression de RSAH dans RN6390, mas pas dans HG001. Le niveau d’expression de RSAG et RSAH ont été augmentés en présence de P. Aeruginosa, mais le mécanisme de cet effet n’a pas été élucidé. Les données obtenues à partir d’échantillons humains ont montré que l’expression globale des cinq petits ARN a été extrêmement variable dans les abcès, plus homogène dans les crachats des patients atteints de mucoviscidose, et très homogène dans les échantillons de colonisation nasale. Le modèle d’expression particulier des ARNS associé à la colonisation nasale pourrait refléter le commensalisme de S. Aureus dans cette niche. / Small RNAs (sRNAs) are involved in the post-transcriptional regulation of metabolic pathways and in responses to stress and virulence. In Staphylococcus aureus, RNAIII, the main effector of the Agr system, acts as an antisense RNA to regulate the expression of many cell wall proteins and cytotoxins in late-exponential growth phase. A series of novel sRNAs – Rsa were discovered by our team in 2009. The objective of this study is i) to construct genetic tools to study their functions and ii) to analyze their expression in various conditions in vitro and in vivo. Thus, we determined the expression level of 4 sRNAs (RsaA, RsaE, RsaG and RsaH) and RNAIII, when the bacterium was exposed to various antibiotics or in contact with other bacteria such as Pseudomonas. Subinhibitory concentrations (1/16 and 1/8 MIC) of levofloxacin could enhance the RsaH expression in RN6390, not in HG001. RsaG and RsaH level were increased in the presence of P. aeruginosa, however the mechanism of this effect has not been elucidated. Data obtained from human samples showed that the global expression of the five sRNAs was extremely variable in the abscesses, more homogeneous in the sputa of cystic fibrosis patients, and highly uniform in the nasal carrier samples. The unique expression pattern of sRNA associated with nasal colonization might reflect the commensalism of S. aureus in this niche.

Sistemas criptográficos como o RSA e o Diffie-Hellman sobre Curvas Elípticas (DHCE) têm fundamento em problemas computacionais considerados difíceis, por exemplo, o problema do logaritmo (PLD) e o problema da fatoração de inteiros (PFI). Diversos trabalhos têm relacionado a segurança desses sistemas com os problemas subjacentes. Também é investigada a segurança do LSB (bit menos significativo) da chave secreta no DHCE (no RSA é o LSB da mensagem) com relação à segurança de toda a chave. Nesses trabalhos são apresentados algoritmos que conseguem inverter os sistemas criptográficos citados fazendo uso de oráculos que predizem o LSB. Nesta dissertação, fazemos a implementação de dois desses algoritmos. Identificamos parâmetros críticos e mudamos a amostragem do formato original. Com essa mudança na amostragem conseguimos uma melhora significativa nos tempos de execução. Um dos algoritmos (ACGS), para valores práticos do RSA, era mais lento que a solução para o PFI, com nosso resultado passou a ser mais veloz. Ainda, mostramos como provas teóricas podem não definir de maneira precisa o tempo de execução de um algoritmo. / Cryptographic systems like RSA and Elliptic Curve Diffie-Hellman (DHCE) is based on computational problems that are considered hard, e.g. the discrete logarithm (PLD) and integer factorization (PFI) problems. Many papers investigated the relationship between the security of these systems to the computational difficulty of the underlying problems. Moreover, they relate the bit security, actually the LSB (Least Significant Bit), of the secret key in the DHCE and the LSB of the message in the RSA, to the security of the whole key. In these papers, algorithms are presented to invert these cryptographic systems making use of oracles that predict the LSB. In this dissertation we implement two of them. Critical parameters are identified and the original sampling is changed. With the modified sampling we achieve an improvement in the execution times. For practical values of the RSA, the algorithm ACGS becomes faster than the PFI. Moreover, we show how theoretical proofs may lead to inaccurate timing estimates.

[pt] Essa dissertação se propõe a introduzir nas aulas de matemática da escola básica um tema que traga significado e interesse ao alunado e que, a partir dele, seja possível desenvolver conteúdos novos e clássicos da disciplina, pertinentes a esse nível de escolaridade. O tema escolhido foi a criptografia que possibilitou o desenvolvimento de uma abordagem histórica da sua evolução até o código RSA, a promoção de discussões sobre a relevância atual do assunto até os nossos dias e o trabalho com conteúdos importantes da matemática. Com o intuito de aprimorar e avaliar a proposta, uma pequena aplicação numa escola pública foi feita, através de uma oficina, com resultados bastante satisfatórios. Pretende-se que este trabalho seja mais uma fonte para auxiliar diversos professores na construção de novas propostas pedagógicas adaptadas à realidade de cada sala de aula com olhar motivador, significativo e contemporâneo. / [en] This dissertation proposes to introduce in the math class of the elementary school a theme that brings meaning and interest to the students and, from it, it is possible to develop new and classic content, relevant discipline at this level of education. The theme chosen was the encryption that made possible the development of a historical approach of its development until the RSA code, the promotion of discussions on the current relevance of the subject until our days and working with important content of mathematics. In order to improve and evaluate the proposal, a small application in a public school was made, through a workshop, with results quite satisfactory. It is intended that this work is more a source to assist several teachers in the construction of new pedagogical proposals adapted to the reality of each classroom with motivating, meaningful and contemporary look.