4 ms·

Well, in this formulation, they're one-time passwords; but once the spy is back in the country they could get a fresh one. Of course the more complete solution

by blahedo 16y ago

Well, in this formulation, they're one-time passwords; but once the spy is back in the country they could get a fresh one. Of course the more complete solution would be public-key encryption, but they didn't know that yet in 1958---this idea of a one-way function is basically a precursor to that.

eru 16y ago
And nowadays we would probably use the discrete logarithm problem or factoring integers as the one-way functions of choice.
- cdavidcash 16y ago
  The suggested solution (modular squaring) already reduces to factoring. http://en.wikipedia.org/wiki/One-way_function#Modular_squaring_and_square_roots http://en.wikipedia.org/wiki/One-way_function#Modular_squari... (And we'd use a cryptographic hash function anyway.)
  - eru 16y ago
    Thanks!
- sirclueless 16y ago
  No, we probably wouldn't. These one-way functions have some nice properties that we use in RSA and Diffie-hellman, like commutativity and the fact that encryption is a permutation, but these properties come with caveats in that they are considerably easier to break. A simple consequence is that we need something like 1024 bits for a strong RSA key, but SHA-256 is still miles out of reach of being attackable.
tzs 16y ago
A chaining method can be used to reduce the frequency of the guard having to go back for a new password. Let F be the one-way function. You give the spy a value x0. Then you compute x1=F(x0), x2=F(x1), ..., x_n = F(x_{n-1}). The guard is given x_n. When the guard challenges the spy, the guard gives the spy x_n, the spy iterates F starting on x0 until he finds x_{n-1}, and gives that to the guard, who checks it. The guard then replaces x_n with x_{n-1} and uses that for the next challenge, and so on. This allows for n border crossings before the spy and guard need to come to headquarters for new numbers. Each spy can either have his own x_0, in which case the guard has to have an x_n for each spy, or you can have all the spies share the same x_0, or you can do something in between such as having the less important spies share a value and have your most important spies have their own values.

by blahedo 16y ago

eru 16y ago

And nowadays we would probably use the discrete logarithm problem or factoring integers as the one-way functions of choice.

cdavidcash 16y ago
The suggested solution (modular squaring) already reduces to factoring. http://en.wikipedia.org/wiki/One-way_function#Modular_squaring_and_square_roots http://en.wikipedia.org/wiki/One-way_function#Modular_squari... (And we'd use a cryptographic hash function anyway.)
- eru 16y ago
  Thanks!
sirclueless 16y ago
No, we probably wouldn't. These one-way functions have some nice properties that we use in RSA and Diffie-hellman, like commutativity and the fact that encryption is a permutation, but these properties come with caveats in that they are considerably easier to break. A simple consequence is that we need something like 1024 bits for a strong RSA key, but SHA-256 is still miles out of reach of being attackable.

tzs 16y ago

A chaining method can be used to reduce the frequency of the guard having to go back for a new password. Let F be the one-way function. You give the spy a value x0. Then you compute x1=F(x0), x2=F(x1), ..., x_n = F(x_{n-1}). The guard is given x_n. When the guard challenges the spy, the guard gives the spy x_n, the spy iterates F starting on x0 until he finds x_{n-1}, and gives that to the guard, who checks it. The guard then replaces x_n with x_{n-1} and uses that for the next challenge, and so on. This allows for n border crossings before the spy and guard need to come to headquarters for new numbers. Each spy can either have his own x_0, in which case the guard has to have an x_n for each spy, or you can have all the spies share the same x_0, or you can do something in between such as having the less important spies share a value and have your most important spies have their own values.