Multiplying and dividing bignums

[Frank]

I'm writing a bignum library for C# at the moment. For calculating stuff to any arbitrary precision (limited only by memory). Mostly for doing specialised encryption stuff. I use an array of UInt32 to store the numbers. And I really hate the tedium involved with doing multiplications and divisions.

What would be the simples (and fast) way to do that with huge numbers (more than 10,000 bits)?

[Rufus]

Fastest way from a programming perspective would be to use one of the libraries that already exists. :roll: Shouldn't be hard to translate something like GMP (http://www.swox.com/gmp/) to C# (assuming licensing allows you to use open code).

[Frank]

Well, if I could find a decent C# lib, I would use that. But I haven't so far. I know of one, but that doesn't have a try-before-buy option. And I'm not going to recommend something untried.

As for translating: no thanks. It's easier and a lot less error prone to write it myself, so I know what happens. Especially when someone wants me to change something.

[BRiT]

As for translating: no thanks. It's easier and a lot less error prone to write it myself, so I know what happens. Especially when someone wants me to change something.

Why would you ever need something changed in a proper infinite precision math lib?

[Frank]

Why would you ever need something changed in a proper infinite precision math lib?
Well, I do have a few, C, C++, Delphi and even JavaScript, but this is for a C# ASP.NET project, and my colleagues want something that fits in and that they all can maintain as well. That means C#. And I should have said "added to or improved upon" instead of changed.

Besides, I don't mind writing it. But I really wonder if multiplication and division can't be done more neatly.

[[maven]]

There was a talk about bignum arithmetic held at the recent CCC-Congress in Berlin, the slides can be found here (http://www.fefe.de/).
Maybe they can help you... :)

[bloodbob]

More then 10,000? wtf

[levicki]

Well, I do have a few, C, C++, Delphi and even JavaScript, but this is for a C# ASP.NET project, and my colleagues want something that fits in and that they all can maintain as well. That means C#. And I should have said "added to or improved upon" instead of changed.

Besides, I don't mind writing it. But I really wonder if multiplication and division can't be done more neatly.

Then why don't you let THEM write it?!?

If I were you that would be option #1.

If you want to do it for yourself then Google for it (http://www.google.com/search?q=big+number+multiplication), there are plenty of results covering that topic out there.

[Simon F]

Fastest way from a programming perspective would be to use one of the libraries that already exists. :roll: Shouldn't be hard to translate something like GMP (http://www.swox.com/gmp/) to C# (assuming licensing allows you to use open code).
Agreed. GMP seemed very good when I played with it a few years ago. I don't recall if it had the (friendly) LGPL or the more restrictive GPL.

[DemoCoder]

Don't bother. I guarantee you that your BigNum library will be vastly slower than GMP or other long maintained packages. Moreover, tracking down bugs will waste lots of your time. Finally, you there is the issue of the security of the calculations as well (not leaking info to heap). I speak as someone who spent alot of time in '96 implementing fast MP for embedded tamper resistant crypto-coprocessors. It's a blackhole of time to go from scratch to something that people can place trust in.

You could theoretically rip the source for Java's builtin java.math.BigInteger/BigDecimal classes, and port them to C#, but for encryption? I seriously question the need of anyone doing "specialized encryption stuff" unless they *know* what they are doing. You don't even seem to be aware of Karatsuba or FFT, which are well known n^lg3 and nlogn algorithms, which casts into doubt any expertise in the field. Even established and experienced people in the security field wouldn't bother writing their own low level mp libraries.

Besides implementing fast mul and mod, you'll need tons of number theoretic algorithms involved in key selection and primality, etc. And did I mention that if you don't know what you're doing, you'll expose your code to tons of attacks, on heap allocated objects (especially with GC based platforms) on timing-attacks, on entropy.

Once again, I say, don't do it.

If you're not using well established protocols already available in third party libraries, chances are, you're inventing your own protocol, and history has shown that even top level academic experts produce protocols that end up being successfully attacked by peers.

Once again, don't do it.

There are tons of open source libs. There is windows CryptoAPI. Before you write one line of code for something intended for real use (and hence, needs real security) stick with well reviewed, mature, implementations.

And god help you if you're working on voting machines.

[Frank]

;904213']There was a talk about bignum arithmetic held at the recent CCC-Congress in Berlin, the slides can be found here (http://www.fefe.de/).
Maybe they can help you... :)
Very interesting. Thanks.

[Frank]

We have data services (MS SQL interface that returns xml pages with the data requested) for use with C# ASP.NET. At the moment, those data services are only accessible by IIS. But we want to use AJAX. And if you use AJAX, you have to have the browser communicate directly with the data services. Which means, that anyone can read and modify the data in the database directly by communicating with that data service port. And we don't want that.

To make that secure, we want the aspx code to set up a secure connection with the browser, by generating an RSA keypair at both sides and sending a symmetric key to the browser, which it can use for 5-15 minutes to query the dataservice. After that time, the key is revoked and has to be renegociated.

It would be easier to use SSL (https), but that isn't allowed by the proxy admins. So we have to do it like that. But that requires the generation of an RSA keypair by the browser (JScript) every 10 minutes or so. Which is pretty slow. And as we don't care about someone finding out what was communicated afterwards, the key length doesn't have to be very long. 128 bits is accceptable, 256 bits is good. It only has to be safe enough for the short duration it is active.

The fastest JScript library I could find takes between 0.4 and 1.8 seconds to generate a 256 bits keypair, while it takes 2+ seconds to generate a 384 bit keypair (demo (http://www-cs-students.stanford.edu/~tjw/jsbn/rsa2.html)), which frequently pops up the message that a script on the page is causing the browser to run slowly, do you want to abort the script? Which is unacceptable, of course.

Microsoft has decided that anything less than a 384 bits keypair is not safe enough, so they aren't supported. So I have to do it myself. And they might decide by the next version of the framework that anything less than 512 or even 1024 bits isn't safe enough, or that a 40 bit symmetric key isn't safe enough, or that a hash algorithm we have to use isn't safe enough anymore. Etc. So we have to be prepared to migrate our own libraries for all that.

And if we do all that, there are some added bonuses. Like a BigNum (BigInt) library. Which can be used for other things as well. And as long as Microsoft doesn't supply one, ours should be able to handle our needs.

So, I started with writing my own BigInt class. Not very hard, but it takes a lot of time, especially the testing. And multiplying and dividing are rather inefficient. Yes, I did look at the alternatives, but they are pretty complex and not worth it except for very long bitsizes. I was just wondering if someone did know something a bit more elegant. I didn't expect it, but you'll never know.

I did find a very nice BigInt implementation (http://www.codeproject.com/csharp/biginteger.asp) that also does the probable prime testing and such, and which has been used as the base for the Mono classes. I fixed some more obvious bugs, rewrote and added a lot of constructors and methods to use big endian, and am adding all the stuff like padding to bring it up to the official specs. And I'm now doing more bugtesting, as it sometimes returns invalid results...

I also want to look at the Mono implementation, and I just stumbled upon an even better looking library (http://www.bouncycastle.org/csharp/index.html), which I'm going to look at as well.

And if that is done, I'll have to see what can be done with the symmetric and hashing algorithms.

[Simon F]

You don't even seem to be aware of Karatsuba or FFT, which are well known n^lg3 and nlogn algorithms,
I think I read that FFT really wasn't worth the effort and that using Toom-Cook (which I guess is a generalisation of Karatsuba-Ofman and gives a cheaper complexity bound than K-O) is a much better approach.

[Blazkowicz]

I remember how we had to write a library for arbritarily big int numbers in Caml, as first year rookie students, and that was easy. I don't remember if we did division and we didn't care at all about such thing as speed, off course.

looks like I found it..
http://communaute.mangue.org/e107_plugins/cours/cours.php?id=caml&cid=cours9.html
a recursive type, isn't that great :).

[Frank]

Btw, it turns out to be a total pain to use different libraries at both sides. There are way too many standards and versions. And backwards compatibility is nonexistent. So it's actually easier to implement the actual encryption functions myself, compatible with some random standard and version.

[Chalnoth]

Well, one of the issues is that these days, if you're worried about security, the encryption itself is not the weak link. It's bugs in the software that can be exploited. I know that I myself like to write my own code as much as possible, but in this instance I think DemoCoder is probably correct and you'll want to use an existing library.

[levicki]

I think I read that FFT really wasn't worth the effort and that using Toom-Cook (which I guess is a generalisation of Karatsuba-Ofman and gives a cheaper complexity bound than K-O) is a much better approach.

PiFast (http://numbers.computation.free.fr/Constants/PiProgram/pifast.html) uses FFT for big number multiplication and it is the fastest PI calculator I know about. FFT seems not to be such a bad choice if you have good (read: fast) FFT implementation.

[Davros]

do it exactly the same way you would do it on paper....

[Simon F]

do it exactly the same way you would do it on paper....
...and it will be relatively slow. Of course, if you rarely have to do these calculations, then that won't matter, but if they are common, then you really need to use better algorithms <shrug>.

[Davros]

hey i never claimed to be clever :D

hmm i wonder if someone could do it on a gpu ?

store the numbers as textures and do something fancy ( thats a technical term by the way ;) )