- #1
FrankJ777
- 140
- 6
Homework Statement
I'm trying to understand RSA and modular math better. I've studied some of the relations and rules, but I keep getting stuck when i try to follow an example all the way through. I'm also getting confused by how I'm supposed to treat ≡ vs = at some times. Here is the background in this particular example:
The encryption function is y ≡ xe (mod n), where x is the integer value of the plain text and y the integer value of the cipher text.
I'm not sure if this means: y = xe (mod n), meaning y = the remainder of xe/n or should i interpret it to mean:
y (mod n) ≡ xe (mod n) where i should solve for y, so that the remainder of y/n = the remainder of xe/n ?
Would I do that using the Chinese remainder theorem or Euclid algorithm? or the relationship y = xe (mod n): ⇒ y-x/m = k ?
Homework Equations
In this example: e = 11, p = 13 , q = 29 and n = pq = 377. Φ(n) = (p-1)(q-1)= 336.
the values for the integer plain text is 110, 111, 119. Y is the cipher text.
y ≡ 11011 ≡ 310 (mod 377)
y ≡ 11111 ≡ 132 (mod 377)
y ≡ 11911 ≡ 189 (mod 377)
What does y equal, and where did the numbers 310, 132, 189 (in red) come from??
According to the example the cipher text is 310, 132, 189.
Here is a hyperlink to the entire example. http://math.gcsu.edu/%7Eryan/12capstone/papers/maxey.pdf
3. The Attempt at a Solution
So now I'm confused. Considering the first line of the relevant equations...
Is it saying
y = 110 11 ( mod 377) = 310, and ⇒ y ≡ 310 (mod 377) ⇒ y (mod 377) = 310 (mod 377) ?
if I calculate 110 11 (mod 377) does not equal 310 (mod 377)...
110 11 ( mod 377) = 28531167061100000000000 (mod 377) = 372
and 310 (mod 377) = 310.
So where does the number 310 come from??
According to the example y is the cipher text, and the cipher text is 310, so how do we find y.
Are we supposed to find y through the relationship..
y ≡ 11011 (mod 377)
y (mod 377) ≡ 11011 (mod 377)
Then we solve for y using anther method and come up with y = 310.
So, to recap...
1) Does y ≡ xe (mod n) mean find y for y (mod n) = xe (mod n) ?? In other words is the cipertext y, the remainder of xe (mod n) or is it a number that when divided by n has a remainder equal to the remainder of xe divided by n.
2) Where did the red numbers (310, 132, and 189) come from in the example. Are these equal to the y's??
I would like to work through this by myself as much as possible, but I'm stuck and thoroughly confused.
Thanks for the help guys.
Last edited by a moderator: