MATHEMATICS IN THE

MODERN WORLD

CODES AND CIPHERS

 The Beauty of Codes
LEARNING OBJECTIVES:

At the end of the chapter, the student is expected to:

1. describe some coding schemes that are used to assign
identification numbers;
2. use check digits for error detection;
3. detect code errors;
4. discuss the process of disguising data; and
5. analyze encrypted data.
 DEFINITIONS
Code
- is a symbolic way to represent information
- utilizesa set of symbols to represent an object.
Example:
“A” can be replaced by a string of “0’s” and “1’s”, say 00101.

*Codes are used in product identification and labeling.

 DEFINITIONS
Cipher
- a scheme to conceal information by switching letters or representing
them with other symbols.
It is used heavily incommunication and data transmission.
 Examples of Codes
.

Bar Code

QR Codes
 Examples of Ciphers
.
 CRYPTOLOGY
Cryptology is the study of codes, or the art of writing and solving
them.
Types:
Cryptography is used to protect digital data. It is a division of
computer science that focuses on transforming data into formats
that cannot be recognized by unauthorized users.
An example of basic cryptography is an encrypted message in
which letters are replaced with other characters.
Cryptanalysis is the process of studying cryptographic systems to
look for weaknesses or leaks of information.
 CODING THEORY
Coding theory is the study of methods for efficient and accurate
transfer of information.
- It is concerned with detecting and correcting transmission errors
- deals with the design of error-correcting codes for the reliable
transmission of information across noisy channels
- makes use of classical and modern algebraic techniques
involving finite fields, group theory, and polynomial algebra
 International Standard Book Number (ISBN)
The International Standard Book Number (ISBN) was introduced as
a scheme of regulating and keeping track of various publications in
different parts of the world.
From a 10-digit code, it was expanded in 2007 to a 13-digit code.
Each published book, including media variations—electronic,
paperback, hardcover—is assigned a distinctive ISBN code.
In the Philippines, the National Library of the Philippines (NLP)
takes charge of the ISBN registration, allocation, and designation
for Filipino publishers and authors.
 International Standard Book Number (ISBN)
An ISBN code takes the form x1x2x3 – x4x5x6 – x7x8 – x9x10x11x12 –
x13. Currently, x1x2x3 = 978 (or 979). The fourth digit x4is allocated
for the country code while the remaining digits (except the last) are
used to identify the author and the title of the book.
The last digit, x13, is called the check digit. This can be obtained
using the formula
x13 = 10 – (x1 + 3x2 + x3 + 3x4 + x5 + 3x6 + x7 + 3x8 + x9 + 3x10 + x11 +
3x12) mod 10
If x13 = 10, then the check digit is 0.
 International Standard Book Number (ISBN)
Example 1
Determine the check digit for the book “Larry Can’t Cook”:
978-971-27-2769-?
 International Standard Book Number (ISBN)
Example 1
Determine the check digit for the book “Larry Can’t Cook”:
978-971-27-2769-?
Solution:
x13 = 10 – (x1 + 3x2 + x3 + 3x4 + x5 + 3x6 + x7 + 3x8 + x9 + 3x10 + x11 +
3x12) mod 10
x13 = 10 – [9+3(7)+8+3(9)+7+3(1)+2+3(7)+2+3(7)+6+3(9)] mod 10
= 10 – (154 mod 10)
= 10 – 4 = 6
Thus, the check digit is 6.
 International Standard Book Number (ISBN)
Example 2
Determine if the ISBN code 978-971-27-2770-4 is valid or not.
 International Standard Book Number (ISBN)
Example 2
Determine if the ISBN code 978-971-27-2770-4 is valid or not.
Solution:
x13 = 10 – (x1 + 3x2 + x3 + 3x4 + x5 + 3x6 + x7 + 3x8 + x9 + 3x10 + x11 +
3x12) mod 10
x13 = 10 – [9+3(7)+8+3(9)+7+3(1)+2+3(7)+2+3(7)+7+3(0)] mod 10
= 10 – (128 mod 10)
= 10 – 8
=2≠4
The ISBN code is not valid.
 Universal Product Code (UPC)
The UPC (Universal Product Code) number is a 12-digit code that
usually accompanies the bar code of a product.
The last digit (or the 12th digit) is the check digit.
Like in the case of the ISBN, it can be computed using the formula
x12 = 10 – (3x1+x2+3x3+x4+3x5+x6+3x7+x8+3x9+x10 +3x11) mod 10
If, x12 = 10, then the check digit is 0.
 Universal Product Code (UPC)
Example 1.
Determine if the UPC of a certain product is valid or not.
 Universal Product Code (UPC)
Example 1.
Determine if the UPC of a certain product is valid or not.
Solution:
x12 = 10 – (3x1+x2+3x3+x4+3x5+x6+3x7+x8+3x9+x10 +3x11) mod 10
x12 = 10 – [3(9)+8+3(7)+6+3(5)+4+3(3)+2+3(1)+0+3(9)] mod 10
= 10 – (122 mod 10)
= 10 – 2 = 8
The UPC is valid.
 Credit Cards
Credit card numbers can be easily checked through the “check
digit.”
In the Philippines, Visa and Mastercard are the dominant credit
cards in the market, normally having 16-digit numbers except for
some Visa cards that have 13 digits only.
Credit card numbers can be checked by doubling every other digit
starting from the second to the last digit (the last digit being the
check digit) and summing up all the resulting numbers.
 Credit Cards
If the doubled digit results in a 2-digit number, simply treat the two
digits as separate digits.
The card number is valid only if the sum of the digits under modulo
10 is congruent to 0
 Credit Cards
Determine which credit card number is valid and which is not.
a. 5234 8213 3410 1298
b. 6011 0123 9145 2317
 Credit Cards
a. 5234 8213 3410 1298

Sum =1+0+2+6+4+1+6+2+2+3+6+4+2+0+2+2+1+8+8
= 60 ≅ 0 (mod 10)
The indicated credit card number is valid.

b. 6011 0123 9145 2317

Sum = 53 ≅ 3 (mod 10)
Not Valid
 Binary Codes
A binary code refers to a string of 0’s and 1’s.
Each character in the string is called a bit (short for binary digit), while
a series of eight bits is called a byte.
Each key in the keyboard of a computer corresponds to a binary
code of at least five bits (but mostly 1 byte).
In particular, computers can translate letters and symbols into binary
codes using the American Standard Code for Information Interchange
(ASCII codes).
 Binary Codes
For purposes of discussion,
consider 5-bit codes for the
familiar keys in a standard
computer keyboard.
 Binary Codes
Figure out the message in the following coded words:
0110100001101000100000000010011001100000001101010101110
 Binary Codes
Example:
Figure out the message in the following coded words:
0110100001101000100000000010011001100000001101010101110

First, segregate the string into blocks of 5-bit codes:

01101 00001 10100 01000 00000 01001 10011 00000 00110
10101 01110
 Binary Codes
Refer to the table for the corresponding key:

01101 M 00001A 10100T 01000H 00000

01001 I 10011 S 00000
00110 F 10101 U 01110 N
 Binary Codes
Write the following using the 5-bit binary codes:
BE LOGICAL
 HAMMING CODES
The Hamming Code, a scheme for error-correction, was
introduced by R. W. Hamming.
This scheme uses a redundant bit which is called a parity bit (also
termed check bit) which is a 1-bit that is inserted in each string of
binary codes.
A parity bit is either ‘even’ or ‘odd’ depending on whether there is
an even or odd number of 1’s.
 HAMMING CODES
Coded messages tend to be very prone to distortion when being
transmitted to available medium because of the presence of some
environmental interference or unforeseen defects in the
transmission medium.
Any changes that may occur in a message that may alter its original
meaning is considered an error.
In the context of binary codes, an error occurs when there is an
unintentional alteration of the bits, the “0” getting altered as “1” or
the other way around.
 Building a Hamming Code
Step 1. Insert additional bit positions
If the length of the original code is r, then add m + 1 more bit
positions, where m is the largest power of 2 that satisfies the
inequality: 2m < r.
The positions (𝑃𝑖) of the additional bits are at the corresponding
powers of 2 : i=20 = 1, 21 = 2, 22 = 4,…, 2m.
 Building a Hamming Code
Step 2. Extract sub-codes for the parity codes of each additional bit.
For P1: copy the bits at positions 1,3,5,7,… (copy 1, skip 1)
For P2: copy the bits at positions 2,3,6,7,10,11,… (copy 2,skip 2) In
general,
For Pk: copy k bits (starting with the kth bit) then skip k bits
Step 3. Find Pi : The value of Pi is 0 if the resulting sub-code in Step
2 is of even parity, otherwise, the value is 1.
 Example: Find the Hamming code of 10010
10010 has 5 bits (that is, it is of length 5) ====> 𝑟=5
Observe:
22 = 4< 5
𝑚 = 2, 𝑚 + 1 = 3
23 = 8 > 5
===> Insert 3 additional bits, at positions 20, 21, and 22 (i.e. P1, P2, P4)
===> the Hamming code has 𝑚 + 1 + 𝑟 = 3 + 5 = 8 bits
Positions 1 2 3 4 5 6 7 8

Digit P1 = ? P2 = ? 1 P4 = ? 0 0 1 0

Observe that the first bit of the original code becomes the third bit of the
Hamming code, the second bit becomes the 5th bit, and all remaining bits
Moving 3 bits forward.
 Example: Find the Hamming code of 10010
.
Positions 1 2 3 4 5 6 7 8

Digit P1 = ? P2 = ? 1 P4 = ? 0 0 1 0

Now form the subcodes:

Subcode for P1: P1P3P5P7 = ?101 ==> parity is even ==> P1 = 0
Subcode for P2: P2P3P6P7 = ?101 ==> parity is even ==> P2 = 0
Subcode for P4: P4P5P6P7 = ?001 ==> parity is odd ==> P4 = 1

Hamming Code: 00110010

 Example
A local government unit was notified that a vaccine package will be
delivered from the DOH central office. For security reasons, the time
of delivery was coded as follows
111101000001010111101000101101

What is the message? Do you think there is an error? If there is,

can you correct it and get the real message?
 Example
• Mark all bit positions that are powers of 2
111101000001010111101000101101
• original message
1010000101011101000101101
10100 00101 01110 10001 01101
T E N Q M
 Example
Corrected Hamming code:
111101000001010111100000101101
Remove parity checks: 111101000001010111100000101101

1010000101011100000101101

10100 00101 01110 00001 01101

T E N A M
 Cryptography
Communication is a process by which information is shared among
individuals. The manner of disseminating messages has evolved
along with the accelerated growth of technology. This technological
growth, however, has posed bigger challenge in terms of
maintaining the integrity of information being shared.
With the advent of wireless communication and the widespread
reliance on the internet, information is at a high risk of being
breached. Mathematics has developed a system by which this
problem can be addressed—through cryptography.
 Cryptography
Cryptography is the process of converting data or information into
codes, primarily for the purpose of keeping it secured (confidential
and undistorted). It involves encryption and decryption.
Encryption basically converts a message into meaningless and
usually unreadable formats that only the intended recipient can
understand.
Decryption, on the other hand, is the process of recovering the
encrypted information.
 Shift Cipher
Use the natural order of the letters of the English
alphabet:

The goal is to replace the letters of a given message by

another letter which is at some fixed number of positions
according to the natural order of the letters.
Shift Cipher

Formula: 𝐶 = (𝑃 + 𝐾)𝑚𝑜𝑑 26

𝑃 is the original position of a letter in the given message,

𝐶 is the shifted position (code letter),
𝐾 is a constant that determines the fixed number of shift
positions.
 Example: Encryption

Encrypt the message “Let us drink coffee” using the shift cipher :
𝐶 = (𝑃 + 9) mod 26
 Example: Encryption

Encrypt the message “Let us drink coffee” using the shift cipher :
𝐶 = (𝑃 + 9) mod 26

For the letter “L”, P=11 ==> C = (11+9) mod 26 = 20

==> the code letter for “L” is “U”
For the letter “T”, P=19 ==> C = (19+9) mod 26 = 2
==> code letter for “T” is “C”
 Example: Encryption

Verify the following:

The Encrypted message is : UNCDBMARWTLXOONN

Decryption
How can the receiver of an encrypted message recover the
original message?
This is where the concept of inversion comes in.
Encryption Cipher: C = (P + K) mod 26
Decryption Cipher: P = (C – K) mod 26
The recovery process of the encrypted message is now
supposed to be backwards, hence the –K in the formula.
Example
Using the encryption formula: C = (P + 9) mod 26

Decrypt the message: RFJWCCXFJCLQVXERN

 Example
The decryption formula: P = (C - 9) mod 26

For the letter “R”, C=17 ==> P = (17-9)mod 26 = 8

==> the corresponding original letter is “I”
For the letter “C”, C = 2 ==> P=(2-9) mod 26 = -7 (mod26)
Recall that -7 means the additive inverse of 7 under modulo 26
(that is, the number to be added to 7 to get 0 mod 26).
Clearly, this must be 19. So, -7 mod 26 = 19, and this corresponds
to the letter “T”.
 Example
Verify the following:

The original message is : I WANT TO WATCH MOVIE

 Remark
In the decryption formula
P = (C - 9) mod 26
recall that -9 also denotes the additive inverse of 9 under modulo
26, and -9 mod 26 = 17. So, an equivalent formula for the
decryption should be
P = (C + 17) mod 26
To verify this, recall that “R” was decrypted as “I” using P=(C-9)
mod 26. If P = (C + 17) mod 26 is applied, with C=17
P = (17+17) mod 26 = 34 mod 26 = 8
And the corresponding letter is also “I”.
 Affine Cipher
A more complicated cipher formula involves multiplying the cipher
values of each letter of the original message. In a way, this will be
more difficult to crack than the shift cipher technique.
Encryption Cipher (m, K): C = (3P + K) mod 26
1
Decryption Cipher (m, K): P = (C – K) mod 26
𝑚
1
As a reminder, denotes the multiplicative inverse of m with
𝑚
respect to modulo 26 operation.
Note also that the pair (m,K) is a valid encryption cipher
parameters if m and 26 are relatively prime.
 Example: Encryption
Encrypt the message:
“rainbow after the rain” using the affine cipher (m,K) = (3,5).
 Example: Encryption
Encrypt the message:
“rainbow after the rain” using the affine cipher (m,K) = (3,5).

Solution:
C = (3P + 5)mod 26

R A I N B O W A F T E R T H E R A I N - message
E F D S I V T F U K R E K A R E FD S - encrypted message
 Decryption
1
Decryption formula: 𝑃 = (𝐶 − 𝐾) mod 26
𝑚
1 1
= ≅ 9mod 26, since (3)(9)mod 26 = 27mod 26 = 1
𝑚 3
-K = -5 ≅ mod 26, since 5 + 21 = 26 ≅ 0mod 26
1
Again, recall that denotes the multiplicative inverse of 3 mod 26,
3
while -5 denotes the additive inverse of 5 mod 26.

Decryption formula: P = 9(C + 21) mod 26 or

P = 9(C – 5) mod 26
 Decryption
Decrypt the message using the formula P = 9 𝐶 + 19 𝑚𝑜𝑑26
SHNHMFXUMFRT
 .

Reference: MTAP-TL Lecture Series