RSA & MD5 algorithm

RSA & MD5 algorithm

• 1.
  RSA ALGORITHM & MD5 ALGORITHM By SivaRushi
• 2.
  INTRODUCTION TO RSA RSA Algorithm was discovered by a group of three scientists namely Ron Rivest,Adi Shamir and Len Adleman and was first published in 1978.  The RSA scheme is a block cipher in which the plain text and cipher text are integers between 0 and n-1 for some n.  A Typical size of n is 1024 bits or 309 decimal digits.  This is a public key encryption scheme. 2
• 3.
   In thisscheme two pairs of integers {e, n} and {d, n} are used. First of them i.e. {e.n} is called the RSA public key and the other one i.e. {d, n} is called the RSA secret key.  The sender uses the public key and encrypts the message say M into cipher text as –  C = M^e mod n.  Where C is the cipher text and M is the message or the plane text  At the receiving end the receiver accept the cipher text C and decrypt the C into M using secret key {d, n}-  M = C^d mod n. 3
• 4.
  EXAMPLE:  Let ,e=3, d=7, n=33.  Suppose the message is ‘SUN’ and we use the numeric values of the characters according to their serial in alphabets. 4 Plaintext Ciphertext(C) after decryption Sym num M^3 M^3 mod33 C^7 C^7mod33 sym S 19 6859 28 13492928512 19 S U 21 9261 21 1801088541 21 U N 14 2744 5 78125 14 N
• 5.
  KEY GENERATION Each usergenerates 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: KU={e,N}  keep secret private decryption key: KR={d,p,q} 5
• 6.
  To encrypt amessage M the sender:  obtains public key of recipient KU={e,N}  computes: C=Me mod N, where 0≤M<N  to decrypt the ciphertext C the owner:  uses their private key KR={d,p,q}  computes: M=Cd mod N  note that the message M must be smaller than the modulus N (block if needed) 6
• 7.
   ap-1 modp = 1  where p is prime and gcd(a,p)=1  also known as Fermat’s Little Theorem  useful in public key and primality testing  when doing arithmetic modulo n  complete set of residues is: 0..n-1  reduced set of residues is those numbers (residues) which are relatively prime to n  eg for n=10,  complete set of residues is {0,1,2,3,4,5,6,7,8,9}  reduced set of residues is {1,3,7,9} 7
• 8.
   to computeø(n) need to count number of elements to be excluded  in general need prime factorization, but for  p (p prime) ø(p) = p-1  for p.q (p,q prime) ø(p.q) = (p-1)(q-1)  Eg:  ø(37) = 36  ø(21) = (3–1)×(7–1) = 2×6 = 12 8
• 9.
   a generalisationof Fermat's Theorem  aø(n)mod N = 1  where gcd(a,N)=1 Eg:  a=3;n=10; ø(10)=4;  hence 34 = 81 = 1 mod 10  a=2;n=11; ø(11)=10;  hence 210 = 1024 = 1 mod 11 9
• 10.
   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 10
• 11.
   Select primes:p=17 & q=11  Compute n = pq =17×11=187  Compute ø(n)=(p–1)(q-1)=16×10=160  Select e : gcd(e,160)=1; choose e=7  Determine d: de=1 mod 160 and d < 160 Value is d=23 since 23×7=161= 10×160+1  Publish public key KU={7,187}  Keep secret private key KR={23,17,11} 11 RSA EXAMPLE
• 12.
   sample RSAencryption/decryption is:  given message M = 88 (nb. 88<187)  encryption:  C = 887 mod 187 = 11  decryption:  M = 1123 mod 187 = 88 12
• 13.
  APPLICATIONS  RSA iswidely used for encryption and decryption in message communication for making the communication secure.  It is used for digital signature.  It is used for key distribution.  RSA is used in e-commerce and remote banking. 13
• 14.
  CONCLUSION  After thestudy, I find that RSA is a powerful and most widely used scheme for encryption / decryption and digital signature. It is more secure than that of DES and others. But as we know that the key length for secure RSA use has increased over recent years, and this has put a heavier processing load on applications using RSA. This burden has ramifications, especially for electronic commerce sites that conduct large numbers of transactions.  Recently, a competing system has begun to challenge RSA: elliptic curve cryptography (ECC). 14
• 15.
   The principalattraction of ECC, compared to RSA, is that it appears to offer equal security for a far smaller key size; thereby reducing processing overhead but the confidence level in ECC is not yet as high as that is in RSA. Also RSA is fundamentally easier to explain than that of ECC. 15
• 16.
  INTRODUCTION TO MD5 MD5 Message Digest is a widely used hash technique, such that it will produce 128-bit hash value we need to convert the input data into bytes in order to convert it to hash value. This is useful in many security applications and it ensures data integrity. 16
• 17.
  ALGORITHM CHARACTERISTICS:-  Message-Digest(Fingerprint) algorithms are special functions which transform input of (usually) arbitrary length into output (so-called "message digest") of constant length. These transformation functions must fulfill these requirements:  no one should be able to produce two different inputs for which the transformation function returns the same output  no one should be able to produce input for given pre-specified output 17
• 18.
   Message-Digest algorithmsserve in digital signature applications for guaranteeing consistency (integrity) of data. Commonly used model is as follows (message-digest in cooperation with asymmetric cryptography): Sender creates input message (M) and computes its message digest . Then he uses his private key and encrypts message digest. Encrypted message digest is attached to the input message and the whole message is sent to receiver. Receiver gets the message and extracts the encrypted message digest. Then he computes his own message digest of the received message. He also decodes received message digest with sender's public key and gets decoded message digest. Then he compares both message digests. When both message digests are equal, the message was not modified during the data transmission. 18
• 19.
  MD5 ALGORITHM DESCRIPTION MD5 algorithm takes input message of arbitrary length and generates 128-bit long output hash. MD5 hash algorithm consist of 5 steps. Step 1. Append Padding Bits Step 2. Append Length Step 3. Initialize MD Buffer Step 4. Process Message in 16-Word Blocks Step 5. Output 19
• 20.
  MD5 ALGORITHM USES MD5 is commonly used hash algorithm. It can be found in many implementations (available on some Unix-based system as utility md5; class MD5CryptoServiceProvider in Microsoft's .NET Framework (namespace System.Security.Cryptography).example implementation in Visual C++ or JavaScript, etc.). It is used sometimes as file CRC function (Napster...) or one-way cipher in authentication operations (for storing user password hash).  MD5 is also used in conjunction with other cryptographic methods in digital signature applications or in protocols like SSL and others. 20
• 21.
  CONCLUSION:-  Both producethe MD5 hash value. The difference between the two samples is the leading bit in each nibble has been flipped. Hash value is not encrypted one exactly, so you can’t retrieve the actual value. 21