Question

In: Computer Science

In this question we show that we can use φ(n)/2. Let n = pq. Let x...

In this question we show that we can use φ(n)/2. Let n = pq. Let x be a number so that gcd(x, n) = 1.

1. show that xφ(n)/2 = 1 mod p and xφ(n)/2 = 1 mod q

2. Show that this implies that and xφ(n)/2 = 1 mod n

3. Show that if e · d = 1 mod φ(n)/2 then xe·d = 1 mod n.

4. How can we use φ(n)/2 in the RSA?

Please explain answers if you can! Thanks!!

Solutions

Expert Solution

Q:-
In this question we show that we can use φ(n)/2. Let n = pq. Let x be a number so that gcd(x, n) = 1.
1. show that xφ(n)/2 = 1 mod p and xφ(n)/2 = 1 mod q.
Answer:--------

φ(n) = (p-1)(q-1). As p and q are primes , both p-1 and q-1 will be even.
By Fermat's little theorem, xp−1 ≅ 1 (mod p).
Hence, x φ(n)/2 = (xp−1)(q−1)/2 ≅ (1)(q−1)/2 ≅ 1 (mod p ).
Similarly, xφ(n)/2 ≅ 1 (mod q).

2. Show that this implies that and xφ(n)/2 = 1 mod n.
Answer:--------

Given equations: y 1 (mod p) and y 1 (mod q), the Chinese Remainder Theorem says there is a unique in y ∈ Zpq that satisfies these two equations, and in this particular case y = 1 is the obvious unique solution. Hence, (b) follows.

3. Show that if e·d = 1 mod φ(n)/2 then xe·d = 1 mod n.
Answer:--------

Since e·d 1 (mod ϕ(n)/2), ed = k·(ϕ(n)/2) + 1, for some integer k.  
So,
xe·d x k·(ϕ(n)/2) + 1 (xϕ(n)/2)k · x (1)k·x x (mod pq).


Related Solutions

In this question we want to show that we can work with ø(n)/2 instead of ø(n)...
In this question we want to show that we can work with ø(n)/2 instead of ø(n) in the RSA. Let p, q be 2 distinct primes and n = pq. Let x be so that gcd(x, n) = 1. How can we work with ø(n)/2 instead of ø(n) in RSA? Please show or explain the correctness of your analysis.
Let V -Φ -> W be linear. Show that ker (Φ) is a subspace of V...
Let V -Φ -> W be linear. Show that ker (Φ) is a subspace of V and Φ (V) is a subspace of W.
Given a function φ(z) with z = x+iy let    U(x, y) = ½ [φ(x+iy) +...
Given a function φ(z) with z = x+iy let    U(x, y) = ½ [φ(x+iy) + φ(x-iy)] and V(x, y) = i/2 [φ(x+iy) –φ(x-iy)] A) For φ(z) = z2 find U and V and their induced vector fields E =▼U and F =▼V also show that ▼2U = ▼2V = 0 B) Repeat for f(z) = z3 C) For f(z) = ln z we get U(x, y) = ½ ln (x2+y2) and V(x, y) = arctan (y/x) Find ▼U (electrostatic...
2. Let x be a real number, and consider the deleted neighborhood N∗(x;ε). (a) Show that...
2. Let x be a real number, and consider the deleted neighborhood N∗(x;ε). (a) Show that every element of N∗(x;ε) is an interior point. (b) Determine the boundary of N∗(x;ε) and prove your answer is correct.
(a) Let n = 2k be an even integer. Show that x = rk is an...
(a) Let n = 2k be an even integer. Show that x = rk is an element of order 2 which commutes with every element of Dn. (b) Let n = 2k be an even integer. Show that x = rk is the unique non-identity element which commutes with every element of Dn. (c) If n is an odd integer, show that the identity is the only element of Dn which commutes with every element of Dn.
Let φ : R −→ R be a continuous function and X a subset of R...
Let φ : R −→ R be a continuous function and X a subset of R with closure X' such that φ(x) = 1 for any x ∈ X. Prove that φ(x) = 1 for all x ∈ X.'  
(2) Let ωn := e2πi/n for n = 2,3,.... (a) Show that the n’th roots of...
(2) Let ωn := e2πi/n for n = 2,3,.... (a) Show that the n’th roots of unity (i.e. the solutions to zn = 1) are ωnk fork=0,1,...,n−1. (b) Show that these sum to zero, i.e. 1+ω +ω2 +···+ωn−1 =0.nnn (c) Let z◦ = r◦eiθ◦ be a given non-zero complex number. Show that the n’th roots of z◦ are c◦ωnk fork=0,1,...,n−1 where c◦ := √n r◦eiθ◦/n.
8. (20 pts) a. RSA encryption. Let n = pq = (7)(17) = 119 and e...
8. (20 pts) a. RSA encryption. Let n = pq = (7)(17) = 119 and e = 5 define a (very modest) RSA public key encryption. Since 25 < 119 < 2525, we can only encode one letter (two digit representation) at a time. Use the function ? = ? mod ? to encode the word MATHY into a series of five numbers that are less than n. b. To decrypt an RSA encrypted message, we need to find d,...
Let X be a random variable with an N(2,4) distribution. FindP(|X−2|^2 >.36)
Let X be a random variable with an N(2,4) distribution. FindP(|X−2|^2 >.36)
Let x1 > 1 and xn+1 := 2−1/xn for n ∈ N. Show that xn is...
Let x1 > 1 and xn+1 := 2−1/xn for n ∈ N. Show that xn is bounded and monotone. Find the limit. Prove by induction
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT