Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

a) Let p = 11. If e = 7 , show the steps and find d. b) Encrypt the message m = 4 c) Decrypt the result of part (b).

GCD(7,p-1) = 1 there is a d such that (m^e)^d = m d satisfies ed - (p -1)k = 1

share|improve this question

closed as off-topic by The Chaz 2.0, dfeuer, T. Bongers, Sujaan Kunalan, Jyrki Lahtonen Nov 13 '13 at 7:48

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – The Chaz 2.0, Community, Sujaan Kunalan, Jyrki Lahtonen
If this question can be reworded to fit the rules in the help center, please edit the question.

1  
Welcome to MSE! What have you tried and where are you stuck? Regards –  Amzoti Nov 13 '13 at 3:35
    
I don't know how to solve this problem!!! help :( I don't even know where to start.... –  mathissuperfunsometimes Nov 13 '13 at 3:41
1  
The first thing you need to do is figure out what cipher you are supposed to use. Since $p$ is a prime number, the most likely choice of $RSA$ has been ruled out. It sounds like you are asking to encrypt message using modular exponentiation. However, what you provided doesn't have enough detail to narrow down this choice. You need to provide us more context and tell us all the background info you know, including the one you don't understand. BTW, if this is a homework, please tag it as one. –  achille hui Nov 13 '13 at 4:09
    
Let e be such that GCD(e,p -1) = 1. Then there is a d such that (m^e)^d = m, for all m belongs to Np. d satisfies ed - (p-1)k = 1. d can be found using the Euclidean Algorithm. –  mathissuperfunsometimes Nov 13 '13 at 4:35

1 Answer 1

up vote 0 down vote accepted

Classical RSA encryption uses modulus $n=pq$, where $p,q\in \mathbb{P}$ (are primes), and has similar structure.

It seems, that your encryption is like RSA, but with prime modulus $p$ ($p\in \mathbb{P}$).

a) To find $d$, for large $p$ one can use extended Euclidean algorithm (see example).
In your case ($p$ is small) one can use simple checking: to find such $d$, that $$ed=1 (\bmod~p-1).$$ Since $e=7$, then
$7\cdot 1 = 7 (\bmod~10)$;
$7\cdot 2 = 14=4 (\bmod~10)$;
$7\cdot 3 = 21=1 (\bmod~10)$;
So, decryption key $\underline{\underline{d=3}}$.

b) Encrypting:

To encrypt message $m$, one calculates value $$c = m^e (\bmod~p).$$
You need to calculate value $c=4^7 (\bmod~11)$.

Step-by-step:
$4^1=4(\bmod~11)$,
$4^2=4 \cdot 4 = 16 = 5(\bmod~11)$,
$4^4=(4^2)^2 = 5^2 = 25 = 3(\bmod~11)$,
$\color{gray}{4^8=(4^4)^2 = 3^2 = 9 (\bmod~11)}$,
...

Now, $$ 4^7 = 4^{1+2+4} = 4^1 \cdot 4^2 \cdot 4^4 = 4\cdot 5 \cdot 3 = 60 = 5 (\bmod~11). $$

So, encrypted mesage is $\underline{\underline{c=5}}$.

c) Decrypting:

To decrypt (encrypted message) $c$, you need to calculate value $$m' = c^d (\bmod~p).$$

I hope it is not hard for you.

Finally, $m'$ must have the same value as $m$, of course.


Just note: this algorithm is not secure, of course, because it has no math problem to find $\varphi(modulus)$, knowing $modulus$, where $\varphi()$ is Euler's totient function

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.