The RSA Algorithm By:Sumanth.S.S :
The RSA Algorithm By:Sumanth.S.S RSA :
RSA 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
nb. exponentiation takes O((log n)3) operations (easy)
uses large integers (eg. 1024 bits)
security due to cost of factoring large numbers
nb. factorization takes O(e log n log log n) operations (hard) Features: :
Features: It is the easiest to understand as well as the most popular to implement
RSA obtains its security from the difficulty of factoring large numbers.
The algorithm is patented in North America (although algorithms cannot be patented elsewhere in the world) this is a source of legal difficulties in using the scheme Review of Encryption :
4 Review of Encryption A message in its original form (plaintext) is encrypted into an unintelligible form (ciphertext) by a set of procedures known as an encryption algorithm (cipher) and a variable, called a key; and the ciphertext is transformed (decrypted) back into plaintext using the decryption algorithm and a key. Public-Key Cryptosystems :
Public-Key Cryptosystems RSA Key Setup :
RSA Key Setup each user generates a public/private key pair by:
selecting two large primes at random - p, q
computing their system modulus N=p.q
note ø(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
e.d=1 mod ø(N) and 0≤d≤N
publish their public encryption key: PU={e,N}
keep secret private decryption key: PR={d,p,q} RSA Key Generation :
RSA Key Generation users of RSA must:
determine two primes at random - p, q
select either e or d and compute the other
primes p,q must not be easily derived from modulus N=p.q
means must be sufficiently large
typically guess and use probabilistic test
exponents e, d are inverses, so use Inverse algorithm to compute the other RSA Use :
RSA Use to encrypt a message M the sender:
obtains public key of recipient PU={e,N}
computes: C=Me mod N, where 0≤M<N
to decrypt the ciphertext C the owner:
uses their private key PR={d,p,q}
computes: M=Cd mod N
note that the message M must be smaller than the modulus N (block if needed) Why RSA Works :
Why RSA Works because of Euler's Theorem:
aø(n)mod N = 1
where gcd(a,N)=1
in RSA have:
N=p.q
ø(N)=(p-1)(q-1)
carefully chosen e & d to be inverses mod ø(N)
hence e.d=1+k.ø(N) for some k
hence :Cd = (Me)d = M1+k.ø(N) = M1.(Mø(N))q = M1.(1)q = M1 = M mod N RSA Security :
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 :
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
biggest improvement comes from improved algorithm
cf “Quadratic Sieve” to “Generalized Number Field Sieve”
barring dramatic breakthrough 1024+ bit RSA secure
ensure p, q of similar size and matching other constraints Timing Attacks :
Timing Attacks developed in mid-1990’s
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 How Fast is RSA? :
13 How Fast is RSA? By comparison, DES and other block ciphers are much faster than RSA. In software, DES is generally at least 100 times as fast as RSA.
In hardware, DES is between 1,000 and 10,000 times as fast, depending on the implementation.
Implementations of RSA will probably narrow the gap a bit in coming years, due to high demand, but DES will get faster as well. THANK YOU !!! :
THANK YOU !!!