Cryptography-Digest Digest #662, Volume #13 Fri, 9 Feb 01 07:13:01 EST
Contents:
Re: Rijndael S-box derivation (Tom St Denis)
Factoring (and not the Philippino :) ("Michael Brown")
Re: relative key strength private vs public key (Steve Portly)
UNIX Crypt for DOS ("Matthew J. Ricciardi")
Re: NPC ("Scott Fluhrer")
Re: UNIX Crypt for DOS (Paul Rubin)
Re: Phillo's alg is faster than index calculus ("Scott Fluhrer")
Re: UNIX Crypt for DOS ("Matthew J. Ricciardi")
Re: Q: WEP (Samuel Paik)
Re: Q: WEP ("Matt Timmermans")
Re: Different cipher type ("Michael Brown")
Re: CipherText patent still pending (Mok-Kong Shen)
Re: NPC ("Peter Shugalev")
stateful modran: uniform distribution over [0,n) (Wei Dai)
Bill Payne and Philippine RSA "break" (lcs Mixmaster Remailer)
Re: stateful modran: uniform distribution over [0,n) (Mok-Kong Shen)
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Rijndael S-box derivation
Date: Fri, 09 Feb 2001 04:07:16 GMT
In article <[EMAIL PROTECTED]>,
mjconroy <[EMAIL PROTECTED]> wrote:
> This may be a newbie question. Sorry.
>
> I'm trying to gen out the S-box of Rijndael by hand. I understand the
> affine transformation, but I'm unclear about the matrix that feeds it.
> Does anyone know of a clear walkthrough of this derivation?
>
> The AES proposal states that the S-box is constructed by the composition
> of two transformations:
>
> 1. First, taking the multiplicative inverse in GF(2^8), with the
> representation defined in Section 2.1. '00' is mapped onto itself.
>
> Assuming that '00' is hex, I can calculate for x = 0 and x =1, and get
> the expected values in the S-box, but these are basically special
> cases. When I try x = 2, I get a result that appears further down in
> the S-box than expected. I'm assuming that the multiplicative inverse
> in GF(2^8) of 2 is 129, but I am somewhat new to this process, so that
> could be my mistake.
Did you apply the affine transform after inversion? Did you use the correct
polynomial modulus to generate the inversions?
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Michael Brown" <[EMAIL PROTECTED]>
Subject: Factoring (and not the Philippino :)
Date: Fri, 9 Feb 2001 17:37:22 +1300
Considering the amount of interest that you showed in the Philippino method,
I thought you might want to check the page I've been trying (for the past
couple of weeks) to get someone to look at. No flames, please, unless you
actually _look_ at it :) But if it's totally screwed then by all means tell
me.
http://odin.prohosting.com/~dakkor/rsa/
Cheers,
Michael
--
Code snippit 1 : Fibbonachi fill
Stats:
In : esi = destination address, ecx = number of numbers / 2
Out : esi,eax,ebx,ecx destroyed. [esi] = 1,2,3,5,8...
Time: 2.5 clocks per Fibbonachi number + 1 clock initialisation
Code (replace ";" with newline):
mov eax,1;mov ebx,1;L1:mov [esi],eax;add ebx,eax;add esi,4;
mov [esi],ebx;add eax,ebx;add esi,4;dec ecx;jnz L1
------------------------------
From: Steve Portly <[EMAIL PROTECTED]>
Subject: Re: relative key strength private vs public key
Date: Thu, 08 Feb 2001 23:53:33 -0500
Bob Silverman wrote:
> In article <[EMAIL PROTECTED]>,
> Steve Portly <[EMAIL PROTECTED]> wrote:
> > For purposes such as intellectual property protection you might have
> the case where
> > a key should last for 30 years or more.
>
> I doubt whether you will find a single authority who suggests
> selecting keys now that will be good for 30 years. Instead,
> pro-active security is recommended.
>
> > Current standards are fine for day to day
> > E-commerce of course. For those of you that write your own programs
> and generate
> > large prime number composites
>
> Huh? What is a "prime number composite"?? Please explain.
A composite of two numbers each of which is prime.
>
>
> > you may have noticed that the spacing between prime
> > numbers grows quite large. Prime numbers only occur about one in a
> hundred thousand
> > numbers at current key sizes.
>
> Where did you get this piece of misinformation? The average
> gap between primes for primes near a large integer n is about log n.
> For 512 bit primes, this yields an average gap of 512 log 2 ~ 360
True for spacing between primes to be greater than 100,000 you would need
to be near a very large prime and these are not being used to create keys
as far as I know.
http://www.utm.edu/research/primes/largest.html
And since I cannot store or work with numbers this large using current C++
standards I hereby invoke the Homer Simpson DOH! clause.
>
>
> > I am wondering if there might be some point in the
> > future (30 years down the road) in which prime numbers are not as an
> attractive
> > alternative for public key systems? Any math theory to prove
> disprove this?
>
> 1) Alternative to what?
Methods that do not require a continual expansion in the size of primes.
>
> 2) How do you propose to do away with needing them?
Sometime in the future perhaps they will remove the prime requirement from
ECC.
>
> 3) You have not made a mathematical statement. To talk about a
> 'disproof' is nonsense. One can only prove or disprove mathematical
> statements.
>
> 4) You have failed to suggest a reason *why* you think they might
> become unattractive.
If finding primes magically becomes much easier for organized crime
sometime in the future, then creating secure primes may be impossible for
consumer owned machines.
>
>
> >>Todays public key systems may prove just as easy to break in
> > time.
>
> This would require a major breakthrough in mathematics. It will
> not occur simply because computers get faster. Such breakthroughs
> are impossible to predict. When one says "may", the statement is
> somewhat vacuous in absence of supporting evidence.
>
> --
> 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/
------------------------------
From: "Matthew J. Ricciardi" <[EMAIL PROTECTED]>
Subject: UNIX Crypt for DOS
Date: Fri, 9 Feb 2001 00:19:32 -0500
I am searching for a DOS port of the UNIX crypt command.
I have the C source code from Schneier's Applied Cryptography but, despite
several hours of tinkering, am unable to make it work properly under DOS.
(I have successfully compiled and used the same source code under UNIX.)
Of course, the UNIX and DOS versions must be interoperable, i.e. a file
encrypted under UNIX must be properly decrypted under DOS provided the
correct password is used.
Admittedly, I am not an expert C programmer, so please excuse any obvious
oversights on my part. Do you have any suggestions for how I might proceed?
Thank you,
Matt Ricciardi
[EMAIL PROTECTED]
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: NPC
Date: Thu, 8 Feb 2001 21:26:58 -0800
Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Peter Shugalev wrote:
> >
> > I think someone tried to prove that either discrete log or factoring
> > problem is NPC (not just NP). I'd like to see some results of these
> > attempts.
> >
> > And if they are *not* NPC. Do you know any attempt to create a public
> > key algorithm based on the problem that is known to be NPC?
>
> Assuming that P!=NP, then any NP complete problem takes exponential time
> in worst case. All known algorithms for doing factoring and DL take
> more than polynomial time, but less than exponential time. I believe
> (but am not certain) that they belong in a class (or maybe two seperate
> classes) of superpolynomial hard problems, seperate from NP complete
> problems.
Actually, it is possible that P!=NP, and yet NP complete problems could be
solved in subexponential/superpolynomial time. This would imply that all NP
problems could be solved in subexponential time.
--
poncho
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: UNIX Crypt for DOS
Date: 08 Feb 2001 21:36:53 -0800
"Matthew J. Ricciardi" <[EMAIL PROTECTED]> writes:
> I am searching for a DOS port of the UNIX crypt command.
Do you mean the crypt(3) function used for hashing passwords, or
the very old crypt(1) encryption program that nobody uses
any more?
Both of them worked as far back as the PDP-11, and should be
straightforward to port to DOS.
> Admittedly, I am not an expert C programmer, so please excuse any obvious
> oversights on my part. Do you have any suggestions for how I might proceed?
Bone up on C, or get someone to help you.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Phillo's alg is faster than index calculus
Date: Thu, 8 Feb 2001 21:35:05 -0800
<[EMAIL PROTECTED]> wrote in message news:95v7r3$itv$[EMAIL PROTECTED]...
>
> > My point is why would I make claims that I am not prepared to back up?
> If I
> > am not a theologian than I shouldn't stake claims.
> >
> > Likewise if he can't back up his algorithm with solving my system
> (using
> > relatively small parameters) then he shouldn't tote it as the next
> mesiah.
>
> You may have twisted my orginal post a bit.
> Let me try it in a different way.
>
> I said, "Phillo's alg is faster than index calculus...What do you
> think?"
>
> So you may answer one of the following:
> a. Yes, it is because __________.
> b. No, it isn't because ___________.
>
> The answer (with the real technical reason) can be as short as 1
> sentence. Now try fill in the blank.
Ok, I'll bite:
b. No, it isn't because Phillo's algorithm is exponential in the size of
the number being factored, while index calculus is subexponential.
--
poncho
------------------------------
From: "Matthew J. Ricciardi" <[EMAIL PROTECTED]>
Subject: Re: UNIX Crypt for DOS
Date: Fri, 9 Feb 2001 00:47:57 -0500
Sorry for the confusion. I am inquiring about the crypt(1) encryption
function.
Matt
"Paul Rubin" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
"Matthew J. Ricciardi" <[EMAIL PROTECTED]> writes:
> I am searching for a DOS port of the UNIX crypt command.
Do you mean the crypt(3) function used for hashing passwords, or
the very old crypt(1) encryption program that nobody uses
any more?
Both of them worked as far back as the PDP-11, and should be
straightforward to port to DOS.
> Admittedly, I am not an expert C programmer, so please excuse any obvious
> oversights on my part. Do you have any suggestions for how I might
proceed?
Bone up on C, or get someone to help you.
------------------------------
From: Samuel Paik <[EMAIL PROTECTED]>
Subject: Re: Q: WEP
Date: Fri, 09 Feb 2001 05:57:19 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> Could some knowledgeable person give a bit useful
> information about the WEP (Wired Equivalent Privacy)
> algorithm that is used in WLANs?
http://www.isaac.cs.berkeley.edu/isaac/wep-faq.html
That's a description of the break from the ISAACs folks at
Berkeley, there is a sufficiently detailed description of
WEP there to see its problems.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Q: WEP
Date: Fri, 09 Feb 2001 06:21:49 GMT
Oh, that's bad.
They are using RC4 with a CRC(!!!!) as an integrity check, and a 24-bit(!!!)
IV.
"Samuel Paik" <[EMAIL PROTECTED]> wrote in message
news:9600rt$774$[EMAIL PROTECTED]...
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > Could some knowledgeable person give a bit useful
> > information about the WEP (Wired Equivalent Privacy)
> > algorithm that is used in WLANs?
>
> http://www.isaac.cs.berkeley.edu/isaac/wep-faq.html
>
> That's a description of the break from the ISAACs folks at
> Berkeley, there is a sufficiently detailed description of
> WEP there to see its problems.
>
>
>
> Sent via Deja.com
> http://www.deja.com/
------------------------------
From: "Michael Brown" <[EMAIL PROTECTED]>
Subject: Re: Different cipher type
Date: Fri, 9 Feb 2001 22:36:30 +1300
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Michael Brown wrote:
> > I mentioned this a while ago, but never really followed up on it. The
idea
> > was to have a cipher where instead of each bit in a key representing a
> > number (bad description, but it's hard to cover DES and RSA keys under
one
> > word :), it represented an instruction.
>
> Before spending much more time in this direction, read what Knuth
> had to say about his youthful attempt at a "super-random" generator
> (the Art of Computer Programming, Vol. 2: Seminumerical Algorithms).
Unfortunately, I can't get hold of this book (don't have it and nor do local
bookstores). Could you tell me what he had to say?
Thanks,
Michael
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: CipherText patent still pending
Date: Fri, 09 Feb 2001 10:39:13 +0100
Bryan Olson wrote:
>
> Mok-Kong Shen wrote:
> > Bryan Olson wrote:
> > > Hard to believe you are looking at the same world as am I.
> > > There's a huge need, and call, for crypto research. But a new
> > > symmetric cipher not known to be secure or insecure just makes
> > > a large pile bigger.
> >
> [...]
> > But don't you
> > see that at schools the pupils are continuing to write
> > compositions (after you have left school)? Should they
> > stop writing??
>
> Experts teaching writing say to write every day. I've never
> heard an expert cryptologist recommend cipher design as an
> exercise.
So any pupil of crypto never gets to do an exercise of a
design and hence will also have zero chance of making
a good (or even half-good) one in his life and, as a
consequence, all good ciphers that exist today ultimately
die out (being no longer secure enough for the future
computing power and techniques) after the current
generation of crypto experts die out. Indeed an extremely
fine and highly desirable scenario for certain government
people (cf. export regulations, Wassenaar Arrangements,
RIPA, etc.).
> > It may be noted that there is a parallel
> > (monitored) group sci.crypt.research which is supposed to
> > be a forum for research stuffs. Since you apparently
> > pose a rather high standard on materials you read, I warmly
> > recommend you to switch to that group,
>
> There's a myth that sci.crypt is for the less technical
> material. Check the charter; you may be in the wrong place.
I don't think that I am in the wrong place. True, there are
sometimes also matters related to politics etc. in the group
and occassionally I post follow-ups in such threads, but
that's tolerated to some extent, if I don't err. For the
rest of what I have posted so far, I am quite certain that
my materials are technical. Whether they are of high or low
level and whether they are correct or erroneous can of
course be questioned and, in fact, the very purpose of my
posting is to learn something from the benevolent experts
but that has nothing to do with 'technicality' of the
materials per se. (I believe that I have, as a 'pupil',
occassionally even succeeded to help my co-'pupils' a tiny
little bit through what I happen to have learned, but that's
another issue.)
My point has been that sci.crypt is open to all beginners
and that persons who desire to 'only' read higher quality
stuffs are better advised to subscribe to sci.crypt.research
instead, while experts (who by definition have barely
anything to learn anywhere anytime) having time, interest
and patience to kindly help the beginners should continue
to remain in this group, which will naturally in large part
consist of 'learners' (not 'learned') and non-technical
stuffs should largely be posted only to other appropriate
internet groups, e.g. talk.politics.crypto. (I haven't
been very long in this group. But I believe that one can
live with the current amount of non-crpto stuffs and
I have the impression that the situation is better than
years before.)
BTW, I suppose that even experts who get annoyed about
chaffs could well live with our group. At least with the
type of newsreader I use there is sufficient possibility
to select (screen) stuffs that one wants to read, since
one can sort according to subjects and senders. Most subject
lines provide ample hints of whether the threads could
eventually be interesting and with time one could, if
desired, build up private lists of posters whose stuffs
one likes or doesn't like to read (a positive and a negative
list) in ways analogous to one's selection of media (films,
TV-shows, songs, books, etc.) according to the names of
the actors involved. I heard that there is even software for
automatically screening away posts from undesirable sources
(sort of personal firewall, I guess), but I don't know any
details about that.
M. K. Shen
==========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: "Peter Shugalev" <[EMAIL PROTECTED]>
Subject: Re: NPC
Date: Fri, 9 Feb 2001 12:47:58 +0300
> > I think someone tried to prove that either discrete log or factoring
> > problem is NPC (not just NP). I'd like to see some results of these
> > attempts.
> >
> > And if they are *not* NPC. Do you know any attempt to create a public
> > key algorithm based on the problem that is known to be NPC?
>
>
> The knapsack problem is NP complete, but the most of the PKE systems
> which use it are broken due to lattice attacks (their method of
> transforming a hard problem into a PKE system is flawed). The only
> knapsack-like system which isn't broken by lattice attack is NTRU.
What does it mean "their method of transforming a hard problem into a PKE
system is flawed"? Think about RSA: if you break RSA in a polynomial time
you'll get a polynomial method of factoring. When I speak about the PKE
based on the NPC problem I mean that breaking the PKE automatically solves
the NPC problem. As far as I can see these flawed PKE systems might gone
wrong in three ways:
1. They are not really based on the NPC problem but on its subset. And that
subset is solveable in polynomial time.
2. In general case the algorithm is exponential (or at least
superpolynomial). But there is an algorithm that with high probabilty solves
the problem in polynomial time (but it doesn't work in 100% of possible
cases).
3. The algorithm is exponential. E.g. its complexity is A*exp(a*n) where n
is key length. But A and a constants might be too small, so n should be too
big to stop the attacker. And n is big enough to make the PKE inpractical.
So, what was wrong with knapsack-based PKE systems?
------------------------------
From: Wei Dai <[EMAIL PROTECTED]>
Subject: stateful modran: uniform distribution over [0,n)
Date: Fri, 9 Feb 2001 03:31:16 -0800
Here is an algorithm for generating a uniformly distributed integer
over [0,n) (i.e., a random integer with an equal chance of being any
number between 0 and n-1, inclusive), using the smallest number of
random bits on average, amortized over multiple calls (n does not have
to be the same in each call). The motivation for it comes from the
recent news of an attack against DSA when the secret per-signature
exponent k isn't chosen uniformly, and the concern that sometimes high
quality random bits may be costly. It can also be used to generate
uniformly distributed permutations.
// generate a random integer in [0,n) with uniform distribution
Integer ModRan(Integer n)
{
static Integer x = 0, y = 1;
for (;;)
{
// loop invariant: x is uniformly distributed in [0,y)
if (y >= n)
{
if (x < y - (y % n))
{
Integer temp = x % n;
// save unused entropy for next time
x /= n;
y /= n;
return temp;
}
// lose some entropy here,
// but it should happen only rarely
x %= n;
y %= n;
}
x = 256 * x + rng.GenerateByte();
y = 256 * y;
}
}
The idea for it came from this message by an anonymous poster:
http://www.deja.com/threadmsg_ct.xp?AN=703802043. He originally
suggested feeding a random bit stream into an arithmetic decoder.
However you would need a decoder with infinite precision in order to
obtain a truly uniform distribution. All practical coder/decoders use
approximations, which is fine for compression/decompression, but it
makes them unsuitable for the current purpose.
--
http://cryptopp.com - free C++ cryptography and compression library
------------------------------
Date: 9 Feb 2001 11:40:03 -0000
From: lcs Mixmaster Remailer <[EMAIL PROTECTED]>
Subject: Bill Payne and Philippine RSA "break"
Ironically, the Philippine RSA "break" is a retread of an old bogus
algorithm which was torn to shreds in the mists of sci.crypt's past.
Bill Payne, now bothering cypherpunks regularly with his nutty self-filed
legal case, first gained notoriety with his own algorithm to break RSA,
available from:
http://www.l0pht.com/pub/blackcrwl/encrypt/RSAISBRO.TXT
It's the same basic algorithm: shift and xor N until you get a value of
all 1's. And it doesn't work any better today than it did back then.
As David Wagner wrote back in 1999 on sci.crypt,
> Bill Payne's method was 100% bogus. (So bogus that I'm a bit embarassed
> to even admit to having read it.) It had exponential time complexity,
> and would probably perform even worse than trial division. In no way
> does his "attack" justify the statement `RSA is broken'.
Plus ca change...
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: stateful modran: uniform distribution over [0,n)
Date: Fri, 09 Feb 2001 13:02:29 +0100
Wei Dai wrote:
>
> Here is an algorithm for generating a uniformly distributed integer
> over [0,n) (i.e., a random integer with an equal chance of being any
> number between 0 and n-1, inclusive), using the smallest number of
> random bits on average, amortized over multiple calls (n does not have
> to be the same in each call). The motivation for it comes from the
[snip]
I have some problems of understanding:
(1) Your algirithm seems never to terminate.
(2) Do I understand correctly that rng.GenerateByte() provides
an 8-bit chunk of a binary sequence that is uniform?
(3) Have you compared your scheme with one proposed by
Herman Rubin (see the thread "Question on biases in
random-numbers & decompression" of ca. 20th Sep. 2000)?
Thanks.
M. K. Shen
========================
http://home.t-online.de/home/mok-kong.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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
