Re: StoN, Diffie-Hellman, other junk..

2000-09-09 Thread Asymmetric

At 01:44 09/09/2000 -0700, Bill Stewart wrote:



Not incorrect, but 2**256 possible keys gets you into
age-of-the-universe territory for cracking.

Well yes, but better safe than sorry.. you never know when the next 
breakthrough might come that makes anything under 256bits "weak."  Not too 
likely I know, but doesn't hurt to keep that in mind.

I'm not aware of one.  IDEA's "non-commercial" definitions have gotten
fuzzier over the years, and it's patented in lots of places.
Avoid Misty.  Several of the AES candidates had policies of
"it's patented now but if we're the AES winner you can all use it for free",
which means you won't really know licensing issues until NIST picks a winner.

Ah.. I'll just have to keep digging myself.. maybe I'll put together a page 
of my own for this purpose.  It's aggravating having to dig all over the 
place for this kind of info.

What's the deal with Misty?


signature

PGP Key ID:
0xCCC57FD7

PGP Key Fingerprint:
446B 7718 B219 9F1E 43DD  8E4A 6BE9 D739 CCC5 7FD7

Available from ldap://certserver.pgp.com




Re: StoN, Diffie-Hellman, other junk..

2000-09-08 Thread Bill Stewart

At 09:20 PM 9/7/00 -0400, Asymmetric wrote:
I agree that voice using TCP has the drawbacks that you mentioned, however, 
because of the other existing requirements such as CBC and File Transfer, 
it is required that you have a reliable connection to get even the basic 
functionality of the program to work.  I'd rather have a delay in hearing 
the voice messages until the packets have arrived than decrease their 
security by using ECB.

You can still do CBC with UDP.  You might want to look at hybrid solutions,
like basic connectivity and voice connections on UDP and separate TCP
connections
for data transfer, though that may be more trouble than it's worth.

...
p196, pp2
"While CBC mode recovers quickly from bit errors, it doesn't recover at all 
from synchronization errors.  If a bit is added or lost from the ciphertext 
stream, then all subsequent bits are shifted one bit out of position and 
decryption will generate garbage indefinitely."

I assume that losing an entire block worth of bits will cause as much havoc 
as losing just one bit would.  If that isn't correct, I'd like to hear it..

There are synchronization problems you can recover from and ones you can't.
You need to stay aligned on the encryption-block barrier, e.g. 64 bits for DES
or 128 bits for some other algorithms.  If you lose that, you're toast.
But if you always pad your packets to multiples of the block size,
you don't have a problem with UDP, since packets either arrive or don't.
So if you lose a packet, then you've toasted the first 16 bytes of the next,
but the rest of the packet and the rest of the conversation are ok.  
With TCP, you don't lose packets, though you don't always have convenient 
mechanisms for keeping track of packet boundaries, but you're always going 
to write in block-size chunks anyway.



The rule of thumb is that you need at least twice as many bits of
DH as you need of secure session key for your application, and you need
at least as many bits of DH as you would need for RSA.
You wouldn't want to use fewer than 1024 bits of RSA these days,
so don't use fewer than 1024 bits of DH.  That's enough for multiple
128-bit keys.
There are various format proposals for turning the DH key into a session
key,
like using Hash(DHKey,YourIP,TheirIP,maybe-a-counter-or-Salt).
4096 may be overkill, but it depends a lot on how often you'll be rekeying
and how long you're willing to watch the CPU crunch to set up a connection.

The D/H is going to be used just to generate a key to securely transfer a 
4096 bit key for use in symmetrical crypto routines later in the program, 
for actual encryption of the chat/voice/file data transfers.  Using 1024 
bits of D/H is fine to generate a key-encryption key to just transfer the 
4096bit key.  I chose 4096 because it's large enough to be used in any 
symmetric crypto algorithm to max out it's key length.

Any symmetric algorithm will have maxed out by 256 bits, and most by 128,
though you may want different keys for your two directions.
So generating the DH key with 1024 bits is probably enough,
though it doesn't hurt much to do 2048 or 4096 -
no need for separately generating a key and shipping it.
In particular, DH takes advantage of both machines' sources of randomness,
which is a major win over something generated by one end
unless you've got a good reason for it.

If you don't have any other keying mechanism, you need to worry about
man-in-the-middle attacks.  A simple approach is to use PGP public keys
to sign the keyparts; that lets you reuse all the PGP infrastructure.
There are alternatives, at least for voice, like reading the bits of the
shared keys to each other.  See the PGPFONE docs for much discussion on
user interfaces - and think about how much of their code you can rip
off\\ reuse.

Well, truth be told, everyone knows that there is the problem "If Mallory 
is God.." which in this world simply means, if Mallory is your upstream 
you're in some serious trouble.  He could just as easily intercept the PGP 
keys and replace them with his own if they didn't already exist on the 
server.. this would cause problems for keys signed outside mallorys realm, 
say if you could distribute your key outside his available channels... 
however, if you could do that, you could just as easily trade a PRNG and a 
list of seeds, or even discuss whatever it is you mean to discuss over a 
cup of coffee.. :)

Sometimes Mallory _is_ your ISP - even without Carnivore.
Public key technology only needs one untampered data transfer to happen,
and PGP has a lot more infrastructure for that than trading PRNGs.
Signing DH keyparts is a job for public-key signatures.

Also read the Photuris internet drafts - there's a lot of experience
on denial-of-service attacks that they've incorporated,
and it doesn't take much work to prevent most of them.

Ah, sorry.. how did we get on the topic of denial of service?

By saying "I'm going to put this chat server on the Internet"
Crypto has its own 

Re: StoN, Diffie-Hellman, other junk..

2000-09-08 Thread Asymmetric

At 02:06 09/08/2000 -0700, Bill Stewart wrote:

You can still do CBC with UDP.  You might want to look at hybrid solutions,
like basic connectivity and voice connections on UDP and separate TCP
connections
for data transfer, though that may be more trouble than it's worth.

I've thought about it and it's definitely something to keep in mind.. 
another advantage to doing TCP from my standpoint is that it's easier to 
multithread.  The old version had some problems where on occasion it would 
stall for a while if it was doing a reverse lookup or something like that, 
and you wouldn't receive any more traffic until whatever operation was 
finished.  Threading the application allows any of the connections to stall 
or slow down without taking the rest of the application with it.. and 
threading UDP isn't nearly as easy.  Honestly, with the tools I have 
available, I don't even know if it's possible. :)

There are synchronization problems you can recover from and ones you can't.
You need to stay aligned on the encryption-block barrier, e.g. 64 bits for DES
or 128 bits for some other algorithms.  If you lose that, you're toast.
But if you always pad your packets to multiples of the block size,
you don't have a problem with UDP, since packets either arrive or don't.
So if you lose a packet, then you've toasted the first 16 bytes of the next,
but the rest of the packet and the rest of the conversation are ok.
With TCP, you don't lose packets, though you don't always have convenient
mechanisms for keeping track of packet boundaries, but you're always going
to write in block-size chunks anyway.

Ah ok.. so losing a block will just nuke the entire next block, and then it 
will recover?  I thought it would be a more serious problem than that, but 
I guess it makes sense that the feedforward wouldn't be able to affect any 
blocks beyond the immdiate next block.  Keeping the packets aligned on 
block boundaries makes so much sense that it's something I'm doing anyway 
regardless of this problem. :)

Any symmetric algorithm will have maxed out by 256 bits, and most by 128,
though you may want different keys for your two directions.
So generating the DH key with 1024 bits is probably enough,
though it doesn't hurt much to do 2048 or 4096 -
no need for separately generating a key and shipping it.
In particular, DH takes advantage of both machines' sources of randomness,
which is a major win over something generated by one end
unless you've got a good reason for it.

Well, the information I have is that Blowfish takes up to 448 bits, RC2 up 
to 1024 bits, Mars up to 1248bits, RC5 and RC6 both up to 2048 bits of key 
material.. is that incorrect?

The system currently supports Blowfish, Cast (128 and 256), Gost, IDEA, 
Mars, Misty1, RC (2, 5 and 6), Rijndael and Twofish for ciphers, and Haval, 
RipeMD160 and SHA1 for hashes.  The user chooses what cipher they want to 
communicate to the other users with, so incoming traffic can possibly use a 
different cipher on every connection, while outgoing traffic will all use 
the same cipher.

This brings up another question.  My document states that Cast256, IDEA(*), 
Mars, Misty1(*), RC5, and RC6 are all patented.. * = "Free for 
noncommercial use."  Is there a good repository somewhere with information 
on all the licensing issues/rules of these algorithms?



Sometimes Mallory _is_ your ISP - even without Carnivore.
Public key technology only needs one untampered data transfer to happen,
and PGP has a lot more infrastructure for that than trading PRNGs.
Signing DH keyparts is a job for public-key signatures.

True, and it is something that I've considered, but I would really like to 
stay away from any kind of server-based options as possible.  The fewer 
points of failure in the chain the better for this application.  I think it 
would suit me better to implement a public-key algorithm in the application 
itself, and then have each client maintain a list of all the public keys it 
has seen and allow the option to the user of signing them with it's own key 
and then sending them back to the owner.  This would allow the same 
failure-rate where only one transmission needs to occur untampered in order 
to allow for key validation.  Possibly in the future clients could exchange 
all their keys and then raise the trust level of a public key the more 
times they see it from different clients.  Since participation is entirely 
voluntary by both parties in both the overall application as well as the 
key signing/trust parts, then a DoS related to a single user forging a key 
and then connecting to many clients with many other clients isn't really an 
issue.  The lack of centralized communications means that the malicious 
user isn't going to have a "master list" to poison, or even an accurate 
view of all the clients in use.

This is all tenative however.. I haven't thought this far ahead until just 
now.  For now, I just want to get the D/H working and the key generation 
underway.


Re: StoN, Diffie-Hellman, other junk..

2000-09-07 Thread Asymmetric

At 15:08 09/07/2000 -0700, Bill Stewart wrote:


Servers are the price of scalability.  The nice thing about ICQ
and similar instant messaging applications, unlike IRC,
is that the server only tracks who's on and where, and doesn't carry
the actual communication traffic between users.  Obviously this is
for one-to-one conversations between two users rather than IRC's
everybody-to-everybody model.  Another option in this space is the
everybody's-a-server model, like Usenet uses.
Servers also offer the benefit that it's harder to tell
who's talking to whom, unlike point-to-point conversations,
but they do cause risks from compromise and downtime.

Right.. I consider the benefits to outweigh the costs.  I am keeping the 
protocol robust enough that if you wanted to implement a server on your 
own, you could probably do so with minimal impact to the clients 
themselves.  When finished, you'll be able to add servers just as you do 
other users to your "buddy list" if you will, and communicate with a larger 
group that way.  Inter-server communications is not restricted either, but 
it's a ways down the road.


 everyone must maintain an active TCP connection to everyone else..

That's a MAJOR downside.  Most operating system and programming environments
limit how many open TCP connections you can keep, typically 20,
so this limits the sizes of communities you can maintain.
Also, if you have TCP connections you need to write code to handle
having them go up and down at unplanned times,
while UDP just dribbles in.
On the other hand, TCP sessions are good for data transfer.
Voice over TCP is a sketchier issue - the problem is that
the best way to handle lost voice packets is just to ignore the noise,
as opposed to waiting for the retransmission to arrive and
speeding up or delaying talk until you've caught up.

Yes.. I understand the differences in TCP/UDP pretty well, and their 
strengths and weaknesses.  I've done extensive programming using both, and 
have decided to go with TCP.  I do however have two points to bring up with 
the beginning of this section of your reply.

1) I've never encountered the 20 socket limit on any OS in recent memory.. 
and many applications open more than this on a regular basis.

2) The target audience of this application is very small, and currently 
restricted to Win32 users because it is written in Delphi.  Before long 
Delphi will be available for Linux, and cross-compiler compatability will 
have to be tested, but it is a big selling point with 
Borland/Inprise.  When Kylix (Delphi/C++ Builder on Linux) is available, I 
am keeping my fingers crossed that it will run well on FreeBSD, since I 
refuse to touch Linux with a ten foot pole, but have several years 
experience not only with Delphi, but with Administration of FreeBSD as well 
as NT based boxes.

I agree that voice using TCP has the drawbacks that you mentioned, however, 
because of the other existing requirements such as CBC and File Transfer, 
it is required that you have a reliable connection to get even the basic 
functionality of the program to work.  I'd rather have a delay in hearing 
the voice messages until the packets have arrived than decrease their 
security by using ECB.


Your issues about ECB mode with UDP are good, though.
The alternative is to use CBC mode and trash the next couple of packets
after the lost/damaged one - CBC does self-recover.
This is ok for voice; may or may not be for chat.

CBC does self recover yes, if bits are flipped that should not be 
flipped.  According to AC, a one bit error will cause a corresponding 1bit 
error, as well as mangling the following block.. but subsequent blocks will 
be OK.  However, it states very clearly that receiving the wrong number of 
bits in the stream will destroy the rest of the stream beyond repair for 
the decryption end, and that makes sense.  If a UDP packet is lost, then 
the rest of the stream is screwed and must be reinitialized.  Since the 
only way around this problem (besides using EBC) is to write my own 
connection-handling on top of UDP; I instead choose to let the OS handle 
this for me, in the form of TCP.

To quote Applied Cryptography, 2nd edition..

p195, pp5
"In CBC mode, a single-bit error in the ciphertext affects one block and 
one bit of the recovered plaintext.  The block containing the error is 
completely garbled.  The subsequent block has a 1-bit error in the same bit 
position as the error."

...

p196, pp2
"While CBC mode recovers quickly from bit errors, it doesn't recover at all 
from synchronization errors.  If a bit is added or lost from the ciphertext 
stream, then all subsequent bits are shifted one bit out of position and 
decryption will generate garbage indefinitely."

I assume that losing an entire block worth of bits will cause as much havoc 
as losing just one bit would.  If that isn't correct, I'd like to hear it..


The rule of thumb is that you need at least twice as many bits of
DH as you need of secure 

Re: StoN, Diffie-Hellman, other junk..

2000-09-07 Thread Bill Stewart

At 12:45 AM 9/7/00 -0400, Asymmetric wrote  [EMAIL PROTECTED] :
To make the application more robust, I have started rewriting it to use TCP 
instead.  It is still a peer-peer network, requiring no dedicated servers.. 
while this increases overhead somewhat, I think it's worth it to keep the 
system from relying on one particular server, or a group of them.  

Servers are the price of scalability.  The nice thing about ICQ
and similar instant messaging applications, unlike IRC,
is that the server only tracks who's on and where, and doesn't carry
the actual communication traffic between users.  Obviously this is
for one-to-one conversations between two users rather than IRC's
everybody-to-everybody model.  Another option in this space is the
everybody's-a-server model, like Usenet uses.
Servers also offer the benefit that it's harder to tell
who's talking to whom, unlike point-to-point conversations,
but they do cause risks from compromise and downtime.

everyone must maintain an active TCP connection to everyone else.. 

That's a MAJOR downside.  Most operating system and programming environments
limit how many open TCP connections you can keep, typically 20,
so this limits the sizes of communities you can maintain.
Also, if you have TCP connections you need to write code to handle
having them go up and down at unplanned times,
while UDP just dribbles in.
On the other hand, TCP sessions are good for data transfer.
Voice over TCP is a sketchier issue - the problem is that
the best way to handle lost voice packets is just to ignore the noise,
as opposed to waiting for the retransmission to arrive and
speeding up or delaying talk until you've caught up.

Your issues about ECB mode with UDP are good, though.
The alternative is to use CBC mode and trash the next couple of packets
after the lost/damaged one - CBC does self-recover.
This is ok for voice; may or may not be for chat.

I have also decided to get rid of the key sharing mechanism, and instead 
utilize D/H to generate a KEK, then transfer a 4096bit data block from the 
initiating client to the serving client .
Now, my main question about D/H is quite simple.. what is considered a 
"good" size for the prime and primitive used, in bits?  

The rule of thumb is that you need at least twice as many bits of
DH as you need of secure session key for your application, and you need
at least as many bits of DH as you would need for RSA.
You wouldn't want to use fewer than 1024 bits of RSA these days,
so don't use fewer than 1024 bits of DH.  That's enough for multiple
128-bit keys.
There are various format proposals for turning the DH key into a session key,
like using Hash(DHKey,YourIP,TheirIP,maybe-a-counter-or-Salt).
4096 may be overkill, but it depends a lot on how often you'll be rekeying
and how long you're willing to watch the CPU crunch to set up a connection.

The bigger risk, though, is the quality of random numbers available 
for seeding your DH keys.  Don't even DREAM of using Delphi's builtins,
if it has them - go find good crypto-quality-randomness work to reuse,
unless you know you'll only run on Linux where there's /dev/random.
At least use sound-card noise or user-entered mouse tracks to help.
Lots of "secure" systems have been cracked by cracking their random seeds.

If you don't have any other keying mechanism, you need to worry about
man-in-the-middle attacks.  A simple approach is to use PGP public keys
to sign the keyparts; that lets you reuse all the PGP infrastructure.
There are alternatives, at least for voice, like reading the bits of the 
shared keys to each other.  See the PGPFONE docs for much discussion on 
user interfaces - and think about how much of their code you can rip
off\\ reuse.

Also read the Photuris internet drafts - there's a lot of experience
on denial-of-service attacks that they've incorporated,
and it doesn't take much work to prevent most of them.

An aside is that I'm writing the application in Delphi 5, and the maximum 
native supported integer sizes are 32bit unsigned, and 64bit signed.. I've 
been writing a math library of my own in assembler that at compile time 
will allow you to specify the maximum bitsize you want it to support, but 
this is proving to be a mind-numbing task.. ;)  

Gak!  Don't do something that ugly.  There are lots of math libraries
available,
such as the GMP Gnu Multiple Precision integer package.  Depending on how
Delphi feels about calling C routines, the most you should need to write
in assembler are some little wrappers to format the function calls,
and hopefully you don't need to do that.

Also, some versions of the RSAREF libraries had Diffie-Hellmann code in them,
as well as multiple-precision integers.


Other chat and messaging systems have been written.
Check out GALE at gale.org, and look through the Cypherpunks archives
for encrypted  IRC and DCC variants.  Don't let that stop you from coding,
but do steal code rather that writing from scratch when you can.


 First, 

Re: StoN, Diffie-Hellman, other junk..

2000-09-07 Thread dmolnar



On Thu, 7 Sep 2000, Asymmetric wrote:

 Mihailescu's methods for prime generation. (Mihailescu has a paper on
 the subject aimed at implementors at
 http://www.inf.ethz.ch/~mihailes/papers/primgen.ps )
 
 Ah.. I have implemented a sieve of eros..whatever his name is.. ;)  for 

Erastothenes, I think. 
I don't know what a sieve of eros is. I think I'd like to try one
sometime. :

 finding smaller primes.. it runs very fast, the old rules don't apply so 
 much anymore, memory footprint being more a concern then speed I've noticed 
 so far.. moving the found primes into a sparse array as you find them and 
 then reusing the memory is one way around that.. even my quickly written 
 implementation takes negligible time to find all the primes within 16 
 bits.. 

Right - I think you may find that this slows down a bit at the 500-bit
range. Still, there are supposed to be ways to use sieving in conjunction
with random search to speed up prime generation. 

but I've been looking at rabin-miller and some other methods as 
 well.  I'll take a look at that link, thanks.. reason again for the math 
 library.. my stuff (obviously) falls apart  32bits since my library for 
 handling larger numbers is unfinished.

Once  you have the primitives, Rabin-Miller is straightforward to
implement from the Handbook of Applied Cryptograpy. I was surprised at how
easy it was...

Another nice trick -- compute the product of the first 1000 primes or so.
Take the GCD of this product and a candidate number. Eliminates candidates
with small prime factors and often faster than trial division.  

 (for reasons that should be obvious) felt that writing the routines myself 
 (with extensive testing) would be preferable, so I could avoid licensing 
 issues as well as bugs/backdoors, but I'll look into this..  Thanks for the 

Backdoors are your responsibility with GMP, so no worries, right. :). It
is GPL'd, though, so be careful. 

 quick response.. the application will of course be available to anyone who 
 wants it once finished.. and once Borland finishes Kylix, should compile 
 nicely on the various x86 *nixes out there..

Looking forward to it. 

-David




Re: StoN, Diffie-Hellman, other junk..

2000-09-07 Thread Asymmetric


-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

At 02:07 09/07/2000 -0400, dmolnar wrote:

Erastothenes, I think.
I don't know what a sieve of eros is. I think I'd like to try one
sometime. :

Hah yeah that spelling looks right.. it's really pretty elegant, and was 
considered at the time of the writing of AC 2nd ed. to be faster for 
numbers of 100 digits or less.. since a base-10 digit is roughly 3.5 bits, 
that should be faster than say the general number sieve for numbers up to 
about 350 bits.

It works by first making an array of bits, all set to true, that represent 
all the numbers from 2 - X, where X is the last number you want to test for 
primeness.  You loop through the array from begining to end.. for each bit 
you find set, you set all multiples of that number up to X off.  This 
results in every multiple of every prime (which is to say, every composite 
number) being marked "false" in the array.  When finished, you have an 
array of bits where an on bit represents a prime.  The storage issue 
results because I currently store an array of bytes instead of an array of 
bits.. so to test the first ~ 16 million numbers (24 bits) requires about 
16 meg of storage.  That would drop to 2 meg if I rewrote it to be a 
bit-array, which I intend to do.. and it would only take N bytes of memory 
if instead implemented as a sparse array of bytes, where N = the number of 
primes from start to finish of your range.


Right - I think you may find that this slows down a bit at the 500-bit
range. Still, there are supposed to be ways to use sieving in conjunction
with random search to speed up prime generation.

Probably would slow down some around 512bits.. which should represent 
numbers about 147 base-10 digits.


Once  you have the primitives, Rabin-Miller is straightforward to
implement from the Handbook of Applied Cryptograpy. I was surprised at how
easy it was...

I expect it'll be easier when I look at it again.. it still looks a bit 
messy though.  AC 2nd ed describes rabin-miller as follows, p260, pp2..

(p = prime)

1. Calculate b, where b is the number of times that 2 divides into p - 1.
2. Calculate m, such that p = 1 + 2^b * m.
3. Choose a random number "a" such that "a" is less than "p".
4. Set j = 0 and set z = a^m mod p.
5. if z = 1, or z = p - 1, then p passes and may be prime.
6. if j  0 and z = 1, then p is not prime.
7. set j = j + 1.  If j  b and z != p - 1, set z = z^2 mod p, and go back 
to 6.  If z = p - 1, then p passes the test and may be prime.
8. If j = b, and z != p - 1, then p is not prime.

I think I need to just be a bit less tired before I can parse that 
efficiently into code.. :)


Another nice trick -- compute the product of the first 1000 primes or so.
Take the GCD of this product and a candidate number. Eliminates candidates
with small prime factors and often faster than trial division.

Do you mean calculate each product of two of the first 1000 primes?  (i.e. 
2*3, 2*5, 2*7... 5*7...) etc? for each possible pair?


Backdoors are your responsibility with GMP, so no worries, right. :). It
is GPL'd, though, so be careful.

Yeah.. hadn't decided if I was going to open source it or not.. but I 
suppose putting it under the GPL myself does prevent anyone else from 
making money off my work.. ;)  I'm not looking to make any money from this 
product, but I certainly don't want anyone else making money off my hard 
work either.  I need to read the GPL or GLPL closely.. whichever GMP is under.


Looking forward to it.

Cool.. thanks for the help and links again.. tried to sleep for the past 
two or three hours, couldn't.. I'm back up and at it. ;)


- ---signature file---

"'There comes a time when the operation of the machine
becomes so odious, makes you so sick at heart, that you
can't take part; you can't even passively take part, and
you've got to put your bodies upon the gears and upon the
wheels, upon the levers, upon all the apparatus, and you've
got to make it stop. And you've got to indicate to the people
who run it, to the people who own it, that unless you're free,
the machine will be prevented from working at all!"
- -Mario Savio-  Founder of the Free Speech Movement.

-BEGIN PGP SIGNATURE-
Version: PGPfreeware 6.5.8 for non-commercial use http://www.pgp.com

iQA/AwUBObdSUGvp1znMxX/XEQKL+wCghGPE649K/LKbWFqyiVU9EeRDVywAn2JA
LAtFdc1JFEEo4YiRcMzrE8L+
=IMRU
-END PGP SIGNATURE-




Re: StoN, Diffie-Hellman, other junk..

2000-09-06 Thread Asymmetric


-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

At 01:21 09/07/2000 -0400, dmolnar wrote:


The modulus should be rather large -- something like 512 or 1024 bits.
With 64 bits, someone can use Pollard's method to find discrete logs in
roughly 2^32 trials, which is Bad. Taking discrete logs for larger primes
requires a variant of the number field sieve; the largest announced
modulus for which I'm aware of this being done is 300-400 bits, but it
hasn't received as much attention as factoring.

I figured it would be something of that nature.. hence the math library I 
was working on.. :)


I think www.cryptosavvy.com has some key length recommendations. You might

Thanks for the link...

The size of the generator is a different issue. I don't see any reason why
a small size generator would hurt...but I haven't thought about it very
much. Note that you need the factors of p-1 in order to test if
something's a generator, which means you may want to look into Maurer or
Mihailescu's methods for prime generation. (Mihailescu has a paper on
the subject aimed at implementors at
http://www.inf.ethz.ch/~mihailes/papers/primgen.ps )

Ah.. I have implemented a sieve of eros..whatever his name is.. ;)  for 
finding smaller primes.. it runs very fast, the old rules don't apply so 
much anymore, memory footprint being more a concern then speed I've noticed 
so far.. moving the found primes into a sparse array as you find them and 
then reusing the memory is one way around that.. even my quickly written 
implementation takes negligible time to find all the primes within 16 
bits.. but I've been looking at rabin-miller and some other methods as 
well.  I'll take a look at that link, thanks.. reason again for the math 
library.. my stuff (obviously) falls apart  32bits since my library for 
handling larger numbers is unfinished.


It was after my time, but the AP Computer Science curriculum now has a
BigInteger library as its "case study." :-)

A web search turned up
http://www.efg2.com/lab/library/Delphi/MathFunctions/Cryptography.htm

which has, among other things, a Pascal header for the Gnu MP library.

Ah cool.. I've heard very good things about GMP and had been thinking about 
ways to implement it.. could solve all my problems in one fell swoop. :)  I 
(for reasons that should be obvious) felt that writing the routines myself 
(with extensive testing) would be preferable, so I could avoid licensing 
issues as well as bugs/backdoors, but I'll look into this..  Thanks for the 
quick response.. the application will of course be available to anyone who 
wants it once finished.. and once Borland finishes Kylix, should compile 
nicely on the various x86 *nixes out there..


- ---signature file---

"'There comes a time when the operation of the machine
becomes so odious, makes you so sick at heart, that you
can't take part; you can't even passively take part, and
you've got to put your bodies upon the gears and upon the
wheels, upon the levers, upon all the apparatus, and you've
got to make it stop. And you've got to indicate to the people
who run it, to the people who own it, that unless you're free,
the machine will be prevented from working at all!"
- -Mario Savio-  Founder of the Free Speech Movement.

-BEGIN PGP SIGNATURE-
Version: PGPfreeware 6.5.8 for non-commercial use http://www.pgp.com

iQA/AwUBObcqEGvp1znMxX/XEQLaYQCgxBxiiYTY2OHcVgso4Iaqy7PYucAAniM9
YL2M9tDag44LaILC6mChDmyf
=TL/e
-END PGP SIGNATURE-