Topic 3

Asymmetric Encryption

1
 Strength of AES
 Disadvantage of Symmetric
Encryption
◦ Key Distribution
 Asymmetric Encryption
◦ Matched Key Pair
◦ Private Key
◦ Public Key
◦ Example: RSA
 Encryption
 c = me(mod n)
 Decryption:
 m = cd(mod n)

Microsoft Windows Security: Essentials by Darril Gibson,

Sybex, 2011 (Available via Books24x7.com)
– Chapter 10

2
 Some early algorithms used 40 bits and could sometimes be
cracked within a week.
 If a cipher text which is created by AES using a 128-bit key, it's
estimated that it would take more than two million, million, million
(2,000,000,000,000,000,000) years to crack this key and then read
the data. If an attacker invested millions in multiple
supercomputers and networked them together to crack a key, the
time might be reduced.

3
 The sender and receiver must share the same secret key. Key
distribution is a must.
 If 52 people want to communicate (two and two, in all possible
ways), each must keep 51secret keys, and the system requires a
total of (51 x 52) / 2 = 1326 secret keys. This makes key
management difficult.

4
 Asymmetric encryption uses two matched keys
◦ Also known as public-key encryption.
◦ It uses two matched keys, a public key and a private key.
◦ When public key encrypts data, only the private key can
decrypt it.
◦ When private key encrypts data, only the public key can
decrypt it.

5
Can such keys exists in reality?

6
 Two common asymmetric encryption
algorithms
◦ RSA
 Named after Rivest, Shamir, and
Adleman, the three individuals who
first described it
◦ Diffie-Hellman
 Named after Diffie and Hellman
 Modern encryption is heavily based on
mathematical theory.
 We will cover the basic mathematics that is
used in the RSA asymmetric encryption
algorithm.

7
 It is crucial to security that keys are generated
with a truly random or at least a pseudo-random
generation process
 Otherwise, an attacker might reproduce the key
generation process and easily find the key used
to secure a specific communication

8
 How to generate random number in C++, Java and php?

Import java.util.Random;

9
 How to generate random number in C++, Java and php?

Import java.util.Random;

10
 A pseudo-random bit generator is an
algorithm which, given a truly random
binary sequence of length k (“seed”),
outputs a binary sequence of length m >>
k which “appears to be random ".
 The seed for pseudo-random number
generators, may be based upon processes
as:
◦ The system clock
◦ Elapsed time between keystrokes or
mouse movement
◦ Content of input/output buffers
◦ User input, and
◦ Operating system values such as system
load and network statistics

11
 All integer numbers (except 0 and 1) are
made up of primes.
 Prime numbers are integers that have
divisors of 1 and itself. In other words,
they cannot be written as a product of
other numbers.
 Facts about primes:
◦ 1 is prime, but is generally not of interest
◦ 2, 3, 5, 7 are prime
◦ 4, 6, 8, 9, 10 are not prime
◦ List of prime number less than 200 is: 2, 3,
5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
101, 103, 107, 109, 113, 127, 131, 137,
139, 149, 151, 157, 163, 167, 173, 179,
181, 191, 193, 197, 199

12
 A common divisor of two integers a and
b is a positive divisor of both a and b.
 The Greatest Common Divisor (GCD) 最
大公因數 refers to the greatest of all the
common divisors of a and b, denoted by
gcd(a,b)
 Example: To find gcd(60, 24)
◦ Divisors of 60: 1, 2, 3, 4, 5, 6, 10, 12, 15,
20, 30, 60
◦ Divisors of 24: 1, 2, 3, 4, 6, 8, 12, 24
◦ 60 and 24 have the common divisors 1, 2,
3, 4, 6, 12
◦ gcd(60, 24) = 12

13
 Write the prime factorization of 280

280

2 140

2 70

2 35

5 7
 Write the prime factorization of 25200

 If the number is too big, you may simply consider

the answer as follows:
 25200 = 8 x 3150  randomly breaking it
 = 2 x 2 x 2 x 315 x 10
 = 2 x 2 x 2 x 2 x 5 x 3 x 105
 = 24 x 3 x 52 x 21
 = 24 x 32 x 52 x 7
 Write the prime factorization of 25200

 If the number is too big, you may simply consider

the answer as follows:
 25200 = 8 x 3150  randomly breaking it
 = 2 x 2 x 2 x 315 x 10
 = 2 x 2 x 2 x 2 x 5 x 3 x 105
 = 24 x 3 x 52 x 21
 = 24 x 32 x 52 x 7
 Method 1
 gcd(15,40)
Method 2
40 = 15 (2) + 10

15 = 10 (1) + 5

10 = 5(2) + 0 gcd(15, 40) = 5

18
 gcd(128,48)?  gcd(95,209)?

128 = 48 (2) + 32
 128 = 48(2) + 32
48 = 32 (?) + ?  209 = 95(2) + 19
 48 = 32(1)
…. + 16

 32 = 16(2) + 0  95 = 19(5) + 0

 gcd(128,48) = 16
 gcd(209,95) = 19

19
 gcd(128,48)?  gcd(95,209)?
 209 = 95(2) + 19
 128 = 48(2) + 32

 48 = 32(1) + 16  95 = 19(5) + 0

 32 = 16(2) + 0
 gcd(209,95) = 19
 gcd(128,48) = 16

20
 a mod n means the remainder餘數 when a is divided by n
 That is a = q x n + r where q is the quotient商數and r is
the remainder.
 Note: n is called modulus More examples:
Even numbers ≡ 0 (mod 2)
 Examples: Odd numbers ≡ 1 (mod 2)
◦ 73 mod 7 = 3 317 ≡ 2 (mod 5)
◦ -11 mod 7 = 3 91 ≡ 1 (mod 9)
◦ The clock has a modulus of 12! 14 ≡ −1 (mod 3)

Quick questions:
What is 7mod2?
What is 11mod3?

21
 a mod n means the remainder餘數 when a is divided by n
 That is a = q x n + r where q is the quotient商數and r is
the remainder.
 Note: n is called modulus
 Examples: Quick questions: Answer
◦ 73 mod 7 = 3 What is 7mod2? 1
◦ -11 mod 7 = 3
What is 11mod3? 2
◦ The clock has a modulus of 12!

22
 In general Modular Arithmetic has lots of use
cases in mathematics and computer science.
 Here, in cryptography especially in public Key
Cryptography, some operations which are crucial
for other operations are done by this math.

23
 Why this math in crypto?
◦ This also has practical application in Public Key Cryptography.
For now, remember that we will use this somewhere in the RSA
algorithm.

https://medium.com/dsc-sastra-deemed-to-be-
university/mathematics-in-cryptography-part-1-3749e5b354c

24
 Step 1: find the gcd(9, 23) • The following
equations will be
 23 = 9 (?) + (?) used for back
substitution.
 23 = 9 (2) + 5 • 5 = 23 - 9 (2)
 9 = 5 (?) + ? • 4 = 9 - 5 (1)
 9 = 5 (1) + 4 • 1 = 5 – 4(1)

 5 = 4 (?) + ?
 5 = 4 (1) + 1
 4 = 1 (4) + 0  if you see
zero remainder, gcd(9,23) = 1
 Step 2: Backward substitution
 Start from 1 = 5 – 4(1) • The following
 Substitute 4 equations will be used
 1 = 5 – (9 – 5(1))(1) for back substitution.
 1 = 5(2) – 9 • 1 = 5 – 4(1)
Substitute 5

• 4 = 9 - 5 (1)
 1 = (23 – 9(2))(2) – 9
 1 = 23(2) – 9(5) • 5 = 23 - 9 (2)
 Because 9 mod 23, Take mod 23
 1(mod23) ≡ (23(2) – 9(5)) (mod 23)
 1 ≡ 0 – 5(9) (mod23)
 Change -5 to positive
 1 ≡ 0 + (23-5)(9)(mod23)
 1 ≡ (18) (9 mod 23)
 Conclusion: Multiplicative inverse of 9 mod23 is
18 or -5.
 Below are formulas
for backward
substitutions
 15=600-43x15
 13=43-15x2
 2=15-13x1

Backward
substitutions
 2=15-13x1
 2=15-13x1
 15=600-43x15
1mod600 = 43x307mod600 – 600x20mod600
1  43x307mod600 – 0
1  307x43mod600
The multiplicative inverse of 43 mode 600
27
  Step 2: back substitution
• Step 1: gcd(50,71)  1 = 3 – 2(1)
1 = 3 – (5 – 3)
• 71 = 50(1) + 21 
 1 = 3(2) – 5
• 50 = 21(2) + 8  1 = (8-5)(2) – 5
• 21 = 8(2) + 5  1 = 8(2) – 5(3)
1 = 8(2) – (21 – 8(2))(3)
8 = 5(1) + 3

•  1 = 8(8) – 21(3)
• 5 = 3(1) + 2  1 = (50 – 21(2))(8) – 21(3)
• 3 = 2(1) + 1  1 = 50(8) – 21(19)
 1 = 50(8) – (71 – 50)(19)
• 2 = 1(2) + 0  1 = 50(27) – 71(19)
• gcd(50, 71) = 1  50(27) = 1 + 71(19)
 50 ≡ 1 mod 71
Conclusion: 27 is an inverse of 50 modulo 71
  Step 2: back substitution
• Step 1: gcd(50,71) 

1 = 3 – 2(1)
1 = 3 – (5 – 3)
• 71 = 50(1) + 21  1 = 3(2) – 5
1 = (8-5)(2) – 5
• 50 = 21(2) + 8 
 1 = 8(2) – 5(3)
• 21 = 8(2) + 5  1 = 8(2) – (21 – 8(2))(3)
1 = 8(8) – 21(3)
8 = 5(1) + 3

•  1 = (50 – 21(2))(8) – 21(3)
• 5 = 3(1) + 2 

1 = 50(8) – 21(19)
1 = 50(8) – (71 – 50)(19)
• 3 = 2(1) + 1  1 = 50(27) – 71(19)
Take mod 71
2 = 1(2) + 0

•  1 ≡ 27 (50 mod 71)
• gcd(50, 71) = 1 Conclusion: 27 is an inverse of 50 modulo 71
Or 27-71= -44 is an inverse of 50 modulo 71
Usually, prefer +ve number as answer
 Step 1: gcd(43,64) • 1 = 43 – (64-43)(2)
64=43(1) + 21

• 1 = 43(3)-64(2)
 43=21(2) + 1
 21=1(21) + 0 • 43(3) = 1 + 64(2)
• 43(3) ≡ 1 mod 64
 Step 2: back
substitution
• Conclusion: 3 is an
 1 = 43 – 21(2)
inverse of 43
modulo 64
 Step 1: gcd(43,64) • 1 = 43 – (64-43)(2)
 64=43(1) + 21 • 1 = 43(3)-64(2)
 43=21(2) + 1 • 43(3) = 1 + 64(2)
 21=1(21) + 0 • Take mod 64
• 1 ≡ 3 (43 mod 64)
 Step 2: back
substitution
 1 = 43 – 21(2) • Conclusion: 3 is an
inverse of 43
modulo 64
 Choose two distinct prime numbers p and q . (The
integers p and q should be chosen at random, similar
in size, and large.)
 Compute n = p x q
◦ The size of n, when expressed in bits, is the key length.
 Computer f = (p-1) (q-1). Find an integer e such that
◦ 1≤ e < f , and
◦ gcd ( e, f ) = 1
 • Find d such that
◦ d x e mod f = 1
 • Public key: n, e – This is to be released to everyone
 • Private key: d - This must be kept private.

32
 Encryption:
◦ When someone wants to send you a message they
◦ Break the message into blocks of length k, where k=log2n
◦ Convert each message block into a number in a simple agreed
upon way such as a = 1, b = 2, c = 3, …
◦ Compute the ciphertext c = me(mod n)
◦ Send you c
 Decryption:
◦ To decrypt their message you:
◦ Compute m = cd(mod n)
◦ Convert their message back into letters and words
◦ Assemble the blocks back to a single message

33
 Generate key pair
◦ Choose p = 3, q = 11
◦ Compute n = p x q = 3(11) = 33
◦ Compute f = (11 – 1) x ( 3 – 1 ) = 20
◦ Now, select e = 7
◦ Compute such that d x 7 mod 20 = 1
 d = 3 ( since 3 × 7 mod 20 = 1 )
◦ – Make n = 33 and e = 7 public.

The private key will be

◦ Public key is (e, n) => (7, 33) used in slide 17 for
◦ Private key is (d, n) => (3, 33) encryption and decryption.

34
 Generate key pair
◦ Given p = 11, q = 17
◦ What would be the private and
public key values?

Answer 1 Answer 2
◦ Compute n = p x q = 7(17) = 187 ◦ Compute n = p x q = 7(17) = 187
◦ Compute f = (11 – 1) x ( 17 – 1 ) = ◦ Compute f = (11 – 1) x ( 17 – 1 ) =
160 160
◦ Now, select e = 7 ◦ Now, select e = 23
◦ Compute such that d x 7 mod ◦ Compute such that d x 23 mod
160 = 1 160 = 1
 Private key: d = 23 ( since 23 ×  Private key: d = 7 ( since 23 × 7
7 mod 160 = 1 ) mod 160 = 1 )
 ➔ (d, n) = (23, 187)  ➔ (d, n) = (7, 187)
 Public key: n = 187 and e = 7.  Public key: n = 187 and e =23.
 ➔ (e, n) = (7, 187)  ➔ (e, n) = (23, 187)

35
 Generate key pair
◦ Given p = 11, q = 17
◦ What would be the private and
public key values?

Answer 1 Answer 2
◦ Compute n = p x q = 7(17) = 187 ◦ Compute n = p x q = 7(17) = 187
◦ Compute f = (11 – 1) x ( 17 – 1 ) = ◦ Compute f = (11 – 1) x ( 17 – 1 ) =
160 160
◦ Now, select e = 7 ◦ Now, select e = 23
◦ Compute such that d x 7 mod ◦ Compute such that d x 23 mod
160 = 1 160 = 1
 Private key: d = 23 ( since 23 ×  Private key: d = 7 ( since 23 × 7
7 mod 160 = 1 ) mod 160 = 1 )
 ➔ (d, n) = (23, 187)  ➔ (d, n) = (7, 187)
 Public key: n = 187 and e = 7.  Public key: n = 187 and e =23.
 ➔ (e, n) = (7, 187)  ➔ (e, n) = (23, 187)

36
 Encryption [public key (e, n) = (7, 33)]:  slide 18
◦ For simplicity, let’s say the message is m . And m = 2.
◦ Compute c where c = me(mod n).
◦ 27 = 128, so c = 128 (mod33) = 29
 because 128 = 29 + 3 x 33
◦ Your friend will send you the ciphertext c = 29

 Decryption [private key (d, n) = (3, 33)]:  slide 18

◦ You just received c = 29 from your friend
◦ Use your private key, d = 3, to compute their message m
◦ m = cd(mod n) = 293 (mod33) = 24389 (mod33)
◦ = 2 because 293 = 24389 =2 + 739 x 33
◦ So your friend sent you the message m= 2

37
 Using your private key and public key
To encrypt a message m = 2 if public key (23,187)
To decrypt a cipher c = 146 if private key (7,187)

Answer1 [public key (23,187) & private key (7,187)] Answer 2 [public key (7,187) & private key (23,187)]

Encryption: Encryption:
For simplicity, let’s say the message is . And m For simplicity, let’s say the message is . And m = 2.
= 2. Compute c where c = me(mod n).
Compute c where c = me(mod n). From slide 17, e = 7
From slide 17, e = 23 so c = 27(mod187) = 128
so c = 223(mod187) = 162 because 27 = 128+ 0 x 187
because 223 = 162 + 8388446 x 187 Your friend will send you the ciphertext c = 128
Your friend will send you the ciphertext c = 162 Decryption:
Decryption: You just received c = 146 from your friend
You just received c = 146 from your friend From slide 17, use your private key, d = 23, to compute
From slide 17, use your private key, d = 7, to their message m
compute their message m m = cd(mod n) = 14623(mod187) =
m = cd(mod n) = 1467(mod187) = 6.02720111278914052e+49 (mod187)  m
1414067010444416(mod187)  m So your friend sent you the message m= 5
because 1467 = 1414067010444416 =
141 + 7561855670825 x 187
So your friend sent you the message m= 141

38
 Using your private key and public key
To encrypt a message m = 2 if public key (23,187)
To decrypt a cipher c = 146 if private key (7,187)

Answer1 [public key (23,187) & private key (7,187)] Answer 2 [public key (7,187) & private key (23,187)]

Encryption: Encryption:
For simplicity, let’s say the message is . And m For simplicity, let’s say the message is . And m = 2.
= 2. Compute c where c = me(mod n).
Compute c where c = me(mod n). From slide 17, e = 7
From slide 17, e = 23 so c = 27(mod187) = 128
so c = 223(mod187) = 162 because 27 = 128+ 0 x 187
because 223 = 162 + 8388446 x 187 Your friend will send you the ciphertext c = 128
Your friend will send you the ciphertext c = 162 Decryption:
Decryption: You just received c = 146 from your friend
You just received c = 146 from your friend From slide 17, use your private key, d = 23, to compute
From slide 17, use your private key, d = 7, to their message m
compute their message m m = cd(mod n) = 14623(mod187) =
m = cd(mod n) = 1467(mod187) = 6.02720111278914052e+49 (mod187)  m
1414067010444416(mod187)  m So your friend sent you the message m= 5
because 1467 = 1414067010444416 =
141 + 7561855670825 x 187
So your friend sent you the message m= 141

39
 In practice, the keys used in asymmetric encryptions are much
longer than our examples.
 For example, in RSA-768, a 768-bit RSA modulus has a 232- digit
decimal representation
◦ 123018668453011775513049495838496272077285356959533
479219732245215172640050726365751874520219978646938
995647494277406384592519255732630345373154826850791
702612214291346167042921431160222124047927473779408
0665351419597459856902143413.
 Ref: http://eprint.iacr.org/2010/006.pdf

40
 It was a challenge put forward by RSA Laboratories on March 18,
1991 to demonstrate the practical difficulty of factoring large
integers and cracking RSA keys.
 They published a list of the RSA numbers, with a cash prize for the
successful factorization of some of them. The smallest of them, a
100 decimal digit number was factored by April 1, 1991.
 The RSA challenges ended in 2007.

41
http://www.isiloniq.com/emc-plus/rsa-labs/historical/the-rsa-factoring-challenge-faq.htm

42
 Asymmetric encryption is about 1,000 times slower than symmetric
encryption.
 For example, it may take only one second to encrypt a file using
symmetric encryption, such as AES. How much time will it take to
encrypt the same file using asymmetric encryption such as RSA?
You can test the speed difference
https://slproweb.com/products/Win32OpenSSL.html
Sym

Asym
43
It takes about 3.0x second to do 2nd hand
benchmark the AES-128 algorithm for
different block sizes

44
It takes about 10.02 second to do 2nd hand
benchmark the RSA2048 algorithm

45
46
 Imagine that Maria's computer is trying to establish a secure
session with the server. The server has a private key matched with
a public key shared with Maria's computer.
 Maria's system creates the session key and then encrypts it with
the server's public key. The encrypted session key is then sent to
the server that holds the matching private key.
 If anyone intercepts the encrypted session key, it isn't useful to
them because it can only be decrypted with the matching private
key, which is kept private.

47
48
 When the server receives the encrypted session
key, it uses the private key in the matched key
pair to decrypt the session key. At this point,
both parties know what the session key is, but no
one else knows what it is.
 The data that is to be transferred between the
two machines can then be encrypted and
decrypted with the session key using symmetric
encryption.
 See next slide.

49
Decryption

50
  Certificates are digital files that include several pieces of
key data used with public key encryption. Certificates are
used for a wide variety of purposes including sharing a
public key.
 Next slide shows a certificate with the public key selected.
 You can access it from the Personal certificate store on a
Windows system. Notice that the public key is 4,096 bits
long and the algorithm is RSA.
https://www.quora.com/Where-is-RSA-encryption-used

51
52
 Secure/Multipurpose Internet Mail Extensions
(S/MIME)
◦ It is the underlying standard used for most email security.
◦ It uses public and private keys to encrypt and digitally sign
email.
◦ The sender must have a certificate with a public key
embedded that matches a private key that only the sender can
access.
◦ Within an Active Directory domain, administrators often create
a certification authority (CA) to issue and manage certificates.
◦ Additionally, public CAs issue and manage certificates that
are commonly used on the Internet and elsewhere.

53
1. The sender creates a session key for symmetric encryption.
2. The sender encrypts the email using the session key and symmetric
encryption.
3. The sender retrieves the recipient's certificate, which contains the
recipient's public key.
4. The sender encrypts the session key with the recipient's public key.
5. The sender sends both the encrypted email and the encrypted session
key.
6. The recipient receives the encrypted email and the encrypted session
key.
7. The recipient decrypts the session key using the recipient's private key.
8. The recipient uses the decrypted session key to decrypt the contents of
the email.

54
 Using asym
encryption

Using sym
encryption

Email is protected by sym encryption and

Sym secret key is protected by asym encryption
55
56
Encrypting email with Microsoft Outlook Secure connection to email server

57
58