Public key algorithm

Public key algorithm

1. Public Key Algorithm By Pankaj Jatav (110101168) Rahul Kumar (120101813) Rahul Aggarwal (110101189) Prateek Pandey (110101180)

2. Cryptography The art of the Secret (crypto-) writing (-graphy). It enables you to store information or transmit it across insecure networks, so that it cannot be read by anyone except the intended recipient.

3. TERMINOLOGY Plain Text:- The message or data that is to be transmitted over the network. Cipher :- A mapping algorithm which is used to encrypt or decrypt the message. Key : A key is a number (or a set of numbers) that the cipher implements to encrypt or decrypt a message. To encrypt a message we need to convert the plaintext to ciphertext using an encryption algorithm and encryption key whereas to decrypt the message we require a decryption algorithm and a decryption key to reveal the plaintext

4. Symmetric Key Cryptography Symmetric-key cryptography refers to encryption methods in which both the sender and receiver share the same key (or, less commonly, in which their keys are different, but related in an easily computable way). This was the only kind of encryption publicly known until June 1976. 5

5. Symmetric Key Cryptography System

6. Asymmetric Key Cryptography Asymmetric cryptography or public-key cryptography is cryptography in which a pair of keys is used to encrypt and decrypt a message so that it arrives securely. Initially, a network user receives a public and private key pair from a certificate authority. Any other user who wants to send an encrypted message can get the intended recipient's public key from a public directory. They use this key to encrypt the message, and they send it to the recipient. When the recipient gets the message, they decrypt it with their private key, which no one else should have access to. 7

7. ASYMMETRIC KEY Cryptography System

8. Why use Public Key Algorithms??

9. ASYMMETRIC KEY Cryptography System

10. Proposed by Diffie and Hellman in 1976. The encryption algorithm must meet 3 requirements: D(E(P))=P It is Exceedingly difficult to deduce D from E. E cannot be broken by a chosen plaintext attack. Public Key Algorithms

11. Public key blueprint The keys used to encrypt and decrypt are different . Anyone who wants to be a receiver needs to “publish” an encryption key, which is known as the public key . Anyone who wants to be a receiver needs a unique decryption key, which is known as the private key . It should not be possible to deduce the plaintext from knowledge of the ciphertext and the public key. Some guarantee needs to be offered of the authenticity of a public key. 13

12. Public Key Algorithms Algorithms Satisfying all three requirements are: RSA ElGamal

13. RSA

14. RSA Choose two large prime numbers p, q. (e.g., 1024 bits each) Compute n = p*q and z = (p-1)(q-1). Choose d (with d<n) that has no common factors with z. (e, z are “relatively prime”). Choose e such that ed-1 is exactly divisible by z. (in other words: ed mod z = 1 ).

15. RSA: Encryption, decryption Given ( n,e ) and ( n,d ) as computed above Dividing Plain Text into Blocks: 0<=P<n To encrypt message P (<n) , compute To decrypt received bit pattern, C , compute Public key is ( n,e ). Private key is ( n,d). C = M (mod n) e M = C (mod n) d

16. RSA example: Let us choose p=3 and q=11 . Then n=33 and z=20 . d=7 (so d, z relatively prime). e=3 (so ed-1 exactly divisible by z). M M e C = M mod n e 19 6859 28 C M = C mod n d 28 13492928512 19 C d Encrypt: Decrypt: Encrypting messages:

17. RSA Issues RSA is computationally intense. Commonly used key lengths are 1024 bits The plain text should be smaller than the key length The encrypted text is of the same size as the key length Generally used to encrypt secret keys. Basis: Factoring a big number is hard

18. Summary Public key systems replace the problem of distributing symmetric keys with one of authenticating public keys Public key encryption algorithms need to be trapdoor one-way functions RSA is a public key encryption algorithm whose security is believed to be based on the problem of factoring large numbers ElGamal is a public key encryption algorithm whose security is believed to be based on the discrete logarithm problem RSA is generally favoured over ElGamal for practical rather than security reasons RSA and ElGamal are less efficient and fast to operate than most symmetric encryption algorithms because they involve modular exponentiation DH key exchange is an important protocol on which many real key exchange protocols are based

19. Thank You

20. Attacks on RSA Smooth Number Attack: If you sign m1 and m2 S 1 = m d 1 mod n S 2 = m 2 d mod n Attacker can sign m 1 m 2 , m 1 /m 2 , m 1 2 , m 1 j m 2 k Easy to do if mi’s are small (smooth) numbers. Cube Root Problem of RSA If public exponent e=3: h de mod n = h h d mod n = h 1/3 Simply compute h 1/3 mod n