RSA encryption with 1024 bit keys

**bennyandthejets** · 09-09-2005

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?

**laserlight** · 09-09-2005

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?

**bennyandthejets** · 09-09-2005

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.

**treenef** · 09-09-2005

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

**bennyandthejets** · 09-09-2005

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.

**Rashakil Fol** · 09-09-2005

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

**bennyandthejets** · 09-10-2005

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

**laserlight** · 09-10-2005

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.

**beanroaster** · 09-10-2005

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,

**laserlight** · 09-10-2005

Does this number have to be exact or can you use scientific notation?

It has to be exact since he's doing cryptography.

**beanroaster** · 09-10-2005

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

**bennyandthejets** · 09-10-2005

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

**Stoned_Coder** · 09-11-2005

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

**Rashakil Fol** · 09-11-2005

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.

**bennyandthejets** · 09-11-2005

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?

Thread: RSA encryption with 1024 bit keys

Thread Tools

Search Thread

Display

RSA encryption with 1024 bit keys

Similar Threads

Copy bit to bit

binary numbers

16 bit or 32 bit

40, 128 BIT encryption

Array of boolean