Cryptography-Digest Digest #595, Volume #14 Tue, 12 Jun 01 12:13:01 EDT
Contents:
Simple Crypto II, the public key... (Phil Carmody)
Re: One last bijection question (Mok-Kong Shen)
Lookup table for DH's prime P? (quequ)
Re: One last bijection question (Mok-Kong Shen)
Re: Alice and Bob Speak MooJoo ("Robert J. Kolker")
Re: Alice and Bob Speak MooJoo ("Robert J. Kolker")
Re: Alice and Bob Speak MooJoo ("Robert J. Kolker")
Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY (Mok-Kong Shen)
Re: differential cryptanalysis with a new twist? (Mika R S Kojo)
Re: Best, Strongest Algorithm (gone from any reasonable topic) - (Mok-Kong Shen)
Yarrow PRNG ([EMAIL PROTECTED])
Re: Alice and Bob Speak MooJoo ([EMAIL PROTECTED])
Re: Free Triple DES Source code is needed. (pink aka Chr. Boesgaard)
Re: Anyone Heard of "Churning" (Tim Tyler)
Re: IV (Tim Tyler)
Re: Simple Crypto II, the public key... ([EMAIL PROTECTED])
Re: IV (Tim Tyler)
Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY
(SCOTT19U.ZIP_GUY)
Re: IV ([EMAIL PROTECTED])
Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY
([EMAIL PROTECTED])
Re: Yarrow PRNG (Anton Stiglic)
Re: Lookup table for DH's prime P? (Anton Stiglic)
----------------------------------------------------------------------------
From: Phil Carmody <[EMAIL PROTECTED]>
Subject: Simple Crypto II, the public key...
Date: Tue, 12 Jun 2001 13:21:15 GMT
OK, is there an asymmetric equivalent to the symmetric
while(c=getchar()!=EOF) putchar(c^k);
I'm talking _real entry level_ algorithms, codable to a competant
programmer, but without requiring numerics smarts or an external crypto
library?
Is the only option out there 32-bit RSA? (No don't laugh - I'm comparing
this to a Caeser cyper remember.)
OK, I hope this doesn't start a long rant, all I want is a simple
opinion...
If I can ask you Egon Ronays to compare the kebab found in the kitchen
bin with the pizza slice found down the side of the sofa:
Which is worth the effort more - security through obscurity or the
trivially disassembable 32/64bit RSA?
Views on the food question only accepted if accompanied by a view on the
crypto. :-)
Phil
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: One last bijection question
Date: Tue, 12 Jun 2001 15:24:55 +0200
Mark Wooding wrote:
>
> You can't read. I said that I was taught to use the word `range' in the
> sense in which Nicol used the word `*co*domain'.
Indeed a big blunder of mine.
M. K. Shen
------------------------------
From: quequ <[EMAIL PROTECTED]>
Subject: Lookup table for DH's prime P?
Date: Tue, 12 Jun 2001 15:31:19 +0200
Hi,
I'm still working on an implementation of DH algorithm and have a new
little question:
in DH protocol the 1024bit prime P and the generator G are public values,
it's right?
In this case can I use a lookup table for P (with 1000-2000 germain
primes, for example) and a fixed generator G (G = 4)??
This seems to be a very fast solution, because P take some minutes to
generate on my machine (K7-500), but is this a safe way to follow?
thanks to all
quequ
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: One last bijection question
Date: Tue, 12 Jun 2001 15:57:53 +0200
Mark Wooding wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> > These terms are explained in most textbooks on algebra, I
> > suppose. BTW, in terminology questions, I find it mostly very
> > practical to take a good dictionary/encyclopedia of math.
>
> The reason we're in this mess is that different books give different
> definitions. I suggest that, to avoid confusion in present discussions,
> we avoid the ambiguous term `range' and stick to `codomain' and
> `image'.
Could you please cite one book where the word 'image'
thoroughly replaces 'range' or where the word 'range'
would lead to ambiguity? In the book L. E. Sigler,
Algebra, Springer-Verlag, the terms used are codomain and
range. In the book H. L. Royden, Real Analysis, Prentice
Hall, there is range (codomain is not mentioned) and there
is a term image that means what is mapped to by a subset
of the domain. So, if these two book are a little bit
representative (I don't know, I just happen to have them),
then use of 'image' as replacement for 'range' doesn't
seem to be supported, I am afraid. (This is only a
layman's argument, I am not a mathematician.)
M. K. Shen
------------------------------
From: "Robert J. Kolker" <[EMAIL PROTECTED]>
Subject: Re: Alice and Bob Speak MooJoo
Date: Tue, 12 Jun 2001 10:06:59 -0400
"Douglas A. Gwyn" wrote:
> Boyd Roberts wrote:
> > "Tom St Denis" <[EMAIL PROTECTED]> a �crit:
> > > How would a blind person learn to speak?
> > verbal feedback. it's a bootstrap problem.
>
> Note that Helen Keller learned to communicate despite
> being deaf, dumb, and blind. But it wasn't easy.
1. Keller was not always blind and deaf. I think she
was rendered so by an acute bout with scarlet
fever or measles.
2. She learned to "speak" through her remaining spatial
sense, i.e. her sense of touch.
Humans must learn their first language through ostention,
i.e. direct perception of the referrent.
That is why the sci fi movies of the 1950's drove me crazy.
"We learned your languages by listening to your radio
broadcasts".
Bob Kolker
------------------------------
From: "Robert J. Kolker" <[EMAIL PROTECTED]>
Subject: Re: Alice and Bob Speak MooJoo
Date: Tue, 12 Jun 2001 10:07:35 -0400
Boyd Roberts wrote:
> "Niklas Frykholm" <[EMAIL PROTECTED]> a �crit dans le message news:
>[EMAIL PROTECTED]
> > But the word for "attack" would always be the same. After a while the
> > opponent might learn to correlate the word for "attack" with actual
> > attacks occuring.
>
> no you could agree to use a different word for each attack.
In effect a synonymous homophone.
Bob Kolker
------------------------------
From: "Robert J. Kolker" <[EMAIL PROTECTED]>
Subject: Re: Alice and Bob Speak MooJoo
Date: Tue, 12 Jun 2001 10:09:49 -0400
"Douglas A. Gwyn" wrote:
> "Robert J. Kolker" wrote:
> > If two people share the referent and no one else does,
> > there is no way for an outsider to decode all of the
> > language.
>
> While it is true that some things can remain ambiguous,
> with enough data the parts of speech clearly stand out,
> and if you have some information about a few referents,
> it is sometimes possible to gradually "fill in the gaps"
> by noting connections to already determined parts of the
> plain language. This kind of thing is done a lot in
> breaking codes (as opposed to ciphers).
And if MooJoo had 17 cases and 25 moods, you would
have two chances of doing what you suggest. Slim and
none.
The Japanese never were able to break what the Navajo
Code Talkers were doing.
Bob Kolker
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY
Date: Tue, 12 Jun 2001 16:05:30 +0200
Tim Tyler wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> : John Savard wrote:
>
> :> It is not surprising, however, that today cryptography is concerned
> :> mainly with an area about which Shannon said little, other than to
> :> give it a name: the work factor. Particularly as the extreme utility
> :> (and practicality, and convenience) of the 'public-key' methods has
> :> made them central to most modern employment of cryptographic
> :> techniques, despite the fact that their security, in the
> :> information-theoretic sense, is precisely nil.
>
> : But, if something that is practically secure is of
> : precisely nil security in the information-theoretical
> : sense, that means a big contradiction to intuition/
> : common-sense, isn't it? How could the theory nonetheless
> : gain acceptance?
>
> All the information necessary to read a public key message
> resides in a combination of the message and the public key - and
> both should be considered to be available to the attacker.
>
> If only he could factor (or whatever) the public key he would
> be able to read the message. He has all the information necessary
> to do this at his disposal - but alas, the task takes a lot of effort
> to perform.
>
> The "information-theoretic" security of such a system can
> usefully be though of as being nil.
But measures should have adquate (intuitionally reasonable)
interpretations, I suppose. If a security measure
says 0 security, then one would 'very naturally' think
that that means no protection at all, isn't it?
I don't think that something that is at the disposal
of the opponent but requires a time of eternity to
exploit isn't equivalent to 'no information' to the
opponent, on the other hand.
M. K. Shen
------------------------------
From: Mika R S Kojo <[EMAIL PROTECTED]>
Subject: Re: differential cryptanalysis with a new twist?
Date: 12 Jun 2001 17:06:24 +0300
"Tom St Denis" <[EMAIL PROTECTED]> writes:
>
> "Mika R S Kojo" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
>
> > The standard higher-order differential cryptanalysis is slightly
> > different. It is ultimately about similar sums as your triples, but
> > based on a bit more elaborate theory. Namely, finding the non-linear
> > degree of a boolean function (e.g. a block cipher under a fixed
> > key).
>
> Would you mind explaning higher-order differentials. Namely how the attack
> works? I have read Knudsen's paper but it's not clear. (Usually it takes a
> few reads...)
I don't mind, but my approach to this subject might be even less
pedagogical than Knudsen's. You may find this a bit difficult but the
sum (1) below is all you really need.
Let K be a field and K[X] a ring of polynomials (we can let X = (X_1,
..., X_n) to get into a more generic situation). We need basic linear
algebra and operators D_x and T_x. Derivation is defined as follows
D_x = T_x - T_0 = T_x - 1,
when
(T_x f)(z) = f(z + x),
(D_x f)(z) = (T_x f - T_0 f)(z) = f(z + x) - f(z),
and where f \in K[X].
The operator T_x satisfies
T_x f + g = T_x f + T_x g,
T_x fg = f T_x g,
T_x a = a,
for f,g \in K[X] and a \in K. Hence the derivation D_x satisfies
D_x f + g = D_x f + D_x g,
D_x fg = f D_x g,
D_x a = 0,
with f,g,a as above. Observe that fg = f o g and not a multiplication
in K[X]. This is a bad convention of mine.
The fact to know is
deg D_x f <= (deg f) - 1,
and if y,x_1,...,x_n are linearily independent then
deg D_y D_{x_1} ... D_{x_n} f <= (deg D_{x_1} ... D_{x_n} f) - 1.
As a corollary we get
D_{x_1} ... D_{x_n} f = c,
iff x_1, ..., x_n are linearily independent and deg f = n. If deg f <
n then c = 0. (Recall that deg is the non-linear order or total
degree, namely given a term X_1^e_1 ... X_n^e_n its degree is e_1 +
... + e_n. In characteristic 2 this all becomes especially simple.)
Idea by Knudsen and Jacobsen is to use these facts to mount an chosen
plaintext attack. They assume that
D_{x_1} ... D_{x_n} T_w f = 0,
and this becomes
\sum_{l \in L} f(w + l) = 0, (1)
where L is the (linear) vectorspace spanned by x_1, ..., x_n. The w is
just a convenient randomization factor that allows rerunning the attack to
gain confidence.
To be more explicit the f \in K[X] is just the block cipher under a fixed
key. In practice K = F_{2} seems to be the usual interpretation.
I have not seen this formulation used elsewhere in cryptographic
literature. However, similar approach is used in p-adic
analysis. Benefit of using derivations is that proofs are pretty much
trivial.
Also this approach allows one to talk about derivatives for truncated
differentials and even impossible differentials. Those seem to be of
marginal importance though. It should be clear that this approach
gives an algorithm for finding the non-linear order.
So in conclusion the main point is to use the sum (1) with some
particularly selected linear vectorspace L. If this seems difficult
obtain a book on linear algebra and read the first few
chapters. (There should be some good online notes also on linear
algebra.)
Oh, the connection to interpolation attacks should not be forgotten
(almost did). Also there are some generalizations of interpolation
attacks and higher-order differential attacks. Some are based on
coding theory (like on "idealic" list decoding algorithms).
Mika
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) -
Date: Tue, 12 Jun 2001 16:22:14 +0200
Tim Tyler wrote:
>
[snip]
> The length of the plaintext can be obscured by cryptography
> like every other aspect of it. It is quite possible for
> cryptanalysis (rather than traffic analysis) to be the only
> method of getting anything useful out of it.
Consider the infinite OTP case. In reality, it is
obvious that we can't send infinite bits within zero time
but send the bit string more or less fast. Now we also
don't have all infinite number of messages to be sent at
once. They have a certain arrival time. So we could
consider sending on each (successive) day a certain amount
of messages. If we could accept this kind of operation,
then we could (as I wrote in another post) concatenate
the messages, say, of a day (or other time intervals) and
send that as a single bunch. The individual message
boundaries would then hardly be discernable by the opponent.
M. K. Shen
======================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: [EMAIL PROTECTED]
Subject: Yarrow PRNG
Date: Tue, 12 Jun 2001 14:32:04 GMT
Hi All,
I have a couple of questions about Yarrow (counterpane.com).
1. Has anyone reviewed the properties of the PRNG? Is it as good as it claims?
2. Has anyone been able to compile the freely available C code?
3. Does anyone have the complete implementation as described in the paper? (The
code included on the site is apparently, not the code which the paper
describes.)
Thank you for any inputs ... Wilson
------------------------------
Subject: Re: Alice and Bob Speak MooJoo
From: [EMAIL PROTECTED]
Date: 12 Jun 2001 10:36:52 -0400
"Robert J. Kolker" <[EMAIL PROTECTED]> writes:
>
> The Japanese never were able to break what the Navajo Code Talkers
> were doing.
Which is no credit to the Japanese: they even had a captured Navajo. If
they had made proper use of him, they would have cracked the code in an
afternoon or so. (If they had looked at English translations of the code
talkers' messages, then the simple alphabet code would have leaped from
the page.)
Len.
--
Could you describe the mess, and explain why you think that the lack
of opportunistic bombardment is a contributing factor?
-- Dan Bernstein
------------------------------
From: [EMAIL PROTECTED] (pink aka Chr. Boesgaard)
Subject: Re: Free Triple DES Source code is needed.
Date: 12 Jun 2001 16:46:50 +0200
Mok-Kong Shen <[EMAIL PROTECTED]> writes:
> Since we are already at this 'derived' topic, I may be
> allowed to ask a question about it: Which current C++
> compliers are known to be strictly standard conforming?
> (My Microsoft Visual C++ compiler, of version 6.0, isn't.)
> Thanks.
KAI C++ is the best conforming compiler I have heard of (www.kai.com).
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Anyone Heard of "Churning"
Reply-To: [EMAIL PROTECTED]
Date: Tue, 12 Jun 2001 14:23:18 GMT
Gregory G Rose <[EMAIL PROTECTED]> wrote:
: In article <[EMAIL PROTECTED]>,
: < APON uses a 24-bit key churning mechanism
: 24 bit keys are worthless.
That sentence should probably be parsed as:
"APON uses a 24-bit (key churning) mechanism"
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: IV
Reply-To: [EMAIL PROTECTED]
Date: Tue, 12 Jun 2001 14:34:02 GMT
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] wrote in <[EMAIL PROTECTED]>:
:>[...] you need some sort of signature or checksum in CTR mode.
: This means one of the so called advantages of CTR. Will cause problems.
: Since you can use CTE to Decrypt portions of a message. IF one used
: it in that way you need some sort of checksum or signature for that
: small portion to protect one self agaisnt being altered by a middle
: man.
The CTR mode advocates say you need to do this /anyway/ if you want
authentication. However, it is a fact that not every message is
authenticated - and the negative consequences of failure to authenicate
can be *much* worse if CTR mode is employed:
If you have a known plaintext, you can extract the entire keystream.
You can then forge messages of that length, resulting in apparently
sensible messages from the POV of the recipient.
Try doing that if CBC mode is employed.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Simple Crypto II, the public key...
Date: Tue, 12 Jun 2001 14:53:36 GMT
Phil Carmody <[EMAIL PROTECTED]> wrote:
: OK, is there an asymmetric equivalent to the symmetric
: while(c=getchar()!=EOF) putchar(c^k);
Okay, I know this is really simplistic, but it does work. The exponents
are really small, of course, but they're large enough to handle 8-bit values.
The values e and m in the encryption program represent the public key and
the d and m values in the decryption program represent the private key.
The encryption program loops 16 times for each character while the
decryption program loops 144 times per char. Also, the size of the encrypted
file is twice the size of the original.
Both programs are basically just RSA. The mod_pow function raises a value to
power <exp> modulo <modulus>.
The encryption program is:
#include <stdio.h>
main(int argc, char *argv)
{
int ch, e, m, enc;
e = 17;
m = 667;
while ((ch= getchar()) != EOF)
{
enc = mod_pow(ch, e, m);
putchar((enc >> 8) & 255);
putchar(enc & 255);
}
}
int mod_pow(int ch, int exp, int modulo)
{
int i, result;
result = ch;
for (i=1; i < exp; i++)
{
result = (result * ch) % modulo;
}
return result;
}
Then the decryption program is:
#include <stdio.h>
main(int argc, char *argv)
{
int ch1, ch2, d, m;
char dec;
d = 145;
m = 667;
while (((ch1= getchar()) != EOF) && ((ch2=getchar()) != EOF))
{
dec = (char) mod_pow((ch1<<8)+ch2, d, m);
putchar(dec);
}
}
int mod_pow(int ch, int exp, int modulo)
{
int i, result;
result = ch;
for (i=1; i < exp; i++)
{
result = (result * ch) % modulo;
}
return result;
}
--
Mark Wutka
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: IV
Reply-To: [EMAIL PROTECTED]
Date: Tue, 12 Jun 2001 14:39:11 GMT
Cristiano <[EMAIL PROTECTED]> wrote:
: I want to encrypt a file of L bytes with a block cipher in CBC mode (like
: RC6 or Rijndael).
: For speed reasons I read N bytes at time (N>1024) and then I encrypt this
: block.
: Every N bytes I use the IV to XORing the firsts 16 bytes of plain text.
: Is there some weakness in this way?
Very possibly. If I understand correctly, you are using the same IV and
the same key - effectively starting again every N bytes, in order to
get speed (through parallelism?).
That means identical plaintexts (at those offsets) will result in
identical cyphertexts.
Either a) use a different IV, or b) increment the IV, or change it in some
way between encryptions of the N bytes. Purists would advise you to go
for a).
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY
Date: 12 Jun 2001 14:56:41 GMT
[EMAIL PROTECTED] (Mok-Kong Shen) wrote in <3B2621AA.ABFA0018@t-
online.de>:
>
>But measures should have adquate (intuitionally reasonable)
>interpretations, I suppose. If a security measure
>says 0 security, then one would 'very naturally' think
>that that means no protection at all, isn't it?
>
But if you don't realize that it has no information
theoritic security. Yout less likely to fall into the
trap that many programs fall into. Which is to ignore
all other possible security features except the hopeful
counting on of a hard to exploit work factor. Many
encryption pregorams could at least offer some safety
if they wished. Such as PGP.
>I don't think that something that is at the disposal
>of the opponent but requires a time of eternity to
>exploit isn't equivalent to 'no information' to the
>opponent, on the other hand.
All those so called time to eternity to exploit are
based on no one finding simple ways to exploit a break.
If history has any lessons. It is thats its foolish to
smuglly sit by and hope that its hard to break. One should
always strive to add what ever security one can. To put
all your eggs in one basket is surely the recipe for
desaster. But that seems to be what AES is all about.
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!
------------------------------
Subject: Re: IV
From: [EMAIL PROTECTED]
Date: 12 Jun 2001 11:19:26 -0400
Tim Tyler <[EMAIL PROTECTED]> writes:
>
>> [CTR mode]
>
> If you have a known plaintext, you can extract the entire keystream.
No you can't. You can only extract the portion of the keystream which
corresponds to the known bits. That gives you (potentially) some
ciphertext corresponding to a known-plaintext, and might be used to
attack the underlying block cipher.
> You can then forge messages of that length, resulting in apparently
> sensible messages from the POV of the recipient.
Not quite--you can change THAT PORTION of the ciphertext stream to
anything you want. But unless you crack the underlying block cipher,
you won't know the rest of the keystream.
The same weakness, BTW, applies to *all* synchronous stream ciphers.
Indeed, it applies to the OTP: if you know the exact plaintext for a
portion of a message, you can modify that portion in transit to say
anything you want. Unless some sort of signature is used, your forgery
will go undetected.
Len.
--
Whatever happened to Preparations A through G?
------------------------------
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY
From: [EMAIL PROTECTED]
Date: 12 Jun 2001 11:26:16 -0400
> [EMAIL PROTECTED] (Mok-Kong Shen) wrote in <3B2621AA.ABFA0018@t-
> online.de>:
>
>> If a security measure says 0 security, then one would 'very naturally'
>> think that that means no protection at all, isn't it?
``Information-theoretic security'' is not synonymous with ``security''.
The former means ``Even if the bad guy has found my key, and read my
message, he still can't be certain whether he's read the correct message
or found the correct key.'' The latter simply means ``the bad guy can't
read my message.''
You can look at it this way. Factoring is at least NP (and possibly
P). So if the bad guy is told, ``Here's Mok's private key,'' he can
verify in polynomial time that he actually has the correct key--thanks
to your public key. So he can be absolutely sure that he has read your
message correctly. That's ``zero information-theoretic security.''
Len.
--
We also believe candor benefits us as managers: the CEO who misleads
others in public may eventually mislead himself in private.
-- Warren Buffett, 1983
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Yarrow PRNG
Date: Tue, 12 Jun 2001 11:59:24 -0400
There is allot of "engineering decisions" that are not described
in the description of yarrow. Also, as you noted, the code on
counterpane's
web site does not correspond to the description they have (it
corresponds
to an older version of Yarrow, for which they don't have any description
on their web site). I hope they do something about it this sometime...
Take a look at
http://opensource.zeroknowledge.com/yarrow/index.html
for notes on implementation of the protocol described in the Yarrow-160
paper.
--Anton
[EMAIL PROTECTED] wrote:
>
> Hi All,
>
> I have a couple of questions about Yarrow (counterpane.com).
>
> 1. Has anyone reviewed the properties of the PRNG? Is it as good as it claims?
>
> 2. Has anyone been able to compile the freely available C code?
>
> 3. Does anyone have the complete implementation as described in the paper? (The
> code included on the site is apparently, not the code which the paper
> describes.)
>
> Thank you for any inputs ... Wilson
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Lookup table for DH's prime P?
Date: Tue, 12 Jun 2001 12:08:18 -0400
quequ wrote:
>
> Hi,
> I'm still working on an implementation of DH algorithm and have a new
> little question:
>
> in DH protocol the 1024bit prime P and the generator G are public values,
> it's right?
> In this case can I use a lookup table for P (with 1000-2000 germain
> primes, for example) and a fixed generator G (G = 4)??
Sure, if you work with Sophie Germain primes (primes q, such that 2*q +
1
is also prime), then you can work in the group mod 2*q + 1. (Note, I'd
keep
2*q + 1 in the table, not just the Sophie Germain prime q, because the
modulus
you need is 2*q + 1).
Any element != 1 and p-1 will generate a large enough group, so G = 4
will work.
The prime modulus can be public. You can even always use the same
modulus,
no need to change (so no need for the table, unless you want primes of
different
sizes, for different levels of security...).
--Anton
> This seems to be a very fast solution, because P take some minutes to
> generate on my machine (K7-500), but is this a safe way to follow?
>
> thanks to all
>
> quequ
--
___________________________________
Anton Stiglic <[EMAIL PROTECTED]>
Software developer & Cryptologist.
Zero-Knowledge Systems Inc.
___________________________________
------------------------------
** 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
******************************
