Our number theory class finally got around to teaching us implementation of PGP.
Now a couple of people on the board have sigs that include short Perl to do large key public key encryption - I assume that means the U.S. has not relaxed its stance on programs using large key sizes.
Therefore I claim to be a weapons factory, since now that I know how it works, I could easily write code for any key size.
(ok, ok, I’m still assimilating this, give me a few days of practice though!)
Poll time! How many other weapons factories do we have on SDMB? Sign in please.
Oh, and a sorta unrelated question. To speed up the congruencies, I was wondering if perhaps an array of the following form might increase speeds for repeated encryptions (say an encrypted HD). Then the broken up mod operations could be straight lookups, instead of calculations.
1 2 4 8 16 ... 2^1024 (or whatever the key size is)
1
2 (insert here in each cell
3 whatever the value is of the row
. to the power of the column mod the base)
.
2^16 (or whatever size blocks you are using)
Granted, that’d be a huge 64 or so MB table, but would it be faster then having to do the Euclidian Algorithm multiple times for each data number? Or is there a faster way?
It would be slow precisely because it’s large. You couldn’t keep it all in memory, not to mention in the CPU cache. The speed of all the modulus operations would be significantly faster than all of the memory access operations.
But, actually, you wouldn’t use public key encryption to encrypt data on a hard drive. Public key encryption, also called asymmetrical encryption, is very, very slow compared to private key (symmetrical) encryption. Typically, public key encryption is used to encode a randomly-generated session key for some symmetrical encryption algorithm, which is then used to actually encrypt the data. PGP does this, encrypting the data using IDEA, and encrypting the IDEA key using RSA.
[and here I thought I was going to beat out the 100+ views to a post ratio record…]
True 'dat.
I forgot the main reason to use public key is to establish a secure channel.
There would be no reason to justify the large amounts of memory (and 64MB isn’t unreasonable to be stored in memory if a computer was dedicated to doing encryption for large scale operation).
Well, given your familiarity with the topic matter, I will assume you qualify as munitions factory number 2 (although you didn’t say so:))
Apparently I am not a weapons factory.
In fact I think I must be a tree stump because I have absolutely no freakin’ idea what the hell you’re talking about.
Hard to say if you are or aren’t…the theory behind PGP and other public key encryption algorythms (epiliptic for instance) is pretty well known. The hard part is writing software that a) impliments it completely correctly, avoiding weak keys etc (Certain PGP keys are susecptable to differential attack if I recall correctly), and b) doesn’t leave traces lying around such as half encrypted swap files.
I studied encryption a bit back when it looked like my company might get into it and I’d have to debug/test the results, but we decided to avoid the encryption aspects of secure memories for the time being.
I’m afraid I don’t follow. Differential attacks? The whole security lies in the difficulty of factoring large prime numbers. As for being a munitions factory, I’ve been implementing my homework up to this point in Perl. I have the Euclidian Algorithm forwards/backwards, the sieve to hunt down primes, pseudoprime method, congruencies, Euclid’s method, Chinese remainder theorem…
Adding public key encryption wouldn’t be a big step. this stuff builds.
Doing it efficiently might be a problem, but I’d be interested in hearing about these weaknesses in the math. Do you have a quick way of factoring 200 digit numbers?
Just realised how silly a sentence in the above post looked, when discussing this with a friend.
er, the difficulty of factoring large numbers. In this case, one that is the product of two large primes.
Factoring a large prime number is actually fairly easy, or sorta easy, if you use pseudoprime test.
Well, so this doesn’t get bumped up for absolutely no reason… How long would it take for the average supercomputer to factor a 2^64 bit number (isn’t that what distributed.net is working on right now)? Wouldn’t it just be a matter of testing every prime below 2^32?
