Course Name: Cryptography and

Cyber Security
Course Code: 22CSE163
Module 2:
Modern Cryptography
Dr. Deepak D J
Associate Professor
Dept. of CSE, BNMIT
Introduction to Cryptography
• The study of mathematical techniques for securing digital
information, systems, and distributed computations against
adversarial attacks.
• Ex: mechanisms for ensuring integrity, techniques for exchanging
secret keys, protocols for authenticating users, electronic auctions
and elections, digital cash, and more.
• Classical: Security through obscurity
• Modern : The security is not based on the secrecy of the protocol
details but based on sound mathematical and computational
principles.
 Classical Vs Modern Cryptography
• Classical cryptography was • Modern cryptography is influences
restricted to military. almost everyone.
• Modern cryptography breaks out of
• Classical cryptography was mostly the “design-break-design” cycle
about secret communication. model of classical cryptography.
• The communication is secure as • The security is not based on the
long as the encoding algorithm is secrecy of the protocol details but
a secret. based on sound mathematical and
computational principles.
• Disadvantages: Reverse • Provable security: mathematically
engineering, coding algorithm demonstrate that a cryptographic
leaks. system is secure against a specific set
of attacks.
Keys and Kerckhoffs’ principle.
• “The cipher method must not be required to be secret, and it must be able
to fall into the hands of the enemy without inconvenience”.
• Kerckhoffs’ principle demands that security rely solely on secrecy of the
key. – cryptographic designs must be made completely public.
• It is simply unrealistic to assume that the encryption algorithm will
remain secret.
• Easier to change a key than to replace an encryption scheme.
• Easier for users to all rely on the same encryption algorithm/software (with
different keys) than for everyone to use their own custom algorithm.
• “security by obscurity”- keeping algorithms secret improves security.
• Published designs undergo public review and are therefore likely to be
stronger.
 AES Requirements
• Private key symmetric block cipher
• 128-bit data, 128/192/256-bit keys
• Stronger & faster than Triple-DES
– DES 168 bit key (56*3)
– Slow in software 16* 3 rounds + key expansion!
– Designed for 70’s hardware
• NIST have released all submissions & unclassified
analyses
• Both C & Java implementations
• Rijndael cipher was made as AES in Oct-2000
The AES Cipher - Rijndael
• Designed by Vincent Rijmen, Joan Daemen in Belgium
• Has 128/192/256 bit keys, 128 bit data
• An iterative rather than feistel cipher
• processes data as block of 4 columns of 4 bytes
• operates on entire data block in every round
• Designed to be:
• resistant against known attacks
• speed and code compactness on many CPUs
• design simplicity
 AES Rounds
• AES is a non-Feistel cipher that encrypts and decrypts a
data block of 128 bits.
• It uses 10, 12, or 14 rounds.
• The key size, which can be 128, 192, or 256 bits, depends
on the number of rounds.

Each version uses a different cipher key size (128, 192, or

256), but the round keys are always 128 bits.
AES Encryption Process
(a) Encryption (b) Decryption

AES Encryption and Decryption

AES Transformation functions
1. Byte substitution (1 S-box used on every byte)
2. Shift rows (permute bytes between groups/columns)
3. Mix columns (subs using matrix multiply of groups)
4. Add round key (XOR state with key material)
1. Substitute byte transformation
2. Shift row transformation
3. Mix column transformation
4. Add round key transformation
Inputs for
Single AES
Round
 RotWord

SubWord
AES Key
Expansion
Round Constants in AES-128
AES Encryption Process
Tools
• Openssl
• [Link]
Advanced Encryption Standard (AES)
• AES is a highly trusted encryption algorithm used to secure data by
converting it into an unreadable format without the proper key.
• Developed by the National Institute of Standards and Technology
(NIST), AES encryption uses various key lengths (128, 192, or 256 bits) to
provide strong protection against unauthorized access.
• AES is a Block Cipher.
• The key size can be 128/192/256 bits.
• Encrypts data in blocks of 128 bits each.
• It takes 128 bits as input and outputs 128 bits of encrypted cipher text.
• AES relies on the substitution-permutation network principle, which is
performed using a series of linked operations that involve replacing and
shuffling the input data.
Block cipher mode of operation
• AES performs operations on bytes of data rather than in bits. Since
the block size is 128 bits, the cipher processes 128 bits (or 16 bytes)
of the input data at a time.
• The number of rounds depends on the key length as follows :
• 128-bit key – 10 rounds
• 192-bit key – 12 rounds
• 256-bit key – 14 rounds
AES modes of operation
• The Electronic Code Book (ECB) mode is one of the easiest and most
effective algorithms to use as a simple replacement technique.
• The input plaintext is divided into blocks and encrypted separately
with the key. This enables the decryption of each encrypted block
independently.
• Encrypting the same block twice returns the same ciphertext twice.
AES modes of operation
• CBC (cipher-block chaining) in cryptography is an AES block cipher
mode that improves the ECB mode for minimizing patterns in
plaintext.
• CBC mode does this by XOR'ing the first plaintext block (B1) with an
initialization vector before encrypting it.
• CBC also uses block chaining, in which each following plaintext block
is XOR-ed with the ciphertext of the preceding block.
Public-Key Cryptography
Terminology Related to Asymmetric Encryption
Asymmetric Keys
Two related keys, a public key and a private key, that are used to perform complementary
operations, such as encryption and decryption or signature generation and signature
verification.
Public Key Certificate
A digital document issued and digitally signed by the private key of a Certification Authority
that binds the name of a subscriber to a public key. The certificate indicates that the
subscriber identified in the certificate has sole control and access to the corresponding
private key.
Public Key (Asymmetric) Cryptographic Algorithm
A cryptographic algorithm that uses two related keys, a public key and a private key. The two
keys have the property that deriving the private key from the public key is computationally
infeasible.
Public Key Infrastructure (PKI)
A set of policies, processes, server platforms, software and workstations used for the
purpose of administering certificates and public-private key pairs, including the ability to
issue, maintain, and revoke public key certificates.
Public-Key Cryptography
Public-Key Cryptography
Conventional and Public-Key Encryption
Public-Key Cryptosystem: Confidentiality
Public-Key Cryptosystem: Authentication
Public-Key Cryptosystem: Authentication and Secrecy
Applications for Public-Key Cryptosystems
 Public-Key Cryptanalysis

• As with symmetric encryption, a public-key encryption scheme is

vulnerable to a brute-force attack.
• The countermeasure is the same: Use large keys.
• However, there is a tradeoff to be considered.
• Public-key systems depend on the use of some sort of invertible
mathematical function.
• The larger the key, the more computationally expensive the
cryptographic operations become.
• Thus, the key size must be large enough to make brute-force attack
impractical but small enough for practical encryption and
decryption.
THE RSA ALGORITHM
• RSA was developed in 1977 by Ron Rivest, Adi Shamir, and Len
Adleman at MIT and first published in 1978.
• The plaintext and ciphertext are integers between 0 and n - 1 for
some n.
• A typical size for n is 1024 bits, or 309 decimal digits. That is, n is less
than 21024.
RSA Encryption Algorithm
• Rivest, Shamir, and Adleman (RSA)
• RSA encryption algorithm is a type of public-key encryption algorithm.
• Asymmetric algorithms are those algorithms in which sender and receiver use
different keys for encryption and decryption. Each sender is assigned a pair of
keys:
• Public key
• Private key
• The Public key is used for encryption, and the Private Key is used for decryption.
• The two keys are linked, but the private key cannot be derived from the public
key.
• The public key is well known, but the private key is secret and it is known only to
the user who owns the key. It means that everybody can send a message to the
user using user's public key. But only the user can decrypt the message using his
private key.
RSA Algorithm
• RSA makes use of an expression with exponentials.
• Plaintext is encrypted in blocks, with each block having a binary
value less than some number n.
• That is, the block size must be less than or equal to log2(n) + 1; in
practice, the block size is i bits, where 2i < n <= 2i + 1.
• Encryption and decryption are of the following form, for some
plaintext block M and ciphertext block C.
RSA Algorithm
• Both sender and receiver must know the value of n. The sender knows
the value of e, and only the receiver knows the value of d.
• Thus, this is a public-key encryption algorithm with a public key of
PU = {e, n} and a private key of PR = {d, n}.
• For this algorithm to be satisfactory for public-key encryption, the
following requirements must be met.
The RSA
Algorithm
Modular Operations
• Modular Addition: (a + b) mod m = ((a mod m) + (b mod m)) mod m
• Modular Multiplication: (a x b) mod m = ((a mod m) x (b mod m)) mod m
• Modular Division
(a / b) mod m is not equal to ((a mod m) / (b mod m)) mod m.
(a / b) mod m = (a x (inverse of b if exists)) mod m
• The modular inverse of a mod m exists only if a and m are relatively prime i.e.
gcd(a, m) = 1. Hence, for finding the inverse of a under modulo m, if (a x b) mod
m = 1 then b is the Modular Inverse of a.
• Modular Exponentiation

A^2 mod C = (A * A) mod C = ((A mod C) * (A mod C)) mod C

 RSA Algorithm: Example

M = 88
 RSA Example
• Solve the RSA algorithm by performing encryption and decryption using the
following: p=3, q=11, M=2.
• To find: n, e, d
 RSA Example
• Choose p = 3 and q = 11
• Compute n = p * q = 3 * 11 = 33
• Compute φ(n) = (p - 1) * (q - 1) = 2 * 10 = 20
• Choose e such that 1 < e < φ(n) and e and φ (n) are coprime. Let e = 7
• Compute a value for d such that (d * e) % φ(n) = 1.
• One solution is d = 3 [(3 * 7) % 20 = 1]
• Public key is (e, n) => (7, 33)
• Private key is (d, n) => (3, 33)
• The encryption of m = 2 is c = 27 % 33 = 29
• The decryption of c = 29 is m = 293 % 33 = 2
 Generate public and private keys:
• Select two large prime numbers, p and q. Multiply these numbers to find n = p x q, where n is called the modulus for
encryption and decryption.
• Choose a number e less than n, such that n is relatively prime to (p - 1) x (q -1). It means that e and (p - 1) x (q -
1) have no common factor except 1. Choose "e" such that 1<e < φ (n), e is prime to φ (n),
gcd (e,d(n)) =1
• If n = p x q, then the public key is <e, n>. A plaintext message m is encrypted using public key <e, n>. To find ciphertext
from the plain text following formula is used to get ciphertext C.
C = me mod n
Here, m must be less than n. A larger message (>n) is treated as a concatenation of messages, each of which is
encrypted separately.
• To determine the private key, we use the following formula to calculate the d such that:
d e mod {(p - 1) x (q - 1)} = 1 Or d e mod φ (n) = 1
• The private key is <d, n>. A ciphertext message c is decrypted using private key <d, n>. To calculate plain text m from
the ciphertext c following formula is used to get plain text m.
m = cd mod n
Encrypt plaintext 9 using the RSA public-key encryption algorithm. This
example uses prime numbers 7 and 11 to generate the public and private
keys.
Step 1: Select two large prime numbers, p, and q.
•p=7
• q = 11
Step 2: Multiply these numbers to find n = p x q, where n is called the
modulus for encryption and decryption.
• First, we calculate
• n=pxq
• n = 7 x 11
• n = 77
Step 3: Choose a number e less that n, such that n is relatively prime to (p -
1) x (q -1). It means that e and (p - 1) x (q - 1) have no common factor except
1. Choose "e" such that 1<e < φ (n), e is prime to φ (n), gcd (e, d (n)) =1.
• Second, we calculate
• φ (n) = (p - 1) x (q-1)
• φ (n) = (7 - 1) x (11 - 1)
• φ (n) = 6 x 10
• φ (n) = 60
• Let us now choose relative prime e of 60 as 7.
• Thus the public key is <e, n> = (7, 77)
Step 4: A plaintext message m is encrypted using public key <e, n>. To
find ciphertext from the plain text following formula is used to get
ciphertext C.
• To find ciphertext from the plain text following formula is used to get
ciphertext C.
• C = me mod n
• C = 97 mod 77
• C = 37
Step 5: The private key is <d, n>. To determine the private key, we use the
following formula d such that:
• d e mod {(p - 1) x (q - 1)} = 1 d = 1 + ( k. φ (n) )
• 7d mod 60 = 1, which gives d = 43 e
• The private key is <d, n> = (43, 77)
Step 6: A ciphertext message c is decrypted using private key <d, n>. To
calculate plain text m from the ciphertext c following formula is used to get
plain text m.
• m = cd mod n
• m = 3743 mod 77
• m=9
• In this example, Plain text = 9 and the ciphertext = 37
DIFFIE–HELLMAN KEY EXCHANGE
• The purpose of the algorithm is to enable two users to securely
exchange a key that can then be used for subsequent symmetric
encryption of messages.
• The Diffie–Hellman algorithm depends for its effectiveness on the
difficulty of computing discrete logarithms.
• Based on - A primitive root of a prime number p is one whose powers
modulo p generate all the integers from 1 to p - 1.
• That is, if a is a primitive root of the prime number p, then the
numbers a mod p, a2 mod p, ... , ap-1 mod p are distinct and consist
of the integers from 1 through p - 1 in some permutation.
The Diffie–Hellman Key Exchange
Example : Diffie Hellman
• For this scheme, there are two publicly known numbers: a prime
number q and an integer α that is a primitive root of q. 51 mod 17 = 5
52 mod 17 = 7
• Let q=17, α<q, α=5 53 mod 17 = 6
• Let XA=4, YA = 5 mod 17 = 13
4 5 4 mod 17 = 13

55 mod 17 = 14
• Let XB = 6, YB = 56 mod 17 = 2 56 mod 17 = 2
5 7 mod 17 7 = 10
• KA = 24 mod 17 = 16 58 mod 17 8 = 16
9 mod 17 9 = 12
• KB = 13 mod 17 = 16
6 5
105 mod 17 10 = 9
511 mod 17 = 11
512 mod 17 = 4
513 mod 17 = 3
514 mod 17 = 15
515 mod 17 = 7
516 mod 17 = 1
Example : Diffie Hellman
• For this scheme, there are two publicly known numbers: a prime
number q and an integer α that is a primitive root of q.
• Let q=7, α<q, α=5
Example : Diffie Hellman
• For this scheme, there are two publicly known numbers: a prime
number q and an integer α that is a primitive root of q. 51 mod 7 = 5
52 mod 7 = 4
• Let q=7, α<q, α=5 3 mod 7 = 6
5
• Let XA=3, YA = 53 mod 7 = 6 54 mod 7 = 2
• Let XB = 4, YB = 54 mod 7 = 2 55 mod 7 = 3
56 mod 7 = 1
• KA = 2 mod 7 = 1
3

• KB = 64 mod 7 = 1
Cryptanalysis
• Because XA and XB are private, an adversary only has the following
ingredients to work with: q, α, YA, and YB. Thus, the adversary is
forced to take a discrete logarithm to determine the key. For example,
to determine Bob’s private key, an adversary must compute

• The adversary can then calculate the key K in the same manner as
Bob calculates it. That is, the adversary can calculate K as

• The security of the Diffie–Hellman key exchange lies in the fact that,
while it is relatively easy to calculate exponentials modulo a prime, it
is very difficult to calculate discrete logarithms
Digital Signatures
• Message authentication protects two parties who exchange messages
from any third party.
• However, it does not protect the two parties against each other. Several
forms of dispute between the two parties are possible.
1. Mary may forge a different message and claim that it came from John.
Mary would simply have to create a message and append an authentication
code using the key that John and Mary share.
2. John can deny sending the message. Because it is possible for Mary to
forge a message, there is no way to prove that John did in fact send the
message.
• There is no complete trust between sender and receiver, something more
than authentication is needed.
• The most attractive solution to this problem is the digital signature.
Digital Signatures - Properties
• The digital signature must have the following properties:
• It must verify the author and the date and time of the signature.
• It must authenticate the contents at the time of the signature.
• It must be verifiable by third parties, to resolve disputes.
• Thus, the digital signature function includes the authentication
function.
 (a) Bob signs a message (b) Alice verifies the signature

Simplified Depiction of
Essential Elements of
Digital Signature Process

No one else has Bob’s

private key and therefore
no one else could have
created a signature that
could be verified for this
message with Bob’s
public key.
Digital Signature Requirements
• The signature must be a bit pattern that depends on the message being
signed.
• The signature must use some information only known to the sender to
prevent both forgery and denial.
• It must be relatively easy to produce the digital signature.
• It must be relatively easy to recognize and verify the digital signature.
• It must be computationally infeasible to forge a digital signature, either by
constructing a new message for an existing digital signature or by
constructing a fraudulent digital signature for a given message.
• It must be practical to retain a copy of the digital signature in storage.
Attacks and Forgeries
• Here A denotes the user whose signature method is being attacked, and C
denotes the attacker.
• Key-only attack: C only knows A’s public key.
• Known message attack: C is given access to a set of messages and their
signatures.
• Generic chosen message attack: C chooses a list of messages before
attempting to breaks A’s signature scheme, independent of A’s public key. C
then obtains from A valid signatures for the chosen messages. The attack is
generic, because it does not depend on A’s public key; the same attack is
used against everyone.
• Directed chosen message attack: Similar to the generic attack, except that
the list of messages to be signed is chosen after C knows A’s public key but
before any signatures are seen.
• Adaptive chosen message attack: C is allowed to use A as an “oracle.” This
means that C may request from A signatures of messages that depend on
previously obtained message-signature pairs.
Attacks and Forgeries
• Success at breaking a signature scheme as an outcome
• Total break: C determines A’s private key.
• Universal forgery: C finds an efficient signing algorithm that provides
an equivalent way of constructing signatures on arbitrary messages.
• Selective forgery: C forges a signature for a particular message
chosen by C.
• Existential forgery: C forges a signature for at least one message. C
has no control over the message. Consequently, this forgery may only
be a minor nuisance to A.