Question

1. Derive the RSA encryption method, justifying your steps from t sults. 2. Encrypt 0002 with public key (7,77). Find the decryption key

Answer 1

1.RSA encryption method:-

Here,I am justify my steps in following order below,

The implementation of RSA makes heavy use of modular arithmetic, Euler's theorem, and Euler's totient function.

steps to follow,

1. First, the receiver chooses two large prime numbers p and q . Their product, , will be half of the public key.
2. The receiver calculates ϕ=(p−1)(q−1) and chooses a number e relatively prime to ϕ(pq) . In practice, e 2¹⁶ +1 = 65537 is often chosen to be , though it can be as small as 3 in some cases. e will be the other half of the public key.
3. The receiver calculates the modular inverse d of e modulo ϕ(n) . In other words, ed≡1 (mod ϕ(n)) . d is the private key.
4. The receiver distributes both parts of the public key: n and e. d is kept secret.

Now that the public and private keys have been generated, they can be reused as often as wanted

the sender converts his message into a number m. One common conversion process uses the ASCII alphabet:

A B C D E F GHJK L M 65 66 67 68 69 70 71 72 73 74 75 76 77 N O P Q R S T U V W X Y Z 78 79 80 81 82 83 84 85 86 87 88 89 90

For example, the message "HI" would be encoded as 7273. It is important that m<n, as otherwise the message will be lost when taken modulo n, so if n is smaller than the message, it will be sent in pieces.

The sender then calculates c ≡ m^e (mod n). c is the ciphertext, or the encrypted message. Besides the public key, this is the only information an attacker will be able to steal.

The receiver computes c^d ≡ m (mod n), thus retrieving the original number m. (It uses Euler Theorem)

The receiver translates m back into letters, retrieving the original message.

Ex:-

For example, suppose the receiver selected the primes p=11 and q=17, along with e=3 .

1. The receiver calculates n=p*q => 11 x 17 = 187, which is half of the public key.
2. The receiver also calculates ϕ=(p−1)(q−1) => 10 x 16 = 160 . e=3 was also chosen.
3. The receiver calculates d=107, since, de=107 x 3 = 321 ≡ 1 (mod ϕ(n)) ,since( ϕ(n) = 160).
4. The receiver distributes his public key n=187: and e=3.

Now suppose the sender wanted to send the message "HI". Since n is so small, the sender will have to send his message character by character.

1. H' is 72 in ASCII, so the message text m is 72.
2. The sender calculates m^e=72³ ≡ 183(mod 187) , making the ciphertext c=183 . Again, this is the only information an attacker can get, since the attacker does not have the private key.
3. The receiver calculates C^d =183¹⁰⁷ ≡ 72 (mod 107), thus getting the message of m=72.
4. The receiver translates 72 into 'H'.

This is for 'H' only as same like this, calculate 'I' also ,it will give 73.

This is the total encryption and decryption procedure,once you can check it.

2.Encrypt 0002 with public key (7,77). find the decryption key.?

1. Step one is selecting two distinct prime numbers p and q. p=7 and q=11 since n=77.
2. To get n= p x q = 7 x 11 = 77.
3. phi(n) = (p-1) x (q-1) = 6 x 10 = 60.
4. given e= 7. where as gcd(60,7)=1 1<=e <=60.  
5. determine d such that d*e % phe(n) = 1; d < phe(n). where as 43 * 7 % 60 =1,so d=43.
6. And next given public key KU (7,77) where e=7 and n=77, so m=2 then, Encryption c = m^e % n; m < n , 2⁷ % 77 = 51. c=51, 51 < 77
7. and next Decryption, m = c^d % n , m= 51⁴³ % 77 .
8. Finally Private Key:
   1. Private key KR = [d, n]
   2. KR=[43,77].

Thank you..!!!