HOMEWORK 4: CS 386 (DUE DATE: Thursday, 3/22/18) 1. Illustrate RSA algorithm to
ID: 3705183 • Letter: H
Question
HOMEWORK 4: CS 386 (DUE DATE: Thursday, 3/22/18) 1. Illustrate RSA algorithm to generate a pair of public and private keys using p 23 and q 37 Select e such that it is higher than p or q value. Use Extended Euclid algorithm to determine d. Give the public key pair (e, n) and private key pair (d, n). 2. The ASCII character codes for different characters are as given belovw ASCII Code: Character to Binary 0011 0000 0011 0001 011 0010 0011 0011 011 0100 011 0101 6 0011 0110 011 0111 0011 1000 011 1001 A 0100 0001 B 0100 0010 C 0100 0011 D 0100 0100 100 0101 P 0100 0110 100 0111 100 1000 I 0100 1001 100 1010 100 1011 L 0100 1100 100 1101 ?? 0100 1110 o 0100 1111 101 0000 0101 0001 0101 0010 101 0011 101 0100 0101 0101 101 0110 0101 0111 X 0101 1000 ? 01011001 0101 1010 110 0001 0110 0010 0110 0011 110 0100 0110 0101 110 0110 0110 0111 0110 1000 0110 1001 m 0110 1101 0110 1110 0110 1111 D 0111 0000 0111 0001 r 0111 0010 0111 0011 t 0111 0100 0111 0101 0111 0110 0111 1000 0111 1001 0111 1010 0010 1110 0010 0111 0011 1010 0011 1011 0010 0001 0010 1100 0010 0010 0010 1000 0010 1001 space 0010 0000 0110 101 0110 1011 0110 1100 Use binary to decimal conversion to get m value to be used for a message Encrypt the word "God" using the keys generated in problem 1. Encrypt each plain text separately. For example, letter I has binary code, 0100 1001 which is equivalent to 73, then m-73Explanation / Answer
1.
Given that, p=23 and q=37, which are two prime numbers.
RSA Algorithm:
Step1: p=23 and q=37
Step2: n=p*q; n=851
Step3: ?=(p-1)*(q-1); ?=792
Step4: Choose a large number e ? [2, ? ? 1] that is co-prime to ?; e=85 (thast is the coprime of ?)
Step5: Compute d ? [2, ? ? 1] such that, e . d = 1 (mod ?). There is a unique such d. Furthermore, d must be co-prime to ?; d=205 such that e . d = 1 (mod 792)
Step6: Announce to the whole word the pair (e, n), which is his public key; public key (85, 851)
Step7: Keep the pair (d, n) secret to himself, which is his private key; Keep the private key (205, 851)
Step8: Knowing the public key (e, n) of Bob, Alice wants to send a message m ? n to Bob. She converts m to C as follows: C = me (mod n)
Step9: Bob’s public key is (85, 851). Assume that m = 583. Then: C = 58385 (mod 851) = 395 Alice sends C to Bob.
Step10: Using his private key (d, n), Bob recovers m from C as follows: m = Cd (mod n)
Step11: In preparation, Bob has obtained his private key is (205, 851) (which he keeps secret). So he calculates: m = 596205 (mod 851) = 583 namely, the message from Alice.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.