Scribd Logo
Upload

Welcome to Scribd!

  • 297 views

    Public Key Cryptography and RSA

    Uploaded by

    ashwinikapse134891
    This document discusses public key cryptography and the RSA algorithm. It explains that public key cryptography uses two keys: a public key that can encrypt messages but only the corresponding private key can decrypt. The RSA algorithm generates these key pairs by choosing two large prime numbers, computing their product and related values to derive the public and private exponents. To encrypt a message, the sender uses the recipient's public key. Only the recipient's private key can decrypt the ciphertext back to plaintext. The security of RSA relies on the computational difficulty of factoring the product of the two primes.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd

    Public Key Cryptography and RSA

    Uploaded by

    ashwinikapse134891
    297 views24 pages
    This document discusses public key cryptography and the RSA algorithm. It explains that public key cryptography uses two keys: a public key that can encrypt messages but only the corresponding private key can decrypt. The RSA algorithm generates these key pairs by choosing two large prime numbers, computing their product and related values to derive the public and private exponents. To encrypt a message, the sender uses the recipient's public key. Only the recipient's private key can decrypt the ciphertext back to plaintext. The security of RSA relies on the computational difficulty of factoring the product of the two primes.

    Original Title

    ch09

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses public key cryptography and the RSA algorithm. It explains that public key cryptography uses two keys: a public key that can encrypt messages but only the corresponding private key can decrypt. The RSA algorithm generates these key pairs by choosing two large prime numbers, computing their product and related values to derive the public and private exponents. To encrypt a message, the sender uses the recipient's public key. Only the recipient's private key can decrypt the ciphertext back to plaintext. The security of RSA relies on the computational difficulty of factoring the product of the two primes.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    297 views24 pages

    Public Key Cryptography and RSA

    Uploaded by

    ashwinikapse134891
    This document discusses public key cryptography and the RSA algorithm. It explains that public key cryptography uses two keys: a public key that can encrypt messages but only the corresponding private key can decrypt. The RSA algorithm generates these key pairs by choosing two large prime numbers, computing their product and related values to derive the public and private exponents. To encrypt a message, the sender uses the recipient's public key. Only the recipient's private key can decrypt the ciphertext back to plaintext. The security of RSA relies on the computational difficulty of factoring the product of the two primes.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 24

    Public Key Cryptography and RSA

    Principles of Public-Key Cryptosystems


    Public-Key Cryptosystems

    Applications for Public-Key Cryptosystems


    Requirements for Public-Key Cryptography Public-Key Cryptanalysis

    Public-Key Cryptosystem
    Public-Key algorithms rely on two keys with the following characteristics:
    computationally infeasible to find decryption key knowing only algorithm &
    encryption key computationally easy to en/decrypt messages when the relevant

    (en/decrypt) key is known


    either of the two related keys can be used for encryption, with the other used for decryption (in some schemes)

    Public-Key Cryptosystems
    1. 2. 3. A public-key encryption scheme has six ingredients; (Refer fig. on next slide) Plaintext: This is the readable message or data that is fed into the algorithm as input. Encryption algorithm: The encryption algorithm performs various transformations on the plaintext. uses two keys a Public-Key, which may be known by anybody, and can be used to encrypt
    messages, and verify signatures
    a Private-Key, known only to the recipient, used to decrypt messages, and sign (create) signatures

    4.

    5.

    Ciphertext: This is the scrambled message produced as output. It depends on the plaintext and the key. For a given message, two different keys will produce two different ciphertexts. Decryption algorithm: This algorithm accepts the ciphertext and the matching key and produces the original plaintext.

    Public-Key Cryptography

    Public-Key Cryptosystems
    The essential steps are the following: 1. Each user generates a pair of keys to be used for the encryption and decryption of messages. 2. Each user places one of the two keys in a public register or other accessible file. This is the public key. The companion key is kept private. As Figure (last slide) suggests, each user maintains a collection of public keys obtained from others. 3. If Bob wishes to send a confidential message to Alice, Bob encrypts the message using Alice's public key. 4. When Alice receives the message, she decrypts it using her private key. No other recipient can decrypt the message because only Alice knows Alice's private key.

    Public-Key Cryptosystems: Secrecy

    Source A produces a message in plaintext, X=[ x1,x2,,xM ] On encryption Ciphertext is Y =[ Y1,Y2,,YM ]

    PUb, is Public key by B PUb, is Public key by B

    Y = E(PUb, X) X = D(PRb, Y)

    Public-Key Cryptosystems: Authentication

    Y = E(PRa, X) X = E(PUa, Y)

    Public-Key Cryptosystems: Secrecy and Authentication

    Z = E(PUb, E(PRa, X)) X = D(PUa, D(PRb, Z))

    Public-Key Applications
    Application/use of public-key systems are characterized by the use of two keys in the algorithm. Depending on the application, the sender uses either the sender's private key or the receiver's public key, or both, to perform some type of cryptographic function.

    So can classify uses of algorithms into 3 categories:


    encryption/decryption (provide secrecy) The sender encrypts a message with the recipient's public key. digital signatures (provide authentication) The sender "signs" a message with its private key. Signing is achieved by a cryptographic algorithm applied to the message or to a small block of data that is a function of the message. key exchange (of session keys) Two sides cooperate to exchange a session key. Several different approaches are possible, involving the private key(s) of one or both parties.

    Public-Key Applications
    some algorithms are suitable for all uses, others are specific to one

    Algorithm RSA Elliptic Curve Diffie-Hellman DSS

    Encryption/Decryption Yes Yes No No

    Digital Signature Yes Yes No Yes

    Key Exchange Yes Yes Yes No

    Requirements for Public-Key Cryptography


    1. conditions that Public-Key Cryptography algorithms must fulfill are; should be computationally easy for a party B to generate a pair; (public key PUb, private key PRb). should be computationally easy for a sender A, knowing the public key and the message to be encrypted, M, to generate the corresponding ciphertext: C = E(PUb, M) should be computationally easy for the receiver B to decrypt the resulting ciphertext using the private key to recover the original message: M = D(PRb, C) = D[PRb, E(PUb, M)] should be computationally infeasible for an adversary, knowing the public key, PUb, to determine the private key, PRb. The two keys can be applied in either order: M = D[PUb, E(PRb, M)] = D[PRb, E(PUb, M)]

    1.

    3.

    4.

    5.

    Security of Public-Key Schemes / Public-Key Cryptanalysis


    like private key schemes brute force exhaustive search attack is always theoretically possible with Public-Key schemes.
    Countermeasure : use too large keys (>512bits)

    security relies on a large enough difference in difficulty between

    easy (en/decrypt) and hard (cryptanalyse) problems


    Not impractical but computationally infeasible.

    RSA
    by Rivest, Shamir & Adleman of MIT in 1977 best known & widely used public-key scheme uses large integers (eg. 1024 bits) security due to cost of factoring large numbers Two parts: 1. 2. RSA Setup / Keys Generation RSA Use / Encryption-Decryption

    RSA Key Generation


    users of RSA must:
    determine two primes at random
    select either e or d

    p, q

    and compute the other

    primes

    p,q

    must not be easily derived from modulus

    n=p.q

    means must be sufficiently large


    typically by guess and use probabilistic test

    exponents

    e, d

    are multiplicative inverses, so use inverse

    algorithm to compute the other

    RSA Key Setup / Keys generation


    each user generates a public/private key pair by:
    selecting two large primes at random p, q (sufficiently large)

    computing their system modulus


    note (n)=(p-1)(q-1)

    n=p.q

    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 0dn .....(e is multiplicative inverse of d)

    publish their public encryption key: keep secret private decryption key:

    PU={e,n} PR={d,p,q}

    RSA Use / Encryption-Decryption


    note that the message M must be smaller than the modulus n

    To Encrypt a message M, the sender :


    obtains public key of recipient PU={e,n} computes: C = Me mod n, where 0M<n

    To Decrypt the ciphertext C, the owner :


    uses their private key PR={d,p,q}

    computes: M = Cd mod n

    RSA Summary

    RSA Example
    1. Select primes: p=17 & q=11

    2.
    3. 4. 5.

    Compute:
    Compute: Select e: Determine d:

    n = pq =1711=187
    (n)=(p1)(q-1)=1610=160 gcd(e, (n))= gcd(e,160)=1; choose e=7 d.e1 mod 160 and d < 160; .........since 237=161 ; PU={7,187} ; PR={23,17,11}

    So the value is d=23 6. 7. Publish public key Keep secret private key PU={e,n} PR={d,p,q}

    RSA Example cont


    sample RSA encryption/decryption is:
    given message encryption:
    C = 887 mod 187 = 11

    M = 88

    (where 88<187; i.e. M<n)

    decryption:
    M = 1123 mod 187 = 88

    Perform encryption and decryption using the RSA algorithm, as in Figure 9.6, for the following: p = 3; q = 11, e = 7; M = 5 p = 5; q = 11, e = 3; M = 9 p = 7; q = 11, e = 17; M = 8 p = 11; q = 13, e = 11; M = 7

    1. 2. 2. 3.

    Solutions: 1. n = 33; (n) = 20; d = 3; C = 26. 2. n = 55; (n) = 40; d = 27; C = 14. 3. n = 77; (n) = 60; d = 53; C = 57. 4. n = 143; (n) = 120; d = 11; C = 106.

    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

    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

    You might also like