# Thread: RSA encryption with 1024 bit keys

1. ## 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?

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

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

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

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

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

6. What sort of algorithm are you using for multiplication? Is it O(n^2) or is it O(n log n)?

7. I'm not familiar with that terminology. Could you briefly explain each one, or refer me to an online resource?

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

I'm not familiar with that terminology.
You could take a look at The Big Oh Notation.

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

10. Does this number have to be exact or can you use scientific notation?
It has to be exact since he's doing cryptography.

11. Oops, sorry, I guess from now on, I'll have to read the whole thread before I reply.

12. 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++?

13. if you want it as fast as possible, yes, especially using mmx,sse etc.
You may find this useful

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

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

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?

Popular pages Recent additions