Cryptography-Digest Digest #481, Volume #13 Wed, 17 Jan 01 06:13:00 EST
Contents:
Re: Any good source of cryptanalysis source code (C/C++)? ("Ryan Phillips")
Re: RSA sign in 40ms on a DSP ? (Paul Rubin)
Re: Comparison of ECDLP vs. DLP (Wei Dai)
Re: NSA and Linux Security (Shawn Willden)
Re: NSA and Linux Security (Shawn Willden)
Re: future trends in asymmetric cryptography (Shawn Willden)
Re: future trends in asymmetric cryptography (Paul Rubin)
Re: multiple anagramming? (Shawn Willden)
Re: multiple anagramming? (Shawn Willden)
Re: future trends in asymmetric cryptography (John Savard)
Re: RSA sign in 40ms on a DSP ? ("Charles Oram")
Re: RSA sign in 40ms on a DSP ? (Paul Rubin)
Re: future trends in asymmetric cryptography (MikeAt1140)
Re: RSA sign in 40ms on a DSP ? (Bo Lin)
Re: multiple anagramming? (David A Molnar)
Re: RSA sign in 40ms on a DSP ? (Paul Rubin)
Re: 16bit collision resistance hash function? (Marc)
----------------------------------------------------------------------------
From: "Ryan Phillips" <[EMAIL PROTECTED]>
Subject: Re: Any good source of cryptanalysis source code (C/C++)?
Date: Tue, 16 Jan 2001 16:21:48 -0800
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:942ga1$f39$[EMAIL PROTECTED]...
> In article <3a647b68$[EMAIL PROTECTED]>,
> "Ryan Phillips" <[EMAIL PROTECTED]> wrote:
> > Haider, check the faq. Now people, when I come to a newsgroup I expect a
> > little courtesy and a little help - a link to the faq would have been
nice.
> > Tom if you don't want to help, don't post a message.
>
> Don't tell me what I shall and shall not do.
>
> Tom
Sorry, that was a little out of line. My apologies.
-Ryan
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: RSA sign in 40ms on a DSP ?
Date: 16 Jan 2001 17:29:04 -0800
"Charles Oram" <[EMAIL PROTECTED]> writes:
> I'm looking at an application where I need to do a 512bit RSA encryption
> using the private key (i.e. sign) on an 80MHz Motorola DSP56301 in around
> 40ms. At this stage all I have to do is say whether or not it can be done -
> does anyone have experience with optimised implementations of this sort of
> thing on a DSP or embedded processor who could tell me whether they think it
> can be done that quickly, or am I kidding myself ?
Yes, you should be able to do it a lot faster than 40 ms than that on
that part. You can probably do it in better than 10 ms.
See the paper "A cryptographic library for the Motorola 56000" by
M. Dusse and B. Kaliski, which I think was in Crypto 90. They used around a
25 mhz part and did a signature in around 50 ms, and it may have been
a 1024 bit signature (two 512 bit modexps plus CRT recombination). I
don't remember off the top of my head. You can probably license that
code from RSA Security if you want to go that route and are willing to
pay them enough.
------------------------------
From: Wei Dai <[EMAIL PROTECTED]>
Subject: Re: Comparison of ECDLP vs. DLP
Date: Tue, 16 Jan 2001 17:43:15 -0800
In article <[EMAIL PROTECTED]>, djohn37050
@aol.com says...
> There are many more ways a candidate RSA public key MIGHT be invalid, if the
> modulus is easy to factor, it is easy to invert. Or if it is hard to factor,
> it means that the (encryption) operation (for example) cannot be inverted by
> anyone, including the owner.
This seems to be a completely different issue from public-key
validation, which is used to detect keys that may allow an attacker to
obtain information about someone else's private key. What you're
talking about here are keys that either don't protect the plaintext or
make the ciphertext impossible to decrypt.
There are potential problems in elliptic curve key generation that are
similiar to the ones you give for RSA. They are also not possible to
detect using the public key alone. For example if the private key has
low entropy because of a RNG failure, it would be easy for anyone to
decrypt. Or if there is a bit flip in the elliptic curve point
multiplication process, the public key may still be a valid point in
the appropriate subgroup, but the owner can't decrypt.
If you do have access to the private key, then what we're talking about
is private-key validation. The situation here isn't very different
between EC and RSA. There is nothing that prevents you from doing lots
and lots of tests with an RSA private key. You can run the primes
through a bunch of different primality tests, encrypt and decrypt a
bunch of messages, etc.
--
http://cryptopp.com - free C++ cryptography and compression library
------------------------------
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Tue, 16 Jan 2001 19:44:55 -0700
Douglas A. Gwyn wrote:
> Shawn Willden wrote:
> > Not much pre-WWII. Heck, for most of the period between WWI and WWII
> > the U.S. didn't even spy on its *enemies* communications, much less its
> > citizens, that being an "ungentlemanly" thing to do (what is that quote
> > from The Black Chamber?).
>
> The Black Chamber was dissolved by Stinson, putting an end
> to most diplomatic communications monitoring, but military
> intelligence activities continued unabated. Thus, Yardley's
> disclosures, which had the effect of causing lots of foreign
> governments to change their cryptosystems, caused serious
> damage to US intelligence efforts.
Ah, thanks for that correction. I hadn't realized that Stinson had stopped
only diplomatic monitoring. Not monitoring enemy communications
seems like a very stupid idea, especially if you're going to continue other
espionage activities.
Shawn.
------------------------------
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Tue, 16 Jan 2001 19:45:59 -0700
Greggy wrote:
> After
> the war, the great depression took place and (if you study history) FDR
> and the congress technically, legally declared the citizens of the US
> enemies of the US
This is quite a statement. Can you provide a reference?
Shawn.
------------------------------
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: future trends in asymmetric cryptography
Date: Tue, 16 Jan 2001 19:51:15 -0700
Dido Sevilla wrote:
> Arguably the main reason why asymmetric crypto has
> been effectively limited to RSA and ElGamal all these years is because
> of these software patents.
Maybe. It seems to me, however, that if RSA hadn't been patented there
would have been even less incentive to research alternatives. I'm not
especially in favor of software patents (nor am I especially opposed to
them), but your conclusion doesn't seem to follow from your argument.
Could you explain how it does in more detail?
Shawn.
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: future trends in asymmetric cryptography
Date: 16 Jan 2001 19:31:56 -0800
Shawn Willden <[EMAIL PROTECTED]> writes:
> > Arguably the main reason why asymmetric crypto has been
> > effectively limited to RSA and ElGamal all these years is because
> > of these software patents.
>
> Maybe. It seems to me, however, that if RSA hadn't been patented there
> would have been even less incentive to research alternatives. I'm not
> especially in favor of software patents (nor am I especially opposed to
> them), but your conclusion doesn't seem to follow from your argument.
>
> Could you explain how it does in more detail?
For many years, RSA monopolized the public key market by claiming that
the DH patent (which they controlled) covered the entire concept of
public key cryptography, so that any public key system, including
those not yet invented, would infringe. The claim was bogus, but
nobody was willing to go to the expense of taking it to court.
But since it wasn't possible to *use* any PK system (at least in the
US) without a big legal fight, there wasn't much incentive to work on
developing them, until the DH patent expired.
------------------------------
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: multiple anagramming?
Date: Tue, 16 Jan 2001 20:18:28 -0700
Mok-Kong Shen wrote:
> Richard Heathfield wrote:
> > You are in a shopping mall. You ask a random stranger if he happens to
> > know the way to the park. He gives you firm and clear directions to the
> > library. Wouldn't you be at least a little disgruntled?
>
> Analogy is o.k. but it must be a correct one. John Savard
> gave the title of a book that treats the topic Mr. Goldberg
> needed to know, while in your analogy the park has nothing to
> do with the library (unless the library is next to the
> park, of course).
Better analogy: give him directions to the gas station, where he can buy a
map that will show the location of the park. :-)
Shawn.
------------------------------
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: multiple anagramming?
Date: Tue, 16 Jan 2001 20:25:11 -0700
Benjamin Goldberg wrote:
> In fact, I think I should mention that my public library has an
> electronic card catalogue, which lists not just it's own books, but
> those of 40 or so other libraries. In all of those, only ONE library
> had a copy of Applied Cryptography. And when I asked about an ILL
> request, it was commented to me that is the type of book which sometimes
> gets borrowed, and never returned.
Well, you know, if you, ahem, "lose" a book they only charge you a
depreciated price on it, often a price that is substantially below what
you'd find in a used book store. I've never chosen to use the library as a
discount bookstore, but I'll bet it happens from time to time.
And AC seems like a good one to "lose" :-)
Shawn.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: future trends in asymmetric cryptography
Date: Wed, 17 Jan 2001 03:46:13 GMT
On Sun, 14 Jan 2001 15:46:52 +0000 (UTC), [EMAIL PROTECTED] (Jan
Fedak) wrote, in part:
>Do you have any good ideas? I should write a conclusion for my thesis
>till tomorrow and after some hard hours at work I feel empty...
Well, you might want to look at what you have written up to this
point. What does it imply?
One could talk about future trends in the use of the methods we now
know - and that would mean increased use of methods other than DH and
RSA, at least elliptic curve methods, if not also the newer ones that
are still patented, but which offer faster speeds. But those methods,
I think, will also become increasingly used, even if many people will
wait until they are better known.
But a big element of the future cannot be known: what new discoveries
might be made? Either a new way to perform public-key encryption, or a
weakness in an existing algorithm, might change things considerably,
but future discoveries like this can hardly be anticipated in detail.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Charles Oram" <[EMAIL PROTECTED]>
Subject: Re: RSA sign in 40ms on a DSP ?
Date: Wed, 17 Jan 2001 18:17:17 +1300
Paul Rubin <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Charles Oram" <[EMAIL PROTECTED]> writes:
> > I'm looking at an application where I need to do a 512bit RSA encryption
> > using the private key (i.e. sign) on an 80MHz Motorola DSP56301 in
around
> > 40ms. At this stage all I have to do is say whether or not it can be
done -
> > does anyone have experience with optimised implementations of this sort
of
> > thing on a DSP or embedded processor who could tell me whether they
think it
> > can be done that quickly, or am I kidding myself ?
>
> Yes, you should be able to do it a lot faster than 40 ms than that on
> that part. You can probably do it in better than 10 ms.
>
> See the paper "A cryptographic library for the Motorola 56000" by
> M. Dusse and B. Kaliski, which I think was in Crypto 90. They used around
a
> 25 mhz part and did a signature in around 50 ms, and it may have been
> a 1024 bit signature (two 512 bit modexps plus CRT recombination). I
> don't remember off the top of my head. You can probably license that
> code from RSA Security if you want to go that route and are willing to
> pay them enough.
Thanks for the advice.
Does anyone know where I can get an electronic copy of that paper - I came
across references to it before, but I can't find it anywhere.
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: RSA sign in 40ms on a DSP ?
Date: 16 Jan 2001 21:27:20 -0800
"Charles Oram" <[EMAIL PROTECTED]> writes:
> Thanks for the advice.
> Does anyone know where I can get an electronic copy of that paper - I came
> across references to it before, but I can't find it anywhere.
It's in the Crypto 90 proceedings which are a book published by
Springer Verlag. If you're near an academic library they might have
it. All the Crypto proceedings are published on a CD-rom also by
Springer. I don't think it's online anywhere. Maybe you can get it
from the authors.
------------------------------
From: [EMAIL PROTECTED] (MikeAt1140)
Date: 17 Jan 2001 06:15:01 GMT
Subject: Re: future trends in asymmetric cryptography
Check out
http://www.tml.hut.fi/~helger/crypto/link/public/braid/
Public Key Cryptography based on Braid Groups
* Braid Groups: Intro
* Braids(intro by Stephen Bigelow)
* Braid Group Cryptography: Intro
* The Arithmetica Key Exchange(Michael Anshel)
* Making, Breaking Codes: An Introduction to Cryptology(Book by Paul
Garrett, contains a section on braid group cryptography)
* Errata
* Specific Errata concerning Arithmetica Cipher
* Arithmetica Key Agreement Protocol(Jim Hughes, Eurocrypt 2000 rump
session)
* Papers
* Word Problem
* A new approach to the word and conjugacy problems in the braid groups
(Birman, Ko, Lee, 1998)
* Updated version
(math.GT/9712211)
* A New Algorithm for Solving the Word Problem in Braid Groups
(David Garber, Shmuel Kaplan, Mina Teicher, math.AG/0101053, 2001) 01/16/01
* Constructing Public Key Cryptosystems via Combinatorial Group
Theory(Michael Anshel, 1999)
* An Algebraic Method for Public-Key Cryptography(Iris Anshel, Michael
Anshel, Dorian Goldfeld, Mathematical Research Letters {6} (1999) 287--291)
* A New Group Theoretic Protocol for Key Exchange(Iris Anshel, Michael
Anshel, Dorian Goldfeld, 1999)
* New Public-key Cryptosystem using Braid Groups(Ki Hyoung Ko, Sang Jin
Lee, Jung Hee Cheon, Jae Woo Han, Ju-sung Kang, Choonsik Park, Crypto 2000)
* Presentations (attack-wise)
* The LeftSSS attack on Ko-Lee-Cheon-Han-Kang-Park Key Agreement Protocol
in B45(Jim Hughes, rump session of Crypto 2000)
* Implementations
* Practical comparison of Fast Public-key Cryptosystems(Priit Karu, Jonne
Loikkanen, 2001) 01/16/01
* People working on braid group cryptography
* Michael Anshel(CUNY)
* Dorian Goldfeld(Columbia)
* Ki Hyoung Ko(KAIST)
* Jim Hughes(StorageTek)
* Sang Jin Lee(KAIST)
* Some more people working on braid groups
* Stephen Bigelow(Melbourne)
* Joan Birman(Columbia)
* Patrick Dehornoy(Caen)
* Companies
* Arithmetica
========================================================================
Cryptology Pointers by Helger Lipmaa
Got any suggestions or additional links? Mail to helger(at)tml.hut.fi
Changed: 1/16/2001
*************************************
Professor Michael Anshel
Department of Computer Sciences R8/206
The City College of New York
New York,New York 10031
------------------------------
From: Bo Lin <[EMAIL PROTECTED]>
Subject: Re: RSA sign in 40ms on a DSP ?
Date: Wed, 17 Jan 2001 09:21:40 +0000
You are not kidding yourself. You can make it under 10 ms without any
technical hurdle. See Dusse and Kaliski: "A Cryptographic Library for
the Motorola DSP56000", Eurocrypt'90, pp.230-244. The DSP56000 device
takes two cycles to do a MAC while the DSP56301 takes one. So In your
application, a 56301 is as 8 times fast as a 56000. If you like, you can
further optimise the method proposed in the paper to make your 512 RSA
running under 5ms. Good luck!
Charles Oram wrote:
>
> Hi there,
> I'm looking at an application where I need to do a 512bit RSA encryption
> using the private key (i.e. sign) on an 80MHz Motorola DSP56301 in around
> 40ms. At this stage all I have to do is say whether or not it can be done -
> does anyone have experience with optimised implementations of this sort of
> thing on a DSP or embedded processor who could tell me whether they think it
> can be done that quickly, or am I kidding myself ?
> I've had two different 'C' code implementations running on the DSP and this
> proves that I will definitely need to use an optimised set of large integer
> routines, probably mostly written in assembly language. I am also planning
> to make good use of the DSP's 24 bit multiply and add instructions (can do a
> 24x24bit multiply into a 56bit accumulator).
> I have looked at the web page for CASCADE
> (www.dice.ucl.ac.be/crypto/cascade) where they claim to have an
> implementation on an 17 MIPS ARM7 that can do an RSA sign in 73ms. Making
> the (not necessarily true) assumption that it can be as efficiently
> implemented on the 80 MIPS DSP would indicate that it may be possible to do
> it in 16ms.
> Thanks.
>
> Charles Oram.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: multiple anagramming?
Date: 17 Jan 2001 09:02:00 GMT
Shawn Willden <[EMAIL PROTECTED]> wrote:
> And AC seems like a good one to "lose" :-)
This would be why Koblitz's _Algebraic Aspects of Cryptography_ is no longer in
the library here, possibly. Which annoys me a bit, because I wasn't the one who
lost it.
-David
(don't ask how long I've had Stinson's book...)
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: RSA sign in 40ms on a DSP ?
Date: 17 Jan 2001 02:15:36 -0800
Bo Lin <[EMAIL PROTECTED]> writes:
> You are not kidding yourself. You can make it under 10 ms without any
> technical hurdle. See Dusse and Kaliski: "A Cryptographic Library for
> the Motorola DSP56000", Eurocrypt'90, pp.230-244. The DSP56000 device
> takes two cycles to do a MAC while the DSP56301 takes one. So In your
> application, a 56301 is as 8 times fast as a 56000. If you like, you can
> further optimise the method proposed in the paper to make your 512 RSA
> running under 5ms. Good luck!
Oops, you're correct, it's Eurocrypt, not Crypto as I said earlier.
Charles: the best way to get all these proceedings is just buy the
cd-rom "Advances in Cryptology 1981 - 1997", which has all the Crypto
and Eurocrypt proceedings for those years. See
http://www.iacr.org/cd/
for info. Hmmm, Amazon.com says it's backordered but fatbrain.com
has it in stock:
http://www1.fatbrain.com/asp/bookinfo/bookinfo.asp?theisbn=3540650695
------------------------------
From: [EMAIL PROTECTED] (Marc)
Subject: Re: 16bit collision resistance hash function?
Date: 17 Jan 2001 10:43:01 GMT
>> is there any way to produce a hash value that has only 16bit length
>> but is as collision resistance as possible?
Well, I guess 16 bit is a little bit too small to offer
solid collision resistance. On the other hand it is small
enough to maintain a TABLE. If your protocol setup allows it,
and you have no more than 65536 messages to hash, you can
look them up in a table. Allocate a "hash" for each new
message, or return the lookup result for known messages.
This approach will be "as collision resistant as possible"
(ie no collisions at all) for <=65536 messages, but fail
miserably for more.
A table for 64bit messages and 16bit "hash" occupies 512kb of
disk space.
------------------------------
** 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
******************************
