Cryptography-Digest Digest #233, Volume #14 Wed, 25 Apr 01 17:13:01 EDT
Contents:
Re: Key scheduling of block cipher (Mok-Kong Shen)
Re: Key scheduling of block cipher (Rick Wash)
Re: OTP WAS BROKEN!!! ("Mark G Wolf")
Re: Key scheduling of block cipher ("Tom St Denis")
Re: What Is the Quality of Randomness? ("Mark G Wolf")
Re: OTP WAS BROKEN!!! ("Tom St Denis")
Re: OTP breaking strategy (newbie)
Re: What Is the Quality of Randomness? ("Tom St Denis")
Re: What Is the Quality of Randomness? ("Mark G Wolf")
Re: OTP breaking strategy ("Tom St Denis")
Re: Key scheduling of block cipher (Mok-Kong Shen)
Re: OTP WAS BROKEN!!! ("Mark G Wolf")
Re: What Is the Quality of Randomness? ("Mark G Wolf")
Re: Key scheduling of block cipher (Mok-Kong Shen)
Re: Micro Video Camera Suitable for Documents? (John Savard)
Re: Micro Video Camera Suitable for Documents? (Mok-Kong Shen)
Re: OTP WAS BROKEN!!! (John Savard)
Re: What Is the Quality of Randomness? ("Tom St Denis")
Re: What Is the Quality of Randomness? ("Jack Lindso")
Re: What Is the Quality of Randomness? ("Brian Gladman")
Re: What Is the Quality of Randomness? (John Savard)
Re: What Is the Quality of Randomness? (John Savard)
Re: First analysis of first cipher ([EMAIL PROTECTED])
Re: OTP breaking strategy (newbie)
Re: What Is the Quality of Randomness? ("Mark G Wolf")
Re: hellman ("Michael Scott")
Re: hellman ("Michael Scott")
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Key scheduling of block cipher
Date: Wed, 25 Apr 2001 22:09:50 +0200
Tom St Denis wrote:
>
[snip]
> > My question was about negative impacts, i.e. whether
> > the modifications could render the cipher weaker than
> > the original and whether it generally means more strength.
>
> Well I don't get it, are you taking a scheduled key and then xoring new
> material in?
(1) means permuting the n subkeys S_i, (2) means xoring
each S_i generated by the original cipher with secret
X_i before being used as subkeys in the way employed
by the original cipher.
M. K. Shen
------------------------------
From: Rick Wash <[EMAIL PROTECTED]>
Subject: Re: Key scheduling of block cipher
Date: 25 Apr 2001 16:12:25 -0400
Mok-Kong Shen <[EMAIL PROTECTED]> writes:
> I like to re-raise an issue that I mentioned in a discussion
> of a thread of the group quite a time back.
>
> A block cipher commonly employs for its n rounds n subkeys
> that are derived from a user supplied key in some manner.
> One can apparently do simple modifications in two ways:
> (1) change the order of the subkeys for the rounds, (2) xor
> the subkeys with some secret random bit sequences. (These
> modifications could be altered independent of the change
> of the proper keys.)
>
> Are there any negative impacts of such modifications to
> the security of the cipher? It seems that at least brute-
> forcing is rendered more difficult thereby.
That depends a lot on the algorithm you are modifying. In general, I
don't know of any side affects that would apply across-the-board for
all algorithms.
However, I have to wonder if that would indeed make the algorithm
stronger. The two ways I can see doing this is to make the order or
the random bit sequences part of the key, which extends the key in a
way that can probably be exploited. The other way of doing this is
basically defining an alternate key schedule that includes these
modification. In this case, it would be an effective strategy to
prevent using off-the-shelf crypto implementations to brute-force the
algorithm, but would not add much security to the algorithm (by
Kerchoff's principle). This is a good way of making a "private"
variation of an algorithm that is not compatible with the standard but
still *probably* as strong.
Rick Wash
------------------------------
From: "Mark G Wolf" <[EMAIL PROTECTED]>
Subject: Re: OTP WAS BROKEN!!!
Date: Wed, 25 Apr 2001 15:17:50 -0500
> The incidence of coincidence comes to mind. Also, the distribution of a
> combination of two plaintexts is not uniform.
Yes, but ultimately your referring to a letter distribution right? As in
the letters of the English language for instance.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Key scheduling of block cipher
Date: Wed, 25 Apr 2001 20:21:37 GMT
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Tom St Denis wrote:
> >
> [snip]
> > > My question was about negative impacts, i.e. whether
> > > the modifications could render the cipher weaker than
> > > the original and whether it generally means more strength.
> >
> > Well I don't get it, are you taking a scheduled key and then xoring new
> > material in?
>
> (1) means permuting the n subkeys S_i, (2) means xoring
> each S_i generated by the original cipher with secret
> X_i before being used as subkeys in the way employed
> by the original cipher.
I can't see how that will strengthen or weaken the cipher directly, except
for contrived cases i.e X_i = S_i (prob=1).
Tom
------------------------------
From: "Mark G Wolf" <[EMAIL PROTECTED]>
Subject: Re: What Is the Quality of Randomness?
Date: Wed, 25 Apr 2001 15:20:43 -0500
So what do I ask the clerk when he shows me several different pieces of
cipher text?
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: OTP WAS BROKEN!!!
Date: Wed, 25 Apr 2001 20:22:32 GMT
"Mark G Wolf" <[EMAIL PROTECTED]> wrote in message
news:9c7bf4$7sfg$[EMAIL PROTECTED]...
> > The incidence of coincidence comes to mind. Also, the distribution of a
> > combination of two plaintexts is not uniform.
>
> Yes, but ultimately your referring to a letter distribution right? As in
> the letters of the English language for instance.
You still don't get it.
It's not any random binary sequence is more probable then say "TOM" it's
that both "TOM" and "FOG" are equal probable. Which means you can't tell
them apart.
Why is this thread going on?
Tom
------------------------------
From: newbie <[EMAIL PROTECTED]>
Subject: Re: OTP breaking strategy
Date: Wed, 25 Apr 2001 16:17:22 -0300
That is a polite answer.
Thank you.
Tom St Denis wrote:
>
> "newbie" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > You have to read more books about politeness and be less arrogant.
> > Arrogance in the sure way to be stupid forever.
>
> Ok.
>
> Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: What Is the Quality of Randomness?
Date: Wed, 25 Apr 2001 20:23:01 GMT
"Mark G Wolf" <[EMAIL PROTECTED]> wrote in message
news:9c7bkh$16d2$[EMAIL PROTECTED]...
> So what do I ask the clerk when he shows me several different pieces of
> cipher text?
What is the context of this question? What are you trying to find out?
Tom
------------------------------
From: "Mark G Wolf" <[EMAIL PROTECTED]>
Subject: Re: What Is the Quality of Randomness?
Date: Wed, 25 Apr 2001 15:22:08 -0500
Or cipher key I should say.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: OTP breaking strategy
Date: Wed, 25 Apr 2001 20:24:25 GMT
"newbie" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> That is a polite answer.
> Thank you.
>
Not to beat a dead horse to death again (somehow) but please just read some
texts or papers or online stuff concerning crypto. It's ok to ask questions
here but like others said we are not here todo your work for you. If you
want to become a cryptographer you have to learn how to learn and adapt.
Step 1: Fill head with knowledge. Step 2: Figure out how to use it.
Tom
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Key scheduling of block cipher
Date: Wed, 25 Apr 2001 22:23:58 +0200
Rick Wash wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> writes:
>
> > I like to re-raise an issue that I mentioned in a discussion
> > of a thread of the group quite a time back.
> >
> > A block cipher commonly employs for its n rounds n subkeys
> > that are derived from a user supplied key in some manner.
> > One can apparently do simple modifications in two ways:
> > (1) change the order of the subkeys for the rounds, (2) xor
> > the subkeys with some secret random bit sequences. (These
> > modifications could be altered independent of the change
> > of the proper keys.)
> >
> > Are there any negative impacts of such modifications to
> > the security of the cipher? It seems that at least brute-
> > forcing is rendered more difficult thereby.
>
> That depends a lot on the algorithm you are modifying. In general, I
> don't know of any side affects that would apply across-the-board for
> all algorithms.
>
> However, I have to wonder if that would indeed make the algorithm
> stronger. The two ways I can see doing this is to make the order or
> the random bit sequences part of the key, which extends the key in a
> way that can probably be exploited. The other way of doing this is
> basically defining an alternate key schedule that includes these
> modification. In this case, it would be an effective strategy to
> prevent using off-the-shelf crypto implementations to brute-force the
> algorithm, but would not add much security to the algorithm (by
> Kerchoff's principle). This is a good way of making a "private"
> variation of an algorithm that is not compatible with the standard but
> still *probably* as strong.
I don't yet see the relevance of Kerchhoff's principle here.
The modifications are done with additional secret materials
than the normal key. Thus one employs more 'effective' key
bits. If both modifications are done, some of these
additional secret 'key' bits determine the permutation of
the subkeys generated by the original algorithm, the other
parts are utilized to xor with these subkeys. The results
are then used in the original ways (in lieu of the original
subkeys). The opponent may know that these modifications
are done (that's what concerns Kerchhoff), but doesn't
know the additional secret 'key' bits.
M. K. Shen
------------------------------
From: "Mark G Wolf" <[EMAIL PROTECTED]>
Subject: Re: OTP WAS BROKEN!!!
Date: Wed, 25 Apr 2001 15:25:32 -0500
> You still don't get it.
Your really on the war path aren't you.
> It's not any random binary sequence is more probable then say "TOM" it's
> that both "TOM" and "FOG" are equal probable. Which means you can't tell
> them apart.
??
> Why is this thread going on?
Why are you asking?
------------------------------
From: "Mark G Wolf" <[EMAIL PROTECTED]>
Subject: Re: What Is the Quality of Randomness?
Date: Wed, 25 Apr 2001 15:28:11 -0500
> What is the context of this question? What are you trying to find out?
I'm trying to find out if given a choice of several different pieces of
cipher key, which do I choose to best encrypt a message.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Key scheduling of block cipher
Date: Wed, 25 Apr 2001 22:26:15 +0200
Tom St Denis wrote:
>
> I can't see how that will strengthen or weaken the cipher directly, except
> for contrived cases i.e X_i = S_i (prob=1).
Questioned also in OP: Isn't it that brute-forcing is
made more difficult?
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Micro Video Camera Suitable for Documents?
Date: Wed, 25 Apr 2001 20:36:17 GMT
On Tue, 24 Apr 2001 14:29:58 GMT, Samuel Paik <[EMAIL PROTECTED]> wrote,
in part:
>60 dpi is probably too low. Consider you are imaging 10 pt type--that's
>12 characters/inch. At 60 dpi you've got about 5 pixels per character--
>probably too low for accurate recognition.
Not five pixels per character. Five pixels across a character, and
about eight pixels high. Although typewritten text would be more like
10 characters per inch - and 12 points, so that gives a six by ten
pixel cell.
That would be enough to make letters into blobs, enough of which could
be recognized to read words by their shape. (60 dpi is, of course,
enough to print documents with a 5x7 matrix - and 100 dpi is used by
low-resolution fax machines.)
But unless you can aim the camera at the document, the required
resolution is still immense.
At 60 dpi, and assuming the document faces the camera directly so that
it can be read, it might still take up just a fraction of the field of
view. Perhaps a 3000 by 4000 pixel sensor. 12 megapixels.
Yes, some of the newer digital cameras are in that range, but a micro
spy camera, probably not. And it would require quite a bit of
bandwidth...
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Micro Video Camera Suitable for Documents?
Date: Wed, 25 Apr 2001 22:39:41 +0200
John Savard wrote:
>
[snip]
> Yes, some of the newer digital cameras are in that range, but a micro
> spy camera, probably not. And it would require quite a bit of
> bandwidth...
One reads in Kahn's book about the micro dots of WWII. How
does that compares with the modern technology in photography?
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: OTP WAS BROKEN!!!
Date: Wed, 25 Apr 2001 20:43:23 GMT
On Wed, 25 Apr 2001 12:57:54 -0300, newbie <[EMAIL PROTECTED]>
wrote, in part:
>I can still convert those words to bit-strings.
>Do you agree with that statement?
>If yes, I continue.
That isn't the hard part.
>My idea is that even if that the statement C= any P Xor K (as
>"complement") can not be mathematically "broken", the probability of any
>bit of P (depending on its position) is not equiprobable. My goal is to
>exploit that difference.
Since you know C, it is indeed also true that K is no longer
equiprobable. It conforms, now, to the probability distribution of P,
because you know C.
But you can go *no further*.
>So you can still deduce the "randomness" of the key.
>You are going to obtain if you compute "pattern" Xor Ciphertext = random
>key really used (this key is unique for the sender).
>This key is not hundred per cent the sender used, but 75% or less.
>If I have the quite-true key, I can use a controlled random key for my
>plain-text to try to recover the plaintext that have more signification
>given the context.
I don't understand these three paragraphs at all.
>I'm waiting for comments.
>I know that I'm trying to find the "impossible".
You can take our word for it that it _is_ impossible. Your first
attempt did show the kind of technique which could be used if K was
not truly random, and similar techniques are possible when the same K
is used twice.
I am sorry, but I do not believe you can receive here any responses
that you will find genuinely useful. If after re-thinking, you still
think you have something, try explaining it very carefully and
plainly. Then it might be possible to explain what we think is the
specific flaw. Otherwise, there is not much that can be done.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: What Is the Quality of Randomness?
Date: Wed, 25 Apr 2001 20:44:29 GMT
"Mark G Wolf" <[EMAIL PROTECTED]> wrote in message
news:9c7c2h$q0u$[EMAIL PROTECTED]...
> > What is the context of this question? What are you trying to find out?
>
> I'm trying to find out if given a choice of several different pieces of
> cipher key, which do I choose to best encrypt a message.
What? If you are given that the OT pad is either A or B then you just try
both. Of course both may lead to sensible messages...
Tom
------------------------------
From: "Jack Lindso" <[EMAIL PROTECTED]>
Subject: Re: What Is the Quality of Randomness?
Date: Wed, 25 Apr 2001 23:48:10 +0200
> No, doesn't there have to be more than one object before you can call
> something a random... "occurrence"? In fact how many objects does there
> have to be before we can decide on a randomness? Is 010 more or less
random
> than 110 ?
Well lets try and put it like this :
a. Find a super mind/computer or just plain old NSA = Entity.
b. Take your super-center's Random String.
Now iterate ( i ) throe the following steps:
1. Show the Entity (i)'th bit + all the previous bits.
2. Let the Entity guess the (i+1)'th bit (Record the result
right/wrong).
Now you have the number of right and wrong answers, they should be the same.
Result 1 : The smaller the | #right - #wrong | the better the quality.
Result 2 : The bigger the ( i ) the more assured you are of Result 1 thus
it's an asymptotic function which reach infinity or 100% sure when ( i ) =
infinity.
*Note: | a | denotes > if(a<0){a=-a}
# denotes > the magnitude (in our case "the number of")
--
Anticipating the future is all about envisioning the Infinity.
http://www.atstep.com
====================================================
"Mark G Wolf" <[EMAIL PROTECTED]> wrote in message
news:9c776u$4qp6$[EMAIL PROTECTED]...
> > Randomness is just a POV topic. If I make a bit say c=0 if that's
random
> > from your point of view it must be random for all intents and purposes.
>
> No, doesn't there have to be more than one object before you can call
> something a random... "occurrence"? In fact how many objects does there
> have to be before we can decide on a randomness? Is 010 more or less
random
> than 110 ?
>
>
>
>
>
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: What Is the Quality of Randomness?
Date: Wed, 25 Apr 2001 21:56:04 +0100
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:rjFF6.56409$[EMAIL PROTECTED]...
>
> "Mark G Wolf" <[EMAIL PROTECTED]> wrote in message
> news:9c776u$4qp6$[EMAIL PROTECTED]...
> > > Randomness is just a POV topic. If I make a bit say c=0 if that's
> random
> > > from your point of view it must be random for all intents and
purposes.
> >
> > No, doesn't there have to be more than one object before you can call
> > something a random... "occurrence"? In fact how many objects does there
> > have to be before we can decide on a randomness? Is 010 more or less
> random
> > than 110 ?
>
> 010 is only more random then 110 if 110 occurs more frequently.
This confuses randomness with probability of occurence. In a bit stream the
isolated fact that 110 occurs more or less frequently than 010 says nothing
about randomness since there may be a pattern in the stream.
For example, in a bit stream that is known to repeat the sequence
'110110110010' endlessly, there is no randomness even though 110 occurs more
frequently than 010.
Randomness is more about (in)predictability (of future bit patterns from
past known bits) than it is about probability of occurence as such.
Brian Gladman
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: What Is the Quality of Randomness?
Date: Wed, 25 Apr 2001 20:51:55 GMT
On Wed, 25 Apr 2001 13:33:56 -0500, "Mark G Wolf"
<[EMAIL PROTECTED]> wrote, in part:
>You guys are a great source of inspiration, so I ask you, what is the
>quality of randomness?
The quality of randomness cannot be established by putting the
generated digits through a sieve of statistical tests. Instead,
randomness comes from true physical sources like the rain from the
clouds in the sky...
Sorry, I couldn't resist.
The quality of the output from a proposed pseudo-random number
generator (PRNG) can be measured by how well it passes various
statistical tests. Is the distribution uniform? Do numbers have any
correlation with those which precede them? The "poker test" is one
heuristic test sometimes used.
But those kinds of tests cannot be used to determine if 'random'
digits are produced by a cryptosecure generator or not, because
cryptanalysis digs much deeper than any simple statistical test. This
is why there is an insistence - when generating private keys for a
public/private key system, when generating session keys, when
generating keys for an OTP - on using random numbers that come from an
authentic physical source (dice, flipping coins, or more convenient
electronic means).
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: What Is the Quality of Randomness?
Date: Wed, 25 Apr 2001 20:54:50 GMT
On Wed, 25 Apr 2001 14:05:11 -0500, "Mark G Wolf"
<[EMAIL PROTECTED]> wrote, in part:
>In fact how many objects does there
>have to be before we can decide on a randomness? Is 010 more or less random
>than 110 ?
Is 010 an object, or is it three objects?
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: First analysis of first cipher
Date: Wed, 25 Apr 2001 12:01:57 -0800
Mark Wooding wrote:
>
> [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
>
> > Last week I posted my first cipher (now dubbed "Brontosaurus") and
> > was challeged to cryptanalyze it. Once again, point out WHY I'm going
> > wrong as well as where:
>
> <grin>
>
> > The short analysis is that Bronto will be "easily" broken using
> > differential cryptanalysis techniques. The primary weakness of the
> > cipher is that S-boxes with 4-bit entries, chosen at random, are
> > used. At this point, I think that the weakness is due primarily to the
> > small m, and not necessarily due to the fact that the entries are
> > randomly chosen.
>
> With an S-box that small, you must choose it carefully, rather than
> trusting to luck.
>
I've seen some papers discussing the use of bent functions to generate
strong S-boxes. Other papers discuss Hadamard matrices. What are the
other common methods of generating strong S-boxes.
> > Since the S-boxes are the only part of the cipher which provides
> > non-linearity, the strength of the cipher depends almost entirely on
> > the strength of the S-boxes.
>
> No. Everything there has an important function. Each component is weak
> in isolation. You must combine them together so that they strengthen
> each other. A cipher is an ensemble piece.
It seems to me that the P-boxes (which provide "diffusion") are only
there
to support the S-boxes i.e. to ensure that different S-boxes are used
rather
than the same S-box being used over and over. A P-box alone doesn't
provide
"security" but an S-box by itself does, provided it is large enough. A
block cipher
simply mimics a large S-box. I think a cipher with strong S-boxes and
weak
P-boxes would be better than a cipher with weak S-boxes and good
P-boxes.
Granted, as you said, ideally every component should be optimized.
>
> > Next, I'm going to try to determine the del_Input, del_Output table for
> > the F function of my cipher.
>
> Unless you have some clever algorithm in mind for this, it will take Too
> Long.
>
Yep. I'll find the round characteristic then!
> -- [mdw]
------------------------------
From: newbie <[EMAIL PROTECTED]>
Subject: Re: OTP breaking strategy
Date: Wed, 25 Apr 2001 16:57:21 -0300
If my post are stupid one, why are you wasting your peciuos time? Do not
read what I wrote.
When you see newbie as sender, do not open the post.
And everyone is ok.
Thank for not reading my posts.
Tom St Denis wrote:
>
> "newbie" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > That is a polite answer.
> > Thank you.
> >
>
> Not to beat a dead horse to death again (somehow) but please just read some
> texts or papers or online stuff concerning crypto. It's ok to ask questions
> here but like others said we are not here todo your work for you. If you
> want to become a cryptographer you have to learn how to learn and adapt.
> Step 1: Fill head with knowledge. Step 2: Figure out how to use it.
>
> Tom
------------------------------
From: "Mark G Wolf" <[EMAIL PROTECTED]>
Subject: Re: What Is the Quality of Randomness?
Date: Wed, 25 Apr 2001 16:03:42 -0500
> Is 010 an object, or is it three objects?
Good point. Or is it a function of time?
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: hellman
Date: Wed, 25 Apr 2001 16:01:44 -0500
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:9FCF6.55680$[EMAIL PROTECTED]...
>
> "Michael Scott" <[EMAIL PROTECTED]> wrote in message
> news:YuCF6.179959$[EMAIL PROTECTED]...
> >
> > "Tom St Denis" <[EMAIL PROTECTED]> wrote in message
> > news:slCF6.55666$[EMAIL PROTECTED]...
> > >
> > > > > For secure DH (or any DLP PK algorithm) in Z*p you want your prime
P
> > to
> > > be
> > > > > large and be such that (P-1)/2 is also prime (or at the very least
a
> > > have
> > > > a
> > > > > huge prime factor). Your base G should be primitive such that
> > > > >
> > > > > G^((P-1)/q) != 1 for all q that divide P-1.
> > > >
> > > > No - that's wrong. The "base" G should be the generator of the prime
> > order
> > > > subgroup of order (p-1)/2. Choose P a 1024-bit prime, make K a
160-bit
> > > > random number, and choose G = 3 (or 4).
> > >
> > > That's chosen because often Sophie Germain primes are not used. You
> want
> > to
> > > make sure G generates the large subgroup. However, if you make sure
> that
> > G
> > > generates the largest subgroup it's more secure. is it not?
> > >
> >
> > There are two ways of doing Diffie-Hellman. Either choose p a safe
prime,
> > use a small 160-bit exponent and a tiny generator (3 or 4), or choose a
> > prime p such that q divides (p-1) where q is itself a 160-bit prime.
Then
> > find a generator of the q-order subgroup, and use a random exponent mod
q.
> >
> > In either case the group order, (p-1)/2 or q, should be prime.
>
> Why would you limit the exponent?
Because its faster. There are two types of attack on the discrete logarithm
problem. One (Index calculus) exploits the small size of p, the other (e.g.
Pollard Rho, Pollard Lambda) exploits the small size of the exponent. They
both have quite different complexities. If you use Elliptic curves index
calculus methods don't apply, and hence a much smaller prime modulus p can
be used here as well. If you use an exponent of 160 bits, the best discrete
logarithm attacks have a complexity of about 2^80 steps - which is reckoned
to be infeasible.
Mike Scott
>
> Tom
>
>
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: hellman
Date: Wed, 25 Apr 2001 16:04:43 -0500
BTW for the reasons for using a prime order subgroup, and justification for
small exponents, see "On Diffie-Hellman Key Agreement with Short Exponents",
van Oorschot & Wiener, Eurocrypt '96
Mike Scott
------------------------------
** 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
******************************
