Cryptography-Digest Digest #905, Volume #12 Thu, 12 Oct 00 18:13:00 EDT
Contents:
Re: A new paper claiming P=NP ("Magnus Lie Hetland")
Public Key Algorithms and Analysis ("Joseph Ashwood")
Re: NIST Random Generator Test Suite Results ("Cristiano")
naval code books were "weighted" (James Muir)
Re: Playfair Cipher Decoders... (JPeschel)
Re: Rijndael implementations (Mok-Kong Shen)
Voynich ("olivier Dubont")
Re: Voynich ("olivier Dubont")
Re: Voynich (Jim Gillogly)
Re: A new paper claiming P=NP (Robert Israel)
Re: Dense feedback polynomials for LFSR (zapzing)
Re: Bored with AES? SHA-256/384/512 spec now out! (Ian Goldberg)
Re: naval code books were "weighted" (jungle)
Re: A new paper claiming P=NP (Mike Oliver)
Re: Rijndael implementations (Paul Schlyter)
Re: naval code books were "weighted" (Jim)
Re: Code Book Cipher Challenge Cracked (Tim Tyler)
Re: naval code books were "weighted" (Jim Reeds)
Re: A new paper claiming P=NP (Mike Oliver)
Re: Bored with AES? SHA-256/384/512 spec now out! ("Joseph Ashwood")
----------------------------------------------------------------------------
From: "Magnus Lie Hetland" <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Thu, 12 Oct 2000 21:07:02 +0200
> You just repeated what I said. Asserting is the same as assuming.
> But it's not the conclusion, since it wasn't arguing that P != NP, but
> that the paper is wrong BECAUSE P != NP. I'm merely pointing that out.
The conclusion of the paper would be (among other things) that P=NP.
Finding an error would be to conclude that this has not been proven.
Assuming P != NP would be to assume that P=NP had not been (and
could not be) proven, no? I.e. assuming that the paper was wrong...
Which is what you wanted to prove... Or? (I'm probably just being
dim her...)
>
> So it's not assuming the conclusion.
>
OK...?
But you *did* assume that P != NP -- or didn't you? So, you were
possibly not assuming the conclusion, but the line of logic from your
assumption to your conclusion was *very* short...
"The paper claims Q. I want to find out whether the paper is correct.
Since Q is wrong, I conclude that the paper is wrong. QED."
Oh, well. I probably didn't understand what you meant, I guess. :)
--
Magnus Lie Hetland (magnus at hetland dot org)
"Reality is what refuses to disappear when you stop
believing in it" -- Philip K. Dick
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Public Key Algorithms and Analysis
Date: Thu, 12 Oct 2000 12:11:20 -0700
I've gotten to a point where I need at least some pointers to some papers.
I'm examining alternative public key encryption and/or signature algorithms
(alternative to RSA, DH, ECC, DSA, ECDSA). I am aware of a small handful
(LUC, XTR, NTRU, RPK), but finding analysis of these is proving daunting,
and I'd like to have more options. To expediate my search I figured I'd ask
around a bit, so does anyone have any reference on the ones I mentioned or
any others? (I've already found http://www.luc.co.nz, http://www.ntru.com).
I'd also of course appreciate avoiding sites I'd have to pay for (like the
LNCS location I found for XTR).
Joe
------------------------------
From: "Cristiano" <[EMAIL PROTECTED]>
Subject: Re: NIST Random Generator Test Suite Results
Date: Thu, 12 Oct 2000 21:21:44 +0200
> >> |At this moment I'm generating the expansion of e by myself
> >> |(this take about 5.5 hours), and then I'll generate the
> >> |expansion of pi.
> >>
> >> How do you calculate them?
>
> C> I use a routine to calculate BITS/3.31 digits of e (or
> C> pi). Then I convert these decimal digits in binary digits with
> C> multiplication by 2 by using a very long integer library.
> C> Suppose you want to convert 2.7182 in bits. Do the following:
> C> 2=10 7182*2=1 (because 14364 is > 10000) 4364*2=0 8728*2=1
> C> 7456*2=1 ... The sequence will be 101011. I don't know if
> C> there is a faster way to do this.
>
> What language and algorithms do you use to compute e and pi?
I use this C routine (**warning** UBYTE is unsigned long):
#include <math.h>
#include <string>
#define MAX 10000
typedef unsigned long UBYTE;
UBYTE *ESP_s,*x;
long xs,ts,i,ndigits;
static void add(UBYTE *ESP_s,UBYTE *x,long xs);
static void divide(UBYTE *x,long xs,long n,UBYTE *y,long *ys);
void EXP1(const int cifre)
{
ndigits=cifre+10;
ESP_s=new UBYTE[ndigits*2+2];
memset(ESP_s,0,(ndigits*2+2)*sizeof(UBYTE));
x=ESP_s+ndigits+1; ESP_s[0]=x[0]=1;
i=0;
do {
i++;
divide(x,xs,i,x,&xs);
add(ESP_s,x,xs);
} while(xs<=ndigits);
}
static void divide(UBYTE *x,long xs,long n,UBYTE *y,long *ys)
{
for(long i=xs,c=0;i<=ndigits;i++) {
c=c*MAX+x[i]; y[i]=c/n; c%=n;
}
*ys=xs; while(*ys<=ndigits && y[*ys]==0) (*ys)++;
}
static void add(UBYTE *ESP_s,UBYTE *x,long xs)
{
long i,c=0;
for(i=ndigits;i>=xs;i--) {
c+=ESP_s[i]+x[i];
if(c>=MAX) { ESP_s[i]=c-MAX; c=1; }
else { ESP_s[i]=c; c=0; }
}
i=xs;
while(c) {
i--; c+=ESP_s[i];
if(c>=MAX) { ESP_s[i]=c-MAX; c=1; }
else { ESP_s[i]=c; c=0; }
}
}
The sequence is stored in ESP_e.
I used the C-Lisp to check the correctness of algorithm for e.
> Could you check my own values (1000002 bits of e, computed by a
> quickly-written Lisp program)?
>
> bit position bit values [pos..pos+15]
> decimal octal
> 729024 2617700 0 1 1 1 1 0 1 1 0 0 0 1 0 1 0 0
0 1 1 1 1 0 1 1 0 0 1 1 0 1 0 0
> 729040 2617720 1 1 0 0 1 1 1 0 0 0 1 0 0 1 1 0
1 0 1 0 0 0 1 1 1 0 1 1 0 1 0 0
[...]
I found the differences showed below your sequence.
With your expansion of e the results are ok?
Your Lisp program put out the bit sequence or the digits of e? In the former
case can you show me the prog?
> What I have found so far in the NIST code are
> 1. The arrays stats[] and results[] in include/proto.h are too small.
> They are indexed 1..NUMOFTESTS and must be increased by 1:
> FILE* stats[NUMOFTESTS+1]; /* FILE OUTPUT STREAM */
> FILE* results[NUMOFTESTS+1]; /* FILE OUTPUT STREAM */
> 2. The computation of pi[] in OverlappingTemplateMatchings() is
> wrong.
> 3. In several places, NaN's are generated (both under Linux and
> Solaris) [this is what I have to track down]
What do you mean in point 2?
I have not changed the OTM test and the result I get is ok.
Perhaps you have some problems with lgam().
> You said you extensively modified the NIST code, so maybe you have
> found some other problems (beside the errors in rng.pdf, pp. 28--29)?
Some routine use this line to zeroing the vectors:
for(i = 1; i < powLen-1; i++) P[i] = 0;
I remember that in some case this line need to be replaced by
for(i = 0; i < powLen-1; i++) P[i] = 0;
I changed calloc with new and memset (when needed) and this problem
disappear.
I don't remember other problems.
Cristiano
------------------------------
From: James Muir <[EMAIL PROTECTED]>
Subject: naval code books were "weighted"
Date: Thu, 12 Oct 2000 19:22:51 GMT
I'm reading a paper in which the author explains that some cipher
systems used in WWII employed countermeasures to protect against the
seizure of key material. The author states for example that naval code
books were "weighted".
I suspected that this is "weighted" in the non-mathematical sense ( i.e.
the books were weighted so that they would sink to the bottom of the
ocean ), but I could be wrong.
Can anyone second my interpretation? or offer a correct one?
-James
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: Playfair Cipher Decoders...
Date: 12 Oct 2000 19:39:55 GMT
[EMAIL PROTECTED] writes:
>Can anybody recommend a good playfair Cipher solving program?
>{dos /Windows only please :-) }
Try Playfair.zip on the "Historical" page of my web site.
Some of the links to the other programs on this page
are broken, but the Playfair link now works.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Rijndael implementations
Date: Thu, 12 Oct 2000 21:54:03 +0200
Paul Schlyter wrote:
>
> David Eppstein <[EMAIL PROTECTED]> wrote:
> >In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> >
> >> This is what "byte" *should* mean in the first place. Having "byte"
> >> defined as "set of bits that represent a single character" seems like a
> >> really dumb idea to me.
> >
> >You've obviously never programmed a 36-bit architecture.
>
> ...or a 60-bit architecture...
CDC had for a very long time used 6 bits to represent
characters on its machines. However, I don't remember that
they called a group of 6 bits a byte in the manuals.
M. K. Shen
------------------------------
From: "olivier Dubont" <[EMAIL PROTECTED]>
Subject: Voynich
Date: Thu, 12 Oct 2000 21:39:25 +0200
I think the manuscript contains a initiatic path, with kabalistic jew
sentences
------------------------------
From: "olivier Dubont" <[EMAIL PROTECTED]>
Subject: Re: Voynich
Date: Thu, 12 Oct 2000 21:51:28 +0200
What i mean is that we should search in the initiatic match
between plants and planets. I think it's a spagyric book.
Spagyri is like Alchemy but with plants.
There is match too between planets and human body.
For example the heart match with sun
Plants like angelica archangelica or chelidonium majus or tifolia match
with Sun too.
All this is the contain of the Voynich manuscript
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Voynich
Date: Thu, 12 Oct 2000 20:43:02 +0000
olivier Dubont wrote:
>
> What i mean is that we should search in the initiatic match
> between plants and planets. I think it's a spagyric book.
> Spagyri is like Alchemy but with plants.
>
> There is match too between planets and human body.
>
> For example the heart match with sun
> Plants like angelica archangelica or chelidonium majus or tifolia match
> with Sun too.
>
> All this is the contain of the Voynich manuscript
If you'd like to discuss this theory with a number of Voynich researchers
who might understand your theory more than I do, you might like to join my
Voynich Manuscript mailing list -- if so, send me mail. Most members do
not read sci.crypt.
--
Jim Gillogly
Highday, 21 Winterfilth S.R. 2000, 20:41
12.19.7.11.5, 8 Chicchan 8 Yax, Ninth Lord of Night
------------------------------
From: [EMAIL PROTECTED] (Robert Israel)
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: 12 Oct 2000 20:41:56 GMT
In article <[EMAIL PROTECTED]>,
Mike Oliver <[EMAIL PROTECTED]> wrote:
>Given T a consistent finite collection of axioms in a recursively-presented
>language, T consistent, Q relatively interpretable in T. For any
>theorem s of T, let f(s) be the length of its shortest proof. Now
>let g(n) be the maximum value of f(s), where s ranges over all theorems
>of T having n or fewer symbols.
>Conjecture: g(n) grows faster than any primitive recursive function.
>Can anyone prove or refute?
Suppose there is a recursive function (never mind primitive
recursive) h(n) with g(n) <= h(n), and "Turing machine number x halts"
corresponds to a statement S(x) in the language, such that for each
positive integer n, S(n) is a theorem of the language iff Turing machine
number n halts. Then you would have an algorithm to check whether
Turing machines halt: if S(n) has N symbols, just check all possible
proofs of length <= h(N).
Robert Israel [EMAIL PROTECTED]
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Dense feedback polynomials for LFSR
Date: Thu, 12 Oct 2000 20:38:04 GMT
In article <8s385f$vdt$[EMAIL PROTECTED]>,
Joaquim Southby <[EMAIL PROTECTED]> wrote:
>
> As to the original question, the Hughes XPD device does something
similar
> to what was asked -- an input to the device chooses both a particular
tap
> sequence and an init vector. Someone else mentioned this technique as
> having the key be an index into a list of possible tap sequences.
This
> could be workable as long as the list is held very closely -- once it
is
> compromised, a large portion of your encipherment scheme is broken.
Well you would still have the key bits of security
that index the table. But I was thinking more in
terms of having the tap sequence be dense at about
50% ones and 50% zeros. The the tap sequence would
actually be the key. The key space would not be "flat"
since not all tap sequences represent primitive
polynomials, but then you would not have to carry
around a look up table, either. On the other hand
you could not specify any key, you would have to
use a key generation program.
BTW I also agree that raw LFSRs should not be used.
I think that the typical techniques of combining
them should be made all the stronger if the taps
are variable, though.
--
Void where prohibited by law.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Ian Goldberg)
Subject: Re: Bored with AES? SHA-256/384/512 spec now out!
Date: 12 Oct 2000 20:47:44 GMT
In article <[EMAIL PROTECTED]>,
David Crick <[EMAIL PROTECTED]> wrote:
>http://csrc.nist.gov/cryptval/shs.html
>
>PDF spec at: http://csrc.nist.gov/cryptval/shs/sha256-384-512.pdf
Hmmm. It worries me a bit that they define functions R and S, and
that R is "shift" and S is "rotate". Are these for sure not mixed up?
- Ian
------------------------------
From: jungle <[EMAIL PROTECTED]>
Subject: Re: naval code books were "weighted"
Date: Thu, 12 Oct 2000 16:38:51 -0400
James Muir wrote:
>
> I'm reading a paper in which the author explains that some cipher
> systems used in WWII employed countermeasures to protect against the
> seizure of key material. The author states for example that naval code
> books were "weighted".
>
> I suspected that this is "weighted" in the non-mathematical sense ( i.e.
> the books were weighted so that they would sink to the bottom of the
> ocean ), but I could be wrong.
you mean, book + brick ? as the package ?
------------------------------
From: Mike Oliver <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Thu, 12 Oct 2000 14:19:08 -0700
Reply-To: [EMAIL PROTECTED]
Robert Israel wrote:
>
> In article <[EMAIL PROTECTED]>,
> Mike Oliver <[EMAIL PROTECTED]> wrote:
>
>> Given T a consistent finite collection of axioms in a recursively-presented
>> language, T consistent, Q relatively interpretable in T. For any
>> theorem s of T, let f(s) be the length of its shortest proof. Now
>> let g(n) be the maximum value of f(s), where s ranges over all theorems
>> of T having n or fewer symbols.
>
> Suppose there is a recursive function (never mind primitive
> recursive) h(n) with g(n) <= h(n), and "Turing machine number x halts"
> corresponds to a statement S(x) in the language, such that for each
> positive integer n, S(n) is a theorem of the language iff Turing machine
> number n halts. Then you would have an algorithm to check whether
> Turing machines halt: if S(n) has N symbols, just check all possible
> proofs of length <= h(N).
Ah, using the fact that if a Turing machine halts, then any
theory satisfying my assumptions will prove that it halts. I
missed that the first time I read your response.
On the face of it, though, we seem to need to strengthen
the assumptions on T to "omega-consistent". Otherwise
T might prove that Turing machine n halts, when in fact
it does not.
Can you eliminate the requirement of omega-consistency, or
show that it is necessary?
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Rijndael implementations
Date: 12 Oct 2000 22:11:23 +0200
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
>Paul Schlyter wrote:
>>
>> David Eppstein <[EMAIL PROTECTED]> wrote:
>> >In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>> >
>> >> This is what "byte" *should* mean in the first place. Having "byte"
>> >> defined as "set of bits that represent a single character" seems like a
>> >> really dumb idea to me.
>> >
>> >You've obviously never programmed a 36-bit architecture.
>>
>> ...or a 60-bit architecture...
>
>CDC had for a very long time used 6 bits to represent
>characters on its machines. However, I don't remember that
>they called a group of 6 bits a byte in the manuals.
>
>M. K. Shen
CDC also had an alternate representation of characters, where each
character was stored in 12 bits. The CDC manuals referred to this
representation as "ASCII"....
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (Jim)
Subject: Re: naval code books were "weighted"
Date: Thu, 12 Oct 2000 21:46:19 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 12 Oct 2000 19:22:51 GMT, James Muir <[EMAIL PROTECTED]> wrote:
>I'm reading a paper in which the author explains that some cipher
>systems used in WWII employed countermeasures to protect against the
>seizure of key material. The author states for example that naval code
>books were "weighted".
>
>I suspected that this is "weighted" in the non-mathematical sense ( i.e.
>the books were weighted so that they would sink to the bottom of the
>ocean ), but I could be wrong.
Yes. They were weighted to sink. They could be thrown overboard
if the warship was cancelled, and in deep water recovery would be
extremely unlikely. Certainly the Royal Navy did this. Probably
still does!
Germany's Enigma cipher key material was printed with ink which
would run and blur on contact with water, and printed on absorbent
paper to help the process along.
('Seizing the Enigma', David Kahn).
--
Jim Dunnett
Germany 1 England 0 !
Finland 0 England 0 !!
amadeus @ netcomuk.co.uk
nordland @ lineone.net
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Code Book Cipher Challenge Cracked
Reply-To: [EMAIL PROTECTED]
Date: Thu, 12 Oct 2000 21:38:31 GMT
JPeschel <[EMAIL PROTECTED]> wrote:
: All 10 stages of Singh's Code Book Cipher Challenge
: have been cracked. [...]
: http://www.simonsingh.com/cipher.htm
Congratulations to Fredrik Almgren, Gunnar Andersson, Torbj�rn Granlund,
Lars Ivansson and Staffan Ulfberg from Stockholm for getting stage 10.
Comiserations for missing October 1st, 2000.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Chaste makes waste.
------------------------------
From: [EMAIL PROTECTED] (Jim Reeds)
Subject: Re: naval code books were "weighted"
Date: Thu, 12 Oct 2000 21:02:31 GMT
In article <8s5324$vhp$[EMAIL PROTECTED]>, James Muir <[EMAIL PROTECTED]> writes:
|> I'm reading a paper in which the author explains that some cipher
|> systems used in WWII employed countermeasures to protect against the
|> seizure of key material. The author states for example that naval code
|> books were "weighted".
|>
|> I suspected that this is "weighted" in the non-mathematical sense ( i.e.
|> the books were weighted so that they would sink to the bottom of the
|> ocean ), but I could be wrong.
|>
|> Can anyone second my interpretation? or offer a correct one?
There is a German naval code book from the late 1800s in
the National Cryptologic Museum in Maryland, which is
very heavy because of lead weights in the binding.
--
Jim Reeds, AT&T Labs - Research
Shannon Laboratory, Room C229, Building 103
180 Park Avenue, Florham Park, NJ 07932-0971, USA
[EMAIL PROTECTED], phone: +1 973 360 8414, fax: +1 973 360 8178
------------------------------
From: Mike Oliver <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Thu, 12 Oct 2000 15:01:57 -0700
Reply-To: [EMAIL PROTECTED]
Mike Oliver wrote:
> On the face of it, though, we seem to need to strengthen
> the assumptions on T to "omega-consistent". Otherwise
> T might prove that Turing machine n halts, when in fact
> it does not.
>
> Can you eliminate the requirement of omega-consistency, or
> show that it is necessary?
Another point too: I conjectured that g dominates every
p.r. function. Your argument (with the strengthened hypothesis)
shows that g is not dominated by any recursive function.
It seems to me that g really ought to dominate every recursive
function, which doesn't immmediately follow from the fact
that it's not dominated by any recursive function, even
knowing (from the way I defined it) that g is monotonic.
Any idea how to fill this gap?
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Bored with AES? SHA-256/384/512 spec now out!
Date: Thu, 12 Oct 2000 14:53:11 -0700
Personally I'm more worried by:
Page 9: These are the rst thirty-two bits of the fractional parts of the
cube roots of the first sixty-four primes.
Page 5: which are obtained by taking the fractional parts of the square
roots of the rst eight primes
Both discussing the initial state of SHA-256.
Joe
"Ian Goldberg" <[EMAIL PROTECTED]> wrote in message
news:8s581g$cju$[EMAIL PROTECTED]...
> In article <[EMAIL PROTECTED]>,
> David Crick <[EMAIL PROTECTED]> wrote:
> >http://csrc.nist.gov/cryptval/shs.html
> >
> >PDF spec at: http://csrc.nist.gov/cryptval/shs/sha256-384-512.pdf
>
> Hmmm. It worries me a bit that they define functions R and S, and
> that R is "shift" and S is "rotate". Are these for sure not mixed up?
>
> - Ian
------------------------------
** 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
******************************
