I need to implement RSA encryption/decryption/key generation for my algorithms class; I already have all the code written and correct, but I need a big number library (2[sup]80[/sup]?) to use to check the timing requirements. Our school has a LEDA license, but I can only use this if I scp my project and ssh onto one of the lab machines, and this is a big pain. Is anyone aware of a free (besides GMP - I spent about an hour trying to get it to work and gave up) arbitrary length number library?

Correct me if I'm wrong, which I could be, but can't you process it in 4-byte blocks? For SHA-1, for sure, you can just store it in an int[5].

That would be about the same as writing my own bignum library, i think. I would have to do special things every time I wanted to do something mathematical instead.

[quote author=K link=board=30;threadid=5912;start=0#msg50891 date=1079977121]
That would be about the same as writing my own bignum library, i think. I would have to do special things every time I wanted to do something mathematical instead.
[/quote]

Ok, so write your own then ;)

For sha-1, all operations are designed to operate on it int-by-int. I guess what you need to do doesn't, in that case, so forget I mentioned it :)

[quote author=iago link=board=30;threadid=5912;start=0#msg50892 date=1079977504]
[quote author=K link=board=30;threadid=5912;start=0#msg50891 date=1079977121]
That would be about the same as writing my own bignum library, i think. I would have to do special things every time I wanted to do something mathematical instead.
[/quote]

Ok, so write your own then ;)

For sha-1, all operations are designed to operate on it int-by-int. I guess what you need to do doesn't, in that case, so forget I mentioned it :)
[/quote]

It's possible that there's a method that does it int by int, but I don't know of it; basically I need to generate ~200-digit primes as well as do modular exponetiation on large numbers.

As a side note, if I were to write my own, I wonder what would be fastest? Storing the number as an array of digits or actually manipulating dword by dword, etc?

I read somewhere that generating a prime that big is so difficult that quasi-primes are often used (almost-prime-numbers). Not sure if it's true, though.

OpenSSL has a big number library as a subcomponent, but check the licenses on it to see if it's compatible with what you want to do.

[quote author=K link=board=30;threadid=5912;start=0#msg50909 date=1079984943]
As a side note, if I were to write my own, I wonder what would be fastest? Storing the number as an array of digits or actually manipulating dword by dword, etc?
[/quote]

If you store it as an array of digits, you'll be manipulating it in base 10. It would be faster to manipulate it in a larger base, like base 2**32 or 2**16. The principle will be the same, so assuming you don't run into limitations in your compiler, they should be about the same to code.

[quote author=iago link=board=30;threadid=5912;start=0#msg50914 date=1079986720]
I read somewhere that generating a prime that big is so difficult that quasi-primes are often used (almost-prime-numbers). Not sure if it's true, though.
[/quote]

the probability of generating a prime number randomly is ln(n) / n. Basically I'm generating a large random number and then running several iterations of fermat's little theorem over it.

Basically, for any number A < P and any prime P working in modulo M:
A[sup]P-1[/sup] mod M = 1

Each iteration has a 1/2 chance of proving P composite except for Carmichael Numbers which have a lower number of witnesses.

[quote author=Adron link=board=30;threadid=5912;start=0#msg50949 date=1079991577]
[quote author=K link=board=30;threadid=5912;start=0#msg50909 date=1079984943]
As a side note, if I were to write my own, I wonder what would be fastest? Storing the number as an array of digits or actually manipulating dword by dword, etc?
[/quote]

If you store it as an array of digits, you'll be manipulating it in base 10. It would be faster to manipulate it in a larger base, like base 2**32 or 2**16. The principle will be the same, so assuming you don't run into limitations in your compiler, they should be about the same to code.
[/quote]

I've been thinking about this and it seems like it would be easy. Just store a (doubly) linked list of DWORDS along with a count of how many nodes and a boolean to keep track of negatives. Addition, Subtraction, and Bit Manipulation also seem like they would be easy to implement, but multiplication/division and exponentiating could be difficult. I think I'll work on this now that I've tested and verified that my RSA code works for large numbers on a lab machine with LEDA.

You can use the regular multiplication and division algorithms that you'd use for multiplying two large decimal numbers on paper.

How do I teach my computer to use a ti-83?

[quote author=iago link=board=30;threadid=5912;start=0#msg51687 date=1080262125]
How do I teach my computer to use a ti-83?
[/quote]

That would be a step down, considering paper extends near infinitely, all you have to do is get more, while a ti-83 can't be extended with much memory at all.

[quote author=Adron link=board=30;threadid=5912;start=0#msg51717 date=1080269882]
[quote author=iago link=board=30;threadid=5912;start=0#msg51687 date=1080262125]
How do I teach my computer to use a ti-83?
[/quote]

That would be a step down, considering paper extends near infinitely, all you have to do is get more, while a ti-83 can't be extended with much memory at all.
[/quote]

Granted, but TI-83 can go up to 10**10000 or something crazy like that, and that would take a whole lot of paper :)