1. RSA encryption and decryption

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 =?

2. Re: RSA encryption and decryption

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.

3. Re: RSA encryption and decryption

Could you be more specific? I don't understand why we need the highest power of 2.

4. Re: RSA encryption and decryption

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 xm 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);
}

5. Re: RSA encryption and decryption

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).