Transcript RSA - people.vcu.edu - Virginia Commonwealth University

Network and Communications
Network Security
Department of Computer Science
Virginia Commonwealth University
Topics

Elements of Number Theory
 Public-Key Cryptography
– Principles
– Knapsack Algorithm
– RSA algorithm
– Computational aspects
– Diffie – Hellman Key Exchange
Elements of Number Theory
Modular Arithmetic
Modular Arithmetic is commutative, associative and
distributive
(a+b) mod n = ((a mod n) + (b mod n)) mod n
(a*b) mod n = ((a mod n ) * (b mod n)) mod n
(a*(b+c)) mod n = (((a*b) mod n) + ((a*c) mod n)) mod n
23 = 11 (mod 12)
A = b (mod n) if a = b+kn for some integer k
Why Modular Arithmetic?
Easy to compute with computer! Since it restricts the
range of all intermediate values and result.
For a k bit modulus, n, operation, the intermediate
results of any +, -, *,/ will not be more than 2 k bit
long
Ex. ax mod n
(a*a*a*a*a*a*a*a) mod n
(a2 mod n)2 mod n)2 mod n
25 = 110012
What id x is not
a power of 2?
a25 mod n = (a16 * a8 * a) mod n = ((a2*a)8 *a) mod n
a25 mod n ?
= ((((((a2 % n)*a) mod n)2) mod n)2) mod n)2 ) mod n*a) mod n
= (a2*a)2)2)2 *a) mod n
Prime and Relatively Prime Numbers
Any integer p>1 is a prime number if its
only divisors are ±1 and ±p.
Two integers a and b are relatively prime if
they have no prime factors in common, that
is, if their only common factor is 1.
Equivalently, a and b are relatively prime if
gcd(a,b)=1
Prime numbers

2
 73
 2521
 1365347734339
 2756839-1
 >2512
Fermat’s Theorem
If p is prime and a is a positive integer not
divisible by p, then
ap-1 Ξ 1 mod p
Alternatively,
ap Ξ a mod p
Euler’s Totient Function

Euler’s Totient Function Φ(n) is the number
of positive integers less than n and
relatively prime to n.
Euler’s Theorem
For every a and n that are relatively prime,
if GCD(a,n) = 1, then
aΦ(n) Ξ 1 mod n
Alternatively,
aΦ(n)+1 Ξ a (mod n)
Inverse Modulo a Number

What is the inverse of 4 in modulo 7 system
 4*x = 1 (mod 7)
 Inverse of 2 , modulo 14
 In general a-1 = x (mod n)
if a & n are
relatively prime
Inverse of 5, modulo7?
Φ(n)
a
mod n Ξ 1
Since Φ(n) = 6,
Φ(n)-1
 x= a
mod n
6-1
5
X=5
mod 7 = 5 mod 7 = 3
Primitive Root
Primitive Root of a prime number p is one
whose powers generate all integers from 1
to p-1.
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
integers from 1 to (p-1) in some
7?
permutation.
5
0
1
2
3
4
3 =1 3 =33 =2 3 =63 =43 =5
Public-Key Cryptography
Public Key Cryptography

All Cryptographic Systems before this were based
on Substitutions and Permutations
 Public-key cryptography is based on mathematical
Functions
 Asymmetric – Uses two separate keys
 Use of two keys has profound consequences in :
– Confidentiality
– Authentication
– Key Distribution
Public-Key Encryption: Myths
and Realities






Myth: More Secure than conventional encryption
Reality: Security of any encryption depends on key length
and computational effort required in breaking a cipher
Myth: General purpose technique that has made
conventional encryption obsolete
Reality: Public-key cryptography has lot of computational
overhead that makes it impractical in many applications
Myth: Facilitates easy key distribution
Reality: Requires some protocol, generally involving a
central agent
Public-key Cryptography: Basics
Six ingredients of the Scheme
 Plaintext, Public Key, Private Key, Encryption algorithm,
Decryption Algorithm, Ciphertext
Essential Steps (for communication from A to B at each end
System/User)
 A and B Generate a pair of keys (public, private)
 A and B publish public key in a public register/file
 A encrypts message using B’s public key (for
confidentiality) or using A’s private key (for
authentication)
 B decrypts message using B’s private key (for
confidentiality) or using A’s public key (for authentication)
Confidentiality Using Public-key
System
Authentication Using Public-key
System
Confidentiality and Authentication
Using Public-key System
Conventional and Public-Key
Encryption: A Comparison
Conventional Encryption
Public Key Encryption
Needed to Work:
1. The same algorithm with the same
key is used for encryption and
decryption.
2. The sender and receiver must share
the algorithm and the key.
Needed to Work:
1. One algorithm is used for encryption and
decryption with a pair of keys, one for
encryption and one for decryption.
2. The sender and receiver must each have
one of the matched pair of keys (not the
same one).
Needed for Security:
1. The key must be kept secret.
2. It must be impossible or at least
impractical to decipher a message
if no other information is available.
3. Knowledge of the algorithm plus
samples of ciphertext must be
insufficient to determine the key.
Needed for Security:
1. One of the two keys must be kept secret.
2. It must be impossible or at least
impractical to decipher a message if no
other information is available.
3. Knowledge of the algorithm plus one of
the keys plus samples of ciphertext must
be insufficient to determine the other key.
Requirements for Public-Key
Cryptography
1.
2.
3.
Computationally easy for a party B to
generate a pair (public key KUb, private
key KRb)
Easy for sender to generate ciphertext:
Easy for the receiver to decrypt ciphertect
using private key:
C  EKUb (M )
M  DKRb (C )  DKRb [ EKUb (M )]
Requirements for Public-Key
Cryptography (contd.)
4.
5.
6.
Computationally infeasible to determine private
key (KRb) knowing public key (KUb)
Computationally infeasible to recover message
M, knowing KUb and ciphertext C
Either of the two keys can be used for
encryption, with the other used for decryption:
M  DKRb [ EKUb ( M )]  DKUb [ EKRb ( M )]
Public-Key Cryptographic
Algorithms

KnapSack, Diffie-Hellman and RSA
 Diffie-Hellman
– Exchange a secret key securely
– Based on difficulty of discrete logarithms

RSA - Ron Rivest, Adi Shamir and Len
Adleman at MIT, in 1977.
– RSA is a block cipher
– Based on difficulty of prime factorization
– The most widely implemented
Knapsack Algorithm

Given a set of values M1, M2, ..Mn and a
sum S compute bi such that
 S = b1M1+ b2M2 + … + bnMn
5, 6, 11 What if S = 24?
 1, 5, 6, 11, 14, 20 S = 22
 Super increasing Knapsack
 {1,3,13,27,52}
Example








{2,3,6,13,27,52}
Fins n > sum of all weight and multiplier such that
gcd(m,n) = 1
Do multiplication (31,105)
2*31 mod 105 = 62,…
31-1 mod 105 ?
– {62,93,81,88,102,37}
011000110110010010101..
31-103 mod 105
011000 = 93 +81 = 174 = C
174 *61 mod 105 = 9 = 3+6 = 011000
RSA Algorithm: Basics

Block Cipher
– Block has binary value < n = pq=> Block Size ≤ log2(n)
– Block Size k bits: 2k<n ≤2k+1





M: message; C: ciphertext;
{e,n}: public key; {d,n}: private key
Both Sender and receiver know n;
Sender knows e, receiver knows d.
C = Me mod n
M = Cd mod n = (Me)d mod n = Med mod n
Requirements:
– Possible to find e,d,n s.t. Med = M mod n for all M<n
– Relatively easy to compute Me and Cd for all M<n
– Infeasible to determine d given e and n
Relationship between d and e


Required: Med = M mod n
Corollary to Euler’s theorem
– Given two prime numbers p and q and two integers m
and n such that n=pq and 0<m<n and an arbitrary
integer k,: mkΦ(n)+1 = mk(p-1)(q-1)+1 Ξ m mod n, where
Φ(n) is the Euler Totient Function

From the above, ed = KΦ(n)+1 satisfies the
requirement
 ed =1 mod Φ(n)
d Ξ e-1 mod Φ(n)
 e and d are multiplicative inverses mod Φ(n)
The RSA Algorithm –
Key Generation
1.
2.
3.
4.
5.
6.
7.
Select p,q
Calculate n = p x q
Calculate
Select integer e
Calculate d
Public Key
Private key
p and q both prime
(n)  ( p  1)( q  1)
gcd( (n), e)  1; 1  e  (n)
1
d  e mod (n)
KU = {e,n}
KR = {d,n}
The RSA Algorithm Encryption

Plaintext:
M<n

Ciphertext:
C = Me (mod n)
The RSA Algorithm Decryption

Ciphertext:
C

Plaintext:
M = Cd (mod n)
Example of RSA Algorithm
For this example, they keys were generated as follows:
1.Select two prime numbers, p = 7 and q = 17
2.Calculate n = pq = 7 x 17 = 119
3.Calculate Φ(n) = (p-1)(q-1) = 96
4.Select e such that e is relatively prime to Φ(n)=96 and less than Φ(n); in this
case e = 5
5.Determine d such that de = 1 mod 96 and d< 96. The correct value is d=77,
because 77 x 5 = 385 = 4 x 96 + 1.
The resulting keys are public key KU = {5, 119} are private key KR= {77, 119}.
The example shows the use of these keys for a plaintext input of M = 19.
Computational Aspects

Raising an integer to an integer power mod n (Me,
Cd)
– fast exponentiation algorithms
– Useful property of modular arithmetic:
(a x b) mod n = [(a mod n) x (b mod n)] mod n

Finding Large Prime Numbers (p,q)
– Currently, no useful techniques to yield arbitrarily large
primes
– Generate a random odd number and test for primality


Probabilistic algorithms (ex Miller-Rabin algorithm)
Selecting e(d) and calculating d(e)
– Extended Euclid’s algorithm
Security of RSA
Three kinds of attacks:
 Brute force: trying all possible private keys
 Mathematical attacks: approaches to factoring the product
of two primes
Suggestions:
– p,q differ in length by only a few digits. (p,q order of 1075 to 10100)
– Both (p-1) and (q-1) should contain a large prime factor
– gcd(p-1, q-1) should be small

Timing attacks: based on running time of decryption
algorithm
Countermeasures:
– Ensure constant exponentiation time
– Add random delay to exponentiation algorithm
– Bliding (multiply ciphertext by a random number before
exponentiation)
Diffie - Hellman Key Exchange
Scheme

First published public-key algorithm (1976)
 Based on difficulty of computing Discrete
Logarithms
 Enables two users to exchange a key
securely to be used for subsequent message
encryption
 Several commercial products based on this
technique
Diffie - Hellman Key Exchange
Algorithm
Diffie – Hellman Key Exchange
Operation

q, α are required to be known ahead of time ( or A could
pick q and α and include in the first message)
Diffie – Hellman Exchange
Example

Key exchange is based on the use of prime number
q=97 and a primitive root of 97, in this case α = 5.
 A and B select secret keys XA=36 and XB=58,
respectively.
 Each computes its public key:
K = (YB)XA mod 97 = 4436 = 75 mod 97
K = (YA)XB mod 97 = 5058 = 75 mod 97
 From XA, XB, an attacker cannot easily compute 75.
Diffie – Hellman Exchange
Example

Key exchange is based on the use of prime number
q=97 and a primitive root of 97, in this case α = 5.
 A and B select secret keys XA=36 and XB=58,
respectively.
 Each computes its public key:
K = (YB)XA mod 97 = 4436 = 75 mod 97
K = (YA)XB mod 97 = 5058 = 75 mod 97
 From [50,44], an attacker cannot easily compute 75.
For any integer ‘b’ and a primitive root ‘a’ of prime
number ‘p’, one can find a unique exponent ‘i’
such that
b = ai mod p where 0 ≤ i ≤ (p-1)
The exponent ‘i’ is called the Discrete
Logarithm or index of b for the base a mod p.
Given a,i, and p, it is straightforward to
compute b.
Given a,b, and p, it is computationally
infeasible to compute the discrete logarithm i.