Malicious Cryptography: Exposing Cryptovirology

Appendix B

Notation and Other Background Information

This appendix describes most of the material that is needed to follow the ideas presented in this book without covering ideas from cryptography. First, standard notations are described that are used throughout the text as well as well-known definitions from number theory. Some basic facts and algorithms from number theory are also given. The appendix then focuses on a set of computational problems in the field of computational number theory. Most of these computational problems are believed to be intractable and many have only been identified recently. The appendix concludes with a description of the random oracle model.

B.1 Notation Used Throughout the Book

In this section notation as well as some basic definitions are given that are used throughout the book. String notation is given followed by logic operations and logic statements. Standard notation from number theory is then given along with basic definitions. This is followed by set theory notation and notation from probability theory. The section concludes with asymptotic notation.

When a is a bit string, |a| denotes the length of a in bits. For example, |01001| = 5. The operator || denotes string concatenation. So, if a and b are bit strings then a||b denotes the bit string that results from concatenating a with b. For example, 010||11 = 01011. When x is a positive integer it is understood that |x| denotes the length of x in bits when x is represented in base 2. The set ...