**[chan] 411**

May 18 06:36 [raw]

The security of many key exchange systems depends upon generating very large prime numbers. As computers get faster and new algorithms take shape the difficulty of finding prime factors of a key is slowly whittled away. Whereas 2048 bit RSA was considered secure for years now some experts recommend using 4096 bit keys, made from primes larger than those used in 2048 bit keys. Generating huge primes, for instance in the 64 kilobit range to 512 kilobits is too mathematically intensive for modern computers. Such huge primes would be highly secure, but finding and proving one such prime, on average, takes a very, very long time on consumer grade hardware. And we need to find at least two such primes for DH key exchange. I have discovered a possible shortcut to this problem. I have discovered a way to generate a huge number (8000+ digits) that is guaranteed with 100% probabilty to be composite of two huge primes. There is a small problem. The number can be proved to be a composite of only two primes, but it can't be factored to show *which* primes are its factors. So of course we can't use the (p-1)(q-1) equation as is to use the numbers for DH key exchange. or can we? Since we can prove each number is composite of two huge primes much longer and harder to factor than current DH / RSA keys, We just generate two such composite numbers and it will still be magnitudes more secure than current implementations. We can use keys up to megabytes in size, which is serious overkill, but makes the point. Can you find the two prime factors of a number that is 512 thousand digits long? Now take two such composite numbers and multiply them together. Can you find any of the four prime factors in it? No, you can't. So each composite number would still have effective security much greater than current implementations that use a Miller-Rabin test. If we wanted to go real gang busters cuckoo for coco puffs paranoid, we could generate two composite numbers each a million or more digits long, guaranteed that each is the factor of two 512 digit primes, yet impossible to know which two primes are the factors. Even the user generating the keys would not know the prime factors. Numbers that huge can be treated *as if* prime even though we know they are not prime. How can you know a number is composed of two huge primes without know the factors? That's the discovery. So although I did not discover a way to quickly factor huge composite numbers (every attacker's dream), I discovered something that eliminates the need to test for primality at all. We know the number is not prime, but we know its structure is a factor of two primes. Knowing this structure is guaranteed means we have the security of a prime number approximately 1/2 the length of the composite.

**[chan] 411**

May 18 07:11 [raw]

typo: "we could generate two composite numbers each a million or more digits long" should be: "we could generate two composite numbers each a million or more bits long"

BM-2cW53MzWqtod8TA6vybdUeqd2LhTuXCX3L