Crypto Formula Malfunction

5 replies to this topic

#1rubarb

New Member

• Members
• 6 posts

Posted 05 September 2006 - 04:02 PM

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

#2Nick

Senior Member

• Members
• 1227 posts
• LocationOttawa, Ontario, Canada

Posted 05 September 2006 - 06:33 PM

rubarb said:

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

#3rubarb

New Member

• Members
• 6 posts

Posted 05 September 2006 - 06:49 PM

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

...
C = -145
d = 22
m = -145

If your getting different results please show code?

#4Nick

Senior Member

• Members
• 1227 posts
• LocationOttawa, Ontario, Canada

Posted 05 September 2006 - 07:02 PM

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:

#5rubarb

New Member

• Members
• 6 posts

Posted 05 September 2006 - 07:20 PM

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!

#6Reedbeta

DevMaster Staff

• 5307 posts
• LocationBellevue, WA

Posted 05 September 2006 - 07:39 PM

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.
reedbeta.com - developer blog, OpenGL demos, and other projects

1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users