Jump to content

Welcome to Geeks to Go - Register now for FREE

Geeks To Go is a helpful hub, where thousands of volunteer geeks quickly serve friendly answers and support. Check out the forums and get free advice from the experts. Register now to gain access to all of our features, it's FREE and only takes one minute. Once registered and logged in, you will be able to create topics, post replies to existing threads, give reputation to your fellow members, get your own private messenger, post status updates, manage your profile and so much more.

Create Account How it Works
Photo

RSA Implementation (C++) (Advanced)


  • Please log in to reply

#1
W-Unit

W-Unit

    Member

  • Member
  • PipPipPip
  • 170 posts
Hey guys,

So I'm trying to write an implementation of RSA in C++. I know - yikes!

I'll try and keep it concise. I've actually modified some of the code so that I don't have to mention custom classes and other stuff I've actually got working here, because it's irrelevant and would require too much explanation.

My first step in the process is to convert an input string into a series of bits (using an std::bitset). I've accomplished this in the following manner:
template <int S>
std::bitset<S>* convertToBitStr(const std::string& msg)
{
	std::bitset<S>* result = new std::bitset<S>();

	const char* cmsg = msg.c_str();
	int bsPos = 0;
	for (int pos = 0; cmsg[pos] != '\0'; ++pos)
	{
		assert(bsPos < S);
		for (char t = 0; t < CHAR_BIT; ++t)
		{
			int p = ((int)cmsg[pos] & pow(2.0,(double)t));
			result[bsPos] = ((p == 0) ? false : true);
			++bsPos;
		}
	}

	return result;
}
(Note: You need includes for <assert.h>, <limits>, and of course <bitset> for this to compile)

This yields a simple conversion - take the string "Hi", for instance. The integer value of 'H' (on my compiler, MS VC++) is 72, which in binary is 1001000. The integer value of 'i' is 105, which in binary is 1101001. Each character in the input string gets 8 bits of space in the resulting bitset, with the first character in the string coming last in the binary representation. Thus the binary representation of "Hi" is 0110100101001000. I've also got a function defined to convert these binary representations back to strings, of course - everything is working fine so far.

Now, the interesting part. Assume I've done all the padding I need to do, I've got all my RSA keys: n, the shared key; d, the private key; and e, the public key.
In that case, the RSA hash c of a message M, whose integer representation is m, is computed by c = m^e (mod n).
However, computing the right-hand side of that equation is where I'm having trouble. I cannot convert the binary representation to any of the builtin types and then compute it using builtin functions, because the value of even a measly 5-character-long string is likely to be larger than the maximum value that can be held by an unsigned long.
Furthermore, e is probably going to have a value of something on the order of 65535, or potentially even larger. So we are raising an incredibly large number to the power of another very large number. That's going to require a *TON* of bits to hold that resultant value. Seems grossly inefficient.

So I have a feeling that I am going about this the wrong way. Am I? If so, what is the right way? And if not, how can I compute the exponentiation of two very large numbers - one of which I am restricted to working with the binary representation of (e could be simply an unsigned long or something, or it could also be a bitset; whichever is more convenient)?

Thanks!! :)

Edited by W-Unit, 10 August 2011 - 05:17 PM.

  • 0

Advertisements


#2
Spike

Spike

    nOoB

  • Member
  • PipPipPipPip
  • 1,355 posts
Hey there W-Unit,

I hope I may be able to help you, the largest number datatype in standard c++ is "unsigned __int64" which range is "18446744073709551615" when unsigned. More than that you would probably have to make your own class and an array, so when the int64 is about to overflow in moves to the next position... To be honest I wouldn't know how efficient this would be for your purposes, but it would definitely be the most efficient from other methods.

Have you considered just using a string? It may not be the most efficient method but by far the simplest.

Peace Out :)
Spike
  • 0

#3
W-Unit

W-Unit

    Member

  • Topic Starter
  • Member
  • PipPipPip
  • 170 posts

the largest number datatype in standard c++ is "unsigned __int64" which range is "18446744073709551615" when unsigned.

You learn something new every day :yes: thanks for this

More than that you would probably have to make your own class and an array, so when the int64 is about to overflow in moves to the next position...

I thought of doing a few things along these lines, but I didn't pursue the idea very far. My first idea was to have a class kind of like this:
struct Bignum
{
	unsigned char lmCount;
	unsigned __int64 offset;

	explicit Bignum(unsigned __int64 val);
	Bignum(unsigned char pmCount, unsigned __int64 pffset);
};
... where "lmCount" represents a number of times to multiply by (max value of unsigned int64)+1, and "offset" represents some number to add to the result, in order to obtain the proper value. So if we had a Bignum with lmCount=3 and offset=1234, this would represent a number whose value is equal to 3*(max value of unsigned int64)+1234.
The problem I ran into was that performing calculations with two Bignums turns out to be surprisingly hard, since you have to be careful never to overflow the value of offset. The only way I could think of to addition of two Bignums, for instance, was hideously inefficient. If you know of a mildly efficient way to perform addition, multiplication, modulus, and ideally exponentiation for numbers in this format, please do tell :)

My next idea was to use another bitset to represent the large numbers, and perform mathematical operations on them in binary. Unfortunately, I do not know how to perform exponentiation or the modulus operation in binary, and I haven't had much success looking up how to do this. The operations would have to be bitwise, so that an algorithm could handle numbers of arbitrary bitlength.

Have you considered just using a string? It may not be the most efficient method but by far the simplest.

Could you explain this a bit more? What would this involve? I presume you mean storing the bits in a string rather than a bitset... But keep in mind that we have to do arithmetic with these strings. I don't see how using a string could escape the constraints of needing to perform operations with numbers that are larger than C++ is designed to work with.

Thanks very much for the reply!! :unsure:

Edited by W-Unit, 12 August 2011 - 03:36 PM.

  • 0

#4
Spike

Spike

    nOoB

  • Member
  • PipPipPipPip
  • 1,355 posts

... where "lmCount" represents a number of times to multiply by (max value of unsigned int64)+1, and "offset" represents some number to add to the result, in order to obtain the proper value. So if we had a Bignum with lmCount=3 and offset=1234, this would represent a number whose value is equal to 3*(max value of unsigned int64)+1234.
The problem I ran into was that performing calculations with two Bignums turns out to be surprisingly hard, since you have to be careful never to overflow the value of offset. The only way I could think of to addition of two Bignums, for instance, was hideously inefficient. If you know of a mildly efficient way to perform addition, multiplication, modulus, and ideally exponentiation for numbers in this format, please do tell :).


That looks about right and is of similar fashion to how I would have put it... And sorry when I suggested the idea, I was most definitely over simplifying the problem. I have looked up some libraries that have the same idea in mind, which I will post further along. I have not actually tried to test what would happen and how I would implement it myself, but it seems like you've got further with your thought processes than I have. In those libraries I mentioned, I recall implementations of preforming operators on your datatype, with all those that you mentioned and some other if I am correct.

My next idea was to use another bitset to represent the large numbers, and perform mathematical operations on them in binary. Unfortunately, I do not know how to perform exponentiation or the modulus operation in binary, and I haven't had much success looking up how to do this. The operations would have to be bitwise, so that an algorithm could handle numbers of arbitrary bitlength.


:unsure: Hopefully with the library provided you can take some functions for preforming your exponentiation and modulus operators, just have to adjust it to suite your bitwise needs.

Could you explain this a bit more? What would this involve? I presume you mean storing the bits in a string rather than a bitset... But keep in mind that we have to do arithmetic with these strings. I don't see how using a string could escape the constraints of needing to perform operations with numbers that are larger than C++ is designed to work with.


Well the idea at the time was to store ALL the bits in an actual string... And when time comes to do arithmetic on the data, split the data into sections and convert back to original type (But will be in parts) that can be worked on. So you could preform your arithmetic, although there would be no place to store your resultant data. So ye, didn't think that one through so well....

Sorry it took so long to reply back, this weekend has been a very busy one.. After realizing the issues after you posted back, I must apologize for replying with such vague and simplified responses to your complex problem. While I was trying to further understand what it is you are trying to do, my mind was set on finding/creating a datatype that could store more bits than the int64. If I am correct finding this datatype and being able to preform operations on it would solve your problem . I found a library that looks promising:

http://gmplib.org/

I haven't fully looked into it's functionality, but it looks like this is exactly what you've been looking for... I really hope this helps, please do let me know!

Peace Out Posted Image
Spike

Edited by spike_hacker_inc, 14 August 2011 - 03:06 PM.

  • 0

#5
Spike

Spike

    nOoB

  • Member
  • PipPipPipPip
  • 1,355 posts
Posted Image Ummm, can't remember where I found this... I know somewhere on sourceforge.net... It seems to work! I don't know how you going to change it to work with your program though, but I'll post it through anyways... That gmp library looks more promising and I would start there...

But if you do consider this and would like my help, I wouldn't mind looking through it properly and seeing how we can adapt it to your purposes...


Peace Out Posted Image
Spike

Attached Files


  • 0

#6
W-Unit

W-Unit

    Member

  • Topic Starter
  • Member
  • PipPipPip
  • 170 posts
Sorry it's taken so long to reply.
Thank you both for your help! I am still working on this project, and making progress with that gmplib. I'll let you know how it goes!! :)
  • 0






Similar Topics

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

As Featured On:

Microsoft Yahoo BBC MSN PC Magazine Washington Post HP