COMPUTER SECURITY

1
CoSc4171
CHAPTER TWO

Basic Cryptography

2
 DEFINITION OF CRYPTOGRAPHY
 The word cryptography describes
 comes from Greek meaning “secret writing.”
 the art of secret communication,
 Mathematical techniques related to information security

 Cryptography enables you to store sensitive

information or transmit it across insecure networks so
that it cannot be read by anyone except the intended
3
recipient.
CONT’D….
 Cryptography is the study of mathematical techniques
related to the aspects of information security, such as
confidentially, data integrity and entity authentication.
 Cryptography is the science of using mathematics to
encrypt and decrypt data.

4
CONT’D….
 Which of the following activities can cryptography not be used
to provide in the electronic world?
 Ensuring that only an intended recipient can obtain some
information
 Ensuring that information cannot be altered before it reaches an
intended recipient
 Ensuring that a sender of some information cannot later deny having
sent the information
 Ensuring that some received information was sent by the claimed
5
sender
 HISTORICAL REMARKS
History – The Manual Era
 Dates back to at least 2000 B.C.
 Pen and Paper Cryptography

 Examples
 Scytale: Spartan method involved wrapping a belt around a rod of a
given diameter and length.
 Atbash: Hebrew cipher which mirrored the normal alphabet
 Caesar: The first substitution ciphering algorithm is also believed to
date back to this period.
 Vigenère: Use of a key and multiple alphabets to hide repeated 6

characters in an encrypted message

CONT’D…
History – The Mechanical Era
 Invention of cipher machines
 Examples
 Confederate Army’s Cipher Disk
 Japanese Red and Purple Machines
 During the industrial age, cryptography was moved from a manual
exercise to one done by machines.
 The invention of cipher disks and rotors for this use allowed for the
creation of much more complex algorithms. 7
CONT’D
History – The Modern Era
 Computers!
 Examples
 Lucifer
 Rijndael
 RSA
 ElGamal

 Modern computing gave cryptographers vast resources for

improving the complexity of cryptosystems as well as for 8

attacking them
BASIC TERMS
 Plain text : Original Message
 Cipher text:-Coded Message.
 Encryption:-The process of converting plain text into cipher text.
 Decryption:-Restoring plain text from cipher text.
 Key – Sequence that controls the operation and behavior of the
cryptographic algorithm
 information used in cipher, known only to sender/receiver
 Key-space – Total number of possible values of keys in a crypto
algorithm 9
CONT’D..

 Cryptanalysis: the science of analysis or breaking of secure

communication.
 The art of defeating cryptographic security systems, and gaining
access to the contents of encrypted messages, without being given
the cryptographic key.
 The study of methods for obtaining the meaning of encrypted
information without accessing the secret information

 Cryptology: The area of cryptography and cryptanalysis

together
10
GOALS OF CRYPTOGRAPHY

 Confidentially:
 Only authorized entities are allowed to view

 only sender, intended receiver should “understand” message

contents

 Data Integrity:
 Ensures the message was not altered by unauthorized individuals

 sender, receiver want to ensure message not altered (in transit, or

afterwards) without detection 11

 Authentication:
 Validates the source of a message, to ensure the sender is

properly identified

 sender, receiver want to confirm identity of each other

 Non-repudiation:
 Establishes sender identity so that the entity cannot deny

having sent the message

 An entity is prevented from denying its previous

12

commitments or actions
TAXONOMY OF
CRYPTOGRAPHY

13
SYMMETRIC ENCRYPTION:

 Mathematically:
Y = EK(X) or Y = E(K, X)
o E = encryption algorithm
X = DK(Y) or X = D(K, Y)
o D = decryption algorithm
o X = plaintext
o Y = ciphertext
o Both E and D are known

o K = secret key to public

Algorithms for encryption/decryption are known to the public.

Keys used are kept secret.
14
PUBLIC KEY ENCRYPTION
 Public key encryption or asymmetric encryption uses two different
keys
 A public key known by all and
 A private key known by only the sender and the receiver.

 Both the sender and the receiver own a pair of keys, one public and
the other a closely guarded private one.
 To encrypt a message from sender A to receiver B, both A and B
must create their own pairs of keys.
 Then A and B publicize their public keys – anybody can acquire
15
them.
CONT’D…
 When A is to send a message M to B, A uses B’s public key to
encrypt M.
 On receipt of M, B then uses his or her private key to decrypt
the message M.
 As long as only B, the recipient, has access to the private key,
then A, the sender, is assured that only B, the recipient, can
decrypt the message.

16
SYMMETRIC CRYPTOGRAPHY
SHIFT CIPHER
Definition:

Characteristics:
 Easy to break because only 25 possible keys!!!!
 Encryption and decryption algorithms are known
 25 possible keys only
17
 Language of plain text is known and easily recognizable
CONT’D…
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

Example:
 Suppose that the key for the shift cipher is k=17 and let the
corresponding cipher text is "RKKRTB". What is the
corresponding plaintext?
 Answer: Attack

 Example: Suppose that the key for the shift cipher is K=11 and let
the plaintext be “we will meet at midnight”. Compute the cipher text.
18
Exercise:

Decode the message LTYTUFWNX using Shift cipher

with shit k = 5. What does the message says?

19
 AFFINE CIPHER
 In affine ciphers, the key used for encipherment
involves using both a multiplicative and additive
parameter.
 Before describing affine ciphers, we give some
necessary mathematics background.
 The greatest common divisor of two natural numbers a and
b, denoted as gcd(a,b), is the largest natural number that
divides a and b with no remainder.
 A natural number p is said to be prime if p>1 and its only
20
divisors are 1 and p.
AFFINE CIPHER

 Definition Affine Cipher

21
 Example: suppose the key of the message are [7,3], then

encipher the message “HOT”?

ek(x)=ax+b mod26

ek(x)=7x + 3 mod26

So H=7; O = 14; and then T = 19;

Therefore; ek(7)=7x7+3 mod26 = 52 mod26 = 0

ek(14)=7x14 mod26 = 101 mod26 =23

ek(19)=7x19 mod26 =136 mod26 = 6 `

:Then the encipher text is AXG 22

Example 15: Decipher the message “ARMMVKARER” that was
encrypted using the affine cipher y=(3x + 5) mod26.
 First we have to change the enciphered functions into decipher

d(y) = a-1(y-b) mod26 ------a=3 and b=5

d(y) = 9(y-5) mod26
d(A)=9(0-5) mod26 = -45 mod26 =-19 = 7
d(R) =9(17-5) mod26 = 108 mod26 = 4
d(M) =9(12-5)mod26 =63 mod26 =11
d(V) =9(21-5) mod26 =144 mod26 =14
d(K) =9(10-5) mod26 =45 mod26 =19
d(E) =9(4-5) mod26 =-9 mod26 =-9 =17
The plain text of “ARMMVKARER” is Hello There
23
Exercise:
Let E(x) = 5x+14(mod26) be an encryption mapping
for an affine cipher. If the cipher-text OTOE is
produced, what is the corresponding plaintext?

Find the keys of affine cypher based on the equation

e(4) =17 and e(19)=3?
24
THE VIGENERE CIPHER -- A POLYALPHABETIC CIPHER

 A polyalphabetic substitution cipher involves the use of two or more cipher

alphabets.
 Instead of there being a one-to-one relationship between each letter and its
substitute, there is a one-to-many relationship between each letter and its
substitutes.

25
26
27
Exercise:
Suppose a Vigenere cipher uses code as the keyword.
Decrypt the cipher-text NAIU.

28
PERMUTATION CIPHER OR TRANSPOSITION
 Permutations are functions which are often used in various
cryptographic constructs.
 Definition Let S be a finite set of elements. A permutation on
S is a bijection from S to itself (i.e., )

29
PERMUTATION CIPHER OR TRANSPOSITION

30
PERMUTATION CIPHER

Suppose we are given the plaintext as SHESELLSSEASHELLS

BYTHESEASHORE, then encipher this plain text?
Solution: first we have to find phi inverse. To find phi inverse first If a
permutation is written as an array, its inverse is easily found by
interchanging the rows in the array and reordering the elements in the new
top row if desired (the bottom row would have to be reordered
correspondingly).
31
 Where the top row in the above array is the domain and the
bottom row is the image under the mapping.
 Since permutations are bijection, they have inverses.

 p(1)=3; p(2)=5; p(3)=1; p(4)=6; p(5)=4; p(6)=2

 Here we have to change the raw

x 3 5 1 6 4 2
(X) 1 2 3 4 5 6

 Then p(3)=1; p(5)=2; p(1)=3; p(6)=4; p(4)=5; p(2)=6

x 1 2 3 4 5 6
X-1 3 6 1 5 2 4

32
SHESEL-LSSEAS-HELLSB-YTHESE-ASHORE
x 1 2 3 4 5 6
X- 3 6 1 5 2 4
 p(3)=1; p(5)=2; p(1)=3; p(6)=4; p(4)=5; p(2)=6
 Therefore; the enciphered text or cypher-text is

EESLSH-SALSES-LSHBLE-HSYEET-HRAEOS

33
HILL CIPHER
 Hill's major contribution was the use of mathematics to design
and analyse cryptosystems.
 It is important to note that the analysis of this algorithm
requires a branch of mathematics known as 'number theory'.

34
Example: Suppose the key is
11 8
K= 3 7

And we want to encrypt the plain text july.

Here the combination (9, 20) and (11, 24)

7 18
K-1 = 23 11 used for decryption

11 8
(9, 20) 3 7 = (99+60, 72+140) = (3, 4)

11 8
(11, 24) 3 7 = (171+72, 88+168) = (11, 22) 35
The encryption of july is DELW
PLAY FAIR CIPHER
 a cipher that encrypts two letters at a time so that the result depends on both
letters.
 Often today polygraphic ciphers are called block ciphers because they
encrypt blocks of plaintext with blocks of ciphertext.
 The technique encrypts pairs of letters (digraphs), instead of single letters
as in the simple substitution cipher
 Create a 5 x 5 matrix using some keyword with no repeating letters
except I & J,
 After entering the keyword, the remaining letters of the alphabet are
entered in order.
36
ONE-TIME PAD
 It's a very simple system and is unbreakable if used correctly.
 To use a one-time pad, you need 2 copies of the "pad" which is a block of
random data equal in length to the message you wish to encode
 The pad is used by XORing every bit of the pad with every bit of the original
message.
 The algorithm:
 Print up a series of random numbers on a pad.
 Make a copy.
 Give one to your correspondent.
 Each bit of plaintext is XOR’d with the key.
37
 As you use each bit of the key, cross it out off the pad.
 When you are done with a page, tear it off.
ONE-TIME PAD
 Some key points to remember are:
 Your key MUST be as long as your plaintext
 Your key MUST NOT be reused
 Your key MUST be random (not pseudorandom and PLEASE not a WORD!!)
 The key MUST be exchanged over an existing secure channel

38
DATA ENCRYPTION STANDARD (DES)
• The Data Encryption Standard, known as DES, is a simple block
cipher developed way back in the 1970s.
• The design is based on the Lucifer cipher, a Feistel cipher
developed by IBM.
• To summarize,
o DES is a feistel cipher with 16 rounds;
o DES has a 64-bit block length;
o DES uses a 56-bit key;
o each round of DES uses a 48-bit subkey and each subkey consists of a
48-bit 39

o subset of the 56-bit key.

DATA ENCRYPTION STANDARD (DES)
• DES operates on two inputs to the encryption function: a 64-bit
block of plaintext to be encrypted and the 56-bit key k.
• Note: Actually, the function expects a 64-bit key as input. However,
only 56 of these bits are ever used; the other 8 bits can be used as
parity bits or simply set arbitrarily.

40
ADVANCED ENCRYPTION STANDARDS (AES)
• The Advanced Encryption Standard (AES) is a specification for the
encryption of data established by the U.S. National Institute of Standards and
Technology (NIST) in 2001.
• In AES, an algorithm known as Rijndael algorithm was ultimately selected.
• AES has been adopted by the U.S. government and is now used worldwide.
• It is a symmetric-key algorithm that supersedes DES.
• Like DES, the AES is an iterated block cipher.
• Unlike DES, the AES algorithm is not a feistel cipher.
• The major implication of this is that, in order to decrypt, the AES operations
must be invertible. 41

• Unlike DES, the AES algorithm has a highly mathematical structure.

ADVANCED ENCRYPTION STANDARDS (AES)
• AES is a non-Feistel symmetric block cipher that encrypt and decrypt a data

block size of 128 bits.

• Key lengths can be 128 bits, 192 bits, or 256 bits; called AES-128, AES-192,

and AES-256, respectively.

• AES-128 uses 10 rounds, AES-192 uses 12 rounds, and AES-256 uses 14

rounds.
• However, the round key, which are generated by the key expansion

algorithm are always 128 bits, the same size as plaintext or ciphertext blocks.

42
PUBLIC-KEY ENCRYPTION
• In traditional (symmetric-key) cryptography, the sender and receiver of a
message know and use the same secret key.

• The main challenge is getting the sender and receiver to agree on the secret
key without anyone else finding out.

• If they are in separate physical locations, they must trust a courier, a phone
system, or some other transmission medium to prevent the disclosure of the
secret key.

• Anyone who overhears or intercepts the key in transit can later read, modify,
and forge all messages encrypted or authenticated using that key. 43
PUBLIC-KEY ENCRYPTION
• Because all keys in a secret-key (symmetric-key) cryptosystem must remain

secret, secret-key cryptography often has difficulty providing secure key

management.

• Public-key cryptography refers to a cryptographic system requiring two separate

keys, one of which is secret and one of which is public.

• Although different, the two parts of the key pair are mathematically linked.
PUBLIC-KEY ENCRYPTION
• The algorithms used for public key cryptography are based on
mathematical relationships (the ones being the integer factorization
and discrete logarithm).

• Although it is easy for the recipient to generate the public and

private keys, to decrypt the message using the private key, and easy
for the sender to encrypt the message using the public key, it is
extremely difficult for anyone to derive the private key, based only
on their knowledge of the public key.
PUBLIC-KEY ENCRYPTION

• This is why, unlike symmetric key algorithms, a public key

algorithm does not require a secure initial exchange of one (or

more) secret keys between the sender and receiver.

• Public-key cryptography is a fundamental, important, and widely

used technology.

• It is an approach used by many cryptographic algorithms and

cryptosystems.
PUBLIC-KEY ENCRYPTION
• Public-key cryptoghphic algorithms have three primary uses:
i. encryption ii. Key distribution and ii. digital signatures.
• i. Encryption: This is a technique to encrypt a message with a recipient's public
key that cannot be decrypted by anyone except a possessor of the matching
private key.
• ii. Digital signatures: This is a technique for signing a message using a sender's
private key that can be verified by anyone who has access to the sender's public
key, thereby proving that the sender had access to the private key and, therefore,
is likely to be the person associated with the public key used.
• iii. Key distribution: This is a technique for the distribution of the public key and
the private keys among the users.
PUBLIC-KEY ENCRYPTION
• Examples of well-regarded asymmetric key techniques for varied purposes
include:
• Diffie–Hellman key exchange protocol
• ElGamal
• DSS (Digital Signature Standard), which incorporates the Digital Signature
Algorithm
• Various elliptic curve techniques
• Various password-authenticated key agreement techniques
• RSA encryption algorithm
• Cramer–Shoup cryptosystem
• YAK authenticated key agreement protocol
 ይቀጥላል ….
“ለደህንነታችን ጥንቃቄ እናድርግ”

49