Thread: 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.

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

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