Re: The Elevator Problem

OK. I'll bite. I realize that whenever non-heavy crypto people tackle heavy
crypto problems, the answers are virtually always: (a) obviously wrong; (b)
proposed 400 years ago; (c) not even related to the original question; (d)
all of the above. 
 
Alice says to Bob, in front of all of the other people on the elevator: "I
have generated a large(ish) amount of large(ish) prime numbers and have
recorded all of them. I have multipled two of the numbers to get an even
larger non-prime number. I have done this a large(ish) number of times
until I have a 'large(ish)/2' set of non-prime numbers. The elements of
this set are [Alice reads off the set of non-prime numbers and Bob along
with the other people on the elevator record them.] Bob, go home and pick
one of the non-prime numbers in the set. Factor it. Use the largest prime
as a private key in your message to me. Since I know what the numbers all
are, I'll try all of them to see which one decrypts your message." 
 
Bob has to factor one large(ish) prime. 
 
Alice has to *try* an average of "large(ish)/2" private keys to decrypt
Bob's message. 
 
The other people on the elevator have to *factor* an average of
"large(ish)/2/2" number of large(ish) numbers to decrypt the message. 
 
The *relative* security then depends on the number of digits in the
large(ish) primes and the number of products in the set Alice reads to Bob.

 
E.G. 
 
Imagine that Alice previously generates 2,000,000 prime numbers, giving her
a set of 1,000,000 products. Neither Bob nor anyone else on the elevator
knows the 2,000,000 primes that Alice has generated. She reads all
1,000,000 products to Bob and everyone else on the elevator. 
 
Imagine that any given product can be factored in 100 MIP days (i.e. a 100
MHz Pentium running for 24 hours or "P-Day"). 
 
Bob factors one and only one of the numbers and uses the factor as a
private key to generate the message. 
 
Neither Alice nor anyone else on the elevator knows what product Bob picked
to factor. 
 
Alice receives the message. She takes the 2,000,000 privately recorded
primes and runs a brute force attack on the encrypted message, decrypting
it in an average of 1,000,000 tries. 
 
The other people on the elevator need to factor each number and then run it
has a brute force attempt to decrypt the message. This takes them an
average of 500,000 P-Days to factor the numbers plus whatever the brute
force time requires. 
 
The relative security develops because it is faster to generate large(ish)
primes and to brute force decryption then to factor the large(ish) primes.
The absolute time it takes to generate the primes and to brute force the
decryption sets the relative time Alice is willing to spend to get a
different relative level of security. If the nasties are the NSA, then
500,000 P-Days is too insecure. If the nasties are Alice and Bob's nosey
neighbor, then 500,000 P-Days is "excessively" secure. If Alice and Bob are
sweet patooties, and the nasty is Alice's father who runs the comp sci
department at the university, then 500,000 P-Days is about right. 
 
Now, if any of you want to waste some time, you can play "kick the newbie"
re points (a) through (d) above. 
 
--tallpaul

tallpaul writes:
> Alice says to Bob, in front of all of the other people on the elevator: "I
> have generated a large(ish) amount of large(ish) prime numbers and have
> recorded all of them. I have multipled two of the numbers to get an even
> larger non-prime number. I have done this a large(ish) number of times
> until I have a 'large(ish)/2' set of non-prime numbers. The elements of
> this set are [Alice reads off the set of non-prime numbers and Bob along
> with the other people on the elevator record them.] Bob, go home and pick
> one of the non-prime numbers in the set. Factor it. Use the largest prime
> as a private key in your message to me. Since I know what the numbers all
> are, I'll try all of them to see which one decrypts your message." 
>  
> Bob has to factor one large(ish) prime. 
>  
> Alice has to *try* an average of "large(ish)/2" private keys to decrypt
> Bob's message. 
>  
> The other people on the elevator have to *factor* an average of
> "large(ish)/2/2" number of large(ish) numbers to decrypt the message. 
>  
> The *relative* security then depends on the number of digits in the
> large(ish) primes and the number of products in the set Alice reads to Bob.
>
[...example with a set of 2 * 10^6 primes...elided]

I think there are two main (related) problems with this protocol:

(1) It does not offer great security. The time required for a brute force 
attack is only linear in the time required to execute the protocol. So Alice 
will want to start out with an enormous number of primes (the linear factor). 
Even so, the attacker's job is relatively easy.

(2) It is rather impractical. The time required to execute the protocol is
prohibitive (assuming Alice uses a huge number of primes). 

Consider the numbers in your example. Alice generates N = 2*10^6 large primes 
and transmits the 10^6 pair products -- that's on the order of .1 gigabits, or
about 12 megabytes, to transmit (assuming products around 100 bits long, so
Bob can factor one before the heat death of the universe). Bob factors one of 
the products, which should take a while for all this to be at all worthwhile.
Let's say it takes Bob approximately an hour to factor.

This will take too long to do online. Alice and Bob won't generate new keys 
for each session this way. But to limit the chance that Eve can start to 
decrypt their communications in real time to 10%, if Eve has 100
times the computing power of Bob, they'll need to negotiate a new key every
6 weeks or so. This is not so hot.

Comments ?

-Futplex <futplex@pseudonym.com>