3.0 Public Key
3.0 Public Key
3.0 Public Key
RSA
Private-Key Cryptography
traditional private/secret/single key
Public-Key Cryptography
probably most significant advance in the 3000
Public-Key Cryptography
public-key/two-key/asymmetric
Public-Key Cryptography
Public-Key Characteristics
Public-Key algorithms rely on two keys with
Secerecy
Authentication
Public-Key Cryptosystems
Public-Key Applications
can classify uses into 3 categories:
encryption/decryption (provide secrecy)
digital signatures (provide authentication)
key exchange (of session keys)
RSA
by Rivest, Shamir & Adleman of MIT in 1977
best known & widely used public-key scheme
based on exponentiation in a finite (Galois) field
RSA Use
to encrypt a message M the sender:
obtains public key of recipient KU={e,N}
computes: C=Me mod N, where 0M<N
RSA Example
1.
2.
3.
4.
5.
6.
7.
Exponentiation
can use the Square and Multiply Algorithm
a fast, efficient algorithm for exponentiation
concept is based on repeatedly squaring base
and multiplying in the ones that are needed
Exponentiation
modulus N=p.q
RSA Security
three approaches to attacking RSA:
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)
Factoring Problem
mathematical approach takes 3 forms:
factor N=p.q, hence find (N) and then d
determine (N) directly and find d
find d directly
currently believe all equivalent to factoring
have seen slow improvements over the years
as of Aug-99 best is 130 decimal digits (512) bit with GNFS
Timing Attacks
developed in mid-1990s
exploit timing variations in operations
eg. multiplying by small vs large number
or IF's varying which instructions executed
infer operand size based on time taken
RSA exploits time taken in exponentiation
countermeasures
use constant exponentiation time
add random delays
blind values used in calculations
Summary
have considered:
principles of public-key cryptography
RSA algorithm, implementation, security