1
81kviews
Explain RSA algorithm with an example.

hello need help for his book search graduate from rsa


1 Answer
4
658views

1.Most widely accepted and implemented general purpose approach to public key encryption developed by Rivest-Shamir and Adleman (RSA) at MIT university.

2.RSA scheme is block cipher in which the plaintext and ciphertext are integers between 0 and n-1 for same n.

3.Typical size of n is 1024 bits. i.e n<2.

4.Description of Algorithm:

  • The scheme developed by Rivest, Shamir and Adleman makes use of an expression with exponentials.
  • Plaintext is encrypted in block having a binary value than same number n.
  • Block Size $≤ \log_2 (n)$

    If block size=1 bits then, $2^1 ≤ n ≤ 2^i+1$

  • Encryption and decryption are of following form for same plaintext M and ciphertext C.

    $C=M^e mod n$

    $M= C^d mod n$

    $M = (M^e)^d mod n$

    $M = M^{ed} mod n$

  • Both sender and receiver must know the value of n.

  • The sender knows the value of e, and only the receiver knows the value of d.
  • Thus this is a public key encryption algorithm with a public key of PU= {c, n} and private key of PR= {d, n}.

5.RSA algorithm as shown below:

a) Key Genration :

  • Select p,q…….. p and q both are the prime numbers, p≠q.
  • Calculate n=p×q
  • Calculate q(n) = (p-1) (q-1)
  • Select integer….g(d ( (n), e)) =1 & 1< e < (n)
  • Calculate d; d= e-1 mod (n)
  • Public Key, PU= {e, n}
  • Private Key, PR ={d,n}

    b) Encryption :

  • Plaintext : m<n< p="">

  • Ciphertext: C

    c) Decryption:

  • Ciphertext: C

  • Plaintext : M= Cd mod n
  • Note 1 : (n) -> Euler’s totient function
  • Note 2: Relationship between C and d is expressed as:

    ed (mod (n))=1

    ed = 1 mod (n)

    d = $e^{-1}$ mod (n)

6.Example:

  • Key Generation :

    1. Select 2 prime numbers -> p=17 and q=11
    2. Calculate n = p×q =17 ×11=187
    3. Calculate = 16 × 10= 160 Select ‘e’ such that e is relatively prime to (n)=160 and e <
    4. Determine d such that :

      de =1 mod (n)

      d × 7 = 1 mod 160

$\hspace{2.7cm}\downarrow$

$\hspace{2.5cm}161$

$d = e^{-1} \ \ mod \ \ (n) [161 /7 = \ \ $

$div. (d) 23 \ \ \text{and remainder (mod) =1} \\ \hspace{2.5cm}d = 23$

  1. Then the resulting keys are public key :

    PU = {7, 187 }

    PR = {23, 187 }

    Let M=88 for encryption

    $C= 88^7 mod (187) \\ 88 mod 187 =88 \\ 88^2 mod 187 = 7744 mod 187 =77 \\ 88^4 mod 187 =59969536 mod 187 = 132$

    $88^7 mod 187$ $= (88^4 mod 187) × (88^2 mod 187) × (88 mod 187) mod 187 \\ =(132 × 77 × 88) mod 187 \\ = 894432 mod 187 \\ =11$

  • For Decryption :

    $M = C^d mod 187 \\ \hspace{0.5cm}= 11^{23} mod 187 \\ \hspace{1cm}11^1 mod 187 =11 \\ \hspace{1cm}11^2 mod 187 =121 \\ \hspace{1cm}11^4 mod 187 =14641 / 187 =55 \\ \hspace{1cm}11^8 mod 187 = 214358881 mod 187 =33 \\ \hspace{1cm}11^{23} mod 187$ $= (11^8 mod 187 × 11^8 mod 187 × 11^4 mod 187 × 11^2 mod 187 × 11^1 mod 187) mod 187 \\ =(33 × 33 × 55 × 81 × 11) mod 187 \\ = 79720245 mod 187 \\ =88$

Figure 5.4 Solution of Above example

$$\text{Figure 5.4 Solution of Above example}$$

Public key is (n,e) Private key is (n,d)


Please log in to add an answer.

Continue reading...

The best way to discover useful content is by searching it.

Search