Cryptography-Digest Digest #645, Volume #13 Tue, 6 Feb 01 21:13:01 EST
Contents:
Re: Mod function (Tom St Denis)
Re: Affordable High-Quality Patents (Tom St Denis)
Re: Well, it stumped the bikers.... (Tom St Denis)
RE: Disk Overwriting (Tom St Denis)
Bleichenbacher finds bug in DSA RNG (Paul Rubin)
Re: Phillo's alg is faster than index calculus (John Myre)
Re: Encrypting Predictable Files ([EMAIL PROTECTED])
Re: 1 to 4 byte hash function ([EMAIL PROTECTED])
Re: Encrypting Predictable Files (Tom St Denis)
Re: Phillo's alg is faster than index calculus ([EMAIL PROTECTED])
Re: Pseudo Random Number Generator (Bryan Olson)
Re: Phillo's alg is faster than index calculus ([EMAIL PROTECTED])
Re: Phillo's alg is faster than index calculus (Tom St Denis)
Re: Phillo's alg is faster than index calculus (Tom St Denis)
Is Cipherunicorn-A Broken? ("Anonymous")
Re: Well, it stumped the bikers.... (Jim Gillogly)
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Mod function
Date: Tue, 06 Feb 2001 23:57:30 GMT
In article <BP%f6.6375$[EMAIL PROTECTED]>,
"Adam Smith" <[EMAIL PROTECTED]> wrote:
> I am looking for a mod function that can work on lery large (100+ digit)
> numbers...
Speficity is key.
Why not not use VB? There are plenty of good packages for C. Gnu's MP, MPI
are two good ones.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Crossposted-To: biz.misc,biz.mlm,sci.electronics
Subject: Re: Affordable High-Quality Patents
Date: Wed, 07 Feb 2001 00:00:13 GMT
In article <95ps88$ug0$[EMAIL PROTECTED]>,
PatentWeaver <[EMAIL PROTECTED]> wrote:
> www.patentweavers.com
>
> Patent Weavers provides experienced software, hardware and business
> method patent research and writing. Expert at infringement & validity
> analysis, we've supported some of the world's foremost technology
> companies in patent litigation. We specialize in IT patents at all
> levels of complexity, and offer low cost patent work for simple
> mechanical and electrical patents.
Thanks for spamming this group you dolt!
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Well, it stumped the bikers....
Date: Tue, 06 Feb 2001 23:59:46 GMT
In article <95plht$np5$[EMAIL PROTECTED]>,
JC <[EMAIL PROTECTED]> wrote:
> There's beer in it!
> Stolen from uk.rec.motorcycles. Parts 2 & 3 can be seen at
> http://x54.deja.com/threadmsg_ct.xp?
> thitnum=30&AN=724668328.1&mhitnum=0&CONTEXT=981488637.1476132911
Um dude, post this to rec.puzzles. sci.crypt is about cryptography not
puzzles.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: RE: Disk Overwriting
Date: Wed, 07 Feb 2001 00:01:09 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Since, once again, we have posters authoritatively claiming either
>
> (1) "Disk data can be recovered from under any amount of overwriting,"
> or
> (2)"Just overwriting once with FF is sufficient to preclude recovery,"
>
> both of which statements are true, but only in context, it seems
> useful to once again post the following overview in an attempt to
> provide such context:
Um if the polly's come and steal my HD what is to stop them from just
planting a camera in my room.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Bleichenbacher finds bug in DSA RNG
Date: 06 Feb 2001 16:20:56 -0800
http://www.cnn.com/2001/TECH/internet/02/06/DSA.flaw.idg/index.html
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Phillo's alg is faster than index calculus
Date: Tue, 06 Feb 2001 17:30:04 -0700
[EMAIL PROTECTED] wrote:
<snip>
> 2. Theoretically, we need x operations. But in practice, we don't.
>
> Sisi's conjecture: worst-case scenario will never happen.
<snip>
But even the best case is horrible, for large numbers. The example
is misleading you. The method is fast for x=20, but so what? Try
to consider the case where n and x are about 1000 bits long. At
each step you can add at most 1000 bits (the length of n). So you
don't need x steps, but you need x/1000 steps, or more.
You need enough steps to get x bits. Since x is about 1000 bits,
x is about 2^1000, so x bits is 2^1000 bits. How many steps
would it take to get 2^1000 bits, 1000 bits at a time? Do the
arithmetic: 1000 is about 1024, which is 2^10; 2^1000 divided
by 2^10 is 2^990. Doing anything 2^990 times, even something
as simple as addition, is way too long to be practical.
You can work out similar examples for various sizes of n and
x. You could even work out the general formula, based on the
sizes of n and x. Clearly the method is ok if x is small,
but no one really cares about that: if x is small there are
a lot of methods that work.
JM
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Encrypting Predictable Files
Date: Wed, 07 Feb 2001 00:25:25 GMT
Two can play this game. Suppose one has a general file encryption
program that works for any file. Take Scott16u or your OTP
The amount of possible plaintext texts is 2**(number of bits in file)
encrypt with scott16u or the OTP the resulting output file has
the same number of bits and there are no possible encrypted files
that could have come from something other then any of the input
files. Since they are the same length plain text and encrypted and
since there is the same number in each set and there is a 1 to 1
relationship between every file in the palin set as encrypted there
is no difference in entropy. Something you fail to understnd.
Most encryption streams add padding or some since nonsince that
weak the code from an information point of view. The methods are
so bad and so common that people like you can't step back
and look at the whole picture. Its maybe not your fault you have
been spoon feed by other people to ignorant to look at facts
or they want to keep people stupid. In fact most methods that
imploy compression with encryption are such that there only exist
one key that can decrypt the message to a file which when uncompressed
can be recompressed and encrypted again. Matt has done a great
service in doing compression properly so as to not add information
to a file. Something you can't seem to grasp.
> <sarcasm>That's a surprising result if I ever saw one.</sarcasm>
>
> I'm sorry DS but you are wrong as usual, unless you would care to
claim that
> OTP is not good cryptography? In which case I'd like a proof from
you, even
> at the fair amount of handwaving level that I gave.
>
You have your proof asshole. I never have stated that a
proper OTP is not great. You may think I have but then your
full of shit as ususal.
> Now on to the other statement I addressed before
> Earlier claims by DS in this thread:
> Matt Timmermanns Rijndael implementation does not add information.
> Matt Timmermanns Rijndael implementation changes the length of files
The two statements are true becasue of the bijective compression in
Matts code .
> So you have once again proven yourself incorrect in at least one way.
Now
> since I'm tired of clogging the NG I'm going to leave DS alone while
he
> tries to figure out whether or not logic applies in his world or not,
so I
> will no longer reply to him (or others replying to him) in this
thread.
> Joe
I guess the honest truth is you can only spout lies so long
and you can't grasp the concept of what I or Matt has done. Thats
OK you don't want to learn the truth anyway your mind is closed.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: 1 to 4 byte hash function
Date: Wed, 07 Feb 2001 00:33:48 GMT
In article <eOg1v$IkAHA.279@cpmsnbbsa07>,
"Joseph Ashwood" <[EMAIL PROTECTED]> wrote:
> "Akita Bright-Holloway" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> [on a 1-4 byte hash]
>
> Regardless of how good the function itself is, it can be directly
mapped out
> in RAM on a machine, from this breaking it is as simple as a lookup.
>
> As to whether or not this would be useful when used in conjunction
with
> another hash function. No it would not, the best you could hopre for
would
> be for the result to have as much strength as the outer-most hash
function.
> This can be proven mathematically by observing that by using
intermediate
> hash functions you can not increase entropy, but you can lose it.
>
> I think I see where this is going though. I'd recommend very strongly
> against creating your own hash function. There are several very fast,
very
> secure hash functions available for whatever your needs are. The most
likely
> candidates are MD5 and SHA-1 both have many freely available
> implementations, I'd recommend you start with openSSL
(www.openssl.org)
> Joe
AS to another point of view. Doing it your self can be fun
I think you should not only look at others. But feel free to
experiment on your own.
And if your interested in other unorthodox ideas take a
look at http://members.nbci.com/ecil/index.htm
Dave
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Encrypting Predictable Files
Date: Wed, 07 Feb 2001 00:36:27 GMT
In article <95q4lc$6mm$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>
>
> Two can play this game. Suppose one has a general file encryption
> program that works for any file. Take Scott16u or your OTP
> The amount of possible plaintext texts is 2**(number of bits in file)
> encrypt with scott16u or the OTP the resulting output file has
> the same number of bits and there are no possible encrypted files
> that could have come from something other then any of the input
> files. Since they are the same length plain text and encrypted and
> since there is the same number in each set and there is a 1 to 1
> relationship between every file in the palin set as encrypted there
> is no difference in entropy. Something you fail to understnd.
Either Scottu19 is an OTP or this paragraph doesn't make sense. If the key
going into Scottu19 is smaller then the message then it's not an OTP **AND**
there is not a 1-1 relationship between messages and keys.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Phillo's alg is faster than index calculus
Date: Wed, 07 Feb 2001 01:03:00 GMT
> > 2. Theoretically, we need x operations.
> You are severely confused. n is known. x is to be determined.
Yes n is know. x is to be determined. Therefore we need x operations.
Please review his method again.
> > 4. Unlike index calculus, we don't use any trial and error.
>
> You clearly do not know how the index calculus algorithms work,
> since they do not use trial and error.
You need a set of base factors. The base factors do not work for every
number. If you get unlucky, you'll need to generate another set of base
factors.
> > So what do you think?
>
> I think you need to do a lot of studying.
Seems like you do too!
>
> --
> 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/
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Pseudo Random Number Generator
Date: Wed, 07 Feb 2001 01:09:47 GMT
Mok-Kong Shen wrote:
> Bryan Olson wrote:
> > Mok-Kong Shen wrote:
>
> > > What can be proved is the following:
> > >
> > > For m non-degenerate independent integer random variables
> > > over [0,n-1] their sum mod n approaches a uniform random
> > > variable as m increases. If one of the random varaible is
> > > uniform, then any value of m results in a uniform random
> > > variable.
> >
> > Counterexample: Lent n = 49, and the distribution of each
> > variable be uniform over the 42 integers in [1..48] that are
> > not divisible by 7, and zero elsewhere.
>
> That's what is excluded by 'non-degenerate'. Sorry, if
> the term is not standard or common.
Typical use of "degenerate" is for cases where a key defining
property is fulfilled in a vacuous way. For example (the one
I assumed) a random variable that only has one possible value
is degenerate. I don't see anything degenerate about the
distribution in my counter-example.
What exactly does your usage of non-degenerate mean? Clearly
divisibility by seven is not the only case.
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Phillo's alg is faster than index calculus
Date: Wed, 07 Feb 2001 01:17:05 GMT
> But even the best case is horrible, for large numbers. The example
> is misleading you. The method is fast for x=20, but so what? Try
> to consider the case where n and x are about 1000 bits long. At
> each step you can add at most 1000 bits (the length of n). So you
> don't need x steps, but you need x/1000 steps, or more.
>
> You need enough steps to get x bits. Since x is about 1000 bits,
> x is about 2^1000, so x bits is 2^1000 bits. How many steps
> would it take to get 2^1000 bits, 1000 bits at a time? Do the
> arithmetic: 1000 is about 1024, which is 2^10; 2^1000 divided
> by 2^10 is 2^990. Doing anything 2^990 times, even something
> as simple as addition, is way too long to be practical.
>
> You can work out similar examples for various sizes of n and
> x. You could even work out the general formula, based on the
> sizes of n and x. Clearly the method is ok if x is small,
> but no one really cares about that: if x is small there are
> a lot of methods that work.
>
> JM
>
First of all, I do believe this algorithm is slow if N is large. What I
am thinking is that maybe it is faster than index calculus. I listed
some reasons in my last post. I like to hear constructive opinions.
One of the things I have in mind is doing a lot of precomputation, eg.
precompute 110110+11011=1010001 So every time we see ...1110 at the end,
we apply 1010001. If we do a lot of these precomputation, we can shorten
the time some what and we'll be dealing with more than say 1000 bits at
a time. It won't be fast enough to break discrete log, but maybe it can
compete with index calculus.
I also think that maybe we have another list of modulus N that are not
secure because of this method. eg. N= 11001100110011 etc.
It's a pleasure to communicate with you.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Phillo's alg is faster than index calculus
Date: Wed, 07 Feb 2001 01:44:53 GMT
In article <95q7mc$98f$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>
> > But even the best case is horrible, for large numbers. The example
> > is misleading you. The method is fast for x=20, but so what? Try
> > to consider the case where n and x are about 1000 bits long. At
> > each step you can add at most 1000 bits (the length of n). So you
> > don't need x steps, but you need x/1000 steps, or more.
> >
> > You need enough steps to get x bits. Since x is about 1000 bits,
> > x is about 2^1000, so x bits is 2^1000 bits. How many steps
> > would it take to get 2^1000 bits, 1000 bits at a time? Do the
> > arithmetic: 1000 is about 1024, which is 2^10; 2^1000 divided
> > by 2^10 is 2^990. Doing anything 2^990 times, even something
> > as simple as addition, is way too long to be practical.
> >
> > You can work out similar examples for various sizes of n and
> > x. You could even work out the general formula, based on the
> > sizes of n and x. Clearly the method is ok if x is small,
> > but no one really cares about that: if x is small there are
> > a lot of methods that work.
> >
> > JM
> >
>
> First of all, I do believe this algorithm is slow if N is large. What I
> am thinking is that maybe it is faster than index calculus. I listed
> some reasons in my last post. I like to hear constructive opinions.
>
> One of the things I have in mind is doing a lot of precomputation, eg.
> precompute 110110+11011=1010001 So every time we see ...1110 at the end,
> we apply 1010001. If we do a lot of these precomputation, we can shorten
> the time some what and we'll be dealing with more than say 1000 bits at
> a time. It won't be fast enough to break discrete log, but maybe it can
> compete with index calculus.
>
> I also think that maybe we have another list of modulus N that are not
> secure because of this method. eg. N= 11001100110011 etc.
>
> It's a pleasure to communicate with you.
Please reply to my post in this thread! It's only a 256-bit prime so your
algorithm should solve in a bit.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Phillo's alg is faster than index calculus
Date: Wed, 07 Feb 2001 01:44:04 GMT
In article <95q6s0$8d2$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>
> > > 2. Theoretically, we need x operations.
>
> > You are severely confused. n is known. x is to be determined.
>
> Yes n is know. x is to be determined. Therefore we need x operations.
> Please review his method again.
>
> > > 4. Unlike index calculus, we don't use any trial and error.
> >
> > You clearly do not know how the index calculus algorithms work,
> > since they do not use trial and error.
>
> You need a set of base factors. The base factors do not work for every
> number. If you get unlucky, you'll need to generate another set of base
> factors.
>
> > > So what do you think?
> >
> > I think you need to do a lot of studying.
>
> Seems like you do too!
Why again did you not reply to my post?
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Anonymous" <[EMAIL PROTECTED]>
Subject: Is Cipherunicorn-A Broken?
Date: Wed, 7 Feb 2001 10:52:17 +0900
I heard "Cipherunicorn-A is broken." in somewhere.
Does anyone know about it?
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Well, it stumped the bikers....
Date: Wed, 07 Feb 2001 02:03:34 +0000
Tom St Denis wrote:
>
> In article <95plht$np5$[EMAIL PROTECTED]>,
> JC <[EMAIL PROTECTED]> wrote:
> > There's beer in it!
> > Stolen from uk.rec.motorcycles. Parts 2 & 3 can be seen at
> > http://x54.deja.com/threadmsg_ct.xp?
> > thitnum=30&AN=724668328.1&mhitnum=0&CONTEXT=981488637.1476132911
>
> Um dude, post this to rec.puzzles. sci.crypt is about cryptography not
> puzzles.
I, for one, welcome occasional fun challenges like this. It's
an interesting twist, and no harder than a Vigenere once you get
your mind around the description. I think 95% of the people
posting authoritatively to sci.crypt haven't broken anything
beyond newspaper simple substitutions, so an occasional reminder
of the basics isn't misplaced.
As a hint, the key is 6 letters long, as you can determine
by the index of coincidence or the Kasiski method.
So... can we get that beer put in escrow before the solution is
divulged?
--
Jim Gillogly
Mersday, 17 Solmath S.R. 2001, 02:00
12.19.7.17.3, 9 Akbal 6 Pax, First Lord of Night
------------------------------
** 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
******************************
