Cryptography-Digest Digest #495, Volume #11 Wed, 5 Apr 00 14:13:01 EDT
Contents:
Re: Q: Entropy (Mok-Kong Shen)
Re: BBS again ("Trevor L. Jackson, III")
Re: Knapsack Problems? (David A Molnar)
Re: help needed : long number arithmetic packages (David A Molnar)
Re: summing hashes is not safe? (David A. Wagner)
Re: Sunday People 26/3/2000: "FORGET YOUR PASSWORD... END UP IN JAIL" ("A. Little")
Re: time-lock crypto (David A. Wagner)
Re: Massey-Omura protocol & ECC (Mike Rosing)
Re: Q: Entropy ("Tony T. Warnock")
Re: Building a stream cipher? (newbie Question) (Mike Rosing)
Re: help needed : long number arithmetic packages (Mike Rosing)
Re: Public|Private key cryptography? (Mike Rosing)
Re: Download Random Number Generator from Ciphile Software (Lincoln Yeoh)
Re: OAP-L3: Semester 1 / Class #1 All are invited. (Xcott Craver)
Re: RNG based on Blum Blum Shub (Mok-Kong Shen)
Re: Q: Entropy (Mok-Kong Shen)
Re: MARKKU AND INTEL BUSINESS ... $ (Eric Chomko)
Re: Is this code crackable? (JimD)
Re: Extended Euclidean Algo (Mok-Kong Shen)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: Wed, 05 Apr 2000 18:48:19 +0200
Tony T. Warnock wrote:
>
> Mok-Kong Shen wrote:
> > After reflecting a bit more about tossing a perfect coin, I
> > believe there is a paradox whose explanation I don't yet know.
> > If a perfect coin is tossed n times, it generates a bit
> > sequence of length n. How much entropy should I ascribe to
> > that sequence? Note that the result is one of the binary numbers
> > in the interval 0 to 2^n-1. Each of these numbers has an equal
> > chance of turning up in my experiment. Suppose by chance I get
> > the number 0, i.e. all n bits are 0. Should I still consider the
> > sequence to have some entropy and, in particular, the same
> > entropy as a sequence having an apparently fairly random pattern
> > of 0 and 1? Thanks.
>
> 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
------------------------------
Date: Wed, 05 Apr 2000 13:06:19 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: BBS again
[EMAIL PROTECTED] wrote:
> All I wanna do is a blum blum shub with a
> boom boom; a dub a dee doo bah dee dooo, do
> wah !
Who put the Blum in ...
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Knapsack Problems?
Date: 5 Apr 2000 16:33:05 GMT
Simon Johnson <[EMAIL PROTECTED]> wrote:
> I have a hasy memory of someone saying that the non-superceding knap-sacks
> where breakable. Is this statement correct? If yes, then how?
In general, the knapsack problem is NP-complete. This means if you could
solve it "in general" (for some notion of "in general"), you could
solve any other NP problem.
Unfortunately, only a restricted subset of knapsack problems are actually
used for public key cryptography. These tend to consist of superincreasing
knapsacks which are then modified in order to obtain a related
non-superincreasing knapsack. Breaking cryptosystems which use these
very special subset of all knapsacks has historically proven to be easy.
An overview of the topic is in
The rise and fall of knapsack cryptosystems, A. M. Odlyzko, pp. 75-88 in
Cryptology and Computational Number Theory, C. Pomerance (ed.), Am. Math.
Soc., Proc. Symp. Appl. Math. #42 (1990).
http://www.research.att.com/~amo/doc/arch/knapsack.survey.ps
It does not cover the cryptanalysis of the Chor-Rivest knapsack, which for
some time had been considered secure. For that you'll have to look at
"Cryptanalysis of the Chor-Rivest Cryptosystem"
http://www.dmi.ens.fr/~vaudenay/pub.html#Vau98h
By the way, has anyone written a "rise and fall of lattice cryptosystems"
article yet? or is it too early to tell if the "fall" has happened?
Thanks,
-David Molnar
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: help needed : long number arithmetic packages
Date: 5 Apr 2000 16:39:30 GMT
[EMAIL PROTECTED] wrote:
> hello all,
> Well as a part of my finishing project at university
> i must use a long number arithmetic package.
Have you considered GMP ?
http://www.swox.com/gmp/
Do you have special requirements for your package - e.g. do you need
crypto algorithms, lattice basis reduction, weird and wooly algebraic
number theory stuff, etc.. or do you just need a big number package?
Thanks,
-David
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: summing hashes is not safe?
Date: 5 Apr 2000 09:20:34 -0700
In article <8c9p6f$g08$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> Just came across some code in which multiple (100's) 20 byte message-
> digests are summed into one 24 byte sum as a hash for the complete
> batch.
Are the inputs to each of the hashes independent? i.e.,
output = H(x_1)+H(x_2)+...+H(x_n) mod 2^160?
If so, it's not very secure. (As other have said, subset
sum will let you find collisions; and I think there are
other techniques.)
If that's what you're thinking of using, re-consider.
------------------------------
From: "A. Little" <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,uk.politics.censorship
Subject: Re: Sunday People 26/3/2000: "FORGET YOUR PASSWORD... END UP IN JAIL"
Date: Wed, 5 Apr 2000 11:20:12 +0100
In article <8c84su$mni$[EMAIL PROTECTED]>, [EMAIL PROTECTED] writes
>In uk.politics.censorship PJS <[EMAIL PROTECTED]> wrote:
>> -----------
>> Given that it's a contest of us vs. the party whips, it's probably a waste
>> of time.
>
>Personally I'd think that if enough MP's got letters from their
>consituents asking that they vote against the legislation then they
>might start to take action
Perhaps you are unaware of the electoral changes proposed for
implementation.
Shortly, you may not be able to elect a person from the major parties,
merely vote for the party.
The party would decide who will "represent" you.
Though the local electorate may have a very strong view on a matter, the
mp allocated to your region may also have a strong, but conflicting
moral viewpoint, should the PM have a different view to both of you, and
should the mp vote against your interests, against his own moral
conscience, but for the party leaders view, that mp will be a good guy.
Should he vote for his own moral conscience, as he would if he voted
against the electorates view, he would be doubly condemned as he was
elected as a party representative, tied to national policy.
If he voted, in a significant party matter, according to his own
conscience and for the electorate, against what he sincerely felt was
wrong, he would almost certainly face disciplinary proceedings.
If you want to use your vote wisely, withhold it.
Incidentally, I have a feeling that inciting people not to vote is
actually illegal in England.
--
A. Little
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: time-lock crypto
Date: 5 Apr 2000 09:30:02 -0700
The attack is trivially parallelizable, so it's not time-lock.
The adversary can throw hundreds of machines at the problem
and solve it hundreds of times faster. Since the number of
machines is under the control of the adversary -- not the
time-lock puzzle designer -- it is the adversary who will have
control on how long he has to wait before he can decrypt it.
If this is ok, then you don't need to use factoring; there
are far simpler constructions. But for most applications,
this is not ok.
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Massey-Omura protocol & ECC
Date: Wed, 05 Apr 2000 11:05:04 -0500
[EMAIL PROTECTED] wrote:
> Thanks very much for yout response. It will probably take me several
> days to digest it all :)
:-) Good luck.
>
> About MQV I found this patent
> US5933504: Strengthened public key protocol
> Assigned to the three of them. I have not read the patent, but I think
> this might be it. Too late I'm afraid.
got it. I don't understand the patent wording at all, or how it
connects
to the method I've implemented. The basic claim is:
A method of determining the integrity of a message exchanged between a
pair of
correspondents, said message being secured by embodying said message in
a function of
.alpha.<SUP>x</SUP> where .alpha. is an element of a finite group S of
order q, said method
comprising the steps of at least one of the correspondents receiving
public information
.alpha.<SUP>x</SUP> where x is an integer selected by another of said
correspondents,
determining whether said public information .alpha.<SUP>x</SUP> when
exponentiated to a
value t where t is a divisor of q provides a resultant value
.alpha.<SUP>xt</SUP> corresponding to the group identity and rejecting
messages utilizing said public information
if said resultant value corresponds to said group identity.
(and claimed for GF(2^m) and elliptic curves)
so, xP would be the ECC version, t|#E, and txP = 1. This doesn't
explain the
more complicated method of converting the "x" component of xP to an
integer and
using it as a multiplier to combine stuff. I better go talk to a lawyer
:-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: Wed, 05 Apr 2000 11:20:47 -0600
Reply-To: [EMAIL PROTECTED]
>
> > 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.
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Building a stream cipher? (newbie Question)
Date: Wed, 05 Apr 2000 11:23:32 -0500
Simon Johnson wrote:
>
> How do you contruct a resonable stream cipher?
> When i say this, I mean, to produce a pseudo-random stream of bytes.
>
> Are there any crutial techniques that should be employed to insure good
> 'randomness'?
>
> Basically, i'm asking someone to spew out everything they know on
> stream-cipher construction. Or point me to a book on the subject.
>
> I am reluctant to use some-else's algorithm, because if feel it is stealing;
> there would be a much greater sence of satsifaction if I did it my self :)
There are lots of good public domain algorithms. It's not stealing at
all,
the point of public domain is that someone else's sense of satisifaction
got there ahead of you :-)
It's also fun to figure out things yourself. But compare what you've
got
to what others have done before you first. You'll find it's not so
simple
to be good at it (like just about everything eh?)
Patience, persistence, truth,
Dr. mike
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: help needed : long number arithmetic packages
Date: Wed, 05 Apr 2000 11:19:38 -0500
[EMAIL PROTECTED] wrote:
> so anyone who can help me to find Lenstra, or can give any other
> comments about a well-defined and accepted long-number-arithmetic is
> wellcome.
I've got a copy of it if you really want it. Check out gmp too, it's
all in C and easily linkable:
www.gnu.org/software/gmp/gmp.html
I haven't used this one, but it's included with RedHat Linux
distributions
so you may already have it (grep for gmp in the RPMS directory).
freelip is pretty easy to use, but you have to initialize variables or
you get segment faults. It's mostly minor annoyance and head slapping
:-)
(send me e-mail via [EMAIL PROTECTED] and I'll be happy to send it).
Patience, persistence, truth,
Dr. mike
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Public|Private key cryptography?
Date: Wed, 05 Apr 2000 11:27:24 -0500
Simon Johnson wrote:
>
> Every algorithm i have seen so far requires the use of massive numbers to be
> secure. Are there any algorithm of this type that deal in small number?
Check out NTRU (www.ntru.com). They use arrays of small numbers to
achieve
the same end as massive numbers (the total space needed to be searched
is
too large to be practical).
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (Lincoln Yeoh)
Subject: Re: Download Random Number Generator from Ciphile Software
Date: Wed, 05 Apr 2000 17:36:49 GMT
Reply-To: [EMAIL PROTECTED]
On Tue, 04 Apr 2000 22:05:47 -0700, Anthony Stephen Szopa
<[EMAIL PROTECTED]> wrote:
>"Douglas A. Gwyn" wrote:
>>
>> Anthony Stephen Szopa wrote:
>> > I just haven't heard of one yet.
>>
>> Sure you have, but you just replied it was "wrong" then ignored it.
>>
>> The stepping motion of the first mixfile allows a standard Friedman
>> square attack against the mixfiles.
>
>I said the person was wrong because it is obvious that to suggest
>this is to clearly misunderstand the software. This can only be
>accounted for by the person not having the software, not
>thoroughly reading the Help Files, not running the examples,
>and not taking all the tutorials.
Hmm. Could you explain why the Friendman square attack is not applicable to
your software?
By the way. My [Link's] Omniscient Analysis Program Level 3 said that your
software was weak crypto/snake oil, and it can't be wrong. Anyone who
claims otherwise, clearly misunderstands the software.
Have a nice day :).
Link.
****************************
Reply to: @Spam to
lyeoh at @[EMAIL PROTECTED]
pop.jaring.my @
*******************************
------------------------------
From: [EMAIL PROTECTED] (Xcott Craver)
Crossposted-To: talk.politics.crypto
Subject: Re: OAP-L3: Semester 1 / Class #1 All are invited.
Date: 5 Apr 2000 17:28:03 GMT
Anthony Stephen Szopa <[EMAIL PROTECTED]> wrote:
[huge snip]
Hi Anthony,
>You want to talk reality? Then consider this:
>
>If there is why do I have to give anyone the raw random digit
>output directly from the random digit generator before they
>can make such an attack?
This isn't true: people can attack the cryptosystem
this way even if you don't directly give them the
pseudo-random digit stream.
In partial known plaintext attacks, say in which I
know what's in the first half of your file but not
the second, I can extract the raw random digit output
used in the first half. This situation occurs very
commonly in real life, say if someone incrementally
updates a large text file, like a log file, a diary,
a business plan, etc etc.
For a stream cipher based on a "cryptographically secure"
generator, the information from the first half should
not provide any information about the second half.
Conversely, if the generator is not cryptographically
secure, meaning that given current outputs one can
predict future outputs (within a single period,) then
one can crack a code based on it.
So being able to predict future generator outputs
_can_ be used to attack the cryptosystem in some
realistic scenarios.
>Keep in mind that there is no way this data is going to be
>available in a real life situation.
I don't see how you can say such a thing. Any
small portion of a ciphertext which is known, or
can be guessed, through other techniques, gives
away a portion of the PRNG output.
You have no idea, because NOBODY has any idea, what
cryptanalytic attacks may exist for a cipher. You can't
simply make a cipher resistant to what you know;
even flaws that do not translate into direct attacks
today can be used to pry open an attack tomorrow.
That's why PRNGs are not used for cryptosystems
if they don't pass a bevy of statistical tests, or
if future outputs can be predicted from previous
outputs.
-Scott
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: RNG based on Blum Blum Shub
Date: Wed, 05 Apr 2000 20:03:15 +0200
Tom St Denis wrote:
>
> What about changing it to
>
> p = large prime, (p - 1)/2 is prime
> X = seed
> g = large primitive generator (modulo p), above (p - 1) / 2, with at
> least log2(p)/2 bits set.
>
> M[0] = g^X
>
> To generate an output compute:
>
> M[i] = M[i - 1] * g (mod p)
> Y = M[i] mod 2^log2(p)
>
> Y = output, so with a 256 bit prime, this will output 8 bits each
> itteration. I know this is probably not strong, so where would you
> start to attack it?
While my humble knowledge by far doesn't suffice to evaluate
the strength of your scheme, I do like to suggest that you
begin by studying the statistical properties of the bit stream
obtained. A crypto PRNG need not have extremely superb
statistical qualities that are demanded in computer simulation
studies but shouldn't on the other hand be fairly poor
statistically. Should it turn out that the bit streams fail,
for example, the FIPS 140-1 tests, then you could save your
effort to prove the strength in the first place. (Of course,
I wish that you would have success with your scheme.) Like with
the BBS, special attention should be paid to liability to short
cycle lengths, I suppose.
M. K. Shen
=============================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: Wed, 05 Apr 2000 20:05:32 +0200
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!
M. K. Shen
------------------------------
From: Eric Chomko <[EMAIL PROTECTED]>
Crossposted-To: alt.politics.org.cia,soc.culture.russian,soc.culture.israel
Subject: Re: MARKKU AND INTEL BUSINESS ... $
Date: 5 Apr 2000 17:57:52 GMT
In alt.politics.org.cia [EMAIL PROTECTED] wrote:
: Since April, 1999, Markku J. Saarelainen has provided the valuable
: service and intelligence for the global audience without any
: compensation. So he has done this by himself without anybody's
: assistance and has utilized his intelligence and knowledge database
: that was developed since 1980's. There are thousands of individuals who
: have benefited from his services and insights. The estimated work time
: spent by him in 1999 and 2000 is approximately 1800 hours and with the
: 50-dollar hourly contract rate this would be approximately 90,000.00 US
: dollars. So if you have benefited from his services in 1999 or in 2000
: and want to make your payment, you can contact him by email at
: [EMAIL PROTECTED] or by phone at 305-374-2834 to make an arragement for
: his compensation. He can also provide further analysis and research
: work in all intelligence fields addressed in his postings. However, he
: shall not continue posting any intelligence reports and notes in the
: future without any considerable compensation for his valuable work.
All this time he's been looking for a handout?! He'd better make damn sure
he declares any income on his taxes! I feel like sending this message to
the IRS now to make sure.
Geez, and all this time I thought that the email spammers were
reprehensible.
: All his 1999 and 2000 postings are available for you and your
: associates for the rest of everybody's life.
Oh boy! Consider it gratis. Man, you commies really don't get how to make
a living, do you?
Have either of you purchased any Real Estate, yet? Maybe you could get a
flat in Minsk, too!
Eric
: Brivet,
: Vladimir
: Sent via Deja.com http://www.deja.com/
: Before you buy.
------------------------------
From: [EMAIL PROTECTED] (JimD)
Subject: Re: Is this code crackable?
Reply-To: JimD
Date: Wed, 05 Apr 2000 17:02:41 GMT
On Wed, 5 Apr 2000 13:54:01 +0800, "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..
>
>
>
>Jethro wrote in message <5owG4.81349$[EMAIL PROTECTED]>...
>>I'm new to this subject, but I'd appreciate an experts opinion on this.
>>
>>I've written a program that generates a "key" file. The key file is a text
>>file composed of 10,000 randomly-selected ASCII characters (character codes
>>1 through 126, excluding the end of file character code 026). The
>>characters were generated randomly using the CPU timer, mouse position and
>>current ocean water temp and barometric pressure inputs for randomizer
>>seeding.
>>
>>To encrypt a plain text file (of less than 10,000 characters, ASCII codes 1
>>through 126), the ASCII value of each character of the text file is added
>to
>>the ASCII value of each character of the key file. This summed character
>is
>>then placed into the encrypted file. Therefore, the encrypted file
>consists
>>of the same number of characters as the unencrypted file and all the
>>encrypted characters are ASCII character codes 127 through 256.
>>
>>To decrypt the encrypted file, the same key file is used, this time
>>subtracting the key character from the encrypted character to obtain the
>>ASCII value of the original text file.
>>
>>It works, but of course it requires one to physically give the key file to
>>someone else. My question is, is it possible to crack this type of code
>>without having the key file? I can't think of a way. Is this a well-known
>>technique?
Provided you don't reuse any of the key, and that the key is reasonably
random, then it cannot be broken.
--
Jim Dunnett.
dynastic at cwcom.net
He who laughs last doesn't
get the joke.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Extended Euclidean Algo
Date: Wed, 05 Apr 2000 20:12:03 +0200
Simon Brown wrote:
>
> I've been playing with Pate Williams Code from The handbook of Applied
> Crypto. I'm trying to calculate d for a RSA decrypt and I'm getting the
> value of Phi -1 not Phi + 1. Thats Phi as in (P-1)(Q-1). It's probably
> something silly but I can't seem to work it out
Which page of the Handbook are you referring to?
M. K. Shen
------------------------------
** 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
******************************
