Re: Padding Question (Cramer-Shoup 98 Crypto System)

From: Kristian Gjøsteen (kristiag+news_at_math.ntnu.no)
Date: 11/22/04 

Date: Mon, 22 Nov 2004 09:36:42 +0000 (UTC)

Oliver Moeller <omoeller@verify-it.de> wrote:
>I have a Java implementation of Cramer-Shoup 98 Crypto System (see links
>below). Version 2.1 now guarantees to de-crypt to the original message by
>introducing a safe way to pad the clear text message up to the required block
>size.
>
>They padding I chose is rather straightforward:
>
>(I)
>Always append a bit pattern of fixed (16 bits) length:
> 1000 1000 1000 1000
>The encryption does pad the message with a pattern (01|10)*[0]?, where
>01 / 10 are picked uniformly random.
>
>For n > 16 (realistic values are around 2000), this reduces the number of
>messages from 2^n to (at least) 2^((n-16)/2).

Why so complicated?

Your message is a bit string of length l. What you need to do (if you
are using F_p* where p is a safe prime) is to embed that bit string as
a quadratic residue.

Assume p is k+1 bits long, and that l < k-9. Append a single 1 followed
by k-8-l 0 bits to the message. The result is exactly k-7 bits long.

Now append 0000000, and check if the resulting binary string has Legendre
symbol 1 when interpreted as an element in F_p*. If it doesn't, try
0000001, 0000010, 0000011, etc.

To extract the embedded message, discard the final 7 bits, then any
trailing zeros, then one one.

This embedding procedure will fail with a probability of roughly 2^128.
Many systems designers can accept that.

The cost is 10 bits plus an expected 2 Legendre symbol evaluations, which
corresponds roughly to two multiplications.

If you pardon my horrible Java code, this is the simplest possible
code I can come up with.

BigInteger embed_message_as_qr(BigInteger p, BigInteger m)
{
        int i;

        m = m.shiftLeft(1).setBit(0);
        m = m.shiftLeft(p.bitLength()-9-m.bitLength());

        for (i = 0; i < 128; ++i)
        {
                if (Legendre(m,p) == 1)
                        return m;
                m.add(BigInteger.ONE);
        }
        return BigInteger.ONE.negate();
}

Implementing Legendre(x,p) is left as an exercise for the reader. 

-- 
Kristian Gjøsteen

Relevant Pages

  • Re: return multiple rows from sql statement
    ... strings from input values is almost certainly a safe path to SQL ... Also, being a MySQL function, it knows what MySQL needs or uses. ... The insert of what surprisinlgly was NOT a syntax error, but a string called "mysql_insert_id" into an integer field resulted in the value zero being put in. ... derived form..now normally I update the database, then read the data from the database back into the form: In this case I was testing 'failed to update, re-enter some data' and the backslashed stuff gave me issues with quotes and backslashes. ...
    (comp.lang.php)
  • Re: return multiple rows from sql statement
    ... strings from input values is almost certainly a safe path to SQL ... Note the order of quotes and dots. ... The insert of what surprisinlgly was NOT a syntax error, but a string called "mysql_insert_id" into an integer field resulted in the value zero being put in. ... I did have an issue with redisplaying data that had come from a POST derived form..now normally I update the database, then read the data from the database back into the form: In this case I was testing 'failed to update, re-enter some data' and the backslashed stuff gave me issues with quotes and backslashes. ...
    (comp.lang.php)
  • Re: Simple and safe evaluator
    ... in string into an abstract symbol tree. ... Python would just use the ast internally to create code. ... fileconstructor not accessible in restricted mode ... evalexploit has to be entered via the "safe" eval to start with. ...
    (comp.lang.python)
  • Re: return multiple rows from sql statement
    ... strings from input values is almost certainly a safe path to SQL ... All characters that are entered in the fields make their way into the database unaltered. ... The insert of what surprisinlgly was NOT a syntax error, but a string called "mysql_insert_id" into an integer field resulted in the value zero being put in. ... Any POST data that needs to be inserted into input fields and the like - ...
    (comp.lang.php)
  • Re: return multiple rows from sql statement
    ... strings from input values is almost certainly a safe path to SQL ... Also, being a MySQL function, it knows what MySQL needs or uses. ... All characters that are entered in the fields make their way into the database unaltered. ... The insert of what surprisinlgly was NOT a syntax error, but a string called "mysql_insert_id" into an integer field resulted in the value zero being put in. ...
    (comp.lang.php)