MODULE in

GEC 3 – Mathematics in the Modern World

1. Title of the Module

CODES AND CRYPTOGRAPHY
2. Introduction
In this era of technology and advanced communication, massive quantities of info
rmation or data (text, numbers, pictures, and graphics) are transmitted via various
media from one stage to another. It is very critical that these data are transmitted in their
original form and during transmission are not distorted.

3. Learning Outcome
At the end of this chapter, you should be able to:
1. explain and apply the substitution Cipher;
2. discuss and apply the transposition cipher;
3. describe and apply the KSA Cryptology system;
4. analyze and apply the autokey cipher;
5. clarify and apply the Vigenère cipher;
6. define parity and illustrate even and odd parity;
7. differentiate compression from decompression;
8. apply the mathematics behind the UPC; and
9. Create valid UPCs.
4. Learning Content
Coding theory and cryptography play an especially important role in the transmis
sion of data. Why does coding theory and cryptography differ? Coding theory is concern
ed with error correcting codes while cryptography concerns the stability, privacy and
confidentiality of information transmitted over a secure channel.
The theory of coding and cryptography makes use of traditional and modern 
algebraic techniques involving finite fields, group theory, number theory, and
experimental design theory.

The term "coding" is basically associated with three areas. These are
1. Data Compression- Effective encoding of source information is concerned,
so that it takes as little space as possible.
 2. Error-correcting codes - These are about the authenticity, safety, 
correctness, integrity and reliability of noisy channel communication.
3. Cryptography (or cryptology) - The protection, privacy, or confidentiality of
communication over an insecure channel is concerned.

EFFICIENT COMMUNICATIONS
All life forms communicate. The people communicate verbally and nonverbally
with each other. Animals like cats use their meows and body language to communicate 
with each other. Peacocks can fan their feathers in an impressive visual display
designed to convey a territorial alert.
A dolphin may slap his tail on the water to draw other people's attention in the
area. Bees tell other bees that when they return to the hive, they have found nectar by
"dancing". Deer twitch their tails to warn other deer to comply of potential
hazards ahead of them.
Communication is round about us. It is imperative that the intended message is
sent and received. The ability to send a direct message in the shortest period of time is
Efficient communication. With this communication type the message may or may not be 
interpreted in the intended manner.
The recipient may feel the brevity is inadequate and may need more clarification
to effectively convey the message. Being able to master effective communication in
business, in classrooms, within the confines of our homes and elsewhere exerts a vital 
and positive impact on the professional and personal relationships of all those involved
in communication. The following diagram shows how the communication process
operates.

In electronics noise in an electrical signal is an unnecessary disturbance. Noise
is generated by electronic devices. It varies greatly, as many different factors generate
it. Noise is an error in communication systems, or an unwanted random disturbance to a
useful information signal. The noise is a summation of unwanted or distracting energy
from natural sources, often man-made.
CRYPTOGRAPHYY
The sending of information over the internet is tantamount to writing a postcard
letter. When a postcard is sent via the mail, anyone who has access to the snail mail
will read the postcard's message to the receiver.
When people send information over the internet, they want their information to be
unreadable or undecipherable, not understood by those who are not the intended
recipients of those messages. The pieces of information should also be safe, should not
be stolen or altered during transmission. It is here that cryptography enters.
Cryptography can be used to authenticate information systems and computer
users. It is an indispensable tool used in computer systems to protect the information. It 
is used everywhere, and on a daily basis by billions of people around the world.
Cryptography can generally be used in three different areas, namely symmetric-
key cryptography, hash functions and cryptography with a public-key.
For a symmetric-key cryptography, both sender and receiver share a common
key. The sender uses this single key to encrypt his or her plaintext message, and
sends the ciphertext to the receiver. This single key is the same key the receiver uses t
odecrypt the ciphertext for plaintext recovery.
There are two different keys in a no key cryptography, the public and private
keys. The Public Key can be distributed freely. The private key shall not be revealed,
and shall remain a secret. For encryption, the public key is used and the private key is
the one used for decryption.
There is no use of key in hash functions. The hash value is determined according
to the plaintext which makes recovery of the plaintext content impossible. Many
operating systems also utilize hack functions to encrypt passwords.
Cryptography involves two steps: encryption, and decryption. Encryption is the
process of encoding a message or information in such a way that it can only be
accessed by authorized recipients and those who are not authorized can not.

SUBSTITUTION CIPHERS
This is a simple encryption method. In this method, each letter in the message is
replaced by another letter following some established mapping. An example of a
substitution cipher is called the Caesar cipher or shift cipher. This is considered the
earliest known use of cryptology developed by Julius Caesar. According to literature, he
made secret messages by shifting each letter three letters forward in the alphabet.
 To express the Caesar's encryption mathematically, first replace each letter by
an integer from 0 to 25, corresponding to the letters of the English alphabet, where A =
0 and Z = 25. The Caesar's encryption can be represented by a function f that assigns
to the non-negative integer p, p < 25; the integer f(p) is the set {0, 1, 2, ., 25}. With
f(p) = (m +3 mod 26)
The encrypted letter represented by m is replaced with the letter represented by
(m + 3) mod 26.
The Caesar's encryption uses modular arithmetic. Modular arithmetic states that
if a and b are integers and n is a positive integer, then a is congruent to b modulo n if n
divides a - b. The notation for congruence modulo is a≅ b (mod n) to indicate that a is
congruent to b modulo n. Two numbers are congruent MOD 26 if they leave the same
remainder when divided by 26.
Example 1
Say that the original message is GODBLESSYOU. If a shift of 5 letters is used,
then the encrypted form of this message will be LTIGQIXXDTZ. That is, a shift of 5
letters means A will be replaced by F, B will be replaced by G, C will be replaced by H,
and so on.
Original: ABCDE FGH I JKLMNO PQRSTUVWXYZ
MAPS T0: FGHIJKLMNO PQRSTUVWX Y Z ABCDE

Example 2
Using modular arithmetic and Caesar cipher, what is the secret message that will
be produced from the original message BAREFOOT ON THE GRASS.
Solution:
First, replace the letters in the original message with numbers. This yields
1 0 17 4 5 14 14 19 14 13 19 7 4 6 17 0 18 18
Next, replace each of these numbers p by f(p)= (p +3) mod 26. This yields
4 3 20 7 8 17 17 22 17 16 22 10 7 9 20 3 21 21
Then, translate these numbers back to letters. This yields
EDUHIRRWRQWKHJUDV
TRANSPOSITION CIPHER
A transposition cipher is another encryption method in which the order of
characters is changed to obscure the message. An early version of a transposition
Cipher was a Scytale, in which paper was wrapped around a stick and the message
was written. Once unwrapped, the message was unreadable, until the message was
wrapped around a same-sized stick again.
The transposition cipher used currently is done by writing the message in rows,
then forming the encrypted message from the text in the columns. Use nonsense letters
to complete the end of the last row if it contains less characters than what was set.
You can create your version of the row-and-column based transposition cipher.
You can specify explicitly the order in which the columns should be recorded. For
example, the method could specify that after writing the message out in rows, you
should record the third column, then the fourth, then the first, then the fifth, then the
second. This adds additional complexity that will make it harder for the not-intended
recipients to decipher the original message.
There are times when you can use a keyword. This keyword specifies how many
characters there are in the row and the order in which the letters in the keyword is
arranged and how the column will be read.
Example 1
Encrypt the message "Let us dance in the dark tonight and you between
my arms" using rows of 9 characters long.
Solution:
There are 45 characters in the message so if you want 9 characters each
row, you will have 5 rows as follows:

L E T U S D A N C
E I N T H E D A R
K T O N I G H T A
N D Y O U B E T W
E E N M Y A R M S
 You can then encode the message by recording down each column with 5
characters each. Starting with the first column and reading down will yield
LEKNE EITDE TNOYN UTNOM SHIUY DEGBA ADHER NATTM CRAWS.
Removing the spaces to hide the size of the original message will yield the
encrypted message
LEKNEEITDETNOYNUTNOMSHIUYDEGBAADHERNATTMCRAWS.
Example 2
Encrypt the message YOU AND ME AGAINST THE WORLD using a
transposition cipher with the keyword SEXY.
Solution:
The keyword is SEXY. This means that the rows should have 4 characters
each. The order of the letters in the alphabet will dictate which order to read the
columns.
To make the encryption key easier to remember, a word can be used. For
example, if the key word is MONEY, it will specify that rows should have 5
characters each. The order of the letters in the alphabet will dictate which order
to
read the columns in. Since E, the 2nd letter in the keyword SEXY, is the earliest
letter in the alphabet from the keyword SEXY, the 2nd column will be used first,
followed by the first column (S), followed by the end column (X), and then by
the 3rd column (Y).
So, writing the message in rows 4 characters yields

Y O U A
N D M E
A G A I
N S T T
H E W O
R L D X

Coding the 4th column first yields AEIT OXYN ANHR ODGS ELUM
ATWD, and removing the space to conceal evidence of encryption yields
AEITOXYNANHRODGSELUMATWD.

RSA PUBLIC-KEY CRYPTOGRAPHY

 RSA is a cryptosystem for public-key encryption. It was introduced in 19977 by
Ron Rivest, Adi Shamir and Leonard Adleman of the Massachusetts Institute of
Technology. So, RSA stands for Rivest, Shamir, and Adleman.
RSA is used largely to secure highly sensitive data and information especially
when these data and information are sent over networks like the internet.
Public-key cryptography is otherwise known as asymmetric cryptography. This
method uses two different keys that are mathematically linked to each other. One is the
public key and the other is the private key. The public key is used to encrypt a plaintext
and can be shared with anyone. The private key is the one used to decrypt the
ciphertext and must not be shared.
In RSA cryptography, both the public and the private keys can encrypt a
message. The opposite key from the one used to encrypt a message is used to decrypt
it. This attribute is one of the reasons why RSA has become the most widely used
encryption-decryption algorithm. It provides a method of assuring the confidentiality,
integrity, authenticity, and non-reputability of communications that transpire on the
internet.
To make sure that the message originated from a sender, and was not just sent
by a third party who may have used the same encryption key (that of the receiver), you
need a digital signature to come with the message.
To use RSA, follow the following steps to generate the keys
1. Randomly choose two different prime numbers p and q.
2. Calculate n by multiplying p and q, that is n = pq. (n is the modulus for the
public key and the private key.)
3. Calculate m = φ(n) = (p - 1) (q - 1).
4. Pick an integer e that is greater than 1 and less than n and relatively prime to
m = ( p - 1) (q - 1). There must be no common factor for e and (p - 1) (q - 1) except for
1. In other words, two numbers e and (p - 1) (q - 1) are coprime.
5. Compute d, the multiplicative inverse of e modulo φ(n) = m. Such that
ed = 1 (mod m) (Euclid's algorithm).
6. Encrypt with the public key P= (e, n). Decrypt with the private key S = (d, n).
Once the public and private keys are known, the following basic steps can be
used to encrypt and decrypt a message.
1. Convert text message to a numerical message.
2. Encrypt a to A using this formula: A = ae mod n.
3. Decrypt A to a using this formula: a = Ad mod n.
CONGRUENCES
A congruence of the form ax = b (mod m), where a and b are integers, m is a
positive integer, and x is an unknown integer, is called a linear congruence in one
variable x. An integer x 0 is called and solution of ax = b (mod m) if a x o = mb (mod m).
For example, consider the linear congruence 4x ≡ (mod 9) in one variable. Now,
4 ∙ 7 = 1 (mod 9), so it follows that 7 is a solution of this noruence. Notice that
4 ∙ 16= 1 (mod 9). Therefore, 16 is also a solution of 4x =1 (mod 9).
RSA public key cryptography uses congruences to compute for the public and
private keys.
Example 1
Find the solution, if any, of the congruence 8x ≡ 6 (mod 4).
Solution: Let 8x ≡ 6 (mod 4). Here, the ged (8, 4) = 4 and 4 does not
divide 6. Hence, this congruence has no solution.

Example 2
Find all solutions of the congruence 17x = 4 (mod 36).
Solution: Here, gcd (17, 36) =1. Therefore, 17x = 4 (mod 36) has a unique
solution.
Express 1 = 17u + 36v
Now, 36 = 2 ∙ 17 + 2
17 = 2 ∙8 + 1
8 = 8 ∙1 + 0
Then, 2 = 36 - 2 ∙17
9 = 17 – 1 ∙ 8
1 = 17 - (36 – 2 ∙ 17) ∙8
1 = 17 ∙ 17 – 36 ∙ 8
Hence, 4 = 17 ∙ 68 +36 (-32). This implies that 17 ∙ 68 = 4 (mod 36).
Hence, x 0 = 68 is a solution of 17x = 4 (mod 36). Now 68 = 36 (mod 36).
Therefore, the given congruence has the solutionx = 36 (mod 36).
 Example3
Find the public key and private key if p = 3, q = 11.
Following the steps to generate the keys:
1. Since p = 3 and q = 11, n =3 * 11 = 33.
2. φ(n) = m = (p - 1) (q - 1) = (2)(10) = 20.
3. Let e = 3.
4. Compute d such that ed = 1 mod m.
That is, d = e−1 mod m = 3−1 mod 20 . find a value for d such that φ
divides (ed- 1), that is 20 divides 3d-1. (You can test for d = 1,2, 3,..).
From these, d = 7.
5. So, the public key is (3, 33) and the private key is (7, 33). 3 4. mod 20.
Find a value for 5.
Now suppose, you want to encrypt the message a = 5. Using A = a e mod n = 533
mod 33 = 125 mod 33 = 26. Hence, the ciphertext A = 26. To decrypt, compute a = Ad
mod n = 267 mod 33 = 5.

Example 4
Encrypt the word PERFECT using p = 43 and q = 59 and e = 13. \
First, generate the keys.
1. Find n = 43 x 59 = 2537.
2. Find φ(n) = (43 -1) (59 - 1) = 2436.
3. Find d = 13−1 mod 2436, d = 97.
So, the encryption key is P (13,2537) and the decryption key is S
(97,2537).
Translating the word PERFECT to numbers yields 15 04 17 05 04 02 19
or 1504 1705 0402 0019. Using a modular calculator, the results are as follows:
a. 1504→1504 mod 2436 = 2008
b. 1705 → 1705 mod 2436 = 865
c. 0402 → 40213 mod 2436 = 2124

d. 0019 → 1913 mod 2436 = 1279

Hence, the encrypted is 200886521241279.
VIGENÈRE CIPHER
Vigenère cipher is a poly-alphabetic substitution system, created by Blaise de
Vigenère. It uses a key (made of letters) and a table by replacing a letter by another
letter, which is not always the same This method uses a 26x26 table with A to Z as the
row heading and column heading. This table is usually referred to as the Vigenère
tableau, Vigenère table or Vigenère square.
 To use this method, use a Vigenère table. The first row of this table has the 26
English letters. Starting with the second row, each row has the letters shifted to the left
one position in a cyclic way. For example, when B is shifted to the first position on the
second row, the letter A moves to the end.The following figure is a Vigenère table.
When using the Vigenère cipher, a keyword is required in addition to the
plaintext. This keyword is repeated so that the total length is equal to that of the
plaintext.
To encrypt, locate the first letter of the plaintext message in the rows of the table
and the first letter of the key on the column. The cipher letter is at the intersection.
To decrypt, take the first letter of the ciphertext and the first letter of the key, and
subtract their value (letters have a value equals to their position in the alphabet starting
from 0). If the result is negative, add 26 (26 = the number of letters in the alphabet); the
result gives the rank of the plain letter.
Example 1
Suppose the plaintext is "I never knew you were the someone waiting for me"
and the keyword is LOVE. Then, the keyword must be repeated as follows:

I N E V E R K N E W Y O U W E R E T H E S O M E O N E W A I T I N G F O R M E
L O V E L O V E L O V E L O V E L O V E L O V E L O V E L O V E L O V E L O V

To use the Vigenère table, in order to cipher a text, take the first letter of the
message and the first letter of the key, and add their value (letters have a value
depending on their rank in the alphabet, starting with 0). The result of the addition
modulo 26 (26 the number of letter in the alphabet) gives the rank of the ciphered letter.
Simply put, the ciphered letter is the intersection of the letter in the plain text (row) and
the key letter (column). For example, the ciphered letter of the intersection of letter I in
the row and letter L in the column is T. This is done for all the letters in the message.
The encrypted message is given below.

I N E V E R K N E W Y O U W E R E T H E S O M E O N E W A I T I N G F O R M E
L O V E L O V E L O V E L O V E L O V E L O V E L O V E L O V E L O V E L O V

T B Z Z P F F E P K U S F K Z V P H C I D C H I Z B Z A L K O M Y U A S C A Z

Example 2
Decrypt the message VCFXTOYHYGUEZL using MINE as key and the
Vigenère cipher
 KEY M I N E M I N E M I N E M I
CIPHER TEXT V C F X T O Y H Y G U E Z L

Take the number equivalent of the first letter V in cipher text as 21 and the
number equivalent of the first letter in the key M as 12. Then, take the difference
21 - 12 = 9. The equivalent letter of 9 is J. Do the same for the other letters in the
cipher text and key. The plain text sent is
JUST HOLD MY HAND
AUTOKEY CIPHER
An autokey cipher, also known as the autoclave cipher, is a cipher which merges
or integrates the message (the plaintext) into the key. The key is then generated from
the message in some automated fashion. The key may be selected letters from the text
or a key may be a short primer key placed in front of the message.
There are two forms of autokey cipher: key autokey and text autokey ciphers. A
key-autokey cipher uses previous members of the keystream to determine the next
element in the keystream. A text-autokey uses the previous message text to determine
the next element in the keystream.
The first autokey cipher was invented by Girolamo Cardano. Another one was
invented in 1564 by Giovan Battista Bellaso using a "reciprocal table" with five
alphabets of his invention. The key was generated by taking the first letter of each word
in the message. The autokey cipher works just like the Vigenère cipher. To encipher a
message, place the keyword above the plaintext. Once all of the key characters have
been written, start writing the plaintext as the key, then append the key. Then, the
Vigenère table is used to determine the cipher text.
To decrypt the message, start by writing down the agreed-on key again. Then,
take the first letter of the key and look at the row in the table. Look across that column
for the first letter of the ciphertext and retrieve the letter to the top. This process
continues for the other letters in the key and corresponding letters in the ciphertext.
Retrieve the equivalent letter in the table. This continues until all letters in the key are
taken into consideration.
Example 1
Use the autokey cipher to encrypt the message WILL NOT GIVE YOU UP THIS
TIME and the keyword is FELL IN LOVE.
PLAIN TEXT W I L L N O T G I V E Y O U U P T H I S T I M E
KEY F E L L I N L O V E W I L L N O T G I V E Y O U
CIPHER TEXT B M T W V B E U D Z A G Z F H D M N Q N X G A Y
The ciphertext is BMTWVBEUDZAGZFHDMQNXGAY.

ERROR DETECTION AND CORRECTION

One of the areas associated with the coding theory 1s error detection and
correction. As mentioned earlier, error-correcting codes are concerned with the
authenticity, safety, correctness, integrity, and reliability of communication over noisy
channels. Whenever a message is transmitted, it may get scrambled by noise or data
may get corrupted even with the best prevention methods. For reliable communication,
errors must be detected and corrected. An error is a condition when the transmitted
information is not the same as the sent information There is a possibility that during the
transmission, the digital signals suffer from noise. The noise can introduce errors in the
binary. Binary digits such as 0 and 1 may be interchanged during transmission and that
will result in errors.

To avoid this, use error-detecting codes which are additional data added to a
given digital message to help you detect if an error occurred during the transmission of
the message. A simple example of error-detecting code is parity check. Parity
checking is the simplest technique for detecting and correcting errors. The data bits
along with the parity bits form a code word.
Error-correcting codes can determine the exact location of the bit that has been
corrupted during transmission.
Along with error-detecting code, you can also pass some data to figure out the
original message from the corrupt message that you received. This type of code is
called an error-correcting code. Error-correcting codes also deploy the same strategy as
error-detecting codes but additionally, such codes also detect the exact location of the
corrupt bit. Parity check has the ability to detect the errors. Once the location of the bit
has been corrupted, the error-correcting code can revert the value from 0 to 1 or from 1
to 0.
A parity bit, otherwise known as check bit, is a bit added to a string of binary
code to ensure that the total number of "1 bits" in the string is even or odd. When a
parity bit is even, it means that the number of1's in the given word including the parity bit
should be even; 2, 4, 6,.and when parity bit is odd, it means that the number of 1's in the
given word including the parity bit should be odd; 1,3, 5, . . .
The parity bit can be set either to 0 or 1 depending on the type of the parity
required during the transmission.
 For even parity, the bit is set to 1 or 0 such that the number of “1 bits” in
the whole word is even. This is shown in the figures below.

Notice in the figure on the left, the number of “1 bits” is 4, which is even, so the
parity is set to 0. The figure on the right, the number of “1 bits” is 3, which is odd,
so the parity is set to 1.
 For odd parity, the bit is also set either 1 or 0 such the number of “1 bits”
in the whole word is odd. This is shown in the following diagram.

Notice in the figure on the left that the number of “1 bits” is 4, which is even. So,
parity is set to 1 to make it odd. For figure on the right, there are 3 “1 bits” so the
parity is set to 0.
When there is a parity check at the receiver. it can determine the presence
of absence o That is, when the expected parity is different from what is supposed
to be parity. For instance, 1t known that the parity of the transmitted signal is odd
but the received signal is even, then the received signal is wrong. If that error is
detected during the transmission, then the receiver will ignore that received byte
and request for another transmission.
The following table shows examples of what happens during the
transmission when the parity is even or odd.
 7 bits of data (count of 1-bits) 8 bits including parity
even odd
0 0 0 10000000
1000001 2 1000001 11000001
1011001 4 1011001 11011001
1110110 5 11110110 1110110

COMPRESSION AND DECOMPRESSION

Most people have downloaded large files, such as music or video, from the
internet. Due to the size of these music or video files, downloading them can take a long
period of time. To solve this problem and make better use of disk space, large files are
compressed using various software. Once downloaded, they can then be
decompressed, and viewed, using a decompression program.
Compression, sometimes known as "packing," refers to the creation of a smaller
file from a larger file (or group of files). For computer enthusiasts, compression is
"storing data in a format that requires less space than usual." Data compression has
been used due to these reasons; large files used less space and smaller files can be
read, uploaded, downloaded, and executed in less time. Decompression, on the other
hand, is the process of restoring compressed data to its original form Decompression is
also known as uncompression.
Compression can either be lossless compression or lossy compression. What is
the difference between these two?
In lossless compression, no data is lost when the file is reduced. In lossy
compression, some data is lost during compression.
There are mathematical formulas called Codecs (compression decompression
algorithms) that are used to compress or decompress files. Several different
compression utilities may use the same codec.
Data decompression is required in almost all cases of compressed data because
compressed data need to be restored back to standard form for these data to be useful.
The following are examples of compression formats and encoding that are used
when data are sent through communication media or saved in a storage device.
 JPEG – JPEG stands for Joint Photographic Experts Group, the original
name of the committee that wrote the standard. JPEG uses lossy
compression to remove redundant visual data. JPEG files usually end with
 the jpeg or jpg extension. JPEG is a standardized compression
mechanism for images (pictures).
 MPEG – MPEG is short for Moving Pictures Expert Group. MPEG is
actually used to refer to several standards for various types of files,
including video (MPEG) and audio (MPEG Layer 3, or MP3).
 Zip/Tar – Zip and Tar files use lossless compression to remove redundant
data from a file. Files that have been zipped or tarred must be unzipped or
untarred before they can be read. Extensions are .zip and .tar
respectively.
 Hex – BinHex is a format which is used to both encode and compress
files. This format is most popular on the Macintosh although there are
programs on other platforms that can read it. Eudora on any platform can
read these files. BinHex files end with the .hqx extension.

THE UNIVERSAL PRODUCT CODES

Every time you buy something from a department store, grocery, or
supermarkets, you see a series of thick and thin lines with numbers at the bottom
printed on an item, like the picture on the right. They are commonly referred to as
barcodes but they are actually called UPCs.
A UPC, short for universal product code, is a type of code printed on retail
product packaging to aid in identifying a particular item. It consists of two parts - the
machine-readable barcode, which is a series of unique black bars (lines), and the
unique 12-digit number beneath it.
Barcodes are very common as soon as point-of-sale systems have been
developed. These codes are very helpful to keep track of inventory especially in
groceries, supermarkets, and department stores. Managers and inventory clerks find it
very easy to determine which items are out-of-stock and which items are saleable.
Bar codes are not just used in groceries, supermarkets, and department stores.
The use of barcodes cannot be overemphasized. Airline crews can easily determine the
passenger who has booked for a flight but has not showed up for boarding. Pieces of
baggage can easily be scanned and transported to their final destinations at airports.
Admission tickets in movie theaters, concerts, or games can easily be identified and
verified for their validity using these bar codes.
Libraries make use of these bar codes for the ISBN or book control numbers.
They can mediately note books and other printed materials that are loaned to people.
Librarians can easily keep track of library materials.
For products and trade items, the purpose of the UPC is to make it easy to
identity product features, such as the brand name, item, size, and color, when an item is
scanned at checkout. A company that is interested to use barcodes for their products
needs to apply to be a part of the system. GS1 US, the Global Standards Organization,
formerly known as the Uniform Code Council, is the agency that manages the assigning
of UPCs within the US. GS1 assigns a 6-digit manufacturer's identification number once
the company or a person has paid the joining fee.
In a 12-digit UPC, the first 6 identifies the particular manufacturer of the product
or trade item. The next five-digits of the UPC is called the item number. It refers to the
actual product itself.
There are many variations for many consumer products based on, for example,
size, flavor, or color. Each variety requires its own item number. For instance, a box of
chocolate for 25 grams will have a barcode different from a box of chocolate of the
same brand for 50 grams.
These figures are two of the UPCs used today.

EAN-133
 There are 13 digits in the code (figure on the right). The first number represents
the country, the next 6 digits represent the manufacturer, the next 5 digits
represent the product, and the last digit is the check digit.

UPC-A

 There are 12 digits in the code (figure on the left). The first digit is the type of
product. The next 5 digits represent the manufacturer, the next 5 digits represent
the size, color, and made of the product, and the last number is the check digit.
The numbers in the type of products determine what kind of product the
merchandise is. The following table shows the distribution.

0, 1, 7, 9 Any
2 Food by weight
3 Drugs, pharmacy, health
4 Sale items
5 Special offers/coupons
 The last digit in the 12-digit UPC is called the check digit. It is the product of
several calculations adding and multiplying several digits in the code-to confirm to the
checkout scanner that the UPC is valid. If the check digit code is incorrect, the UPC will
not scan properly. The check digit in barcode is a form of redundancy check used for
error detection. It consists of a single digit computed from the other digits in the
message. These check digits can be seen in many items that you see every day to help
detect forgery or errors, Items like driver's licenses, money orders, airline tickets, visas,
movie tickets, and UPCs on merchandise. A check digit is formed on an algorithm that
uses modular arithmetic, then is added to the end of the identification number.
Notice that a bar code encodes a sequence of digits (or letters) as a series of
light and dark bars. The bars act like bits in a binary encoding-the presence of a bar is
equivalent to a "l", and the absence of a bar is equivalent to a "0." So, for each digit, a
short bit string is chosen to represent that digit. The bar code is simply these bit strings
put together and converted into bars. Two (or more) active bits next to each other
correspond to a wider bar, not two bars next to each other.
When a bar code scanner scans a bar code, it sends a signal over the bar code
and measures the intensity of the light reflected back. A low reflection is a bar, a high
reflection is a gap. So, when it scans a barcode with a bit pattern of "10110101" what it
sees might be (depending on scanning speed) a dark bar 20ms wide, a gap of 20ms, a
dark bar of 40ms, a gap of 20ms, a bar of 20ms, a gap of 20ms, and finally a bar of
20ms. From this, it can be deduced that the bit-length is 20ms which reconstructs the
code.
In order to form a reliable bar code, some rules have to be followed:
1. The digits have to have sufficient light-dark transitions, which means that every
digit has to have at least one "on" bit and one "off" bit. This means that the standard
Binary Coded Decimal encoding (which has "0000" for 0) won't work, but a 2-in-S
encoding (each digit 1s represented by 2 on bits and 3 off bits, and there are 10
combinations of 5 bits which meet that), might. The idea here is that with sufficient
transitions, the scanner can "self-clock and figure out the bit boundaries, even in wide
bars, regardless of the scanning speed,
2. The encodings should not be translationally similar, so that it is possible to
detect the beginnings of a digit. Keeping in mind that a scanner cannot actually see a
gap, a barcode scanner could not distinguish between "011010101" and "110101010,"
so it would be best those two were not both valid codes.
3. If possible, the encodings should not be reversible, i.e., it should not be
possible to have two barcodes which are mirror images of each other. The scanner
often scans the code both forward and backwards, and needs to be able to tell which
direction is correct. If both lead to valid codes, that is a problem.
 4. It is not always easy or convenient to meet those goals, so there are tricks
used to relax them. For instance, many barcode standards include "guard bars," which
is a bit pattern added to the beginning and end of an encoding (like "11010....01101")
which ensures that the scanner can easily pick up the beginning and end of the
encoding and can get good clocking. With the guard bars listed, the 2-in-5 encoding
would probably work.
5. Universal Product Codes (UPC) meet these requirements by having two
different 7-bit encodings for each character, each encoding having 2 bars and 2 gaps.
The left half of the UPC uses encodings of the form "Oxxxxx1," each of which has either
2 or 4 of the “x" as 1's such that there is two bars and two gaps, and the right half of the
UPC uses the inverse encodings (i.e., "1xxxxx0,"2 or 4 of the "x" are 0, two bars, two
gaps) with 0 being encoded as "0001101" on the left and "1110010 on the right, and so
on. It also has a "quiet zone" before and after the encoding with no bars, guard bars on
either side of the form "101." and a middle set of guard bars of the form "01010.
Because of these design choices, the scanner gets enough transitions to self-clock; it
can find the beginning and end of the digits easily: and it can tell if it is reading forward
or backward.

ISBN
Modern books published worldwide are identified by a string of digits knows as
International Standard Book Number, or ISBN. In was in 1970 when the ISBN was
used. The ISBN of a book is usually found on the last cover page. It appears as a string
of ten digits (ISBN-10, assigned before 2007) or thirteen digits (ISBN-13) assigned after
January 2007. An ISBN is assigned to each additional edition and variation (except
reprints) of a book.
The first digit, which is called the leading digit, means that the book is published
in the English- speaking countries (the U.K, the United States, Australia, New Zealand,
and Canada). The next group of digits, 619, identifies the publisher. The third set of
digits, is the number assigned to the book by the publisher. The last digit is the check
digit.

THE MATHEMATICS BEHIND THE UPC

 The original UPC code is also known as UPC-A or UCC-12, the latter to indicate
its 12-digit size. (UCC is an abbreviation for the Uniform Code Council, a not-for-profit
organization responsible in part for the issuance of the UPC codes).
The twelve UPC-A digits are comprised of three groups: a 6-digit company prefix
(assigned by the UCC to a specific manufacturer), a 5-digit product code (assigned by a
responsible person within the company), and 1 check digit (calculated according to an
algorithm discussed next).
Assume the 12 digits are d 1, d 2, d 3,… d 11, d 12. In a valid UPC barcode, d 12 is so
selected as to make the following identity true:
(1) 3 x d 1+ d 2+d 3+ d 4 +…+ 3 x d 11 + d 12 = 0 (mod 10)

If you let Sodd be the sum of the digits in the odd positions and Seven be the sum of
the digits in the even positions, then

3 x Sodd + Seven = 0 (mod 10). 3 x Sodd + Seven = 0 (mod 10).

In other words, the total must be divisible by 10. If that is so, it is a valid UPC.
For a 13-digit EAN code d 1, d 2, d 3,… d 11, d 12, C, is valid if this identity is true.

(2) d 1+ 3d 2+d 3+ 3d 4 +…+ d 11 + 3d 12 = 0 (mod 10)

For the ISBN-10, suppose the first nine digits x 1, x n, x 3… x 9 have been chosen. The
check digit x 1 0, which is one of 0, 1, 2, 3,….,9, X, is determined by the following
congruence:
1 x 1 + 2 x x ,+…8 x 8,+ 9 x 9, + 10 x 10 ≡ 0 mod 11
That is,
1 x 1 + 2 x x ,+…8 x 8,+ 9 x 9, + 10 x 10 + x 10 ≡ x 10 mod 11
Or
1 x 1 + 2 x x ,+…8 x 8,+ 9 x 9, + 11 x 1 0 ≡ x 10 mod 11
Or
1 x 1 + 2 x x ,+…8 x 8,+ 9 x 9 ≡ x 10 mod 11 because 11 = 0 mod (11).

Example 1
The first 9 digits of a book are 0-619-06213. Find the check digit.
 Solution: The check digit is determined by the congruence
1∙ 0 + 2∙6 + 3 ∙ 1 + 4 ∙ 9 + 5 ∙ 0 + 6 ∙ 6 + 7 ∙ 2 + 8 ∙ 1 + 9 ∙ 3 ≡ x 10 mod 11

i.e., 136≡ x 10 (mod 11). Now, 136 ≡ 12 ∙ 11 + 4 = 132 + 4.

Thus, write 136≡ x 10 (mod 11) as 132 + 4 ≡ x 10 (mod 11). This implies that 4≡ x 10
(mod 11).
Because 0 ≤ x 10 ≤ x10 ≤ 11, it follows that x 10 = 4. Hence, the check digit for the
ISBN of this book is 4.

Example 2
Determine if this UPC is a valid code: 6-44209-42095-7.
Solution: Using the modular arithmetic above, you will get
(3 x 6) + 4 + (3 x 4) + 2 (3 x 0) + 9 + (3 x 4) + 2 + (3 x 0) + 9 + (3 x 5) + 7 = 0 (mod 10)
18 + 4 + 12 + 2 + 9 + 12 + 2 + 9 + 15 + 7 = 0 (mod 10)
90 = 0 (mod 10)
Hence, 6-44209-42095-7 is valid UPC.

Example 3
Determine if the UPC 0-51000-01252-5 is valid code:
Solution: Using modular arithmetic yields
(3 x 0) + 5 + (3 x 1) + 0 + (3 x 0) + 0 + (3 x 0) + 1 + (3 x 2) + 5 + (3 x 1) + 7= 0 (mod 10)
0 + 5 + 3 + 0 + 0 + 0 + 0 + 1 + 6 + 5 + 3 + 5 = 0 (mod 10)
28 = 0 (mod 10)
Hence, 0-51000-01252-5 is NOT a valid UPC.

Example 4
Find the check digit to make UPC 8 9 0 4 0 0 0 2 1 0 0 3 C (check digit position)
valid.
Solution: Perform the following calculations.
 1. Starting with the first number on the right, add all the alternate
numbers: 3 + 0 + 2 + 0 + 4 + 9 = 18
2. Multiply the result by three:18 x 3 = 54
3. Starting with the second number on the right, add all alternate
numbers: 0 + 1 + 0 + 0 + 0 + 8 = 9
4. Add the results of steps two and three: 54 + 9 = 63
5. Add the number needed to bring the total to the next multiple of 10:
63 + 7 = 70
The number which is needed to add to make it the next multiple of 10 is
the check digit. So, the check digit here is 7. The complete valid number should be 890
4000 21003 7.

Example 5
Suppose that you want to find the check digit of UPC-A number 72641217542.
1. From the right to left, start with odd position and assign the odd/even position
to each digit.
2. Sum all digits in odd position and multiply the result by 3:
(7+6+1+1+5+2) x 3 = 66
3. Sum all digits in even position: (2 + 4 + 2 + 7 + 4) = 19
4. Sum the results of steps three and four: 66 + 19 = 85
5. Divide the result of step four by 10. The check digit is the number which adds
the remainder to 10. In this case, divide 85 by 10 to get the remainder 5. The
check digit then is the result of 10 – 5 = 5. If there is no remainder, then the
check digit equals zero.

SUMMARY
One of the most important key technologies for digital communication systems as
well as storage media is coding theory. It provides a means to transmit information
across time and space over noisy and unreliable communication channels. Although its
roots lie in information theory, the applications of coding theory now extend to statistics,
cryptography, and many areas of pure mathematics.
Coding theory is the study of the properties of codes and their respective fitness
for specific applications. Codes are used for data compression, cryptography, and data
transmission and storage. Codes are studied by various scientific disciplines – such as
information theory, electrical engineering, mathematics, linguistics and computer
science – for the purpose of designing efficient and reliable data transmission methods.
This typically involves the removal of redundancy and the correction or detection of
errors in the transmitted data.
 The term “coding” is basically associated with three areas. These are:
1. Data Compression: It is concerned with the efficient encoding of source
information so that it takes as little space as possible.
2. Error-correcting Codes: They are concerned with the authenticity, safety
correctness, integrity, and reliability of communication over noisy channels.
3. Cryptography (or Cryptology): It is concerned with security, privacy, or
confidentiality of communication over an insecure channel.

The advent of technology and communication made it possible to send

information via different communications media. These pieces of information are
susceptible to errors and theft especially data on profiles, credit cards numbers, and
other private information. Cryptology, which is the study of secret codes makes it
possible for data and information sent in different media to be protected from the
prying eyes of unscrupulous people and not-intended recipients.
The Caesar cipher, also known as a shift cipher, is one of the oldest and simplest
forms of encrypting a message. It is a type of substitution cipher where each letter in
the original message (called the plaintext) is replaced with a letter corresponding to
a certain number of letters shifted up or down in the alphabet.
The transposition cipher is a method of encryption by which the positions held
by units of plaintext (which are commonly characters or groups of characters) are
shifted according to a regular system, so that the ciphertext constitutes a
permutation of the plaintext. That is, the order of the units is changed (the plaintext is
recorded).
The Vigenère cipher uses a 26x26 table with A to Z as the row heading and
column heading. This table is usually referred to as the Vigenère tableau, Vigenère
table, or Vigenère square. The first row of this table has the 26 English letters.
Starting with the second row, each row, has the letters shifted to the left one position
in a cyclic way. This table is used to determine the letter for the cipher text
equivalent to the intersection of the letter in the plaintext and the letter in the key.
The autokey cipher is an extension to the Vigenere cipher that makes it much
harder to break. Instead of repeating the passphrase over in order to encrypt the
text, the passphrase is used once and the cleartext is used to decrypt and encrypt
the text.
The RSA is an asymmetric algorithm for public key cryptography created by Ron
Rivest, Adi Shamir and Len Adleman. It is the most used data exchange over the
internet and a more difficult type of encryption to break.
Data Compression, also called compaction, is the process of reducing the
amount of data needed for the storage or transmission of a given piece of
 information, typically by the use of encoding techniques. Uploading and downloading
music and video files, due to their large size, take a long period of time to execute.
With compression and decompression, the large files can be uploaded and
downloaded in a faster time frame. Compression also helps lessen the storage
spaces required for very large files.
The universal product code (UPC) is a 12-digit number or 13-digit number and
associated machine-readable bar code used to identify products and trades being
purchased. The check digit in barcode is a form of redundancy check used for error
detection. Error detection is part of coding theory. It consists of a single digit
computed from the other digits in the message. These check digits can be in many
items that you see every day to help detect forgery or errors.

5. Teaching and Learning Activities

1. Encrypt the message YOU LOOK PERFECT TONIGHT by translating the letters
into numbers and applying the function specified. Then, translate back into
letters.
a. f ( p ) =( p+ 3 ) mod 26(Caesar Ciper)

2. Encrypt the message CONGRATULATIONS by changing the letters into its

equivalent number. Then, change the numbers using the encryption
f ( p ) =( p+ 5 ) mod 26.

3. Use the following substitution mapping for the following encryption and
decryption.

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9
M Y 5 V 0 Z N B K W T L 0 6 S 4 3 G H X 7 I J 1 R U C 8 E 9 F P D Q 4 A

ORIGINAL: ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789
MAPS TO: MYSVOZNBKWTL206S43GHX71JIRUC8E9FPDQ4A

a. Encrypt the message I FOUND A LOVE FOR ME.

b. Decrypt the message K BM70 4MKXS KG JBMX K H00
c. Decrypt the message LSI0 5BM6NOH XBO JSGLV.
 4. Using a mapping to an alphanumeric mapping of an original message
ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789, encrypt the following
messages using an alphanumeric Caesar cipher with shift 16 (mapping A to Q).

a. YOU LOOK PERFECT TONIGHT

b. SEE YOU IN THE PARK AFTER CLASS

5. What is the encrypted message if the original message is “SILVER” using the
RSA system with p = 43, q = 59, and e = 13.

6. Use the Vigenère cipher to encrypt the following messages:

a. BE GENTLE WITH MY HEART using EMOTE as key.

b. I WILL BE YOUR MAN using MAN as key.

7. Use the Vigenère cipher to decrypt the following messages:

a. MEDSEIIS WAQBDWHCE with the key LADY

b.
Plain text
Key T E S Y E S Y E
Cipher M J U M Y J Q I
text

8. Use the autokey cipher to encrypt the messages in #6 a-b.

9. Determine if the following numbers are VALID UPCs manually. Then, check your
result using the UPC Check Digit Calculator online.

a. 245501225419
b. 940122541 725
c. 9401254501725

6. Recommended learning materials and resources for supplementary reading.

Cryptography: https://youtu.be/-yFZGF8FHSg
Substitution Cipher: https://youtu.be/bKbc5ICEu1E
https://youtu.be/1P8Xpxm76e8
 Transposition Cipher: https://youtu.be/sHsnH1u03e4
https://youtu.be/bcyUJK1BvHw
https://youtu.be/0um-_4SvPg0
RSA Public Key: https://youtu.be/wXB-V_Keiu8
https://youtu.be/4zahvcJ9glg
https://youtu.be/oOcTVTpUsPQ
Autokey Cipher: https://youtu.be/noWh1lMbx34
Universal Product Code: https://youtu.be/tw7lFmA3iH8
https://youtu.be/T1QMouEF1JM
https://youtu.be/4C3uwfoR88c
https://youtu.be/lCFI-kRWOOw
ISBN: https://youtu.be/5qcrDnJg-98
https://youtu.be/WstjjL5CPqk
https://youtu.be/ZFFa3sq305E

7. Flexible Teaching Learning Modality (FTLM) adopted

Example:
Online (synchronous)
//Zoom
Remote (asynchronous)
//module, exercises, problems sets, youtube

8. Assessment Task
1. Find the value of the check digit for each set of numbers manually. Then, check your
result using the UPC Check Calculator online.
a. 54236211146C
b. 02622946010C
2. Do a research on quick response codes. Then, present your findings through written
output.
3. Do a research on the role of information theory in the field of compression and
decompression. Summarize the results and make a one-page essay on your findings.
4. Do a research on the other codes SCC-14, GTIN, SSCC-18, EAN-8, and ISBN. Then,
present your findings through written output.
5. Do a research on cipher methods not covered in this text like Affine cipher, Atbash
cipher, Mixed alphabet cipher, and Pigpen cipher. Give your own examples on how to
apply each method. Present it through written output.

9. References (at least 3 references preferably copyrighted within the last 5 years,
alphabetically arranged)

Calingasan,M. (2018). Mathematics in the Modern World. C & E Publishing , Inc.

Hathaway, D. (2011). Mathematics for the modern world (3 rd ed.) Boston, MA: Pearson
Learning Solutions.
Maniti, G. III (2019). Mathematics in the Modern World-Mathematics in our World.

What is a MODULE?
It refers to an instructional unit that focuses on a particular topic. It includes
information about the topic, focuses on student – centered learning activities and
culminate in an output for students, uses active rather than passive learning
experiences, thus students, may be more engaged, understand real-world.

Learning Resources
Key readings and other learning materials for students to study, to learn the key
concepts covered in the module.
Learning resources are texts, videos, software, and other materials that the
teacher use to assist students to meet the expectations for learning.
ISUE__ __ Syl ___
Revision: 02
Effectivity: August 1, 2020