Cryptography is a key technology in electronic security systems. Modern cryptograpic techniques have many uses such as to digitally sign documents for access control to implement electronic money and for copyright protection. Because of these important uses it is necessary that users be able to estimate the efficiency and security of cryptographic techniques. It is not sufficient for them to know only how the techniques work. This book is written for readers who want to learn about mod- ern cryptographic algorithms and their mathematical foundation but who do not have the necessary mathematical background. It is my goal to explain the basic techniques of modern cryptography including the necessary mathematical results from linear algebra algebra number theory and probability theory. I assume only basic mathematical knowledge. The book is based on courses in cryptography that I have been teaching at the Technical University Darmstadt since 1996. I thank all students who attended the courses and who read the manuscript carefully for their interest and support. In particular I would like to thank Harald Baier Gabi Barking Manuel Breuning Sa- fuat Hamdy Birgit Henhapl Michael Jacobson (who also corrected my English) Andreas Kottig Markus Maurer Andreas Meyer Stefan v vi Preface Neis Sachar Paulus Thomas Pfahler Marita Skrobic Edlyn Thske Patrick Theobald and Ralf-Philipp Weinmann. I also thank the staff at Springer-Verlag in particular Martin Peters Agnes Herrmann Claudia Kehl Ina Lindemann and Thrry Kornak for their support in the preparation of this book.