Re: java.security expert?

[Johan Peeters]

I am no cryptographer, so please take my comments for what they are 
worth. I am also not sure what Tom's specific concern is.

The use of the looping construct is ugly. However, it seems to me to 
faithfully implement the algorithm described. I believe the algorithm 
could be refactored so that it would not result in such ugly code, 
but I am not sure of the wisdom of that. There seems to be merit in 
sticking closely to a published and readily available algorithm.
I fail to see why the while loop was put in though. It does not alter 
the behavior of the code (if I understand 'continue steptwo', that 
is) and, in my opinion, it does not make the code any less ugly, on 
the contrary.

I am surprised that the pmin and pmax parameters are interpreted as 
only conveying information about the desired bitlength of the result. 
I don't think that is the intention of the original algorithm. It 
also seems to offer strange guarantees: the result will not be 
greater than 2^n - 1 where n is the number of bits in pmax. Surely it 
would be more intuitive either to guarantee
- that the result is no greater than pmax
- or that the result is no greater than 2^pmax - 1.
If the latter path were chosen, I assume that pmax could be an int (or perhaps 
a long).
Similar considerations obviously apply to pmin.

The guarantee that the result is prime seems rather weak considering 
that isProbablePrime() is called with argument 1. Assuming that the 
likelihood that steps 1 to 6 comes up with a prime is about 1/2, it 
seems to me that isProbablePrime() should be called with argument 100 
if the guarantee that the result of the function is prime should be 
the same as that of BigInteger.probablePrime(), i.e. 1 - 2^(-100). As 
it is, if isProbablePrime()'s implementation's guarantee is no 
stronger than documented in Javadoc and, again, assuming that steps 1 
to 6 generate a prime in 1 out of 2 cases, I think that 
generateRandomPrime() yields a prime in 2 out of 3 cases. Has anyone 
tested this?
I have a hunch that, unfortunately, the assumption that steps 1 to 6 
generate a prime 1 in 2 cases is overoptimistic. If so, the 
guarantees of the current implementation are even weaker and the 
argument to isProbablePrime() would need to be increased further to 
make them reasonable.
 
kr,

Yo

On 3 Mar 2004 at 12:03, Tom Tromey wrote:

> While debugging gcjx, I ran across some strange code in Prime.java.
> I think the intention was for the code to resemble the result of the
> appended patch.  The patch looks big, but it just wraps the body in 
a
> `while (true)' and changes a `break' to `continue'.
> 
> Any comments on this?  I didn't look up the IEEE spec that this
> references, for all I know the comments are the only part that are
> wrong.
> 
> Tom
> 
> Index: ChangeLog
> from  Tom Tromey  <address@hidden>
> 
>       * gnu/java/security/util/Prime.java (generateRandomPrime): Loop
>       as intended.
> 
> Index: gnu/java/security/util/Prime.java
> ===================================================================
> RCS file: /cvs/gcc/gcc/libjava/gnu/java/security/util/Prime.java,v
> retrieving revision 1.3
> diff -u -r1.3 Prime.java
> --- gnu/java/security/util/Prime.java 11 Aug 2002 16:34:44 -0000 
1.3
> +++ gnu/java/security/util/Prime.java 3 Mar 2004 19:12:40 -0000
> @@ -1,5 +1,5 @@
>  /* Prime.java --- Prime number generation utilities
> -   Copyright (C) 1999 Free Software Foundation, Inc.
> +   Copyright (C) 1999, 2004 Free Software Foundation, Inc.
>  
>  This file is part of GNU Classpath.
>  
> @@ -105,60 +105,64 @@
>    /*
>      See IEEE P1363 A.15.5 (10/05/98 Draft)
>    */
> -  public static BigInteger generateRandomPrime( BigInteger r, 
BigInteger a, int pmin, int pmax, BigInteger f )
> +  public static BigInteger generateRandomPrime( BigInteger r, 
BigInteger a,
> +                                             int pmin, int pmax,
> +                                             BigInteger f )
>    {
>      BigInteger d, w;
>  
>      //Step 1 - generate prime
>      BigInteger p = new BigInteger( (pmax + pmin)/2, new Random() 
);
>  
> -  steptwo:{ //Step 2
> -      w = p.mod( r.multiply( BigInteger.valueOf(2) ));
> +  steptwo:
> +    while (true)
> +      {
> +     //Step 2
> +     w = p.mod( r.multiply( BigInteger.valueOf(2) ));
> +
> +     //Step 3
> +     p = p.add( r.multiply( BigInteger.valueOf(2) ) );
> +     p = p.subtract( w );
> +     p = p.add(a);
> +
> +     //Step 4 - test for even
> +     if( p.mod( BigInteger.valueOf(2) ).compareTo( BigInteger.valueOf( 
0 ))
> +         == 0)
> +       p.add( r );
> +
> +     for(;;)
> +       {
> +         //Step 5
> +         if( p.compareTo( BigInteger.valueOf( 1 ).shiftLeft( pmax)) > 
0)
> +           {
> +             //Step 5.1
> +             p = p.subtract( BigInteger.valueOf( 1 ).shiftLeft( pmax) );
> +             p = p.add( BigInteger.valueOf( 1 ).shiftLeft( pmin) );
> +             p = p.subtract( BigInteger.valueOf( 1 ) );
> +
> +             //Step 5.2 - goto to Step 2
> +             continue steptwo;
> +           }
> +
> +         //Step 6
> +         d = p.subtract( BigInteger.valueOf(1) );
> +         d = d.gcd( f );
>  
> -      //Step 3
> -      p = p.add( r.multiply( BigInteger.valueOf(2) ) );
> -      p = p.subtract( w );
> -      p = p.add(a);
> -
> -      //Step 4 - test for even
> -      if( p.mod( BigInteger.valueOf(2) ).compareTo( 
BigInteger.valueOf( 0 )) == 0)
> -     p.add( r );
> -
> -      for(;;)
> -     {
> -       //Step 5
> -       if( p.compareTo( BigInteger.valueOf( 1 ).shiftLeft( pmax)) > 0)
> -         {
> -           //Step 5.1
> -           p = p.subtract( BigInteger.valueOf( 1 ).shiftLeft( pmax) );
> -           p = p.add( BigInteger.valueOf( 1 ).shiftLeft( pmin) );
> -           p = p.subtract( BigInteger.valueOf( 1 ) );
> -
> -           //Step 5.2 - goto to Step 2
> -           break steptwo;
> -         }
> -
> -       //Step 6
> -       d = p.subtract( BigInteger.valueOf(1) );
> -       d = d.gcd( f );
> -
> -       //Step 7 - test d
> -       if( d.compareTo( BigInteger.valueOf( 1 ) ) == 0)
> -         {
> -           //Step 7.1 - test primality
> -           if( p.isProbablePrime( 1 ) == true )
> -             {
> -                             //Step 7.2;
> -               return p;
> -             }
> -         }
> -       //Step 8
> -       p = p.add( r.multiply( BigInteger.valueOf(2) ) );
> -
> -       //Step 9
> -     }
> -    }
> -    //Should never reach here but makes the compiler happy
> -    return BigInteger.valueOf(0);    
> +         //Step 7 - test d
> +         if( d.compareTo( BigInteger.valueOf( 1 ) ) == 0)
> +           {
> +             //Step 7.1 - test primality
> +             if( p.isProbablePrime( 1 ) == true )
> +               {
> +                 //Step 7.2;
> +                 return p;
> +               }
> +           }
> +         //Step 8
> +         p = p.add( r.multiply( BigInteger.valueOf(2) ) );
> +
> +         //Step 9
> +       }
> +      }
>    }
>  }
> 
> 
> _______________________________________________
> Classpath mailing list
> address@hidden
> http://mail.gnu.org/mailman/listinfo/classpath
> 


-- 
Johan Peeters bvba
software architecture services
tel:+32 16 64900
http://www.johanpeeters.com