Hey math88.
Hint: Use the result a^(b+c) mod n = (a^b mod n)*(a^c mod n) mod n and break things into powers of 2.
The highest power of 2 is 2048 for 2707. Then you can use this to find your answer.
Hi everyone, I don't know how to decrypt and encrypt ciphertext using RSA cryptosystem.
I have a problem:
Let n=4189, e=3, d=2707. Encrypt DO(0314) and decrypt 3971.
I think to encrypt DO (0314)
0314^3 mod 4189 = 2434
but I don't know how to decrypt 3971
3971^2707 mod 4189 =?
Please help me. Thank you very much.
Hi,
The decrypted value is 614. I did not do this by hand; certainly the RSA algorithm is not meant to be done by hand. What is needed once e, d and n are specified is a way to compute x^{m} mod n (encryption m=e and decryption m=d).
Here is C code to do exactly this. The first is recursive and the second is non-recursive. With enough patience you can do these algorithms by hand to arrive at 614, but I'm too lazy.
Code:/* Recursive computation of x^m mod n (so n != 0) where m>0. Of course ints involved must be all < MAX_INT and also n^2 < MAX_INT Algorithm works because x^m=(x^(m/2))^2*x^(m%2). At each step the result is reduced mod n. */ int powmod(int x,int m,int n) { int temp; if (m==1) { return(x%n); } temp=powmod(x,m/2,n); temp*=temp; if (m&1==1) { temp%=n; temp*=x; } return(temp%n); } /* Computes x^m mod n as in recursivePowmod. Same caveats as there. The validity of this technique can be verified by considering m written in binary. This is more efficient than the above because it takes away the log(m) function calls, but practically there is little difference in efficiency. */ int powmod1(int x,int m,int n) { int z=1,y=x; while (m>0) { if (m&1==1) { z=z*y%n; } y=y*y%n; m>>=1; } return(z); }
As an example lets say you want to calculate 3^129. In binary this is 129 = 128*1 + 1*1. So you have to calculate 2^129 = 2^128*2^1.
You calculate 3^1 mod n, 3^2 mod n, 3^4 mod m, 3^16 mod n 3^32 mod n, ..., 3^128 mod n. You do this by squaring the previous value and simplifying mod n.
Then you use the fact that a^(b+c) = a^b * a^c and use the results to obtain mod n.
The reason you use binary is because you can use x = a*2^n + b*2^(n-1) + ... + z where the coefficients are either 0 or 1.
Another example is say 72 = 1*64 + 0*32 + 0*16 + 1*8 + 0*4 + 0*2 + 0*1 or 75 = 1*64 + 0*32 + 0*16 + 1*8 + 0*4 + 1*2 + 1*1.
By using the results of a^(2n) you can use these in addition to a^(b+c) = a^b * a^c to figure out really large values (if you don't have a computer).