• Support PF! Buy your school textbooks, materials and every day products Here!

RSA encryption problem

  • Thread starter muso07
  • Start date
  • #1
54
0

Homework Statement


This is a problem my lecturer did in class but I'm a bit confused.

We have 2 large primes p=137 and q=131, choose e = 3
n = pq = 137.131 = 17947
(p-1)(q-1) = 136.130 = 17680

Compute d = e-1 mod (p-1)(q-1) = 3-1 mod 17680 = 11787.

This is where I'm confused. How did he get d=11787?

Homework Equations




The Attempt at a Solution


I think I'm supposed to use the Euclidean algorithm to find d, but he didn't show how.
 
Last edited:

Answers and Replies

  • #2
73
0
for d to be the multiplicative inverse of 3 mod 17680 you need 3*d = 1 mod 17680; there will be a unique positive d < 17680 for which this is true, and this d can be found using the extended euclidean algorithm. the following page will be helpful:
http://www-math.cudenver.edu/~wcherowi/courses/m5410/exeucalg.html [Broken]

for your problem you will start
17680 = 5893(3) + 1
and the euclidean algorithm terminates quickly because
3 = 3(1) + 0
rearranging the line above you get
1 = 17680 - 5893(3)
so you know that d = -5893, which is 11787 mod 17680.
 
Last edited by a moderator:
  • #3
54
0
Lindsay Childs in "A Concrete Introduction to Higher Algebra" deals with RSA details if you need more information.
 

Related Threads for: RSA encryption problem

  • Last Post
Replies
2
Views
934
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
602
  • Last Post
Replies
0
Views
735
  • Last Post
Replies
0
Views
1K
Replies
1
Views
2K
Top