UNIT 2 :- MODULAR ARITHEMETIC AND CRYPTOGRAPHY BASICS

CRYPTOGRAPHY
Classical encryption techniques

There are two basic building blocks of all encryption techniques: substitution and transposition.

1. SUBSTITUTION TECHNIQUES
A substitution technique is one in which the letters of plaintext are replaced by other letters
or by numbers or symbols. If the plaintext is viewed as a sequence of bits, then substitution
involves replacing plaintext bit patterns with cipher text bit patterns.

● Caesar cipher (or) shift cipher

The earliest known use of a substitution cipher and the simplest was by Julius Caesar. The Caesar
cipher involves replacing each letter of the alphabet with the letter standing 3 places further down
the alphabet.

e.g., Plain text : pay more mone Cipher text: SDB PRUH PRQHB

● Playfair cipher

The best known multiple letter encryption cipher is the playfair, which treats digrams in the plaintext
as single units and translates these units into cipher text digrams. The playfair algorithm is based on
the use of 5x5 matrix of letters constructed using a keyword. Let the keyword be „monarchy‟. The
matrix is constructed by filling in the letters of the keyword (minus duplicates) from left to right and
from top to bottom, and then filling in the remainder of the matrix with the remaining letters in
alphabetical order.

● The letter „i‟ and „j‟ count as one letter. Plaintext is encrypted two letters at a time according to
the following rules:
● Repeating plaintext letters that would fall in the same pair are separated with a filler letter such
as „x‟.
● Plaintext letters that fall in the same row of the matrix are each replaced by the letter to the
right, with the first element of the row following the last.
● Plaintext letters that fall in the same column are replaced by the letter beneath, with the top
element of the column following the last.
● Otherwise, each plaintext letter is replaced by the letter that lies in its own row and the column
occupied by the other plaintext letter.

Plaintext = meet me at the school house

Splitting two letters as a unit => me et me at th es ch ox ol ho us ex Corresponding cipher text => CL

KL CL RS PD IL HY AV MP HF XL IU
 ● Polyalphabetic ciphers

Another way to improve on the simple monoalphabetic technique is to use different monoalphabetic
substitutions as one proceeds through the plaintext message. The general name for this approach is
polyalphabetic cipher. All the techniques have the following features in common.

A set of related monoalphabetic substitution rules are used

A key determines which particular rule is chosen for a given transformation.

● Vigenere cipher

In this scheme, the set of related monoalphabetic substitution rules consisting of 26 caesar ciphers
with shifts of 0 through 25. Each cipher is denoted by a key letter. e.g.,

Caesar cipher with a shift of 3 is denoted by the key value 'd‟ (since a=0, b=1, c=2 and so on). To aid
in understanding the scheme, a matrix known as vigenere tableau is constructed.

Each of the 26 ciphers is laid out horizontally, with the key letter for each cipher to its left. A normal
alphabet for the plaintext runs across the top. The process of encryption is simple: Given a key letter
X and a plaintext letter y, the cipher text is at the intersection of the row labeled x and the column
labeled y; in this case, the ciphertext is V.

To encrypt a message, a key is needed that is as long as the message. Usually, the key is a repeating
keyword.

e.g., key = d e c e p t i v e d e c e p t i v e d e c e p t i v e

PT =wearediscoveredsaveyourself

CT = ZICVTWQNGRZGVTWAVZHCQYGLMGJ

● One Time Pad Cipher

It is an unbreakable cryptosystem. It represents the message as a sequence of 0s and 1s. this can be
accomplished by writing all numbers in binary, for example, or by using ASCII. The key is a random
sequence of 0‟s and 1‟s of same length as the message. Once a key is used, it is discarded and never
used again.

The system can be expressed as follows:

Thus the cipher text is generated by performing the bitwise XOR of the plaintext and the key.
Decryption uses the same key. Because of the properties of XOR, decryption simply involves the
same bitwise operation:
TRANSPOSITION TECHNIQUES

All the techniques examined so far involve the substitution of a cipher text symbol for a plaintext
symbol. A very different kind of mapping is achieved by performing some sort of permutation on the
plaintext letters. This technique is referred to as a transposition cipher.

Rail fence is simplest of such cipher, in which the plaintext is written down as a sequence of
diagonals and then read off as a sequence of rows.

Plaintext = meet at the school house

To encipher this message with a rail fence of depth 2, we write the message as follows:

m e a t e c o l o s

e t t h s H o h ue

The encrypted message is

MEATECOLOSETTHSHOHUE

Row Transposition Ciphers

A more complex scheme is to write the message in a rectangle, row by row, and read the message
off, column by column, but permute the order of the columns. The order of columns then becomes
the key of the algorithm.

e.g., plaintext = meet at the school house

CT = ESOTCUEEHMHLAHSTOETO

A pure transposition cipher is easily recognized because it has the same letter frequencies as the
original plaintext. The transposition cipher can be made significantly more secure by performing
more than one stage of transposition. The result is more complex permutation that is not easily
reconstructed.
Block Cipher

A block cipher encrypts data in fixed-size blocks usually 64 or 128 bits at a time. The encryption
algorithm processes each block of data separately using the cryptographic key to transform the
plaintext into the ciphertext. Block ciphers function on complex mathematical computation and
permutation to ensure that the data encrypted is safe. The choice of block size does not directly
affect the strength of the encryption scheme.

The strength of the cipher depends upon the key length. However, any size of the block is acceptable.
The following aspects can be kept in mind while selecting the size of a block: Avoid very small block
sizes, Do not have very large block sizes, and Multiples of 8-bit.

Key Features of Block Ciphers

● Fixed Block Size: The Data is encrypted in a fixed-size block.

● Complex Operations: In block ciphers, substitution combined with permutation forms
the operation to achieve encryption.
● Modes of Operation: Block ciphers employ several modes such as ECB (Electronic
Codebook) and CBC (Cipher Block Chaining) for enhanced security.
● Examples: AES (Advanced Encryption Standard), DES (Data Encryption Standard) and
Blowfish.

Stream Cipher

A stream cipher encrypts data one bit or one byte at a time rather than in fixed-size blocks. It
generates a keystream that is combined with the plaintext to the produce ciphertext. Stream ciphers
are made for the scenarios where data needs to be encrypted in the continuous stream making them
suitable for the real-time applications.
It can be categorized into the synchronous, self-synchronizing and one-time pad types. The
Synchronous encryption requires independently generated keystream from both the plaintext and
the ciphertext. They have to be in the same state, with the same key, in order to decode the data
properly.

Key Features of Stream Ciphers

● Continuous Encryption: The data is encrypted in a stream that runs continuously, a bit or
byte at a time
● Keystream Generation: To create encryption keys, the Stream ciphers use a
pseudorandom keystream generator.
● Efficiency: Stream ciphers are generally more efficient for encrypting data of variable
length and in the streaming applications.
● Examples: RC4, Salsa20, and ChaCha20.

Data Encryption Standard

The Data Encryption Standard (DES) is a symmetric-key block cipher published by the National
Institute of Standards and Technology (NIST).

DES is an implementation of a Feistel Cipher. It uses 16 round Feistel structure. The block size is
64-bit. Though, key length is 64-bit, DES has an effective key length of 56 bits, since 8 of the 64 bits of
the key are not used by the encryption algorithm (function as check bits only). General Structure of
DES is depicted in the following illustration -
Since DES is based on the Feistel Cipher, all that is required to specify DES is −

● Round function
● Key schedule
● Any additional processing − Initial and final permutation

Initial and Final Permutation

The initial and final permutations are straight Permutation boxes (P-boxes) that are inverses of each
other. They have no cryptography significance in DES.

Round Function

The heart of this cipher is the DES function, f. The DES function applies a 48-bit key to the rightmost
32 bits to produce a 32-bit output.
Expansion Permutation Box − Since right input is 32-bit and round key is a 48-bit, we first need to
expand right input to 48 bits. Permutation logic is graphically depicted in the following illustration −

The graphically depicted permutation logic is generally described as table in DES specification

XOR (Whitener). − After the expansion permutation, DES does XOR operation on the expanded right
section and the round key. The round key is used only in this operation.

Substitution Boxes. − The S-boxes carry out the real mixing (confusion). DES uses 8 S-boxes, each
with a 6-bit input and a 4-bit output. Refer the following illustration –

The S-box rule is illustrated below –

There are a total of eight S-box tables. The output of all eight s-boxes is then combined in to 32 bit
section.

Key Generation

The round-key generator creates sixteen 48-bit keys out of a 56-bit cipher key. The process of key
generation is depicted in the following illustration −

The logic for Parity drop, shifting, and Compression P-box is given in the DES description.

DES Analysis
The DES satisfies both the desired properties of block cipher. These two properties make cipher very
strong.

● Avalanche effect − A small change in plaintext results in the very great change in the
ciphertext.
● Completeness − Each bit of ciphertext depends on many bits of plaintext.

During the last few years, cryptanalysis have found some weaknesses in DES when key selected are
weak keys. These keys shall be avoided.

DES has proved to be a very well designed block cipher. There have been no significant cryptanalytic
attacks on DES other than exhaustive key search.

Advanced Encryption Standard

The more popular and widely adopted symmetric encryption algorithm likely to be encountered
nowadays is the Advanced Encryption Standard (AES). It is found at least six time faster than triple
DES.

A replacement for DES was needed as its key size was too small. With increasing computing power, it
was considered vulnerable against exhaustive key search attack. Triple DES was designed to
overcome this drawback but it was found slow.

The features of AES are as follows −

● Symmetric key symmetric block cipher

● 128-bit data, 128/192/256-bit keys
● Stronger and faster than Triple-DES
● Provide full specification and design details
● Software implementable in C and Java

Operation of AES

AES is an iterative rather than Feistel cipher. It is based on ‘substitution–permutation network’. It

comprises of a series of linked operations, some of which involve replacing inputs by specific outputs
(substitutions) and others involve shuffling bits around (permutations).

Interestingly, AES performs all its computations on bytes rather than bits. Hence, AES treats the 128
bits of a plaintext block as 16 bytes. These 16 bytes are arranged in four columns and four rows for
processing as a matrix −

Unlike DES, the number of rounds in AES is variable and depends on the length of the key. AES uses
10 rounds for 128-bit keys, 12 rounds for 192-bit keys and 14 rounds for 256-bit keys. Each of these
rounds uses a different 128-bit round key, which is calculated from the original AES key.

The schematic of AES structure is given in the following illustration –

Encryption Process

Here, we restrict to description of a typical round of AES encryption. Each round comprise of four
sub-processes. The first round process is depicted below –

Byte Substitution (SubBytes)

The 16 input bytes are substituted by looking up a fixed table (S-box) given in design. The result is in
a matrix of four rows and four columns.

Shiftrows

Each of the four rows of the matrix is shifted to the left. Any entries that ‘fall off’ are re-inserted on
the right side of row. Shift is carried out as follows −

● First row is not shifted.

● Second row is shifted one (byte) position to the left.
● Third row is shifted two positions to the left.
● Fourth row is shifted three positions to the left.
● The result is a new matrix consisting of the same 16 bytes but shifted with respect to each
other.
Mix Columns

Each column of four bytes is now transformed using a special mathematical function. This function
takes as input the four bytes of one column and outputs four completely new bytes, which replace
the original column. The result is another new matrix consisting of 16 new bytes. It should be noted
that this step is not performed in the last round.

Add round key

The 16 bytes of the matrix are now considered as 128 bits and are XORed to the 128 bits of the
round key. If this is the last round then the output is the ciphertext. Otherwise, the resulting 128 bits
are interpreted as 16 bytes and we begin another similar round.

Decryption Process

The process of decryption of an AES ciphertext is similar to the encryption process in the reverse
order. Each round consists of the four processes conducted in the reverse order −

● Add round key

● Mix columns
● Shift rows
● Byte substitution

Since sub-processes in each round are in reverse manner, unlike for a Feistel Cipher, the encryption
and decryption algorithms needs to be separately implemented, although they are very closely
related.

AES Analysis

In present day cryptography, AES is widely adopted and supported in both hardware and software.
Till date, no practical cryptanalytic attacks against AES has been discovered. Additionally, AES has
built-in flexibility of key length, which allows a degree of ‘future-proofing’ against progress in the
ability to perform exhaustive key searches.

However, just as for DES, the AES security is assured only if it is correctly implemented and good key
management is employed.

RC5 ALGORITHM

● In RC-5, the word size (i.e. input plaintext block size), number of rounds and number of keys
are not fixed i.e. all can be of variable length.
● Once w, r, k (word size, number of rounds, number of keys) are finalized then they remain
same for all the rounds.
● Plain text can be 32 bits, 64 bits or 128 bits
● Number of rounds can be between 0-255
● Key size can be between 0 to 255 bytes
Encryption using RC5

Encryption involved several rounds of a simple function. 12 or 20 rounds seem to be recommended,

depending on security needs and time considerations.

We initialize the counter to 1 and perform some permutation and combination using addition and
XOR

The algorithm works into two phases:

a. First it starts with phase one

b. Output of phase one become input of phase two

We divide the plaintext block into two equal parts A and B

Then they are XOR with two subkeys S{0} and S{1}

C=A+S[0]

D=B+S[1]

for i = 1 to r do:

1. C⊕D=E
2. perform circular left shift on E by D bits
3. add E and S[2 * i] and store the result in F which is input for step 4
4. D⊕F=G
5. perform circular left shift on G by F bits
6. add G and S[2 * i + 1] and store the result in H
7. If i< r
Call F as C and H as D and repeat the steps from 1 to 7

else stop

● Once both the phases are completed the counter is incriminated and we check if it is greater
than the number of rounds, if yes then the algorithm terminals and if no then the algorithm
iterates.

Decryption:

Decryption is a straightforward reversal of the encryption process.

MODULAR ARITHMETIC
What is Modular Arithmetic?

In modular arithmetic, numbers are reduced within a certain range, defined by the modulus. For two
integers a and b, and a positive integer n, we say that a is congruent to b modulo n if their difference
is an integer multiple of n. This is denoted as:

a ≡ b (mod n)

Quotient Remainder Theorem

It states that, for any pair of integers a and b (b is positive), there exist two unique integers q and r
such that:

a = b x q + r where 0 <= r < b

Example: If a = 20, b = 6 then q = 3, r = 2 20 = 6 x 3 + 2

Modular Addition

The rule for modular addition is:

(a + b) mod m = ((a mod m) + (b mod m)) mod m

Example

(15 + 17) % 7

= ((15 % 7) + (17 % 7)) % 7

= (1 + 3) % 7

=4%7

=4

The same rule is to modular subtraction. We don’t require much modular subtraction but it can also
be done in the same way.

Modular Multiplication

The Rule for modular multiplication is:

(a x b) mod m = ((a mod m) x (b mod m)) mod m

Example:

(12 x 13) % 5

= ((12 % 5) x (13 % 5)) % 5

= (2 x 3) % 5

=6%5

=1

Modular Division

The modular division is totally different from modular addition, subtraction and multiplication. It also
does not exist always.

(a / b) mod m is not equal to ((a mod m) / (b mod m)) mod m.

This is calculated using the following formula:

(a / b) mod m = (a x (inverse of b if exists)) mod m

Modular Inverse

The modular inverse of a mod m exists only if a and m are relatively prime i.e. gcd(a, m) = 1. Hence,
for finding the inverse of a under modulo m, if (a x b) mod m = 1 then b is the modular inverse of a.

Example: a = 5, m = 7 (5 x 3) % 7 = 1 hence, 3 is modulo inverse of 5 under 7.

Modular Exponentiation

Finding a^b mod m is the modular exponentiation. There are two approaches for this – recursive and
iterative.

Example:

a = 5, b = 2, m = 7

(5 ^ 2) % 7 = 25 % 7 = 4

There is often a need to efficiently calculate the value of xn mod m. This can be done in O(logn) time
using the following recursion:

It is important that in the case of an even n, the value of xn/2 is calculated only once.

This guarantees that the time complexity of the algorithm is O(logn) because n is always halved when
it is even.

The following function calculates the value of xn mod m:

int modpower(int x, int n, int m)

if (n == 0)

return 1%m;

long long u = modpower(x,n/2,m);

 u = (u*u)%m;

if (n%2 == 1)

u = (u*x)%m;

return u;

Euclidean algorithms (Basic and Extended)

The Euclidean algorithm is a way to find the greatest common divisor of two positive integers. GCD of
two numbers is the largest number that divides both of them. A simple way to find GCD is to
factorize both numbers and multiply common prime factors.

Basic Euclidean Algorithm for GCD:

The algorithm is based on the below facts.

If we subtract a smaller number from a larger one (we reduce a larger number), GCD doesn’t change.
So if we keep subtracting repeatedly the larger of two, we end up with GCD.

Now instead of subtraction, if we divide the larger number, the algorithm stops when we find the
remainder 0.

Extended Euclidean Algorithm:

Extended Euclidean algorithm also finds integer coefficients x and y such that: ax + by = gcd(a, b)

Examples:

Input: a = 30, b = 20

Output: gcd = 10, x = 1, y = -1

(Note that 30*1 + 20*(-1) = 10)

Input: a = 35, b = 15

Output: gcd = 5, x = 1, y = -2

(Note that 35*1 + 15*(-2) = 5)

The extended Euclidean algorithm updates the results of gcd(a, b) using the results calculated by the
recursive call gcd(b%a, a). Let values of x and y calculated by the recursive call be x1 and y1. x and y
are updated using the below expressions.

ax + by = gcd(a, b)

gcd(a, b) = gcd(b%a, a)

gcd(b%a, a) = (b%a)x1 + ay1

ax + by = (b%a)x1 + ay1

ax + by = (b – [b/a] * a)x1 + ay1

ax + by = a(y1 – [b/a] * x1) + bx1

Comparing LHS and RHS,

x = y1 – ⌊b/a⌋⌊b/a⌋* x1 y = x1

How is Extended Algorithm Useful?

The extended Euclidean algorithm is particularly useful when a and b are coprime (or gcd is 1). Since
x is the modular multiplicative inverse of “a modulo b”, and y is the modular multiplicative inverse of
“b modulo a”. In particular, the computation of the modular multiplicative inverse is an essential step
in RSA public-key encryption method.