Jean-Guillaume Dumas - Foundations of Coding Compression, Encryption, Error Correction

Copyright 2015 by John Wiley & Sons, Inc. All rights reserved

Published by John Wiley & Sons, Inc., Hoboken, New Jersey

Published simultaneously in Canada

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 750-4470, or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permissions.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Dumas, Jean-Guillaume.

Foundations of coding : compression, encryption, errorcorrection / Jean-Guillaume Dumas, Jean-Louis Roch, Eric Tannier, Sebastien Varrette.

pages cm

Includes bibliographical references and index.

ISBN 978-1-118-88144-6 (cloth)

1. Coding theory. I. Roch, Jean-Louis (Mathematician) II. Tannier, Eric. III. Varrette, Sebastien. IV. Title.

TK5102.92.D86 2015

003.54dc23

2014039504

List of Figures

List of Tables

List of Algorithms

1.1 Simplified Fax Encoding for a Line of Pixels

1.2 Fax Decoding for a Decrypted and Checked Line

1.3 GCD: Euclidean Algorithm

1.4 GCD: Extended Euclidean Algorithm

1.5 Modular Exponentiation

1.6 Miller--Rabin Primality Test

1.7 Horner Polynomial Evaluation

1.8 Ben-Or's Irreducibility Test

1.9 Generation of a sparse irreducible polynomial

1.10 Test Primitive Root

1.11 Test Generator Polynomial

1.12 Discrete Fast Fourier Transform

1.13 Fast product of two polynomials

1.14 Berlekamp--Massey Algorithm

1.15 Yuval's birthday attack

1.16 Pollard's Factoring

1.17 Lenstra's elliptic curve factoring

1.18 Gordon's algorithm

2.1 Description of Huffman's Algorithm

2.2 Arithmetic Encoding

2.3 Arithmetic Decoding

2.4 Dynamic Huffman Algorithm: Compression

2.5 Dynamic Huffman's Algorithm Decompression

2.6 Inverse of BWT

2.7 LZW: compression

2.8 LZW: decompression

3.1 AES Encryption

3.2 Key Schedule in AES

3.3 GCM

3.4 Shamir's Trick for Simultaneous Double-And-Add

4.1 Hard-Decision Decoder by Bit-Flipping Algorithm

4.2 Generic BPA for LDPC Code Decoding

4.3 Decoding of a Reed-Solomon code

4.4 Viterbi's Algorithm (Decoding of Convolutional Codes)

1 AES Decryption

2 Factoring n from (n,e,d) in RSA (Special Case: e is Small)

3 Factoring n from (n,e,d) in RSA

4 RSA Cryptographic Pseudo-Random Generator

5 Repetition Code Decoding with Maximum Detection

6 Repetition Code Decoding with Maximum Correction

7 Repetition Code Decoding with Detection and Correction

8 Minimum Distance of a Code (|V|=2)

acronym

ADSL Asymmetric Digital Subscriber Line

AES Advanced Encryption Standard

AKS Agrawal--Kayal--Saxena

APP A posteriori probability

ARQ Automatic Repeat reQuest

BBAN Basic Bank Account Number

BCH Bose--Chaudhuri--Hocquenghem

BEC Binary Erasure Channel

BI-AWGNC Binary-input Additive White Gaussian Noise Channel

BPA Belief Propagation Algorithm

BSC Binary Symmetric Channel

BWT Burrows--Wheeler Transform

CA Certification Authority

CAIN Confidentiality, Authentication, Integrity, Nonrepudiation

CBC Cipher Block Chaining

CFB Cipher FeedBack

CIRC Cross-Interleaved Reed--Solomon Code

CML Coded Modulation Library

CRC Cyclic Redundancy Checks

CRL Certification Revocation List

CSS Content Scrambling System

CTR Counter Mode Encryption

CVV Card Verification Value

DCT Discrete Cosine Transform

DDF Distinct Degree Factorization

DES Data Encryption Standard

DFT Discrete Fourier Transform

DLP Discrete Logarithm Problem

DRM Digital Right Management

DSS Digital Signature Standard

DVB Digital Video Broadcasting

ECB Electronic Code Book

ECC Elliptic Curve Cryptography

ECDSA Elliptic Curve Digital Signature Algorithm

GCD Greatest Common Divisor

GCM Galois Counter Mode

GIF Graphics Interchange Format

GSM Global System for Mobile Communications

HDD Hard Disk Drives

JPEG Joint Photographic Experts Group

JPSEC Secure JPEG-2000

KDC Key Distribution Center

LCG Linear Congruential Generator

LDPC Low Density Parity Check

LFSR Linear Feedback Shift Register

LLR log-Likelihood Ratio

LR Likelihood Ratio

LZ77 Lempel-Ziv 1977

LZ78 Lempel-Ziv 1978

LZAP Lempel-Ziv All Prefixes

LZMA Lempel--Ziv--Markov-chain Algorithm

LZMW Lempel-Ziv-Miller-Wegman

LZO Lempel-Ziv-Oberhumer

LZW Lempel-Ziv-Welch

MAC Message Authentication Code

MD5 Message-Digest Algorithm 5

MDC Manipulation Detection Code

MDD Minimum Distance Decoding

MDS Maximum Distance Separable

MGF Mask Generating Function

MLD Maximum Likelihood Decoding

MPA Message Passing Algorithm

MPEG Motion Picture Experts Group

NESSIE New European Schemes for Signatures, Integrity, and Encryption

NIST National Institute of Standards and Technology

NSC Nonsystematic Convolutional code

OAEP Optimal Asymmetric Encryption Padding

OFB Output FeedBack

PGP Pretty Good Privacy

PKI Public Key Infrastructure

PKIX Public Key Infrastructure for X.509 certificates

PNG Portable Network Graphics

PRNG Pseudo-Random Number Generators

QR-code Quick Response code

RA Registration Authority

RAID Redundant Array of Independent Disks

RLE Run-Length Encoding

RSA Rivest--Shamir--Adleman

RSC Recursive Systematic Convolutional codes

RGB Red/Green/Blue

SDSI Simple Distributed Security Infrastructure