Student "pizza" problem
Roedy Green
Let's say you owned a chain of pizza stores, and you wanted to offer a
premium. The customer takes a number off a pizza box he has
purchased, and enters it into a website, to say let them play games,
or win a prize, or enter a lottery.
You want to make the numbers unique. They can only be used once. You
want to make it impossible for a bright kid to guess the numbers on
pizza boxes that he did not buy. Using Java to generate and validate
the numbers, how would you do it with the least amount of coding?
You want to keep the length of the numbers to something reasonable to
expect people to type without error.
--
Roedy Green Canadian Mind Products
http://mindprod.com
Without deviation from the norm, progress is not possible.
~ Frank Zappa (born: 1940-12-21 died: 1993-12-04 at age: 52)
Roedy Green
<see_w...@mindprod.com.invalid> wrote, quoted or indirectly quoted
someone who said :
>You
>want to make it impossible for a bright kid to guess the numbers on
>pizza boxes that he did not buy.
He also might attack you with a computer program that just tries all
possible numbers.
Wojtek
> This is an easy problem, so please give newbies first crack at it.
>
> Let's say you owned a chain of pizza stores, and you wanted to offer a
> premium. The customer takes a number off a pizza box he has
> purchased, and enters it into a website, to say let them play games,
> or win a prize, or enter a lottery.
>
> You want to make the numbers unique. They can only be used once. You
> want to make it impossible for a bright kid to guess the numbers on
> pizza boxes that he did not buy. Using Java to generate and validate
> the numbers, how would you do it with the least amount of coding?
>
> You want to keep the length of the numbers to something reasonable to
> expect people to type without error.
See:
http://mindprod.com/jgloss/homework.html
--
Wojtek :-)
Wojtek
> This is an easy problem, so please give newbies first crack at it.
Sorry, couldn't help myself...
:-))
--
Wojtek :-)
Casey Hawthorne
Solid
Banner
Numbering
On Fri, 06 Nov 2009 11:30:56 -0800, Roedy Green
<see_w...@mindprod.com.invalid> wrote:
>This is an easy problem, so please give newbies first crack at it.
>
>Let's say you owned a chain of pizza stores, and you wanted to offer a
>premium. The customer takes a number off a pizza box he has
>purchased, and enters it into a website, to say let them play games,
>or win a prize, or enter a lottery.
>
>You want to make the numbers unique. They can only be used once. You
>want to make it impossible for a bright kid to guess the numbers on
>pizza boxes that he did not buy. Using Java to generate and validate
>the numbers, how would you do it with the least amount of coding?
>
>You want to keep the length of the numbers to something reasonable to
>expect people to type without error.
--
Regards,
Casey
alexandre...@yahoo.fr
wrote:
> This is an easy problem, so please give newbies first crack at it.
>
> Let's say you owned a chain of pizza stores, and you wanted to offer a
> premium. The customer takes a number off a pizza box he has
> purchased, and enters it into a website, to say let them play games,
> or win a prize, or enter a lottery.
>
> You want to make the numbers unique. They can only be used once. You
> want to make it impossible for a bright kid to guess the numbers on
> pizza boxes that he did not buy. Using Java to generate and validate
> the numbers, how would you do it with the least amount of coding?
>
> You want to keep the length of the numbers to something reasonable to
> expect people to type without error.
>... "to type without error"
Then don't use numbers but numbers encoded in a Base32
alphabet crafted to reduce typing errors (that is, do
*not* use the RFC3548 algorithm which is pretty naive
regarding the alphabet chosen: use instead a Base32 made
on purpose to be easy on the user).
This is what people generating product key number are
doing and arguably they know more about entering
'numbers' than people writing generated lottery numbers
on pizza boxes ;)
You'll then have 32 characters per 'digit' (instead of 10),
so the 'number' is going to be smaller to enter.
;)
Now how bright is the kid? Are you looking for a security
by obscurity scheme or some modulo-math or elliptic-curve
based scheme?
As as already been stated, how big the keyspace? Because
at 3.3 bits/digit or so (like you suggest), you already need
quite a lengthy number (prone to typing error) to dodge
brute-force attacks.
Seen that I'm not here working on a defence contract, I'd
go for some security by obscurity scheme where I'd do
something like this:
- choose one of the 4 814 936 primes from, say, [1000000007 biggest:
1099999997]
(the kid doesn't know the interval I'm using)
- multiply it by another prime, that I only know (private prime) and
that
I know shall not, after discarding bits, create any dupe for the
interval
chosen (trivially easy to choose too and actually, with a sufficient
number
of bits, collision are going to be extremely rare)
- hash it using XOR and a magic number I only know
- discard bits from the 'big int' result depending on how big you want
your keyspace
For verification, it's easy... all that is needed is the interval,
the private prime, the XOR magic number (so I don't need to keep
track of all generated numbers).
I simply brute force my interval and see if I'm generating the
number the kid entered. If yes, it's a valid number... That brute
forcing knowing the interval, private prime and XOR magic number
takes one second or so on a fast machine (and make it unnecessary
to keep track of the numbers issued).
How many bits you want?
30: 1JSH9J
50: QCN2D1 - BGW7
200: JX5XG7 - D2XJ - QGAWM7 - FN8K - B1H52W - 41AF - 0GR2HV - 30HJ
(I'd probably go for less and use checkdigit, to give kid a second
chance if he mistype his number).
Heck, with 50 bits and by publishing my algorith, but not my
private prime nor the prime range nor my XOR magic number
you'd have a hard time finding a valid pizza number even with
a lot of computing power available (and 'reverse engineering'
the prime range used, forget about it...).
So a 'smart kid' that doesn't know the algo used...
Of course that's about 20 lines of code when you have methods
like primesFromNtoM( n, m ) available (but who doesn't ;) so
I realize that 20 lines of code probably don't match your
"least amount of coding".
It all depends how 'short' you want your code to be :)
P.S: Yup, Base32, really, because with Base64 you'd have
all these users perplexed by the uppercase/lowercase SNAFU
(been there, done that ;)
Roedy Green
wrote, quoted or indirectly quoted someone who said :
>This is what people generating product key number are
>doing and arguably they know more about entering
>'numbers' than people writing generated lottery numbers
>on pizza boxes ;)
This is one of my pet peeves, arbitrary codes you are supposed to type
containing both 0 and O, I and l and 1.
You want to eliminate O for example from your legal set, but treat it
if as the user typed as 0.