Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #4808 > unrolled thread

bike locks and encryption

Back to article view | Back to comp.programming

Contents

  bike locks and encryption RichD <r_delaney2001@yahoo.com> - 2014-10-06 23:28 -0700
    Re: bike locks and encryption Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-10-07 11:39 +0100
      Re: bike locks and encryption Richard Heathfield <invalid@see.sig.invalid> - 2014-10-07 11:53 +0100
        Re: bike locks and encryption Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-10-07 16:24 +0100
          Re: bike locks and encryption Richard Heathfield <invalid@see.sig.invalid> - 2014-10-07 21:26 +0100
            Re: bike locks and encryption Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-10-08 01:34 +0100
            Re: bike locks and encryption RichD <r_delaney2001@yahoo.com> - 2014-10-07 23:16 -0700
        Re: bike locks and encryption RichD <r_delaney2001@yahoo.com> - 2014-10-07 23:27 -0700
    Re: bike locks and encryption RichD <r_delaney2001@yahoo.com> - 2014-10-07 13:57 -0700
      Re: bike locks and encryption Kaz Kylheku <kaz@kylheku.com> - 2014-10-07 21:21 +0000
        Re: bike locks and encryption "BartC" <bc@freeuk.com> - 2014-10-07 22:33 +0100
          Re: bike locks and encryption Jongware <jongware@no-spam.plz> - 2014-10-08 15:51 +0200
    Re: bike locks and encryption Kaz Kylheku <kaz@kylheku.com> - 2014-10-07 21:10 +0000
      Re: bike locks and encryption RichD <r_delaney2001@yahoo.com> - 2014-10-07 23:34 -0700
        Re: bike locks and encryption Kaz Kylheku <kaz@kylheku.com> - 2014-10-08 14:10 +0000
          Re: bike locks and encryption RichD <r_delaney2001@yahoo.com> - 2014-10-10 18:33 -0700

#4808 — bike locks and encryption

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

[toc] | [next] | [standalone]

#4809

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.

[toc] | [prev] | [next] | [standalone]

#4810

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

[toc] | [prev] | [next] | [standalone]

#4811

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.

[toc] | [prev] | [next] | [standalone]

#4813

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

[toc] | [prev] | [next] | [standalone]

#4818

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.

[toc] | [prev] | [next] | [standalone]

#4819

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

[toc] | [prev] | [next] | [standalone]

#4820

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.
> 
> 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 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). 
> All the postal workers involved in the delivery try to peek in the box, but none 
> can, because they don't have the key. (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.)

Like the bike lock - 
 
> Alice, however, can easily open the box, because she has the key.

Of course, for the bike lock, the combination is the key.

The idea, the point here, is to see that the lock can be 'encrypted' - 
Inserting the cylinder, after the dials have been twirled - with relative 
ease, without the key.  

Decryption is infeasible, obviously. 
What's the complexity to encrypt?
 

The one way function analogy came to me, after I faced exactly 
this situation recently.

--
Rich

[toc] | [prev] | [next] | [standalone]

#4814

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

[toc] | [prev] | [next] | [standalone]

#4816

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.

[toc] | [prev] | [next] | [standalone]

#4817

"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 

[toc] | [prev] | [next] | [standalone]

#4823

On 07-Oct-14 23:33 PM, BartC wrote:
> "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:
 > ..
> Or you could just use wire bolt-cutters to cut the chain. (And with the
> keyed lock, you might try the bump method.)

The mathematical analog of a wire bolt cutter, now *that* is exactly 
what the NSA is mortified by. (Unless they already have it. Then they 
are mortified by the thought someone else may have it as well.)

[Jw]

[toc] | [prev] | [next] | [standalone]

#4815

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.

[toc] | [prev] | [next] | [standalone]

#4821

On October 7, Kaz Kylheku wrote:
>> bicycle locks as examples of one way functions, so useful in 
>> encryption.
> 
> All the bicycle locks with which I am familiar are not one-way functions in any
> sense. 

Think harder.

> To open the lock, you must show that you either know a secret (the
> combination) 

Thus, without the combination, it's infeasible.

> 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.

well yeah
And you have to try every one.

But you missed the point completely.
Think about trying to close (mate) an opened lock, without the 
combination.  What's the complexity?  There's the one way function aspect.

--
Rich

[toc] | [prev] | [next] | [standalone]

#4824

On 2014-10-08, RichD <r_delaney2001@yahoo.com> wrote:
> On October 7, Kaz Kylheku wrote:
>>> bicycle locks as examples of one way functions, so useful in 
>>> encryption.
>> 
>> All the bicycle locks with which I am familiar are not one-way functions in any
>> sense. 
>
> Think harder.

That's clearly your preferred domain, so it makes sense you would encourage
others, but here you are required to think smarter, as well as to be better
informed.

>> 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.
>
> well yeah
> And you have to try every one.
>
> But you missed the point completely.
> Think about trying to close (mate) an opened lock, without the 
> combination.  What's the complexity?  There's the one way function aspect.

Closing the lock is just another form of unlocking the lock: changing the state
of the lock, based on knowing the combination.

The machine has a secret. If you know the secret, you can change the
machine's state from open to closed or vice versa.

The machine provides an elementary operation: you can load it with an input
value by turning the dials, and it will report whether or not that value
matches the correct combination. The machine does not compute any other
function.

You, the operator, can use this elementary operation to solve a search
problem, thereby implementing a function.

The search function can be made much faster when the lock is open, than when it
is closed. The search function for the open state is bounded only by O(D),
where D is the number of dials/digits. When the lock is closed, the search
problem is O(N = 10**D), where N is the number of combinations.

In the open situation, the search can be faster because the machine leaks
information which provides the operator with an additional operation.  The
operator can not only load a trial value and test the lock, as before, but can
also peek into the lock to determine whether the outermost dial is in the
correct position to allow passage. If that is the case, it is possible to peek
deeper, to see whether the second dial is in the correct position and so on.

These two versions of the search problem are not the opposite directions of a
one-way function. They are just variants of the same problem with different
constraints on what information is available from the "black box".

A one-way function is a calculation from M bits to N bits, where M > N.
The inverse of a one-way function isn't a function, because more than one M-bit
value corresponds to a given N-bit value. That's what "one way" means.

For example, calculating a remainder is a one-way function.  Both 31 mod 16,
and 255 mod 16 produce 15; 15 cannot be uniquely reversed to 31 or 255.
The solution set to "what positive integer, mod 16, produces 15" is an infinite
set consisting of { 15, 31, 47, 63, ... }.

[toc] | [prev] | [next] | [standalone]

#4826

On October 8, Kaz Kylheku wrote:
>>>> bicycle locks as examples of one way functions, so useful in 
>>>> encryption.
> 
>>> Mechanical locks evaluate this function mechanically, powered by 
>>> the user... 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.
> 
> > And you have to try every one.
> > But you missed the point completely.
> > Think about trying to close (mate) an opened lock, without the 
> > combination.  What's the complexity?  There's the one way function aspect.
> 
> Closing the lock is just another form of unlocking the lock: 
> changing the state of the lock, based on knowing the combination.

And how to know the combination?

> The machine provides an elementary operation: you can load it with an input
> value by turning the dials, and it will report whether or not that value
> matches the correct combination. The machine does not compute any other
> function.

> You, the operator, can use this elementary operation to solve a search
> problem, thereby implementing a function.
> The search function can be made much faster when the lock is open, 
> than when it is closed. The search function for the open state is 
> bounded only by O(D), where D is the number of dials/digits. When 
> the lock is closed, the search problem is O(N) = 10**D, where N 
> is the number of combinations.

Right!
 
> In the open situation, the search can be faster because the machine leaks
> information which provides the operator with an additional operation.  
> The operator can not only load a trial value and test the lock, as before,
> but can also peek into the lock to determine whether the outermost dial 
> is in the correct position to allow passage. If that is the case, it is 
> possible to peek deeper, to see whether the second dial is in the correct 
> position and so on.

Bravo, you solved it.  Yet you seem unaware of that - 


--
Rich

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web