[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.programming

bike locks and encryption

RichD

10/7/2014 6:28:00 AM

Something occurred to me recntly - bicycle locks
as examples of one way functions, so useful in
encryption. That is, easy to compute in encryption,
but intractable for decrytion, lacking the key.

Specifically, the combination type: 4 dials,
numbered 0..9, the cylinder mates with the receptacle
with the correct combination. Presumably, everybody
has seen one of these.

Like a good one way function, it's easy to
'encrypt' - even if you don't know the code -
but hard to 'decrypt', i.e. unlock. Details
left as an exercise.

I figure some of the members of a computer board
would be familiar with RSA, and find this cute -

--
Rich
15 Answers

Ben Bacarisse

10/7/2014 10:39:00 AM

0

RichD <r_delaney2001@yahoo.com> writes:

> Something occurred to me recntly - bicycle locks
> as examples of one way functions, so useful in
> encryption. That is, easy to compute in encryption,
> but intractable for decrytion, lacking the key.

I don't think that's a good analogy for a one-way function. Although
all one-way functions have, in some very abstract sense, a "key" (the
function's inverse is, I suppose, a key) they are not, usually,
invertable with some small amount of data acting as a key.

<snip>
--
Ben.

Richard Heathfield

10/7/2014 10:54:00 AM

0

Ben Bacarisse wrote:

> RichD <r_delaney2001@yahoo.com> writes:
>
>> Something occurred to me recntly - bicycle locks
>> as examples of one way functions, so useful in
>> encryption. That is, easy to compute in encryption,
>> but intractable for decrytion, lacking the key.
>
> I don't think that's a good analogy for a one-way function. Although
> all one-way functions have, in some very abstract sense, a "key" (the
> function's inverse is, I suppose, a key) they are not, usually,
> invertable with some small amount of data acting as a key.

I think RSA is a counter-example, isn't it? (More on that in a second.)

It is unfortunate for the OP that the world has beaten him to it on this
occasion. It is indeed the case that bicycle locks (or padlocks in general)
are a good analogy for a one-way function.

Consider: Alice designs a padlock that is unique to her. She makes one key
to fit it. She then manufactures a million Alice-locks, and distributes them
to post offices around the world. Now, whenever you want to send Alice
something securely, you pop it in a box, go to the post office, ask for an
Alice-lock, and lock the box with it. That's the one-way function (you don't
need a key for that bit). You check that you cannot unlock the box. When you
are satisfied that it is indeed so securely locked that not even you, the
sender, can open it, you send it to Alice.

All the postal workers involved in the delivery try to peek in the box (co-
incidentally, they are all called Eve), but none of them can, because they
don't have the key for the Alice-lock. (If it's a combination lock, they
could try every combination, but Alice can fix that by designing a lock with
enough digits to make trying every combination infeasible.)

Alice, however, can easily open the box, because she has the key.

The Alice-lock is Alice's Public Key. The combination is her Private Key.

RSA is a counter-example to your claim because it is a one-way function that
is invertible with only a handful of bytes. Even if you go completely
bananas with your key and have 8192 bits, that's still only a kilobyte of
data, which is considerably less than the number of bytes used to encode
this Usenet article.

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

Ben Bacarisse

10/7/2014 3:24:00 PM

0

Richard Heathfield <invalid@see.sig.invalid> writes:

> Ben Bacarisse wrote:
>
>> RichD <r_delaney2001@yahoo.com> writes:
>>
>>> Something occurred to me recntly - bicycle locks
>>> as examples of one way functions, so useful in
>>> encryption. That is, easy to compute in encryption,
>>> but intractable for decrytion, lacking the key.
>>
>> I don't think that's a good analogy for a one-way function. Although
>> all one-way functions have, in some very abstract sense, a "key" (the
>> function's inverse is, I suppose, a key) they are not, usually,
>> invertable with some small amount of data acting as a key.
>
> I think RSA is a counter-example, isn't it? (More on that in a
> second.)

I think you (and the OP) might be confusing trap-door functions with
one-way functions.

<snip>
--
Ben.

Richard Heathfield

10/7/2014 8:26:00 PM

0

Ben Bacarisse wrote:

> Richard Heathfield <invalid@see.sig.invalid> writes:
>
>> Ben Bacarisse wrote:
>>
>>> RichD <r_delaney2001@yahoo.com> writes:
>>>
>>>> Something occurred to me recntly - bicycle locks
>>>> as examples of one way functions, so useful in
>>>> encryption. That is, easy to compute in encryption,
>>>> but intractable for decrytion, lacking the key.
>>>
>>> I don't think that's a good analogy for a one-way function. Although
>>> all one-way functions have, in some very abstract sense, a "key" (the
>>> function's inverse is, I suppose, a key) they are not, usually,
>>> invertable with some small amount of data acting as a key.
>>
>> I think RSA is a counter-example, isn't it? (More on that in a
>> second.)
>
> I think you (and the OP) might be confusing trap-door functions with
> one-way functions.

My understanding of a trap-door function is that it's easy to compute in one
direction but hard to compute in the other without a crib (for example,
RSA).

My understanding of a one-way function is that it's easy to compute in one
direction but hard to compute in the other without a crib (for example,
RSA).

So yes, I may well be confusing them. ;-)



--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

RichD

10/7/2014 8:58:00 PM

0

On October 6, RichD wrote:
> bicycle locks as examples of one way function...
> Specifically, the combination type: 4 dials,
> numbered 0..9, the cylinder mates with the receptacle
> with the correct combination.

To be precise, the cable type, with the ends
that mate, not the U lock.


--
Rich

Kaz Kylheku

10/7/2014 9:11:00 PM

0

On 2014-10-07, RichD <r_delaney2001@yahoo.com> wrote:
> Something occurred to me recntly - bicycle locks
> as examples of one way functions, so useful in
> encryption.

What type of bike locks?

All the bicycle locks with which I am familiar are not one-way functions in any
sense. To open the lock, you must show that you either know a secret (the
combination) or that you posess a secret object (the key whose pattern has the
imprint of a combination). The lock itself also contains a representation of
the secret (the configuartion of tumblers, wheels or whatever) in such a way
that this is not externally visible. The secret is not functionally derived
from something else.

Locks do, however, as you suspect, compute a function. Namely, they compute the
boolean function "matches?(lock, key)" or "matches?(lock, combination)": in
other words, they evaluate the predicate whether the secret matches the lock.

Mechanical locks evaluate this function mechanically, powered by the user. For
instance, you rotate some dials to bring them to some configuration, and then
have the lock evaluate the matches? predicate by trying to pull the lock open.
The lock either says "True" by separating or "No" by refusing to separate.

Kaz Kylheku

10/7/2014 9:21:00 PM

0

On 2014-10-07, RichD <r_delaney2001@yahoo.com> wrote:
> On October 6, RichD wrote:
>> bicycle locks as examples of one way function...
>> Specifically, the combination type: 4 dials,
>> numbered 0..9, the cylinder mates with the receptacle
>> with the correct combination.
>
> To be precise, the cable type, with the ends
> that mate, not the U lock.

There is less difference between these than you think. With a cable lock, you
manually arrange some dials into a configuration.

With a keyed U-lock, there is still a combination: that combination is
imprinted as a machined pattern on the key. When the key is inserted, it moves
some pins into a configuration, which is equivalent to turning the dials,
except that since you have only one key, you can only express one combination.

Ordinary residential entrance keys are also combinations. The keys have
teeth, and these teeth arise because "valleys" between the teeth are machined
to different depths. The depths are quantized, typically to 10 possibilities,
which can be represented by the digits 0 to 9. So a key with four "valleys"
between five teeth represents a combination somewhere between 0000 and 9999.

If you know the combination number, you can machine a key which will open the
lock, and in principle, you could have all 10,000 keys made which match
that lock's "key way", and do a brute force by trying them one by one.

When you buy a lock re-keying kit which consists of replacement tumblers for
the lock, together with matching keys, you will probably see that there is a
combination number written on the packaging. That number could be used to order
additional matching tumblers, which, if installed into additional locks, will
all work with the same key.

Bartc

10/7/2014 9:34:00 PM

0

"Kaz Kylheku" <kaz@kylheku.com> wrote in message
news:20141007141104.666@kylheku.com...
> On 2014-10-07, RichD <r_delaney2001@yahoo.com> wrote:
>> On October 6, RichD wrote:
>>> bicycle locks as examples of one way function...
>>> Specifically, the combination type: 4 dials,
>>> numbered 0..9, the cylinder mates with the receptacle
>>> with the correct combination.
>>
>> To be precise, the cable type, with the ends
>> that mate, not the U lock.
>
> There is less difference between these than you think. With a cable lock,
> you
> manually arrange some dials into a configuration.
>
> With a keyed U-lock, there is still a combination: that combination is
> imprinted as a machined pattern on the key. When the key is inserted, it
> moves
> some pins into a configuration, which is equivalent to turning the dials,
> except that since you have only one key, you can only express one
> combination.

> If you know the combination number, you can machine a key which will open
> the
> lock, and in principle, you could have all 10,000 keys made which match
> that lock's "key way", and do a brute force by trying them one by one.

Physical locks can be a bit simpler to break than encrypted data.

With the cheaper cylinder-type bike locks (which only had 6**4 or 1296
combinations anyway), it's not always necessary to go sequentially through
the combinations. (By pulling it tight, differences in machining mean one
cylinder turns more tightly than the rest, so you try the 1-6 positions of
that until something gives and another one is now tight. It takes a knack.)

Or you could just use wire bolt-cutters to cut the chain. (And with the
keyed lock, you might try the bump method.)

--
Bartc

Ben Bacarisse

10/8/2014 12:34:00 AM

0

Richard Heathfield <invalid@see.sig.invalid> writes:

> Ben Bacarisse wrote:
>
>> Richard Heathfield <invalid@see.sig.invalid> writes:
>>
>>> Ben Bacarisse wrote:
>>>
>>>> RichD <r_delaney2001@yahoo.com> writes:
>>>>
>>>>> Something occurred to me recntly - bicycle locks
>>>>> as examples of one way functions, so useful in
>>>>> encryption. That is, easy to compute in encryption,
>>>>> but intractable for decrytion, lacking the key.
>>>>
>>>> I don't think that's a good analogy for a one-way function. Although
>>>> all one-way functions have, in some very abstract sense, a "key" (the
>>>> function's inverse is, I suppose, a key) they are not, usually,
>>>> invertable with some small amount of data acting as a key.
>>>
>>> I think RSA is a counter-example, isn't it? (More on that in a
>>> second.)
>>
>> I think you (and the OP) might be confusing trap-door functions with
>> one-way functions.
>
> My understanding of a trap-door function is that it's easy to compute in one
> direction but hard to compute in the other without a crib (for example,
> RSA).
>
> My understanding of a one-way function is that it's easy to compute in one
> direction but hard to compute in the other without a crib (for example,
> RSA).

s/without a crib//

> So yes, I may well be confusing them. ;-)

All things are confusingly similar if you ignore the differences!
Trap-door functions are a special case, and an analogy that is good for
a special case is not always going to be a good one for the general
case. The existence of a combination to open the padlock is such a huge
special feature, that it makes the analogy more confusing then helpful.

--
Ben.

RichD

10/8/2014 6:16:00 AM

0

On October 7, Richard Heathfield wrote:
>>> bicycle locks as examples of one way functions, so useful in
>>> encryption. That is, easy to compute in encryption,
>>> but intractable for decrytion, lacking the key.
>
>> I think you (and the OP) might be confusing trap-door functions with
>> one-way functions.
>
> My understanding of a trap-door function is that it's easy to compute in one
> direction but hard to compute in the other without a crib.
> My understanding of a one-way function is that it's easy to compute in one
> direction but hard to compute in the other without a crib.
> So yes, I may well be confusing them. ;-)
>

haha

me too!

--
Rich