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].
[1] http://www.nist.gov/dads/HTML/millerRabin.html
--
Jeremiah Rogers
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
[Clips] MIT Real ID Meeting Postponed to December 5th, AND Homeland Security to Propose Regulations - Join the Discussion
--- begin forwarded text Delivered-To: [EMAIL PROTECTED] Date: Wed, 9 Nov 2005 18:43:07 -0500 To: Philodox Clips List [EMAIL PROTECTED] From: R. A. Hettinga [EMAIL PROTECTED] Subject: [Clips] MIT Real ID Meeting Postponed to December 5th, AND Homeland Security to Propose Regulations - Join the Discussion Reply-To: [EMAIL PROTECTED] Sender: [EMAIL PROTECTED] --- begin forwarded text Date: Wed, 9 Nov 2005 15:16:43 -0800 (PST) From: Daniel J. Greenwood [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] Subject: MIT Real ID Meeting Postponed to December 5th, AND Homeland Security to Propose Regulations - Join the Discussion To: [EMAIL PROTECTED] ** In-Person Event Postponed to December 5th, 2005 ** This note is to inform you that the MIT Real ID Forum in-person meeting will take place on Monday, December 5th, 2005 at the Media Lab at MIT. The event will take place from 9am to 3pm. I encourage you to register, if you had not already, at http://ecitizen.mit.edu/realid.html and to participate in our pre-conference online discussion, at http://ecitizen.mit.edu/realid.html. The program had to be postponed from November 17th due to a last minute important meeting called by the Department of Homeland Security on regulations implementing the Real ID Act related to privacy. Understandably, key privacy advocates and relevant Homeland Security individuals must now attend this meeting in Washington, DC. For this reason, we have decided to postpone the event to December 5th. We apoligize for any inconvenience this may cause. ** Regulations Under Real ID -- Join the Discussion ** I invite anybody on this list who may have opinions you wish to share on the topic of Real ID regulatory issues to post those ideas to our online forum under the new topic Homeland Security Regulations. This topic thread is for participants in this Online Forum on the Real ID Act to share ideas you may have on problems and prospects associated with potential regulations under this federal law. All comments posted to this thread will be presented, as part of our conference proceedings, and published as part of our in-person conference to happen on December 5, 2005. The conference proceedings will also be presented to the Department of Homeland Security, as a record of the remarks made by participants, for their considerations as they determine how to implement the Real ID Act. I encourage you to attend the in-person meeting on December 5th at MIT and to participate in the dialog at the Online Forum. Best regards, - Daniel Greenwood Daniel J. Greenwood, Esq. Lecturer, Massachusetts Institute of Technology The Media Lab, Program of Media Arts and Science Principal, CIVICS.com The InfoSociety Consultancy http://ecitizen.mit.edu www.civics.com 1770 Mass. Ave, #205, Cambridge, MA 02140 USA [EMAIL PROTECTED] --- end forwarded text -- - R. A. Hettinga mailto: [EMAIL PROTECTED] The Internet Bearer Underwriting Corporation http://www.ibuc.com/ 44 Farquhar Street, Boston, MA 02131 USA ... however it may deserve respect for its usefulness and antiquity, [predicting the end of the world] has not been found agreeable to experience. -- Edward Gibbon, 'Decline and Fall of the Roman Empire' ___ Clips mailing list [EMAIL PROTECTED] http://www.philodox.com/mailman/listinfo/clips --- end forwarded text -- - R. A. Hettinga mailto: [EMAIL PROTECTED] The Internet Bearer Underwriting Corporation http://www.ibuc.com/ 44 Farquhar Street, Boston, MA 02131 USA ... however it may deserve respect for its usefulness and antiquity, [predicting the end of the world] has not been found agreeable to experience. -- Edward Gibbon, 'Decline and Fall of the Roman Empire' - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Pseudorandom Number Generator in Ansi X9.17
Hi, The Pseudorandom Number Generator specified in Ansi X9.17 used to be one of the best PRNGs available if I am correct. I was just wondering if this is still considered to be the case? Is it widely used in practical situations or is there some better implementation available? What would be the advantages/disadvantages of modifying the Ansi X9.17 PRNG to use AES instead of 3DES? Is this feasible at all? Best Regards, Terence _ Dating has never been easier - get FREE Match.com membership! http://match.msn.ie/match/mt.cfm?pg=channeltcid=237596 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Fermat's primality test vs. Miller-Rabin
On Wed, 9 Nov 2005, Jeremiah Rogers wrote:
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.
For large n the ratio s to log n is small (where n-1 = d 2^s) and s is
exactly the number of multiplication you may hope to avoid.
But MR will still fail when given a Carmichael number,
since elsewhere MR is defined as iterated application of the Fermat
test.
It is very easy to check.
561 is a Carmicael number (the smallest one), for example, for a = 2
2^560 = 1 (561) and the same for all a's coprime to 561.
Btw, 651 = 3*11*17, so don't try with a = 3 :-)
Let us now go to the RM test: 560 = 35 * 2^4 (d = 35 and s = 4), so,
e.g., for a = 2, 2^35 = 263 (that is a^d \ne 1) and
263^2 = 166, 166^2 = 67, 67^2 = 1 (that is a^{2^r d} \ne -1 \forall r
\in [0, s-1]), so RM test declares that 561 is composite and 2 is a
strong witness of this.
--
Regards,
ASK
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
event in NYC: The Secret World of Global Eavesdropping
Apparently there's an event at The New School on November 17th entitled The Secret World of Global Eavesdropping -- one of the panel is John Young of Cryptome fame. http://worldpolicy.org/calendar/2005/fall/05nov17.html -- Perry E. Metzger[EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Pseudorandom Number Generator in Ansi X9.17
On Thu, 10 Nov 2005, Terence Joseph wrote: The Pseudorandom Number Generator specified in Ansi X9.17 used to be one of the best PRNGs available if I am correct. I was just wondering if this is still considered to be the case? Is it widely used in practical situations or is there some better implementation available? What would be the advantages/disadvantages of modifying the Ansi X9.17 PRNG to use AES instead of 3DES? Is this feasible at all? It is now called ANSI X9.31 Appendix A.2.4 http://csrc.nist.gov/CryptoToolkit/tkrng.html and yes, there is NIST-Recommended Random Number Generator Based on ANSI X9.31 Appendix A.2.4 Using the 3-Key Triple DES and AES Algorithms http://csrc.nist.gov/cryptval/rng/931rngext.pdf Btw, anybody was lucky enough to cache the draft of X9.82 which was posted on the NIST site some time ago? -- Regards, ASK - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Pseudorandom Number Generator in Ansi X9.17
On Thu, Nov 10, 2005 at 10:33:18AM +, Terence Joseph wrote: Hi, The Pseudorandom Number Generator specified in Ansi X9.17 used to be one of the best PRNGs available if I am correct. I was just wondering if this is still considered to be the case? Is it widely used in practical situations or is there some better implementation available? What would be the advantages/disadvantages of modifying the Ansi X9.17 PRNG to use AES instead of 3DES? Is this feasible at all? Asides from the relatively small internal state, and the state compromise extension problems noted by Schneier, Wagner, et al, X9.17/X9.31 are AFAIK good PRNGs. It is very trivial to use AES instead of 3DES (just swap out the algorithms, and change the size of the various internal values to match the 128-bit block size), and you get a larger keyspace, larger internal state, and faster operation, so I'd say doing so is a complete win. Technically, X9.17 has been withdrawn by ANSI, but X9.31 contains the exact same PRNG in Appenxix A.2.4. ANSI still requires 2-key 3DES, but NIST allows the use of 3-key 3DES or of AES with any keylength instead. -Jack - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Another Skype Study
Don't recall seeing this on the list: http://www.ossir.org/windows/ supports/2005/2005-11-07/EADS-CCR_Fabrice_Skype.pdf Enjoy, Aram Perez - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
[Clips] [EMAIL PROTECTED]: [IP] Apple tries to patent 'tamper-resistant software']
--- begin forwarded text Delivered-To: [EMAIL PROTECTED] Date: Thu, 10 Nov 2005 12:00:24 -0500 To: Philodox Clips List [EMAIL PROTECTED] From: R. A. Hettinga [EMAIL PROTECTED] Subject: [Clips] [EMAIL PROTECTED]: [IP] Apple tries to patent 'tamper-resistant software'] Reply-To: [EMAIL PROTECTED] Sender: [EMAIL PROTECTED] --- begin forwarded text Date: Thu, 10 Nov 2005 13:44:24 +0100 From: Eugen Leitl [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: [EMAIL PROTECTED]: [IP] Apple tries to patent 'tamper-resistant software'] User-Agent: Mutt/1.5.9i Sender: [EMAIL PROTECTED] - Forwarded message from David Farber [EMAIL PROTECTED] - From: David Farber [EMAIL PROTECTED] Date: Wed, 9 Nov 2005 23:47:04 -0500 To: ip@v2.listbox.com Subject: [IP] Apple tries to patent 'tamper-resistant software' X-Mailer: Apple Mail (2.746.2) Reply-To: [EMAIL PROTECTED] Begin forwarded message: From: Dewayne Hendricks [EMAIL PROTECTED] Date: November 9, 2005 7:44:54 PM EST To: Dewayne-Net Technology List [EMAIL PROTECTED] Subject: [Dewayne-Net] Apple tries to patent 'tamper-resistant software' Reply-To: [EMAIL PROTECTED] Apple tries to patent 'tamper-resistant software' By Ina Fried http://news.com.com/Apple+tries+to+patent+tamper-resistant+software/ 2100-1045_3-5942107.html Story last modified Wed Nov 09 11:16:00 PST 2005 Apple Computer, which is in the process of switching to computers based on the omnipresent Intel processor, has filed a patent application describing a method for securely running Mac OS X on specific hardware. The Mac maker has applied for a patent to cover a system and method for creating tamper-resistant code. Apple describes ways of ensuring that code can be limited to specific hardware, even in a world in which operating systems can be run simultaneously, in so-called virtual machines. The patent application was made in April of 2004, but only made public last Thursday. In its application, Apple describes a means of securing code using either a specific hardware address or read-only memory (ROM) serial number. Apple also talks about securing the code while interchanging information among multiple operating systems. Mac OS X, Windows and Linux are called out specifically in the filing. This invention relates generally to the field of computer data processing and more particularly to techniques for creating tamper- resistant software, Apple says in its patent filing. Specifically, Apple refers to the technique of code obfuscation, in which software makers employ techniques that make it harder for those using debuggers or emulators to figure out how a particular block of code is working. Apple's patent application comes as the company prepares to offer its Mac OS X operating system for Intel-based chips, with the first machines slated to go on sale next year. Historically, the company has had to worry less about the Mac running on non-Apple hardware because it has used different chips and other components from those that power Windows PCs. With its move to Intel chips, though, the innards of the Mac will become more similar to those of its Windows-based counterparts. The company said it is not planning on supporting Windows or other operating systems on the Intel-based Macs it sells but has also said it doesn't plan on taking steps to prevent Mac owners from running other operating systems. We won't do anything to preclude that, Apple Senior Vice President Phil Schiller told CNET News.com in June. However, Schiller also said Apple has no plans to allow its operating system to run on non-Apple hardware. We will not allow running Mac OS X on anything other than an Apple Mac, he said. An Apple representative declined to comment Wednesday on the patent filing. Clearly, though, Apple is gearing up the intellectual property push around the Intel move. The company has reportedly been beefing up the technology that constrains the Intel versions of Mac OS X to run only on authorized machines, to this point a set of test Macs given to developers. The company has also applied for a trademark on Rosetta, its technology for running existing Mac programs on the Intel chips. Weblog at: http://weblog.warpspeed.com - You are subscribed as [EMAIL PROTECTED] To manage your subscription, go to http://v2.listbox.com/member/?listname=ip Archives at: http://www.interesting-people.org/archives/interesting-people/ - End forwarded message - -- Eugen* Leitl a href=http://leitl.org;leitl/a __ ICBM: 48.07100, 11.36820http://www.leitl.org 8B29F6BE: 099D 78BA 2FD3 B014 B08A 7779 75B0 2443 8B29 F6BE [demime 1.01d removed an attachment of type application/pgp-signature which had a name of signature.asc] --- end
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.
That is true but is not the result of a direct conclusion. Let X
represent the event that n is composite, and Y_t the event that
MILLER-RABIN(n,t) declares n to be prime. Because for a composite n there
is at least 3/4 of a's that fail the test, we can conclude that Pr(Y_t |
X) = (1/4)^t.
But the probability I think you are referring to (the one that is usually
considered the most interesting) is P(X | Y_t). It happens to be the case
that P(X | Y_t) is in fact = (1/4)^t when using uniform random
candidates, but to come to that conclusion you need to consider the fact
that the error probability of Miller-Rabin is usually far smaller than
(1/4)^t (and apply Bayes theorem and a theorem on the distribution of
prime numbers). See Note 4.47 in the Handbook of applied cryptography, or
the following paper:
http://www.cs.mcgill.ca/~crepeau/PS/BBC+87.ps
--Anton
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: How broad is the SPEKE patent.
-- From: Charlie Kaufman From a legal perspective, they would probably have a better chance with SRP, since Stanford holds a patent and might be motivated to support the challenge. The vast majority of phishing attacks and other forms of man in the middle attack seek to steal existing shared secrets - passwords, social security numbers, credit card numbers. I figured that the obvious solution to all this was to deploy zero knowledge technologies, where both parties prove knowledge of the shared secret without revealing the shared secret. Now I see that zero knowledge technologies have been deployed - or almost so: SRP-TLS-OpenSSL http://www.edelweb.fr/EdelKey/ (not quite ready for prime time) And SRP GNU-TLS http://www.gnu.org/software/gnutls/manual/html_node/ Of course, actual use of these technologies means that the browser chrome, not the web page, must set up and verify the password. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG FtM0KMPHrqFLxpaSShaR05Rlxb8CnxF4pHnz9Yqy 4RHOMGs4NJv8heDXAxtfYQ4sYI82tcElZ5wJ4qgvc - 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, 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].
That is not true, in several counts.
Firstly Miller-Rabin probabilistic primality test doesn't generate a
number, it verifies a number for primality.
Secondly, the Miller-Rabin probabilistic primality test is not based on
Fermat's Little theorem, or so called pseudoprime test, but rather on the
strong pseudoprime test, which derives from a theorem that says that if n
is an odd prime, n-1 = 2^s * r with r odd, then for any a such that
gcd(a,n) = 1 either a^r == 1 (mod n) or a^(r*2^j) == -1 (mod n) for some
j, 0 = j = s-1. See Handbook of a applied cryptography fact 4.20.
I'm affraid the reference you gave is incorrect.
--Anton
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
FW: Fermat's primality test vs. Miller-Rabin
(resending after bounce) -Original Message- From: Charlie Kaufman Sent: Tuesday, November 08, 2005 3:11 PM To: 'Travis H.'; 'cryptography@metzdowd.com' Subject: RE: Fermat's primality test vs. Miller-Rabin Is that the distinction that makes Miller-Rabin a stronger primality test? Yes. The Miller-Rabin test will fail to detect that a Carmichael number is composite 25% of the time. Thus, repeating the Miller-Rabin test many times gives ever greater confidence. Fermat's test will fail to detect that a Carmichael number is composite 100% of the time, so repeating it doesn't help (in the fringe case of a Carmichael number). In practice, the probability of randomly choosing a Carmichael number of size 250 bits is vanishingly small. The probability of a single run of Miller-Rabin or Fermat not detecting that a randomly chosen number is composite is almost vanishingly small. 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. --Charlie Kaufman -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Travis H. Sent: Tuesday, November 08, 2005 3:05 AM To: cryptography@metzdowd.com Subject: Fermat's primality test vs. Miller-Rabin In Practical Cryptography, Schneier states that the you can prove that when n is not a prime, a certain property of a mod n holds for at most 25% of possible values 1 a n. He later states that Fermat's test can be fooled by Carmichael numbers, and finally he basically says that Miller-Rabin is based on Fermat's test. It appears that Fermat's test can be fooled by Carmichael numbers, whereas Miller-Rabin is immune, but I'm not sure why. 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? It's amazing how many words that took to state, and I didn't even specify the squaring process. -- 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] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
FW: How broad is the SPEKE patent.
(resending after bounce) -Original Message- From: Charlie Kaufman Sent: Wednesday, November 09, 2005 8:59 PM To: 'James A. Donald'; [EMAIL PROTECTED]; cryptography@metzdowd.com Subject: RE: How broad is the SPEKE patent. James A. Donald said: Does SPEKE claim to patent any uses of zero knowledge proof of possession of the password for mutual authentication, or just some particular method for establishing communications? Is there any way around the SPEKE patent for mutual authentication and establishing secure communications on a weak passphrase? That's the wrong question. The patents related to SPEKE (at least the ones that have issued - there's no way to know whether there are additional submarines out there) are available free on line from the patent office. You can read the claims and make your own judgment. The right question is whether there is any strong password protocol - either known or that you invent yourself - that you can implement without fear of being sued for patent infringement. And the answer is no. Patent claims, like the U.S. Constitution, mean whatever the courts decide they mean. The only way to have confidence that you won't be sued for implementing any technology is to observe that lots of other people in similar situations to yours are doing it and not being sued. I am not aware of anyone who is publicly shipping - either in a commercial product or as open source - an implementation of a strong password protocol without having paid protection money to either Lucent or Phoenix (or both). It would be great if someone would. But proclaiming that the King is wearing no clothes is not without risk. --Charlie Kaufman - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
FW: How broad is the SPEKE patent.
(resending after bounce) -Original Message- From: Charlie Kaufman Sent: Wednesday, November 09, 2005 9:54 PM To: 'Steven M. Bellovin'; James A. Donald Cc: [EMAIL PROTECTED]; cryptography@metzdowd.com Subject: RE: How broad is the SPEKE patent. - Steven M. Bellovin wrote: Radia Perlman and Charlie Kaufman invented PDM specifically as a patent-free method. However, the claim was made that it infringed the SPEKE patent. Since it wasn't patented, there was no one willing to spend the money on legal fees to fight that claim, per a story I heard. I am not aware that any claim (in the legal sense) has been made that PDM infringed SPEKE. Radia and I were pushing PDM in various standards bodies as a strong password protocol after convincing our employers not to patent it (no easy feat!). We were approached by David Jablon, the inventor of SPEKE but no longer the patent holder, who suggested that we should not assume that PDM did not infringe SPEKE and should not make such claims to others. This was based on claims in a patent filed many years before but which through various techniques had been prevented from issuing (a practice known as 'submarining'). While we convinced our employers not to patent the protocol, we certainly weren't going to get them to defend it. That was sufficient to get us to stop promoting PDM. If anyone would like to pick it up, they are of course free to do so. From a legal perspective, they would probably have a better chance with SRP, since Stanford holds a patent and might be motivated to support the challenge. --Charlie - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
