Implementing a pricing function (Extracting Square Roots)
Falk Köppe
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?
Thomas Pornin
> // 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
Falk Köppe
> 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.
Thomas Pornin
> 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
Falk Köppe
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
Falk Köppe
sorry, that my answer is late, but I had too much to do the last two
days. First I want to thank you again for your effort to help me to
better understand modular integer arithmetic. Specially your
literature paved the way for my better understanding.
> 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').
I changed the function accordingly.
> 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.
I decided to go this way and use a prime modulus p congruent to 3 mod
4. This is implemented with the following function, which returns a
random prime with numBits number of bits and the characteristic of
beeing congruent to 3 mod 4. I can't decide yet, if the prime p should
be fixed or not, because I want to regulate the difficulty or time it
takes to find a square root.
private BigInteger findConvenientPrime(int numBits) {
boolean foundConvenientPrime = false;
Random random = new SecureRandom();
BigInteger result = null;
while (!foundConvenientPrime) {
result = BigInteger.probablePrime(numBits, random);
if (isCongruent(result, BigInteger.valueOf(3),
BigInteger.valueOf(4)) {
foundConvenientPrime = true;
}
}
return result;
}
> 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).
I create a random BigInteger value b, with 0 <= b < p. This would be
my equivalent to the proposed hash function. Because I can't accept
values b that don't have a square root, the following algorithm
increments b by one until a value b is found that has a square root.
// finds the square root of the first integer starting with b
// that has a square root
public BigInteger findSquareRoot(BigInteger b, BigInteger p) {
BigInteger squareRoot = null;
if (p.compareTo(BigInteger.valueOf(2) == 0) {
squareRoot = b;
}
else {
boolean foundSquareRoot = false;
while (!foundSquare) {
squareRoot = b.modpow(p.add(BigInteger.ONE)
.divide(BigInteger.valueOf(4)), p)
if (isCongruent(squareRoot.multiply(squareRoot), b, p) {
foundSquareRoot = true;
} else {
b = b.add(BigInteger.ONE);
}
}
}
return squareRoot;
}
So if someone is unlucky, than she gets a value b that does not have a
square root and needs to try as long as she finds a square root. The
reason I need a square root is, that if I would accept null values,
then I can't be sure she really calculated the challenge, instead of
just returning null. To check, if she said the truth I would have to
calculate the square root myself, which defeats the purpose of the
pricing function. I'm not interested in the actual square root, but in
the fact, that she really calculated it.
I will now try to regulate the number of bits of prime p and the
number of bits of value b to figure out how it effects the time it
takes to find a square root with the given algorithm.
Greetings,
Falk Köppe
Lew
> private BigInteger findConvenientPrime(int numBits) {
> boolean foundConvenientPrime = false;
> Random random = new SecureRandom();
> BigInteger result = null;
>
> while (!foundConvenientPrime) {
> result = BigInteger.probablePrime(numBits, random);
>
> if (isCongruent(result, BigInteger.valueOf(3),
> BigInteger.valueOf(4)) {
> foundConvenientPrime = true;
> }
> }
>
> return result;
>
Alternative idioms
1)
private BigInteger findConvenientPrime(int numBits) {
Random random = new SecureRandom();
BigInteger result;
boolean found;
do {
result = BigInteger.probablePrime( numBits, random );
found = isCongruent( result, BigInteger.valueOf(3),
BigInteger.valueOf(4) );
} while ( ! found );
return result;
}
2)
private BigInteger findConvenientPrime(int numBits) {
Random random = new SecureRandom();
BigInteger result;
for ( boolean found = false; ! found;
found = isCongruent( result, BigInteger.valueOf(3),
BigInteger.valueOf(4) )
) {
result = BigInteger.probablePrime( numBits, random );
}
return result;
}
3)
private BigInteger findConvenientPrime(int numBits) {
Random random = new SecureRandom();
while ( true ) {
final BigInteger result = BigInteger.probablePrime( numBits,
random );
if ( isCongruent( result, BigInteger.valueOf(3),
BigInteger.valueOf(4) ) {
return result;
}
}
}
This code hasn't been compiled, much less tested, so it might contain
typos.
--
Lew
Falk Köppe
thanks for your improvement. I really liked your first implementation
and changed my function accordingly.
> 1)
> private BigInteger findConvenientPrime(int numBits) {
> Random random = new SecureRandom();
>
> BigInteger result;
> boolean found;
> do {
> result = BigInteger.probablePrime( numBits, random );
>
> found = isCongruent( result, BigInteger.valueOf(3),
> BigInteger.valueOf(4) );
> } while ( ! found );
>
> return result;
> }
Greetings,
Falk Köppe
Lew
Each has something to recommend it. #1 is probably the easiest to read. #2
limits the scope of 'found' to the loop, a good thing since 'found' is the
most temporary of the variables. #3 (which could have used 'for(;;)' instead
of 'while(true)') eliminates 'found' altogether, limits the scope of 'result'
to the loop, and makes the 'result' variable 'final'.
--
Lew
Thomas Pornin
> my equivalent to the proposed hash function. Because I can't accept
> values b that don't have a square root, the following algorithm
> increments b by one until a value b is found that has a square root.
You have several other ways.
I assume that your protocol is some kind of interactive protocol where
one party dynamically issues the challenge, and the other party returns
the square root. You want the first party (let's call it A) to use much
less CPU than the second party (B).
1. Party A creates a random integer a modulo p (0 < a < p), computes
b = a^2 mod p (in Java, b = a.multiply(a).mod(p)). b is the challenge.
Party B must then respond with c, a square root of b modulo p. Party
A verifies that either c = a, or c = p-a.
2. Party A creates a random integer b modulo p (0 < b < p). b is the
challenge. If b is a square, -b is not, and vice versa. Party B
computes c which is a square root of b or -b. Party A verifies that
the c^2 mod p is equal to either b or p-b.
Either of those protocols makes things substantially easier to
implement. Only the second protocol is amenable to non-interactive use,
i.e. replacing party A with a hash function.
> I will now try to regulate the number of bits of prime p and the
> number of bits of value b to figure out how it effects the time it
> takes to find a square root with the given algorithm.
Note that BigInteger, while being quite fine in many ways, is not the
fastest implementation of modular arithmetics that you may find. For
modular square root extraction, native code libraries such as gmp will
crunch numbers about ten times faster on a recent PC (in 64-bit mode).
--Thomas Pornin