Prev: HttpServletRequest setHeader
Next: Why can nsmc, local classes or anonymous classes have static members ?
From: Falk Köppe on 11 Dec 2009 17:57
Hello @all,

I have a problem implementing a pricing function (Extracting Square
Roots). The following explanation of the pricing function Extracting
Square Roots is by Cynthia Dwork and Moni Noar from their paper
"Pricing via Processing or Combating Junk Mail" (1993).

"The simplest implementation of our idea is to base the difficulty of
sending on the difficulty (but not infeasibility) of extracting square
roots modulo a prime p. Again, there is no known shortcut for this
function.

- Index:A prime p of length depending on the difference parameter; a
reasonable length would be 1024 bits.

- Definition of fp: The domain of fp is Zp. fp(x) = sqrt(x) mod p.

- Verification: Given x, y, check that y.pow(2) == x mod p.

The checking step requires only one multiplication. In contrast, no
method of extracting square roots mod p is known that requires fewer
than about log p multiplications. Thus, the larger we take the length
of p, the larger the difference between the time needed to evaluate fp
and the time needed for verification."

My wrong approach with a smaller test prime number looks like this:

public void extract() {
int primeLength = 4;
BigInteger prime = BigInteger.probablePrime( primeLength, new
SecureRandom() );

BigInteger x = BigInteger.ZERO;
BigInteger y = BigInteger.ZERO;

do {
x = x.add( BigInteger.ONE );

y = sqrt( x ).mod( prime );
} while( ! verify( x, y, prime ) );

System.out.println( x );
System.out.println( y );
System.out.println( prime );
}

private boolean verify( BigInteger x, BigInteger y, BigInteger prime )
{
return ( y.pow( 2 ).compareTo( x.mod( prime ) ) == 0 );
}

// source: faruk akgul /blog - Java's Missing Algorithm: Biginteger
Sqrt
private BigInteger sqrt( BigInteger n ) {
BigInteger a = BigInteger.ONE;
BigInteger b = new BigInteger( n.shiftRight( 5 ).add( new
BigInteger( "8" ) ).toString() );

while ( b.compareTo( a ) >= 0 ) {
BigInteger mid = new BigInteger( a.add( b ).shiftRight
( 1 ).toString() );
if ( mid.multiply( mid ).compareTo( n ) > 0 ) {
b = mid.subtract( BigInteger.ONE);
} else {
a = mid.add( BigInteger.ONE );
}
}

return a.subtract( BigInteger.ONE );
}


I don't get the concept of the pricing function at all. My head hurts.
I would really appreciate some help on how to implement the explained
function or answers on one of the following questions:
- What exactly is the domain of Zp? Are those all integer numbers from
0 to p, because everything mod p is either smaller or equal to p? That
would make y definitely a BigInteger.
- What am I exactly looking for? Am I right to increase x by one each
time the verification returned false?
- Should y be a large number given, or is it calculated in the loop
the way I implemented it?
- Do we even talk about BigIntegers only, or should x be a decimal
because of the sqrt method?
- My implementation can't be right, because, for example, it always
returns y=1 and x=1, which is verified, but probably not the point of
the pricing function.

Gosh...it's supposed to be the simplest implemenation, and I'm not
even able to get that right...where is the hole I can bury myself?
From: Thomas Pornin on 11 Dec 2009 22:37
According to Falk K�ppe <falk.koeppe(a)googlemail.com>:
> // source: faruk akgul /blog - Java's Missing Algorithm: Biginteger
> Sqrt
> private BigInteger sqrt( BigInteger n ) {
> BigInteger a = BigInteger.ONE;
> BigInteger b = new BigInteger( n.shiftRight( 5 ).add( new
> BigInteger( "8" ) ).toString() );
>
> while ( b.compareTo( a ) >= 0 ) {
> BigInteger mid = new BigInteger( a.add( b ).shiftRight
> ( 1 ).toString() );
> if ( mid.multiply( mid ).compareTo( n ) > 0 ) {
> b = mid.subtract( BigInteger.ONE);
> } else {
> a = mid.add( BigInteger.ONE );
> }
> }
>
> return a.subtract( BigInteger.ONE );
> }

That's not the method you are looking for. This one is for an
approximation of the square root computed in the field of real numbers,
whereas you want to use modular integers which are something entirely
different.

You may want to look at:
http://en.wikipedia.org/wiki/Modular_exponentiation
for a starter on modular integer. Then, proceed to the "Handbook
of Applied Cryptography": download chapter 2 from:
http://www.cacr.math.uwaterloo.ca/hac/
and read pages 67 to 70.

Then (and only then ! Mathematics make sense only if you lookup things
in the right order) proceed to:
http://en.wikipedia.org/wiki/Quadratic_residue
and especially the part titled "Complexity of finding square roots".
You will find that if you choose your prime p to be equal to 3 modulo 4,
then extracting a square root is mostly a matter of a modPow() call.


--Thomas Pornin
From: Falk Köppe on 12 Dec 2009 07:04
According to Thomas Pornin <por...(a)bolet.org>:

> That's not the method you are looking for. This one is for an
> approximation of the square root computed in the field of real numbers,
> whereas you want to use modular integers which are something entirely
> different.
>
> You may want to look at:
>    http://en.wikipedia.org/wiki/Modular_exponentiation
> for a starter on modular integer. Then, proceed to the "Handbook
> of Applied Cryptography": download chapter 2 from:
>    http://www.cacr.math.uwaterloo.ca/hac/
> and read pages 67 to 70.
>
> Then (and only then ! Mathematics make sense only if you lookup things
> in the right order) proceed to:
>    http://en.wikipedia.org/wiki/Quadratic_residue
> and especially the part titled "Complexity of finding square roots".
> You will find that if you choose your prime p to be equal to 3 modulo 4,
> then extracting a square root is mostly a matter of a modPow() call.
>
>         --Thomas Pornin

Thank you Thomas for your quick and thoughtful reply.

I started reading your literature and already noticed, that my
approach was way off, because of my false naive assumptions. The sqrt
method got deleted. I started to fix my verify method to check
congruency of modular integers:

private boolean isCongruent( BigInteger a, BigInteger b, BigInteger
n )
{
BigInteger aRemainder = a.remainder(n);
BigInteger bRemainder = b.remainder(n);

return ( aRemainder.compareTo(bRemainder) == 0 );
}

The next enlightenment you provided was an exact term of what I'm
actually looking for: finding a modular square root with a prime
modulus p (a^2 congruent to b mod p). The description of the pricing
function by Cynthia Dwork and Moni Noar does not state further details
on the prime modulus p. So there are three cases:

(1) the prime modulus p is congruent to 3 modulo 4 or
(2) the prime modulus p is 2 or
(3) the prime modulus p is congruent to 1 modulo 4.

You already said that case (1) is simple: a = b.modpow( ( p + 1 ) / 4,
p ).
Probably p must be > 2 because of case (2).
I need an algorithm for case (3).

Now the question is, what algorithm to use to find the modular square
root with a prime modulus p congruent to 1 modulo 4. The Shanks-
Tonelli Algorithm (http://www.math.vt.edu/people/brown/doc/sqrts.pdf
starting on page 91) seems to be a solution. I found a python
implementation of that algorithm (http://eli.thegreenplace.net/
2009/03/07/computing-modular-square-roots-in-python/), which I don't
trust/understand completely. I could not find a java implementation of
the Shanks-Tonelli Algorithm. I can't convice my head just yet that
this algorithm was meant by Cynthia Dwork and Moni Noar in their paper
"Pricing via Processing or Combating Junk Mail" (1993).


I feel like I'm getting closer, but I'm not there yet...
- Are there better/other algorithms for finding a modular square root
with a prime modulus?
- Is there a java implementation of such an algorithm?
- I assume that the pricing function works by me providing prime p and
integer b. Then I ask for integer a with a^2 congruent to b mod p.
Wouldn't it be unfair if the prime modulus p is case (3) for some and
case (1) or case (2) for others? Is b an arbitrary integer number > 0
or are there any requirements on b?


Sorry, it took me about five hours to write this response, so please
excuse any clouded parts. I hope it still makes sense.
From: Thomas Pornin on 12 Dec 2009 17:02
According to Falk K�ppe <falk.koeppe(a)googlemail.com>:
> private boolean isCongruent( BigInteger a, BigInteger b, BigInteger
> n )
> {
> BigInteger aRemainder = a.remainder(n);
> BigInteger bRemainder = b.remainder(n);
>
> return ( aRemainder.compareTo(bRemainder) == 0 );
> }

You may want to use mod() instead of remainder(): mod() will return
a more appropriate result for a negative source value. For positive
integers, remainder() and mod() return the same value (but 'mod' is
shorter, thus easier to type than 'remainder').


> Probably p must be > 2 because of case (2).

Since p is a prime number, it is either equal to 2, or odd. Modulo 2,
there are only two values (0 and 1) and each of them has a square root
which is equal to itself. That's not interesting for what you are after.
The 'pricing' protocol you want to implement makes sense only for
large prime values, thus values of p which are odd.


> You already said that case (1) is simple:
> a = b.modpow( ( p + 1 ) / 4, p ).

A word of caution here: not every value modulo p has a square root.
Actually, if p = 3 mod 4, and b is not 0 modulo p, then either b has two
distinct square roots, or b has no square root. Moreover, if b has
square roots, then -b (i.e. 'p-b') has none, and vice versa.

The expression above always 'works' in that it computes a value 'a'
from 'b', but if b has no square root then the compute 'a' cannot be
a square root for b. Practically, if b has no square root, then the
expression above computes 'a' as a square root of -b. To test for
that, verify that the computed 'a', when squared, yields b
(i.e. a.multiply(a).mod(p).equals(b), assuming that 0 <= b < p).
Alternatively, computing a square root of either b or -b, whichever
fits, may be exactly what you want as a pricing function.


> I need an algorithm for case (3).

Not necessarily. In the protocols described by Dwork and Naor, the
prime p may be fixed; actually, it should be fixed, once and for all,
and everybody should use that p. You then are free to select a p
which is convenient, i.e. equal to 3 modulo 4.

Alternatively, you may implement the Shanks-Tonelli algorithm from
its mathematical description. The description in Wikipedia:
http://en.wikipedia.org/wiki/ShanksTonelli_algorithm
is theoretically sufficient, but somewhat terse. There is a better
description in IEEE P1363 (Annex A) but that standard is not freely
available for download.
(If you google-search for 'P1363-A-11-12-99.pdf' then you may find
a few hits; however, I doubt that these downloads are legal, in the
sense of 'compatible with the IEEE copyright policy'.)

At that point, if you want to implement a pricing protocol as roughly
described by Dwork and Naor, then you really need to have some basic
understanding of the underlying mathematics. Basically, you should know
of modular integers and algorithms for computations with such numbers.
Beside the Handbook of Applied Cryptography (in particular chapters 2
and 14), I recommend the book "A Course in Number Theory and
Cryptography" by Neal Koblitz (easy to find on Amazon).


> Is b an arbitrary integer number > 0 or are there any requirements on b?

The Dwork-Naor article describes b as being computed with a hash
function on a some data which includes the source message, the sending
date and the destination address. The point is to make it impossible for
the sender to reuse the same b for several messages (the pricing
function makes sense only if the sender must 'pay' the price for each
sent message). You will need to specify some conventions on that step
(which hash function to use, how to encode the data and so on), which is
not infeasible but requires that you master some notions about
mathematics and cryptography. You are in for some learning.


--Thomas Pornin
From: Falk Köppe on 12 Dec 2009 19:55
Hello Thomas,

I just want to leave a quick note to really thank you for your effort
and endurance. I will step through your suggestions tomorrow.

Greetings
Falk Köppe
 |  Next  |  Last
Pages: 1 2
Prev: HttpServletRequest setHeader
Next: Why can nsmc, local classes or anonymous classes have static members ?