Cryptography-Digest Digest #522, Volume #14 Tue, 5 Jun 01 09:13:01 EDT
Contents:
Re: about DH parameters & germain primes ("Tom St Denis")
Re: Def'n of bijection ("Tom St Denis")
Re: BBS implementation ("Tom St Denis")
Sophie Germaine Benefits for DH ("Tom St Denis")
Re: PRP vs PRF (was Luby-Rackoff Theorems) ("Tom St Denis")
Some questions on GSM and 3G (Arturo)
Re: 2,2-multipermutation? ("Tom St Denis")
Re: 2,2-multipermutation? ("Tom St Denis")
Re: about DH parameters & germain primes (Mark Wooding)
PRP => PRF (TRUNCATE) ("Tom St Denis")
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
Re: WEB PAGES (SCOTT19U.ZIP_GUY)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
White-Hat Security Arsenal http://white-hat.org/ (New book) (Avi Rubin)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
Re: Def'n of bijection (Tim Tyler)
Re: Def'n of bijection (Tim Tyler)
Re: RSA's new Factoring Challenges: $200,000 prize. (my be repeat) (Bob Silverman)
Re: Sophie Germaine Benefits for DH (Mark Wooding)
----------------------------------------------------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: about DH parameters & germain primes
Date: Tue, 05 Jun 2001 08:47:39 GMT
"Mark Wooding" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> quequ <[EMAIL PROTECTED]> wrote:
>
> > "If p, (p-1)/2 both prime, then you can just use any
> > g you please [other than 0, 1, and -1], and you'll
> > get a very large order [at least (p-1)/2]"
> >
> > It's right?
>
> Yes, it's right.
>
> > I've tried a 1024bit germain prime P and the generator G set to (P-1)/2.
> > Are these good parameters?
>
> (P - 1)/2 is a bit big. This won't affect security, but it can affect
> performance in some cases. In your case, I'd choose G = 4, which
> definitely has order (P - 1)/2. At least this way you know exactly what
> you're getting.
>
> On the other hand, I don't really believe in Sophie-Germain primes.
> They take too long to generate, and I don't see any practical advantage
> over Lim-Lee primes.
Something that bugs me.... When you do (g^x)^y mod p, is g^x consider a new
base wrt to the group the entire operation generates or is it simply g^xy
mod p.
Like if p=257, g=45, x=17,y=33 we get (g^x) mod p equal to 103, (103^33) mod
257 equal to 167
In the second step is 103 considered a new base? I'm thinking of an example
where (g^x mod p) results in a base that generates a small group, for effect
suppose g^x mod p = -1. Then -1^y mod p will be 1 or -1 depending on the
lsb right?
Well with a SG prime this cannot happen (well the -1 and 1 can occur). All
bases will generate a huge group.
That's one possible benefit?
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Date: Tue, 05 Jun 2001 08:49:33 GMT
"JPeschel" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Tom St Denis" [EMAIL PROTECTED] writes, in part:
>
> >If you're a regular you should know to read what I say with a grain of
salt.
> >I.e be cautious because I tend to make mistakes. Espescially with math
> >notation I haven't formally learnt yet.
>
> Reviewing, from time to time, the first few chapters from Menezes's book
> might be a good way to reinforce the notation. Beats being corrected.
Good tip. Menezes's book is? HAC?
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: BBS implementation
Date: Tue, 05 Jun 2001 08:50:48 GMT
"Mark Wooding" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
>
> > How do I know it is not on a short or degenerate cycle?
>
> Because if it is, you've managed to factor the modulus.
As I understand it, if you know the length of the cycle you only know
factors of (p-1)(q-1) right?
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Sophie Germaine Benefits for DH
Date: Tue, 05 Jun 2001 09:35:20 GMT
A question was raised whether Lim-Lee primes were better in terms of ease of
generation and securtity versus a Sophie Germaine Prime.
So we get our terminology all straight a Lim-Lee (LL) prime is one where it
has several huge prime factors, a Sophie-Germaine (SG) prime is a prime of
the form 2p + 1 where p itself is prime.
As a contrived example I chose p=257, g=45. This isn't a LL or SG but shows
off the point I started on earlier.
Suppose we have one key x=66, the resulting base 45^66 mod 257 = 239 will
only generate a group of 128 elements.
While this is a contrived example a similar effect is possible with LL and
SG primes. In an LL prime for example you may have three 256-bit primes to
form a 768-bit prime, whereas in SG you will have one 767-bit prime (times 2
plus 1).
This means in LL it is possible to find a base that generates all units (in
the multiplicative group modulo the prime) but when trying to make a DH
shared key your public key will only generate a group on the order of 2^256.
It is rather trivial to verify which group your public key will generate.
Since g^xy mod p is normally not given out I can't see this as being a DLP
wrt to the group size.
Whereas in SG your public key will generate a group of size p or 2*p (unless
your public key is 1 or -1) where p is a large 767 (in this case) bit prime.
The chances of finding a bad LL public key (i.e where it generates a small
by comparison) sub-group is low why not use a SG prime?
SG primes take forever to make, but once you make one you're done. DH is
just as fast with LL or SG primes.
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: PRP vs PRF (was Luby-Rackoff Theorems)
Date: Tue, 05 Jun 2001 09:56:22 GMT
"Gregory G Rose" <[EMAIL PROTECTED]> wrote in message
news:9fete7$[EMAIL PROTECTED]...
> In article <_WAS6.21053$[EMAIL PROTECTED]>,
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> >Oh yeah that makes sense. So not all PRFs are invertable (i.e
one-to-one)
> >right?
> >
> >Sorry if these questions seem lame. They don't teach this much group
theory
> >(or whatever this is) in school...
>
> I find it easiest to thing of a PRF as an
> "idealised" hash function, and a PRP as an
> "idealised" block cipher. (For some unspecified
> meaning of "idealised".)
Yeah this makes sense. I was hung up on the notion that a PRF had to be
invertable (which it doesn't).
Tom
------------------------------
From: Arturo <aquiranNO$[EMAIL PROTECTED]>
Crossposted-To: alt.privacy
Subject: Some questions on GSM and 3G
Date: Tue, 05 Jun 2001 10:39:38 +0200
I´m doing a conference on GSM and 3G security protocols, and I´ve got a
couple pending questions, so I´d like to ask if anybody could help me with more
information, so I don´t have to write "it´s rumored that...":
- It seems like the GSM consortium is updating its algorithms: COMP128-2
(to replace COMP128) and A5/3 (a stronger version than A5/1). Anybody got
confirmation?
- I´ve heard that in a famous criminal case, the suspect´s phone was
forced to use no encryption by use of an IMSI catcher (basically, impersonating
a base station). Was it OJ Simpson?
- I´m trying to find papers on cryptanalysis and strength of Kasumi, the
cipher algorithm to be used for encryption and authentication in 3G phones.
- I´ve heard on an algorithm called BEANO, supposedly to be used for
encrypting calls outside the phone-to-base-station leg. Heard anything?
TIA.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: 2,2-multipermutation?
Date: Tue, 05 Jun 2001 10:03:18 GMT
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Tom St Denis wrote:
> >
> > Does the following pseudocode define a 2,1 Multipermutation?
> [snip]
>
> Would you please give a reference where the term
> 'multipermutation' occurs or is defined?
Sure, um Vaudenay has a paper on the subject. Just goto LASEC and look it
up :-)
Generally a multi-permutation means all the components of a an output vector
are a permutation of the components of an input vector.
For example, a 2,2-multipermutation means if you fix on input both outputs
will rotate through all values as you cycle the unfixed input. This has the
property that if only one input differs (say in a differential attack) both
outputs will differ.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: 2,2-multipermutation?
Date: Tue, 05 Jun 2001 10:03:51 GMT
"Niels Ferguson" <[EMAIL PROTECTED]> wrote in message
news:9esd1s$s4k$[EMAIL PROTECTED]...
>
> "Tom St Denis" <[EMAIL PROTECTED]> wrote in message
> news:GpfQ6.58257$[EMAIL PROTECTED]...
> > To get away from politics for a bit...
> >
> > Does the following pseudocode define a 2,1 Multipermutation? (a,b)
forms
> > the input
> >
> > 1. a = a xor b
> > 2. a = S[a]
> > 3. b = b xor a
> > 4. b = S[b]
> >
> > Where S is some bijection. assume for no entries in S does S[a xor b]
xor
> b
> > equal zero (i.e not linear enough).
>
> This restriction on S does not make much sense. Wlog, suppose S[p] = q.
> Then we can choose b:=q and a:= p xor q, and we have S[ a xor b ] xor b =
0.
> In other words, S[a xor b] = b will always happen for some pairs (a,b).
>
> Your function is not a multipermutation. Look at the 'b' output, which is
> defined by
> Fb( a, b ) = S[ b xor S[ a xor b ] ]
> The final S does not change the permuation property, so we can look at
> Fb'( a, b ) = b xor S[ a xor b ]
>
> In general this will not be a permutation. It would be if you construct S
> such
> that the differentials of the form x -> x all have probability zero.
Ah thanks for the head up. I think Serge proposed a better style function
than my original
Tom
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: about DH parameters & germain primes
Date: 5 Jun 2001 10:09:53 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
[Lots of irrelevant quoted stuff snipped.]
> Well with a SG prime this cannot happen (well the -1 and 1 can occur). All
> bases will generate a huge group.
But the same is true with a Lim-Lee prime. The only possible element
orders are 2 or some multiple of at least one of the q_i, which we
already know is large enough (by hypothesis).
-- [mdw]
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: PRP => PRF (TRUNCATE)
Date: Tue, 05 Jun 2001 10:36:37 GMT
Reading the paper David pointed to a bit ago I see they have one way to go
from PRP to PRF by truncating bits of the output.
Obviously there will be alot of PRPs that make the same PRF. Wouldn't a
better method of truncating be reducing modulo a prime?
I.e if you want a four bit PRF you do (PRP mod 17) mod 16 = PRF. That way
the higher order bits will affect the output. Did I misunderstand the
original intent?
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Tue, 5 Jun 2001 11:55:42 GMT
David Hopwood <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Tom St Denis <[EMAIL PROTECTED]> wrote:
:> : CTR mode is just a bloody xor of some random bits against a
:> : message. How can that possibly be less secure than BICOM?
:>
:> To repeat David Scott's example, consider a 1 byte cyphertext message.
:>
:> In CTR mode it maps to one of 256 possible plaintexts.
:>
:> With BICOM it maps to one of *billions* of possible messages.
:>
:> You tell me which is more likely to be secure.
: The only way BICOM (with a 128-bit block cipher) can produce a 1 byte
: ciphertext with probability greater than 2^-120, is if you decrypt a
: 1 byte ciphertext and call the resulting junk the plaintext.
: IOW, David Scott's example is of no practical relevance.
It certainly indicates that use of counter mode leaks information
about the plaintext in large quantities when the message is small.
Is that "of no practical relevance"?
: If you want to disguise the plaintext length (in CTR mode or in any
: other secure mode), that is quite easy, and does not require "bijective"
: encryption in the sense meant by Scott; it simply requires padding
: the original plaintext.
That's a possibility - but it's not what us normally done when using a
cypher in counter mode.
If someone wants to propose a modification for the purpose of making a
fairer comparison with BICOM, then they should specify what system they
are talking about.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Tue, 5 Jun 2001 12:00:41 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: "Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
:> Tom St Denis <[EMAIL PROTECTED]> wrote:
:> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
:> :> Knowledge that a message comes from a set of billions of possible key
:> :> selected messages, rather than a set of 256 possible key selected
:> :> messages *is* a feature that has an immediate impact on security.
:> :>
:> :> If you can narrow the plaintext down to one of 256 possibilities, then
:> :> that is already a significant leak of information about the message
:> :> contents.
:>
:> : OTP encrypted message.
:>
:> : C=1101111010001
:>
:> : What is P?
:>
:> : (How long must this go on?)
:>
:> I don't know:
:>
:> Maybe until you realise that an OTP doesn't have perfect secrecy if it's
:> dealing with finite files, and converting them to cyphertexts of the same
:> length as the plaintexts?
: SO WHAT?
: What is your problem?
: All OTP's are named OTP, ah a flaw!
: That's about as valid as your logic. Tell me what P was in the system above
: and we can talk.
I can't say what P was *exactly* - but I can narrow it down to one of only
256 possibilities.
In a system with a 128 bit key, being able to narrow the message down
from one of 2^128 possibilities to one of 2^8 possibilities surely
represents a gigantic loss of security, no?
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: comp.compression
Subject: Re: WEB PAGES
Date: 5 Jun 2001 12:09:26 GMT
[EMAIL PROTECTED] (those who know me have no need of my name)
wrote in <[EMAIL PROTECTED]>:
><[EMAIL PROTECTED]> divulged:
>
>>I have been having a terible time even accessing my site
>>at http://members.nbci.com/ecil/index.htm
>
>seems to work, at least right now.
>
Yes just as I was ready to give up it is partially
working.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Tue, 5 Jun 2001 12:12:33 GMT
Paul Pires <[EMAIL PROTECTED]> wrote:
: Tim Tyler <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
:> Tom St Denis <[EMAIL PROTECTED]> wrote:
:> : (How long must this go on?)
:>
:> I don't know:
:>
:> Maybe until you realise that an OTP doesn't have perfect secrecy if it's
:> dealing with finite files, and converting them to cyphertexts of the same
:> length as the plaintexts?
: Ehrr? Why not? [...]
See the definition of "perfect secrecy" - e.g.:
http://www.io.com/~ritter/GLOSSARY.HTM#PerfectSecrecy
``The unbreakable strength delivered by a cipher in which all possible
ciphertexts may be key-selected with equal probability given any
possible plaintext. This means that no ciphertext can imply any
particular plaintext any more than any other. This sort of cipher needs
as much keying information as there is message information to be
protected. A cipher with perfect secrecy has at least as many keys as
messages, and may be seen as a (huge) Latin square.''
: It seems to me that that a Ct could be from any possible Plaintext of
: exactly the same size.
That's perfectly correct.
: Are you saying that just leaking the size is a lapse in perfect secrecy?
Yes. It is - unless your system is a bizarre one which can only transmit
one byte messages.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Tue, 5 Jun 2001 12:19:09 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: "Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
:> Tom St Denis <[EMAIL PROTECTED]> wrote:
:> : Why do you think that's a problem? If you can't tell a byte from random
:> : it's provably secure. I.e if the prob of the output is exactly 1/256
:> : what advantage do you have?
:>
:> This is provable *insecurity* - not provable security.
:>
:> Ideally for security, the cyphertext should contain no information
:> that suggests any plaintext is more likely than any other (Shannon's
:> perfect secrecy).
: yes I agree. If you have 256 states that's a prob of 1/256. [...]
Since when is CTR mode restricted to only transmitting 256 possible
messages?
CTR mode can transmit messages of any length.
You can't just make up a totally useless system with no practical
application half way through the discussion and pretend you were
talking about that all along.
If you compare a variant of CTR mode that can only transmit 256
possible messages with BICOM then there really is no contest.
:> Here we a have a case where the cyphertext eliminates every possible
:> plaintext *except* for 256. This is a *tiny* figure - and
:> may well represent a massive gain in information on the part
:> of the attacker upon observation of the cyphertext.
: Not really. [...]
Really. Think about it.
--
__________ http://rockz.co.uk/ http://alife.co.uk/ http://hex.org.uk/
|im |yler http://atoms.org.uk/ http://mandala.co.uk/ [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Avi Rubin)
Subject: White-Hat Security Arsenal http://white-hat.org/ (New book)
Date: Tue, 5 Jun 2001 12:20:31 GMT
My new book,
White-Hat Security Arsenal: Tackling the Threats
- with a foreword by Bill Cheswick
Paperback - 384 pages (June, 2001)
Addison-Wesley ISBN: 0-201-71114-1
hit the printing presses this past week, and is now available
for online ordering. It should hit the retail stores in the
next couple of weeks.
See http://white-hat.org/ for detailed information.
Amazon page:
http://www.amazon.com/exec/obidos/ASIN/0201711141
Addison Wesley page:
http://cseng.aw.com/book/0,3828,0201711141,00.html
Avi Rubin
--
http://avirubin.com/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Tue, 5 Jun 2001 12:25:31 GMT
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
: [...] for any OTP system to have "perfect security" You need to use a
: pad that outputs a file of the length of the longest piece of
: information you need. That means for short messages you need the
: same size pad as for long messages. [...]
Yes, exactly.
You would probably need some sort of padding scheme to say when the
messages end.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Tue, 5 Jun 2001 12:34:24 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: "Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
:> Tom St Denis <[EMAIL PROTECTED]> wrote:
:> : So what? [...]
:>
:> So a 1-byte cyphertext can only represent 256 possible plaintexts.
:>
:> Do you think it is acceptable to have a 128 bit key and then
:> throw away 120 bits of entropy from it when dealing with
:> particular plaintexts?
:>
:> What sort of "provable security" do you think that is?
: This is meaningless and you should know it. First off there are 256! =
: 2^1680 ways to permute a byte. So technically you are not throwing away
: entropy. So even if it *were* a 1-byte block cipher you're not reducing the
: key space.
We're *not* talking about "permuting a byte"!
We're talking about *XOR*ing it with another 1-byte value!
You *do* know what CTR mode is, don't you? ;-)
: Second, in CTR mode the counter is not fixed in size. You do encode full
: blocks. You just end up not having to use all of the output.
If you like - so you encode 128 bits and then throw away 120 of them, leaving
you with 8. How on earth do you think this is a point in your favour?
--
__________ http://rockz.co.uk/ http://alife.co.uk/ http://hex.org.uk/
|im |yler http://atoms.org.uk/ http://mandala.co.uk/ [EMAIL PROTECTED]
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Tue, 5 Jun 2001 12:41:39 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> This concern has been seriously raised. Again (for example) Terry
:> Ritter has expressed reservations about counter mode *because* of the
:> powerful driving signal that the cryptographic primitive is being fed,
:> that might allow an attacker to use differential analysis on it.
:>
:> We all know that *if* the cypher is behaving idealy, it will make no
:> difference - but if there's some attack on the cypher, it might.
:>
:> It seems to me that since the attack is not known to be impossible, while
:> a plausible-looking defense against appears to be is incredibly cheap,
:> there's no good reason not to apply the defense.
: From this stand point it stands to reason that using a LFSR to clock it may
: be just as a bad. You haven't given any evidence either way.
Ah well, I'm talking it for granted that lots of single bit changes
in a predictable region are more likely to give the cryptanalyst ammo
than having inputs that shift continuously sideways, with novel ones
fed in from one end.
If you want me to give a proof of this - or even empirical evidence for
it, I'll pass - but I assume that the idea is unlikely to prove very
controversial.
: Note that many good ciphers are analyzed wrt to hash modes and still
: are consider ok.
Oh yes - at least in the sense that no weaknesses are found.
: I think in any mode where you can control the key and plaintext and still
: not win, just incrementing by 1 will not hurt it,.
I agree completely. *If* we could be sure that we had such a system to
hand, then we wouldn't need to concern ourself about maikng the input
more variable.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Reply-To: [EMAIL PROTECTED]
Date: Tue, 5 Jun 2001 12:48:29 GMT
[EMAIL PROTECTED] wrote:
: "Tom St Denis" <[EMAIL PROTECTED]> writes:
:>
:> My question now is ... replace A..Z with 0..255. Now why isn't CBC mode
:> encryption a "BIJECTIVE" operation?
: If you are now defining a message as ``any possible array of bites'', and
: you are viewing CBC mode as a mapping from possible messages to possible
: messages, then it is indeed a bijection.
Er...
How do you think you encrypt a 2 byte message with a conventional block
cypher in CBC mode?
: What sticks in Scott's craw is that encryption is not (necessarily) a
: bijection between the set of *meaningful* messages and the set of
: *possible* messages.
A dubious assertion. Gat any references or quotes to support it.
: He proposes to ``remedy'' that by first applying a bijection between
: meaningful messages and possible messages, which he calls ``bicom
: compression''.
Ah. Now it transpires that you don't know what you're talking about.
"BICOM compression" is what happens when you apply BICOM:
http://www3.sympatico.ca/mtimmerm/bicom/bicom.html
That has *nothing* to do with "meaningful messages and possible messages".
BICOM is a bijection between the set of all possible messages and itself.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Reply-To: [EMAIL PROTECTED]
Date: Tue, 5 Jun 2001 12:56:16 GMT
[EMAIL PROTECTED] wrote:
: He seems to be trying to create a scheme w.r.t. which every message of
: size <n is the possible compression of a meaningful message. He seems to
: be bothered that the domain of an encryption function is a strict subset
: of the codomain, and he seems to want a pre-encryption step to remedy
: this. In particular, he seems to think that BICOM is such a step.
: If I've understood his aims right, I sincerely doubt he has succeeded. Such
: a ``compression'' scheme is possible--for example, by enumerating the set
: of English messages and the set of all possible messages--but I'd be
: willing to bet that no such scheme would be practical.
Yes, this is essentially the idea David is aiming for.
Yes he has achieved it - for /some/ sets of target data.
No he hasn't achieved it for the domain of English language sentences.
Yes, achieved it for the domain of English language sentences is probably
an impractical goal.
However, note that progress towards the goal is itself worthwile.
Even if you don't have "perfect" compression, good compression still
helps.
If you can't make all the cyphertexts smaller than n decrypt to
correct-looking messages, increasing the proportion that do may
still be worthwhile.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: [EMAIL PROTECTED] (Bob Silverman)
Crossposted-To: sci.math
Subject: Re: RSA's new Factoring Challenges: $200,000 prize. (my be repeat)
Date: 5 Jun 2001 06:08:21 -0700
"Michael Brown" <[EMAIL PROTECTED]> wrote in message
>
> First, go read my page at http://odin.prohosting.com/~dakkor/rsa
I did. Your web site is pseudo-mathematical gibberish. You have not
presented an algorithm.
>
> Then have a quick look at the 1024, 896, 704, or 576 bit numbers. Last 2 bits
> for each of these are ....11 (eg: Last 8 bits of the 1024 bit number are
> ....11001011). Look closely at the second to last digit. A perfect example of
> where the algorithm will work.
>
> Based on my previous tests, the about of RAM required will be about 128 meg
> maximum, and the factoring time should be about 8 minutes (for the 1024 bit
> one).
Terrific. Let us know when you get it done!
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Sophie Germaine Benefits for DH
Date: 5 Jun 2001 13:07:56 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> This means in LL it is possible to find a base that generates all units (in
> the multiplicative group modulo the prime) but when trying to make a DH
> shared key your public key will only generate a group on the order of
> 2^256.
There's something important you're missing. Attempting to solve
discrete log problems in the subgroup is much harder than solving them
in the main field -- you appear to have to use techniques like Pollard's
rho. So, just because the subgroup is relatively small doesn't mean you
have less security.
> The chances of finding a bad LL public key (i.e where it generates a
> small by comparison) sub-group is low why not use a SG prime?
But this isn't `bad' in any sense. This is the whole point of the
exercise. The Lim-Lee construction takes advantage of the relative
difficulty of the subgroup discrete-log problem to produce primes which
are effectively as safe as Sophie-Germain primes, but much easier to
find.
-- [mdw]
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
