book

A Course in Mathematical Cryptography

Name: A Course in Mathematical Cryptography
ISBN: 9783110386165

by Gilbert Baumslag, Benjamin Fine, Martin Kreuzer, Gerhard Rosenberger

June 2015

Intermediate to advanced

389 pages

11h 12m

English

De Gruyter

Read now

Unlock full access

Cover
Title
Copyright Page
Preface
Table of content
1 Basic Ideas of Cryptography
1.1 Mathematical Cryptography1.2 Cryptography, Cryptanalysis and Cryptosystems1.3 A Very Brief History of Cryptography1.4 Encryption and Number Theory1.5 Public Key Cryptography1.6 Cryptosystems and the Key Space1.7 Cryptographic Protocols1.8 Exercises
2 Symmetric Key Cryptosystems
2.1 Mixed Encryption2.2 Block Ciphers2.3 Stream Ciphers2.4 Feistel Networks, DES and AES2.5 One-Way Functions and Trapdoors2.6 Exercises
3 Cryptanalysis and Complexity
3.1 Cryptanalysis and Cryptanalytic Attacks3.2 Statistical Methods3.3 Cryptographic Security3.3.1 Security Proofs3.4 Perfect Security and the One-Time Pad3.4.1 Vigenere Encryption and Polyalphabetic Ciphers3.4.2 Breaking a Protocol3.5 Complexity of Algorithms3.6 Exercises
4 Cryptographic Protocols
4.1 Cryptographic Protocols4.2 Cryptographic Hash Functions4.3 Authentication Protocols4.4 Digital Signatures4.5 Secret Sharing Schemes4.5.1 The Shamir Secret Sharing Scheme4.5.2 Alternatives for Secret Sharing Protocols4.5.3 Verifying Secret Sharing Protocols (VSS)4.6 Zero-Knowledge Proofs4.7 Exercises
5 Elementary Number Theoretic Techniques
5.1 Cryptography and Number Theory5.2 Modular Arithmetic5.3 Units and the Multiplicative Group Z*5.4 The Field Zp and Finite Fields5.5 Finite Abelian Groups5.6 Cyclic Groups and Primitive Elements5.7 The Chinese Remainder Theorem5.8 Exercises

6 Some Number Theoretic Algorithms
6.1 Algorithms for Public Key Cryptography6.2 Quadratic Residues and Square Roots6.3 Modular Square Roots6.4 Products of Two Primes6.5 The Discrete Log Problem6.5.1 Shank’s Baby Step Giant Step Algorithm (BSGS)6.5.2 Pollard’s p-Algorithm6.5.3 The Index Calculus Method6.6 Primality Testing6.6.1 Sieving Methods6.6.2 Fermat’s Primality Testing6.6.3 Pseudoprimes and Probabilistic Primality Testing
6.6.4 Miller-Rabin Primality Testing
6.6.5 Mersenne Primes and the Lucas-Lehmer Test6.7 Exercises
7 Public Key Cryptography
7.1 Public Key Cryptography7.2 Standard Model for Public Key Encryption7.3 The Diffie-Hellman Key Exchange and Protocol7.4 ElGamal Encryption7.4.1 Generalizations of ElGamal7.5 The RSA Algorithm and Protocol7.5.1 The RSA Cryptosystem7.5.2 RSA as a Block Cipher7.5.3 Practical Implementation of RSA7.5.4 Feasibility of the RSA Algorithm7.5.5 Security of RSA7.5.6 Cryptanalysis of RSA7.6 Rabin Encryption7.6.1 Quadratic residues and Rabin Encryption7.6.2 The Rabin Cryptosystem7.6.3 Security Equivalence of the Rabin Cryptosystem7.7 Session Keys and Mixed Encryption7.8 The RSA Signature Method7.9 Exercises
8 Elliptic Curve Cryptography
8.1 The ElGamal and Elliptic Curve Encryption System8.2 Elliptic Curves8.2.1 Fields and Field Extensions8.2.2 Elliptic Curves8.2.3 Elliptic Curve Groups8.2.4 The Order of an Elliptic Curve Group
8.2.5 Calculating Points in Elliptic Curve Groups
8.3 Elliptic Curve Cryptography8.4 Cryptoanalysis of Elliptic Curve Cryptosystems8.5 The MOV-Algorithm8.6 The Elliptic Curve Digital Signature8.7 Exercises
9 Basic Concepts from Group Theory
9.1 Groups and Group Theory9.2 Cosets and Normal Subgroups9.3 Examples of Groups9.4 Generators and Group Presentations9.5 Free Groups and Group Presentations9.6 Group Presentations9.6.1 The Modular Group
9.7 Presentations of Subgroups
9.8 Group Decision Problems9.9 Group Amalgams9.10 Exercises
10 Group Based Cryptography
10.1 Group Based Methods10.2 The Magnus Method10.2.1 The Wagner-Magyarik Method10.3 Free Group Cryptosystems10.3.1 An Implementation Within the Classical Modular Group10.3.2 A Variation Using the Magnus Representation10.4 Cryptographic Protocols Using Groups10.5 Non-Abelian Digital Signatures10.6 Password Security10.6.1 The Strong Generic Free Group Property10.6.2 Security Analysis of the Group Randomizer Protocols10.6.3 Actual Implementation of a Group Randomizer System Protocol10.7 A Secret Sharing Scheme10.8 Exercises
11 Braid Group Cryptography
11.1 Cryptographic Platforms and Platform Groups11.2 The Ko-Lee and AAG Protocols11.2.1 The Ko-Lee Protocol11.2.2 The Anshel-Anshel-Goldfeld Protocol11.3 Some Other Group Based Cryptosystems11.4 The Shamir Three-Pass11.5 Hard Group Theoretic Properties11.6 Braid Group Cryptography11.7 The Braid Groups11.7.1 The Artin Presentation11.7.2 Normal Forms Within Bn11.7.3 The Pure Braid Group for Bn11.7.4 Linear Representations of Bn11.8 Cryptanalysis of Braid Group Cryptosystems11.8.1 Attacks on the Conjugacy Search Problem11.8.2 Length Based Attacks11.8.3 Representation Theoretic Attacks11.8.4 Braid Group Security Summary11.9 Some Other Braid Group Based Protocols11.10 Exercises
12 Further Applications
12.1 Finitely Presented Groups and Cryptography12.2 Group Theory for Access Control12.3 Public Key Control Groups12.4 Diophantine Control Security groups12.5 The Social Security Control Groups12.6 Further Extensions of Diffie-Hellman and RSA12.7 Exercises
13 Commutative Grobner Basis Methods
13.1 Commutative Grobner Bases13.2 Commutative Grobner Basis Cryptosystems13.3 Algebraic Attacks Using Grobner Bases13.3.1 The Grobner Basis Attack13.3.2 The Integer Programming Attack13.3.3 The SAT Attack13.4 Exercises
14 Non-Commutative Grobner Basis Methods
14.1 Non-Commutative Grobner Bases14.2 Elimination and its Applications
14.3 Grobner Bases of Modules
14.4 Non-Commutative GB Cryptosystems14.5 Exercises
15 Lattice-Based Cryptography
15.1 Lattice-Based Cryptography15.2 General Cryptoprimitives15.3 Lattices and Their Properties15.3.1 The Geometry of Numbers15.4 Hard Lattice Problems15.5 Lattice Reduction and Babai’s Algorithm15.6 Main Lattice Based Cryptosystems15.6.1 Ajtai’s Hash Function and Cryptosystem15.6.2 The Ajtai-Dwork Cryptosystem15.6.3 The GGH Cryptosystem15.6.4 NTRU Cryptosystem15.7 Security Proofs15.8 Exercises
Bibliography
Index

Content preview from A Course in Mathematical Cryptography

14 Non-Commutative Grobner Basis Methods

14.1 Non-Commutative Gröbner Bases

Since we encountered some problems when we tried to use commutative polynomials for constructing secure Gröbner basis cryptosystems, it is natural to examine the possibility to use non-commutative algebraic structures. Given a finite set of letters X = {x₁,…, x_n}, a word in X is an element of the form w = x_t x_t · x_jt with ij ϵ {1,…, n}. Here we denote the empty word by 1 and the set of all words by (X}. It is clear that concatenation makes (X} into a monoid with neutral element 1. We call it the free monoid on X.

Definition 14.1.1. Let K be a field and X = {x₁,…,x_n}. The K-vector space with basis (X} can be made into a K-algebra by extending the multiplication of words ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Publisher Resources

ISBN: 9783110386165

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

A Course in Mathematical Cryptography

by Gilbert Baumslag, Benjamin Fine, Martin Kreuzer, Gerhard Rosenberger

14 Non-Commutative Grobner Basis Methods

14.1 Non-Commutative Gröbner Bases

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.