Cryptography-Digest Digest #577, Volume #14 Sun, 10 Jun 01 08:13:01 EDT
Contents:
Re: Algorithms ("BenZen")
Re: Knapsack security??? Ah....huh ("rosi")
Re: cubing modulo 2^w - 1 as a design primitive? ("Peter L. Montgomery")
Re: Uniciyt distance and compression for AES ([EMAIL PROTECTED])
Re: Algorithms ("Sam Simpson")
Jacobian projective coordinates ("himanee")
Let Win2000 use Diffie-Hellman during KeyExchange ("Ricardo")
Re: Algorithms ("Tom St Denis")
Re: shifts are slow? ("Niels J=?ISO-8859-1?B?+A==?=rgen Kruse")
Re: shifts are slow? ("Tom St Denis")
----------------------------------------------------------------------------
From: "BenZen" <[EMAIL PROTECTED]>
Subject: Re: Algorithms
Date: Sat, 9 Jun 2001 06:58:33 -0400
Tom St Denis wrote in message <_XcU6.61619$[EMAIL PROTECTED]>...
>
>"Sam Simpson" <[EMAIL PROTECTED]> wrote in message
>news:wEcU6.20648$[EMAIL PROTECTED]...
>> Out of interest Tom, what did you think of the Koblitz text? Last time we
>> 'spoke' about it you had ordered but not received it.
>
>I got it around May 5th. I have read through it (neat book). Some of the
>math I don't get yet, but it's well laid out and a really good review of
>number theory.
>
>Tom
>
Which text ?
* Algebraic Aspects of Cryptography , N. Koblitz, Springer 1998
* P-adic Numbers, p-adic Analysis and Zeta-Functions, (2nd edn.) N. Koblitz,
Graduate Text 54, Springer 1996.
* A Course in Number Theory and Cryptography, N. Koblitz, Graduate Texts in
Mathematics 114, 2nd Edition, Springer 1994
* Introduction to Elliptic Curves and Modular Forms, N. Koblitz, Springer Graduate
Text 97, 2nd Edition 1993
* P-adic Analysis, A Short Course on Recent Work, N. Koblitz, LMS Lectures Notes 46,
CUP 1980
Regards,
Just Lurking.
Ben
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: Knapsack security??? Ah....huh
Date: Sun, 10 Jun 2001 02:18:28 -0400
John Bailey wrote in message <[EMAIL PROTECTED]>...
>On Fri, 8 Jun 2001 00:21:58 -0400, "rosi" <[EMAIL PROTECTED]> wrote:
[snip]
>> So, is it a go?
Answer for you (sorrily arbitrarily). No.
>>
>> I think it is only fair that I give you enough information on
>>what is ahead. I have some simple stuff, from which I would like
>>to see if certain things are as trivial as I seem to see. So I give the
>>best shot I can fire and would like you to help me. I will put
>>forth two quite non-technical questions, which do not require
>>definitive answers (or in other words, what answers come back is
>>not that important). There is one technical issue I would appreciate
>>it if you could share your thoughts with us, but that is not really
>>expected. It is up to you. The issue is to prove from what I
>>give you that P != NP. (Hope you are still in your chair if you
>>were:). Checked, I am still in mine)
>
>Would it help if we used Rojas' papers as a common ground of
>understanding?
>http://arXiv.org/find/math/1/au:+rojas/0/1/0/1998/0/1
>
Not 100% sure. Forgive me for taking a perhaps pretty accurate
guess. The answer to your question is : NO. It will not help at all.
There does not seem to be any common ground for us on the
papers at all.
I did not read the papers themselves. From the titles I took the
guess that the papers can only be quite remotely related, 'related'
even in a very loose sense. Bennett gates and non-linear quantum
gates might be closer (though I know virtually nothing about that
discipline, but would be very interested in considering that aspect
more thoroughly in private). Even those, from my understanding
now, changes no situation here. "THE" issue is, IMHO, settled.
>> Please do not be alarmed. It should be simple. Ideas about
>>both the two questions and the P!=NP issue can be formed in
>>your head by simply ‘staring at’ a construction I give you for a
>>few minutes. I am not saying that you may come up with all
>>the boring details of a proof after reading and thinking about
>>it for a few minutes. I mean that you can get the sense of it.
>>
>
>If you are heading off in the direction of complexity theory, I don't
>think its productive. To me the issue is far simpler. Standard
>format knapsack systems have been shown sufficiently suspect that
>nothing commercial is likely to be trusted. NTRU may have gone one of
False. Nothing has ever shown anything sufficient to me in that regard.
True possibly if I do not count.
Uncertain because of the informal vague nature of the statement which
renders its semantics a 'what?'.
>two ways. 1) they may have found a basis (excuse the pun) on which a
>knapsack or sparse diophantine system can be made secure OR 2) they
>just hide the knapsack formal equivalence. If the latter, I hope this
>isn't regarded as an attack on their business. If the former, it
>would be useful to understand the underlying source of the improvement
>because other parallel approaches might yield something useful as
>well.
>
>Given Rojas' (and certailnly others) work, it should not be hard to
>find a one way function which would require solving Hilbert's tenth
>problem, in order to reverse (short of an exhaustive search)
>
Now, I am conclusive on the direction WE are going. There will not
be a go. You do not have to prove whether you are "purely in NTRU". I
see already the tunnel at the end of light.
The whole thing is about (and actually is) the complexity questions.
But I fully understand that it will NOT be productive. What is 'standard
format knapsack systems'??? Who standardized them???
'likely' only sounds scientific in crypto, I dare to guess. 'Far
simpler' ??? 'Not hard'??? I am not sure if it will be hard for me
to find one. Since you said it should not be hard, but so far no
one else has found one yet (to the best of my knowledge), maybe
you can be kind enough to show us one. Or some one you know
can? The rest above sounds a bit above me and I do not know
how to comment. By the way, by 'one-way' you did not mean OTP,
did you?
I am very serious on this one. My memory is short. What is the
tenth Proprosition of David? Appreciate it if you could take your
time and repeat it here and give its semantics as you understand
it. But I promise, there will be no more about P and NP between
you and me in this thread. Serious. I could care less if I do not
hear from you any other thing. I only want to hear this one. Only
this one.
[snip]
>> So if you think this is of interest to you and this can be
>>a go, please let me know. But I repeat, if you are only
>>interested in NTRU, we are definitely not on the same track.
>>(I am pretty sure that is the case, which makes a pretty good
>>excuse. :) But please prove me wrong.)
>
>My comments above and on another post confirm you understanding. The
Have difficulty understanding the above sentence.
>whole basis for my questioning is an attempt to understand what if
>anything is different about the NTRU system and to apply the
>principles underlying such difference to other systems. If your
>approach is to treat them all alike, its of interest to me only if its
In what way you imply that we can (treat them alike?) Making them
all ring-based: NTRU[n]? Or take them all as secure? Or dump them
as all insecure? Or have a new way of leaving the security issue
dangling? :)
>a more general approach than outlined in previous papers on knapsack
>cracking. I'll happily watch.
So finally, you want to find the 'secure principle' underlying NTRU but
you are only interested in a more general cracking method (i.e. even
covering the cracking of NTRU?). Interesting proposition I can not fulfil
obviously. (And excuse me for the light tone. This is not David's 24th, is
it?)
Or maybe that is my misunderstanding. You mean, since most others
fell and NTRU stands. So you would like to find out something ( which
could be a secure aspect or insecure aspect) about NTRU that when
applied to other systems, they fall twice and hurt more???
Or you are interested in the 'something about NTRU' that can make others
ring-based or whatever, so as to make them secure so that you will not be
interested (for you are only interested in 'general cracking')???
Luckily for you, I do no crack systems and this may be the last from me
for you this time around. The things you expect to watch may not come from
me.So, if you would please, do not strain your eyes or expectations. :) :)
:)
Thanks
--- (My Signature)
>
>John
>
>> Any other readers are interested? Want to help? Please
>>let me know.
>
------------------------------
From: "Peter L. Montgomery" <[EMAIL PROTECTED]>
Subject: Re: cubing modulo 2^w - 1 as a design primitive?
Date: Sun, 10 Jun 2001 08:27:45 GMT
In article <N1qU6.68844$[EMAIL PROTECTED]>
"Tom St Denis" <[EMAIL PROTECTED]> writes:
>
>"Peter L. Montgomery" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> In article <H5eU6.62238$[EMAIL PROTECTED]>
>> "Tom St Denis" <[EMAIL PROTECTED]> writes:
>> >I was wondering if anyone ever considered cubing modulo 2^w - 1 as a
>design
>> >primitive?
>> >It is a bijection since 3 does not divide the order for w=32 or w=64.
>> The prime 6700417 divides 2^32 + 1. This prime is 1 modulo 3,
>> so cubing is not a bijection modulo 2^64 - 1.
>Hmm? What I am missing? The inverse exponent of 3 modulo 2^64 -1 is
>6148914691236517205. Hence you get
>(g^3)^6148914691236517205 mod (2^64 - 1) = g as an identity
>
>I thought as long as 3 doesn't divide phi(p) it forms a bijection since
>there is an inverse exponent which will form the identity g^(x/x) mod p = g.
Experiment with cubes modulo 35 by hand.
Cubing is not a bijection because 3^3 == (-2)^3 (mod 35) for example.
Find where your understanding is wrong.
If you are willing try an even modulus, you can use 14 rather than 35.
Here 3^3 == (-1)^3 (mod 14).
--
The 21st century is starting after 20 centuries complete,
but we say someone is age 21 after 21 years (plus fetus-hood) complete.
[EMAIL PROTECTED] Home: San Rafael, California
Microsoft Research and CWI
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Uniciyt distance and compression for AES
Date: Sun, 10 Jun 2001 00:24:07 -0800
Dennis Ritchie wrote:
>
> [EMAIL PROTECTED] wrote:
>
> >
> > I think I will order that [Shannon Collected Papers book] (although
> > I may have to save my lunch money
> > for a month to pay for it). BTW, are you "the" Dennis Ritchie (as in
> > one of "the men")? ;)
>
> As Gwyn pointed out, an alternative is locating a library copy,
> though I suppose it would have to be a fairly good library.
I just found out it's available at my library - I'll pick it up tomorrow
afternoon.
> Nevertheless it is a neat book--Shannon had a very broad career,
> and so his papers on chess programs, his mouse-in-maze machine,
> and even juggling are all there.
I heard he was pretty good on a unicycle too. What is amazing to me is
the way that he was able to determine the general characteristics which
could be used to describe many specific (and complicated!) systems.
Being
able to analyze an encryption algorithm is neat, but coming up with a
model which can be used to describe all secrecy systems is a much more
difficult intellectual feat, IMHO. Being able to analyze a communication
system takes skill, but determining the fundamental limits and the
general
characteristics of all communication systems is, IMHO, pure genius.
> re BTW--well, all indications are that I have exactly one X and one Y
> chromosome in most cells, so..., but there are other Dennis Ritchies:
>
> http://www.cs.bell-labs.com/~dmr/otherlives.html
>
> Dennis
Thank you, thank you, thank you for giving the world a *real* operating
system.
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: Algorithms
Date: Sat, 9 Jun 2001 11:22:31 +0100
If you hadn't snipped his previous post, you'd have caught the line:
"> > A Course in Number Theory and Cryptography -- Neal Koblitz"
--
Sam Simpson
http://www.scramdisk.clara.net/
"BenZen" <[EMAIL PROTECTED]> wrote in message
news:dzCU6.10033$[EMAIL PROTECTED]...
> Tom St Denis wrote in message
<_XcU6.61619$[EMAIL PROTECTED]>...
> >
> >"Sam Simpson" <[EMAIL PROTECTED]> wrote in message
> >news:wEcU6.20648$[EMAIL PROTECTED]...
> >> Out of interest Tom, what did you think of the Koblitz text? Last time
we
> >> 'spoke' about it you had ordered but not received it.
> >
> >I got it around May 5th. I have read through it (neat book). Some of
the
> >math I don't get yet, but it's well laid out and a really good review of
> >number theory.
> >
> >Tom
> >
> Which text ?
> * Algebraic Aspects of Cryptography , N. Koblitz, Springer 1998
> * P-adic Numbers, p-adic Analysis and Zeta-Functions, (2nd edn.) N.
Koblitz,
> Graduate Text 54, Springer 1996.
> * A Course in Number Theory and Cryptography, N. Koblitz, Graduate Texts
in
> Mathematics 114, 2nd Edition, Springer 1994
> * Introduction to Elliptic Curves and Modular Forms, N. Koblitz, Springer
Graduate
> Text 97, 2nd Edition 1993
> * P-adic Analysis, A Short Course on Recent Work, N. Koblitz, LMS
Lectures Notes 46,
> CUP 1980
>
> Regards,
> Just Lurking.
> Ben
>
>
------------------------------
From: "himanee" <[EMAIL PROTECTED]>
Subject: Jacobian projective coordinates
Date: Sun, 10 Jun 2001 16:13:44 +0530
Hello,
I had posted a question to this newsgroup involving Jacobian projective
coordinates, which are used in ecc.
For some reason, my Find is not showing me the thread.
I got the following reply from Bodo Moeller.
> E.g. see the book "Elliptic Curves in Cryptography" by I.F. Blake,
> G. Seroussi and N.P. Smart (London Mathematical Society Lecture Note
> Series vol. 265, Cambridge University Press, 1999).
Regards,
Himanee
------------------------------
From: "Ricardo" <[EMAIL PROTECTED]>
Subject: Let Win2000 use Diffie-Hellman during KeyExchange
Date: Sun, 10 Jun 2001 12:53:32 +0200
Hi,
I want Win2000 using Diffie-Hellman during a Key Exchange in
SSL/TLS-session.
Does anyone know how to set this configuration?
...this is what I have already tried:
with regedt32 I changed the settings to the following values
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\SecurityProviders\SCHAN
NEL\KeyExchangeAlgorithms\Diffie-Hellman]
"Enabled"=dword:ffffffff
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\SecurityProviders\SCHAN
NEL\KeyExchangeAlgorithms\Fortezza]
"Enabled"=dword:00000030
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\SecurityProviders\SCHAN
NEL\KeyExchangeAlgorithms\PKCS]
"Enabled"=dword:00000030 (When I changed for PKCS the setting into the value
0x0 no SSL-handshake could be made.
What I received was an alert-message ("handshake-failure").)
ServicePack2 is already installed.
I know that W2k uses for a Key Exchange the DLL-files dssenh.dll and/or
dssbase.dll.
They exist in the dir E:\WINNT\system32\.
But even the changes in the register no handshake can be made with
Diffie-Hellman.
Could anyone please help me.
Thx.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Algorithms
Date: Sun, 10 Jun 2001 11:44:20 GMT
"BenZen" <[EMAIL PROTECTED]> wrote in message
news:dzCU6.10033$[EMAIL PROTECTED]...
> Tom St Denis wrote in message
<_XcU6.61619$[EMAIL PROTECTED]>...
> >
> >"Sam Simpson" <[EMAIL PROTECTED]> wrote in message
> >news:wEcU6.20648$[EMAIL PROTECTED]...
> >> Out of interest Tom, what did you think of the Koblitz text? Last time
we
> >> 'spoke' about it you had ordered but not received it.
> >
> >I got it around May 5th. I have read through it (neat book). Some of
the
> >math I don't get yet, but it's well laid out and a really good review of
> >number theory.
> >
> >Tom
> >
> Which text ?
> * A Course in Number Theory and Cryptography, N. Koblitz, Graduate Texts
in
> Mathematics 114, 2nd Edition, Springer 1994
Tom
------------------------------
From: "Niels J=?ISO-8859-1?B?+A==?=rgen Kruse" <[EMAIL PROTECTED]>
Subject: Re: shifts are slow?
Date: Sun, 10 Jun 2001 13:44:34 +0200
I artiklen <[EMAIL PROTECTED]> ,
[EMAIL PROTECTED] (Bob Jenkins) skrev:
> I've been talking to people trying to optimize assembly for the P4.
> They say there is a "shift penalty". What is more, they claim that
> shifts are necessarily slower than addition or xor. Wire length
> is starting to matter more than gate count.
You might consider using a sequence of adds to shift. The P4 has a nifty
double pumped ALU with midcycle forwarding, so you can do a + b + c in a
single cycle. Caveat: I don't have a P4, this is what I have read about the
P4 on the net.
> I asked, do you mean that the low bits of x and y in x+y are closer
> together than the low and high bits of x? They said yes. The
> registers are interleaved that way. Perhaps they could do shifts
> by 2 or 3, or maybe 4, in the same time as addition, but more than
> that is inherently slower.
The distance from the register file to the shift unit can hardly be less
than between the outer bits of a register. Carry on an add can ripple the
full with, unless you use a redundant representation, so this is no better
than a shift. The PPC7450 running at 733 Mhz has a single cycle shift, so a
1500 Mhz CPU should not have to do worse than 2 cycles for a shift.
> My old model of the world had +-^|&~ take 1 cycle, tab[] take 2,
> if() take 5 if it guesses wrong, * take 10, and / take 20. That's
> apparently no longer close to reality. What is the new reality?
This depends very much on the CPU. For the PPC7450, the timings are
(latency,throughput):
+-^|&~ (1,1) (except arithmetic right shift
and other oddities)
tab[], int/vector (3,1)
tab[], floating point (4,1) (distance from L1 to FP register file is
larger than to int and vector r. files)
mispredict 6 (minimum)
32*8 bit (3,1)
32*16 bit (3,1)
32*32 bit (4,2)
/ (23,23)
These are the latencies as far as forwarding is concerned. Getting condition
codes ready take another cycle.
What was your old world? Pentium MMX? I believe load is 3 cycle latency on
Pentium III.
--
Mvh./Regards, Niels Jørgen Kruse, Vanløse, Denmark
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: shifts are slow?
Date: Sun, 10 Jun 2001 12:08:40 GMT
"Niels Jørgen Kruse" <[EMAIL PROTECTED]> wrote in message
news:xhJU6.173$[EMAIL PROTECTED]...
> I artiklen <[EMAIL PROTECTED]> ,
> [EMAIL PROTECTED] (Bob Jenkins) skrev:
>
> > I've been talking to people trying to optimize assembly for the P4.
> > They say there is a "shift penalty". What is more, they claim that
> > shifts are necessarily slower than addition or xor. Wire length
> > is starting to matter more than gate count.
>
> You might consider using a sequence of adds to shift. The P4 has a nifty
> double pumped ALU with midcycle forwarding, so you can do a + b + c in a
> single cycle. Caveat: I don't have a P4, this is what I have read about
the
> P4 on the net.
Good idea. Get an Athlon. They are cheaper and really magic.
The Athlon is the only x86 cpu I know of where you can write mildly
optimized code and still get amazing clock counts.
> > I asked, do you mean that the low bits of x and y in x+y are closer
> > together than the low and high bits of x? They said yes. The
> > registers are interleaved that way. Perhaps they could do shifts
> > by 2 or 3, or maybe 4, in the same time as addition, but more than
> > that is inherently slower.
>
> The distance from the register file to the shift unit can hardly be less
> than between the outer bits of a register. Carry on an add can ripple the
> full with, unless you use a redundant representation, so this is no better
> than a shift. The PPC7450 running at 733 Mhz has a single cycle shift, so
a
> 1500 Mhz CPU should not have to do worse than 2 cycles for a shift.
Let's not forget that the P4 will clock down to 750Mhz when it crosses over
a certain temperature. At least the Athlon will continue to burn up ! :-)
Tom
------------------------------
** 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
******************************
