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

``` I guess the small increase in efficiency would not be worth additional
program code.

That depends on the size of the numbers you're working with...
Considering the research that goes into fast implementations of
PowerMod I don't think the required computation is trivial.

Although the Carmichael numbers fool the Fermat test
(that is, \$a^{n-1} = 1 (n)\$) for *all* a, there are no such things for
the Miller-Rabin test:  for any odd composite n at least 3/4 of a's
fail the test, that is if you made m MR tests with random a's then you
are mistaken with probability at most (1/4)^m.

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 [1].

--
Jeremiah Rogers

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

```

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

``` It appears that Fermat's test can be fooled by Carmichael numbers,
whereas Miller-Rabin is immune, but I'm not sure why.

Where does it say Miller-Rabin is immune to Carmichael numbers? It
seems confusingly worded and says that Fermat's Test is not immune to
Carmichaels, but this does not imply M-R is immune. Additionally, the
book says We limit the probability of a false result [with M-R] to
2^(-128) to achieve our required security level.

It appears that
M-R tests that just before the squaring of a that produces a residue
of 1, is the residue n-1.  Apparently that's not true for most bases
of Carmichael numbers.  Is that the distinction that makes
Miller-Rabin a stronger primality test?

To me it looks like M-R just eliminates some needless computation that
a naive application of the Fermat test would require. Computing a^n -
a (mod n) is harder than computing smaller powers of a and checking
each of those. This is why s the largest s such that 2 does not divide
s is found. If one power q is such that a^(sq) - a != 0 (mod n)
then continued squaring isn't going to generate a power of a that is
congruent to 1.

The n vs n-1 distinction appears only when discussing if x^2 - 1
= 0 (mod n). This is why M-R fails for n=2.

--
Jeremiah Rogers

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

```

### Re: Java: Helping the world build bigger idiots

```It used to be that checking bounds on certain collections was less
efficient than waiting for the out of bounds exception. I think Joshua
Bloch discusses this in his book.

I've also seen this in generated code where you aren't sure of the
nature of the object you're indexing and thus don't know the
appropriate length variable (.length vs .length()).

That said it's still awful.

On 9/19/05, Peter Gutmann [EMAIL PROTECTED] wrote:
Found on the Daily WTF, http://www.thedailywtf.com/forums/43223/ShowPost.aspx:

try {
int idx = 0;

while (true) {
displayProductInfo(prodnums[idx]);
idx++;
}
}
catch (IndexOutOfBoundException ex) {
// nil
}

The editor also comments that when he got the first few of these submitted he
rejected them as being faked, but ended up with so many that he realised this
usage must be relatively common.

Peter.

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

--
Jeremiah Rogers

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

```

### Re: Feature or Flaw?

```
This site is set so that there is a frame of https://www.bankone.com
inside my https://slam.securescience.com/threats/mixed.html site. The
imaginative part is that you may have to reverse the rolls to
understand

the impact of this (https://www.bankone.com with
https://slam.securescience.com frame - done via cross-user attacks
trivially).

Let me get this right: here we have a page which appears to be from
domain A, but in fact it has frame(s) which display domain B. This
allows a page to have the content from domain B but the outward
appearance is of domain A, including the SSL lock on the page which

It looks like this allows
one to spoof domain A quite successfully, unless I'm missing
something.

Jeremiah

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

```

### origin of SHA 224 initial hash values

```I'm having trouble pinpointing the origin of the initial hash values
for SHA 224 and, for that matter, 128. These values are defined as hex
representations of cube roots of primes for sha-1 of lengths 256, 384
and 512, but  I can't find where they were obtained for the shorter
lengths.

Thanks and apologies if this is something well known.

- jeremiah

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

```

### Re: A-B-a-b encryption

```On Nov 16, 2003, at 12:24 PM, lrk wrote:
Stupid crypto, probably. Unless I'm missing something, this only
works
if A(A(M)) = M. Symetric crypto, not just symetric keys.

NEVER willingly give the cryptanalyst the same message encrypted with
the same system using two different keys.
For the simple case, suppose F(X) = X ^ S (exclusive or with a string
generated from the key).
Then  M = A(M) ^ B(M) ^ B(A(M)), right?

Probably something similar for other symetric systems.
This is Shamir's Three-Pass protocol and it doesn't require a symmetric
system, it requires a commutative system. See Schneier p 516 (section
22.3) or [1] for details.

so A(A(M)) != M

Unless I'm mistaken, this commutative system does not leak information
in the same way as XOR does.

- Jeremiah

[1] http://www.afn.org/~afn21533/keyexchg.htm

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

```