We assume that Triple-DES is stronger than plain DES because DES is not a group. So what does that mean?
Subject: Re: What is "group" means in block cipher ? Date: 15 Dec 1998 09:26:46 -0500 From: juola@mathcs.duq.edu (Patrick Juola) Message-ID: <755rj6$497$1@quine.mathcs.duq.edu> References: <36766E0C.F0BF70B2@sec-cse.sch.ac.kr> Newsgroups: sci.crypt Lines: 22 In article <36766E0C.F0BF70B2@sec-cse.sch.ac.kr>, Seung-Chul, Chae <chae@sec-cse.sch.ac.kr> wrote: >Someone said, DES encryption generates a semigroup and other encryption >generates a group. >What is "group" means ? it is a set of block ? A group is a mathematical abstraction; the relevant property here is that a group is "closed" under a particular operation. Which is to say, if you do the operation once (with one parameter) and then do the operation again (with another parameter), there's some third parameter that could do it in one step. Just as an example, the set of whole numbers is closed under addition. If I add three to a number X (getting X + 3), and then add five to the result, that's exactly the same as if I had added eight directly to the original number. So the operation pair (adding five, adding three) is exactly the same as the operation (adding eight). -kitten
Subject: Re: What is "group" means in block cipher ? Date: 15 Dec 1998 16:51:13 GMT From: aph@cygnus.remove.co.uk (Andrew Haley) Message-ID: <756421$aet$1@korai.cygnus.co.uk> References: <36766E0C.F0BF70B2@sec-cse.sch.ac.kr> Newsgroups: sci.crypt Lines: 24 Seung-Chul, Chae (chae@sec-cse.sch.ac.kr) wrote: : Someone said, DES encryption generates a semigroup and other encryption : generates a group. : What is "group" means ? it is a set of block ? A group (G, *) is a set G with a binary operator * with the following properties: Associativity: a * (b * c) = (a * b) * c There is an identity element I: a * I = I * a, for all a elem G. For each a elem G there exists an inverse a ^ (-1) elem G, a * (a^(-1)) = (a^(-1)) * a = 1 DES is not a group; that is the operation DES on a block does not have these properties. You ought to get a book on the mathematics behind cryptography before proceeding any further. Andrew.
Subject: Re: What is "group" means in block cipher ? Date: Tue, 15 Dec 1998 17:16:54 GMT From: jsavard@tenMAPSONeerf.edmonton.ab.ca (John Savard) Message-ID: <367698cd.875397@news.prosurfr.com> References: <36766E0C.F0BF70B2@sec-cse.sch.ac.kr> Newsgroups: sci.crypt Lines: 21 "Seung-Chul, Chae" <chae@sec-cse.sch.ac.kr> wrote, in part: >Someone said, DES encryption generates a semigroup and other encryption >generates a group. >What is "group" means ? it is a set of block ? If DES encryption _were_ a group - the term is taken from algebra - which it is not, then for any two keys x, y, there would exist a key z such that encrypting any and all plaintext blocks, first with key x, then with key y, exactly the same result could be obtained by just encrypting once with key z. If that were true, then double-DES, or triple-DES, or quintuple-DES, would just be regular DES in disguise. Even though one would not know what the key is that is equivalent, for someone not knowing the key, it would be no harder to crack. John Savard http://www.freenet.edmonton.ab.ca/~jsavard/index.html
Subject: Re: What is "group" means in block cipher ? Date: Tue, 15 Dec 1998 11:45:42 -0800 From: Bryan Olson <first.last@xuptronicsx.com> Message-ID: <3676BC66.C851EE5C@xuptronicsx.com> References: <36766E0C.F0BF70B2@sec-cse.sch.ac.kr> Newsgroups: sci.crypt Lines: 28 "Seung-Chul, Chae" wrote: > Someone said, DES encryption generates a semigroup and other encryption > generates a group. > What is "group" means ? it is a set of block ? I'm not really up on semigroups, but I understand that given a finite set of elements, they're the same thing as groups. DES, like all block ciphers, generates a group. The elements of the group are one-to-one functions from 64 bit blocks to 64 bit blocks (equivalently, permutations of the set of 64 bit blocks). Specifically, any permutation that can be generated as a composition of DES encryptions (possibly with different keys) is in the set. The group operation is function composition. The pure Feistel structure of DES generates only even permutations, so the group generated by DES is a subgroup of the alternating group (which has half the elements of the symmetric group). If DES is any good at simulating random even permutations, it should generate the alternating group. A couple other posts answered the question of whether DES _is_ a group, which is not the same as the one you asked about generating a group. A block cipher is a group iff each of the permutations in the group it generates is equivalent to some single encryption. --Bryan
Subject: Re: What is "group" means in block cipher ? Date: Tue, 15 Dec 1998 23:06:04 GMT From: keaak@tgr.arg Message-ID: <756q2r$sht$1@news-2.news.gte.net> References: <3676BC66.C851EE5C@xuptronicsx.com> Newsgroups: sci.crypt Lines: 37 On Tue, 15 Dec 1998 11:45:42 -0800, Bryan Olson <first.last@xuptronicsx.com> wrote: > >"Seung-Chul, Chae" wrote: >> Someone said, DES encryption generates a semigroup and other encryption >> generates a group. >> What is "group" means ? it is a set of block ? >I'm not really up on semigroups, but I understand that given a >finite set of elements, they're the same thing as groups. No, they're not the same thing. A semigroup is a set S together with an associative binary operation, t : SxS---->S. Nothing is said of the existence of inverses, nor of an identity element under t (Although the latter is included in the definition in some texts). A trivial example: Let S={1,s} and define a 'multiplication' in the obvious way except define s^2=s. This defines a semigroup, and it's finite. To see it's not a group, try to find the inverse of s under this multiplication. Someone already defined a 'group' in this thread. Mike Decrypt keaak@tgr.arg with ROT13 for email address. NOTICE TO BULK EMAILERS: Pursuant to US Code, Title 47, Chapter 5, Subchapter II, 227, any and all nonsolicited commercial E-mail sent to this address is subject to a download and archival fee in the amount of $500 US. E-mailing denotes acceptance of these terms.
Subject: Re: What is "group" means in block cipher ? Date: 16 Dec 1998 02:02:48 GMT From: John Pliam <pliam@ima.umn.edu> Message-ID: <36771FC8.524C073F@ima.umn.edu> References: <7571kk$lun$1@nntp1.uunet.ca> <756q2r$sht$1@news-2.news.gte.net> Newsgroups: sci.crypt Lines: 61 jme@mycpu.org wrote: > any pointer on a paper about that ? i know there is one paper about > the proof that des is not a group, but i dont remember the title. See refs below. Bryan Olson <first.last@xuptronicsx.com> wrote: > "Seung-Chul, Chae" wrote: > > Someone said, DES encryption generates a semigroup and > > other encryption generates a group. What is "group" means ? > > it is a set of block ? > > I'm not really up on semigroups, but I understand that given a > finite set of elements, they're the same thing as groups. There are finite semigroups which are not groups. (An important family of examples comes from finite automata whose state transition diagrams are not a Cayley graphs. The *syntactic monoid* of such an automaton is the semigroup of partial functions induced on the state space by words in the regular expression. This semigroup is not a group.) However, there are no sub-semigroups of a finite group. Thus the requirement of decryption means that no block cipher can generate a semigroup (which is not itself a group). > If DES is any good at simulating random even permutations, it > should generate the alternating group. Wernsdorf [1] showed that, in fact, the one-round functions of DES generates the full alternating group. It can be inferred that the 16-round functions do as well. > A couple other posts answered the question of whether DES _is_ a > group, which is not the same as the one you asked about generating > a group. A block cipher is a group iff each of the permutations > in the group it generates is equivalent to some single encryption. Yeah, I think things are sufficiently confusing and the results are sufficiently spread out that a summary could be useful to the beginner: o No block cipher can generate true semigroup. o No block cipher can ``be'' a true semigroup. o Any block cipher generates a subgroup of the symmetric group S_(2^n). o Any Feistel cipher generates a subgroup of A_(2^n). [2] o DES ``is'' not a group. [3] o DES generates the full alternating group, A_(2^n). [1] John Pliam pliam@ima.umn.edu http://www.ima.umn.edu/~pliam refs: [1] R. Wernsdorf, "The One-Round Functions of DES Generate the Alternating Group", EUROCRYPT '92, pp. 99-112, 1993. [2] S. Even & O. Goldreich, "DES-Like Functions can Generate the Alternating Group, IEEE inf. theo., IT-29:6, pp. 863-865, 1983. [3] K.W. Campbell and M.J. Wiener, "DES is not a Group", CRYPTO '92", pp. 512-517, 1992.
Subject: Re: What is "group" means in block cipher ? Date: Sat, 26 Dec 1998 09:04:19 -0100 From: fungus <spam@egg.chips.and.spam.com> Message-ID: <3684B4A3.1A92ABE1@egg.chips.and.spam.com> References: <36766E0C.F0BF70B2@sec-cse.sch.ac.kr> Newsgroups: sci.crypt Lines: 21 Seung-Chul, Chae wrote: > > Someone said, DES encryption generates a semigroup and other > encryption generates a group. > What is "group" means ? it is a set of block ? Imagine you encrypt some data twice with seperate keys K1 and K2 If there exists a single key K3 which can decrypt the data then the encipherment is a group. In DES this is not possible. You may find one key which will decrypt one block of data, but it would be luck. You probably won't even be able to decrypt other blocks of the same message. -- <\___/> / O O \ \_____/ FTB.
Terry Ritter, his current address, and his top page.
Last updated: 1999-02-20