[LUAU] Re: dangers to (Software) Freedom

[Jim Thompson]

On Aug 26, 2007, at 5:49 PM, Clifton Royston wrote:

> On Sun, Aug 26, 2007 at 05:32:00PM -1000, Angela Kahealani wrote:
>> On Sunday, 2007-08-26 11:32:35 Jim Thompson wrote:
>>> In any case, modern crypto-systems do not depend on "prime numbers"
>>> per se.  Rather, the[y] depend on the difficulty of factoring large
>>> numbers,
>>> especially those that are the product of two prime numbers.
>>
>> Yes... so if you can quickly generate primes,
>> you can quickly test factoring those primes out of another number.
>
>   No, absolutely not.  His claim that generating primes was formerly
> hard, and that's the source of the problem, is typical of what happens
> when you get outsiders to a field making "discoveries".  Occasionally
> they really find something new by looking at it with fresh eyes, but
> far more often they completely misunderstand the nature of the problem
> they are looking at, make fools of themselves, and then rant about how
> the "establishment" is ignoring them out of fear.  (Consider that
> centuries after the question was resolved via abstract algebra, you
> still get non-mathematicians claiming to have trisected an angle with
> compass and straightedge.)

Yep.

here is now Diffie-Hellman works:

Alice and Bob agree to use a prime number, say p=23 and base g=5.

Alice chooses a secret integer a=6, then sends Bob (g^a % p)

So: 5^6 % 23 = 8.

Bob chooses a secret integer b=15, then sends Alice (g^b % p)

So: 5^15 mod 23 = 19.

Alice computes (g^b mod p)a % p

19^6 % 23 = 2.

Bob computes (g^a % p)^b % p
8^15 % 23 = 2.
Both Alice and Bob have arrived at the same value, because g^(ab) and  
g^(ba) are equal, and can be used as symmetric keys.

The order of g (and G) should be prime or have a large prime factor  
to prevent use of the Pohlig-Hellman algorithm to obtain a or b.


Note that only a, b and g^(ab) = g^(ba) are kept secret. All the  
other values are sent in the clear. Once Alice and Bob compute the  
shared secret they can use it as an encryption key, known only to  
them, for sending messages across the same open communications channel.

Of course, much larger values of a, b, and p would be needed to make  
this example secure, since it is easy to try all the possible values  
of g^(ab) mod 23 (there will be, at most, 22 such values, even if a  
and b are large). If p were a prime of at least 300 digits, and a and  
b were at least 100 digits long, then even the best algorithms known  
today could not find a given only g, p, and ga mod p, even using all  
of mankind's computing power. The problem is known as the discrete  
logarithm problem. Note that g need not be large at all, and in  
practice is usually either 2 or 5.

> It is relatively easy to generate primes, and has been for a long
> time; it is fairly easy to *statistically* guess whether a given  
> number
> is prime or not, with good odds; it's very hard to find the prime
> factors of large non-primes.

Generating primes was easy back in the 1870s.  That is not a typo, I  
typed "1870s".
http://www.jsoftware.com/jwiki/Doc/Articles/Play104

Even if factoring the product of two large primes becomes tractable,  
we still have elliptic curves to use, (although if the discrete  
logarithm problem is in NP or even NP-hard, then so is ECC.)

>   As evidence of the former, I suggest you take a look at the size of
> the prime numbers being generated and tested by the Internet Mersenne
> Prime Search, for instance.  The last one found had 9,808,358 decimal
> digits, or 32,582,687 bits; compare that to the 1024 bit primes  
> used in
> a typical RSA key.  Remember, that number is not merely 32,000 times
> larger, it's 32,000 *powers* larger.

1024 bits is now too short, due to advances in factoring.
http://my.opera.com/yngve/blog/2007/05/24/1020-bit-special-number- 
factored

>  Also, despite the visibility that public-key cryptosystems have,
> symmetric block cryptosystems like Twofish, AES, Rijndael, etc. get
> much more use in practice, and they typically don't use prime-based
> calculations in any way.

Unfortunately, popularity is not a reliable indicator of security.  
Some algorithms have security proofs with various properties and of  
varying quality.

In fact, though you can construct a crypto-system from public-key  
crypto, you're stupid to do so.

You have a lot more risk of leaking the private key, and a lot more  
data protected by the key, if you do which is why a key-derivation  
function is normally present, never-mind the extra computation for no  
real gain in security.

Jim