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]
Re: gonzo cryptography; how would you improve existing cryptosystems?
On Fri, 4 Nov 2005, Travis H. wrote: PS: There's a paper on cryptanalyzing CFS on my homepage below. I got to successfully use classical cryptanalysis on a relatively modern system! That is a rare joy. CFS really needs a re-write, there's no real good alternatives for cross-platform filesystem encryption to my knowledge. On Mon, 7 Nov 2005, Jason Holt wrote: Take a look at ecryptfs before rewriting cfs: http://sourceforge.net/projects/ecryptfs Nice, but linux-only and requires special kernel support. cfs supports lots and lots of different OSs and doesn't require kernel modes. So far as I know, in this regard cfs is unique among cryptographic filesystems. ciao, -- -- Jonathan Thornburg [EMAIL PROTECTED] Max-Planck-Institut fuer Gravitationsphysik (Albert-Einstein-Institut), Golm, Germany, Old Europe http://www.aei.mpg.de/~jthorn/home.html Washing one's hands of the conflict between the powerful and the powerless means to side with the powerful, not to be neutral. -- quote by Freire / poster by Oxfam - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: gonzo cryptography; how would you improve existing cryptosystems?
Nice, but linux-only and requires special kernel support. cfs supports lots and lots of different OSs and doesn't require kernel modes. So far as I know, in this regard cfs is unique among cryptographic filesystems. The only thing close that I've seen is Bestcrypt, which is commercial and has a Linux and Windows port. I don't recall if the Linux port came with source or not. I had problems with the init script hanging the boot process, or at least delaying it significantly, so I uninstalled it until I could devote the time to analyze what was going on. Right after installation I tried using it to read a container copied from a corrupted Windows machine, but was not successful. It is unclear to me if this was due to the corruption which occured, or some kind of incompatibility between the Windows and Linux ports. -- 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: gonzo cryptography; how would you improve existing cryptosystems?
On Mon, 7 Nov 2005, Jason Holt wrote: Take a look at ecryptfs before rewriting cfs ... or at TrueCrypt (which works on linux and windows): http://www.truecrypt.org/downloads.php -- Regards, ASK - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: gonzo cryptography; how would you improve existing cryptosystems?
On Tue, Nov 08, 2005 at 05:58:04AM -0600, Travis H. wrote: The only thing close that I've seen is Bestcrypt, which is commercial and has a Linux and Windows port. I don't recall if the Linux port came with source or not. http://www.truecrypt.org/ TrueCrypt Free open-source disk encryption software for Windows XP/2000/2003 and Linux Main Features: * It can create a virtual encrypted disk within a file and mount it as a real disk. * It can encrypt an entire hard disk partition or a device, such as USB memory stick, floppy disk, etc. * Provides two levels of plausible deniability, in case an adversary forces you to reveal the password: 1) Hidden volume (more information may be found here). 2) No TrueCrypt volume can be identified (TrueCrypt volumes cannot be distinguished from random data). * Encryption algorithms: AES-256, Blowfish (448-bit key), CAST5, Serpent (256-bit key), Triple DES, and Twofish (256-bit key). Supports cascading (e.g., AES-Twofish-Serpent). * Based on Encryption for the Masses (E4M) 2.02a, which was conceived in 1997. Further information regarding the features of the software may be found in the documentation. Complete source code (in C) of the latest stable version of TrueCrypt for all supported operating systems and all supported hardware platforms are available from http://www.truecrypt.org/downloads.php /Thomas -- signature.asc Description: Digital signature
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]
