0
101 Sep 05, 2006 at 16:02

Hi, probably not the best place for this but maybe someone can help.
For one of my programs i’m trying to impliment my own version of the RSA algorithm, the encryption works fine, however the decrption does not, even though it uses basically the same algorithm. The code is as follows:

//      g++ main.c -o main

#include <stdio.h>
#include <stdlib.h>
#include "math.h"

int do_crypto(int M, int e, int N);

int main()
{

printf("...\n");

//  TWO PRIMES FOR OUR KEY
int p = 17;
int q = 11;
//  THIRD PART OF OUR KEY (PUBLIC)
int e = 7;
//  CALCULATE THE OTHER PART OF THE PUBLIC KEY
int N = p * q;  //  = 187

//  THE CHARACTER TO ENCODE AS ASCII
int M = 88;
//int M = "M";

//  ENCRYPT A CHARACTER
//int C = int ( M * exp(e) ) % N;
int C = do_crypto(M, e, N);     //  int M, int e, int N)
printf("C = %d \n", C);

//  CALCULATE THE DECRYPT KEY
//int d = ( 1 % ( (p-1) * (q-1) ) ) / e;
int d =  ( ( (p-1) * (q-1) ) / e );
printf("d = %d \n", d);

// DECRYPT THE CHARACTER
int m = do_crypto(11, 23, 187);     //  int C, int d, int N)
printf("m = %d \n", m);

return 0;
}

int do_crypto(int M, int e, int N)
{
int iret = int ( M * exp(e) ) % N;

return iret;
}


When decrypting I have put in actual values for the keys etc, and the result should be 88.
The actual formulas are:
ENCRYPT: C = Me (Mod N)
DECRYPT: M = Cd (Mod N)
*** Please note the ‘e’ and ‘d’ are supposed to be superscript, e.g. raised to the power of…

#### 5 Replies

0
102 Sep 05, 2006 at 18:33

@rubarb

M * exp(e)

That’s really not doing what you expect. Me can be computed with pow(M, e).

0
101 Sep 05, 2006 at 18:49

I did try that first. I’ve re-tried with the following results:

C = -145
d = 22
m = -145

0
102 Sep 05, 2006 at 19:02

The result of pow(11, 23) is gigantic, it’s even too large to store in a double without loosing precision. On top of that, the primes you’re using are way too small; the encryption can be broken really easily.

So what’s the intent of this? :huh:

0
101 Sep 05, 2006 at 19:20

I did wonder whether this was a problem. I tried using unsigned long’s to see if result was slightly different, it wasn’t.

I’m currently looking at http://www.efgh.com/software/rsa.htm, this defines it’s own data type from what I can tell, using an unsigned, or unsigned short, as they call it ‘mpuint’. To be honest i’m new to such large numbers, yet aware. In one book I have it mentions <complex> numbers, but not really looked at them yet.

For now i’m just messing around trying to write programs from reading ‘The Code Book’ by Simon Singh (this is why the primes are small).

The final use is for a simple encryption method for an in-game chat client. Also i’m aware of alternative existing methods for secure communication, but hey I like to try…

Cheers for any help!

0
165 Sep 05, 2006 at 19:39

It’s definitely worth it to try to implement RSA for your own experience. But if you want to use encryption for something serious like chatting in a game, it would be far easier to find an existing encryption library.

However, under the assumption that you do want to do RSA yourself, you will need a data type capable of storing very large numbers (bigger than 32 bits or even 64 bits). With a little bit of work, you can implement this yourself with a C++ class. You just need to break up the number into 32-bit chunks. It’s as if each chunk is a digit, and the number is being expressed in base 232. Addition, multiplication, and all the usual operations can be implemented on such numbers essentially by the same algorithms that you would use in grade school to work with multi-digit numbers in base 10.

Also, be aware that even if you get it working perfectly RSA is rather slow. Most systems that use RSA to do data encryption actually only use RSA at the beginning of a conversation, to agree upon a symmetric encryption key. The rest of the conversation is encrypted using a symmetric method (the same key both encodes and decodes the data), which is much faster.