Cryptography-Digest Digest #862, Volume #8 Thu, 7 Jan 99 21:13:03 EST
Contents:
Re: U.S. Spying On Friend And Foe (Jim Dunnett)
Re: On the Generation of Pseudo-OTP (Theo Honohan)
Re: DES Hardware Implementation!! (Christof Paar)
RSA source code? (Antonio ROMEO)
Re: What is left to invent? (R. Knauer)
Re: symmetric vs various asymmetric [was: DH is "stronger" than RSA?] (DJohn37050)
Re: What is left to invent? (Helger Lipmaa)
Re: What is left to invent? ("Nick Payne")
Re: coNP=NP Made Easier? (rosi)
Re: Help: a logical difficulty (Nicol So)
Re: One-time pads not secure ? (NSA's Venona project) (Gideon Yuval)
Re: On the Generation of Pseudo-OTP (Darren New)
Re: On the Generation of Pseudo-OTP (Darren New)
Re: Help: a logical difficulty (Nicol So)
Re: coNP=NP Made Easier? (Matt Brubeck)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Jim Dunnett)
Subject: Re: U.S. Spying On Friend And Foe
Date: Thu, 07 Jan 1999 19:53:16 GMT
Reply-To: Jim Dunnett
On Wed, 6 Jan 1999 22:52:57 +0000, Withheld <[EMAIL PROTECTED]>
wrote:
>In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
>"Tony T. Warnock" wrote:
>> The great problem of "friends" spying on the US is that the
>> "friend" may not be able to keep secrets. Some of our allies may not
>> mean harm to us, but they cannot keep secrets. Vice versa.
>
>The British can keep secrets, and they have an Official Secrets Act to
>enforce it.
I fail to see how the OSA makes someone keep secrets!
There have been as many Brit defectors as American.
--
Regards, Jim. | A drunk man is more likely to find a
olympus%jimdee.prestel.co.uk | woman attractive. So if all else fails,
dynastic%cwcom.net | get him drunk.
nordland%aol.com | - Dr Patrick McGhee, who coaches women
marula%zdnetmail.com | on successful dating.
Pgp key: wwwkeys.uk.pgp.net:11371
------------------------------
From: Theo Honohan <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Date: 07 Jan 1999 21:00:04 +0000
[EMAIL PROTECTED] (R. Knauer) writes:
> On Thu, 07 Jan 1999 17:37:37 GMT, Darren New <[EMAIL PROTECTED]>
> wrote:
>
> >Heck, SGI (if I remember who properly)
>
> Yes it is SGI, although I cannot find it anymore.
It's (still) at http://lavarand.sgi.com/.
------------------------------
From: [EMAIL PROTECTED] (Christof Paar)
Subject: Re: DES Hardware Implementation!!
Date: 7 Jan 1999 21:50:45 GMT
Samer EL HAJJ ([EMAIL PROTECTED]) wrote:
: Hello!
: I'm working on the hardware inmplementation (with VHDL into an FPGA) of
: DES decryption.
: after many searh I did not find any publication or example about this
: topic.
:
: Can anyone point me to some documentation on the subject?
: Thanks in advance!!
:
Please check our SAC '98 paper and Jens Kaps' MS Thesis, both of which
can be found on our web page at:
http://ece.wpi.edu/Research/crypt
We implemented DES on Xilinx FPGAs and achieved encryption rates
betweeen about 100 Mbit/s and 400 Mbit/s, depending on the degree
of pipeling and loop unrollment.
Hope that's of help,
Christof
>>> WORKSHOP ON CRYPTOGRAPHIC HARDWARE AND EMBEDDED SYSTEMS (CHES) <<<
>>> WPI, August 12 & 13, 1999 <<<
>>> check http://ece.wpi.edu/Research/crypt/ches <<<
***********************************************************************
Christof Paar, Assistant Professor
Cryptography and Information Security (CRIS) Group
ECE Dept., WPI, 100 Institute Rd., Worcester, MA 01609, USA
fon: (508) 831 5061 email: [EMAIL PROTECTED]
fax: (508) 831 5491 www: http://ee.wpi.edu/People/faculty/cxp.html
***********************************************************************
------------------------------
Date: Thu, 07 Jan 1999 22:34:59 +0100
From: Antonio ROMEO <[EMAIL PROTECTED]>
Subject: RSA source code?
I need the RSA C source code.
Can anyone help me?
Thanks.
--
Antonio ROMEO
=========================================
Swiss Federal Institute of Technology
Department of Electrical Engineering
Integrated Systems Center (C3I)
EPFL-DE-C3i ELB-Ecublens
CH-1015 Lausanne
tel. +41 21 693 69 79
fax +41 21 693 46 63
email [EMAIL PROTECTED]
http://c3iwww.epfl.ch/people_frame.html
==========================================
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: What is left to invent?
Date: Thu, 07 Jan 1999 23:01:52 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 07 Jan 1999 19:00:43 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>I believe that there are indeed an almost infinite number of
>ingeneous ways to devise session keys that are changed as often
>as needed and that are safe from prediction by the analyst. The
>56-bit restriction then doesn't hurt very much since the message
>length encrypted by a particular key is small.
Of course, if an attacker learns about the scheme being used to
generate the key, it's all over.
> Perhaps one
>should not follow 'standard' (commonly known) ways of generating
>keys but better use one's own 'invention'.
Yeah, but nothing has the wide applicability of public keys.
Bob Knauer
"The American Republic will endure, until politicians realize they
can bribe the people with their own money."
--Alexis de Tocqueville
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: symmetric vs various asymmetric [was: DH is "stronger" than RSA?]
Date: 7 Jan 1999 23:32:18 GMT
For EC on a random curve, the known best attack is a square root attack so the
bit size is about twice the bit size of the symmetric key. Add a bit or two
for fudge factor.
Don Johnson
------------------------------
From: Helger Lipmaa <[EMAIL PROTECTED]>
Subject: Re: What is left to invent?
Date: Fri, 08 Jan 1999 01:34:28 +0200
Darren New wrote:
> Just out of curiousity, what is the theoretical cutting edge nowadays?
Buy "Crypto '98" and "Eurocrypt '98" proceedings (76 papers in total).
Check at the end of every paper. They usually have a section "Open
problems" :-)
Some of those problems have been solved already, tho ;-(
--
Helger Lipmaa
http://home.cyber.ee/helger
------------------------------
From: "Nick Payne" <[EMAIL PROTECTED]>
Subject: Re: What is left to invent?
Date: Fri, 8 Jan 1999 11:28:56 +1100
This reminds me of Lord Kelvin's pronouncement about a century ago that all
of Physics had been discovered and all that was needed was a bit of tidying
up around the edges...
Darren New <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>Other than user interfaces, efficiency, ubiquity, and trying to
>circumvent stupid politics, what's left to be invented?
------------------------------
From: rosi <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: Re: coNP=NP Made Easier?
Date: Thu, 07 Jan 1999 13:45:01 -0800
Planar wrote:
>
> >From: rosi <[EMAIL PROTECTED]>
>
> > I first commit to what I adopt as the definition for the complexity
> >class of P (which is quoted from "Handbook of Applied Cryptography" by
> >Menezes et al):
> > The complexity class P is the set of all decision problems
> > that are solvable in polynomial time.
>
> Aha. Now we know where the problem is. The correct definition of P ^^
Who? Who is/are this 'we'? Sure this 'we' know(s)?
> would be more like this: ^^^^
'like'? You do mathematics in this 'like' manner?
>
> The complexity class P is the set of all decision problems
> that are solvable in polynomial time BY DETERMINISTIC TURING
> MACHINES.
>
Where did you get that? Where did you quote from? From one of your
own volumes?
Interesting typo or omission by M. et. al.
Cryptographic stuff depends on P!=NP for its security. Now, even
NDTM's are real, P!=NP. But what security? Profoundly Confused. OR are
you saying that RSA is 'super NP', in other words, even NP problems
are solvable in P time (by those real NDTM's), RSA is still secure?
Or are you saying that NDTM's can not solve NP problems in P time?
I hope you are not calling NDTM's pieces of crap. :) That would truly
offend a lot of people including their inventors. :)
Why do we need that kind of convolution? Why not just stick with
DTM's which can at least solve in E time. Look at the problem of that H
function. See why I say 26 is NOT acceptable?
But I advise you to look at Idias's words:
The mechanism's existence (i.e. P=NP) trivially implies NP=coNP
^^^^^^^^^^^^^^^^^^^^
I guess the people who talk about the dependency of crypto efforts
on P!=NP must not know what they are talking about. Only you do. (Or
'we' do/does?)
> > I here also commit my understanding of the definition. As long as
> >the problem is solvable in polynomial time, be via DTM or NDTM, it is
> >in P.
>
> And this is equivalent (for people who know the correct definition of
> P and NP) to claiming P = NP.
I guess you are also a complexity theory super guru. Show us the
equivalence, which would be your daily cup of tea.
The quote did not say the extra words you gave. I do not have the
habit of putting my stuff in other people's mouths.
>
> I'm quite sure Ilias won't disagree with me (this time).
>
He won't!
Look at his words again (repetition never bores):
The mechanism's existence (i.e. P=NP) trivially implies NP=coNP
^^^^^^^^^^^^^^^^^^^^^
Surprise, isn't it? He agrees now with me!
He agrees with me; I contradict you; and you claim that he agrees
with you. Beautiful isn't it? More like this complicated issue, right?
> --
> Planar
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Help: a logical difficulty
Date: Thu, 07 Jan 1999 19:54:37 -0500
Mark Ingram wrote:
>
> Nicol So wrote:
>
> > On the other hand, a finite binary string can be interpreted as encoding a
> > natural number. If we order all finite binary strings in lexicographical
> > (dictionary) order, we can interpret the i-th string as encoding the integer i.
> > It is easy to see that the set of all finite binary strings has the same
> > cardinality as the set of natural numbers.
>
> Dictionary order, you say. So '0' comes before '00', which comes before '000', ...
> . What integer does the string '1' encode in this ordering?
My carelessness, thanks for catching it. I had a different ordering in
mind (the "increasing order") when I was writing the above, but decided
to just name a familiar ordering instead (thinking, mistakenly, it
wouldn't make a difference. I thought I was using too many words
already to explain something simple and explaining clearly what I meant
by "increasing order" wouldn't make things more concise).
Nicol
------------------------------
From: [EMAIL PROTECTED] (Gideon Yuval)
Subject: Re: One-time pads not secure ? (NSA's Venona project)
Date: 8 Jan 1999 01:06:50 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> 1. To cut down on the required number of pads, the Russians
> started re-using them, sending the same pad to two or
> even three different "channels" (military, intelligence,
> diplomatic). The Venona attack relied on collecting
...
It turns out that a single pad was sometimes used twice in _one_ message.
http://www.nsa.gov:8080/docs/venona/docs/May42/22_May_1942_p4.gif
is a classical example.
--
The opinions expressed in this message are my own personal views
and do not reflect the official views of Microsoft Corporation.
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Date: Fri, 08 Jan 1999 01:18:25 GMT
> How do you KNOW that any particualr realization of a physical process
> based on quantum theory is without bias?
Because you tune it to be without bias. You adjust the halflife you
expect to match the halflife you have, for example.
> I am not a physicist but
> even the quantum theory itself is yet a theory and not 100% without
> disputes, if I don't err.
Last I heard, QED was pretty darned solid. Verified to dozens of decimal
places and such.
Note, tho, that QED doesn't address nuclear decay. Also, the disputed in
QED, as far as I understand, are along the lines of "why" and not
"what."
--
Darren New / Senior Software Architect / MessageMedia, Inc.
"You could even do it in C++, though that should only be done
by folks who think that self-flagellation is for the effete."
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Date: Fri, 08 Jan 1999 01:23:28 GMT
> A patent? Hmm... Is that how our tax dollars are being wasted?
I fail to see what patents have to do with wasted tax dollars.
> Turbulence in a bulk fluid is not quantum mechanical at the
> macroscopic level, so I question whether it is random on that basis.
I was just pointing out that there are random processes that aren't QM
in nature, also.
> Chaotic, yes, but is it really random? There could be long wavelength
> correlations inherent in the geometry of a lava lamp that would
> introduce non-random features.
Not after you run the bitmap you photographed thru a cryptographic hash,
I would expect.
> >If you use electronics, yes.
>
> Radioactive measurements use electronics, unless you want to use a
> fluoroscope. :-)
I think a photomultiplier (or whatever one for beta decay measurement is
called) has enough amplification to not be affected by minor
fluctuations in the power feeding the coils.
And yes, you could use a fluroscope with a computer watching the screen,
for example. :>
Nuff said.
--
Darren New / Senior Software Architect / MessageMedia, Inc.
"You could even do it in C++, though that should only be done
by folks who think that self-flagellation is for the effete."
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Help: a logical difficulty
Date: Thu, 07 Jan 1999 20:33:42 -0500
Trevor Jackson, III wrote:
>
> Nicol So wrote:
>
> > Trevor Jackson, III wrote:
> >
> > > Also, is there are reason why name or description strings have to be finite?
> > > ...
> >
> > The reason you want a description to be finite is that you want to be able to
> > write it down, store it, communicate it, or do something useful with it. ...
>
> Of course. However, using a finite length string as a key imposes a length limit
> that a POTENTIALLY infinite length string does not. Thus using a finite string as
> the name for an infinite string has some (minor) benefit.
Unless you don't need to store or communicate them in their entirety,
infinite strings not capable of finite representation are really a
problem. If you need to talk about such a string, how would you
*unambiguously* tell someone exactly what it is?
> > > Why is the set of
> > > strings any larger than the set of string names?
> >
> > The short answer is: Cantor's diagonalization argument.
> >
> > ...
>
> Duh. Is is really necessary to use the diagonalization construct to prove that a
> the cardinality of the set of FINITE strings is not the same as the cardinality of
> the set of INFINITE strings?
I think it is. See my reason below.
> ... Hardly. This is simply a problem of definition.
> Aleph-null v. Aleph-one.
It is easy to see that the set of all finite strings has cardinality
aleph-0. It is just about as easy to see that the set of all infinite
strings and the continuum are equipotent. But how did you arrive at the
conclusion that the continuum is aleph-1? I think the Continuum
Hypothesis was open for a long time, and it was finally resolved that it
is independent of the usual axiomizations of set theory. But regardless
of whether you accept or reject the Continuum Hypothesis, you can still
prove that the continuum is not aleph-0.
(I don't want to pretend to know more about the subject than I do, so I
welcome correction.)
Nicol
------------------------------
From: [EMAIL PROTECTED] (Matt Brubeck)
Crossposted-To: sci.math,comp.theory
Subject: Re: coNP=NP Made Easier?
Date: Thu, 07 Jan 1999 18:00:16 -0800
rosi <[EMAIL PROTECTED]>:
>>> I first commit to what I adopt as the definition for the complexity
>>> class of P (which is quoted from "Handbook of Applied Cryptography" by
>>> Menezes et al):
>>> The complexity class P is the set of all decision problems
>>> that are solvable in polynomial time.
Planar:
>> Aha. Now we know where the problem is. The correct
>> definition of P would be more like this:
>>
>> The complexity class P is the set of all decision problems
>> that are solvable in polynomial time BY DETERMINISTIC
>> TURING MACHINES.
rosi <[EMAIL PROTECTED]>:
> Where did you get that? Where did you
> quote from? From one of your own volumes?
I'm afraid that Planar is correct here. "NP" is defined as follows:
nondeterministic polynomial time (NP): A set or property of
computational decision problems solvable by a nondeterministic
Turing Machine in a number of steps that is a polynomial
function of the size of the input. The word "nondeterministic"
suggests a method of generating potential solutions using some
form of nondeterminism or "trial and error". This may take
exponential time as long as a potential solution can be
verified in polynomial time.
NP is obviously a superset of P (polynomial time problems
solvable by a deterministic Turing Machine in polynomial time)
since a deterministic algorithm can be considered as a degenerate
form of nondeterministic algorithm. The question then arises:
is NP equal to P? I.e. can every problem in NP actually be solved
in polynomial time? Everyone's first guess is "no", but no one
has managed to prove this...
My source is Dennis Howe's Free On-line Dictionary of Computing at
<http://wombat.doc.ic.ac.uk/foldoc/index.html>. It gives the same
definitions which I've always seen for P and NP in other references (I'd
cite more sources, but don't have any others immediately at hand).
> Interesting typo or omission by M. et. al.
When defining the class P, I often see references omit the exact
definition of the algorithm or machine which must solve the problem in
polynomial time. Strictly speaking, P is the class of problems solved in
polynomial time by DETERMINISTIC TURING MACHINES. The "Handbook" failed to
mention this. Apparently you were an unwitting victim of Menezes and
company's editorial oversight.
Of course, you should have suspected the problem. Given your definition of
P, it would be obvious that P=NP, and one of the most famous open problems
of mathematics would be reduced to a triviality.
rosi:
>>> I here also commit my understanding of the definition.
>>> As long as the problem is solvable in polynomial time,
>>> it is be via DTM or NDTM, in P.
Planar:
>> And this is equivalent (for people who know the correct
>> definition of P and NP) to claiming P = NP.
rosi:
> I guess you are also a complexity theory super guru. Show
> us the equivalence, which would be your daily cup of tea.
> The quote did not say the extra words you gave. I do not
> have the habit of putting my stuff in other people's mouths.
I don't claim to be a "guru," nor am I accusing you of misquoting anyone,
but the definition given in "Handbook of Applied Cryptography" was not
complete. This appears to be the source of the misunderstanding here.
Through no fault of your own, you have been using an incorrect definition
for P.
With that confusion cleared up, hopefully you can continue your argument
using the same definitions as your colleagues.
Matt Brubeck
------------------------------
** 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
******************************
