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]
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: 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 [1]:
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}.
[1] http://cvs.openssl.org/getfile/openssl/crypto/bn/bn.h?v=1.21
--
Regards,
ASK
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
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 [1].
I hate to jump on the bandwagon about this, but these statements fail
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
tests are probabilistic, and return answers of "composite" or "answer
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]
