Cryptography-Digest Digest #496, Volume #11 Wed, 5 Apr 00 16:13:01 EDT
Contents:
Re: Download Random Number Generator from Ciphile Software ("John E. Kuslich")
Re: Q: Entropy (Johann Hibschman)
Re: RNG based on primitive multiplicative generator. (David A. Wagner)
Re: GSM A5/1 Encryption (David A. Wagner)
Re: Q: Entropy (Mok-Kong Shen)
Re: GSM A5/1 Encryption (David A. Wagner)
Re: GSM A5/1 Encryption (David A. Wagner)
Re: Is this code crackable? (Dan Day)
Re: Q: Entropy (Mok-Kong Shen)
Re: GSM A5/1 Encryption (David A. Wagner)
Re: Keeping numbers small in RSA (Bob Silverman)
Re: Keeping numbers small in RSA (Bob Silverman)
Re: Keeping numbers small in RSA (Bob Silverman)
Re: Q: Entropy (Bryan Olson)
Re: Key exchange using Secret Key Encryption (zapzing)
lattice based cryptosystems (David A Molnar)
Re: Key exchange using Secret Key Encryption (zapzing)
Even more crypto humor ! ([EMAIL PROTECTED])
Re: Q: Entropy ("Tony T. Warnock")
Re: generator of Zp (Bob Silverman)
Re: generator of Zp (Bob Silverman)
----------------------------------------------------------------------------
From: "John E. Kuslich" <[EMAIL PROTECTED]>
Subject: Re: Download Random Number Generator from Ciphile Software
Date: Wed, 5 Apr 2000 11:10:05 -0700
The following number is PERFECTLY random as anyone who has read my help
files can plainly see!!! 42
Since I have explained it, must be true! Anyone who disagrees has not read
my help files.
This is NOT herpetological lubricant. This guy sells really random numbers,
honest, no really...REALLY!
I'll bet this guy almost had perpetual motion too!
The author suggests dragging and dropping...good idea.
JK http://www.crak.com Password Recovery Software
...where do they all come from...
:--) :--) :--)
Anthony Stephen Szopa <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Douglas A. Gwyn" wrote:
> >
> > Anthony Stephen Szopa wrote:
> > > I address this issue when I discuss inherent or introduced bias
> > > either in the theory or the processes in the Theory Help file.
> > > If there are no biases in either then there are no
> > > cryptoanalytically exploitable characteristics.
> >
> > That's simply not true, if you're using "bias" with its usual
> > statistical meaning. For example: take *any* (possibly biased)
> > binary cipher stream, and map its "0" to "AB", maps its "1" to
> > "BA". If you wish, then map "A" to "0" and "B" to "1". The
> > result is a totally unbiased binary cipher stream, which can
> > readily be converted back into the original (biased) cipher
> > stream and then broken however the original cipher could be
> > broken. So, the absence of bias doesn't imply anything one
> > way or the other about the system's security.
> >
> > Or perhaps by "bias" you mean something about the elementary
> > operators that are composed to construct the encryption system.
> > It is a fact that any Boolean function can be built solely
> > using NAND operators, and the output of a NAND operator is a
> > symmetric function of the inputs. Yet the overall system is
> > an arbitrary, typically highly unsymmetric, function. One has
> > to be careful in asserting that properties of the components
> > of a system are inherited by the system as a whole; usually
> > that is not true. (When it is true, we have an "algebra", and
> > that is mathematically worthy of study.)
>
> Discuss the software. I do not want to have you exploit your
> erudition, and pontificate.
>
> If you have a point about the software make it and support it
> with fact.
>
> To do this you must have the software, have thoroughly read the
> Help Files, run the examples, and taken all the tutorials.
>
> If you will not do this I have no time to spend with such an
> unmotivated person.
------------------------------
From: Johann Hibschman <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: 05 Apr 2000 11:29:10 -0700
Reply-To: [EMAIL PROTECTED]
I was idly wandering along when I notied Mok-Kong Shen writing:
> Anyway, you don't seem to have specifically answered
> my question of whether the sequence of all 0 has the same or
> different entropy as an apparently random sequence in the experiment.
> According to the above, the answer should be yes. Now consider
> applying compression to both, then they are likely to get compressed
> to different lengths. Would that fact conform to their having
> the same entropy? Thanks.
I don't know information entropy; I just know statistical mechanics
entropy. There, yes, a sequence of all 0's has the same probability
as any other sequence generated by a fully random 0 or 1 process.
Its entropy, however, is undefined.
In order to get an *entropy*, you have to lump individual sequences
(usually called microstates) into categories (macrostates). The
entropy is then proportional to the log of the number of microstates
in a given macrostate.
If, for example, you lumped all bit-sequences with the same number of
ones into a macrostate, then the entropy of that all-0 sequence would
be 0, since there is exactly 1 microstate corresponding to it.
In short, you're asking the wrong question. Even for info theory, if
you want to call something an entropy, it depends on the model you
have for the communication channels and messages. For compression,
you need to know what kinds of patterns count as "the same". You need
a bigger model in there, somewhere, otherwise all you have is
probability. That's all raw conjecture, though, since all I really
know is the stat-mech entropy.
--
Johann Hibschman [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: RNG based on primitive multiplicative generator.
Date: 5 Apr 2000 10:59:32 -0700
In article <Y6RE4.95936$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> How would one start to attack a generator like so:
> [ M[i] = g*M[i-1] mod p; N[i] = M[i] dot-product b ]
You might look at the papers which cryptanalyze truncated
linear congruential generators. (M[i] = g*M[i-1]+a;
N[i] = some bits of M[i]) The similarities are striking.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: GSM A5/1 Encryption
Date: 5 Apr 2000 11:06:33 -0700
By modern cryptographic standards, A5/1 is a weak cipher, but I
think you were more interested in the practicalities of interception,
right?
What's your threat model? The curious average man on the street
who wanders down to Radio Shack to pick up a scanner, or a dedicated
knowleadgeable individual with some budget (e.g., $10k), or worse?
I think the GSM A5/1 cipher is likely to be secure against the former,
but it would be unwise to assume that it is secure against dedicated
attack by knowleadgeable individuals. Today, breaking GSM A5/1 appears
to be feasible for corporate espionage, but probably not for most curious
hobbyists. But that could well change 3--5 years down the road; in
this field, history teaches us that sophisticated attacks often have
a way of filtering down to the street in the form of black boxes that
require little or no sophistication to use.
If you are interested in intelligence agencies, I would be amazed if
they do not have the capability to eavesdrop on GSM traffic when they
want to.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: Wed, 05 Apr 2000 20:54:25 +0200
Johann Hibschman wrote:
>
> > Anyway, you don't seem to have specifically answered
> > my question of whether the sequence of all 0 has the same or
> > different entropy as an apparently random sequence in the experiment.
> > According to the above, the answer should be yes. Now consider
> > applying compression to both, then they are likely to get compressed
> > to different lengths. Would that fact conform to their having
> > the same entropy? Thanks.
>
> I don't know information entropy; I just know statistical mechanics
> entropy. There, yes, a sequence of all 0's has the same probability
> as any other sequence generated by a fully random 0 or 1 process.
>
> Its entropy, however, is undefined.
>
> In order to get an *entropy*, you have to lump individual sequences
> (usually called microstates) into categories (macrostates). The
> entropy is then proportional to the log of the number of microstates
> in a given macrostate.
>
> If, for example, you lumped all bit-sequences with the same number of
> ones into a macrostate, then the entropy of that all-0 sequence would
> be 0, since there is exactly 1 microstate corresponding to it.
>
> In short, you're asking the wrong question. Even for info theory, if
> you want to call something an entropy, it depends on the model you
> have for the communication channels and messages. For compression,
> you need to know what kinds of patterns count as "the same". You need
> a bigger model in there, somewhere, otherwise all you have is
> probability. That's all raw conjecture, though, since all I really
> know is the stat-mech entropy.
Sorry, I don't yet understand what you mean by 'lumping all the
sequences'? If the bit sequences (of length n) are obtained with
a perfect coin, do you mean lumping together 2^n different sequences
generated? Thru XOR-ing these? Could you elaborate a bit? Note, on
the other hand, that in a (crypto) application one may be using
only one single such sequence.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: GSM A5/1 Encryption
Date: 5 Apr 2000 11:08:31 -0700
By the way, if you're looking for hard information, the
one-stop shop is at JYA's Cryptome site:
http://jya.com/cryptout.htm#GSM
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: GSM A5/1 Encryption
Date: 5 Apr 2000 11:16:33 -0700
In article <8cbkbm$i12$[EMAIL PROTECTED]>,
Matt Linder <[EMAIL PROTECTED]> wrote:
> P.S. Some people imply that the NSA made it weak on purpose, but after
> doing some research it sounds like it would be difficult even for
> them.
Sorry to respond so many times, but I just saw this comment.
There are good reasons to be extremely suspicious that the A5
ciphers were deliberately weakened [*], but there is no way
to tell who is responsible for the weaknesses. Intelligence
agencies are the only ones with any obvious motive, but because
all information on the design process and the flaws of the A5
cipher have been kept deliberately secret, there is no
accountability and no way for outsiders to know for sure, at
least as things stand today. I can't offer anything more than
speculation on the source of the weaknesses. Sorry.
[*] Some evidence that they were deliberately weakened:
1. The leading 10 key bits are forced to zero, something
that has no effect other than to weaken the cipher.
2. The design of A5/2 cries for attention: either
it was purposefully and cleverly designed to make
shortcut attacks easy, or it is an amazing coincidence
that certain changes from A5/1 to A5/2 happened to be
at exactly the right spot to make these attacks easy.
If you were at the Crypto'99 rump session given by
Ian Goldberg, these comments might make more sense.
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
Subject: Re: Is this code crackable?
Date: Wed, 05 Apr 2000 19:03:50 GMT
On 5 Apr 2000 11:26:17 GMT, [EMAIL PROTECTED] (Richard Herring) wrote:
>In article <[EMAIL PROTECTED]>, 1198 ([EMAIL PROTECTED]) wrote:
>> If the key file can be safely sent to the other end without security problem
>> then there is no point of having any encrytion at all..
>
>Not so. You're assuming that a channel that is "safe" now will
>always be safe.
Or even more importantly, "still available".
The classic example is a spy out in the field -- he can carry with
him a one-time-pad that he acquired the last time he visited
Headquarters (at which time he was physically handed the OTP in
person by his boss, which is of course a "secure channel").
Once he's out in the field, that "hand a message to the recipient"
method is obviously no longer available. Now the spy has *no*
secure channels left to him at all. But the spy can use
the OTP (acquired via a secure channel that is now no longer
available) to send a message back to Headquarters via
unsecure channels and still be assured that the plaintext
can't fall into the wrong hands.
The utility of an OTP is that you only need to have a secure
channel ONCE, at any time prior to the time that you actually
need to send a secure message. You don't need a secure channel
at the exact time you might need to send a message.
--
"How strangely will the Tools of a Tyrant pervert the
plain Meaning of Words!"
--Samuel Adams (1722-1803), letter to John Pitts, January 21, 1776
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: Wed, 05 Apr 2000 21:16:06 +0200
Mok-Kong Shen wrote:
>
>
> Sorry, I don't yet understand what you mean by 'lumping all the
> sequences'? If the bit sequences (of length n) are obtained with
> a perfect coin, do you mean lumping together 2^n different sequences
> generated? Thru XOR-ing these? Could you elaborate a bit? Note, on
> the other hand, that in a (crypto) application one may be using
> only one single such sequence.
Sorry that I didn't carefully read your follow-up. But it seems
to be disputable why you do lumping based on the number of 1's (or
equivalently 0's). The special sequence 01010101....... has a
very regular pattern, while anothers with the same number of 1's
may not. I am not sure that disregarding such properties wouldn't
mean neglecting some essential crypto-relavant aspects.
One way that I could think of (though practically not realizable)
is to take the Kolmogorov complexity to measure the information
content instead of the entropy or other concepts that could be
traced back to Shannon. But I don't know whether this is o.k. from
the standpoint of crypto.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: GSM A5/1 Encryption
Date: 5 Apr 2000 11:32:32 -0700
In article <8cc3hq$[EMAIL PROTECTED]>, Gregory G Rose <[EMAIL PROTECTED]> wrote:
> Biryukov/Shamir/Wagner have the combined technique
> that Tom mentioned, however it assumes *known
> plaintext*. While I agree that it means A5/1 is
> cryptographically broken, known plaintext for a
> voice call is pretty hard to arrange, what with
> vocoder compression and stuff happening to the
> signal. [...] It is this difficulty which
> accounts for the crypto people saying it is broken
> and the telephone people saying it isn't.
I agree strongly with Greg Rose. If you care about
practical impact, you should be very careful about
the assumptions that cryptographers often make. I
thought maybe I could comment a bit further on the
topic, though.
Probably only the telephone people know for sure
whether the necessary known plaintext can be obtained
in practice, but unfortunately, many of them in the
GSM industry have an interest in persuading people
that the system is secure, so it's not obvious how
to take some of the statements from the GSM folks.
Anyway, from the information I've received, it
looks like the required known plaintext may indeed
be available to the cryptanalyst. Although it is
hard to make any definitive statements, as far as
I can tell, yes, the attacks do seem as though
they may be workable in real life.
The key is to look at silence frames. I'm told
that they are often encoded as some constant: every
frame of silence in the call gets encoded to the
same thing. I don't personally know whether this
is correct or not, but if it is, it makes it look
like required known plaintext may be available.
The rest of my comments will be predicated on the
correctness of this assumption.
The other thing one needs to know is that the
two directions of the call are encoded independently
(in different frames). Since parties to a
conversation usually speak one at a time, this
means we can expect at least half of the frames
to be silence frames.
If we take the A5/2 attack, this property alone
is enough to make it work. The cryptanalyst needs
only to know the xor of some pair of frames, and
the xor of two silence frames is zero, so the obvious
thing to do is to try pairs of frames at random
(hoping that they are both silence frames, and
knowing that the attack will succeed when this
is the case) until you succeed. This guessing does
not increase the complexity of the attack very much,
since silence frames are common.
I haven't looked at the A5/1 attacks in detail,
but it also looks as if they can be made to work
using just this fact about silence frames.
Certainly if the encoding of a silence frame
is constant *and known to the attacker*, this
gives the attacker the necessary known text.
(Just look for a stretch of silence in the
conversation, derive some known plaintext, try
the attack, and if the attack fails, try again;
once you correctly identify a stretch of
silence in the conversation, you'll recover
the correct key.) Even in the case where the
silence frame encoding is constant but unknown
to the attacker, I *think* it may also be
possible to modify the A5/1 attacks to work
under this model.
This is all very sketchy, because I'm not a
telephone guy, and I just don't know everything
that one would need to know to make an assessment.
This is also all from memory, so I could be
misremembering some details here and there.
But, if I had to place bets, I'd bet in an
instant that some of the attacks can be mounted
in real life, if you just give them a try.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Keeping numbers small in RSA
Date: Wed, 05 Apr 2000 19:09:14 GMT
In article <8cb73q$3me$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> I am having some trouble calculating result = A*B mod n as part of a
> modular exponentiation. The tempory value for A*B gets too big too
> store before the modular reduction. I am limited to 32 bit storage
for
> the tempory register.
See the section in Knuth, Vol 2. on multi-precision arithmetic.
You have two choices: use a double length register to store the
temporary double length product or use a radix that is half the
word size.
What language are you using? Many C compilers support _longlong.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Keeping numbers small in RSA
Date: Wed, 05 Apr 2000 19:11:24 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> You can use the repeated squaring technique based on the equation:
> a**b mod n = ( ... ((a^2 mod n) ^2 mod n) ..etc.
Please re-read the question. This was not what was asked.
See my earlier reply.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Keeping numbers small in RSA
Date: Wed, 05 Apr 2000 19:14:07 GMT
In article <[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> > I am having some trouble calculating result = A*B mod n as part of a
> > modular exponentiation. The tempory value for A*B gets too big too
> > store before the modular reduction. I am limited to 32 bit storage
for
> > the tempory register.
> > Can anybody suggest a technique(s) or algorithm to reduce these
> > numbers, ideally to allow large A and B usage.
> > Thanks in advance.
>
> Use a large number library such as MPI :-)
Please re-read the question. The poster did not ask for the name of
a software package that would solve his problem, he asked for a
"technique(s) or algorithm "
Typical internet reply. Poster asks for "A" and everyone answers "B".
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: Wed, 05 Apr 2000 19:11:12 GMT
Mok-Kong Shen wrote:
[...]
> If I understand correctly, then your sentence should read:
> The information in a particular message text, measured in
> entropy, is a function of the probability of occurence of
> that text
Fair enough.
> Anyway, you don't seem to have specifically answered
> my question of whether the sequence of all 0 has the same or
> different entropy as an apparently random sequence in the experiment.
Messages with the same probability carry the same amount of
information.
> According to the above, the answer should be yes. Now consider
> applying compression to both, then they are likely to get compressed
> to different lengths.
No. The identity function is an optimal compressor for the
given language (all n-bit strings equally likely). In fact,
if shorter strings are more likely than longer strings, then
any compression function for which some string has a shorter
image must have a worse expected compression ratio than the
identity function.
Arbitrary compression functions will produce differing
relative image lengths. For any finite string there's some
compressor that compresses it to one bit.
> Would that fact conform to their having
> the same entropy?
The actual situation is consistent.
My previous posts answers the question of why a conventional
compression algorithm, which is not optimal for the given
language, does so much better on the sample string.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Key exchange using Secret Key Encryption
Date: Wed, 05 Apr 2000 19:14:59 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>
>
> zapzing wrote:
> >
> > Why in the world would two complete strangers
> > want to exchange encrypted information ???
> > What could they possibly have to say to
> > each other?
> > *************************
> > And why can't public key
> > encryption be used? It seems to
> > be the *only* solution to this
> > (rather strange) problem.
> ---------------------
> The problem is not strange, not long ago I read about a Baptist
> priest who published his PGP key and people could send him
> messages in confidence.
> (Please don't think that I advertise it, I'm an atheist)
> Best wishes BNK
> -----------------------------
Yes, you have to watch out for those
Baptist *priests*. What kind of
messages was he getting?
Confessions? Do you think there
would be a market in that?
(in a secular, theraputic
sort of way)
--
Do as thou thinkest best.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: lattice based cryptosystems
Date: 5 Apr 2000 19:22:55 GMT
Hi,
I'm wondering which lattice based cryptosystems are out there. So far
I know of
* NTRU (not explicitly related to any of the "normal" lattice problems,
but close enough to fit)
* Goldwasser, Goldreich, Halevi (broken)
* Ajtai-Dwork (broken)
* Cai-Cusick
* R. Fischlin and JP Seifert "Tensor-based trapdoors for CVP"
* McEliece (using the analogy between codewords and lattices...)
anything else?
Thanks much,
-David Molnar
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Key exchange using Secret Key Encryption
Date: Wed, 05 Apr 2000 19:17:44 GMT
In article <8c9j60$9oh$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> In article <8c3psb$alm$[EMAIL PROTECTED]>,
> zapzing <[EMAIL PROTECTED]> wrote:
> > Why in the world would two complete strangers
> > want to exchange encrypted information ???
> > What could they possibly have to say to
> > each other? Surely you are not thinking
> > of starting a secret cabal with a
> > complete stranger. that is not recommended.
> >
> > And why can't public key
> > encryption be used? It seems to
> > be the *only* solution to this
> > (rather strange) problem.
>
> Ever heard of e-commerce? Two complete strangers (customer and vendor)
> will definately want to exchange encrypted information such as billing
> info, addresses etc. There are plenty of other examples.
>
> Public key encryption is too slow to be used for encrypting messages
or
> streams. Instead, you use it to encrypt the symmetric keys used for
the
> actual session encryption, and for creating signatures.
>
> Public key encryption does not solve the problem here though, since
you
> still need a secure way of transfering the public key. (If someone
> claims to be Alice and gives me a public key, how do I know it really
is
> Alice's and not Mallot's?)
>
You know, I really do have my
doubts about e-commerce, I mean
it's like just floating your
money out onto the sea of the
internet, and hoping someone send
you back something you want.
IMHO.
--
Do as thou thinkest best.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Even more crypto humor !
Date: Wed, 05 Apr 2000 19:22:22 GMT
[I'm putting crypto humor here so that the last
thread doesn't get too long.]
What did the ciphertext reveal as the
cryptographer kept giving it mod 2 addition?
A: I feel xor.
The cryptographer: Ugghh, I don't feel so well
either. I think I've had one *byte* too many.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: Wed, 05 Apr 2000 13:35:29 -0600
Reply-To: [EMAIL PROTECTED]
Mok-Kong Shen wrote:
> Tony T. Warnock wrote:
> >
> > >
> > > > It's the process that is "random" not the sequence that comes from the
> > > > process. If the process is the usual "fair coin toss" then everything is OK.
> > > > Probability (in this sense) is a priori. One doesn't get 40 heads in a row
> > > > from an unbiased coin.
> > >
> > > I don't understand your last sentence. That probability is 2^(-40),
> > > isn't it?
> > >
> > > M. K. Shen
> >
> > Yes. Really small. The point is, in practice one does not see things this rare.
> >
> > On a related issue. Not only will a team (finite) of monkeys not type the works of
> > Shakespeare, they won't even get the first 50 digits of pi. A team of screen
> > writers could come up with "Romeo and Ethel, the Pirates Daughter" perhaps.
>
> But note that any other bit pattern has exactly the same (small)
> probability!
Exactly!
One must not confuse symmetry (or interest) with probability. All zeros is interesting
because of the way it combines with other numbers, not because of its probability.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: generator of Zp
Date: Wed, 05 Apr 2000 19:30:33 GMT
In article <[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
<snip>
> If your prime is p- strong, just randomly try 'g' values to get
>
> g^p-1 = 1 (mod p)
> g^(p-1)/2 != 1 (mod p)
>
> Any 'g' that satisfies those too conditions is a generator mod p.
^^^
If you want your replies to be professional, may I suggest that you
proofread your posts?
And your reply is wrong. (Hint: there is a value of g
such that g^(p-1) = 1 mod p, and g^q = -1 mod p).
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: generator of Zp
Date: Wed, 05 Apr 2000 19:25:47 GMT
In article <[EMAIL PROTECTED]>,
"Goi Bok Min" <[EMAIL PROTECTED]> wrote:
> Help... can some one help me on this?
>
> recently, i came across the Chaum_van Heijst_Pfitzmann Hash Function
which
> basically based on discrete logarithm problem.
> The algorithm is as following:
> Let p =2*q+1 be a prime such that q is prime.
> Let a and b be two primitive elements of Zp - Group p.
A technical nitpick:
There are two separate cyclic groups mod p -- an additive one and
a multiplicative one. Both have primitve elements. I'm sure you mean
the latter, but it doesn't hurt to be specific.
>
> now, my problems are:
> 1) how can i calculate the "a" and "b" - the primitive elements
given
> primary "p"?
Your use of the word "the", as in "the primitive elements" is
incorrect as it implies that the choice is unique.
Elements are primitive iff their order is p-1. So randomly choose
a and b and check that there order is p-1. Lagrange's theorem says
that the only possible orders of elements must divide p-1, and
the divisors of p-1 are all known, so checking the order is easy.
>
> 2) supposedly, the order of generator is (p-1) - is it always true?
This follows from the definition of generator.
> so that a^(p-1) mod p = 1.
> but why a^q = -1 = p-1 (mod p) ?
Because if a^q = +1 mod p, then a would have order q, not p-1.
Select h at random. The possible orders for h are 2, q and p-1.
Just check them.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
