Cryptography-Digest Digest #529, Volume #11 Tue, 11 Apr 00 13:13:01 EDT
Contents:
Re: Crypto for embeded platforms? ("Douglas A. Gwyn")
Re: Encryption in Software... (Kent Briggs)
Quantum Teleportation ( Doug Goncz)
Re: Equivalent permutation polynomials ("Douglas A. Gwyn")
Re: Encode Book? (James Felling)
Re: Is AES necessary? (Bob Silverman)
Re: Factoring Composite Numbers (Bob Silverman)
Re: Equivalent permutation polynomials (James Felling)
Re: Checksum for digits (Michael J. Fromberger)
Re: skipjack F function (John Savard)
Re: Skipjack algorithm. (Brian K. Ogilvie)
SECAN (Pascal Nourry)
Re: Q: Entropy (Tim Tyler)
Re: Quantum Teleportation ("Douglas A. Gwyn")
Re: Schoof's Algorithm (Mike Rosing)
Re: are self-shredding files possible? (Paul Koning)
Re: GSM A5/1 Encryption (Paul Koning)
Re: strength of altered vigenere cipher? (Paul Koning)
----------------------------------------------------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Crypto for embeded platforms?
Date: Tue, 11 Apr 2000 14:32:12 GMT
Paul Rubin wrote:
> A lot of times you have to try different variants til you get the best
> code out of your compiler. Sometimes a[i] doesn't work as well as *(a+i), etc.
> Maybe it's best to just write a small reference implementation in C
> and don't worry about careful optimization. That should be done in asm anyway.
Indeed, I wouldn't recommend worrying about such micro-optimizations
such as *(a+i) for a[i] etc. Any decent modern C compiler is able to
perform these, and many other, optimizations automatically. The best
approach is to write a simple, clean implementation of the algorithm,
optimizing only aspects of the *design* (e.g. use look-up tables if
ROM is available) that a compiler wouldn't be able to do for you.
------------------------------
From: Kent Briggs <[EMAIL PROTECTED]>
Subject: Re: Encryption in Software...
Date: Tue, 11 Apr 2000 14:56:27 GMT
Paul Koning wrote:
> Kent Briggs wrote:
> >
> > Simon Johnson wrote:
> >
> > > Hasn't the export restriction been lifted?
> > >
> > > Or is that on Two_Fish?
> >
> > The U.S. export restrictions were loosened considerable in January but
> > exported software over 64 bits in strength still requires a blessing
> > from the BXA.
>
> Not necessarily. In some cases all that is needed is notification
> rather than approval.
By "software", I was referring to compiled, commercial encryption
applications. Just posting source code is a different matter.
--
Kent Briggs, [EMAIL PROTECTED]
Briggs Softworks, http://www.briggsoft.com
------------------------------
From: [EMAIL PROTECTED] ( Doug Goncz )
Subject: Quantum Teleportation
Date: 11 Apr 2000 15:11:59 GMT
I have read the Scientific American and other articles on quantum
teleportation. Briefly, the state of a particle can be transmitted to another
particle by sending a message from the location of the first particle
describing an operation to be performed on the second particle that will result
in the second particle adopting the state of the first. The first and second
particles must be entangled, and there is no implication of transmitting the
required message faster than light. The message transmission in a physics lab
is usually just another particle. A phone, the internet, or a spaceship could
all be used to carry such a message. Since the particles involved have no
significant properties other than their state, the resulting particle is
completely identical to the first. It is indistinguishable.
There are interesting implications to cryptography and cryptography. The
message says something like "hit it with a hammer". To an interested party
intercepting the message, it is meaningless, or to parody politically correct
language, meaning-free. Clearly it's transmission without knowledge. Even if
the interested party hits their sample particle with the hammer, it won't adopt
the state of the first particle with any significant probability. Their
particle isn't entangled with the first one, that's the reason.
The genetic code of all living things is "sort of" transmitted without
knowledge. We certainly don't know explicitly the full DNA sequence of even a
single individual. That work is in process. Various viruses have been
completely coded. I don't think anyone's every synthesized a virus from such a
code.
My twenty year and continuing obsession is with self reproducing machine tools,
which have some relations to living things. I am working on compact notation
and the computability of construction sequences. I have almost twenty years of
machining experience.
Can any of you here make any connections between these four topics?
I hope I'm not way OT, and that this isn't too speculative. If so, might you
direct me? I saw very little in sci.crypt.research the other day. Like three
posts.
Please feel free to go way out there. I'm interested in novel insights as well
as anything well recognized. I can certainly look up any references at the
university library. I'll take your suggestions that seriously, I promise. This
is not idle chatter.
Yours,
Doug Goncz
Experimental Machinist
Replikon Research
Seven Corners, VA 22044-0394
What I'm into:
http://www.deja.com/profile.xp?[EMAIL PROTECTED]*
Home Page (1999-11-24):
http://members.aol.com/DGoncz
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Equivalent permutation polynomials
Date: Tue, 11 Apr 2000 15:00:15 GMT
Tom St Denis wrote:
> F(x) = 0 + 3x + 5x^2 + 0x^3 + 7x^4 + 0x^5 [mod 16]
> F(x) = 0 + 11x + 13x^2 + 0x^3 + 7x^4 + 0x^5 [mod 16]
> Now for you math gurus this is probably a joke, but why are these two
> polynomials congruent?
> BTW: they both create [0, 15, 10, 13, 12, 3, 6, 1, 8, 7, 2, 5, 4, 11,
> 14, 9] as the output [when stepping from F(0)..F(15)].
Call the second one G(x).
Consider D(x) = G(x)-F(x) = 8x(1+x) [mod 16].
D(i+1) = D(i) + 16(i+1) = D(i) [mod 16],
so all D(i) = D(0) = 0. I.e., F(i)=G(i) for all i.
The key is that that the coefficients differ by 0 or 8,
which is half of 16..
I don't know if there is any deep significance.
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Subject: Re: Encode Book?
Date: Tue, 11 Apr 2000 10:23:27 -0500
Tom St Denis wrote:
> Paul Rubin wrote:
> >
> > Tom St Denis <[EMAIL PROTECTED]> wrote:
> > >I can sum up my gut reaction for you with "bite me". I can see being
> > >busy and not posting often such as some "specialists". But I have yet
> > >to hear anything from her, or see anything she has done. The "paper" I
> > >saw of hers was second hand thru some media thingy...
> > >
> > >I couldn't give a rats azz if she were female, male, or a martian, the
> > >fact she does not maintain *any* public discussion or etc, shows me that
> > >she is not really in the field, or just shy...
> >
Actually I have read two of her papers on the web( I don't remember the URLs
though -- it was a couple of months ago)
She writes well reasoned and thourough papers. True she is not incredibly
active, but she does produce output.
>
> > Come to think of it I haven't seen anything here on the ng lately
> > by Shamir, Knudsen, Simmons, etc. etc. either. You just aren't looking
> > in the right places.
>
> Adi Shamir did Twinkle did he not?
I don't, however, recall him writing any posts to the group in re: that. If we
count that we are forced to count the media induced posings in re: her media
debut.
>
> Knudsen did Serpent [with Biham et al] and some other papers related to
> AES
On the wweb, not the group.
>
> and I have never heard of Simmons
>
> Tell me again they haven't done anything lately?
>
> Tom
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Is AES necessary?
Date: Tue, 11 Apr 2000 15:35:21 GMT
In article <[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
>
>
> Mok-Kong Shen wrote:
> > 3DES is currently yet strong enough. If that's too weak, we could
> > use 5DES etc.
<snip>
>
> But won't these variants of DES just be in the same vain (sic) as
> AES?
No. The block length is longer for AES. and this is *important*.
> BTW I would tend to believe ciphers like RC6/Twofish/Serpent
> as way more securer [i.e harder to attack] then 3DES.
Oh so? I suggest you examine the amount of work needed to effect the
various attacks.
Also, (no flame intended) you don't have enough knowledge or experience
to be taken credibly when you say "I would tend to believe....".
Your *belief* is irrelevant. If you have an analysis to suggest what
you say is true, then present it.
Triple DES has effective security of 112 bits. However, the SPACE
needed to conduct a meet-in-the-mmiddle attack is massive. Such an
attack is totally impractical. The same applies to the various
linear and differential attacks on *all* symmetric ciphers.
(1) The space requirement is prohibitive making direct search as the
only realistic attack.
(2) Even if one could solve the space problem, where does one get the
very large number of (plaintext,ciphertext) pairs??? Even for single
DES, how do you propose to get an adversary to provide 2^46 such pairs?
--
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/
Before you buy.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Factoring Composite Numbers
Date: Tue, 11 Apr 2000 15:38:35 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
> "Nickolaus Benjamin Padgett" <[EMAIL PROTECTED]> wrote, in
> part:
>
> >2) The most basic of all factorization methods is to divide 'n' up
to the
> >sqrt('n'). If I were to further decrease this space by 99% so that
the
> >total space to search was 1% of sqrt('n') would this be a viable
decrease or
> >would this expectancy still be to great?
>
> That would still be too great, because the fast methods don't go up in
> time as n gets bigger by the same rate as the sqrt(n) method. Thus,
> for very big n,
You don't need "very" big. As soon as .01n^1/2 > 3 n^1/4, Pollard Rho
becomes faster. i.e. n > 81 * 10^8.
--
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/
Before you buy.
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Subject: Re: Equivalent permutation polynomials
Date: Tue, 11 Apr 2000 10:50:20 -0500
Tom St Denis wrote:
> I just discovered equivelent permutation polynomials. In my test I use
> this initial polynomial
>
> F1(x) = 0 + 3x + 5x^2 + 0x^3 + 7x^4 + 0x^5 [mod 16]
>
> And then I did all the modular inverse of the coefficients [mod 16] to
> get
>
> F2(x) = 0 + 11x + 13x^2 + 0x^3 + 7x^4 + 0x^5 [mod 16]
>
> Now for you math gurus this is probably a joke, but why are these two
> polynomials congruent? I was aiming for something else at the time and
> found this :)
It is simple why that is the case. ( I renamed them above to allow myself
to be clear).
F2(x) = F1(x) + P(x) mod 16.
Where P(x) = 8x + 8x^2 = 8(x + x^2)
Since x + x^2 is always even P(x) = 0 mod 16.
>
>
> BTW: they both create [0, 15, 10, 13, 12, 3, 6, 1, 8, 7, 2, 5, 4, 11,
> 14, 9] as the output [when stepping from F(0)..F(15)].
>
> Tom
------------------------------
From: Michael J. Fromberger <[EMAIL PROTECTED]>
Subject: Re: Checksum for digits
Date: 11 Apr 2000 15:41:55 GMT
In <8csfud$ml2$[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
>I'm writing an application where the user needs to enter a number of
>digits (>30) in a field and I need a good algorithm that can verify
>that the data the user has entered is correct. It should support
>variable checksum length and should detect as many faulty digits as
>possible. It's not necessary to detect which digits are incorrect.
>Thanks in advance!
>P.S. Please reply with e-mail as well.
>/Jesper Nordenberg
Hi there,
There is a good paper on decimal check digits in CACM:
Wagner, Neal R. & Putter, Paul S. "Error Correcting Decimal
Digits", CACM v. 32 n. 1, Jan 1989, p. 106.
This paper surveys several prevalent digit checksumming techniques,
and provides a good account of their strengths and weaknesses.
Cheers,
-M
--
Michael J. Fromberger Software Engineer, Thayer School of Engineering
sting <at> linguist.dartmouth.edu http://www.dartmouth.edu/~sting/
OfUb/Q/gvcIAtVDQ7kbZelrae4GIXJT8mmn38wXEpdUjthIOaDBPen8LcEij9zNFJzRNoe0W
Keep America beautiful; swallow your cigarette butts.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: skipjack F function
Date: Tue, 11 Apr 2000 16:07:51 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote, in part:
>Where can I get a copy of the Skipjack F function? I was in the midst
>of copying it from the badly scanned paper [I found somewhere] but I
>mistook the 'e' for 'c's and I am really peeved...
When I copied the table for my own web site, I checked on the e's and
c's by making sure there were no duplicates in the table with a
computer program.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Brian K. Ogilvie)
Subject: Re: Skipjack algorithm.
Date: 11 Apr 2000 12:15:00 -0400
[EMAIL PROTECTED] (John Savard) writes:
>
> I remember Bruce Schneier saying that attempting to extend the length
> of its keys would be unsafe.
Certainly the work of Biham, Biryukov, and Shamir on "Cryptanalysis of
Skipjack Reduced to 31 Rounds using Impossible Differentials" would
lead one to believe that the full Skipjack cipher has only 80-bits of
strength and the key size and algorithm strength were "balanced" by
NSA in its design. Their work shows clearly that Skipjack does not
have a large overdesign safety margin and gives 80-bit strength with
80-bit keys.
--
Brian K. Ogilvie
[EMAIL PROTECTED]
(You know what to do, right?)
------------------------------
From: Pascal Nourry <[EMAIL PROTECTED]>
Subject: SECAN
Date: Tue, 11 Apr 2000 18:36:32 +0200
Reply-To: [EMAIL PROTECTED]
Hi,
I am trying to found some information about SECAN security evaluation in
NATO context.
Is someone can help me ?
Thanks.
PN
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Reply-To: [EMAIL PROTECTED]
Date: Tue, 11 Apr 2000 16:25:48 GMT
[EMAIL PROTECTED] wrote:
: [EMAIL PROTECTED] wrote:
:> Calculating entropy generally runs into the Halting problem.
[...]
:> *Proving* that these programs don't halt and output your target
:> sequence can be "a little bit tricky". See the work of G J Chaitin
:> (http://www.cs.auckland.ac.nz/CDMTCS/chaitin/) for more about this.
: Hi, you might enjoy my latest paper
: "A century of controversy over the foundations of mathematics".
: You can find it at http://www.cs.umaine.edu/~chaitin/cmu.html
Hmm. Wow. Until just now I was completely unaware of your results
dealing with your unknowable Omega.
The page made me giggle as well. It's good to see famous folk saying
stuff like:
``I think logicians hate my work, they detest it! And I'm like
pornography, I'm sort of an unmentionable subject in the world
of logic, because my results are so disgusting!''
;-)
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Be good, do good.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Quantum Teleportation
Date: Tue, 11 Apr 2000 16:07:14 GMT
Doug Goncz wrote:
> There are interesting implications to cryptography and cryptography.
I don't think quantum teleportation has any direct bearing on
cryptography. However, quantum cryptography is a contemporaneous
development based on many of the same concepts.
> The genetic code of all living things is "sort of" transmitted without
> knowledge.
But that's not much related to quantum teleportation or cryptography.
> My twenty year and continuing obsession is with self reproducing
> machine tools, ...
What I like is the notion of using remote actuators to build smaller
machine shops, including smaller actuators, recursively..
> Can any of you here make any connections between these four topics?
I don't think there are especially close connections.
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Schoof's Algorithm
Date: Tue, 11 Apr 2000 10:58:13 -0500
Robert Harley wrote:
> If you have an algebra package like GP/PARI, you can do this:
>
> ------------------------------------------------------------------------------
> #
> prec=100;
> a=sum(n=1,prec-1,sigma(n,3)*q^n)+O(q^prec);
> b=sum(n=1,prec-1,sigma(n,5)*q^n)+O(q^prec);
> j=1/((1-(1-504*b)^2/(1+240*a)^3)/1728)
> ------------------------------------------------------------------------------
:-) Thanks, that's what I'm doing the hard way.
> Output is:
>
> ------------------------------------------------------------------------------
> time = 0 ms.
> time = 4 ms.
> time = 5 ms.
> time = 28 ms.
> %4 = q^-1 + 744 + 196884*q + 21493760*q^2 + 864299970*q^3 + 20245856256*q^4
> + 333202640600*q^5 + 4252023300096*q^6 + 44656994071935*q^7 +
> [...screenful of numbers deleted...]
> + 12831568450930566237049157191017104861217433634289960*q^97 + O(q^98)
> ------------------------------------------------------------------------------
I should get the same answer. Thanks, this will help me a lot.
And thanks Nigel and Michael, eventually I'll figure this stuff out.
The help is much appreciated.
Patience, persistence, truth,
Dr. mike
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: are self-shredding files possible?
Date: Tue, 11 Apr 2000 12:20:09 -0400
[EMAIL PROTECTED] wrote:
>
> With regard to ?self-shredding encrypted files , while it is difficult
> to see how a file could shred it itself, it is not so difficult to see
> how a key could revoke itself. ...
>
> (6) When asked to decrypt, pgp would query the server to see if the
> shared key were revoked ,and if so, refuse further decryption.
And what if you used a modified PGP that didn't query
the server, or if it did, ignored the revocation indication
Sorry, it still doesn't work, and it never will...
paul
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: GSM A5/1 Encryption
Date: Tue, 11 Apr 2000 12:15:29 -0400
[EMAIL PROTECTED] wrote:
> ...
> I would like your opinion as to what you think is a suitable ( "strong")
> stream cipher for something like a GSM crypto system. As I said in my
> previous post, one Euro company has developed a strong GSM crypto
> phone..but they are using a block cipher for some strange
> reason ( the only reason I can think of is that they are
> using a crypto core which has an embeded symmetric algo)...interested in
> your comments....
Why does it have to be a stream cipher?
Anyway, any block cipher can be turned into a stream cipher, that's
elementary stuff. So pick a good block cipher: 3des, idea, cast,
etc.
Alternatively, pick a stream cipher with a good reputation, such
as RC-4.
The way I look at this: one of the first things any good student of
crypto learns is that he isn't qualified to design a good cipher,
and won't be for many years if ever. Clearly, no good students of
crypto were involved in the A5 process, because they flunked that
test...
(They also never heard of the Kerckhoff criteria, apparently...)
paul
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: strength of altered vigenere cipher?
Date: Tue, 11 Apr 2000 12:24:33 -0400
Mok-Kong Shen wrote:
>
> [EMAIL PROTECTED] wrote:
> >
>
> > My question is: Is a Vigenere cipher, regardless of length,
> > uncrackable, if the key is as long as the message itself?
>
> The strength question has been answered by others. I just want
> to say that, if you want to use polyalphabetic substitution,
> then don't use Vigenere with all alphabets being shifted versions
> of one another but use so-called independent alphabets (i.e.
> the the characters of the alphabets are randomly ordered) and
> long keys.
That will only help a little. As soon as I get enough ciphertext,
I can determine the period (key length) and at that point the
problem reduces to that many simple substitution ciphers. If the
key length is less than 3% or so of the message length, you're
in trouble...
An interesting approach is to use Tom Jefferson's cipher device
instead, picking a different row each time. (See Kahn for a
description. Nice widget...)
paul
------------------------------
** 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
******************************
