Public-Key Cryptography.pdfWrite the result of the following operation with the correct number of significant figure of 0.248?

Write the result of the following operation with the correct number of significant figure of 0.248?Write the result of the following operation with the correct number of signi

1. PUBLIC-KEY CRYPTOGRAPHY
CS432: Network Security

2. Private-Key Cryptography
2





Traditional private/secret/single key
cryptography uses only One key
Shared by both sender and receiver
If this key is disclosed, communications are
compromised
Symmetric, parties are equal
Does not protect sender from receiver forging
a message & claiming is sent by sender

3. Public-Key Cryptography
3









Encryption and decryption are carried out using
two different keys
Public & Private key
Asymmetric since parties are not equal
Any party encrypts messages or verifies signatures
can not decrypts messages or creates signatures
Complements rather than replaces private key
crypto
All parties interested in secure communications
publish their public keys
No problem of key distribution
Infeasible to determine private key from public
key
Provides confidentially and authentication

4. Public-Key Cryptography
4














Why Public-Key Cryptography?
Key distribution
In symmetric key cryptosystems: parties already shared a key,
or they use Key Distribution Center (KDC)
Digital signatures
Verify a message
Public-key cryptography involves the use of two
keys:
Public-key
Known by anybody
Used to encrypt messages
Verify signatures
Private-key
Known only to the recipient
Used to decrypt messages
Sign (create) signatures

5. Confidentially & Authentication
5
Confidentiall
y
Authentication

6. Confidentially & Authentication
6
Confidentially &
Authentication

7. Confidentially & Authentication
7

8. Confidentially & Authentication
8

9. Private-Key and Public-Key
Cryptography
9

10. Public-Key Applications
10



Encryption/Decryption (provide Confidentially)
Digital signatures (provide Authentication)
Key exchange (of session keys)

11. Public-Key Requirements
11



Public-Key algorithms rely on two keys where:
Computationally infeasible to find decryption key
or plain text knowing only algorithm, encryption
key, and ciphertext
Computationally easy to encrypt/decrypt
messages when the relevant (encrypt/decrypt)
key is known

12. Public-Key Requirements
12




One-way function
Maps a domain into a range such that every
function value has a unique inverse
Trap-door one-way function
Easy to calculate in one direction and infeasible to
calculate in the other direction unless certain
additional information is known.

13. Security of Public Key Schemes
13





Brute force exhaustive search attack is always
theoretically possible
Keys used are too large (>512bits)
Security relies on a large enough difference in
difficulty between easy (encrypt/decrypt) and
hard (cryptanalyze) problems
Use of very large numbers
Slow compared to private key schemes

14. RSA
14







By Rivest, Shamir & Adleman of MIT in 1977
Best known & widely used public-key scheme
Based on exponentiation in a finite (Galois)
field over integers modulo a prime
Exponentiation takes O((log n)
3) (easy)
Uses large integers (eg. 1024 bits)
Security due to cost of factoring large numbers
Factorization takes O(e
log n log log n) (hard)

15. RSA Setup
15












Each user generates a public/private key pair by:
Selecting two large primes at random: p, q
Computing their system modulus n=p.q
ø(n)=(p-1)(q-1)
Selecting at random the encryption key e, where:
1<e<ø(n)
gcd(e,ø(n))=1
Solve following equation to find decryption key d
d= e
-1
mod ø(n) and 0≤d≤ø(n)
Publish their public encryption key: PU={e,n}
Keep secret private decryption key: PR={d,n}
(p, q, ø(n), d) are secret

16. RSA Encryption and Decryption
16







To encrypt a message M the sender:
Obtains public key of recipient PU={e,n}
Computes: C = M
e mod n, where 0≤M<n
To decrypt the ciphertext C the owner:
Uses their private key PR={d,n}
Computes: M = C
d mod n
M must be smaller than the modulus n (block if
needed)

17. Power Reduction
17



When n is a product of two primes, in
arithmetic operations modulo n, the exponents
behave modulo the ø(n), if ø(n) < e
Example:
5
7·5
4 mod 15 = 5
(7+4) mod ø(15) mod 15
= 5
(7+4) mod 8 mod 15
= 5
3 mod 15
= 125 mod 15
= 5

18. Why RSA Works?
18








Because of Euler's Theorem:
a
ø(n) mod n = 1, where gcd(a,n)=1
RSA have:
n=p.q
ø(n)=(p-1)(q-1)
e & d to be inverses mod ø(n)
e.d=k.ø(n)+1 for some k
Hence :
C
d = M
e.d = M
k.ø(n)+1 = M
1.(M
ø(n))
k
= M
1.(1)
k = M.1 = M mod n

19. RSA Example
Key Setup
19












Select primes:
p=17 & q=11
Calculate n = pq
17 x 11=187
Calculate ø(n)=(p‒1)(q-1)
16x10=160
Select e: gcd(e, ø(n))=1; 0≤e≤ø(n)
Choose e=7
Determine d: d.e=1 mod ø(n) and 0≤d≤ø(n)
d=23 since 23x7=161 mod ø(n) = 1
Publish public key PU={7,187}
Keep secret private key PR={23,187}

20. RSA Example
Encryption and Decryption
20





Given message M = 88
Encryption:
C = 88
7 mod 187 = 11
Decryption:
M = 11
23 mod 187 = 88

21. Exponentiation
21







Use the Square and Multiply Algorithm
Fast, efficient algorithm for exponentiation
Based on repeatedly squaring base and multiplying
in the ones that are needed to compute the result
Look at binary representation of exponent
Takes O(log2 n) multiples for number n
Example: Solve 75 mod 11?
5 = (101)2
7
1 = 7 mod 11 = 7
7
2 = 49 mod 11 = 5
7
4 = 5.5 mod 11 = 25 mod 11 = 3
7
5 = 7
4.7
1 = 3.7 = 10 mod 11 = 10
Solve 3129 mod 11?

22. RSA Example
n = p.q = 77
ø(n) = (p-1)(q-1) = 10 . 6 = 60
d = e-1 mod ø(n) = 37-1 d 60 = 13
C = Me = 1537 mod 77
37 = (100101)2
151 = 15 mod 77 = 15
152 = 15.15 mod 77 = 225 mod 77 = 71
154 = 71.71 mod 77 = 5041 mod 11 =
36
158 = 36.36 mod 77 = 1296 mod 11 =
64
1516 = 64.64 mod 77 = 4096 mod 11 =
15
1532 = 15.15 mod 77 = 225 mod 11 = 71
1537 = 1532.154 .151 = 71.36.15 = 71
C = 71


M = C
d mod n
= 71
13 mod 77
13 = (1101)
2
71
1 = 71 mod 77 = 71
71
2 = 71.71 mod 77 = 5041 mod 11 = 36
71
4 = 36.36 mod 77 = 1296 mod 11 = 64
71
8 = 64.64 mod 77 = 4096 mod 11 = 15
71
13 = 71
8.71
4 .71
1 = 15.64.71 = 15
M = 15

22
Encryption Decryption
Let p=11, q=7, m=15, e=37
Show the calculation of encryption and decryption?

23. Efficient Encryption
23






Encryption uses exponentiation to power e
If e small, this will be faster
Examples:
e=65537 (2
16-1), e=3, or e=17
If e is too small
It is easy to be attacked using CRT

24. Efficient Decryption
24




Decryption uses exponentiation to power d
It is likely to be large, insecure if not
CRT could be used to compute modulo p and q
separately
Only the owner of the private key could use this
technique (p and q are secret)

25. RSA Key Generation
25







RSA users must:
Determine two primes at random - p, q
Select either e or d and compute the other
p,q must not be easily derived from modulus
n=p.q
Must be sufficiently large
Exponents e, d are inverses
So use Inverse algorithm to compute the other

26. RSA Security
26





Possible approaches to attacking RSA are:
Brute force key search - infeasible given size of
numbers
Mathematical attacks - based on difficulty of
computing ø(n), by factoring modulus n
Timing attacks - on running of decryption
Chosen ciphertext attacks - given properties of
RSA

27. Factoring Problem
27







Mathematical approach takes three forms:
Factor n=p.q, hence compute ø(n) and then d
Determine ø(n) directly and compute d
Find d directly
All considered as factorization problem
Best results reach 663 bits
A key size that ranges between 1024 to 2048 is
reasonable

28. Timing Attacks
28









Exploit timing variations in operations
Multiplying by small vs large number
Varying which instructions executed
Infer operand size based on time taken
Time taken in exponentiation
Countermeasures
Use constant exponentiation time
Add random delays
Blind values used in calculations

29. Chosen Ciphertext Attacks
29






RSA is vulnerable to a Chosen Ciphertext
Attack
Attackers chooses ciphertexts & gets decrypted
plaintext back
Choose ciphertext to exploit properties of RSA to
provide extra information to help cryptanalysis
Countermeasures
Random pad of plaintext
Optimal Asymmetric Encryption Padding (OASP)

30. Another RSA Example
30
Let p=197, q=211, m=28, e=17
Show the calculation of encryption and decryption?

31. Diffie-Hellman Key Exchange
31









Enable two users to securely exchange a key that can
then be used for subsequent encryption of messages
Exchange of a secret key
Public-key distribution scheme
Can not be used to exchange an arbitrary message
It can establish a common key
Known only to the two participants
Value of key depends on the participants (and their
private and public key information)
Based on exponentiation in a finite (Galois) field - easy
Security relies on the difficulty of computing discrete
logarithms (similar to factoring) ‒ hard

32. Discrete Logarithm


If ‘a’ is a primitive root of the prime number p, then the
numbers
a mod p, a
2
mod p,..., a
p-1
mod p
are distinct and consist of the integers from 1 through p-1
in some permutation.
For any integer ‘b’ and a primitive root ‘a’ of prime
number ‘p’, we can find a unique exponent ‘i’ such that
b ≡a
i
(mod p) where 0≤ i≤ (p -1)
The exponent i is referred to as the discrete logarithm of
b for the base a, mod p.
i=log
a(b) mod p

IS-876

33. Diffie-Hellman Setup
33








All users agree on global parameters:
Large prime integer or polynomial q
g being a primitive root mod q
Each user (ex. A) generates their key
Chooses a secret key (number): x
A < q
Compute their public key: y
A = g
xA
mod q
Each user makes public that key y
A
Primitive root of a prime number as one whose
powers modulo generate all the integers from
1 to p-1

34. Diffie-Hellman Key Exchange
34




Shared session key for users A & B is K
AB :
K
AB = g
xA.xB mod q
= y
A
xB mod q (which B can compute)
= y
B
xA mod q (which A can compute)
K
AB is used as session key in private-key
encryption scheme between Alice and Bob
if Alice and Bob subsequently communicate,
they will have the same key as before, unless
they choose new public-keys
attacker needs an x, must solve discrete log

35. Diffie-Hellman Example
35










Alice & Bob who wish to swap keys:
Agree on prime q=353 and g=3
Select random secret keys:
A chooses x
A=97, B chooses x
B=233
Compute respective public keys:
y
A=3
97 mod 353 = 40 (Alice)
y
B=3
233 mod 353 = 248 (Bob)
Compute shared session key as:
K
AB= y
B
xA mod 353 = 248
97 = 160 (Alice)
K
AB= y
A
xB mod 353 = 40
233 = 160 (Bob)

36. Key Exchange Protocols
36




Users could create random private/public D-H
keys each time they communicate
Users could create a known private/public D-H
key and publish in a directory, then consulted
and used to securely communicate with them
Both of these are vulnerable to a Man-in-the-
Middle Attack
Authentication of the keys is needed

37. Man-in-the-Middle Attack
37








Mallory prepares by creating two private / public
keys
Alice transmits her public key to Bob
Mallory intercepts this and transmits his first public
key to Bob. Mallory also calculates a shared key with
Alice
Bob receives the public key and calculates the shared
key (with Mallory instead of Alice)
Bob transmits his public key to Alice
Mallory intercepts this and transmits his second public
key to Alice. Mallory calculates a shared key with Bob
Alice receives the key and calculates the shared key
(with Mallory instead of Bob)
Mallory can then intercept, decrypt, re-encrypt,
forward all messages between Alice & Bob

38. Man-in-the-Middle Attack
38