### Re: Fermat's primality test vs. Miller-Rabin

```  Although the Carmichael numbers fool the Fermat test
(that is, \$a^{n-1} = 1 (n)\$) for *all* a,

I thought it would work properly if a shares a factor with n.

Yes I guess the difference is that with MR you are trying to find a
number that is *likely* a prime, whereas with Fermat you are testing
primality. But MR will still fail when given a Carmichael number,
since elsewhere MR is defined as iterated application of the Fermat
test .

a basic consistency test.  Iterating a deterministic test will not
generate a probabilistic one.  And since the Fermat test fails for
Carmichael numbers, I wouldn't say that it's testing primality.   Both
unclear for a chosen basis.

MR does appear to save some exponentiations, but it also appears to
check that the last (temporally) non-1 square root of 1 we used was
-1, which it must be if n is prime, making it a stronger test than
Fermat's.  Wikipedia concurs that MR is preferred over Fermat,
primarily (pun intended) because of Carmichael numbers.
--
http://www.lightconsulting.com/~travis/  --
We already have enough fast, insecure systems. -- Schneier  Ferguson
GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### Re: Fermat's primality test vs. Miller-Rabin

```On Fri, 11 Nov 2005, Joseph Ashwood wrote:
From: Charlie Kaufman [EMAIL PROTECTED]

I've heard but not confirmed a figure of one failure in 20 million. I've
never heard an estimate of the probability that two runs would fail to
detect the composite. It couldn't be better than one failure is 20 million
squared or worse than one in 80 million.

I can confirm that that number of completely wrong. I just implemented a
small Java program to test exactly that. Each number was vetted by a single
pass of Miller-Rabin (iterations = 1). With 512-bit numbers the first 52
random guesses that pass the first test resulted in 26 numbers that failed
to pass 128 iterations. I find it rather odd that this is exactly half, and
I also notice that of those that failed they almost all seem to have failed
at least half of them.

The general consensus is that for 500-bit numbers one needs only 6 MR
tests for 2^{-80} error probability :

number of Miller-Rabin iterations for an error rate of less
than 2^-80 for random 'b'-bit input, b = 100 (taken from table
4.4 in the Handbook of Applied Cryptography [Menezes, van
Oorschot, Vanstone; CRC Press 1996]; original paper: Damgaard,
Landrock, Pomerance: Average case error estimates for the
strong probable prime test. -- Math. Comp. 61 (1993) 177-194)

#define BN_prime_checks(b) ((b) = 1300 ?  2 : \
(b) =  850 ?  3 : \
(b) =  650 ?  4 : \
(b) =  550 ?  5 : \
(b) =  450 ?  6 : \
(b) =  400 ?  7 : \
(b) =  350 ?  8 : \
(b) =  300 ?  9 : \
(b) =  250 ? 12 : \
(b) =  200 ? 15 : \
(b) =  150 ? 18 : \
/* b = 100 */ 27)

and thus a single test gives ~2^{-13}.

 http://cvs.openssl.org/getfile/openssl/crypto/bn/bn.h?v=1.21

--
Regards,

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### Re: On Digital Cash-like Payment Systems

``` Don't ever encrypt the same message twice that way, or you're likely to
fall to a common modulus attack, I believe.

Looks like it (common modulus attack involves same n, different (e,d) pairs).

However, you're likely to be picking a random symmetric key as the
message, and Schneier even suggests picking a random r in Z_n and
encrypting hash(r) as the symmetric key.

More generally, I wonder about salting all operations to prevent using
the same value more than once.  It seems like it's generally a bad
idea to reuse values, as a heuristic, and applying some kind of
uniquification operation to everything, just as it's a good idea to
pad/frame values in such a way that the output of one stage cannot be
used in another stage of the same protocol.

Since I'm on the topic, does doing exponentiation in a finite field
make taking discrete logarithms more difficult (I suspect so), and if
so, by how much?

This doesn't make sense. The discrete log operation is the inverse of
exponentiation. Doing exponentiation is a prerequisite for even
considering discrete log operations. Hence it cannot make them more
difficult.

What I really meant was, if it wasn't computed in a finite field, how
difficult would it be to compute the logarithm?  I'm just curious
about how much work factor is involved in reducing modulo n.

I also wonder about some of the implications of choosing a message or
exponent such that not enough reductions take place during
exponentiation.

I'm not sure conventional covert-channel analysis is going to be that
useful here, because the bandwidths we are looking at in this attack
model are so much greater (kilobytes to megabytes per second).

Well, it depends on how you define the attack, which wasn't defined.
If the attack is to smuggle out a key using a covert channel, it may
apply.  If the attack is to download the key on a conventional
network, it wouldn't make much difference.

Unless, of course, you're auditing network flows over a certain size
or lasting a certain amount of time.
--
http://www.lightconsulting.com/~travis/  --
We already have enough fast, insecure systems. -- Schneier  Ferguson
GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```

### RE: On Digital Cash-like Payment Systems

```  Don't ever encrypt the same message twice that way, or you're likely to
fall to a common modulus attack, I believe.

Looks like it (common modulus attack involves same n,
different (e,d) pairs).

However, you're likely to be picking a random symmetric key as the
message, and Schneier even suggests picking a random r in Z_n and
encrypting hash(r) as the symmetric key.

More generally, I wonder about salting all operations to prevent using
the same value more than once.  It seems like it's generally a bad
idea to reuse values, as a heuristic, and applying some kind of
uniquification operation to everything, just as it's a good idea to
pad/frame values in such a way that the output of one stage cannot be
used in another stage of the same protocol.

I forget the beginning of this conversation... but if you're
salting all public-key encryption operations you may as well
just use a standard RSA encryption scheme, such as OAEP or
RSA-KEM. OAEP is specified in PKCS#1, available from
http://www.rsasecurity.com/rsalabs/node.asp?id=2125; it's well-
studied and has a proof of security, and should certainly be
used in preference to any home-grown system.

If you were talking about salting something other than public
key operations, accept my apologies...

William

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

```