Cryptography-Digest Digest #660
Cryptography-Digest Digest #660, Volume #13 Thu, 8 Feb 01 20:13:01 EST Contents: Re: NPC (Benjamin Goldberg) Re: Mod function (Jerry Coffin) Q: WEP (Mok-Kong Shen) Re: Mod function (Mok-Kong Shen) Re: relative key strength private vs public key (Roger Schlafly) Re: Enigma replicas ? (digiboy | marcus) Re: File encryption with Rijndael (John Myre) Re: relative key strength private vs public key (Steve Portly) Re: ECDSA certs (=?ISO-8859-1?Q?Tom=E1s?= Perlines Hormann) Re: MIKE - alternative to SPEKE and PAK ("Michael Scott") Re: Encrypting Predictable Files [now on AONTs] ("parag") Re: Phillo's alg is faster than index calculus ([EMAIL PROTECTED]) Re: Disk Overwriting (Kat Hopwood) Re: Mod function (Jerry Coffin) Re: Encrypting Predictable Files [now on AONTs] ("Joseph Ashwood") From: Benjamin Goldberg <[EMAIL PROTECTED]> Subject: Re: NPC Date: Thu, 08 Feb 2001 21:15:40 GMT Peter Shugalev wrote: > > I think someone tried to prove that either discrete log or factoring > problem is NPC (not just NP). I'd like to see some results of these > attempts. > > And if they are *not* NPC. Do you know any attempt to create a public > key algorithm based on the problem that is known to be NPC? Assuming that P!=NP, then any NP complete problem takes exponential time in worst case. All known algorithms for doing factoring and DL take more than polynomial time, but less than exponential time. I believe (but am not certain) that they belong in a class (or maybe two seperate classes) of superpolynomial hard problems, seperate from NP complete problems. The knapsack problem is NP complete, but the most of the PKE systems which use it are broken due to lattice attacks (their method of transforming a hard problem into a PKE system is flawed). The only knapsack-like system which isn't broken by lattice attack is NTRU. I don't know of any other NPC problems which are used as ciphers. Maybe someone else does? -- A solution in hand is worth two in the book. Who cares about birds and bushes? -- From: Jerry Coffin <[EMAIL PROTECTED]> Subject: Re: Mod function Date: Thu, 8 Feb 2001 14:17:38 -0700 In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says... [ ... ] > Logic doesn't get in the way of greed. You would think that > it would similarly be impossible for anyone to patent the > use of XOR to draw and erase a cursor in a bitmap, but > exactly that did occur and was the source of litigation. Like most people who mention this patent, you're _grossly_ mis- characterizing it -- in fact, what you mention is specifically cited in the patent as prior art. Yes, there was litigation. Yes, the patent was upheld, and yes, that's because the patent covers things you haven't mentioned, and nobody (before, during or since the trial) has come up with even the slightest reason to believe that anybody had actually come up with the patented technique before the patent holders did. Above and beyond that, everybody I've ever met who has actually done their homework and read the patent almost immediately says something like "Geeze -- now that really IS cool; why didn't I think of that?" -- Later, Jerry. The Universe is a figment of its own imagination. -- From: Mok-Kong Shen <[EMAIL PROTECTED]> Subject: Q: WEP Date: Thu, 08 Feb 2001 22:45:00 +0100 Could some knowledgeable person give a bit useful information about the WEP (Wired Equivalent Privacy) algorithm that is used in WLANs? I haven't heard of it before but read today in a newspaper article that certain security problems were found in it by scientists in Berkeley. Thanks in advance. M. K. Shen -- From: Mok-Kong Shen <[EMAIL PROTECTED]> Subject: Re: Mod function Date: Thu, 08 Feb 2001 22:52:07 +0100 Jerry Coffin wrote: > > [EMAIL PROTECTED] wrote: > > Logic doesn't get in the way of greed. You would think that > > it would similarly be impossible for anyone to patent the > > use of XOR to draw and erase a cursor in a bitmap, but > > exactly that did occur and was the source of litigation. > > Like most people who mention this patent, you're _grossly_ mis- > characterizing it -- in fact, what you mention is specifically cited [snip] Is that patent available online? Could someone give the URL? Thanks. M. K. Shen -- From: Roger Schlafly <[EMAIL PROTECTED]> Subject: Re: relative key strength private vs public key Date: Thu, 08 Feb 2001 13:56:37 -0800 DJohn37050 wrote: > NIST has agreed that the minimum DSA key size is 1024 bits. This will be made > explicit in the update to DSA (aka DSA-2) that
Cryptography-Digest Digest #660
Cryptography-Digest Digest #660, Volume #12 Tue, 12 Sep 00 05:13:01 EDT Contents: Re: SV: Intel's 1.13 MHZ chip (John Savard) Re: CAST-Cipher / CAST-Algorithm (John Savard) Re: RSA public exponent ("Scott Fluhrer") Re: Camellia, a competitor of AES ? (Hideo Shimizu) Re: Getting Started, advice needed (FAQs , yes I read them) (Andy C) Re: Camellia, a competitor of AES ? (Hideo Shimizu) Re: Getting Started, advice needed (FAQs , yes I read them) (Andy C) Re: Camellia, a competitor of AES ? (Hideo Shimizu) Re: Getting Started, advice needed (FAQs , yes I read them) (Andy C) Re: Getting Started, advice needed (FAQs , yes I read them) (Andy C) Re: CRC's as MAC's (D. J. Bernstein) Re: Scottu19 Broken (Johnny Bravo) Re: RSA public exponent (Thomas Pornin) Re: nice simple function (Mok-Kong Shen) Re: Steganography and secret sorting (Mok-Kong Shen) Re: Camellia, a competitor of AES ? (Mok-Kong Shen) Re: Camellia, a competitor of AES ? (Mok-Kong Shen) From: [EMAIL PROTECTED] (John Savard) Subject: Re: SV: Intel's 1.13 MHZ chip Date: Tue, 12 Sep 2000 05:03:49 GMT On Sun, 10 Sep 2000 01:29:25 GMT, [EMAIL PROTECTED] (John Savard) wrote, in part: >K - kilom - milli 1 000 Oops, that should have been small k for kilo. John Savard http://home.ecn.ab.ca/~jsavard/crypto.htm -- From: [EMAIL PROTECTED] (John Savard) Subject: Re: CAST-Cipher / CAST-Algorithm Date: Tue, 12 Sep 2000 05:17:29 GMT On Mon, 11 Sep 2000 23:33:03 +0100, "Brian Gladman" <[EMAIL PROTECTED]> wrote, in part: >> > can anyone of you send or tell me where to get a good description of >> > the (function of the) CAST-Cypher / CAST-Algorithm (256-bit version >> > pereferred). It would also be great if you coud send me or tell me >> > where to get an implementation (C++-source-code preferred) of said >> > cipher / algorithm. >I have a C version of the CAST cipher submitted in AES round one on my >web site at: >http://www.gladman.uk.net/ >It would be easy to put into C++ Since you (the original poster) are interested in CAST-256, the AES entrant, my web page has a description of that cipher on it, complete with a diagram, at: http://home.ecn.ab.ca/~jsavard/crypto/co040810.htm John Savard http://home.ecn.ab.ca/~jsavard/crypto.htm -- From: "Scott Fluhrer" <[EMAIL PROTECTED]> Subject: Re: RSA public exponent Date: Mon, 11 Sep 2000 22:16:24 -0700 Bob Silverman <[EMAIL PROTECTED]> wrote in message news:8pk2e3$vab$[EMAIL PROTECTED]... > In article <[EMAIL PROTECTED]>, > lcs Mixmaster Remailer <[EMAIL PROTECTED]> wrote: > > > > Keep in mind that phi(n) and lambda(n) are equivalent for this > purpose, > > because phi(n) and lambda(n) factor into the same primes (albeit > possibly > > with different exponents). Hence to be relatively prime to one is to > > be relatively prime to the other. > > Not quite. We have (2, lambda(N)) = 1, whereas (2, phi(N)) = 2. > Huh? lambda(N) (for N in the form pq, for odd primes p and q) is always even, and hence (2, lambda(N)) = 2. For such N, lambda(N) = lcm(p-1, q-1). Since p-1 and q-1 are both even, then their least common multiple must also be even. For example, if N=15=3*5, then, phi(N) = (3-1)*(5-1) = 8 lambda(N) = lcm(3-1, 5-1) = 4 -- poncho -- From: Hideo Shimizu <[EMAIL PROTECTED]> Subject: Re: Camellia, a competitor of AES ? Date: Tue, 12 Sep 2000 15:49:12 +0900 [EMAIL PROTECTED] wrote: > > Hideo Shimizu <[EMAIL PROTECTED]> wrote: > > 1) ISO entry > > Now, ISO standarize some cryptographic algorithms (block cipher, stream > > cipher, public-key cipher). Japanese national body will entry this project. > > Camellia is one of the five block ciphers. > > The ISO has "registered" block ciphers for a while, choosing not to > standardise any of them. For example, B-CRYPT, IDEA, and LUC are all > "ISO/IEC 9979 Registered" but none are a standard. Since there are > absolutely no requirments for registration, execept for it being > submitted by a national body, I'm not really sure I see the point. Yes. But, new project for deciding standard is now progressing. > > Personally, I think the ISO should probably follow NIST and declare > the AES winner a standard. I hear that U.S. National body entry AES final winner to ISO's new algorithm standard. -- Subject: Re: Getting Started, advice needed (FAQs , yes I read them) From: [EMAIL PROTECTED] (Andy C) Date: Tue, 12 Sep 2000 06:57:47 GMT On 11 Sep 2000, [EMAIL PROTECTED] (Douglas A. Gwyn) spake in
Cryptography-Digest Digest #660
Cryptography-Digest Digest #660, Volume #11 Sat, 29 Apr 00 10:13:01 EDT Contents: Re: Karatsuba threshold ("Michael Scott") Re: sboxes for the bored... (Tom St Denis) Re: sboxes for the bored... (Tom St Denis) Re: New and want to learn (Tom St Denis) Re: The Illusion of Security (Tom St Denis) Re: Help In encryption!!! (Tom St Denis) As long as we are asking naive questions... (Guy Macon) Re: Speaking of HD Overwriting... (Guy Macon) Transparent encryption for Windows CE ("Roman - do not replay") Re: Speaking of HD Overwriting... (Mark Wooding) Sbox Generator Update (Tom St Denis) Re: OAP-L3: Semester 1 / Class #1 All are invited. (Anthony Stephen Szopa) Vs: Vs: sci.crypt think will be AES? ("Helger Lipmaa") Modification of RC5 (Tom St Denis) From: "Michael Scott" <[EMAIL PROTECTED]> Subject: Re: Karatsuba threshold Date: Sat, 29 Apr 2000 11:17:55 +0100 The threshold depends crucially on the speed of the multiplication instruction on the host architecture (which is really to state the obvious). If there is no integer multiplication instruction then even 2x2 word multiplications may benefit. The same may apply if the multiplication instruction requires multiple cycles to complete. For this reason it is really quite pointless to build-in a fixed threhold - its architecture dependant. For (an extreme) example GF(2) "multiplication" (carry-free multiplication - in GF(2) add and subtract are both XOR) is not supported by any instruction set I know of. Therefore it must be implemented by a shift-and-xor program. On a Pentium Pro my best effort for a 32x32 GF(2) multiplication requires 144 instructions. Of course the regular integer MUL instruction requires just 1 clock cycle. So in this scenario the Karatsuba thresold is right down at the 2x2 level - helped by the fact that you don't have to keep track of those pesky carries... Mike Scott -- From: Tom St Denis <[EMAIL PROTECTED]> Subject: Re: sboxes for the bored... Date: Sat, 29 Apr 2000 10:29:05 GMT Terry Ritter wrote: > > On Sat, 29 Apr 2000 00:05:55 GMT, in <[EMAIL PROTECTED]>, in > sci.crypt "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote: > > >Terry Ritter wrote: > >> Measuring Boolean function nonlinearity is well-known technology. > > > >However, there are apparently different measures of nonlinearity; > > Yes, of course there would be different measures, in the same sense as > there are many different forms of linearity. > > >are they strictly equivalent? > > Within the context of Boolean functions (that is, n-bit to 1-bit > lookup tables), such functions are likely equivalent. The extension > to n-bit to m-bit tables, in which we measure each bit-column > independently, seems fairly common, if that is what we want to do. > Now, we might well *want* to do something else in which the sequences > are not measured independently, but I'm unaware of a useful > cryptographic measure for anything like that. Well meseasuring n by 1 sbox non-linearnity is not what I am trying todo here. I implemented a WT transform that goes thru all possible inputs and outputs. Could you just look at my code to see I implemented the WT properly please? Tom -- Want your academic website listed on a free websearch engine? Then please check out http://24.42.86.123/search.html, it's entirely free and there are no advertisements. -- From: Tom St Denis <[EMAIL PROTECTED]> Subject: Re: sboxes for the bored... Date: Sat, 29 Apr 2000 10:31:32 GMT Terry Ritter wrote: > > On Sat, 29 Apr 2000 01:24:40 GMT, in <[EMAIL PROTECTED]>, > in sci.crypt Tom St Denis <[EMAIL PROTECTED]> wrote: > > >"Douglas A. Gwyn" wrote: > >> > >> Terry Ritter wrote: > >> > Measuring Boolean function nonlinearity is well-known technology. > >> > >> However, there are apparently different measures of nonlinearity; > >> are they strictly equivalent? E.g., do all comparable bent > >> functions have the same "Ritter nonlinearity", and is that > >> necessarily maximal? > > > >I dunno what he is talking about the walsh transform (taken from "On > >linear cryptanalysis") will give you a negative when the function is > >affine, a positive when it's linear and close to zero if it's neither. > > Is that true? I don't think so. Let's see you deliver a few examples > where that is so. Look at the paper, there are negative entries in the WT table of SBOX 5. > In any case, Boolean function nonlinearity is defined as a distance, > not a direction. Understa
Cryptography-Digest Digest #660
Cryptography-Digest Digest #660, Volume #10 Wed, 1 Dec 99 20:13:01 EST Contents: Question about CFB mode (Eric Lee Green) Re: Encrypting short blocks (Eric Lee Green) Re: VIC cipher strength? ("r.e.s.") Re: more about the random number generator (Eric Lee Green) Re: Simpson's Paradox and Quantum Entanglement ("karl malbrain") Re: Decyption proof cellphones in Europe? [x3] (Ian Goldberg) Re: High Speed (1GBit/s) 3DES Processor (David Kessner) Re: more about the random number generator (Scott Nelson) Re: Elliptic Curve Public-Key Cryptography (Paul Rubin) Re: Simpson's Paradox and Quantum Entanglement (Jim Carr) Re: Elliptic Curve Cryptography (Mike Rodriquez) Re: Encrypting short blocks (SCOTT19U.ZIP_GUY) Re: more about the random number generator (CLSV) One Round Block Cipher and 8-bit block Cipoher (Seongtaek Chee) newbie question (Kyle Hayes) One round or 8-bit block cipher (Seongtaek Chee) Re: The $10,000.00 contesta (Bruce Schneier) Re: NSA should do a cryptoanalysis of AES (Bruce Schneier) Re: Decyption proof cellphones in Europe? [x3] (Bruce Schneier) Fast Software Encryption 2000 - Call for Papers/Participation (Bruce Schneier) From: Eric Lee Green <[EMAIL PROTECTED]> Subject: Question about CFB mode Date: Wed, 01 Dec 1999 13:18:54 -0700 I'm implementing CFB mode using the description in Bruce Schneir's "Applied Cryptography" (page 200, 2nd edition), and have a question. He mentions a "left-most byte". Little Endian vs. Big Endian? I am assuming that if I have a "unsigned char cryptbuf[16]" that holds my encrypted counter value, he is referring to cryptbuf[0]? Also, he describes shifting the resulting encrypted byte (from xor'ing the input byte with that 'left-most byte' into a shift register (16 bytes long, if we're using one of the AES candidates). If my shift register is declared the same as 'cryptbuf' above, do I "shift left" (i.e., move sr[1] to sr[0], sr[2] to sr[1], etc., and the new crypto-char goes into sr[15]) or do I "shift right" (the new crypto-char goes into sr[0])? I know, I know, it doesn't really matter as long as both ends do it the same way, but I want to get a WEE bit of interoperability with other implementations of CFB mode, especially since I might use a "stock" cryptographic toolkit on platforms other than Linux (even though it's so much more fun rolling your own!). (For those browsing the group looking for an education -- CFB mode is a method of emulating a stream cipher using a block cipher. Start with a block-sized unique initial value. Encrypt it with the key. Use the 'left most byte' of the encrypted value to XOR with the byte of data you're wanting to encrypt. Then shift the resulting encrypted byte into the shift register, as well as return it as the value of the encryption). -- Eric Lee Green [EMAIL PROTECTED] Software Engineer Visit our Web page: Enhanced Software Technologies, Inc. http://www.estinc.com/ (602) 470-1115 voice (602) 470-1116 fax -- From: Eric Lee Green <[EMAIL PROTECTED]> Subject: Re: Encrypting short blocks Date: Wed, 01 Dec 1999 13:23:58 -0700 Markus Peuhkuri wrote: > > Is there an encyprion algorithm that can be used for short > blocks (variable from ~10 to 24 bits) _and_ the result is same > length as original data. The key may be much larger (128, 256, > ...). Any stream cipher, or a block cipher in CFB or OFB/Counter mode. I.e., almost all encryption algorithms. Note you'll need to use the left-most BIT in CFB mode if you're wanting to do bitstream encryption... Well, they do require you to first "chat" a unique salt value across the 'net or whatever you're using as your transmission medium, but that doesn't make the result any larger than the original message. Pick up any good book on encryption to see what CFB means... -- Eric Lee Green [EMAIL PROTECTED] Software Engineer Visit our Web page: Enhanced Software Technologies, Inc. http://www.estinc.com/ (602) 470-1115 voice (602) 470-1116 fax -- From: "r.e.s." <[EMAIL PROTECTED]> Subject: Re: VIC cipher strength? Date: Wed, 1 Dec 1999 12:28:27 -0800 "UBCHI2" <[EMAIL PROTECTED]> wrote ... : Looking at the VIC Cipher, it appears that many of the steps : leading up to the straddling checkerboard are quite unecessary. : Why not just start with a predeterminded straddling checkerboard : and then perform the rest of the encipherment. The critical 10 digits serve to generate a "key sequence&
Cryptography-Digest Digest #660
Cryptography-Digest Digest #660, Volume #9Fri, 4 Jun 99 20:13:02 EDT Contents: Re: The BRUCE SCHNEIER Tirade (wtshaw) Re: random numbers in ml ([EMAIL PROTECTED]) Re: what cipher? (better description) ("Particle") Re: Another source of random numbers (STL137) Re: what cipher? (wtshaw) Re: Challenge to SCOTT19U.ZIP_GUY (Tim Redburn) From: [EMAIL PROTECTED] (wtshaw) Crossposted-To: talk.politics.crypto,alt.privacy Subject: Re: The BRUCE SCHNEIER Tirade Date: Fri, 04 Jun 1999 15:43:01 -0600 In article <7j8j0e$2hb0$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote: > In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Tim Redburn) wrote: > > I ok I guess I have to spoon feed you to show you how you can get > exactly 128 bits of security since the concept is above you, > To get exactlt 128 buts of secruity you would need to be able to type > in 16 charaters each of which has 256 combinations. This is not feasible > since cetain patterns not allowed or could abort the program. So here > is a way you could do it. Let the pass phrase be made of octal characters > "0,1,2,3,4,5,6,7" then take your 128 bits of key you > need and rewrite is in hex this makes it 128/3 which equals 43 octal > characters. Type in these for the password. SInce you get a unique > S-table for each octal combination you have your 128bit key that could > be used but becareful all 7's is to big and make sure you use exactly > 43 octal characters to represent the binary key of your choice. I think that my octal hash method is as workable here as any, allowing for 3 bits per character, and working from alphabetic characters, only one case needed. I make a list of seeds from the results, but they need not be used that way at all. You need a base string from which to work. The easiest to start with is the normal alphabet, but any deranged alphabet would likely make the hash give entirely different results. Get the number of characters you have, and convert each character to a digit 0-7 as you encounter it, beginning in normal sequence with each A. If you reach 7, then reset for 0 for the next assignment, and go to the next letter in your base sequence if you hit the end of the string. What you get is a line of 3 bit values the same as your string length. If you need a shorter sequence, trim the overage. FOR INSTANCE,THIS IMPLEMENTATION REQUIRES ONE HUNDRED CHARACTERS IN ORDER TO FUNCTION CORRECTLY.HERE ARE THE RESULTS: Offhand, I don't remember which base sequence I used, but any will do, with any set of characters; you might want to include punctuation. Bold face is returned from the routine to confirm the use of the string which can be up to 250 characters. 300 bits are harvested by this Octal Hash, represented in 20 15-bit values, which can easily be converted to any binary form. You could just as well do a count of 16 rather than 8 to get another variation. OCTAL NUMBERS: 40551 02471 46450 23636 25770 26074 13761 10572 40243 11152 04325 21126 05253 66433 46451 46527 72750 70656 71363 33071 > Note the part that may be confusing you. In order to get some speed > I make the table not from a binarry number but from a list of remainders > for speed. You have pointed out and that since I do a mod on each random > number with a decreasing base that certain remainders are more favored > than others. on other words for those that have no looked at the entropy > if I have a random number in range 0 to 7 and need a number 0 to 2 I > could divide by 3 and get a remainder of 0 to 2 but then there is more > chance of the remainders 0 to 1 occuring then the remainder 2 since > 0 resultes from 0,3,6 while 1 restults from 1,4,7 while 2 results > form 2,5 so it is less likely. > However when the tables is built from the short key you no longer have > random input and since the string is repeated over and over you keep > dividing the same numbers by a decreasing base as you build the table. > since each number is repreated many times but a dieffernt divsor is used > I don't think there is a problem of 2 octal sequences as described > above producing the same sequences. IF there is then I am wrong and > maybe you can show me the error. > > > > >> -- Weathermen prosphesize and insurance companies predict, while both pretend to be doing the other to get an audience. -- From: [EMAIL PROTECTED] Crossposted-To: comp.sys.cbm,comp.sys.apple2.programmer Subject: Re: random numbers in ml Date: 4 Jun 1999 22:38:06 GMT Reply-To: [EMAIL PROTECTED] (Matthew Montchalin) Jeffrey Coffin wrote: >> When you're trying to express an algorithm, C has the distinct >> advantage of being understandable to a wide variety of programmers.