Re: Question for the math wizards...

From: Brian Doyle (brian_at_balance-software.com)
Date: 02/11/04 

Date: Wed, 11 Feb 2004 12:44:03 -0800

First let me say thank you very much Tom (that's two helpful replies in the
past week :-), and to the rest of you who have replied!!

Tom's comment:

> At the very least you'd have to make ||c|| >= ||m||.

was very instructive and helps me refine my requirements such that c should
be equal in size or slightly larger than m. I think what I'll do rather
than speak in the abstract to everyone is lay out what I'm trying to
accomplish and why and then hopefully we can get this nailed down
(apologies in advance if it's a bit long-winded). FIrst some background:

        My friend and I have a tiny little programming company and we're starting
to write shareware. We have one product that is doing fairly well and a
few others that we're about to release. We have a typical shareware
registration scheme in that we allow people to try our product for a few
weeks and then the program expires. If a person wants to continue to use
the program they pay us a small fee and we send them a serial number. As
our product has gained popularity, we've noticed that from time-to-time
someone releases a crack which patches our application and defeats the
serial number scheme.

        All in all, we don't mind this too much. Primarily it's because we can't
do anything about it programmatically without getting nasty (which we
choose not to do) and also because we release updates fairly frequently so
a cracker has to be very diligent in patching every version of our app that
comes out, and that never happens.

        Well a couple of weeks ago someone released a serial number generator for
our application. This is much more effective than a crack because we don't
change our serial number scheme from release to release, so it effectively
cracks our future releases too. Not only that, but since we want to re-use
our serial number engine (albeit with a different seed) across our entire
product line, it makes it very easy to release generators for our other
products.

        So this brings me to the issue at hand... we would would like to use RSA
encryption to make it computationally infeasible for someone to write a
serial number generator for our products (this won't make an iota of
difference as far as cracking goes, but as I mentioned our concern is
serial number generators not cracks), and here's what I have in mind
generally:

1) We ship our app with an embedded 512-bit (or larger) RSA public key {
n, e }.
2) Locally when someone buys the product we generate a serial number that
is about 120 bits long (m).
3) We then encrypt the serial number (m) with the corresponding 512-bit
RSA private key { n, d } to get ciphertext c.
4) We ship c to the customer where our software decrypts it with {n, e} to
get back m which is then put through the normal serial number processing
code.

Here is the main constraint:

        We need to ship to the end-user a serial number that is a human readable
string of characters that isn't too long (say no more than 25 characters),
and isn't too confusing (i.e. doesn't use easily transposable characters
such as capital letter O and zero). Really this constrains us to a base-32
representation for our serial number, so if you figure we can represent 5
bits per character with base-32 encoding, then we are limited to shipping
them a ciphertext c which encodes to 5 * 25 or 125 bits.

        Please notice that I'm using the phrase "serial number" for both m and
c... in the context of "m" as a serial number, it is the serial number
that the application uses internally to detect its registration parameters.
 In the context of "c" as a serial number, this is the string that is sent
to the user that they would think of as their personalized "serial number"
(and might look like XYZVA-12345-ABCDEF-HAHAH-BLAHB).

        So this was the motivation for the post that started this thread. When we
start out with our original serial number m and map it to c via:

m**d mod n = c

what results is a c that is in the range 0 <= c < n. If c happens to be
greater than about 125 bits, then the base-32 encoding of c produces some
huge ugly string of characters that is too long to manage. Thus I wanted
to know if it was possible given m to map m via a function F() to an m'
such that:

F( m, 125 ) = m'
m' ** d mod n = c

where the c that is generated is less than or equal to the maximum number
of bits our serial number base-32 encoding will support (125 bits).

Of course if there is a function F() that works like this, then the
decryption operation of:

c ** e mod n = m'

produces not m, but the m' that was used to feed the encryption function,
so there has to be a corresponding function F'() in the application (on the
client side) that maps m' back to m:

F'( m' ) = m

        Another important thing to remember here is that its important to deal
with who the cracker might be. Our product costs $25. We don't need
protection from the government here and the secrecy of m is a non-issue as
the whole point is to decrypt it on the client side anyway. Our objective
is to make it computationally infeasible for Joe Cracker on his home
computer (or even someone with marginally better computing resources) to
write a serial number generator (since they don't have d or the factors of
n).

        Ok, sorry for the long winded post but I hope that makes things very
clear.

What does everyone think?

Thanks again!!

Brian Doyle
brian@balance-software.com

Please feel free to email me if you like (that's my real email)... I get
so much spam I'm beyond caring whether I post my real email in newsgroups
or not :)

On 2004-02-11 04:51:32 -0800, "Tom St Denis" <tom@securescience.net> said:

>
> "Brian Doyle" <brian@balance-software.com> wrote in message
> news:2004021103383016807%brian@balancesoftwarecom...
> > In real world terms, say n is 100 digits, m is 50 digits, and I want to
> > produce a c that is no more than 10 digits long. Is it possible to
> > generate a function (and importantly, if so, how) that translates m to
m'
> > such that m'^e mod n produces a c that is no more than 10 digits long?
>
> That's not possible on it's face. 10^50 is much larger than 10^10 so the
> function could no longer be a bijection [or at least have an inverse].
>
> At the very least you'd have to make ||c|| >= ||m||.
>
> Tom

---- original message follows ---:

I have a question for the math wizards regarding modular exponentiation...

Given positive integers n, m (0 <= m < n), d, and e, in the RSA
cryptographic scheme the following relationship holds:

m^e mod n = c
c^d mod n = m

Considering an abstract m, it is obvious that c will be in the range 0 <= c
< n.

What I'd like to know is this:

If we know m, and we want c to be no larger than some value z less than n
(say n/2 or n/4 or whatever), is it possible to generate a function F that
given m produces a new m' (0 <= m' < n) that when input as:

m'^e mod n = c

generates a c that meets the requirement of being less than or equal to z?

In real world terms, say n is 100 digits, m is 50 digits, and I want to
produce a c that is no more than 10 digits long. Is it possible to
generate a function (and importantly, if so, how) that translates m to m'
such that m'^e mod n produces a c that is no more than 10 digits long?

Clearly if there is such a function (or way to generate one), it would also
be necessary given c and therefore m' (via c^d mod n = m') to have a
corresponding function F' that maps m' back to m.

I'm not a mathematician by any stretch of the imagination so I'm totally in
the dark as to the possibility of a solution here (although I know what I'd
like to do ;-). I will be extremely grateful to anyone who can help me
determine how to do this (or if it's even possible, computationally
feasible, etc.).

Thank you very much!!

Brian Doyle
brian@balance-software.com

Relevant Pages

  • Re: Paper & pencil password algorithm
    ... currently I am using a 10x10 Polybius square. ... How would you convert base 11 digits to base 10 digits with uniform ... characters to find on the keyboard. ... I'm undecided on whether it should be 2 or 3 foldsums. ...
    (sci.crypt)
  • Re: Invariant with DIGIT-CHAR-P and the reader.
    ... should appear to the Lisp reader as a number. ... >> reading of the standard makes me believe the Lisp reader should ... > Why a new CL could not accept more forms for unicode digits? ... a..z, characters chosen by the implementation, and not from some higher ...
    (comp.lang.lisp)
  • Re: Word count of minimum vocabulary
    ... >> Nor do I have to map a Japanese Kanji to a word when I read ... tie it up with any words -- whether Chinese words or Japanese ones. ... António> to add to 'ideograph being used as a logograph'? ... the characters, ...
    (sci.lang)
  • Re: Calling Bob Phillips - Please
    ... The cell can hold test strings of up to 32k characters. ... cell display. ... Therefore the maximum number of digits ... This works from row 1 to the last row and concatenates values from ...
    (microsoft.public.excel.programming)
  • Re: heard on 40m yesterday at twilight CQ DX DE G2MT EMMA TOCK cq dx in the future
    ... Radio Callsigns. ... "Identification of Stations". ... digits in the cases specified below, may be used to form call signs. ... characters or in certain cases the first character of a call sign constitute ...
    (uk.radio.amateur)