In Public Key Cryptography, there are two keys created, one for encoding a message (the public key) and one for decoding
Posted: Mon Jul 11, 2022 12:46 pm
In Public KeyCryptography, there are two keys created, one for encoding amessage (the public key) and one for decoding the message (theprivate key). One form of this scheme is known as RSA, from thefirst letters of the last names of Ron Rivest, Adi Shamir, andLeonard Adleman, who published the method in 1977 while professorsat the Massachusetts Institute of Technology. This method usesmodular arithmetic in a very unique way.To create a coding and decoding scheme in RSA cryptography, webegin by choosing two large, distinct primenumbers p and q, say,
p =59
and
q =83.
In practice,these would be prime numbers that are 200 or more digitslong.Find the productof p and q,
n = p · q =59 · 83 = 4897.
The valueof n is the modulus. Now find theproduct
z =(p − 1)(q − 1) =58 · 82 = 4756
and randomlychoose a number e, where
1< e < z
and e and z have nocommon factors. We will choose
e =129.
Solve themodular equation
ed = 1mod z
for d. For the numbers we are using, we mustsolve
129d ≡ 1mod 4756.
We won't go intothe details but the solution is
d =1401.
Recall thatbecause
129 · 1401 ≡1 mod 4756,
1401 is themultiplicative inverse of 129 mod 4756.To receive encrypted messages, Jenna posts these valuesof n and e to a public keyencryption service, called a certificate authority, whichguarantees the integrity of her public key. If Henry wants to sendJenna a message, he codes his message as a number using a numberfor each letter of the alphabet. For instance, he mightuse A = 11, B = 12, C = 13, D = 14, E = 15, F = 16, G =17, H = 18, I = 19, J = 20, K = 21, L = 22, M = 23, N = 24, O = 25,P = 26, Q = 27, R = 28, S = 29, T = 30, U = 31, V = 32, W = 33, X =34, Y = 35, Z = 36.For Henry to send the message MATH, he would use the numbers 23 1130 18 and code those numbers using Jenna’s public key, (n= 4897, e = 129) in
t e mod n ≡ c
as
t129 mod 4897 ≡ c,
where t is the plaintext (23 11 30 18),and c is the ciphertext, the result of using themodular equation. This is shown below:
23129 mod 4897
≡
3065
11129 mod 4897
≡
2001
30129 mod 4897
≡
957
18129 mod 4897
≡
2753
Thus Henry sends Jennathe ciphertext numbers 3065, 2001, 957, and 2753.When Olivia receives the message, she uses her privatekey, (n = 4897, d = 1401) in
c d mod n ≡ t
as
c1401 mod 4897 ≡ t,
where c is the ciphertext she receivedfrom Henry and t is the original plaintext, todecode the message. Jenna calculates:
30651401 mod 4897
≡
23
20011401 mod 4897
≡
11
9571401 mod 4897
≡
30
27531401 mod 4897
≡
18
She decodes the message as 23 11 30 18 or MATH.Summary: Public Key is (n = 4897, e= 129). Private Key is (n = 4897, d = 1401).
Answer the question below using these items.a) Use p=59, q=83, e=129,d=1401. Calculate n and z fromthose numbers.b) The letter=number code: A = 11, B = 12, C = 13, D = 14,E = 15, F = 16, G = 17, H = 18, I = 19, J = 20, K = 21, L = 22, M =23, N = 24, O = 25, P = 26, Q = 27, R = 28, S = 29, T = 30, U = 31,V = 32, W = 33, X = 34, Y = 35, Z = 36.c) Use Wolfram Alpha or any calculator to calculateexpressions like 23^129 mod 4897: enter the expression into theentry blank and receive the answer 3065.What is the ciphertext for the word RODE? (Simplify youranswers completely. Enter your answers as a comma-separatedlist.)
p =59
and
q =83.
In practice,these would be prime numbers that are 200 or more digitslong.Find the productof p and q,
n = p · q =59 · 83 = 4897.
The valueof n is the modulus. Now find theproduct
z =(p − 1)(q − 1) =58 · 82 = 4756
and randomlychoose a number e, where
1< e < z
and e and z have nocommon factors. We will choose
e =129.
Solve themodular equation
ed = 1mod z
for d. For the numbers we are using, we mustsolve
129d ≡ 1mod 4756.
We won't go intothe details but the solution is
d =1401.
Recall thatbecause
129 · 1401 ≡1 mod 4756,
1401 is themultiplicative inverse of 129 mod 4756.To receive encrypted messages, Jenna posts these valuesof n and e to a public keyencryption service, called a certificate authority, whichguarantees the integrity of her public key. If Henry wants to sendJenna a message, he codes his message as a number using a numberfor each letter of the alphabet. For instance, he mightuse A = 11, B = 12, C = 13, D = 14, E = 15, F = 16, G =17, H = 18, I = 19, J = 20, K = 21, L = 22, M = 23, N = 24, O = 25,P = 26, Q = 27, R = 28, S = 29, T = 30, U = 31, V = 32, W = 33, X =34, Y = 35, Z = 36.For Henry to send the message MATH, he would use the numbers 23 1130 18 and code those numbers using Jenna’s public key, (n= 4897, e = 129) in
t e mod n ≡ c
as
t129 mod 4897 ≡ c,
where t is the plaintext (23 11 30 18),and c is the ciphertext, the result of using themodular equation. This is shown below:
23129 mod 4897
≡
3065
11129 mod 4897
≡
2001
30129 mod 4897
≡
957
18129 mod 4897
≡
2753
Thus Henry sends Jennathe ciphertext numbers 3065, 2001, 957, and 2753.When Olivia receives the message, she uses her privatekey, (n = 4897, d = 1401) in
c d mod n ≡ t
as
c1401 mod 4897 ≡ t,
where c is the ciphertext she receivedfrom Henry and t is the original plaintext, todecode the message. Jenna calculates:
30651401 mod 4897
≡
23
20011401 mod 4897
≡
11
9571401 mod 4897
≡
30
27531401 mod 4897
≡
18
She decodes the message as 23 11 30 18 or MATH.Summary: Public Key is (n = 4897, e= 129). Private Key is (n = 4897, d = 1401).
Answer the question below using these items.a) Use p=59, q=83, e=129,d=1401. Calculate n and z fromthose numbers.b) The letter=number code: A = 11, B = 12, C = 13, D = 14,E = 15, F = 16, G = 17, H = 18, I = 19, J = 20, K = 21, L = 22, M =23, N = 24, O = 25, P = 26, Q = 27, R = 28, S = 29, T = 30, U = 31,V = 32, W = 33, X = 34, Y = 35, Z = 36.c) Use Wolfram Alpha or any calculator to calculateexpressions like 23^129 mod 4897: enter the expression into theentry blank and receive the answer 3065.What is the ciphertext for the word RODE? (Simplify youranswers completely. Enter your answers as a comma-separatedlist.)