Fundação de Amparo à Pesquisa do Estado do Rio de Janeiro / Neste trabalho discutimos vários sistemas de dígitos verificadores utilizados no Brasil, muitos deles semelhantes a esquemas usados mundialmente, e fazemos uma análise da sua capacidade de detectar os diversos tipos de erros que são comuns na entrada de dados em sistemas computacionais. A análise nos mostra que os esquemas escolhidos constituem decisões subotimizadas e quase nunca obtêm a melhor taxa de detecção de erros possível. Os sistemas de dígitos verificadores são baseados em três teorias da álgebra: aritmética modular, teoria de grupos e quasigrupos. Para os sistemas baseados em aritmética modular, apresentamos várias melhorias que podem ser introduzidas. Desenvolvemos um novo esquema ótimo baseado em aritmética modular base 10 com três permutações para identificadores de tamanho maior do que sete. Descrevemos também o esquema Verhoeff, já antigo, mas pouquíssimo utilizado e que também é uma alternativa de melhoria para identificadores de tamanho até sete. Desenvolvemos ainda, esquemas ótimos para qualquer base modular prima que detectam todos os tipos de erros considerados. A dissertação faz uso ainda de elementos da estatística, no estudo das probabilidades de detecção de erros e de algoritmos, na obtenção de esquemas ótimos. / In this paper we present several check digit systems used in Brazil, many of them similar to schemes used worldwide, and we do an analysis of their ability to detect various types of errors that are common in data entry computer systems. This analysis shows that the schemes constitute suboptimal decisions and almost never get the best rate possible error detection. Check digit schemes are based on three algebra theory: modular arithmetic, group theory and quasigroup. For the schemes based on modular arithmetic we present several improvements that can be made. We developed a new optimal scheme based on modular arithmetic base 10 with three permutations for identifers larger than 7. We also present the Verhoeff scheme, already old but used very little and that is also a good alternative for improvement identifers for size up to 7. We have also developed,optimum schemes for any modular base prime that detect all types of errors considered. The dissertation also makes use of elements of statistics in the study of the probability of error detection and algorithms to obtain optimal schemes.

In this thesis we obtain several interesting algebraic properties of the operations used in the block cipher IDEA which are important for cryptographic analyzes. We view each of these operations as a function from $mathbb Z_{2}^n times mathbb Z_{2}^n to mathbb Z_{2}^n$. By fixing one of variables $v(z)=mathbf Z$ in $mathbb Z_{2}^n times mathbb Z_{2}^n$, we define functions $mathbf {f}_z$ and $mathbf {g}_z$ from $mathbb Z_{2}^n$ to $mathbb Z_{2}^n$ for the addition $BIGboxplus$ and the multiplication $BIGodot$ operations, respectively. We first show that the nonlinearity of $mathbf {g}_z$ remains the same under some transformations of $z$. We give an upper bound for the nonlinearity of $mathbf {g}_{2^k}$, where $2leq k &lt / n-1$. We list all linear relations which make the nonlinearity of $mathbf {f}_z$ and $mathbf {g}_z$ zero and furthermore, we present all linear relations for $mathbf {g}_z$ having a high probability. We use these linear relations to derive many more linear relations for 1-round IDEA. We also devise also a new algorithm to find a set of new linear relations for 1-round IDEA based on known linear relations. Moreover, we extend the largest known linear class of weak keys with cardinality $2^{23}$ to two classes with cardinality $2^{24}$ and $2^{27}$. Finally, we obtain several interesting properties of the set $ { ({mathbf X},{mathbf X} BIGoplus {mathbf A}) in mathbb Z_2^n times mathbb Z_2^n ,|, (mathbf {X}BJoin {mathbf Z})BIGoplus( ({mathbf X} BIGoplus {mathbf A} ) BJoin mathbf {Z} ) = {mathbf B} }$ for varying ${mathbf A}, {mathbf B}$ and ${mathbf Z}$ in $mathbb Z_2^n$, where $BJoin in { BIGodot,BIGboxplus }$. By using some of these properties, we present impossible differentials for 1-round IDEA and Pseudo-Hadamard Transform.

Trapdoor functions, introduced in the seminal paper of Diffie and Hellman, are a fundamental notion in modern cryptography. Informally, trapdoor functions are injective functions that are easy to evaluate but hard to invert unless given an additional input called the trapdoor. Specifically, the classical security notion considered for trapdoor functions is one-wayness, which asks that it be hard to invert (except with very small probability) a uniformly random point in the range without the trapdoor. Motivated by the demands of emerging applications of cryptography as well as stronger security properties desired from higher-level cryptographic primitives constructed out of trapdoor functions, this thesis studies new strengthenings to the classical notion of one-way trapdoor functions and their applications. Our results are organized along two separate threads, wherein we introduce two new cryptographic primitives that strengthen the notion of one-wayness for trapdoor functions in different ways: Deterministic Encryption: Our notion of deterministic (public-key) encryption addresses the weaknesses of using trapdoor functions directly for encryption articulated by Goldwasser and Micali, to the extent possible without randomizing the encryption function (whereas Goldwasser and Micali address them using randomized encryption). Specifically, deterministic encryption ensures no partial information is leaked about a high-entropy plaintext or even multiple correlated such plaintexts. Deterministic encryption has applications to fast search on encrypted data, securing legacy protocols, and ``hedging' randomized encryption against bad randomness. We design a conceptually appealing semantic-security style definition of security for deterministic encryption as well as an easier-to-work-with but equivalent indistinguishability style definition. In the random oracle model of Bellare and Rogaway, we show a secure construction of deterministic encryption for an unbounded number of arbitrarily correlated high-entropy plaintexts based on any randomized encryption scheme, as well as length-preserving such construction based on RSA. In the standard model, we develop a general framework for constructing deterministic encryption schemes based on a new notion of ``robust' hardcore functions. We show a secure construction of deterministic for a single high-entropy plaintext based on exponentially-hard one-way trapdoor functions; single-message security is equivalent to security for an unbounded number of messages drawn from a block-source (where each subsequent message has high entropy conditioned on the previous). We also show a secure construction of deterministic encryption for a bounded number of arbitrarily correlated high-entropy plaintexts based on the notion of lossy trapdoor functions introduced by Peikert and Waters. paragraph*{Adaptive Trapdoor Functions:} Our notion of adaptive trapdoor functions asks that one-wayness be preserved in the presence of an inversion oracle that can be queried on some range points. The main application we give is the construction of black-box chosen-ciphertext secure public-key encryption from weaker general assumptions. (``Black-box' means that the specific code implementing the trapdoor function is not used in the construction, which typically incurs a huge efficiency cost.) Namely, we show such a construction of chosen-ciphertext secure public-key encryption from adaptive trapdoor functions. We then show that adaptive trapdoor functions can be realized from the recently introduced notions of lossy trapdoor functions by Peikert and Waters and correlated-product secure trapdoor functions by Rosen and Segev. In fact, by extending a recent result of Vahlis, we show adaptivity is strictly weaker than the latter notions (in a black-box sense). As a consequence, adaptivity is the weakest security property of trapdoor functions known to imply black-box chosen-ciphertext security. Additionally, by slightly extending our framework and considering ``tag-based' adaptive trapdoor functions, we obtain exactly the chosen-ciphertext secure encryption schemes proposed in prior work, thereby unifying them, although the schemes we obtain via adaptive trapdoor functions are actually more efficient. Finally, we show that adaptive trapdoor functions can be realized from a (non-standard) computational assumption on RSA inversion, leading to a very efficient RSA-based chosen-ciphertext secure encryption scheme in the standard model.

Submitted by PEDRO VALIM SAMPAIO null (pedrovalimsampaio@gmail.com) on 2018-01-11T01:06:31Z No. of bitstreams: 1 pedro-sampaio-dissertacao-pgmat-dezembro-2017-com-ficha.pdf: 8235020 bytes, checksum: 58adc9b07110ff0e572b49fd9bc15579 (MD5) / Rejected by Marcia Correa Bueno Degasperi null (mcbueno@rc.unesp.br), reason: Prezado Pedro Valim Sampaio, Solicitamos que realize uma nova submissão seguindo as orientações abaixo: - capa (faltou a capa que é elemento obrigatório no seu programa de pós-graduação. Agradecemos a compreensão e aguardamos o envio do novo arquivo. Atenciosamente, Biblioteca câmpus Rio Claro Repositório institucional Unesp on 2018-01-11T12:47:44Z (GMT) / Submitted by PEDRO VALIM SAMPAIO null (pedrovalimsampaio@gmail.com) on 2018-01-11T13:35:32Z No. of bitstreams: 2 pedro-sampaio-dissertacao-pgmat-dezembro-2017-com-ficha.pdf: 8235020 bytes, checksum: 58adc9b07110ff0e572b49fd9bc15579 (MD5) pedro-sampaio-dissertacao-pgmat-dezembro-2017-com-ficha-e-capa.pdf: 8377820 bytes, checksum: 3d6af025594125f81c9f43dc70d7b7f8 (MD5) / Approved for entry into archive by Adriana Aparecida Puerta null (dripuerta@rc.unesp.br) on 2018-01-11T16:45:12Z (GMT) No. of bitstreams: 1 sampaio_pv_me_rcla.pdf: 8271293 bytes, checksum: 10bf9858fb1a38ce127cb3c9b992f9df (MD5) / Made available in DSpace on 2018-01-11T16:45:12Z (GMT). No. of bitstreams: 1 sampaio_pv_me_rcla.pdf: 8271293 bytes, checksum: 10bf9858fb1a38ce127cb3c9b992f9df (MD5) Previous issue date: 2017-12-18 / Esta dissertação explora fundamentos comuns de dois temas, Música e Matemática, que são desenvolvidos lado a lado. Noções musicais e matemáticas são reunidas, como escalas e aritmética modular, intervalos e logaritmos, música de doze tons e aritmética modular, timbre e análise de Fourier. Quando possível, as discussões de noções musicais e matemáticas estão diretamente interligadas. Ocasionalmente o texto permanece por um tempo sobre um assunto e não sobre o outro, mas finalmente a conexão é estabelecida, tornando este um tratamento integrador dos dois assuntos. É uma tradução matematicamente comentada de uma grande parte de Mathematics and Music de David Wright. / This dissertation explores the common foundations of the two subjects, Music and Mathematics, which are developed side by side. Musical and mathematical notions are brought together, such as scales and modular arithmetic, intervals and logarithms, twelve tone music and modular arithmetic, timbre and Fourier analysis. When possible, discussions of musical and mathematical notions are directly interwoven. Occasionally the text stays for a while on one subject and not the other, but eventually the connection is established, making this an integrative treatment of the two subjects. It is a mathematically commented translation (to portuguese) of a major part of David Wright’s Mathematics and Music.

Fundação de Amparo à Pesquisa do Estado do Rio de Janeiro / Neste trabalho discutimos vários sistemas de dígitos verificadores utilizados no Brasil, muitos deles semelhantes a esquemas usados mundialmente, e fazemos uma análise da sua capacidade de detectar os diversos tipos de erros que são comuns na entrada de dados em sistemas computacionais. A análise nos mostra que os esquemas escolhidos constituem decisões subotimizadas e quase nunca obtêm a melhor taxa de detecção de erros possível. Os sistemas de dígitos verificadores são baseados em três teorias da álgebra: aritmética modular, teoria de grupos e quasigrupos. Para os sistemas baseados em aritmética modular, apresentamos várias melhorias que podem ser introduzidas. Desenvolvemos um novo esquema ótimo baseado em aritmética modular base 10 com três permutações para identificadores de tamanho maior do que sete. Descrevemos também o esquema Verhoeff, já antigo, mas pouquíssimo utilizado e que também é uma alternativa de melhoria para identificadores de tamanho até sete. Desenvolvemos ainda, esquemas ótimos para qualquer base modular prima que detectam todos os tipos de erros considerados. A dissertação faz uso ainda de elementos da estatística, no estudo das probabilidades de detecção de erros e de algoritmos, na obtenção de esquemas ótimos. / In this paper we present several check digit systems used in Brazil, many of them similar to schemes used worldwide, and we do an analysis of their ability to detect various types of errors that are common in data entry computer systems. This analysis shows that the schemes constitute suboptimal decisions and almost never get the best rate possible error detection. Check digit schemes are based on three algebra theory: modular arithmetic, group theory and quasigroup. For the schemes based on modular arithmetic we present several improvements that can be made. We developed a new optimal scheme based on modular arithmetic base 10 with three permutations for identifers larger than 7. We also present the Verhoeff scheme, already old but used very little and that is also a good alternative for improvement identifers for size up to 7. We have also developed,optimum schemes for any modular base prime that detect all types of errors considered. The dissertation also makes use of elements of statistics in the study of the probability of error detection and algorithms to obtain optimal schemes.

Submitted by Liliane Ferreira (ljuvencia30@gmail.com) on 2018-06-14T11:27:09Z No. of bitstreams: 2 Dissertação - Rodolfo Cavalcante Pinheiro - 2018.pdf: 4080017 bytes, checksum: 1b6327fe77c42c43ee400950ab032b87 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Rejected by Luciana Ferreira (lucgeral@gmail.com), reason: Verfique o local na citação. on 2018-06-15T10:27:19Z (GMT) / Submitted by Liliane Ferreira (ljuvencia30@gmail.com) on 2018-06-15T10:43:46Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Rodolfo Cavalcante Pinheiro - 2018.pdf: 4080017 bytes, checksum: 1b6327fe77c42c43ee400950ab032b87 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2018-06-15T10:47:52Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Rodolfo Cavalcante Pinheiro - 2018.pdf: 4080017 bytes, checksum: 1b6327fe77c42c43ee400950ab032b87 (MD5) / Made available in DSpace on 2018-06-15T10:47:53Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Rodolfo Cavalcante Pinheiro - 2018.pdf: 4080017 bytes, checksum: 1b6327fe77c42c43ee400950ab032b87 (MD5) Previous issue date: 2018-05-15 / This paper presents a proposal to work with Modular Arithmetic with elementary students II (6th, 7th, 8th and 9th years) in order to make the teaching of mathematics more in depth and to get rid of textbooks. We present a sequence of contents that begins in the prime and compound numbers, discusses the meanings of multiples, divisors (and the remainders of divisions) and divisibility rules. To develop the Modular Arithmetic theme we are still exploring the definitions of Diophantine Equations. We conclude by showing the applicability of the theme to the study of Cryptography (Caesar cipher and RSA method). The work still brings results of the application of the project carried out with a specific group of students in a private school in the state of Goiás. / Este trabalho apresenta uma proposta de se trabalhar com Aritmética Modular com os alunos do Ensino Fundamental II (6º, 7º, 8º e 9º anos) com o intuito de tornar o ensino de matemática mais aprofundado e de se desprender dos livros didáticos. Apresentamosuma sequência de conteúdos que se inicia nos números primos e compostos,discute-se os significados dos múltiplos, divisores (e os restos das divisões) e as regras de divisibilidade. Para desenvolver o tema Aritmética Modular ainda exploramos as definições das Equações Diofantinas. Concluímos mostrando a aplicabilidade do tema com o estudo da Criptografia (cifra de César e método RSA). O trabalho ainda trás resultados da aplicação do projeto realizado com um grupo específico de alunos em uma escola da rede particular de ensino do estado de Goiás.

The main objective of this research is to build an interest based peer – to – peer network which is structured yet non-DHT. Maintaining DHTs is a complex task and needs substantial amount of effort to handle the problem of churn. So, the major challenge facing such architectures is how to reduce this amount of effort while still providing an efficient data query service. The rationale behind choosing non- DHT based interest based network is that users sharing common interests are likely to share similar contents, and therefore searches for a particular type of content is more efficient if peers likely to store that content type are neighbors. We have used a mathematical model based on modular arithmetic, specifically residue class (RC), to design a two-level structured architecture. To the best of my knowledge, there does not exist any such work that has used this mathematical model.

[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.

Embedded systems are so ubiquitous that they account for almost 90% of all the computing devices. They range from very small scale devices with an 8-bit microcontroller and few kilobytes of RAM to large-scale devices featuring PC-like performance with full-blown 32-bit or 64-bit processors, special-purpose acceleration hardware and several gigabytes of RAM. Each of these classes of embedded systems have unique set of challenges in terms of hardware utilization, performance and power consumption. As network connectivity becomes a standard feature in these devices, security becomes an important concern. Public Key Cryptography is an indispensable tool to implement various security features necessary on these embedded platforms. In this thesis, we provide optimized PKC solutions on platforms belonging to two extreme classes of the embedded system spectrum. First, we target high-end embedded platforms Qualcomm Snapdragon and Intel Atom. Each of these platforms features a dual-core processor, a GPU and a gigabyte of RAM. We use the SIMD coprocessor built into these processors to accelerate the modular arithmetic which accounts for the majority of execution time in Elliptic Curve Cryptography. We exploit the structure of NIST primes to perform the reduction step as we perform the multiplication. Our implementation runs over two times faster than OpenSSL implementations on the respective platforms. The second platform we targeted is an energy-harvested wireless sensor node which has a 16-bit MSP430 microcontroller and a low power RF interface. The system derives its power from a solar panel and is constrained in terms of available energy and computational power. We analyze the computation and communication energy requirements for different signature schemes, each with a different trade-off between computation and communication. We investigate the Elliptic Curve Digital Signature Algorithm (ECDSA), the Lamport-Diffie one-time hash-based signature scheme (LD-OTS) and the Winternitz one-time hash-based signature scheme (W-OTS). We demonstrate that there’s a trade-off between energy needs, security level and algorithm selection. However, when we consider the energy needs for the overall system, we show that all schemes are within one order of magnitude from each another. / Master of Science

Estudamos a criptografia RSA como uma importante aplicação dos números primos e da aritmética modular. Apresentamos algumas sugestões de atividades relacionadas ao tema a serem desenvolvidas em sala de aula nas séries finais do ensino fundamental / We studied RSA cryptography as an important application to prime numbers and modular arithmetic. We present some suggestions of activities related to the subject to be developed in classrooms of the final years of elementary school vii