Prev: HttpServletRequest setHeader
Next: Why can nsmc, local classes or anonymous classes have static members ?
From: Falk Köppe on 15 Dec 2009 17:24
Hello Thomas,

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
From: Lew on 15 Dec 2009 17:41
Falk Köppe wrote:
> 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
From: Falk Köppe on 16 Dec 2009 03:39
Hello Lew,

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
From: Lew on 16 Dec 2009 09:44
Falk Köppe wrote:
> 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;
>> }

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
From: Thomas Pornin on 16 Dec 2009 10:12
According to Falk K�ppe <falk.koeppe(a)googlemail.com>:
> 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.

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
First  |  Prev  | 
Pages: 1 2
Prev: HttpServletRequest setHeader
Next: Why can nsmc, local classes or anonymous classes have static members ?