One place the greatest common divisor is used is in encryption schemes. RSA encr
ID: 3623946 • Letter: O
Question
One place the greatest common divisor is used is in encryption schemes. RSA encryption is one common encryption scheme. It uses the following steps:
1. If I want you to send me an encrypted message I take any two relatively large primes p and q (we'll use 11 and 17 for this example, although primes actually are much larger) and multiply them together to get n=pq: 187.
2. I next take any number e with the property that gcd(e, (p-1)(q-1))=1. (e.g., e=3 works since gcd(3, (11-1)*(17-1))=1.)
3. I send you e and n.
4. To send me an encrypted message you take your message, assign numerical equivalents to each character, and then encrypt these numerical equivalents by C=a^e mod n. You then send the results.
Example:
Write two functions:
1. A function check_epq that, given e, and prime numbers p, and q, checks that gcd(e, (p-1)(q-1))=1. (You can assume p and q are prime here.)
2. A function char_to_number that takes in an upper case alphabetic character, and returns an integer that is the postion of the character in the alphabet. For example char_to_number('A') should return 1, character_to_number('B') should return 2, etc.
Once you get all these functions written, write a main program that does the following: it first asks the user to input e, p, and q. It then uses your check_epq function to check that e, p, and q obey the gcd condition. If they do not, the program should print out an error message and terminate. If they do, the program should ask the user to input four upper case alphabetic characters, change each to an integer using your char_to_number function, encode each using the following encode function, and print out the result.
Here is the encode function
int encode (int a, int e, int n)
{
return (static_cast<int>(pow(static_cast<double>(a), e))%n);
}
Here are some examples of running the main program:
Example 1:
Please input e, p, and q: 5 11 17
GCD of e and (p-1)*(q-1) is not 1.
Example 2:
Please input e, p, and q: 3 11 17
Please input four upper case letters: S T O P
The encoding of STOP is 127 146 9 169.
Note: this program will only work with small values of e, p, and q. (What happens if you try to encode "STOP" with e, p and q being 11, 19, and 31 respectively? Why?)
Will Rate Lifesaver!!
Explanation / Answer
1) compute n = pq , n = (19*31) = 589
2) encryption exponent e = 11 so raise your message to this power to encrypt the message
3) to encrypt STOP we need to turn it into m (or integer format) and then raise it to the e power (mod n) -> s=18 t=19 o=14 p=15 so m=18191415
4) so raise 18191415 to the 11th power and % 589 and the encrypted version of STOP is now
18191415^11 = 72199019000875890352261203188281040491199833459205966171308856565434866552734375
that number modulo 589 = 99
index j = 9 so the encrypted stop is jj
so
plaintext: stop
ciphertext: JJ
I'm really sleepy, if anything is unclear let me know.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.