Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2019 | Buch

Secure, Reliable Information Kapitel lesen Erstes Kapitel lesen

Cryptology and Error Correction

An Algebraic Introduction and Real-World Applications

verfasst von: Prof. Lindsay N. Childs

Verlag: Springer International Publishing

Buchreihe : Springer Undergraduate Texts in Mathematics and Technology

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

This text presents a careful introduction to methods of cryptology and error correction in wide use throughout the world and the concepts of abstract algebra and number theory that are essential for understanding these methods. The objective is to provide a thorough understanding of RSA, Diffie–Hellman, and Blum–Goldwasser cryptosystems and Hamming and Reed–Solomon error correction: how they are constructed, how they are made to work efficiently, and also how they can be attacked. To reach that level of understanding requires and motivates many ideas found in a first course in abstract algebra—rings, fields, finite abelian groups, basic theory of numbers, computational number theory, homomorphisms, ideals, and cosets. Those who complete this book will have gained a solid mathematical foundation for more specialized applied courses on cryptology or error correction, and should also be well prepared, both in concepts and in motivation, to pursue more advanced study in algebra and number theory.

This text is suitable for classroom or online use or for independent study. Aimed at students in mathematics, computer science, and engineering, the prerequisite includes one or two years of a standard calculus sequence. Ideally the reader will also take a concurrent course in linear algebra or elementary matrix theory. A solutions manual for the 400 exercises in the book is available to instructors who adopt the text for their course.

Inhaltsverzeichnis

Frontmatter
Chapter 1. Secure, Reliable Information
Abstract
This chapter introduces “clock arithmetic”, or modular arithmetic, using the division theorem and the concept of least non-negative residue. These ideas are used to describe some historic examples of the two main applications of the book. Cryptology, or the study of methods of making information secret except to persons with special knowledge, is illustrated by additive Caesar ciphers, and Vigenere and Vernam (one-time pad) cryptosystems. Coding, or the study of methods to add redundancy to a message to determine if it is compromised by errors, is illustrated by check digits in several settings, and by repetition coding, a special case of which has historically been known as triple modular redundancy.
Lindsay N. Childs
Chapter 2. Modular Arithmetic
Abstract
This chapter introduces and studies modular arithmetic, the clock arithmetic of Chap. 1, and introduces congruence as an alternate way of looking at modular arithmetic. An application to the construction of multiplicative Caesar ciphers motivates the ideas of units and zero divisors modulo m. The final section briefly discusses established ways (ASCII, Unicode) in which text is transformed into numbers, and shows how to transform numbers into sequences of bits (numbers in base 2).
Lindsay N. Childs
Chapter 3. Linear Equations Modulo m
Abstract
This chapter presents some fundamental ideas and methods of arithmetic. These include the greatest common divisor of two numbers, Euclid’s algorithm to find the greatest common divisor, and the Extended Euclidean Algorithm to write the greatest common divisor of two numbers as an integer linear combination of the two numbers (Bezout’s Identity). We show how to solve linear congruences and find all integer solutions of integer linear equations in two variables. A short section is devoted to what we call the “Coprime Divisibility Lemma”: if a number divides the product of two numbers and is coprime to one of them, it divides the other. That result and all of the methods of this chapter are basic tools for studying applications later in the book.
Lindsay N. Childs
Chapter 4. Unique Factorization in
Abstract
This chapter presents the concept of induction, in two equivalent forms: complete induction, and the well-ordering principle. One or the other is used to prove the existence and uniqueness of factorization of any number > 1 into a product of prime numbers (the so-called Fundamental Theorem of Arithmetic), to prove the Division Theorem, and to prove the existence of Bezout’s Identity. Uniqueness of factorization permits an alternative description of when one number divides another. It also provides alternate descriptions of the greatest common divisor and the least common multiple of two numbers.
Lindsay N. Childs
Chapter 5. Rings and Fields
Abstract
This chapter introduces some basic concepts of elementary abstract algebra: groups, rings and commutative rings, fields, ideals, cosets of ideals and quotient rings. The immediate objective is to describe modular arithmetic as addition and multiplication in the ring \(\mathbb {Z}/m\mathbb {Z}\), of cosets of integers modulo the ideal consisting of all multiples of the modulus m. Doing so places modular arithmetic on a firm theoretical foundation. One consequence is to show that if m is a prime number, then doing modular arithmetic modulo p is the same as working in \(\mathbb {Z}/p\mathbb {Z}\), and the latter is a field. So concepts and results involving polynomials (in Chap. 6) and matrices (in Chap. 7) make sense when the “numbers” are integers modulo a prime number p.
Lindsay N. Childs
Chapter 6. Polynomials
Abstract
This chapter introduces elementary ideas involving polynomials with coefficients in a field, including the Degree Formula, the Division Theorem for polynomials, and special cases of the latter, the Remainder Theorem and the Root Theorem. The main objective here is D’Alembert’s Theorem: a polynomial of degree n with coefficients in a field can have no more than n roots in the field. D’Alembert’s Theorem will become highly useful for explaining Reed-Solomon error correction in Chap.15, and for understanding algorithms for factoring large numbers in cryptology. Polynomials will be revisited in Chap. 18.
Lindsay N. Childs
Chapter 7. Matrices and Hamming Codes
Abstract
This chapter introduces two Hamming codes, the first modern examples of error correcting codes. A Hamming code provides a way of transforming pieces (words) of a message so that at a later point, a reader of the message will be able to not just detect an error in a word, but correct the error. In order to understand Hamming codes, the chapter begins by introducing some elementary ideas of matrices and linear algebra: row vectors, column vectors and matrices, operations of addition and scalar multiplication, and matrix multiplication. Chapter 3 introduced vectors in the Extended Euclidean Algorithm to find the coefficients in Bezout’s identity and to find integer solutions of integer linear equations in two variables. The idea there was to work with vectors of coefficients of equations that describe successive remainders in Euclid’s Algorithm for two given numbers a and b as integer linear combinations of the two numbers. Matrices play a similar role in isolating and working efficiently with the coefficients of a system of linear equations in order to find solutions of the system. So they will show up again in Chaps. 15, 17 and 19. The chapter ends with a brief description of Hill cryptography, an historically significant generalization to matrices of the multiplicative Caesar cipher introduced in Chap. 2.
Lindsay N. Childs
Chapter 8. Orders and Euler’s Theorem
Abstract
This chapter concludes the theory needed to describe the cryptography in Chap. 9. The key concept is that of the order of a unit b modulo m, and Euler’s Theorem, which places a constraint on the possible values of the order of b. When m is prime, Euler’s Theorem is the same as Fermat’s Theorem, which is given a proof using the Binomial Theorem. The final section describes an efficient algorithm for computing a high power of a number modulo m. This algorithm will have both an obvious use in using the cryptosystems presented in Chaps. 9 and 13 and a less obvious use to help construct cryptosystems in the last section of Chap. 9.
Lindsay N. Childs
Chapter 9. RSA Cryptography and Prime Numbers
Abstract
This chapter presents the RSA cryptosystem, a much-heralded cryptosystem used worldwide. Large prime numbers are needed to construct an RSA cryptosystem, so the second half of the chapter is devoted to seeing how many large primes there are, and how to identify large primes with high confidence.
Lindsay N. Childs
Chapter 10. Groups, Cosets and Lagrange’s Theorem
Abstract
For the cryptosystems to be introduced in Chaps. 13 and 16 and for further study of RSA, we present some fundamental ideas in finite group theory, namely the concepts of a subgroup of a finite group and a coset of a subgroup, and Lagrange’s Theorem, a counting theorem involving a finite group, a subgroup and the cosets of that subgroup. Lagrange’s Theorem immediately implies Euler’s Theorem, a key result for the RSA cryptosystem. All of the groups used in this book are abelian, but for completeness, a concluding section introduces a non-abelian group with six elements to hint at the vast amount of group theory that is not discussed in this book.
Lindsay N. Childs
Chapter 11. Solving Systems of Congruences
Abstract
This chapter extends Chap. 3 by giving a complete description of the solutions of systems of two or more simultaneous linear congruences. One solution method, for pairwise coprime moduli, uses Bezout’s Identity and yields the Chinese Remainder Theorem. An immediate application of this case is to speed up the decryption of messages in an RSA cryptosystem. For the general case of systems of congruences to non-coprime moduli, we show how to decide if solutions exist, and if so, how to find all of the solutions.
Lindsay N. Childs
Chapter 12. Homomorphisms and Euler’s Phi Function
Abstract
This chapter introduces some more ideas of abstract algebra: ring homomorphisms, group homomorphisms, the Fundamental Homomorphism Theorem, the direct product of rings or of groups. These concepts provide a suitable setting for proofs of the Chinese Remainder Theorem and for the formula satisfied by Euler’s phi function, which counts the number of units of the ring \(\mathbb {Z}_{m}\) in terms of the factorization of m. Ideas in this chapter will also be used in some of the analyses in Chaps. 14 and 16.
Lindsay N. Childs
Chapter 13. Cyclic Groups and Cryptography
Abstract
This chapter presents another public-key cryptographic method used world-wide, the Diffie-Hellman key exchange. Section 8.​5 introduced an efficient algorithm for finding \(h = g^{m}\) where g is an element of a finite group, for example when the group is the group of units modulo a prime p and m is a large exponent. The reverse problem, given g and h, find m, is called the discrete logarithm problem, and is a hard problem. The security of Diffie-Hellman key exchange and the closely related ElGamal cryptosystem is based on that fact. Needed for Diffie-Hellman are cyclic groups of large order. We find many such groups by proving the Primitive Root Theorem, which states that for every prime number p, the group of units of \(\mathbb {Z}_{p}\) is a cyclic group. The chapter concludes with two methods that can be more efficient than constructing log tables for solving the discrete logarithm problem; one method involves use of the Chinese Remainder Theorem.
Lindsay N. Childs
Chapter 14. Applications of Cosets
Abstract
The idea of cosets is often thought of as a difficult concept in elementary abstract algebra. To help increase the comfort with cosets and the counting argument in the proof of Lagrange’s Theorem found in Chap. 10, this chapter gives have different applications of cosets to ideas from earlier chapters of the book. We give a proof of part of what is called the “Fundamental Theorem of Linear Algebra”, for vector spaces over the field of p elements \(\mathbb {Z}_{p}\). We look at Hamming codes and Euler’s Theorem from the point of view of cosets. The last two sections use cosets to look again at the strong pseudoprime test for finding large primes, and to obtain a result of Boneh that cracking an RSA cryptosystem by finding some decrypting exponent is essentially equivalent in difficulty to factoring the RSA modulus.
Lindsay N. Childs
Chapter 15. An Introduction to Reed–Solomon Codes
Abstract
Reed-Solomon codes were the first widely used codes that can correct multiple errors in transmitted information words. They remain useful in many contexts because they can correct bursts of errors to adjacent bits. They do this by turning words made up of bits into sequences of elements of a finite field with q elements where q is large, and working in that finite field. By contrast, Hamming codes work directly with individual bits and are defined over the field of 2 elements. This chapter introduces coding and decoding in a Reed-Solomon code, using Reed and Solomon’s original encoding procedure and the Welch-Berlekamp decoding procedure. The latter reduces to finding solutions of a system of n linear equations in \(n + 1\) unknowns. The theoretical discussion of why decoding works relies on D’Alembert’s Theorem from Chap. 6, and the decoding method requires some elementary knowledge of matrices and solving systems of linear equations, not all of which is found in Sect. 7.​1.
Lindsay N. Childs
Chapter 16. Blum-Goldwasser Cryptography
Abstract
Blum-Goldwasser cryptography is a modern incarnation of a Vernam cryptosystem (see Chap. 1) that solves the problem in the Vernam system that sender and receiver need to share a long sequence of random numbers in order to encrypt and decrypt. Encrypting and decrypting of a message is done by using a secret shared “pseudo-random” sequence k of bits. The sequence is obtained by successive squaring a secret starting number b modulo a large public modulus m that is the product of two secret primes p and q. This chapter describes how to choose p and q so that the period of the sequence k is large, what the sender sends to the receiver (who is the only person who knows the prime factors of m) to enable the receiver to reconstruct the sequence k, how the receiver can obtain the sequence efficiently using the Chinese Remainder Theorem, and, most crucially, why it is essentially necessary for a third party to factor the modulus m in order to crack the cryptosystem.
Lindsay N. Childs
Chapter 17. Factoring by the Quadratic Sieve
Abstract
The RSA and the Blum-Goldwasser cryptosystems both depend on their security on the difficulty of factoring a large modulus m into a product of primes. The Diffie-Hellman key exchange, using the cyclic group of units modulo a large prime, depends for its security on the difficulty of solving the discrete logarithm problem. This chapter first looks at Fermat’s method of factoring a modulus m: find a number b so that \(b^{2} - m = a^{2}\), a square, then the greatest common divisor of m and \(b - a\) is often a factor of m. Fermat’s original approach is a crude method to find such b. The Quadratic Sieve method is a clever adaptation of Fermat’s method for finding b and a that ultimately involves solving a system of equations over the field of two elements. Similar in approach is the Index Calculus method, a clever adaptation of the Baby Step-Giant Step algorithm of Sect. 13.​10 for finding discrete logarithms in the group of units modulo a large prime. These methods are examined in sects. 4 and 5. Both methods described in this chapter are models for methods currently used in practice to try to crack those cryptosystems. An appendix compares the speed of Fermat’s original method of factoring with the grade school method of factoring by trial division.
Lindsay N. Childs
Chapter 18. Polynomials and Finite Fields
Abstract
This chapter shows how to construct all fields with a finite number of elements: they all have \(p^{n}\) elements where p can be any prime number and n can be any number \(\ge 1\). For the construction we begin with the information on polynomials with coefficients in a field found in Chap. 6 and adapt to polynomials the results on unique factorization, ideals and cosets, and quotient rings obtained for \(\mathbb {Z}\) in Chaps. 3-5. The outcome is that if m(x) is an irreducible polynomial in F[x], F a field, then the ring of cosets modulo the principal ideal generated by m(x) is also a field. Every finite field can be described in that way. The method also yields the complex numbers, when the field F is the field of real numbers and \(m(x) = x^{2} +1\). So complex numbers are cosets. They aren’t “imaginary” at all.
Lindsay N. Childs
Chapter 19. Reed-Solomon Codes II
Abstract
This chapter begins by defining the discrete Fourier transform, a square matrix \(\mathcal {F}\) whose entries are roots of unity of some field, and whose inverse is easy to write down and has almost the same form as \(\mathcal {F}\). We then look at two examples of Reed-Solomon codes, based on fields with 8 and 13 elements, respectively. For each example, encoding is done by evaluating the plaintext word W(x) at a complete set of roots of unity. As a consequence, the computational effort required in decoding to solve the set of equations to recover the original word W(x) can be substantially reduced by first multiplying the matrix of coefficients by the inverse of a discrete Fourier transform.
Lindsay N. Childs
Backmatter
Metadaten
Titel
Cryptology and Error Correction
verfasst von
Prof. Lindsay N. Childs
Copyright-Jahr
2019
Electronic ISBN
978-3-030-15453-0
Print ISBN
978-3-030-15451-6
DOI
https://doi.org/10.1007/978-3-030-15453-0

Premium Partner

    Bildnachweise