# RSA encryption with 1024 bit keys

Printable View

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 09-09-2005
bennyandthejets
RSA encryption with 1024 bit keys
I've just completed a program which does arithmetic on arbitrarily large integers, and I'd now like to implement RSA encryption with it. Unfortunately, it seems that I am doing things very inefficiently. I have a binary powering routine, and am trying to calculate a number on the order of:

50^(2^512) (mod 2^1024)

The program grinds to a halt almost immediately, because the powers of 50 soon become incredibly large.

I'm not aware of any techniques for RSA encryption except binary powering, but I'm sure there must be cleverer ways to do it. Does anyone have any advice?
• 09-09-2005
laserlight
Quote:

Unfortunately, it seems that I am doing things very inefficiently.
And how might you be doing things currently?

Have you considered using an existing library such as the GMP?
• 09-09-2005
bennyandthejets
Quote:

And how might you be doing things currently?
I have some value 'a' that I want to raise to the power of 'e', then take modulo 'm'. I split a^e into multiple factors, each a binary power of a. Ie: a^7=(a^4)(a^2)(a^1). I calculate each of those factors by squaring the previous factor and taking modulo m. Afterwards I multiply all the appropriate factors together, taking modulo m each step of the way.

The numbers are all stored as an array of chars, each storing 8 bits. Addition and multiplication are performed just like you would on paper.

Thanks for the link to the GMP, but the reason I was coding this was to learn how to work with large numbers, not just to encrypt things.
• 09-09-2005
treenef
Have you thought about using Chinese remainder theorem to simplify the mammoth computation of finding 50^(2^512) (mod 2^1024).

With RSA there are a few tricks you can use to simplify the amount of math you have to do.

Invariably you have to have a system which can handle v. large numbers. You say you have implemented the addition and multiplication part.

What about the division and modulus part? That may be your next step if you haven't done so already.

Quote:

Thanks for the link to the GMP, but the reason I was coding this was to learn how to work with large numbers, not just to encrypt things.
The GMP handles large numbers. I'm not sure what you mean by the 'encryption' comment?

Have a looky here for extra ideas, in particular the pdf about rsa and its implementation.

http://cboard.cprogramming.com/showt...t=67189&page=2

Btw the hardest part is generating large prime numbers. I'll let you find out about that :)
• 09-09-2005
bennyandthejets
I can't use the Chinese Remainder Theorem because the whole point is that RSA encryption keys are too large to factor, so I won't know the factors of whatever 'm' is.

I've implemented a good division and modulus system, but it's not nearly fast enough to compute such large numbers as the ones I need.

What I meant about the GMP is that I don't want something else to do the work for me; I want to know for myself how to optimize the arithmetic. Encrypting data will just be an added bonus. I'll check out those links, thanks.

I'm not so concerned about generating large primes. I've read about a few algorithms that can produce large primes with a lot of certainty.
• 09-09-2005
Rashakil Fol
What sort of algorithm are you using for multiplication? Is it O(n^2) or is it O(n log n)?
• 09-10-2005
bennyandthejets
I'm not familiar with that terminology. Could you briefly explain each one, or refer me to an online resource?
• 09-10-2005
laserlight
You could have a look at an article on Arbitrary-Precision Arithmetic. The author's intention is not so much to provide solutions as to provide a problem, but he does list Karatsuba's algorithm as one thing to try, and Fourier transformations as another.

Quote:

I'm not familiar with that terminology.
You could take a look at The Big Oh Notation.
• 09-10-2005
beanroaster
That is a really big number. I think that FAQ says that scientists use fortron to crunch really big numbers. Does this number have to be exact or can you use scientific notation?
Well, good luck with your problem,
• 09-10-2005
laserlight
Quote:

Does this number have to be exact or can you use scientific notation?
It has to be exact since he's doing cryptography.
• 09-10-2005
beanroaster
Oops, sorry, I guess from now on, I'll have to read the whole thread before I reply.
• 09-10-2005
bennyandthejets
I've been looking at the source for GMP, but the actual computational code is in assembly, and I'm not very proficient at reading it. Does this sort of thing absolutely have to be done in assembly, or could it be done fast enough in straight c++?
• 09-11-2005
Stoned_Coder
if you want it as fast as possible, yes, especially using mmx,sse etc.
You may find this useful
• 09-11-2005
Rashakil Fol
Don't bother with assembly; something's wrong with the algorithms you're using. If I can write Ruby code that performs 50 ^ (2 ^ 512) (mod 2^1024) - order calculations almost instantaneously, than using assembly won't help; it will only scale your running time down a little bit.

I can write
Code:

```def powmod(b,x,m)   if (x == 0)     return 1   end   tmp = powmod(b, x / 2, m)   if (x % 2 == 1)     return (((tmp * tmp) % m) * b) % m   else     return (tmp * tmp) % m   end end```
This Ruby function computed powmod(123, 2 ** 512 + 12344535, 2 ** 2048 + 1234) and produced
Code:

```22813624981075065545135850558173269231510448307866093786909898690881909635625 28026233653165635689972639687049986456799967595172328506910777276889008060872302 35464631832286336920331501492018763317107266447462587900392315073114991959333059 51421717310407289760318099206126989926255863894581434267272318153188897013984781 84378062834515623677409012707914256130537336028576225644897284752852800312488149 65148676160157595427552224160566504933248486744939428838549003370569396501573929 63204417521093027295195029595437349786705582067498498129131203940551923664015160 678987418146095882019961441850108090812140059913087917725917```
in less than a second. It's your algorithm that's the problem, and jumping into assembly language would not help.
• 09-11-2005
bennyandthejets
Quote:

if you want it as fast as possible
Nup, I just want something reasonable. I would like to be able to perform operations that large at something like 15 per second.

Quote:

something's wrong with the algorithms you're using
I'm sure that's the case. I don't understand how your code works though. Does this "Ruby" thing have built in support for arbitrarily large numbers? My whole aim was to implement that functionality myself, in C++. How should I do that?
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last