GEK1505/GEH1036: Chapter 5 – Enciphering

Chapter 5 – Enciphering 1 / 86
Overview

1 Early cryptosystems
Transposition & substitutiton systems
Shift transformation

2 Frequency analysis

3 Vignere Cipher

4 Affine Cryptosystems

5 Greatest common divisor & Euclidean algorithm

6 Public Key Codes: RSA

Chapter 5 – Enciphering 2 / 86
Introduction

What is the difference between Coding Theory and Cryptography?

Coding Theory aims to ensure the accurate and reliable transmission

of information, especially in electronic form.

Cryptography aims to conceal the meaning of messages and prevent

unauthorised access to information.

Chapter 5 – Enciphering 3 / 86
Introduction

Cryptography

Science of concealing the meaning of secret messages

Used since ancient times
First devised (and still used) for military purposes
Earliest methods are mechanical ones.
Modern methods use sophisticated mathematics.
Nowadays also widely used in business, banking and computer security

Chapter 5 – Enciphering 4 / 86
Introduction

Example 5.1 (Polybius Square)

Used in ancient Greece.
Letters of message are written in 5 × 5 squares and transposed in a
prearranged order such as by columns or rows.

Chapter 5 – Enciphering 5 / 86
Introduction

Example 5.2 (Caesar’s Code)

Used by Julius Caesar.
Each letter of the message is replaced by the letter which occupies
three positions after the original letter in the natural sequence of the
latin alphabet

Example: The message ADVANCE becomes

DGYDQFH.

Chapter 5 – Enciphering 6 / 86
Introduction

The earliest ciphers or cryptosystems are essentially of two types:

Transposition system This merely rearranges the position of the

letters or symbols of the original message according to a prearranged
procedure.

Substitution system This replaces each letter or symbol of the

original message by a different letter or symbol according to some rule.

Chapter 5 – Enciphering 7 / 86
Rail Fence

Example 5.3 (“Rail Fence” Transposition)

Arrange the message in a line without spacing between words.

Separate it into two lines of letters: the first consisting of those

letters occupying odd positions, and the second consisting of those
occupying even positions.

Juxtapose these two lines of letters into one single line.

Chapter 5 – Enciphering 8 / 86
Suppose the original message is

MEETATYISHUNSTATION.

Separate it into two lines:

M E A Y S U S A I N

E T T I H N T T O

Juxtapose the two lines to form the concealed message:

MEAYSUSAINETTIHNTTO.

Chapter 5 – Enciphering 9 / 86
We can juxtapose in a different way to form the concealed message:

ETTIHNTTOMEAYSUSAIN.

Chapter 5 – Enciphering 10 / 86
Rail Fence
Generalized Rail Fence Transposition

We can make the transposition more complicated by forming, for example,

three lines instead of just two.

The first line L1 consists of all those letters in positions

1, 4, 7, 10, 13, . . . , 3k + 1, . . .

The second line L2 consists of all those letters in positions

2, 5, 8, 11, 14, . . . , 3k + 2, . . .

The third line L3 consists of all those letters in positions

3, 6, 9, 12, 15, . . . , 3k, . . .
Chapter 5 – Enciphering 11 / 86
Rail Fence

Juxtapose these three lines of letters into one single line of letters. This
can be done is several ways:
L1 L2 L3
or

L2 L1 L3
or

L3 L2 L1
and so on.
This line of letters will be conveyed or transmitted.

Chapter 5 – Enciphering 12 / 86
Shift transformation

Caesar’s code, which shifts each letter of the alphabet forward by three
places, is the earliest documented use of a substitution cipher for military
purposes.

This is mentioned in Suetonius Lives of the Caesars LVI,written in the 2nd

Century A.D.

The letters are arranged in a circle in a clockwise direction and the shifting
is done three places in the clockwise direction.

X → A, Y → B, Z → C , A → D.

Chapter 5 – Enciphering 13 / 86
Shift transformation

The shift transformation is a more general form of Caesars code and

moves each letter cyclically a fixed number (k say) of places forward.

If we denote the letters of the alphabet by integers:

A B C D E F G H I J K L M
0 1 2 3 4 5 6 7 8 9 10 11 12

N O P Q R S T U V W X Y Z
13 14 15 16 17 18 19 20 21 22 23 24 25

Chapter 5 – Enciphering 14 / 86
Shift transformation

Shifting k places forward:

Input: an integer x between 0 and 25 inclusive.

Output: integer y , between 0 and 25, satisfying the congruence

y ≡ x +k (mod 26).

Chapter 5 – Enciphering 15 / 86
Shift transformation

Example 5.4
Apply the shift transformation with k = 15 to the message

MEET AT NOON.

Solution. Ignore spaces. First, convert the letters into numbers:

12 4 4 19 0 19 13 14 14 13.

Chapter 5 – Enciphering 16 / 86
Shift transformation

Apply the formula y ≡ x + 15 (mod 26):

x 12 4 19 0 13 14
x + 15 27 19 34 15 28 29
y 1 19 8 15 2 3

The encrypted message is

1 19 19 8 15 8 2 3 3 2

or in letters
BTTI PI CDDC .

Chapter 5 – Enciphering 17 / 86
Shift transformation

Example 5.5
Suppose a PIN (personal identification number) number is a sequence of 6
digits x1 x2 x3 x4 x5 x6 such that 0 ≤ xi ≤ 9 for 0 ≤ i ≤ 6.

Suppose the PIN has been encrypted as y1 y2 y3 y4 y5 y6 using the rule

yi ≡ xi + k (mod 10).

If the encrypted sequence is 803256 using k = 4, retrieve the original PIN.

Chapter 5 – Enciphering 18 / 86
Shift transformation

Solution. We apply the “inverse” formula x ≡ y − 4 (mod 10).

y 8 0 3 2 5 6
y −4 4 −4 −1 −2 1 2
x 4 6 9 8 1 2

The original PIN is 469812.

Chapter 5 – Enciphering 19 / 86
Frequency analysis

Frequency analysis:

Based on statistical analysis of the occurrences of letters in a given

language.

Search for the original letters based on the frequency of occurrences

of the enciphered letters.

The most commonly occurring letters in the English language are

E T A O I N S H R
12.7% 9.1% 8.2% 7.5% 7.0% 6.7% 6.3% 6.1% 6.0%

Chapter 5 – Enciphering 20 / 86
Frequency analysis

Example 5.6
Suppose the following encrypted message is received:

ZU GIIUSVROYN MXKGZ ZNOTMY CK SAYZ TUZ UTRE GIZ

HAZ GRYU JXKGS.

We suspect that it is encrypted using a shift transformation of the form
y ≡ x + k (mod 26). Use frequency analysis to decipher the message.

Chapter 5 – Enciphering 21 / 86
Frequency analysis

Solution. The most frequently occurring letter in the encrypted message

is Z .

Suppose Z is the encrypted letter of E . Then

25 ≡ 4 + k (mod 26).

Hence, k = 21. Using the “inverse” formula

x ≡ y − 21 ≡ y + 5 (mod 26),

the encrypted message are deciphered as:

EZ GNN · · ·

which is gibberish.

Chapter 5 – Enciphering 22 / 86
Frequency analysis

Next, we try T , i.e. suppose Z is the encrypted letter of T . Then

25 ≡ 19 + k (mod 26).

Hence, k = 6. Using the “inverse” formula x ≡ y − 6 (mod 26), the

encrypted message are deciphered as:

TO ACCOMPLISH GREAT THINGS WE MUST

NOT ACT BUT ALSO DREAM.

It seems we have hit on the right guess.

Chapter 5 – Enciphering 23 / 86
Vignere Cipher

In Shift-transformation, each letter is encrypted uniquely. That is, for

each x, there is a unique encrypted y .

To make deciphering more difficult, it is possible to encrypt a

particular letter using several different letters according to a specified
procedure. This is the idea behind the Vignere Cipher.

Chapter 5 – Enciphering 24 / 86
Vignere Cipher

Vignere Cipher:

Uses a 26 × 26 square (called the Vignere square) and a keyword.

Write the keyword repeatedly in a row above the row of the message
– one letter of the keyword above one letter of the message.

Suppose the letter k of the keyword is above the letter X of the

message. In the Vignere square, locate the letter that is at the
intersection of the row labelled by X and the column labelled by k. If
that letter is Y , then encrypt X as Y .

Chapter 5 – Enciphering 25 / 86
Vignere Cipher
Vignere square:

Chapter 5 – Enciphering 26 / 86
Vignere Cipher

Example 5.7
With the keyword “ostrich”, use the Vignere Cipher to encrypt the message

A BIRD IN THE HAND IS WORTH TWO IN THE BUSH.

Solution. Repeat the keyword “above” the message:

o s t r i c h o s t r i c h o s t
A B I R D I N T H E H A N D I S W
r i c h o s t r i c h o s t r i
O R T H T W O I N T H E B U S H

Chapter 5 – Enciphering 27 / 86
Vignere Cipher

The Ao-entry of the Vignere square is O.

The Bs-entry of the Vignere square is T .

The I t-entry of the Vignere square is B.

The Rr -entry of the Vignere square is I .

..
.
The enciphered message is

OTBILKUHZXYIPKWKPFZVOHOHZVVOSTNJP.

Chapter 5 – Enciphering 28 / 86
Vignere Cipher

Example 5.8
Suppose the keyword for a Vignere Cipher is dog . The encrypted message
is
LOSKITJFE .
Find the original message.

Answer:
I AM . . .

Chapter 5 – Enciphering 29 / 86
Multiplicative inverse modulo n

Definition 5.9 (Multiplicative inverse)

If n is a positive integer greater than 1 and a is any integer, then a is said
to have a (multiplicative) inverse modulo n if there is an integer b such
that
ab ≡ 1 (mod n).

Remark
If ab ≡ 1 (mod n), then a is an inverse of b and b is an inverse of a. i.e.,
they form an inversive pair.

If b is an inverse, then so is b + kn for any integer k.

In particular, if r is the remainder when b is divided by n, then r is also an
inverse.
Chapter 5 – Enciphering 30 / 86
Multiplicative inverse modulo n

Example 5.10
The number 8 is an inverse of 2 modulo 5 since

2×8≡1 (mod 5).

Since the remainder of 8 when divided by 5 is 3, another inverse of 2

is 3.
Thus (2, 3) is an inverse pair modulo 5.

Chapter 5 – Enciphering 31 / 86
Multiplicative inverse modulo n

Remark
When one tries to find an inverse of a modulo n, one needs to check for
values between 1 and n − 1 since the value of the remainder lies in this
range.

Chapter 5 – Enciphering 32 / 86
Multiplicative inverse modulo n

Example 5.11
The number 2 does not have an inverse modulo 6 since

2 × 1, 2 × 2, . . . , 2 × 5

are all 6≡ 1 (mod 6).

Chapter 5 – Enciphering 33 / 86
Multiplicative inverse modulo n

Example 5.12
Find the inverse of 2 modulo 7.

Try 2 × 1, 2 × 2, . . . , 2 × 6. We find that 2 × 4 ≡ 1 (mod 7). Thus an

inverse of 2 modulo 7 is 4.

Remark
When n is small, we can use this method. We’ll learn another method for
large n.

Chapter 5 – Enciphering 34 / 86
Multiplicative inverse modulo n

Example 5.13
Find all inverse pairs modulo 10.

By trial and error, we have the following pairs:

(1, 1), (3, 7), (9, 9)

The numbers 2, 4, 5, 6, 8 do not have an inverse modulo 10.

Chapter 5 – Enciphering 35 / 86
Multiplicative inverse modulo n

Example 5.14
Find all inverse pairs modulo 26.

By trial and error, we have the following pairs:

(1, 1), (3, 9), (5, 21), (7, 15), (11, 19), (17, 23), (25, 25)

The other numbers between 1 and 25 do not have an inverse modulo 26.

Chapter 5 – Enciphering 36 / 86
Affine Cryptosystems

An affine cryptosystem/cipher is a crypto system in which the

enciphering transformation is of the form

y = f (x) ≡ ax + b (mod n)

where
n is the total number of letters and symbols that may be used in the
plaintext. Usually, n = 26.

a and b are integers.

the pais (a, b) is called the key of the affine crypto system.

Chapter 5 – Enciphering 37 / 86
Affine Cryptosystems

Affine Cryptosystems on a 26-letter alphabet

Condition on the choice of the key (a, b) for n = 26:

0 ≤ a, b ≤ 25.
a is odd and a 6= 13.

Remark
The key (1, 0) is admissible but it is useless. Why?

Hence, there are 12 × 26 − 1 = 311 useful affine crypto systems.

The reason for the condition will become obvious later.

Chapter 5 – Enciphering 38 / 86
Affine Cryptosystems

The following example shows why a = 13 is not allowed.

Example 5.15
Choose the key (13, 1). Note that

f (0) ≡ 13(0) + 1 ≡ 1 (mod 26)

f (2) ≡ 13(2) + 1 ≡ 1 (mod 26).

This means that when deciphering 1, the original letter could be 0 or 2.
This ambiguity will make deciphering bothersome and inefficient.

Chapter 5 – Enciphering 39 / 86
Affine Cryptosystems

The following example shows why a = 2 is not allowed.

Example 5.16
Choose the key (2, 1). Note that

f (0) ≡ 2(0) + 1 ≡ 1 (mod 26)

f (13) ≡ 2(13) + 1 ≡ 1 (mod 26).

This means that when deciphering 1, the original letter could be 0 or 13.
This ambiguity will make deciphering bothersome and inefficient.

Chapter 5 – Enciphering 40 / 86
Affine Cryptosystems

Deciphering transformation of an affine cryptosystems on 26

letters:
Suppose the enciphering transformation is given by

y = f (x) ≡ ax + b (mod 26).

Then the deciphering transformation is given by

x = f −1 (y ) ≡ a0 y − a0 b (mod 26)

where a0 is the inverse of a modulo 26.

Chapter 5 – Enciphering 41 / 86
Affine Cryptosystems

Remark
Since a does not have an inverse modulo 26 when a is even or when
a = 13, the condition on a is necessary to enable the deciphering.

Chapter 5 – Enciphering 42 / 86
Affine Cryptosystems

Example 5.17
Using the affine cryptosystem on 26-letter alphabet with key (3, 5), the
encrypted message is
HRMM SVT .
Decipher the encrypted message.

Solution. The inverse of 3 modulo 26 is 9. Thus, the deciphering

transformation is

x = f −1 (y ) ≡ 9y − 45 ≡ 9y + 7 (mod 26).

Chapter 5 – Enciphering 43 / 86
Affine Cryptosystems

letter H R M M S V T
y 7 17 12 12 18 21 19
9y + 7 70 160 115 115 169 196 178
x 18 4 11 11 13 14 22
letter S E L L N O W

The original message is

SELL NOW .

Chapter 5 – Enciphering 44 / 86
Greatest common divisor (GCD)

Definition 5.18
Let a and b be integers, not both zero.

An integer that divides both a and b is a common divisor of a and b.

The Greatest Common Divisor of a and b, denoted by gcd(a, b), is the

largest common divisor of both a and b.

Chapter 5 – Enciphering 45 / 86
Greatest common divisor (GCD)

Example 5.19
The common divisors of 72 and 63 are 1, 2 and 9. Thus gcd(72, 63) = 9.

Chapter 5 – Enciphering 46 / 86
Greatest common divisor (GCD)

Example 5.20
Let n be a positive integer. The common divisors of 0 and n are all the
divisors of n. Thus gcd(0, n) = n.

Example 5.21
Let n be a positive integer. There is only one common divisor of 1 and n,
namely, the number 1. Thus gcd(1, n) = 1.

GCD can be found by using the Euclidean algorithm.

Chapter 5 – Enciphering 47 / 86
Euclidean algorithm

Theorem 5.22
Let a, b, q, r be integers such that a = bq + r . Then

gcd(a, b) = gcd(b, r ).

Chapter 5 – Enciphering 48 / 86
Euclidean algorithm

Proof.
Let d = gcd(a, b), e = gcd(b, r ). (Our aim is to prove that d = e.)

We have a = bq + r and d = gcd(a, b),

∴ d is a common divisor of a, b.

∴ d is a divisor of r .

∴ d is a common divisor of b and r .

∴ d ≤ e.

Similarly, we have e ≤ d. Therefore e = d.

Chapter 5 – Enciphering 49 / 86
Euclidean algorithm
Euclidean Algorithm:

Given two integers n and a, where 0 < a < n, we divide n by a and make a
series of such divisions which eventually terminate with a zero remainder.
The ri ’s are the remainders.

n = a q1 + r1 , (divide n by a)
a = r1 q2 + r2 , (divide a by r1 )
r1 = r2 q3 + r3 , (divide r1 by r2 )
..
.
rj−3 = rj−2 qj−1 + rj−1 , (divide rj−3 by rj−2 )
rj−2 = rj−1 qj + rj , (divide rj−2 by rj−1 )
rj−1 = rj qj+1 + 0. (STOP)

Chapter 5 – Enciphering 50 / 86
Euclidean algorithm & GCD

Note that

gcd(n, a) = gcd(a, r1 )
gcd(a, r1 ) = gcd(r1 , r2 )
gcd(r1 , r2 ) = gcd(r2 , r3 )
..
.
gcd(rj−2 , rj−1 ) = gcd(rj−1 , rj )
gcd(rj−1 , rj ) = gcd(rj , 0) = rj

Therefore gcd(n, a) = rj .

Chapter 5 – Enciphering 51 / 86
Euclidean algorithm & GCD

Remark
Using the Euclidean algorithm, we can write the gcd, rj , in terms of n and
a. We simply work backwards.

Chapter 5 – Enciphering 52 / 86
Euclidean algorithm & GCD

Write rj = gcd(n, a) in terms if n and a.

Start from the last equation with nonzero remainder. Write rj as the
subject of the formula:
rj = rj−2 − rj−1 qj
Use the preceding equation, replace rj−1 with its expression in terms of
rj−2 and rj−3 .
rj = rj−2 − (rj−3 − rj−2 qj−1 )qj
= rj−2 (1 + qj−1 qj ) − rj−3 qj
Continue this process successively, replacing rj−2 , rj−3 , . . ., until you
obtain the final equation
rj = ax + ny ,
with x and y integers.

Chapter 5 – Enciphering 53 / 86
Euclidean algorithm & GCD

Example 5.23
Find gcd(7, 480) using the Euclidean algorithm. Then write the GCD in
terms of 7 and 480.

Solution. Euclidean algorithm equations for n = 480, a = 7 (the

important numbers have been boxed:

480 = 7 · 68 + 4
7 = 4 ·1+ 3
4 = 3 ·1+ 1
3 = 1 · 3 + 0.

Therefore gcd(7, 480) = 1.

Chapter 5 – Enciphering 54 / 86
Euclidean algorithm & GCD

1 = 4 − 3 ·1
= 4 − ( 7 − 4 · 1) · 1 = 4 · 2 − 7
= ( 480 − 7 · 68) · 2 − 7 = 480 · 2 − 7 · 137

Therefore
1 = 480 · 2 − 7 · 137

Chapter 5 – Enciphering 55 / 86
Multiplicative inverse & GCD

Theorem 5.24
Suppose a has an inverse b modulo n. Then gcd(a, n) = 1.

Proof
We have
ab ≡ 1 (mod n).
Thus there is an integer k such that

ab = kn + 1

If d is a common divisor of a and n, d must also divide 1. Thus d = 1 and

gcd(a, n) = 1.

Chapter 5 – Enciphering 56 / 86
Multiplicative inverse & GCD

Theorem 5.25
Suppose a, n are positive integers. If gcd(a, n) = 1, then a has an inverse
modulo n.
Proof
We can write the gcd, which is 1, in terms of a and n:

1 = ax + ny .

Taking mod n, we have

ax ≡ 1 (mod n)
Thus x is an inverse of a mod n.

Chapter 5 – Enciphering 57 / 86
Multiplicative inverse & GCD

From the above two results, we conclude that

Theorem 5.26
Suppose a, n are positive integers. Then a has an inverse modulo n iff
gcd(a, n) = 1.

Chapter 5 – Enciphering 58 / 86
Euclidean algorithm & Multiplicative inverse

Example 5.27
Find an inverse of 7 modulo 480
Solution:
We already have

1 = 480 · 2 − 7 · 137
Take mod 480, we have

7 · (−137) ≡ 1 (mod 480)

Therefore −137 in an inverse. Add 480 to it, we get the answer 343.
(We usually want an answer between 1 and n − 1 and in this case
n = 480.)

Chapter 5 – Enciphering 59 / 86
Modular exponentiation

In many applications, it is necessary to solve the following

Problem
Find the remainder of an when divided by m, where a and n are large
numbers.

Chapter 5 – Enciphering 60 / 86
Modular exponentiation

Example 5.28
Find the remainder when 223 is divided by 9.

Solution:
We can proceed by using mod. (Here all the congruences are (mod 9).

22 ≡ 4, 23 ≡ 8
25 ≡ 4 × 8 ≡ 5, 210 ≡ (25 )2 ≡ 25 ≡ 7
220 ≡ (210 )2 ≡ 49 ≡ 4 223 ≡ 220 23 ≡ 4 × 8 ≡ 5

Hence the remainder is 7.

However, this is not practical when the power is large.

Chapter 5 – Enciphering 61 / 86
Modular exponentiation

Modular exponentiation
Find the remainder of an when divided by m, where a and n are large
numbers.
Step 1. Express n in binary form.
Step 2. Write n as a sum of powers of 2.
Step 3. Write an = ab1 ab2 . . . abk where each bi is a power of 2.
Step 4. Compute the remainder ri when abi is divided by m.
Step 5. Find the remainder when the product r1 r2 . . . rk is divided by m to
get the answer.

Chapter 5 – Enciphering 62 / 86
Modular exponentiation

Example 5.29
Find the remainder when 223 is divided by 9.

Step 1: 22 = (10111)2
Step 2: 10 = 24 + 22 + 21 + 1 = 16 + 4 + 2 + 1.
Step 3: 210 = 216+4+2+1 = 216 24 22 21 .

Chapter 5 – Enciphering 63 / 86
Modular exponentiation

Remark
Steps 1, 2 can be done as follows:
First write down all powers of 2 which are ≤ 10: 1, 2, 4, 8, 16.
Then 23 − 16 = 7, 7 − 4 = 3, 3 − 2 = 1. Thereofore

23 = 16 + 4 + 2 + 1

Chapter 5 – Enciphering 64 / 86
Modular exponentiation

Step 4. Each step is obtain by squaring the previous step. (All

congruences are (mod 9).)

2 ≡ 2
22 ≡ 4
24 ≡ (22 )2 ≡ 42 ≡ 7
28 ≡ (24 )2 ≡ 72 ≡ 4
216 ≡ (28 )2 ≡ 42 ≡ 7

Step 5: 223 = 216 24 22 21 ≡ 7 × 7 × 4 × 2 ≡ 5 (mod 9).

Chapter 5 – Enciphering 65 / 86
Modular exponentiation

Example 5.30
Find the remainder when3101 is divided by 100.

Step 1. Powers of 2 ≤ 101: 1, 2, 4, 8, 16, 32, 64.

Step 2. 101 − 64 = 37, 37 − 32 = 5, 5 − 4 = 1. So 101 = 64 + 32 + 4 + 1.

Step 3. 3101 = 364 332 34 31 .

Chapter 5 – Enciphering 66 / 86
Modular exponentiation

Step 4. With all congruence (mod 100):

3 ≡ 3
32 ≡ 9
34 ≡ 92 ≡ 81
38 ≡ 812 ≡ 61
316 ≡ 612 ≡ 21
332 ≡ 212 ≡ 41
364 ≡ 412 ≡ 81.

Step 5. 3101 ≡ 364 332 34 31 ≡ 81 · 41 · 81 · 3 ≡ 3 (mod 100).

Chapter 5 – Enciphering 67 / 86
Modular exponentiation

Remark
In general, if n = (ak . . . a1 a0 )2 , then 2k ≤ n < 2k+1 .
From here we deduce that k = blog2 nc.
The binary conversion also takes k steps.The squaring operation have to
be performed k times. Another k multiplications are needed to obtain the
final result.
Thus the total number of operations is roughly 3k.
This is much lower than the n operations that you’d need if you were to
perform the calculation by brute force.
For example if n = 1000, k = 9.

Chapter 5 – Enciphering 68 / 86
Fermat’s Little Theorem (FLT)

Theorem 5.31
Let p be a prime number and a be an integer which is not a multiple of p.
Then
ap−1 ≡ 1 (mod p).

We shall not prove this theorem.

Chapter 5 – Enciphering 69 / 86
Fermat’s Little Theorem (FLT)

Example 5.32
24 ≡ 1 (mod 5)

36 ≡ 1 (mod 7)

612 ≡ 1 (mod 13)

Chapter 5 – Enciphering 70 / 86
Public Key Codes: RSA

Disadvantage of Common Key:

Traditional cryptosystems like the affine transformation depends on a

common key for both enciphering and deciphering.

Its security depends on the ability to keep the key safe in two places:
the sender and the recipient.

May need to pass the key from sender to recipient.

Chapter 5 – Enciphering 71 / 86
Public Key Codes: RSA

A public key code is a cryptosystem in which

the enciphering key is not the same as the deciphering key,

the enciphering key may be made public, only the receiver has the
deciphering key.

Ability to encipher does not enable you to decipher!

The most celebrated public key code is the so-called RSA

cryptosystem invented by Ron Rivest, Adi Shamir and Leonard
Adleman.

Chapter 5 – Enciphering 72 / 86
Public Key Codes: RSA

Ronald Linn Rivest

Born: May 6, 1947 (age 67), Schenectady, New York, United States.
Co inventor of RSA. He is the Andrew and Erna Viterbi Professor of
Computer Science at MIT’s Department of Electrical Engineering and
Computer Science and a member of MIT’s Computer Science and
Artificial Intelligence Laboratory. United States
Chapter 5 – Enciphering 73 / 86
Public Key Codes: RSA

Adi Shamir
Born: July 6, 1952 (age 62), Tel Aviv, Israel
Co-inventor of the RSA. Currently at Weizmann Institute of Science

Chapter 5 – Enciphering 74 / 86
Public Key Codes: RSA

Leonard Max Adleman

Born: December 31, 1945 (age 68), San Francisco, California, United
States
Co inventor of RSA. Professor of computer science and molecular biology
at the University of Southern California.
Chapter 5 – Enciphering 75 / 86
Public Key Codes: RSA

RSA Encipering:

Pick two large primes p and q (in practice each has about 200 digits).
Let n = pq.

Pick any integer k that is coprime to (p − 1)(q − 1)).

The pair of integers (n, k) is the enciphering key.

Let M be the number formed from the string of digits of the

plaintext. We require that 0 ≤ M < n.

Compute the remainder r of M k on division by n:

r ≡ Mk (mod n).

The ciphertext is the string of digits of r .

Chapter 5 – Enciphering 76 / 86
Public Key Codes: RSA
RSA Deciphering:

Find the inverse of k modulo (p − 1)(q − 1) where 1 < j < n. The

inverse exists as k and (p − 1)(q − 1) are coprime. Note that

kj ≡ 1 (mod (p − 1)(q − 1)).

This means, for some integer t:

kj = t(p − 1)(q − 1) + 1.

The integer j is the deciphering key.

To decipher the ciphertext r , compute r j .

Then the plaintext M is the remainder of r j modulo n:

r j ≡ M kj ≡ M t(p−1)(q−1)+1 ≡ M (mod n).

Chapter 5 – Enciphering 77 / 86
Public Key Codes: RSA

The final step

r j ≡ M kj ≡ M t(p−1)(q−1)+1 ≡ M (mod n).

is justified as follows:
We have
r j ≡ M(M (p−1) )t(q−1) ≡ M (mod p).
and
r j ≡ M(M (q−1) )t(p−1) ≡ M (mod q).
Thus r j − M are both multiples of p and q. Since p, q are distinct primes,
r j − M is a multiple of pq = n. Therefore

rj ≡ M (mod n).

Chapter 5 – Enciphering 78 / 86
Public Key Codes: RSA

Security of RSA:

The enciphering key (n, k) is public; anyone can use it for encryption.

The prime factors p and q of n are kept secret. If they are known, then
the deciphering key j can be worked out.

Chapter 5 – Enciphering 79 / 86
Public Key Codes: RSA

The security on the practical impossibility of factoring large numbers even

by the fastest computers of today.

The most difficult integers to factor in practice using existing algorithms

are those that are products of two large primes of similar size, and for this
reason these are the integers used in cryptographic applications. The
largest such semiprime yet factored was RSA-768, a 768-bit number with
232 decimal digits, on December 12, 2009. This factorization was a
collaboration of several research institutions, spanning two years and
taking the equivalent of almost 2000 years of computing on a single-core
2.2 GHz AMD Opteron. Like all recent factorization records, this
factorization was completed with a highly optimized implementation of the
general number field sieve run on hundreds of machines.

Chapter 5 – Enciphering 80 / 86
Public Key Codes: RSA

Example 5.33
Suppose the plaintext is M = 141. Determine the RSA ciphertext using
the public key (n, k) = (1537, 47).

Solution.The ciphertext is

r ≡ 14147 (mod 1537).

Chapter 5 – Enciphering 81 / 86
Public Key Codes: RSA

We use modular exponentiation.

47 = 32 + 8 + 4 + 2 + 1.

With all congruences (mod 1537):

1412 ≡ 1437. 1414 ≡ 778.

1418 ≡ 1243. 14116 ≡ 364.

14132 ≡ 314.
∴ 14147 = 14132 1418 1414 1412 1411 ≡ 314 · 1243 · 778 · 1437 · 141 ≡ 658.
Therefore, the ciphertext is r = 658.

Chapter 5 – Enciphering 82 / 86
Public Key Codes: RSA

Example 5.34
Suppose the RSA ciphertext is r = 1252 using the public key
(n, k) = (1537, 47). Determine the plaintext given that 1537 = 29 × 53.

Solution. First determine the deciphering key j which is the inverse of 47

modulo φ(1537) = (29 − 1)(53 − 1) = 1456, i.e.,

47j ≡ 1 (mod 1456).

Chapter 5 – Enciphering 83 / 86
Public Key Codes: RSA

Euclidean algorithm equations:

1456 = 47 · 30 + 46
47 = 46 · 1 + 1 .

∴ 1 = 47 − 46
 
= 47 − 1456 − 47 · 30
= 47 · 31 − 1456 .
∴ 1 ≡ 47 · 31 (mod 1456)

The deciphering key is j = 31.

Chapter 5 – Enciphering 84 / 86
Public Key Codes: RSA

The plaintext is the remainder of r j = 125231 after divided by 1537. Again

we use modular exponentiation with all congruences (mod 1537).

12522 ≡ 1301. 12524 ≡ 364.

12528 ≡ 314. 125216 ≡ 228.

Since 31 = 16 + 8 + 4 + 2 + 1,

125231 ≡ 125216 12528 12524 12522 12521 ≡ 228·314·364·1301·1252 ≡ 125.

The plaintext is 125.

Chapter 5 – Enciphering 85 / 86
Public Key Codes: RSA

When we are given a message such as SELL NOW, we first convert it into
a number, using A = 01, B = 02, . . . , Z = 26, space = 27 so that each
symbol is represented by 2 digits. In this case we get a 16 digit number.
They will need to be broken into blocks of equal size so that each block is
a number < n. For example if n has 5 digits, you’ll need to break it up
into 4 blocks, each of size 4. If n has 6 digits, you append 4 copies of 0 on
the left to make it a 20-digit number and break it up into 4 blocks each of
size 5.

Chapter 5 – Enciphering 86 / 86