Cryptanalysis of Number Theoretic Ciphers

Samuel S. Wagstaff, Jr.

• Publisher: Chapman and Hall/CRC
• Year: 2019
• ISBN:
  9781351991940
• Edition: 1
• Topic: Matematica
• Subtopic: Conteggio e numerazione

At the heart of modern cryptographic algorithms lies computational number theory. Whether you're encrypting or decrypting ciphers, a solid background in number theory is essential for success. Written by a number theorist and practicing cryptographer, Cryptanalysis of Number Theoretic Ciphers takes you from basic number theory to the inner workings of ciphers and protocols.First, the book provides the mathematical background needed in cryptography as well as definitions and simple examples from cryptography. It includes summaries of elementary number theory and group theory, as well as common methods of finding or constructing large random primes, factoring large integers, and computing discrete logarithms. Next, it describes a selection of cryptographic algorithms, most of which use number theory. Finally, the book presents methods of attack on the cryptographic algorithms and assesses their effectiveness. For each attack method the author lists the systems it applies to and tells how they may be broken with it.Computational number theorists are some of the most successful cryptanalysts against public key systems. Cryptanalysis of Number Theoretic Ciphers builds a solid foundation in number theory and shows you how to apply it not only when breaking ciphers, but also when designing ones that are difficult to break.

Part I

Mathematical Foundations of Cryptanalysis

Chapter 1

Terminology of Cryptography

This chapter introduces the basic facts of cryptography. Refer to Denning [36] for more basic information on cryptography.

1.1 Notation

Cryptography is the study of secret writing. A cipher is a way of hiding ordinary text, called plaintext, by transforming it into ciphertext. This process is called enciphering or encryption of the plaintext into ciphertext. The reverse process is called deciphering or decryption. The following figure illustrates this terminology.

Ciphers are divided into two categories: substitution and transposition ciphers. Substitution ciphers replace letters or larger blocks with substitutes, usually of the same length. In a simple substitution cipher, the same alphabet is used for plaintext and ciphertext, and a fixed permutation of this alphabet gives the substitution rule. As an example, suppose the letters of the alphabet are arranged in a circle (with A following Z) and a message is encrypted by replacing each plaintext letter by the fifth letter after it in the circle. Thus, the message “SECRET” would be enciphered as “XJHWJY.” Decryption is performed by replacing each ciphertext letter by the fifth letter before it in the alphabet circle. This type of cipher, in which the alphabet is rotated, is called a Caesar cipher because Julius Caesar used it.

The letters in the ciphertext of a transposition cipher are the same letters, with the same frequencies, as the letters in the plaintext, but they are rearranged. A simple example of a transposition cipher uses a matrix. The plaintext and ciphertext are broken into blocks with length equal to the number of entries in the matrix. A message is enciphered by writing each block of plaintext into the matrix by rows and reading a ciphertext block out of the matrix by columns backwards. For example, suppose we use a 2 × 3 matrix to encipher the message “SECRET,” which has only one block. We form the matrix

SECRET

and read the ciphertext “CTEESR.” Decryption is performed by writing each ciphertext block into the matrix by columns backwards and reading the plaintext block by rows.

Product ciphers are created by the composition of several ciphers whose types alternate between substitution and transposition. Substitution and transposition ciphers each have certain weaknesses which may be overcome by composing them in this alternating fashion. To give a simple example, compose the two ciphers above, using the Caesar cipher first. The plaintext “SECRET” is first changed into “XJHWJY.” This is written into the matrix

XJHWJY

and the ciphertext is “HYJJXW.” The Data Encryption Standard, DES, and Rijndael are two well known examples of product ciphers.

Both encryption and decryption are controlled by keys. The key for a transposition cipher is the fixed permutation of the letters in a block. The key for a simple substitution cipher is the fixed permutation of the alphabet. In the simple case of the Caesar cipher, the key is the amount of shift of the alphabet.

1.2 Types of Attacks

Suppose E and D are the prototype encryption and decryption methods before the key is...