1
Explain RSA algorithm with an example.
rsa algorithm • 71k  views
1

hello need help for his book search graduate from rsa

4

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}$$

4

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

Please log in to add an answer.

Continue reading

Find answer to specific questions by searching them here. It's the best way to discover useful content.

Find more