. 1
( 36 .)



>>

BASICS O F
CONTEMPORARY
C R Y P T O G R A P H Y FOR
IT PRACTITIONERS
Series on Coding Theory and Cryptology

Editors: Harald Niederreiter (National University of Singapore, Singapore) and
San Ling (Nanyang Technological University, Singapore)



Published

Basics of Contemporary Cryptography for IT Practitioners
Vol. 1
B. Ryabko and A. Fionov
Series on CodingTheory and Cryptology -Vol. I




BASICS OF
CONTEMPORARY
CRYPTOGRAPHY FOR
IT PRACTITIONERS

Boris Ryabko
Andrey Fionov
S ibe ria n State U nive r s ity of Te Iec om munic atio ns
and Computer Science, Russia




r pWorld Scientific
- -
N E W JERSEY L O N D O N * SINGAPORE BElJlNG S H A N G H A I * HONG KONG * TAIPEI CHENNAI
* *
Published by
World Scientific Publishing Co. Re. Ltd.
5 Toh Tuck Link, Singapore 596224
USA ofice: 27 Warren Street, Suite 401-402, Hackensack, NJ 07601
UK ofice: 57 Shelton Street, Covent Garden, London WC2H 9HE




British Library Cataloguing-in-Publication Data
A catalogue record for this book is available from the British Library.




BASICS OF CONTEMPORARY CRYPTOGRAPHY FOR IT PRACTITIONERS
-
Series on Coding Theory and Cryptology Vol. 1
Copyright Q 2005 by World Scientific Publishing Co. Re. Ltd.
All rights reserved. This book, or parts thereoi may not be reproduced in any form or by any means,
electronic or mechanical, including photocopying, recording or any information storage and retrieval
system now known or to be invented, without written permissionfrom the Publisher.




For photocopying of material in this volume, please pay a copying fee through the Copyright
Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, USA. In this case permission to
photocopy is not required from the publisher.



ISBN 981-256-405-5




Printed in Singapore by World Scientific Printers ( S ) Pte Ltd
Preface



For centuries, cryptography, as the science of ciphering or covering infor-
mation from unauthorised use, had been employed mainly for protecting
messages communicated between the military or governmental officials.
Therefore, the circle of people employing cryptography was quite restricted
and the very methods of this science secret. However, in the last decades,
when the mankind has entered the information society stage, cryptographic
methods of information protection become widely used, serving, in the first
place, business needs. At that, not only inter-bank payments carried out
over computer networks are meant or, say, electronic exchanges operating
via the Internet, but also numerous transactions in which millions of
dinary” people are involved every day, such as payments by credit cards,
transferring wages onto bank accounts, ordering tickets and buying goods
over the Internet, etc. It is a natural demand that all these transactions, as
well as mobile phone conversations and electronic mail, be secured against
dishonest or just overly inquisitive persons and organisations. Therefore
nowadays many specialists working in the field of information technologies
(IT) are engaged in designing and- exploiting the systems of information
protection. Since many of the methods used thereon are based on the
results of contemporary cryptography, this subject is now studied in the
universities preparing IT specialists.
The present book is to a great extent based on the courses taught by
the authors at several universities in Russia, Germany, and Finland. The
book describes the main techniques and facilities of contemporary cryp-
tography. The topics covered include block ciphers, stream ciphers, public
key encryption, digital signatures, cryptographic protocols, elliptic curve
cryptography, theoretical security, and random numbers. The preference is
given to the methods that become (part of) cryptographic standards.


V
Basics of Contemporary Cryptography f o r IT Practitioners
vi


As the book title suggests, the content of the book is intended to I T
students and graduates. The aim of the authors was to provide a com-
prehensive introductory course of cryptography without resorting to com-
plex mathematical constructions. All themes, even the elliptic curves and
theoretical security, are conveyed so that only require the knowledge of
secondary school mathematics. Some special facts of number and probabil-
ity theories are considered when necessary, usually through examples rather
than by giving strict and complex proofs. On the other hand, all cryptogra-
phy results are proved. Thus the intended audience is very wide stretching
from the IT specialists who wish to become qualified users of cryptographic
algorithms to those who are looking for an elementary course to start a
career of the developer of cryptosystems.
In conveying the matter, we tried to follow A. Einstein™s principle:
“everything should be made as simple as possible, but not simpler”. All
methods are described in sufficient details to enable their computer imple-
mentation. Justification for every method is always given, sometimes with
reference to known results in number theory and other fields. When it is
appropriate, algorithms written in pseudo-code are provided. All methods
are supplied by numerical examples. In fact, for the sake of simplicity, all
public-key algorithms are studied in the “integers modulo n” system. The
higher algebraic terminology (rings, fields, etc.) is not used since it may
be foreign to the majority of the intended readers. Nevertheless, all math-
ematical results (even in case of elliptic curves) are strict and consistent.
The contents of the first 5 chapters can be used as a basis for one-
semester course. The other chapters can be read as specialisation courses.
Our experience shows that successful learning is facilitated by practising ex-
ercises and problems and working in computer laboratories for implement-
ing basic algorithms and systems. Therefore the book contains training
problems supplied by the answers and themes for labs.
We hope that the present book will help the reader not only understand
the main problems and methods of contemporary cryptography but also
estimate the beauty and elegance of its ideas and results.

B. Ryabko
A . Fionov
Contents



Preface V


1. Introduction 1
Problems and Exercises . . . . . . . . . . . . . . . . . . . . . . . 6

2. Public Key Cryptosystems 7
2.1 Prehistory and Main Ideas . . . . . . . . . . . . . . . . . . . 7
2.2 The First Public Key System - Diffie-Hellman Key Agree-
ment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 The Elements of Number Theory . . . . . . . . . . . . . . . 15
2.4 Shamir Cipher . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5 ElGamal Encryption . . . . . . . . . . . . . . . . . . . . . . 24
2.6 RSA Encryption and Trapdoor Functions . . . . . . . . . . 27
Problems and Exercises . . . . . . . . . . . . . . . . . . . . . . . 30
Themes for Labs . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3. Solving Discrete Logarithm Problem 33
3.1 Problem Setting . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 The Baby-step Giant-step Algorithm . . . . . . . . . . . . . 35
3.3 Index Calculus Algorithm . . . . . . . . . . . . . . . . . . . 37
Problems and Exercises . . . . . . . . . . . . . . . . . . . . . . . 42
Themes for Labs . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4 . Digital Signatures 43
.....................
4.1 RSA Digital Signature 43
...................
4.2 ElGamal Digital Signature 46

vii
Basics of Contemporary Cryptography for IT Practitioners
viii


4.3 Digital Signature Standards . . . . . . . . . . . . . . . . . . 49
Problems and Exercises . . . . . . . . . . . . . . . . . . . . . . . 52
Themes for Labs . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

5. Cryptographic Protocols 55
5.1 Mental Poker . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.2 Zero Knowledge Proofs . . . . . . . . . . . . . . . . . . . . . 59
5.2.1 Graph Colouring Problem . . . . . . . . . . . . . . . 60
5.2.2 Hamiltonian Cycle Problem . . . . . . . . . . . . . . 63
5.3 Digital Cash . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.4 Mutual Identification with Key Establishment . . . . . . . . 76
Problems and Exercises . . . . . . . . . . . . . . . . . . . . . . . 81
Themes for Labs . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

6. Elliptic Curve Cryptosystems 83
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1 83
Mathematical Foundations . . . . . . . . . . . . . . . . . . .
6.2 84
Choosing Curve Parameters . . . . . . . . . . . . . . . . . .
6.3 91
Constructing Cryptosystems . . . . . . . . . . . . . . . . . .
6.4 93
6.4.1 Elliptic Curve ElGamal Encryption . . . . . . . . . . 94
6.4.2 Elliptic Curve Digital Signature Algorithm . . . . . . 95
6.5 Efficient Implementation of Operations . . . . . . . . . . . . 95
6.6 Counting Points on Elliptic Curve . . . . . . . . . . . . . . 102
6.7 Using Standard Curves . . . . . . . . . . . . . . . . . . . . . 110
Problems and Exercises . . . . . . . . . . . . . . . . . . . . . . . 112
Themes for Labs . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

7. Theoretical Security of Cryptosystems 115
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.2 Theory of Perfect Secrecy . . . . . . . . . . . . . . . . . . . 116
7.3 Vernam Cipher . . . . . . . . . . . . . . . . . . . . . . . . . 118
7.4 Elements of Information Theory . . . . . . . . . . . . . . . 119
7.5 Unicity Distance for Secret Key Cipher . . . . . . . . . . . . 125
7.6 Ideal Cryptosystems . . . . . . . . . . . . . . . . . . . . . . 130
Problems and Exercises . . . . . . . . . . . . . . . . . . . . . . . 136

8. Modern Secret Key Ciphers 137
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
Contents ix


8.2 Block Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . 140
8.2.1 The GOST 28147-89 Block Cipher . . . . . . . . . . 141
8.2.2 The RC5 and RC6 Ciphers . . . . . . . . . . . . . . 144
8.2.3 The Rijndael (AES) Cipher . . . . . . . . . . . . . . 148
8.3 Main Modes of Operation of Block Ciphers . . . . . . . . . 158
8.3.1 ECB Mode . . . . . . . . . . . . . . . . . . . . . . . 159
8.3.2 CBC Mode . . . . . . . . . . . . . . . . . . . . . . . 159
8.4 Stream Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . 160
8.4.1 The OFB Block Cipher Mode . . . . . . . . . . . . . 162
8.4.2 The CTR Block Cipher Mode . . . . . . . . . . . . . 163
8.4.3 The RC4 Algorithm . . . . . . . . . . . . . . . . . . 163
8.5 Cryptographic Hash Functions . . . . . . . . . . . . . . . . 165

9 . Random Numbers in Cryptography 169
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.1 169
Refining Physical Random Number Generators . . . . . . .
9.2 170
Pseudo-Random Number Generators . . . . . . . . . . . . .
9.3 173
9.4 Statistical Tests for Random and Pseudo-Random Number
Generators . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
9.5 Statistical Attack to Block Ciphers . . . . . . . . . . . . . . 178

Answers to Problems and Exercises 185

Bibliography 189

Author Index 193

Subject Index 195
This page intentionally left blank
Chapter 1

Introduction

. 1
( 36 .)



>>