Cryptography-Digest Digest #926, Volume #9 Thu, 22 Jul 99 17:13:03 EDT
Contents:
Re: Q: Does ElGamal require that (p-1)/2 is also prime like DH? (Doug Stell)
Re: randomness of powerball, was something about one time pads (John Briggs)
Re: randomness of powerball, was something about one time pads (John Briggs)
PKZIP Cipher - What if ? ("jd_bertron")
Re: RSA public key ([EMAIL PROTECTED])
Re: publuc key (Medical Electronics Lab)
Re: randomness of powerball, was something about one time pads ("karl malbrain")
Re: Good Book on Linear Algebra (Michael Slass)
Re: obliterating written passwords (Lincoln Yeoh)
Re: Traffic Analysis (Lincoln Yeoh)
ElGamal in Applied Cryptography ("Jonathan 'Wolf' Rentzsch")
Re: Traffic Analysis (David A Molnar)
Re: What the hell is XOR? ("karl malbrain")
What the hell is XOR? ("Spud")
Re: Xor Redundancies (JPeschel)
Re: What the hell is XOR? (Michael Slass)
Re: What the hell is XOR? (Michael Slass)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Doug Stell)
Subject: Re: Q: Does ElGamal require that (p-1)/2 is also prime like DH?
Date: Thu, 22 Jul 1999 14:57:30 GMT
On Thu, 22 Jul 1999 07:21:51 GMT, [EMAIL PROTECTED] (Hartmut Schroeder)
wrote:
>while reading "Applied Cryptography" it is mentioned that
>ElGamal and Diffie-Hellman are based on the same mathematical Problem.
>It is also said that prime p you choose for Diffie-Hellman
>has also to be a prime when you compute (p-1)/2.
Bruce does not say that the prime "has" to be of that form, but
"should" be for better security.
The difficulty of doing a discrete log is related to doing a discrete
log on each of the factors of p-1 and combining the results by the
Chinese Remainder Theorem. This, in turn, is dominated by the largest
of the prime factors of p-1. The suggested choice of factors gurantees
that the largest factor is a large as possible,
>It would take a while to find great Primes that meet this criteria.
It does. Primes are constructed. Find prime q and then test to see if
2q+1 is also a prime.
>The Book seem nothing to say in the ElGamal Section that this
>is also true for prime p when using ElGamal.
My understanding is that it is probably true for all algorithms based
on the discrete log problem.
------------------------------
From: [EMAIL PROTECTED] (John Briggs)
Subject: Re: randomness of powerball, was something about one time pads
Date: 22 Jul 99 12:00:04 -0400
In article <[EMAIL PROTECTED]>, "Doug Gwyn (ISTD/CNS) <gwyn>" <[EMAIL PROTECTED]>
writes:
> [EMAIL PROTECTED] wrote:
>> Mok Kong Shen wrote:
>> > Maybe I misunderstood. But doesn't the issue call into memory
>> > the case where an ideal RNG can generate a sequence of 0's of
>> > arbitrary length? There is a non-zero chance that the time point
>> > of (huge) win is at infinity.
>
> Actually the probability of that is zero.
>
>> There is no huge win anywhere. The rules stated that bet doubling
>> follows a loss. Following a win the bet reverts to one unit.
>
> But, every time you win a play, you have a net gain of $1 since the
> last time you won (or began play). The wins may not be huge, but
> if you accumulate enough of them you should become very wealthy.
>
> So far, I haven't seen anyone in sci.crypt come close to identifying
> the flaw in this strategy.
The flaw? There are a couple, depending on what kind of flaw you're after.
1. It's sub-optimal. (Optimizing for minimum number of bets).
If you want to win a million quatloos, one optimal strategy is to:
Bet a million quatloos. If you win, you're done.
Bet two million quatloos. If you win, you're done.
Bet four million quatloos. If you win, you're done.
etc.
Obviously, no strategy can get you your million quatloos unless you
first win a bet. And don't give me that stuff about negative bets.
This strategy ensures that your first win will net you the requisite
sum. Thus this strategy is optimal.
2. To provide the absolute guarantee of success, you've got to find
someone willing to accept arbitrarily large markers and to
fade arbitrarily large bets. This is the important real world flaw.
3. If you consider that the bet is fair or worse, you've got the seeming
paradox that there is a strategy that provides a guaranteed win
but there is also the assurance that the expected value for any
such (finite anyway) strategy is zero at best. The resolution
of this is to note that in the limit there is a vanishingly small
probability of a crushingly huge deficit. The product of these two
is precisely enough to cover the disrepancy in expected value.
If you want to measure this strategy, one good way would be to
put your instruments in after the n'th bet rather than after
the n'th cycle since you've got only a statistical guarantee
that any particular cycle will ever end.
If you want to take the expected value of this potentially
infinite game, you've got to define that expected value first.
There are at least three ways to define it. You can sum over
all non-zero probabilities. You can take the limit of
all the finite leading games. Or you can sum over both zero
and non-zero probabilities in some way that is sure to be
fascinating.
You could perhaps label this philosophically as the difference
between "will happen" and "will happen with probability 1".
On the other hand, if you've found an infinite banker to cover
your markers, an infinite house to fade your bets, if you've
got unbounded time to play and if you're willing to accept
"probability 1" as a surrogate for "can't fail" then there is no
flaw. Go for it.
John Briggs [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (John Briggs)
Subject: Re: randomness of powerball, was something about one time pads
Date: 22 Jul 99 12:08:04 -0400
In article <[EMAIL PROTECTED]>, John Myre <[EMAIL PROTECTED]> writes:
>
> Patrick Juola wrote:
>> In article <[EMAIL PROTECTED]>,
>> Alan Braggins <[EMAIL PROTECTED]> wrote:
> <snip>
>> >I'm still not sure about the case where he doesn't always open a door,
>> >and sometimes opens a door when it will help you, but is more likely
>> >to open a door if you have already chosen the prize.
>>
>> Surely that's a mixed case and depends on the exact percentages.
>> Where *did* I put my game theory text? 8-)
>>
>> -kitten
>
> OK, I'll bite: what is the optimal *host* strategy?
Never open a door.
This yields a 33% win rate for the player. If the host had a better
strategy then the player could adopt a "never switch" strategy and get
a 33% win rate. So 33% is as good as the host can do and "never open"
is thus optimal.
John Briggs [EMAIL PROTECTED]
------------------------------
From: "jd_bertron" <[EMAIL PROTECTED]>
Subject: PKZIP Cipher - What if ?
Date: Thu, 22 Jul 1999 16:15:35 GMT
Hi all,
For those of you who understand the Biham-Kocher attack on the PKZip
stream cipher, I have this question:
What would it take to modify the update-keys() function to render the
attack NP-Hard ?
Here is a reminder of the algorithm:
key0 <- crc32(key0,char)
key1 <- [(key1 + LSB(key0)) * 134775813+1 ] mod 2^32
key2 <- crc32(key2,MSB(key1))
temp <- LSW( key2 | 3 )
key3 <- LSB((temp * (temp xor 1)) >> 8)
For more info on the attack, please read the paper:
http://www.unix-ag.uni-kl.de/~conrad/krypto/pkcrack.html
--
Posted via Talkway - http://www.talkway.com
Exchange ideas on practically anything (tm).
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RSA public key
Date: Thu, 22 Jul 1999 16:45:56 GMT
In article <7n6qi7$ils$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Thomas Pornin) wrote:
> According to vincent <[EMAIL PROTECTED]>:
> > If I always take the same very small exponent for the public key
[...]
> > do I limit the number of private key which will result from this
> > computation ?
>
> Obviously, yes, but that is not a problem, since you will still get a
> valid private key for each pair of primes (p, q). For 1024-bit public
> keys, this still means about 2^1006 possible keys, which is *huge*.
>
> > Is it weak to do so, because obviously it would make the encryption
> > faster (as well as the key generation) ?
>
> If you encrypt three times a message with three different public
modulus
> but with the public exponent 3, an eavesdropper might guess the
message
> (not the public key) from the three encryption.
>
How would you guess the message?
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: publuc key
Date: Thu, 22 Jul 1999 12:56:58 -0500
John Xiao wrote:
>
> Can anyone show me a sample of public key?
> I know how the key works conceptually, but just can't get into detail.
> Thanks.
This is an example of how to do public key using ECC. There are
a lot of books that get into much more detail for just this form.
There are several other forms of PK, but I'll let the other guys
and gals explain 'em.
Step 1: choose public parameters. These parameters determine the
level of security: field size (either GF(p) or GF(2^n)), a curve
and a base point (B) on the curve. Suppose I choose Gf(2^n) with
n=162, then I pick a curve (formula is y^2 + xy = x^3 + b so I pick
b), and find some random point (X, Y) on the curve to be my base
point. [If I know the order of the curve, I multiply the random
point by the cofactor of the curve to ensure the base point I use
has the order of the largest prime in the order of the curve.]
Step 2: choose private parameters and generate public keys.
Each side picks their own private key. A nice way to do this is
to hash a pass phrase. For our purpose, a 160 bit hash like SHA-1
will work well. So let Alice have Ka and Bob pick Kb. Alice
computes her public key as Pa = Ka*B and Bob computes his public
key as Kb*B = Pb (the multiplication is done over the curve).
Alice sends Bob Pa, and Bob sends Alice Pb.
Step 3: Generate a shared secret. This step has many possible
protocols. The simplest is Diffie-Hellman, so I'll describe it.
Check out ElGamal and MQV for more advanced methods which help
thwart man-in-the-middle attacks. Bob computes his shared secret
as Kb*Pa = S and Alice computes her shared secret as S = Ka*Pb.
Both of them have the same secret point because S = Ka*Kb*B.
Only the X component of S is used, the Y component can easily
be found from X, so there's no security in it.
The shared secret can now be used with a symmetric algorithm
so Bob and Alice can exchange information securely.
That's a touch more detail. But there is a lot more math involved
as well as a lot of decisions you can make at every step. And it's
only one of many possible methods.
Patience, persistence, truth,
Dr. mike
------------------------------
Reply-To: "karl malbrain" <[EMAIL PROTECTED]>
From: "karl malbrain" <[EMAIL PROTECTED]>
Subject: Re: randomness of powerball, was something about one time pads
Date: Thu, 22 Jul 1999 11:05:18 -0700
John Briggs <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <[EMAIL PROTECTED]>, John Myre <[EMAIL PROTECTED]>
writes:
> >
> > OK, I'll bite: what is the optimal *host* strategy?
>
> Never open a door.
>
> This yields a 33% win rate for the player. If the host had a better
> strategy then the player could adopt a "never switch" strategy and get
> a 33% win rate. So 33% is as good as the host can do and "never open"
> is thus optimal.
>
The other end of the <<optimum>> never-switch player 33% strategy is the
<<optimum>> host 33% strategy:
open a door when the player picks the prize, plus randomly when he doesn't.
The host opens a door 2/3 the time, but maintains the 33% payout ratio.
Karl M
------------------------------
From: Michael Slass <[EMAIL PROTECTED]>
Subject: Re: Good Book on Linear Algebra
Date: Thu, 22 Jul 1999 10:33:38 -0700
The book I used for linear algebra in my freshman undergraduate year was
by Gilbert Strang, and was titled something like _Introduction to Linear
Algebra_. Probably the best math text I've ever used.
Mike
[EMAIL PROTECTED] wrote:
> I was visiting Windsor this week and I stopped by a bookstore. They
> happen to have this book so I picked it up. It's
>
> Linear Algebra, 2nd Edition, Stephen H. Friedberg, Arnold J. Insel and
> Lawrence E. Spence.
>
> It's a first year intro book into Linear Algebra which I find quite
> informative. If anyone wants to learn about this they should try to
> find this book.
>
> ISBN 0-13-537102-3
>
> Tom
> --
> PGP key is at:
> 'http://mypage.goplay.com/tomstdenis/key.pgp'.
> Free PRNG C++ lib:
> 'http://mypage.goplay.com/tomstdenis/prng.html'.
>
> Sent via Deja.com http://www.deja.com/
> Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Lincoln Yeoh)
Subject: Re: obliterating written passwords
Date: Thu, 22 Jul 1999 18:09:50 GMT
Reply-To: [EMAIL PROTECTED]
On Sun, 18 Jul 1999 07:15:44 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>Lincoln Yeoh wrote:
>> Burn it and flush it down the toilet.
>
>After eating it, as pointed out elsewhere in this thread.
Nah, most people don't like eating their words.
I figure they wouldn't like passing their passwords either :).
Link.
****************************
Reply to: @Spam to
lyeoh at @[EMAIL PROTECTED]
pop.jaring.my @
*******************************
------------------------------
From: [EMAIL PROTECTED] (Lincoln Yeoh)
Subject: Re: Traffic Analysis
Date: Thu, 22 Jul 1999 18:24:44 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 19 Jul 1999 15:41:36 GMT, Roger Carbol <[EMAIL PROTECTED]> wrote:
>It seems like I haven't read very much in this newsgroup about
>traffic analysis. It seems like an avenue of attack which is often
>neglected by both the White Hats and the Black Hats.
>
>Has anyone set up a system (that they can talk about) which regularly
>sent out a lot of noise? Any interesting phenomena arise?
I believe we call it Usenet ;).
Maybe someone is exchanging top secrets here in some kind of code via lots
of conversations. Who knows, it may explain some people's speeling
mistakes...
Instead of sending noise one could send the Usenet newsfeed processed the
same way as the real messages would be.
I figure "real" noise may be more easily differentiated from real messages.
Of course sending the Usenet feed may having known plaintext. But I'm sure
things can be arranged to prevent that.
Link.
****************************
Reply to: @Spam to
lyeoh at @[EMAIL PROTECTED]
pop.jaring.my @
*******************************
------------------------------
From: "Jonathan 'Wolf' Rentzsch" <[EMAIL PROTECTED]>
Subject: ElGamal in Applied Cryptography
Date: 22 Jul 1999 19:09:05 -0000
Greetings,
I'm working off of Bruce Schneier's _Applied Cryptography_, second
edition, sixth printing. I am attempting to implement ElGamal public key
encryption, but have run into difficulties. Specifically, when I follow
the steps outlined in the book (pages 476 through 478), I can't recover
the encrypted message.
The following C function implements an ElGamal encryption and decryption.
I chose small numbers that would fit into a 32-bit long, so you should
just be able to copy and paste this code into a C compiler and run it.
Where am I going wrong? How would you fix this function so M2 is set to M?
void ElGamal()
{
// "choose a prime, p"
long p = 23;
// "and two random numbers, g and x, such that both g and x are less than p"
long g = 4, x = 3;
// "to encrypt message M,"
long M = 9;
// "first choose random k, such that k is relatively prime to p - 1"
long k = 5;
long y, a, b, M2;
// "To generate key pair...calculate:
// y = g^x mod p"
y = exp( g, x ) % p; // y == 18
// "To encrypt...compute:
// a = g^k mod p
// b = y^k M mod p"
a = exp( g, k ) % p; // a == 12
b = ( exp( y, k ) * M ) % p; // b == 4
// "The pair, a and b, is the ciphertext. To decrypt a and b compute:
// M = b/a^x mod p"
M2 = b / ( exp( a, x ) % p ); // M2 == 1
// The following assertion breaks because 9 != 1.
assert( M == M2 );
}
// Simple inefficient exponent. returns a^x.
long exp( long a, long x )
{
long result = a;
for( --x; x; --x )
result *= a;
return( result );
}
......................................................
Jonathan 'Wolf' Rentzsch jon at redshed dot net
Red Shed Software http://redshed.net (847) 584-7465
PGP: B2AF 1A09 F881 EBDE C9D6 C4D2 C04F A3C0 3EC5 D5F2
"Don't do what 'Johnny Don't' does!"
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Traffic Analysis
Date: 22 Jul 1999 19:37:01 GMT
Lincoln Yeoh <[EMAIL PROTECTED]> wrote:
> Maybe someone is exchanging top secrets here in some kind of code via lots
> of conversations. Who knows, it may explain some people's speeling
> mistakes...
Shades of BlackNet. Except instead of keeping to itself in
alt.anonymous.messages, spread throughout all of usenet like veins in blue
cheese! A creeping cancer, raising tentacles to...uh, no.
Slightly more seriously, it will be interesting to see what uses
subliminal channels are put to when signing a message becomes more
widespread. Wonder if people will demand proof of subliminal-free
signatures?
Oh, and if the idea of rendering a signature into a picture (was on Ian
Goldberg and Raph Levien's home pages, can't find it now) catches on, how
long before people start drawing conclusions from the "shape" of your
posting? Then we can have crypto-"palmistry"!
-David Molnar
------------------------------
Reply-To: "karl malbrain" <[EMAIL PROTECTED]>
From: "karl malbrain" <[EMAIL PROTECTED]>
Subject: Re: What the hell is XOR?
Date: Thu, 22 Jul 1999 13:11:35 -0700
Spud <[EMAIL PROTECTED]> wrote in message
news:7n7r3j$538$[EMAIL PROTECTED]...
> I was reading "Applied Cryptography" by Bruce Schneier and I really don't
> get the XOR function. Help, please! Thanks.
>
XOR is the <<half-add>> register operation. It adds the bits of the
registers, ignoring carries. The boolean function is <<exclusive-or>> with
the truth table (^ is the C operator for XOR):
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
Karl M
------------------------------
From: "Spud" <[EMAIL PROTECTED]>
Subject: What the hell is XOR?
Date: Thu, 22 Jul 1999 12:21:22 -0700
I was reading "Applied Cryptography" by Bruce Schneier and I really don't
get the XOR function. Help, please! Thanks.
PS -- I'm not a computer newbie so you don't have to dilute any
explainations with "easy words".
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: Xor Redundancies
Date: 22 Jul 1999 20:34:43 GMT
>[EMAIL PROTECTED] writes:
>Alot of crypto utilities out their are crap. I should know when I was
>12 I wrote 'Zcrypt' which was a really fast autokey cipher. It worked
>in my view but I didn't know any better. A lot of these peoples are
>just ignorant and don't care.
>
Yes, the UBE98 vendor asked for advice in sci.crypt, and then
ignored it. He chose to "protect" his program from disassembly.
Apparently, though, he knew a debuggger could break UBE in
a few seconds.
>I cought up with the author of 'Absolute Security' which is repeated
>OTP cipher. Basically you take a 'secret' random file and add it to
>the message. You share the file so you can send 100s of messages with
>the same file. However I tried to point out that re-using the same
>keyfile would lead to all sorts of attacks (I proposed three different
>attacks I think...). He is still pretty sure of himself. Oh well...
>
That's the same company that sells WinXFiles (broken by Casimir)
ins't it?.
>Basically if I can't see the source I won't get the program. A lot
>of 'secure' programs are just simple RNGs that are linear or
>tractable. Another program 'The Vault' uses a totally secure hidden
>method with 20 bit keys... :) etc...etc...
>
Yup, most in this newsgroup won't use a crypto program unless
they can see the source code. Unfortunately, the people who
actually purchase crypto programs don't know enough to ask to
see the source.
>BTW where is the snake-oil faq and is it upto date?
>
The snake-oil faq is at Matt Curtin's site:
http://www.interhack.net/people/cmcurtin/snake-oil-faq.html
last revised April 98.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Michael Slass <[EMAIL PROTECTED]>
Subject: Re: What the hell is XOR?
Date: Thu, 22 Jul 1999 13:42:19 -0700
Spud:
XOR is eXclusive OR
Like, OR, but FALSE if both bits are TRUE so..
^ is a symbol for XOR
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
XOR-ing two numbers together is just XORing each of their corresponding bits
in turn so
in binary:
25 = 00011001
50 = 00110010
so 25^50 =
00011001 = 25
^ 00110010 = 50
================
00101011 = 43
Ja Love,
-Mike
Spud wrote:
> I was reading "Applied Cryptography" by Bruce Schneier and I really don't
> get the XOR function. Help, please! Thanks.
>
> PS -- I'm not a computer newbie so you don't have to dilute any
> explainations with "easy words".
------------------------------
From: Michael Slass <[EMAIL PROTECTED]>
Subject: Re: What the hell is XOR?
Date: Thu, 22 Jul 1999 13:47:42 -0700
Spud:
Sorry about the last posting; I got messed up by the variable-width font in my
message composition window. This should look right.
-Mike
Spud:
XOR is eXclusive OR
Like, OR, but FALSE if both bits are TRUE so..
^ is a symbol for XOR
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
XOR-ing two numbers together is just XORing each of their corresponding bits
in turn so
in binary:
25 = 00011001
50 = 00110010
so 25^50 =
00011001 = 25
^ 00110010 = 50
================
00101011 = 43
Ja Love,
-Mike
>
------------------------------
** 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
******************************
