Public Key Cryptography: Knapsack, RSA, Diffie-Hellman
CS 3IS3
Ryszard Janicki
Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada
Acknowledgments: Material based on Information Security by Mark Stamp (Chapters 4.1-4.4)
Ryszard Janicki
Public Key Cryptography: Knapsack, RSA, DH 1/16
Public Key Cryptography: Idea I
Two keys:
PRIVITE KEY known only to individual PUBLIC KEY available to anyone
A has private key kA and public key KA, while B has private key kB and public key KB . A message send by A and encrypted using kA and KB practically can only be decrypted when B will use kB and KA. How is it possible?
The private key k and the public key K are not random.
The public key K is a function of the private key k, i.e. K = f (k) for some function f (hence KA = f (kA) and KB =f(kB)).
The function f must have the property that for any K, finding f −1(K ) is practically impossible.
Ryszard Janicki
Public Key Cryptography: Knapsack, RSA, DH 2/16
Public Key Cryptography: Idea II
Conditions:
1 It must be computationally easy to encipher or decipher a
message given the appropriate key.
2 It must be computationally infeasible to derive the private key
from the public key.
3 It must be computationally infeasible to determine the private
key from a chosen plaintext attack.
Ryszard Janicki
Public Key Cryptography: Knapsack, RSA, DH 3/16
Public Key Cryptography: Idea III
Two keys, one to encrypt, another to decrypt Alice uses Bob’s public key to encrypt
Only Bob’s private key decrypts the message
Based on “trap door, one way function”
“One way” means easy to compute in one direction, but hard to compute in other direction
Example: Given p and q, product N = pq easy to compute, but hard to find p and q from N (for large primes p and q) “Trap door” is used when creating key pairs (private, public).
Encryption
Suppose we encrypt M with Bob’s public key
Bob’s private key can decrypt C to recover M
There must be some relationship between private and public keys!
Digital Signature
Bob signs by “encrypting” with his private key
Anyone can verify signature by “decrypting” with Bob’s public key
But only Bob could have signed
Like a handwritten signature, but much better. . .
Ryszard Janicki
Public Key Cryptography: Knapsack, RSA, DH 4/16
Knapsack Cryptosystem: Basis–Subset Sum/Knapsack
Subset Sum problem: given a set of n weights W1, . . . , Wn and a sum S, find a subset Wi1,…,Wik such that
Wi1 +…+Wik =S.
Example. Weights: 62, 93, 26, 52, 166, 48, 91, 141, S = 302, solution: 62+26+166+48=302
The Subset Sum problem is NP-complete. In cryptography it is usually called (general) knapsack problem (GK, historical reasons).
The real Knapsack problem is: given a list (repetitions allowed) of n weights W1,…,Wn and a capacity C, find a subset Wi1,…,Wik such that Wi1 +…+Wik is maximal and smaller or equal than C.
Ryszard Janicki
Public Key Cryptography: Knapsack, RSA, DH 5/16
Knapsack Cryptosystem: Superincreasing Knapsack (SIK)
SIK – each weight greater than the sum of all previous weights
Example: Weights (2, 3, 7, 14, 30, 57, 120, 251), S = 186, solution: 120 + 57 + 7 + 2 = 186, a simple efficient algorithm that works from the largest to the smallest weight.
Knapsack Cryptosystem:
1 Generate superincreasing knapsack (SIK)
2 Convert SIK to “general” knapsack (GK)
3 Public Key: GK
4 Private Key: SIK and conversion factor
Goal. . .
Easy to encrypt with GK
With private key, easy to decrypt (solve SIK)
Without private key,Trudy has no choice but to try to solve GK
Ryszard Janicki
Public Key Cryptography: Knapsack, RSA, DH 6/16
Modular Arithmetic: m−1 mod n
Standardlym−1 =a ⇐⇒ m·a=1. Suppose m mod n = a. Then
m−1 modn=b⇐⇒abmodn=1
Example: m=41,n=491. Then41mod491=41. We have to find b that 41 · b mod 491 = 1, i.e.
41·b = 491·i +1 for some i.
Note that b = 12 works as 41 · 12 = 492 = 491 · 1 + 1.
For example an efficient ‘Extended Euclidean Algorithm’ can be used to solve this problem.
Hence 41−1 mod 491 = 12
Ryszard Janicki
Public Key Cryptography: Knapsack, RSA, DH 7/16
Knapsack Cryptosystem: Description by Example
Start with (2, 3, 7, 14, 30, 57, 120, 251) as the SIK
Choose m = 41 and n = 491 (m, n relatively prime, n exceeds sum of elements in SIK)
Thenm−1 modn=41−1 mod491=12
Private Key: SIK = (2, 3, 7, 14, 30, 57, 120, 251), m = 41, n=491andm−1 modn=12.
Compute “general” knapsack 2 · 41 mod 491 = 82
3 · 41 mod 491 = 123
7 · 41 mod 491 = 287
14 · 41 mod 491 = 83
30 · 41 mod 491 = 248
57 · 41 mod 491 = 373
120 · 41 mod 491 = 10
251 · 41 mod 491 = 471
“General” knapsack: (82, 123, 287, 83, 248, 373, 10, 471) Public Key: GN = (82, 123, 287, 83, 248, 373, 10, 471),
n = 491.
Ryszard Janicki
Public Key Cryptography: Knapsack, RSA, DH 8/16
Private Key: SIK = (2, 3, 7, 14, 30, 57, 120, 251), m = 41, n=491andm−1 modn=12.
Public Key: GN = (82, 123, 287, 83, 248, 373, 10, 471),
n = 491.
Encryption. Plaintext M = 150 = 10010110 82 123 287 83 248 373 10 471
10010110
82 + 83 + 373 + 10 = 548
Decryption. Private key is used.
548 · 12 = 193 mod 491
The solution (easy) of SIK for S = 193 is 193 = 2 + 14 + 57 + 120.
◦ Now we transform the list SIK into a binary sequence with 1 for elements in sum and 0 for elements not in sum.
2 3 7 14 30 57 120 251
10010110
◦ The result is the paintext M = 150 = 10010110.
Unfortunately this knapsack cryptosystem is insecure. It was broken in 1983 with Apple II computer! But there are better knapsack cryptos.
Ryszard Janicki
Public Key Cryptography: Knapsack, RSA, DH 9/16
RSA is the gold standard in public key cryptography
Invented by Clifford Cocks and, independently by Ron Rivest, Adi Shamir, and Leonard Adleman.
Let p and q be two large prime numbers Let N = pq be the modulus
Choose e relatively prime to (p − 1)(q − 1)
Two integers are relatively prime if there is no integer greater than one that divides them both (that is, their greatest common divisor is one). For example, 12 and 13 are relatively prime, but 12 and 14 are not.
Find d such that ed = 1 mod (p − 1)(q − 1) Public key is (N, e)
Private key is d
Ryszard Janicki
Public Key Cryptography: Knapsack, RSA, DH 10/16
RSA: Algorithm
Public Key is (N,e) and Private Key is d
Message M is treated as a number
To encrypt plaintext M we compute C = Me mod N
To decrypt ciphertext C, we compute M = Cd mod N
If an attacker can factor N = pq, she can use e to (relatively) easily find d since ed = 1 mod (p − 1)(q − 1)
So, factoring the modulus breaks RSA. However, so far no reasonably algorithm has been found for N = pq and huge primes p, q. There are other approaches for breaking RSA, but so far none is considered successful.
RSA works because of the following fact:
Theorem
M=(Me modN)d modN
A proof is in the textbook.
Ryszard Janicki
Public Key Cryptography: Knapsack, RSA, DH 11/16
Simple RSA Example
Select “large” primes p = 11, q = 3
Then N = pq = 33 and (p − 1)(q − 1) = 20
Choose e = 3 (relatively prime to 20 = 2 · 2 · 5)
Find d such that ed = 1 mod 20, in this case d = 7 works Public Key: (N, e) = (33, 3) and Private Key: d = 7
Suppose message to encrypt is M = 8
Ciphertext C is computed as
C=Me modN=83=512=17mod33=17
Decrypt C to recover the message M by
M=Cd modN=177 =410,338,673=
12, 434, 505 · 33 + 8 = 8 mod 33 = 8
RSA does make sense only if N is at least 1024-bits (more than 300 decimal digits), often 2048-bits or even more! Operations involving long integers, especially modular exponentiation of large numbers with large exponents are very time consuming and tricky. Many special techniques have been invented to make it more efficient, See textbook.
Ryszard Janicki
Public Key Cryptography: Knapsack, RSA, DH 12/16
Diffie-Hellman Key Exchange
Invented by Malcolm Williamson, and, independently, by Whitfield Diffie and Martin Hellman
A “key exchange” algorithm
Used to establish a shared symmetric key Not for encrypting or signing
Based on discrete logarithm problem:
Given: g,p, and gk mod p, find: exponent k
Discrete logarithms are quickly computable in a few special cases. However, no efficient method is known for computing them in general.
Ryszard Janicki
Public Key Cryptography: Knapsack, RSA, DH 13/16
Diffie-Hellman: Algorithm
Let p be prime, let g be a generator. p and g are public. Foranyx∈{1,2,…,p−1}thereisnsuchthatx=gn modp
Alice selects her private value a
Bob selects his private value b
Alice sends ga mod p to Bob b
Bob sends gDimfofdipet-oHAliecellman
Both compute shared secret, gab mod p. Public: g and p
Shared secret can be used as symmetric key.
Private: Alice’s exponent a, Bob’s exponent b
Public: g and p. Private: Alice’s: a, Bob’s: b
ga mod p gb mod p
Alice, a
Bob, b
ba ba ab
Alice computesb(ga ) = g = gab mod p
Alicecomputes(g ) modp=g modp a ba b ab ab
BBoobbcocmompuptuetse(sg(g))m=odgp=mogdpmodp
They can use K = g mod p as symmetric key They can use K = g mod p as symmetric key
ab
ab
Part 1 Cryptography
Ryszard Janicki
Public Key Cryptography: Knapsack, RSA, DH 14/16
124
Diffie-Hellman: Why It Works
Suppose Bob and Alice use Diffie-Hellman to determine symmetric key K = gab mod p
An attacker Trudy can see ga mod p and gb mod p. But ga modp·gb modp=ga+b modp̸=gab modp.
If Trudy can find a or b, she gets K
If Trudy can solve discrete logarithm problem, she can find a
or b
However, no efficient method is known for computing them in general, and it looks as it is especially infeasible for huge primes p.
Ryszard Janicki
Public Key Cryptography: Knapsack, RSA, DH 15/16
Diffie-Hellman
Diffie-Hellman: Man-In-the-Middle (MiM) Attack
Subject to man-in-the-middle (MiM) attack
ga mod p gt modp
gt mod p gb modp
Alice, a
Trudy, t
Bob, b
Part 1 Cryptography 126 How to prevent MiM attack?
at at
mod p with Alice
Trudy shares secret g
An attacker Trudy shares secret g mod p with Alice
Trudy shares secret gbt mod p with Bob Trudy shares secret gbt mod p with Bob
Alice and Bob don’t know Trudy is MiM Alice and Bob don’t know Trudy is MiM
Encrypt Diffe-Hellman exchange with symmetric key Encrypt Diffie-Hellman exchange with public key Sign Diffie-Hellman values with private key
You MUST be aware of MiM attack on Diffie-Hellman Key Exchange. We will discuss this issue later at the end of this course.
Ryszard Janicki
Public Key Cryptography: Knapsack, RSA, DH 16/16