1

March 2023
Public Key Encryption
Information Security

Public Key Encryption

S. Hassan Adelyar, Ph.D

Instructor of Computer Science Faculty
Kabul University

March 2023
 2
Public Key Infrastructure March 2023
Public Key Encryption
Information Security
 3
March 2023
Public Key Encryption
Information Security
 4
March 2023
Public Key Encryption
◼ Cryptography protects data in many
applications:
Information Security

◼ Banking

◼ Military communications

◼ Secure emails
 5
Public Key Encryption March 2023
Public Key Encryption
◼ Based on mathematical functions
◼ Asymmetric cryptography
Information Security

◼ A public-key encryption has six ingredients:

◼ Plaintext

◼ Encryption algorithm

◼ Private key

◼ Public key

◼ Cipher-text

◼ Decryption algorithm
 6
March 2023
Public Key Encryption
◼ One key for encryption & a different but
related key for decryption.
Information Security

◼ The essential steps are the following:

◼ Each user generates a pair of keys to be
used for the encryption & decryption.
◼ Each user places one of the two keys in a
public register or other accessible file. This
is the public key.
◼ RSA Key Generator
◼ https://cryptotools.net/rsagen
 7 Public Key Encryption
March 2023
Public Key Encryption
Information Security
 8
Encryption with Public-Key March 2023
Public Key Encryption
Information Security
 9
Encryption with Private Key March 2023
Public Key Encryption
Information Security
 10
March 2023
Public Key Encryption
◼ User can change private key & publish the
public key to replace the old public key.
Information Security

◼ The scheme of public key encryption provide

confidentiality.
◼ The scheme of private key encryption provide
data integrity.
 11
March 2023
Public Key Encryption

◼ In broad terms, we can classify the use of

public-key cryptosystems into three
Information Security

categories:
◼ Digital signature

◼ Symmetric key distribution

◼ Encryption of secret keys

◼ Some algorithms are suitable for all three

applications, whereas others can be used only
for one or two of these applications.
 12 Requirements for Public-Key Cryptography
March 2023
Public Key Encryption
◼ Computationally easy to generate a pair public
key, private key.
Information Security

◼ Computationally easy for a sender, knowing

the public key to generate the cipher-text.
◼ Computationally easy for the receiver to
decrypt the resulting cipher-text using the
private key.
◼ Computationally infeasible for an opponent,
knowing the public key to determine the private
key.
 13
March 2023
Public Key Encryption
◼ Computationally infeasible for an opponent,
knowing the public key, & a cipher-text, to
recover the original message.
Information Security

◼ Either of the two related keys can be used for

encryption.
 14
Asymmetric Encryption Algorithms March 2023
Public Key Encryption

◼ RSA
◼ One of the first public-key schemes was
Information Security

developed in 1977 at MIT and first published

in 1978.
◼ The RSA scheme is the most widely accepted
& implemented approach to public-key
encryption.
◼ RSA is a block cipher in which the plaintext
& cipher-text are integers between 0 and n - 1
for some n.
 15
Diffie Hellman Key Exchange March 2023
Public Key Encryption
◼ Common Numbers between A & B:
◼ P= 23, g = 5
Information Security

◼ A Secret number: 4
◼ A calculate : g^4 % p = 5^4 % 23 = 4
◼ B secret number: = 3
◼ B calculate: g^3 % p = 5^3 % 23 = 10
◼ A & B exchange their secrete numbers and
calculate a common secrete number as:
◼ A: B^a % P = 10^4 % 23 = 18
◼ B: A^b % P = 4^3 % 23 = 18
 16
RSA March 2023
Public Key Encryption
◼ RSA public / Private Keys:
▪ The RSA algorithm involves four steps:
▪ Key generation
Information Security

▪ Key distribution
▪ Encryption
▪ Decryption
◼ Two prime numbers p, q

◼ N = p*q

◼ Select e where: 1< e <= (p-1)*(q-1) & coprime

with (p-1)*(q-1)
 17
March 2023
Public Key Encryption
◼ Compute d = ed ≡ 1 % (p-1)*(q-1)
◼ Then public key = (n, e), private key =(n, d)
Information Security

◼ Example:
◼ P=3, q=11, n=33, e=7, d=3

◼ Public key=(33, 7), private key = (33,3)

◼ Now use the following formula for encryption

& decryption:
◼ C = P^e % n = 2^7 % 33 = 29
◼ P = C^d % n = 29^3 % 33 = 2
 18
March 2023
Public Key Encryption
▪ A basic principle behind RSA is the
observation that it is practical to find three
very large positive integers e, d, and n, such
Information Security

that with modular exponentiation for all

integers m (with 0 ≤ m < n):

▪ and that knowing e and n, or even m, it can be

extremely difficult to find d.
▪ The triple bar (≡) here denotes modular
similarity.
 19
March 2023
Public Key Encryption
▪ In addition, for some operations it is
convenient that the order of the two
exponentiations can be changed and that this
Information Security

relation also implies:

 20 Security of RSA
March 2023
Public Key Encryption
• The security of RSA depends on the strengths of
two separate functions:
• Encryption Function: It is considered as a
Information Security

one-way function of converting plaintext

into ciphertext & it can be reversed only
with the knowledge of private key d.
• Key Generation: The difficulty of
determining a private key from an RSA
public key is equivalent to factoring the
modulus n.
 21
March 2023
Public Key Encryption
• If either of these two functions are proved non-
one-way, then RSA will be broken.
• In fact, if a technique for factoring efficiently is
Information Security

developed then RSA will no longer be safe.

• The strength of RSA encryption drastically
goes down against attacks if the number p and q
are not large primes and/ or chosen public key e
is a small number.
 22
March 2023
Public Key Encryption
◼ To encrypt a number you multiply it by itself
pub times, making sure to wrap around when
you hit the maximum.
Information Security

◼ To decrypt a message, you multiply it by itself

priv times & you get back to the original
number.
◼ This property was a big breakthrough when it
was discovered.
 23
March 2023
Public Key Encryption
◼ To create a RSA key pair, first randomly pick
the two prime numbers to obtain the maximum
(max).
Information Security

◼ Then pick a number to be the public key pub.

◼ As long as you know the two prime numbers,
you can compute a corresponding private key
priv from this public key.
 24
March 2023
Public Key Encryption
◼ This is how factoring relates to breaking RSA,
factoring the maximum number into its
component primes allows you to compute
Information Security

someone's private key from the public key &

decrypt their private messages.
◼ Example:
◼ Take the prime numbers 3 & 11, their
product gives us our maximum value of 33.
◼ Let's take our public encryption key to be the
number 7.
 25
March 2023
Public Key Encryption
◼ Then using the fact that we know 3 & 11 are
the factors of 33 & applying an algorithm
called the Extended Euclidean Algorithm,
Information Security

we get that the private key is the number 3.

◼ These parameters (max: 33, pub: 7; priv: 3)
define a fully functional RSA system.
◼ You can take a number (for example 2) &
multiply it by itself 7 times to encrypt it,
then take that number & multiply it by itself
3 times & you get the original number back.
 26
March 2023
Public Key Encryption
◼ Example: encrypt 2:
◼ 2*2=4; 4*2 = 8; 8*2= 16; 16*2 = 32; 32*2 =64
Information Security

◼ 64 % 33 = 31
◼ 31 *2 = 62; 62 % 33 = 29, so the encryption of
2 is 29.
◼ To decrypt 29: 29 * 29 = 841; 841 % 33 = 16
◼ 16 * 29 = 464; 464 % 33 = 2
 27
March 2023
Public Key Encryption
◼ Example:
◼ Let's use these values to encrypt the message
Information Security

"CLOUD".
◼ In order to represent a message
mathematically we have to turn the letters
into numbers.
◼ A common representation of the Latin
alphabet is UTF-8.
◼ Each character corresponds to a number.
 28
March 2023
Public Key Encryption
◼ Under this encoding, CLOUD is 67, 76, 79,
85, 68.
Information Security

◼ Each of these digits are smaller than our

maximum of 91, so we can encrypt them
individually.
◼ We have to multiply it by itself 5 times to get
the encrypted value.
◼ 67×67 = 4489 = 30
◼ Since 4489 is larger than max, we have to
wrap it around.
 29
March 2023
Public Key Encryption
◼ We do that by dividing by 91 & taking the
remainder. 4489 = 91×49 + 30
Information Security

◼ 30×67 = 2010 = 8
◼ 8×67 = 536 = 81
◼ 81×67 = 5427 = 58
◼ This means the encrypted version of 67 is 58.
◼ Repeating the process for each of the letters we
get that the encrypted message CLOUD
becomes:
◼ 58, 20, 53, 50, 87
 30
March 2023
Public Key Encryption
◼ To decrypt this scrambled message, we take
each number & multiply it by itself 29 times:
Information Security

◼ 58×58 = 3364 = 88 (remember, we wrap around

when the number is greater than max)>
◼ 88×58 = 5104 = 8
◼ …
◼ 9×58 = 522 = 67
◼ We're back to 67. This works with the rest of the
digits, resulting in the original message.
 31 Elliptic Curve Cryptography (ECC)
March 2023
Public Key Encryption
◼ ECC:
❑ Key-based encryption & authentication.
Information Security

❑ Use math of elliptic curve.

❑ Maintain security with small key size.

❑ High level of performance and security.

❑ Good for mobile resources.

❑ Create keys that are more difficult to crack.

 32
March 2023
Public Key Encryption
◼ Elliptic Curve:
❑ Curve on a plane made up of the points
Information Security

satisfying the equation:

❑ Y^2 = x^3 + ax + b

❑ A & b are constant and x & y are variables.

❑ Any point on the curve can be mirrored over

the x-axis.
❑ Any non-vertical line will intersect the curve

in 3 places or fewer.
 33
March 2023
Public Key Encryption
Information Security
 34
March 2023
Public Key Encryption
◼ Elliptic Curve Properties:
❑ Horizontal symmetry
Information Security

❑ Any non-vertical line will intersect the curve

in at most 3 places.
❑ Easy to compute and hard to reverse

(trapdoor).
❑ Given 2 points P & Q on an elliptic curve,

there is a third point R such that P+Q = R.

❑ Elliptic curve is not an ellipse or oval shape.
 35
March 2023
Public Key Encryption
◼ Advantages of ECC:
❑ Public key cryptography use Algorithms that
Information Security

are easy to process in one direction &

difficult to process in the reverse direction.
◼ Example:
❑ RSA relies on the fact that multiplying prime
numbers to get a larger number is easy, while
factoring huge number back to the original
primes is more difficult.
 36
March 2023
Public Key Encryption
◼ To remain secure, RSA needs keys that are
2048 bits or larger.
Information Security

◼ Size of the keys is an important advantage of

ECC. 384 bit key achieve the same level of
security as 7680 bit key of RSA (Non-linear
relationship). So, ECC key generation &
signing are quicker.
◼ In ECC pub is a point on the curve & private
key is an integer.
◼ Not: It is not easy to securely implement ECC.
 37
March 2023
Public Key Encryption
◼ ECC Usages:
❑ Digital signature in cryptocurrency.
Information Security

❑ Financial transactions

❑ On-line banking & payments (credit card

information is encrypted using ECC).
❑ Web applications

❑ Messages services

❑ SSL / TLS

❑ Pretty Good Privacy (GPG), that is email

encryption software use ECC.
 38
March 2023
Public Key Encryption
◼ We have to restrict ourselves to numbers in a
fixed range, like in RSA.
Information Security

◼ Rather than allow any value for the points on

the curve, we restrict ourselves to whole
numbers in a fixed range.
 39
March 2023
Public Key Encryption
◼ ECC relies on the elliptic curve discrete
logarithm problem, which states that:
Information Security

◼ It is hard to solve for x if we know y=g^x % p

where g is some known integer & p is prime.
◼ This problem is complex because there is no
known way efficiently find x given y ( that is,
without trying every possible value of x until
we find one that works).
 40
March 2023
Public Key Encryption
◼ It is also hard to solve for y if we know x=g^y
% p.
Information Security

◼ That is, it would be difficult for someone who

doesn’t know the secret exponent y to compute
y given x ( again, without trying every possible
value until they find one that works).
◼ Y^2 = x^3 +ax + b
◼ Each of these cryptography mechanisms uses
the concept of a one-way, or trapdoor function.
 41
Digital Envelope March 2023
Public Key Encryption
◼ Another application in which public-key
encryption is used to protect a symmetric key
is the digital envelope, which can be used to
Information Security

protect a message without needing to first

arrange for sender & receiver to have the same
secret key.
◼ The technique is referred to as a digital
envelope, which is the equivalent of a sealed
envelope containing an unsigned letter.
 42
March 2023
Public Key Encryption
◼ The general approach is shown in Figure 2.9.
Suppose B wishes to send a confidential
message to A, but they do not share a
Information Security

symmetric secret key.

◼ B does the following:
◼ 1. Prepare a message.

◼ 2. Generate a random symmetric key that

will be used this one time only.
◼ 3. Encrypt that message using symmetric
encryption the one-time key.
 43
March 2023
Public Key Encryption
◼ 4. Encrypt the one-time key using public-
key encryption with A’s public key.
Information Security

◼ 5. Attach the encrypted one-time key to the

encrypted message & send it to A.
◼ Only A is capable of decrypting the one-time
key & therefore of recovering the original
message.
◼ If B obtained A’s public key by means of A’s
public-key certificate, then B is assured that
it is a valid key.
 44
Figure 2.9 Digital Envelopes March 2023
Public Key Encryption
Information Security
 45
March 2023
Public Key Encryption
◼ Symmetric encryption benefits:
❑ Speed
Information Security

❑ Efficiency

❑ Simplicity

❑ Compatibility
 46
March 2023
Public Key Encryption
◼ Benefits of Asymmetric Encryption
❑ Security
Information Security

❑ Authentication

❑ Key distribution

❑ Non-repudiation

❑ Flexibility
 47
March 2023
Public Key Encryption
◼ Symmetric encryption is commonly used in
applications such as email, file sharing, and
virtual private networks (VPNs).
Information Security

◼ Asymmetric encryption is used in applications

where security is critical, such as online
banking and cryptocurrency.
◼ It is used in digital signatures, SSL/TLS, and
secure email communication.
End of Lesson 4

Question / Discussion?