RSA Algorithm

Views:
 
Category: Education
     
 

Presentation Description

RSA is a Public KEy Encrytion Algorithm which is used in network Securities

Comments

Presentation Transcript

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 !!!