Cryptography-Digest Digest #940, Volume #10 Thu, 20 Jan 00 18:13:02 EST
Contents:
Re: Ciphers for Parallel Computers (David A Molnar)
Transposition over ASCII-coded text ("Markus Eiber")
Codebook URL (Mike Andrews)
Re: ECC vs RSA - A.J.Menezes responds to Schneier (Tom St Denis)
Re: Codebook URL (John Savard)
Re: Codebook URL (John Savard)
Re: MIRDEK: more fun with playing cards. (John Myre)
Re: Transposition over ASCII-coded text (Mok-Kong Shen)
Re: ECC vs RSA - A.J.Menezes responds to Schneier (lordcow77)
Re: MIRDEK: more fun with playing cards. (CLSV)
Publication Reference for Vernam Cipher (Jim Haynes)
Re: Blowfish & pi. (Martin Kahlert)
Re: NIST, AES at RSA conference (Mok-Kong Shen)
----------------------------------------------------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Ciphers for Parallel Computers
Date: 20 Jan 2000 20:33:46 GMT
Tim Tyler <[EMAIL PROTECTED]> wrote:
> John Savard <[EMAIL PROTECTED]> wrote:
> : Well, maybe, but I can't think of a way to force an attacker to
> : perform a brute-force search of the keyspace serially.
> This is the NTRU system. http://www.ntru.com/tutorials/techsecurity.htm :
I thought that they had removed this page from their web site. :-(
> ``It is worth pointing out that the process of breaking a key pair does
> not seem to have much chance of being significantly improved by the
> use of many computers working in parallel. This technique can be
> effective in attacks on an RSA key - using the quadratic or number
> field sieve to factor a large number. [...]''
I think the recent threads on the current space requirements for the
number field sieve are appropriate here. The first stage of both these
algorithms can be distributed -- looking for sufficiently smooth numbers.
The next stage, that of looking for relations in a matrix, is not easily
distributed or parallelized yet. Plus it requires massive amounts of
space.
What's more, the attacks this page discusses are based on the LLL lattice
basis reduction algorithm. As far as I know, no one has yet shown that
either lattice basis reduction OR the second stage of the NFS cann't
be parallelized!
So it seems to me that both attacking NTRU and factoring with NFS are in a
similar position : for large keysizes, the running time is dominated by a
"linear algebra" step which it is not known how to distribute. Neither
do we know that these steps can not be distributed.
I should now make clearer what I mean by "distributed" and "parallel".
When I say distributed, I mean something like distributed.net, where
many processors are connected by very slow or intermittent links.
When I say parallel, I mean something like a mesh of processors
connected together with shared memory.
I want more precise, but creating a model which respects
this difference seems to be rather hard. Much less a model which would
then allow us to prove statements of the form "Problem X is likely not
{parallelizable, distributable}." Suggestions of models are welcome.
So a problem can be parallelizable, but not easy to distribute. Below I'll
give some pointers to a "parallel lattice basis reduction" algorithm which
scales to give an O(n^2) improvement with O(n^2) processors on a parallel
architecture. I do not think it extends to a distributed basis reduction
algorithm, unfortunately.
> The page concludes falteringly, though:
> ``It is not inconceivable that the process of completing one step could
> be speeded up by a factor of about N by using N processors, (though this
^^^^^^^^^^
> has never been tried), but even this would only reduce the time by
^^^^^^^^^^^^^^^^^^^^^
> an insignificant factor of N.''
This is incorrect and has been since 1992.
I actually have a web page on parallel lattice basis reduction. It is not
a very good web page and needs updating, but it has links to some papers
on the subject. You can find it at
http://www.hcs.harvard.edu/~dmolnar/parallel-reduce/index.html
The short summary is that at least one parallel version of the LLL
algorithm exists. If you believe the conference papers and PhD theses,
it's been implemented on various parallel architectures.
This algorithm gives about an O(n^2) speedup with O(n^2) processors,
where n is the dimension of the lattice being reduced.
The most extensive report I know of on _implementations_ is the PhD
thesis of Christian Heckler. Unfortunately, it's in German, which
I don't read yet. If anyone happens to read German and would like to
comment, it's at
http://math-www.uni-paderborn.de/~chh/diss/
I haven't looked at the dimensions of the lattices which must be reduced
to break NTRU. It is worth noting, however, that the LLL algorithm is
normally O(n^4) arithmetic operations. As n becomes even moderately large,
this becomes unpleasant. The parallel algorithm reduces this to about
O(n^2) arithmetic operations, which seems significant.
Anyway, I had thought that this page was no longer on the NTRU web site.
I'm sorry to see it brought up again.
I should also add that the authors of the NTRU system _are_ aware of
these results on parallel lattice basis reduction, and claim to have
compensated for its effects in their recommendation of key sizes.
Thanks,
-David
------------------------------
From: "Markus Eiber" <[EMAIL PROTECTED]>
Subject: Transposition over ASCII-coded text
Date: Thu, 20 Jan 2000 22:18:19 +0100
Hi there!
I study electronic engineering having a focus on transmission units.
In digital transmission units there is often used a scrambler or an
interleaver in order to improve error correction for the transmitted data.
In general those functions could be interpreted as a transposition of the
digital data. Let this data be for instance be ASCII-coded (8 bit) text and
let us assume, that we don't know the key for transposition. If we decode
the scrambled bit stream we will note, that the result is a polygraphic
substitution (if the length of one transposition_block is not equal to 8
bit). Depending on this length the redundancy of the transmitted text goes
down and with great length, it will be very difficult to break the
substitution (Hill-cipher!). Anyway, we are still in posession of the
digital data. My question is, if there is a way to break the cipher using
the digital bit stream (this means not to decode it) when only ciphertext is
available?
Sorry for my english and thanks for your answers
--
Markus Eiber
Werner-Heisenberg-Weg 106
85579 Neubiberg
Germany
[EMAIL PROTECTED]
____________________________
"Gewöhnlich glaubt der Mensch, wenn er nur Worte hört,
es müsse sich doch dabei auch was denken lassen."
Goethe
------------------------------
From: [EMAIL PROTECTED] (Mike Andrews)
Subject: Codebook URL
Date: Thu, 20 Jan 2000 21:21:00 GMT
I'm in the process of scanning in and making available a WW-II
US Army training codebook. The URL is
"http://mikea.ath.cx/codebook".
It's incomplete, but I get a bit farther into the stack of
pages every day.
Also got some US Army training material on cryptanalysis
and on construction of Signal Operating Instructions (SOIs),
which I'll be putting up as time permits.
--
Mike Andrews
[EMAIL PROTECTED]
Tired old sysadmin since 1964
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: ECC vs RSA - A.J.Menezes responds to Schneier
Date: Thu, 20 Jan 2000 21:38:29 GMT
In article <[EMAIL PROTECTED]>,
James Felling <[EMAIL PROTECTED]> wrote:
> There are composite numbers that will work as P/Q for RSA. They are
VERY,
> VERY rare-- it is much much more likely that a randomly chosen
number is
> prime than a usable composite number.
Well can't you do RSA with more then two primes anyways?
Tom
>
> Tom St Denis wrote:
>
> > In article <865vmm$8es$[EMAIL PROTECTED]>,
> > Greg <[EMAIL PROTECTED]> wrote:
> > > Perhaps I leave myself open to a known attack of a well studied
> > > curve, but it seems to me that this is prefered to leaving one's
> > > self open to a weakness in a random curve. Does this make sense?
> >
> > Sorry no comment.
> >
> > > > > I could not see using a random prime.
> > > >
> > > > Again, why? Please tell us what you think is wrong with
> > > > randomly chosen primes.
> > >
> > > Well, I mentioned in another thread that I am not sold on primes
> > > that are so large that they are tested and then at some point
> > > simply assumed to be prime. Some have told me that this does not
> > > weaken the cryptosystem, but I have always wondered why that would
> > > be if the strength depended on primes to begin with.
> >
> > Well there are ways to make primse and tests them. See Knuth Vol2
for
> > info on that. The problem is spending an hour making a key is a bad
> > idea. If it takes 2 mins to verify a key is ok that's not so
shotty.
> >
> > > Again, I believe a well studied cryptosystem and all of its
> > > components are superior to anything randomly selected on the
> > > fly- the latter seems like a crap shoot. If anything is
> > > randomly selected, it should be just as equally capable
> > > of being a strong candidate as any other. With primes,
> > > you do not have this. With integers used for ECC private keys,
> > > you get exactly that- except in a few cases, like 0, 1, and n-1,
> > > which are too easy not to avoid.
> >
> > Funny you say that but even in symmetric ciphers round keys are
made on
> > the fly. In RC5 for example it has never been proven to be a strong
> > key schedule, yet people trust it....
> >
> > > IMHO, every cryptosystem today has its own small element
> > > of unknown. I simply have more confidence in one set of unknowns
> > > than I do in others. I really can't sleep at night knowing that
> > > my data is hanging from a crap shoot. It just does not work
> > > for me.
> >
> > Umm... maybe smoothness will be defined for ecc? hehehe
> >
> > > > > RSA relies on
> > > > > this approach since primes are not "studied" ahead of use.
> > > >
> > > > I can't understand what you are saying here. What does it mean
to
> > > > "study" a prime? Also, what is the antecedent of the
word "this"
> > > > in the phrase "this approach"?
> > >
> > > As I understand it, RSA randomly generates prime candidates
> > > to use for private keys. You cannot take a lot of time and
> > > a lot of people to study a pair of primes to ensure they are
> > > really primes like you can an elliptic curve, because to do
> > > so exposes the keys. But again, others would say that this
> > > is not important- that a number does not have to be a pure
> > > prime. If you could explain that to me, I would be all ears.
> >
> > If you choose p and q, and say p actually is p = a * b, then your
rsa
> > key will not work since
> >
> > n = pq
> > phi(n) = phi(pq) = (p - 1) * (q - 1)
> >
> > But the order of the group is not that.. it's actually
> >
> > phi(n) = (a - 1) * (b - 1) * (q - 1)
> >
> > But since p and q are random you can't be sure of either. Finally
you
> > will find that the original definition of phi will not let you find
a
> > decryption exponent.
> >
> > So the chances that a) the candidates survies testing and b) works
> > flawlessly in RSA and c) are not prime, is very very very very
slim...
> >
> > Tom
> >
> > Sent via Deja.com http://www.deja.com/
> > Before you buy.
>
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Codebook URL
Date: Thu, 20 Jan 2000 14:49:00 GMT
[EMAIL PROTECTED] (Mike Andrews) wrote, in part:
> "http://mikea.ath.cx/codebook".
Your server does not appear to have an entry in my Domain Name Server.
I even tried replacing .cx by .com, in case this was a spam defense.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Codebook URL
Date: Thu, 20 Jan 2000 14:50:44 GMT
[EMAIL PROTECTED] (John Savard) wrote, in part:
>[EMAIL PROTECTED] (Mike Andrews) wrote, in part:
>> "http://mikea.ath.cx/codebook".
>Your server does not appear to have an entry in my Domain Name Server.
>I even tried replacing .cx by .com, in case this was a spam defense.
Never mind, it's my ISP who is down. E-mail isn't working right now
either, but USENET is still up.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: MIRDEK: more fun with playing cards.
Date: Thu, 20 Jan 2000 14:49:43 -0700
Paul Crowley wrote:
> CLSV <[EMAIL PROTECTED]> writes:
<snip>
> > One thing I would like to see in MIRDEK is a richer character
> > set. "A".."Z", "0".."9", " ", and "." would me enough.
>
> This is pretty much impossible. If you use the jokers you could
> create a cipher with one extra character, perhaps " "; I suggest a
> number encoding on the Web pages, and you can use STOP telegram-like
> for full stops (though of course it takes 2:30 to encode it). But
> then what will you map to joker in the output? No, I think I'll keep
> it the way it is. Mirdek depends fundamentally on having twice as
> many cards as characters.
I was thinking a bit about using the old trick of having shift
modes. It's rather ugly with 26 symbols since you have to steal
a letter to do it. But with a joker, maybe it would be practical?
That is, the 27'th symbol would mean "alternate character set".
Of course you could invent all sorts of coding schemes; the hope
is that you could invent one that is easy and fast. What if
we said that joker followed by black card is one of 13 punctuation
symbols; joker followed by a sequence of red cards and a terminating
joker are used for numbers (10 digits plus perhaps some helpful
symbols for scientific notation or money). (Then we get to decide
what two consecutive jokers means, and so on).
I haven't actually sat down with Mirdek to try this, of course,
so I don't know if it really is practical.
John M.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Transposition over ASCII-coded text
Date: Thu, 20 Jan 2000 23:38:02 +0100
Markus Eiber wrote:
>
> I study electronic engineering having a focus on transmission units.
> In digital transmission units there is often used a scrambler or an
> interleaver in order to improve error correction for the transmitted data.
> In general those functions could be interpreted as a transposition of the
> digital data. Let this data be for instance be ASCII-coded (8 bit) text and
> let us assume, that we don't know the key for transposition. If we decode
> the scrambled bit stream we will note, that the result is a polygraphic
> substitution (if the length of one transposition_block is not equal to 8
> bit). Depending on this length the redundancy of the transmitted text goes
> down and with great length, it will be very difficult to break the
> substitution (Hill-cipher!). Anyway, we are still in posession of the
> digital data. My question is, if there is a way to break the cipher using
> the digital bit stream (this means not to decode it) when only ciphertext is
> available?
I know much too little about electronics, hence some questions
of ignorance:
(1) Does one use in 'normal' transmission a 'scrambler' to improve
'error correction'? I thought that various much-studied codes
with capabilities of doing error-correction are used. But
these are in my view not scrambling in the sense of encryption,
since these codes are well-known (public).
(2) If one uses a single error-correcting code, then one has a
monoalphabetic substitution. Where does polyalphabetic
substitution come from?
(3) I am yet ignorant of any use of Hill's method in the context
of transmission error-correction. Could you please give a
literature reference?
Thanks,
M. K. Shen
------------------------------
From: lordcow77 <[EMAIL PROTECTED]>
Subject: Re: ECC vs RSA - A.J.Menezes responds to Schneier
Date: Thu, 20 Jan 2000 14:32:03 -0800
In article <867pg9$jc5$[EMAIL PROTECTED]>, Greg <[EMAIL PROTECTED]>
wrote:
> At first, I thought you were saying that the composite would
> be stronger than a prime. Is that correct?
> But the real question is can you find a composite number that you
> think is prime, that appears to work and yet can weaken the key?
> If so, it is a crap shoot.
> IFP differs from ECC in that the strength of IFP is determined
> randomly and with a quick check because the strength lies in the
> key itself. With ECC, the strength lies in the curve, not the
> key, so the strength of such a cryptosystem can be studied for
> years by many people without compromising the keys themselves.
If you're so worried about generating a prime by accident that passes a
preliminary sieve and multiple pseudoprimality tests, please generate a
512-bit composite number that will do so. I'll even make it easier for
you: instead of sieving all primes under 2^16, just sieve all primes
under 1000. Instead of strong pseudoprimality tests (Miller-Rabin,
Lucas sequence, Frobenius test, etc.) just use a simple Fermat test to
base 2. It should be very easy for you since these tests are just a
"crap shoot."
Once you do this, calculate the probability that a randomly selected
composite will pass these (comparatively weak) tests and be falsely
declared a prime.
Then add in a larger sieve range at the beginning and using multiple
strong pseudoprimality tests and find the aforementioned probability.
Put up or shut up.
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: CLSV <[EMAIL PROTECTED]>
Subject: Re: MIRDEK: more fun with playing cards.
Date: Thu, 20 Jan 2000 22:52:06 +0000
Paul Crowley wrote:
>
> CLSV <[EMAIL PROTECTED]> writes:
> > Well you could skip the key setup phase completely at the
> > expense of communicating the initial 52-card state of
> > the deck as your secret key. If you do 10 proper shuffles
> > the order of the cards will be random enough.
> If you have a channel over which you can communicate such a key, why
> not send the message over it? Or use one-time-pads?
A 52-card key is the equivalent of a 225 bit key
I don't see the connection with a one-time pad.
> The convenient thing about Mirdek is that you and I can meet up one
> day and agree a nice, memorable passphrase, then much later you can go
> and buy a pack of cards, encrypt as many messages as you like, and I
> can decrypt them all.
You have to remember that the opponents will use
computers to crack your codes. So it does pay to
use a strong password. If you are not able to communicate
a 52-card key one time I don't believe you have any
chance to communicate securely.
In the context of civil rights you'll need a semi-secret
communication channel anyway. If someone catches you
sending letters with content like "AXQZV WXYXZ OINAF ..." I
think you can expect a visit of the local Gestapo pretty
soon.
> > Well, I've tried it (not for speed I must admit) and
> > I believe calculating modulo 52 is possible for most people.
>
> I'd be interested to hear some stopwatch results for this one.
In a few weeks I have more time on my hands for
experiments, I'll try it out and post some results.
Module 52 arithmetic can be made easier by splitting
it into modulo 4 and modulo 13 arithmetic.
> > One thing I would like to see in MIRDEK is a richer character
> > set. "A".."Z", "0".."9", " ", and "." would me enough.
>
> This is pretty much impossible. If you use the jokers you could
> create a cipher with one extra character, perhaps " "; I suggest a
> number encoding on the Web pages, and you can use STOP telegram-like
> for full stops (though of course it takes 2:30 to encode it). But
> then what will you map to joker in the output? No, I think I'll keep
> it the way it is. Mirdek depends fundamentally on having twice as
> many cards as characters.
Well you could use two decks of cards, say a blue deck
and a red deck. There are quite a few card games using
two decks so it would not look too suspicious.
Regards,
CLSV
------------------------------
Subject: Publication Reference for Vernam Cipher
Reply-To: [EMAIL PROTECTED]
From: [EMAIL PROTECTED] (Jim Haynes)
Date: Thu, 20 Jan 2000 22:59:54 GMT
Since I stumbled on to this this afternoon while looking for something
else I will pass it along in case anybody wants it.
G. S. Vernam; "Cipher Printing Telegraph Systems for Secret Wire
and Radio Telegraphic Communications." Transactions of the A.I.E.E.
Feb. 1926, p. 295.
There is a funny story connected with the Vernam cipher in the book
"Old Wires and New Waves" by Harlow. (from memory now, so may be
distorted) After WW-I there was a show-and-tell for the press, and
one of the things they showed was a Vernam cipher machine. (Which
mixes Teletype characters with a one-time key tape to produce
encrypted Teletype; and then reverses the process at the receiving
end with a copy of the key tape to produce clear text.) They told
the press they had invented a machine that would translate between
French and English. They put a pre-punched tape with an English
sentence into the machine and out came a French translation. Putting
the French into the machine they got back the English. Of course what
they really had were English and French versions with precisely the
same number of letters, and a carefully hand-prepared key tape that
would transform one into the other.
------------------------------
From: [EMAIL PROTECTED] (Martin Kahlert)
Subject: Re: Blowfish & pi.
Date: 20 Jan 2000 08:03:22 GMT
Reply-To: [EMAIL PROTECTED]
[Posted and mailed]
In article <85p46e$76q$[EMAIL PROTECTED]>,
XTR <[EMAIL PROTECTED]> writes:
> Hi,
>
> Problem when to initialize P-array and S-array, that is,
> by taking fractional part of pi.
> After taking correct values for P[0] and P[1], the fractional
> part of pi goes all 0.00000....
> I'm using Turbo C++3.0, and the 'double' gives 64 bits datatype.
>
> Any better tip to overcome this?
Here is a program, which produces hexdigits of pi.
(Sorry, i don't know, where i got it from originally)
/* Pi = Sum[k=0..] 16^(-k)( 4/(8k+1) - 2/(8k+4) - 1/(8k+5) - 1/(8k+6) )
due to Borwein et. al.
*/
#include <stdio.h>
#define BASE 0x10000
typedef unsigned long ulong;
ulong power( ulong a, ulong b, ulong c )
{
/* Computes a^b mod c */
ulong x = 1;
while (1)
{
if (b & 1) x = (x*a)%c;
b >>= 1;
if (b==0) break;
a = (a*a)%c;
}
return x;
}
ulong sum( ulong m, ulong d )
{
ulong s = 0, k, p = BASE;
for (k = 0; k < d; k++)
{
ulong ak = (k<<3) + m;
s += ( power( 16, d-k, ak ) * BASE ) / ak;
}
for (k = d;; k+=1)
{
ulong t = p / ( (k<<3) + m );
if ( t == 0 ) break;
s += t;
p >>=4;
}
return s;
}
int hex_digit_of_pi( ulong d )
{
ulong R = 4*sum( 1, d ) - 2*sum( 4, d ) - sum( 5, d ) - sum( 6, d );
int d1 = (int)( ( R / ( BASE/16 ) ) % 16 );
int d2 = (int)( ( R / ( BASE/256 ) ) % 16 );
if ( d2 == 0 || d2 == 15 )
{
int td2 = hex_digit_of_pi(d+1);
if ( td2 == 0 && d2 == 15 ) d1 += 1;
else if ( td2 == 15 && d2 == 0 ) d1 -= 1;
}
return d1 % 16;
}
int main(void)
{
ulong d;
printf("Pi in hex is 3.\n");
for (d=0;d<17*64;d+=1)
{
printf("%X", hex_digit_of_pi(d));
if ( (d+1) % 64 == 0 ) printf("\n");
}
return 0;
}
--
The early bird gets the worm. If you want something else for
breakfast, get up later.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: NIST, AES at RSA conference
Date: Fri, 21 Jan 2000 00:10:07 +0100
Serge Vaudenay wrote:
>
> Actually, if an expert do not have any personal interest about AES, he
> should better wait
> for the final standard before doing some substantial work. In the
> meanwhile he can work
> for other standards.
Very probably I misunderstood. But my (superficial) interpretation
of your sentence means that the AES winner would not have got much
study by the majority of the experts at the time point the winner
is declared to be a standard by NIST for use by people of the
whole world. That's pretty bad, isn't it?
M. K. Shen
------------------------------
** 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
******************************
