Cryptography-Digest Digest #567, Volume #9 Wed, 19 May 99 19:13:02 EDT
Contents:
Re: symmetric boolean functions (Medical Electronics Lab)
Re: PK Security (Patrick Juola)
Re: Biprime Cryptography, Part II (David A Molnar)
Re: symmetric boolean functions ("Ted W.")
Re: Cryptonomicon Review ("Alan J. Robinson")
Re: Can Somebody Verify My DES execution? (Paul Koning)
Re: where can i find a frequency list? (Paul Koning)
Re: Reasons for controlling encryption (Nathan Kennedy)
Re: Cryptonomicon Review (wtshaw)
Re: Encryption starting ([EMAIL PROTECTED])
Re: Can Somebody Verify My DES execution? (Eric Cordian)
Re: prime numbers and the multplicative inverse (John Savard)
Re: Diophantine equations (David A Molnar)
Re: Hash Program (Jim Dunnett)
Re: Scramdisk/Norton query (Jim Dunnett)
Re: Reasons for controlling encryption (Doug Stell)
----------------------------------------------------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Crossposted-To:
sci.chem,sci.econ,sci.image.processing,sci.electronics.design,sci.physics,sci.physics.fluid-dynamics,sci.math
Subject: Re: symmetric boolean functions
Date: Wed, 19 May 1999 12:21:59 -0500
Hankel O'Fung wrote:
> Thanks for your help, but please forgive my ignorance. What are the
> definitions of Trace() and GF(2^n)? I am also interested in any textbooks
> or journal papers that point to the application of the function you
> mentioned. Any suggestions?
GF(2^n) means "Galois Field of n vectors in range {0,1}" Same thing
as you wrote {0,1}^n (kind of).
The Trace(g) = g^2^0 + g^2^2 + g^2^3 + ... + g^2^n.
In a "normal basis" this is just the parity function (already mentioned
in a previous message by someone else).
Any text on number theory should cover it. I'll shamelessly plug
my book too :-) check out http://www.manning.com/Rosing
> BTW, forget the sigma. By "symmetric" I just mean that f(x1, x2, ..., xn)
> = f(y1, y2, ..., yn) for ANY rearrangement y1, ..., yn of the n boolean
> variables x1, ..., xn. For n=3, this means f(x1,x2,x3) = f(x1,x3,x2) =
> f(x2,x1,x3) = f(x2,x3,x1) = f(x3,x1,x2) = f(x3,x2,x1).
I get ya. Any linear system will do that, any sums of equal powers
and mixings of equal terms and powers will also do that. So the
number of combinations is infinite. For example:
f() = sum(prod(x_i)^j) for all i and as many j's as you like.
Multiplication is taken over the field in question, sum is just XOR.
Sorry, might be a bit more than you need :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: PK Security
Date: 19 May 1999 14:16:11 -0400
In article <[EMAIL PROTECTED]>,
Mark E Drummond <[EMAIL PROTECTED]> wrote:
>Realising that this has much to do with key-length and the algorithms
>used, in a general sense, how secure is public key cryptography today?
>iow, how secure is a message that has been encrypted using my Verisign
>certificate (1024 bit key)?
>
>I know of at least one person who insists that with "modern technology",
>Public-Private key cryptography is moot. I continue to argue otherwise
>but I'd like to hear the opinions of some of the experts on this feed.
Well, it's certainly not moot and probably never will be; as long
as there are problems which are harder to invert than to solve
directly, the possibility of a private/public key encryption will
exist.
1024 bit keys are still believed to be secure against any attacks
that non-mythological opponents can make. Depending on whether
you believe that NSA is staffed by human beings or by demigods from
parallel dimensions, you may or may feel reassured by this statement.
But they're secure against any practical civilian attacks. The
cracks are starting to appear in 768-bit keys....
-kitten
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Biprime Cryptography, Part II
Date: 19 May 1999 18:48:19 GMT
John Savard <[EMAIL PROTECTED]> wrote:
> The alternative to it, whose patent has already expired, can be termed
> the MEPG algorithm (Mutual Exponent Product Generation), a special
Please not this particular acronym. It's too close to MPEG and it's
hard to pronounce.
-David Molnar
------------------------------
From: "Ted W." <[EMAIL PROTECTED]>
Crossposted-To:
sci.chem,sci.econ,sci.image.processing,sci.electronics.design,sci.physics,sci.physics.fluid-dynamics,sci.math
Subject: Re: symmetric boolean functions
Date: Wed, 19 May 1999 11:15:03 -0700
Hankel O'Fung wrote:
> Thanks a lot, Ted and Russell. Yes, the parity function and the
> (multiple) AND and (multiple) OR operators are good examples. Are there
> any examples that looks more "strange" (or less classical)? For example,
> a symmetric or shift-invariant boolean function whose output is not
> boolean but may take more than two values (that's why I considered also
> f:{0,1}^n --> (0,1)^n).
> Regards, Hankel
Strip the phase information from the Fourier Transform and it
becomes shift invariant.
f(x1,x2,x3,...,xN)={u1,u2,u3,...um}
um = 1/N Abs( SumOverl ( xl exp[ i * 2 Pi * l * m ]))
This has many applications, see "power spectral density" for example.
-Ted W.
------------------------------
From: "Alan J. Robinson" <[EMAIL PROTECTED]>
Subject: Re: Cryptonomicon Review
Date: Wed, 19 May 1999 14:51:45 -0500
Reply-To: [EMAIL PROTECTED]
Terry Ritter wrote:
>
> On Mon, 17 May 1999 15:32:47 -0500, in <[EMAIL PROTECTED]>,
> in sci.crypt "Alan J. Robinson" <[EMAIL PROTECTED]> wrote:
>
> >[...]
> >The breaking of the Enigma code for German U boat messages was of such
> >overwhelming importance to the Allied war effort because of staggering
> >losses of supply ships from the U.S, that when the Enigma code was
> >finally broken in early 1943, Churchill mounted a DISINFORMATION
> >campaign so that the Germans would not realize the code had been
> >cracked.
>
> Disinformation is an expected part of cryptography / intelligence. We
> don't tell the other side when we break their ciphers. In fact we run
> dangerous intelligence ops so it will seem that we got what we got in
> some other way just so they *won't* change their cipher. Which tells
> us how important it is for *us* to change *our* ciphers, whether we
> *know* they are broken or not.
>...
I didn't go into all the evidence here, because after all this is
SCI.crypt,
but apparently there were unique aspects of the Enigma disinformation
campaign which had ended up being at least partially responsible for
some
unanticipated and far-reaching effects on western society after WWII.
It's a story that still needs to be fully researched by scientific
historians.
Because I don't live in England I don't have access to the PRO info.
> >research field in particular, operations research/management science
> >flourished after the war because its originators falsely believed that
> >their techniques had helped win the war.
>
> The book "The Pleasures of Counting" by T. W. Korner (Cambridge Press,
> 1996) has a number of chapters which seem to be "operations research"
> and which do make a pretty good case for having improved various
> aspects of the conduct of the war.
This is very suspect... One of the funny things was that when private
industry tried to use OR/MS techniques after WWII, they very rarely
could make
them work. In fact, the whole field of OR/MS had been largely abandoned
between 1970 and 1980 because of its inability to produce useful
results.
When I read the footnote in the book in 1980, I went to the management
of
my company and told them about it. Several days later I found out that
they
themselves had decided some weeks earlier to abolish the OR/MS
department
because of lack of results. Talk about a coincidence!
But the effects of this disinformation campaign were much more
wide-reaching
than just OR/MS.
AJR
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Can Somebody Verify My DES execution?
Date: Tue, 18 May 1999 18:00:35 -0400
Thomas Pornin wrote:
> ...
> The DES standardization paper should include some test vector.
Strangely enough, it does not.
On the other hand, there's an exhaustive set of test vectors
in NIST Special Publication 800-17. Exhaustive in the sense
that it tests every significant aspect of the algorithm, for
example every S box entry.
paul
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: where can i find a frequency list?
Date: Tue, 18 May 1999 18:06:38 -0400
Pete wrote:
>
> dear all,
>
> i used to have a book that had marvellous frequency tables, digraphs,
> double letters, etc. the book was stolen from me a long, long time ago
> and i can't remember what the title was.
>
> i looked in the faq, and the faq doesn't really answer the question.
>
> can someone point me to frequency tables on the net? if none exist (that
> are known) can you point me to a book with a decent one?
Cryptanalysis, by Helen Fourche Gained. Dover publishes a reprint
of it. Nice inexpensive intro of pre WW2 vintage. Plenty of frequency
tables in the back.
paul
------------------------------
From: Nathan Kennedy <[EMAIL PROTECTED]>
Subject: Re: Reasons for controlling encryption
Date: Thu, 20 May 1999 05:03:26 +0800
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
"Markku J. Saarelainen" wrote:
>
> I have heard various reasons why commercial encryption is being
> controlled and what real motives are behind these control maneuvers. I
> would like to learn more what you think that real motives behind many
> encryption control issues are and how, if true, this might be tied to
> some commercial and business interests.
Simple. The real motives behind encryption control is that
government intelligence agencies want to know what you're
saying, and crypto prevents that to an extent.
Nate
=====BEGIN PGP SIGNATURE=====
Version: GnuPG v0.9.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org
iD8DBQE3Qybr8WKagKsEr/ERAvfBAKCM5TAmX4TFaCKhNW/lRM2c3D/qIwCggVKf
b/YeBuvom9nBCEGqbTo7XuM=
=8XfT
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Cryptonomicon Review
Date: Wed, 19 May 1999 15:55:22 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>
> .... Thus the
> determining factors of economics are, at least in a large part,
> essentially 'irrational'. Attempting to model irrationality with
> mathematics which is rational is doomed to failure, I believe.
>
A government professor I once had said, "If you could lay all the economic
experts end on end, you should leave them there."--B. M. Forbes, 1965.
Lady Luck shelters a mean right cross.
--
Weathermen prosphesize and insurance companies predict, while both pretend to be doing
the other to get an audience.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Encryption starting
Date: Wed, 19 May 1999 21:40:41 GMT
In article <7huc8r$v2l$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>
> > I am relatively new in encryption, and I'm looking for a good start
to
> > medium level encryption book just to get me a good start. I know
the basic
> > concept such as stream ciphering and block ciphering, but I need
more in
> > depth detail. Anyone have any good suggestions? Thank you very
much.
> >
> >
>
> Read sci.crypt first, lots of good easy info. Then try to find AC
Yes, read the group, but don't post "better" algorithms that you think
that you just invented.
> (Applied Cryptography) from Scheiner (see www.counterpane.com, sorry
if
> the name is spelt wrong).
Applied Cryptography is indeed an excellent book, but as the name
suggests, it is intended mostly for people who want to implement a
specific protocol or algorithm. It lacks the mathematical rigor of say
_Cryptography: Theory and Practice_ or _The Handbook of Applied
Cryptography_, although it is very useful as a reference book, say when
you forget how to do a blind signature scheme.
Then try to read some papers. I have many
> easy read papers (tea, xtea, rc5, rc6, blowfish, etc...) that I could
> send you.
The easy to read papers are nearly as helpful as the more difficult to
read ones. You might get an intuitive sense of the design elements that
make an algorithm "good" (ex. large S-boxes) but you won't gain any
more understanding of why these elements make an algorithm secure.
>
> Just play with ideas, and you will see how they are good/bad.
You will most probably *not* see whether your ideas are good or bad.
Rather, you will think that it is great, post it to the world, annoy
many people, and someone will find a problem with it.
>Try to
> explain an algorithm, and the theory behind it. For example recently
I
> learnt about multiplication in prime groups, and primitive exponential
> generators. (in IDEA and SAFER)
I think you need to clarify your understanding of the relationships
among fields, groups, and rings. You can't use the terms without regard
for their definition...
A set and an operation is called a group if the set is closed wrt to
the operation, there is an identity element such that when any element
in the set is combined with this element it is not changed, and every
element has an inverse such that the identity element is obtained when
the an element and its inverse are operated upon.
I really don't feel like going into fields and rings, but suffice it to
say, a field imposes stricter properties on the structure than a ring.
>
> Tom
>
> --
> PGP public keys. SPARE key is for daily work, WORK key is for
> published work. The spare is at
> 'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
> 'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
>
> --== Sent via Deja.com http://www.deja.com/ ==--
> ---Share what you know. Learn what you don't.---
>
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
From: Eric Cordian <[EMAIL PROTECTED]>
Subject: Re: Can Somebody Verify My DES execution?
Date: Tue, 18 May 1999 15:44:19 GMT
Matthias Bruestle <[EMAIL PROTECTED]> wrote:
> Are there test vectors for wrong implementations?
> E.g. "You got this vector, so you did not convert this into the
> correct endianness."
There are a variety of published test vectors you can find on the web.
As far as I know, there are no diagnostic test vectors, which specifically
illuminate the exact problem in ones code.
The easiest way to debug a DES implementation is to print out the key
schedule and the output of each round. Then, using the S-boxes and
permutations, you can check the algorithm by hand and see where the
problem lies.
--
Eric Michael Cordian 0+
O:.T:.O:. Mathematical Munitions Division
"Do What Thou Wilt Shall Be The Whole Of The Law"
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: prime numbers and the multplicative inverse
Date: Wed, 19 May 1999 18:25:26 GMT
Bob Silverman <[EMAIL PROTECTED]> wrote, in part:
>He phrased the question with respect to fields, but perhaps
>he meant more general modular arithmetic with respect to a prime vs.
>non-prime modulus?
That is exactly what he meant, and I noted that - and my misuse of the
term "field" - in a response to your answer to him.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Diophantine equations
Date: 19 May 1999 22:12:49 GMT
Alan J. Robinson <[EMAIL PROTECTED]> wrote:
> But I would be very interested in hearing about solving such equations
> from the mathematical and cryptographic literature.
You are correct in noticing that linear congruential generators give rise to
linear programming / diophantine problems. What may not be immediately obvious
is that while the general integer linear programming problem is NP-complete,
LCGs give rise to a very easy to solve subset of these problems.
The crucial observation is that you can construct a lattice from the outputs
of an LCG whose shortest vector corresponds to the seed of the generator.
Then you can prove that each of the vectors in the lattice is unique within
a ball of exponentially large radius (in the dimension of the lattice).
There is an algorithm, the Lenstra, Lenstra, and Lovas algorithm, which
will solve for the shortest vector approximate within some ball with exponential
radius, but a radius can be made smaller than the radius for which vectors
are unique. This algorithm runs in polynomial time.
So LLL only gives you an approximate answer, but for LCGs it's good enough because
you know there's only one possible lattice point within that radius...and that's
the seed. or something which will let you predict the generator, anyway.
Lattices aren't the only way to solve the problem, but they are sort of nice
if you are partial to linear algebra.
Daniele Micciancio, at MIT, has a paper which shows how to cryptanalyse an LCG
even when the whole output is not known :
http://theory.lcs.mit.edu/~miccianc/papers/dss.ps
He also has a problem set which describes a slightly different method of
attack from the one I outlined
http://theory.lcs.mit.edu/~miccianc/6876/ps1.ps
Antoine Joux has a more general overview of lattice attacks on
http://www.dmi.ens.fr/~stern/data/JS94.ps
which includes an attack on a truncated random number generator
that makes concrete the ideas contained in one of the more
annoying papers I have yet to read in my short little life.
You may also want to see Hugo Krawczyk's article on "How to Predict
Congruential Generators" in Journal of Algorithms 13 p.527-545 1992
for some mention of previous methods of accomplishing the task w/o
explicitly using lattices or LLL (particularly Joan Boyar).
Recently someone posted an implementation of Boyar's methods for
predicting an LCG. I regret that I can't locate it right now
(and along with it the correct spelling of the author's name..)
but will look for it if you're interested.
but uh, yeah, this seems to be an example of how comparatively
easy instances can exist even when the overall problem is
NP-hard.
-David Molnar
------------------------------
From: [EMAIL PROTECTED] (Jim Dunnett)
Subject: Re: Hash Program
Date: Wed, 19 May 1999 21:17:29 GMT
Reply-To: Jim Dunnett
On Tue, 18 May 1999 22:42:51 -0400, Boris Kazak <[EMAIL PROTECTED]>
wrote:
>Jim Dunnett wrote:
>>
>> Anyone know from where (or if) I can obtain an
>> MSDOS/Windows executable to 'distill' hardware
>> produced bits by 'hashing'?
>>
>> --
>> Regards, Jim. | Gouverner, c'est choisir.
>> olympus%jimdee.prestel.co.uk |
>> dynastic%cwcom.net | - Duc de L�vis 1764-1830
>> nordland%lineone.net |
>> marula%zdnetmail.com |
>> Pgp key: pgpkeys.mit.edu:11371
>----------------------------------
> Try this, it works under DOS, reads a file, writes a file.
>time penalty of 255 modular multiplications.
>
Oh dear! Afraid I'm no good at math, and I don't
have a clue about C. Nor do I have a compiler.
Which is why I asked for a DOS/Win program.
Nonetheless, many thanks for taking the time to send
all that information, Boris. I will look at it, but I
have my doubts that I can do much with it, as it's
well above my head!
--
Regards, Jim. | Gouverner, c'est choisir.
olympus%jimdee.prestel.co.uk |
dynastic%cwcom.net | - Duc de L�vis 1764-1830
nordland%lineone.net |
marula%zdnetmail.com |
Pgp key: pgpkeys.mit.edu:11371
------------------------------
From: [EMAIL PROTECTED] (Jim Dunnett)
Subject: Re: Scramdisk/Norton query
Date: Wed, 19 May 1999 21:17:28 GMT
Reply-To: Jim Dunnett
On Tue, 18 May 1999 09:12:12 GMT, [EMAIL PROTECTED] wrote:
>Go to your dos prompt.
>c:
>cd c:\recycled
>dir
>
>Do you see any files of those sizes?
>
>Mount your encrypted drive (Let's call it N)
>n:
>cd n:\recycled
>dir
>
>Do you see any files of those sizes?
>
>Maybe you aren't missing any space and Norton just doesn't know they are
>gone, and it stores the information somewhere else.
>
>I'm not sure what you did exactly nor where those files "appear".
If you must use Norton, then turn off the 'Protection'
for deleted files.
In a crypto screnario this facility is bloody dangerous!
--
Regards, Jim. | Gouverner, c'est choisir.
olympus%jimdee.prestel.co.uk |
dynastic%cwcom.net | - Duc de L�vis 1764-1830
nordland%lineone.net |
marula%zdnetmail.com |
Pgp key: pgpkeys.mit.edu:11371
------------------------------
From: [EMAIL PROTECTED] (Doug Stell)
Subject: Re: Reasons for controlling encryption
Date: Wed, 19 May 1999 22:33:25 GMT
On Wed, 19 May 1999 10:41:11 -0700, "Markku J. Saarelainen"
<[EMAIL PROTECTED]> wrote:
>I have heard various reasons why commercial encryption is being
>controlled and what real motives are behind these control maneuvers. I
>would like to learn more what you think that real motives behind many
>encryption control issues are and how, if true, this might be tied to
>some commercial and business interests.
The stated reasons I've heard from the NSA are the following. The
first few are laudable goals, although impossible to achieve and under
assumptions that are not true in the modern world.
Keep the good stuff out of the hands of terrorist organizations for
national security reasons.
Keep the good stuff out of the hands of organized crime for law
enforcement reasons.
Keep usage to a minimum, so that they know who the above two
categories are.
Stonewall as long as possible to keep usage to a minimum.
Not be found not doing their job, should anything bad happen. (I don't
remember the original wording, but it was very good.)
Protect existing organizations and positions of power.
------------------------------
** 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
******************************
