Cryptography-Digest Digest #440, Volume #13 Mon, 8 Jan 01 14:13:01 EST
Contents:
Re: Need of very simple algorithms? (Mok-Kong Shen)
Re: Fastest way to factor primes? (Paul Crowley)
Re: Unsolved Elgar Cipher... ("Rob Marston")
Re: Reviews of 50 cryptography books (Richard John Cavell)
Re: Reviews of 50 cryptography books ("Sam Simpson")
Idiots guide to Montgomery multiplication ([EMAIL PROTECTED])
Intriguing commercial encryption scheme (unbroken) for study :) (Troed)
FPGA SHA-1 implementation ([EMAIL PROTECTED])
Re: Can anyone break these cryptograms? (Chris Gillespie)
Re: Comparison of ECDLP vs. DLP (DJohn37050)
Re: Can anyone break these cryptograms? ("Douglas A. Gwyn")
Re: NSA and Linux Security ("Douglas A. Gwyn")
Re: Genomes (Mok-Kong Shen)
Re: Need of very simple algorithms? (Robert Scott)
Re: Question regarding OS's. ("Douglas A. Gwyn")
Re: Fastest way to factor primes? ("Douglas A. Gwyn")
Re: Unsolved Elgar Cipher... (Jim Gillogly)
Re: Can anyone break these cryptograms? (Jim Gillogly)
Re: Need of very simple algorithms? ("Brian Gladman")
new Bamford book soon ("Douglas A. Gwyn")
Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution Systems
(Warning: LONG post) ("Paul Pires")
Re: Reviews of 50 cryptography books (John Savard)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Need of very simple algorithms?
Date: Mon, 08 Jan 2001 11:28:07 +0100
Brian Gladman wrote:
>
[snip]
> But the 'telecoms layer' is so penetrated by government snooping that no-one
> should ever rely on this for security - 'end to end' encryption is vital for
> just this reason. And this is why some governments (e.g. the UK with RIPA)
> are now adopting laws that attempt to provide access to end user keys.
Maybe a not entirely unrealistic hope: If with the availability
of relatively cheap means a large enough number of people do
end-to-end encryptions on all occasions, then they wouldn't
know (due to the sheer volume) which messages are 'noises' and
which are relevant and the crypto laws would become practically
useless.
M. K. Shen
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: Fastest way to factor primes?
Date: Mon, 08 Jan 2001 10:33:30 GMT
Steve Portly wrote:
>
> What would be the fastest way to determine if 362293147 is prime?
> Wouldn't a prime number sieve be the fastest method?
Some errors in this question have been pointed out (you can't factor
primes, primality testing is much faster than factoring, etc), but here
are some tips anyway.
For a number this small, trial division is a perfectly practical way of
factoring. It even fits in a 32-bit integer! It should take an instant
to factor on any PC. When the numbers get bigger, you'll need a bigint
library to manipulate them. There are many (like GNU mp) but for
relatively small numbers the license will probably be the most
importaint part of your choice.
Another way to manipulate such numbers, which might be easier, would be
to use a language with bigint support builtin, like "bc" or Python. I
heartily recommend Python on general grounds of goodness anyway, and
it's a nice language to write simple bigint maths programs in.
When the numbers get too big for trial division, the "Pollard Rho"
method is not too hard to implement and can factorise numbers roughly
twice as long as trial division in the same time. This technique (and
all necessary mathematical and numeric background) is covered in
"Introduction to Algorithms", by Cormen, Leiserson, and Rivest, which
covers lots of other stuff too but which you certainly won't regret
buying if you're interested in this sort of programming.
hope this helps,
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: "Rob Marston" <[EMAIL PROTECTED]>
Crossposted-To: rec.puzzles
Subject: Re: Unsolved Elgar Cipher...
Date: Mon, 8 Jan 2001 10:04:25 -0000
Yes, but it seem's that I have problem typing :-)
Rob
------------------------------
From: Richard John Cavell <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc,misc.books.technical
Subject: Re: Reviews of 50 cryptography books
Date: Mon, 8 Jan 2001 21:53:18 +1100
On Sun, 7 Jan 2001, Roger Schlafly wrote:
> You give thumbs down to "A Million Random Digits: with 100,000
> Normal Deviates", but perhaps you didn't realize that you can
> get it online for free. See:
>
> The download is machine readable, and has errors corrected! (I realize
> that sounds totally ridiculous -- but see the explanation yourself.)
Thank Christ for the corrections! The random digits previously were
arranged in a pattern.
For those who are interested, the pattern was that of a string of one
million non-random digits, which repeated over and over again. Periodicity
of once every copy of the book.
=============================================================
Richard Cavell - [EMAIL PROTECTED]
Newsgroups - Please keep any discussion on the group, and copy your
replies to me via email. (Server problems). Sending me bulk email
guarantees a nasty response.
Judge Thomas Penfield Jackson on Bill Gates: "He has a Napoleonic concept
of himself and his company, an arrogance that derives from power"
=============================================================
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc,misc.books.technical
Subject: Re: Reviews of 50 cryptography books
Date: Mon, 8 Jan 2001 11:19:43 -0000
Hey, that's a good collection of books! :) A couple of well-known books you
appear to be missing:
(Mathematics) A Course in Number Theory and Cryptography 2nd Ed by Koblitz
(General) Computer Security by Gollamnn
(Pen & Paper / Pre-computer) Decrypted Secrets by Baurer
(Pen & Paper / Pre-computer) Making, Breaking Codes by Garrett
(Programming or Mathematics) Implementing ECC by Rosing
(Politics) Building in Big Brother by Hoffman
Regards,
Sam
Crypto-Boy <[EMAIL PROTECTED]> wrote in message
news:93bj76$qpo$[EMAIL PROTECTED]...
> Check out http://www.youdzone.com/cryptobooks.html
>
> for reviews of 50 cryptography books that I own and have read, plus an
> additional 10 I've yet to finish.
>
> Make sure to check out "Cryptography Decrypted" under the reference
> section, if you haven't yet heard of this new book.
>
>
> Sent via Deja.com
> http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED]
Subject: Idiots guide to Montgomery multiplication
Date: Mon, 08 Jan 2001 11:37:51 GMT
Hi,
I need an idiots guide to montgomery multiplication, i have read
numerous paper,thesis and web pages and i'm still no closer to sorting
it out. I have a degree in electronics so i need something that
doesn't go too deep into the maths...in fact i'm not that bothered
abount the math i just need to know how to implemement one. I need a
step by step guide on where each parameter comes from, how to calc
them. I have noticed that the "mod" operator is used in many of the
desciptions but i am tring to find a "mod" so..arrragggg..i don't
know...please someone put me out of my misery...
Thanks
Jonathan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (Troed)
Subject: Intriguing commercial encryption scheme (unbroken) for study :)
Reply-To: [EMAIL PROTECTED]
Date: Mon, 08 Jan 2001 12:59:15 GMT
Chosen plaintext and ciphertext available, can it be any better?
(Encryption of ROMs in Arcade machines, but that's not what's
interesting .. it's figuring out the algorithm used for the
encryption)
more info at:
http://cps2shock.retrogames.com/razpages/en-raz06.html
At the bottom is an Excel sheet with the plain/cipher-pairs. I'm
looking at it now, and have come to some conclusions already. I just
thought there'd be some people here that would also be interested in
breaking a commercial system depending on security by obscurity :)
regards,
___/
_/
------------------------------
From: [EMAIL PROTECTED]
Subject: FPGA SHA-1 implementation
Date: Mon, 08 Jan 2001 14:26:02 GMT
Besides the one specified below, are there any research groups doing
VHDL hardware FPGA SHA-1 implementation ? Or you may suggest some
pointers.
Thank you.
1. NASD project (http://www.pdl.cs.cmu.edu/NASD/darpa99.html)
2. Benchmarking of Configurable Computing Systems
(http://www.darpa.mil/ito/psum1999/e274-0.html)
W.S.Chong
[EMAIL PROTECTED]
Sent via Deja.com
http://www.deja.com/
------------------------------
Date: Mon, 08 Jan 2001 15:08:27 +0000
From: Chris Gillespie <[EMAIL PROTECTED]>
Subject: Re: Can anyone break these cryptograms?
Multiple Anagramming? I have never heard of this.
Is there a description of it somewhere online?
I analysed these ciphers and reached the conclusion it was a
monoalphabetic cipher. The frequency analysis is too close to
normal text for it to not be. I also stipulated it was a random
cipher alphabet. This lead me to using di/triagraphic analysis,
which I have just begun. However if transposition is also used
this will be useless.
Chris.
--
--
Chris Gillespie
Researcher
Dept of Computing
University of Bradford
email: [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 08 Jan 2001 16:17:36 GMT
Subject: Re: Comparison of ECDLP vs. DLP
A security proof on ECDSA will be showing up shortly. It is interesting to
note that in this case, the proof does not apply to DSA.
Don Johnson
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Can anyone break these cryptograms?
Date: Mon, 8 Jan 2001 16:11:27 GMT
Chris Gillespie wrote:
> Multiple Anagramming? I have never heard of this.
> Is there a description of it somewhere online?
I doubt it. Multiple anagramming is a standard method
for cryptanalysis of complex transpositions, e.g. double
transposition. Until a couple of years ago, documents
describing solution of such systems were still classified.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Mon, 8 Jan 2001 16:16:49 GMT
Simon Johnson wrote:
> ... I remember once reading that the NSA broke the
> encryption of between an candian exporter of grain and some EU
> distrubuter. The NSA then promptly sold this information to an American
> supplier and the American comapny successfully undercut the deal.
If you have evidence of this (highly illegal) event,
please send it to me and I'll see that an investigation
is launched. Frankly I doubt that it occurred, but if
it did the individual responsible should be prosecuted.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Genomes
Date: Mon, 08 Jan 2001 18:32:41 +0100
Terry Ritter wrote:
>
[snip]
> Although I am somewhat familiar with "Allan variance," and continue to
> read the many papers available on the web, I am confused about the
> implication that it can be relied upon to distinguish between noise
> and information.
[snip]
Could you or someone else kindly give a good reference of
Allan variance or a tiny summary of it? I failed to find
pointers from a couple of well-known and very comprehensive
reference materials of statistical sciences in the library.
Thanks.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Robert Scott)
Subject: Re: Need of very simple algorithms?
Reply-To: [EMAIL PROTECTED]
Date: Mon, 08 Jan 2001 17:33:38 GMT
On Sun, 7 Jan 2001 15:23:50 -0000, "Brian Gladman"
<[EMAIL PROTECTED]> wrote:
>
>What does your 'handy user' have to do encryption with? If he or she has
>anything more than their brain it may well be good enough to run AES.
>
>AES is simple enough to implement in mobile phones, in hand held devices
>like the Palm Pilot (where it is already available) and in a number of
>scientific calculators (e.g. TI86).
If you want an application that could benefit from the best security
but still may not have the resources to run AES, consider remote
keyless entry. A generalized crack in a widely-used cipher could
be of great interest to a car theft ring. But the market dictates
that the keyfobs that implement this technology have to cost under
$1 and generally have severe RAM and ROM limitations. Can you
implement AES is a Microchip 12C508?
Robert Scott
Ypsilanti, Michigan
(Respond through newsgroups, not by direct e-mail.)
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Question regarding OS's.
Date: Mon, 8 Jan 2001 16:49:56 GMT
[EMAIL PROTECTED] wrote:
> Is the usage of data piping (such as you described in the UNIX
> shell environment), how cryptoanalysis programs are actually
> implemented?
More accurately, it's the way that individual tools can be
quickly combined. For example, here is how I print Zendian
problem work sheets:
for i in [0-9A-Z]*/?????
do (sed 3q < $i; cat $i.r) | pr -d -f -h $i -
done | lp -T simple
By putting this into a text file (shell script, similar to
MS-DOS batch file) I can invoke the procedure by typing a
single word (the name of the shell script). Since UNIX
comes with a good assortment of sorting, searching,
counting, formatting, etc. utilities designed to be used
in combination, it is a very productive environment.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Fastest way to factor primes?
Date: Mon, 8 Jan 2001 16:50:52 GMT
Steve Portly wrote:
> What would be the fastest way to determine if 362293147 is prime?
> Wouldn't a prime number sieve be the fastest method?
$ factor 362293147
362293147
19031
19037
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Crossposted-To: rec.puzzles
Subject: Re: Unsolved Elgar Cipher...
Date: Mon, 08 Jan 2001 17:55:35 +0000
Anders Thulin wrote:
> Was it Balzac who published a cryptogram in one
> of his books? There's another challenge...
>
> However, he probably just asked his typsetter to deliberately
> make pie for a page or two ...
Kahn in "The Codebreakers" points out that the cipher in Balzac's
"The Physiology of Marriage" differs in different editions, which
suggests that you're right about the typesetter. The great
cryptographer Bazeries tried solving one version of it head-on, and
decided it was bogus.
--
Jim Gillogly
Trewesday, 17 Afteryule S.R. 2001, 17:31
12.19.7.15.13, 5 Ben 16 Kankin, Seventh Lord of Night
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Can anyone break these cryptograms?
Date: Mon, 08 Jan 2001 18:32:38 +0000
Chris Gillespie wrote:
>
> Multiple Anagramming? I have never heard of this.
> Is there a description of it somewhere online?
Yes, Google comes up with nearly a dozen pages where it's
mentioned. The point is that transposition ciphers can
be broken if two or more (the more, the easier) are found
with the same key and the same length: you stack them up
"in depth", snip them into vertical strips (literally, if
you enjoy manipulating paper strips), and anagram those
strips around until you get sensible stuff horizontally...
the same procedure you'd use for solving a complete
columnar. This doesn't require figuring out how the
transposition works... at least not for the equal-length
cryptograms, because no matter how the letters are shifted
around, one from position 7 in the original plaintext will
move to the same ciphertext position if the same key is used.
If you have other cryptograms of different lengths you will
still want to try to recover the key.
Courville's monograph on solving double columnar
transposition discusses ways of varying the multiple
anagramming to allow solution of two or more ciphers
that are only <nearly> the same length. It's trickier,
as you might expect.
> I analysed these ciphers and reached the conclusion it was a
> monoalphabetic cipher. The frequency analysis is too close to
> normal text for it to not be. I also stipulated it was a random
> cipher alphabet. This lead me to using di/triagraphic analysis,
> which I have just begun. However if transposition is also used
> this will be useless.
I agree that the monoliteral frequency distribution looks
pretty good for monoalphabetic. I'm not totally convinced that
this is right, though: if you add the two messages together
you get an I.C. of 0.0721, which is almost unreasonably high,
meaning there's more variation in frequency than you would expect
from English. The individual frequencies look like this:
a b c d e f g h i j k l m n o p q r s t u v w x y z
3 6 2 1 1 0 19 12 23 5 20 7 3 2 5 1 2 0 19 12 30 8 15 14 2 2
Note that we have some good high-frequency letters, but the
medium-frequency letters are pretty sparse. Perhaps most of
the sense of the message is carried only in a few of these,
such as ghikstuwx (like a checkerboard), with the others left
around for punctuation or nulls or something.
The paucity of useful repeats suggests it isn't just simple
substitution.
--
Jim Gillogly
Trewesday, 17 Afteryule S.R. 2001, 18:11
12.19.7.15.13, 5 Ben 16 Kankin, Seventh Lord of Night
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: Need of very simple algorithms?
Date: Mon, 8 Jan 2001 18:51:29 -0000
"Robert Scott" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Sun, 7 Jan 2001 15:23:50 -0000, "Brian Gladman"
> <[EMAIL PROTECTED]> wrote:
>
> >
> >What does your 'handy user' have to do encryption with? If he or she has
> >anything more than their brain it may well be good enough to run AES.
> >
> >AES is simple enough to implement in mobile phones, in hand held devices
> >like the Palm Pilot (where it is already available) and in a number of
> >scientific calculators (e.g. TI86).
>
> If you want an application that could benefit from the best security
> but still may not have the resources to run AES, consider remote
> keyless entry. A generalized crack in a widely-used cipher could
> be of great interest to a car theft ring. But the market dictates
> that the keyfobs that implement this technology have to cost under
> $1 and generally have severe RAM and ROM limitations. Can you
> implement AES is a Microchip 12C508?
I don't know since I have not tried this. But I have implemented AES on a
number of processors used in mobile phones and I am confident that AES can
meet such needs.
In a more general sense Rijndael is not a resource hungry algorithm so it
stands a good chance of being implementable in low resource situations. But
to determine whether it can be implemented in a particular environment
requires a significant effort.
Brian Gladman
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: new Bamford book soon
Date: Mon, 8 Jan 2001 17:35:37 GMT
Several weeks ago I talked briefly with James Bamford (author of
"The Puzzle Palace"), who was attending a function in the R&E
building at NSA, and he mentioned that he has been working on a
new book: "Body of Secrets: Anatomy of the Ultra-Secret National
Security Agency: From the Cold War Through the Dawn of a New
Century". Expect publication in April 2001; Amazon.com is
accepting pre-orders for this.
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution Systems
(Warning: LONG post)
Date: Mon, 8 Jan 2001 10:50:45 -0800
John Savard <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Sun, 7 Jan 2001 13:14:47 -0800, "Paul Pires" <[EMAIL PROTECTED]>
> wrote, in part:
>
> >What's wrong with a good stream cipher based on a
> >cryptographically secure PRNG, used in the proper way
> >That is different from block ciphers under the same
> >assumptions?
>
> One weakness that remains, with even the one-time-pad, let alone a
> secure PRNG, is that if an active attacker happens to _know_ one
> particular plaintext, a bit-flipping attack, in which inverting
> selected bits of the ciphertext results in inverting exactly the same
> bits of the plaintext allows the attacker to alter the plaintext
> despite not having broken the cipher, is possible.
>
> So this needs to be remembered, and authentication needs to be used.
This is exactly what I was getting at. Stream ciphers are discussed as if their
developement or evolution is complete. Kind of like, "These are the
constraints of the process" rather than "More work needs doing on these
issues". To me, It seems that:
*if you can make a stream cipher that breaks the locational relationship
between ciphertext, state and plaintext. AND
*if you can make a stream cipher that automagically authenticates. AND
*if you can do these things without loosing the speed and simplicity
advantages......
Then, it might just be interesting.
I have been playing around with a few ideas that lead me to believe that
the first two ideals and "Stream" are not incompatible. The third is a little
tougher :-)
Paul
>
> John Savard
> http://home.ecn.ab.ca/~jsavard/crypto.htm
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: comp.security.misc,misc.books.technical
Subject: Re: Reviews of 50 cryptography books
Date: Mon, 08 Jan 2001 18:39:30 GMT
On Mon, 8 Jan 2001 21:53:18 +1100, Richard John Cavell
<[EMAIL PROTECTED]> wrote, in part:
>For those who are interested, the pattern was that of a string of one
>million non-random digits, which repeated over and over again. Periodicity
>of once every copy of the book.
The book only offered one million random digits, not an infinite
number of them, so I do not see that the condition you describe is an
error. :)
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
