Cryptography-Digest Digest #225, Volume #9 Fri, 12 Mar 99 03:13:03 EST
Contents:
Re: How to PROPERLY implement CFB8 for DES? (Augustin Volker)
How to PROPERLY implement CFB8 for DES? (Augustin Volker)
Certicom Benchmark ("Michael Scott")
Re: Certicom Benchmark (DJohn37050)
Re: Cyclotomic Number Generators ("Tony T. Warnock")
Re: Cyclotomic Number Generators (R. Knauer)
How do i compute (a^b) mod n ("Luke Herbert")
Re: Finite Field with Hard Division? ([EMAIL PROTECTED])
Re: How do i compute (a^b) mod n ("Luke Herbert")
Re: How do i compute (a^b) mod n ("Luke Herbert")
NO CREDIT CARD ([EMAIL PROTECTED])
Re: ElGamal vs RSA ([EMAIL PROTECTED])
Crypto transmission in noisy ambient ("F. Arndt")
Re: Crypto transmission in noisy ambient (David A Molnar)
Re: ElGamal vs RSA ("Roger Schlafly")
Re: ZKS Freedom Server (Michael Curry)
Re: Crypto transmission in noisy ambient (Chris Monico)
Re: Crypto transmission in noisy ambient ("Douglas A. Gwyn")
Re: Certicom Benchmark (R. Dale Shipp)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Augustin Volker)
Subject: Re: How to PROPERLY implement CFB8 for DES?
Date: Thu, 11 Mar 1999 20:12:26 LOCAL
I forgot a few things:
Algorithm used: DES/CFB8/PKCS5Padding
Key: 481CA5EB44A4DCA4 (Hex)
Initialization vector: C2FF4F639737FF36 (Hex)
Plaintext: 64 (Hex)
My Ciphertext: 84A6 (Hex)
Sun's Ciphertext: 8428F66395E328CB (Hex)
Both algorithms encrypt and decrypt consistently, so decryption is the inverse
of encryption. Just the results are not consistent.
Volker
"The only system that is truly secure is one that is switched off and unplugged,
locked in a titanium-lined safe, buried in a concrete bunker, and surrounded by nerve
gas and very highly-paid armed guards. Even then, I wouldn't stake my life on it."
-- Gene Spafford
Insure your privacy! Use Pretty Good Privacy!
http://www.pgpi.com/
------------------------------
From: [EMAIL PROTECTED] (Augustin Volker)
Subject: How to PROPERLY implement CFB8 for DES?
Date: Thu, 11 Mar 1999 20:03:58 LOCAL
Hi!
I have a DES algorithm working properly in ECB mode. Now I wrote CFB mode and
compared it to the one Sun implements in the Java Cryptographic Extension 1.2
beta2.
The problem is, that there are differences. First of all, when I do padding in
CFB8 mode, I always pad 1 byte. Sun seems to pad 1 to 8 bytes.
Then, the output is different. Can anyone give a detailed description on how
to implement CFB8 using a working DES cipher which has a function, say
encryptBlock(byte[] input, int inputOffset, byte[] output, int outputOffset,
length)? (length should be DES blocksize in this case).
Thanks, Volker
"The only system that is truly secure is one that is switched off and unplugged,
locked in a titanium-lined safe, buried in a concrete bunker, and surrounded by nerve
gas and very highly-paid armed guards. Even then, I wouldn't stake my life on it."
-- Gene Spafford
Insure your privacy! Use Pretty Good Privacy!
http://www.pgpi.com/
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Certicom Benchmark
Date: Thu, 11 Mar 1999 20:47:58 -0000
Concerning the benchmarks provided by Certicom at
www.certicom.com/ecc/ipsec.html
These benchmarks compare standard Diffie-Hellman (DH) with the Elliptic
curve equivalent (ECDH). It would appear from the benchmarks that the EC
method is up to 70 times faster than standard Diffie-Hellman for comparable
levels of security. The text implies that the advantage to ECDH may in fact
be even greater than that. While not disputing the figures quoted I would
maintain that they do not accurately reflect the innate speed of each
method. They compare the best acheived by Certicom with ECDH, with a
particular 3rd party implementation of DH. So I implemented DH myself on a
Pentium Pro 200MHz. The timings I get are in brackets after the times quoted
in the benchmark.
Key generation 1024-bit DH - 91.67ms (14ms)
Shared secret 1024-bit DH - 108.33ms (17ms)
Key generation 2048-bit DH - 611.67ms (65ms)
Shared secret 2048-bit DH - 728.33ms (80ms)
As you can see the differences are highly significant. It is suggested in
the text that standard DH benefits from the use of the Pentium Pro
co-processor. It doesn't, and I didn't use it.
When I commented on these benchmarks before, I was surprised that even
someone as knowledgable as our own patient, persistent and truthful Dr, mike
was apparently happy to take them at face value. But to do so would in my
opinion be a mistake.
I then checked out the Certicom Whitepaper entitled "The Elliptic Curve
Cryptosystem for Smart Cards", available from www.certicom.com In it is a
table which would suggest that on another platform (UltraSPARC) DH is 226
times slower than ECDH. I laughed so much I nearly fell off my chair. But
really - I was shocked. And it is not so much that the EC implementation is
amazingly fast (although it seems moderately impressive), but that the
implementation that it is compared to is so grindingly slow.
For a well-balanced comparison see Michael Weiner's article "Performance
comparison of Public Key Cryptosystems" in RSA labs Cryptobytes, Vol. 4, No.
1, 1998 from www.rsa.com
After a thoughtful analysis he gives some results (also from a Pentium
200MHz) which indicate that certain EC methods are about 50% faster when
comparing DSA (1024-bits) with ECDSA (168 bits). He states that DH and ECDH
are comparable speed-wise - which flatly contradicts Certicom's claims. He
also makes the interesting observation that software implementations of
Elliptic curves over GF(2^m) appear to be slower than those over GF(p), but
accepts that reports differ on this.
Another good source would be Wei Dai's benchmarks which can be viewed at
www.eskimo.com/~weidai/benchmarks.html
Perhaps some of the eminent cryptographers that work for Certicom could have
a quiet word in the ear of their sales people.
Mike Scott
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Certicom Benchmark
Date: 11 Mar 1999 21:30:43 GMT
Any performance data is always for a particular implementation at a particular
time running on a particular platform. As such, it is always open to
improvement and refinement.
Don Johnson
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Cyclotomic Number Generators
Date: Thu, 11 Mar 1999 15:53:10 -0700
Reply-To: [EMAIL PROTECTED]
R. Knauer wrote:
>
>
> Stream Ciphers and Number Theory (North-Holland
> Mathematical Library, V. 55)
> by Thomas W. Cusick, C. Ding, Ari Renvall
> Hardcover (April 1998)
> Elsevier Science; ISBN: 0444828737
>
> >> The cyclotomic generator is supposedly the most secure
> >> keystream generators known.
The binary cyclotomic generator relative to the prime P=2*Q+1 is given by:
F(x) = ( x^Q mod(P))mod 2 where the mod function returns 0...P-1.
This gives a mapping of the integers 0...P-1 to 0 or 1. What is interesting
is that this is equivalent to mapping a number x to 1 or 0 depending on
whether or not x is a quadratic residue of P. Even though the authors discuss
the Jacobi symbol (and Legendre symbol) they do not make this connection
(they probably thought it was obvious.) In the Feb 99 issue of Journal of
Number Theory (or maybe Jan) there is a discussion of the behavior of
quadratic residues by Maudit et al. Maudit shows that the quadratic residues
are evenly distributed and have little correlation.
The above computation is rather expensive for large P. The cyclotomic
generators for base 3 is much more complicated. I'll post how it works when I
work an example.
Tony
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Cyclotomic Number Generators
Date: Fri, 12 Mar 1999 00:55:05 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 11 Mar 1999 15:53:10 -0700, "Tony T. Warnock"
<[EMAIL PROTECTED]> wrote:
>The binary cyclotomic generator relative to the prime P=2*Q+1 is given by:
>F(x) = ( x^Q mod(P))mod 2 where the mod function returns 0...P-1.
The version the authors give for order 2 is (p. 199, op. cit.):
f(x) = (x^((N-1)/2) mod N) mod2, where N is prime.
>The above computation is rather expensive for large P.
You get what you pay for, eh.
>The cyclotomic
>generators for base 3 is much more complicated. I'll post how it works when I
>work an example.
My main interest is in whether this PRNG (see above) is crypto-grade
secure, as the authors claim.
Bob Knauer
"There's no way to rule innocent men. The only power any government
has is the power to crack down on criminals. Well, when there aren't
enough criminals, one makes them. One declares so many things to be
a crime that it becomes impossible to live without breaking laws."
--Ayn Rand
------------------------------
From: "Luke Herbert" <[EMAIL PROTECTED]>
Subject: How do i compute (a^b) mod n
Date: Fri, 12 Mar 1999 01:16:20 -0000
I would like to calculate (a^b) mod n
where a,b and n are large integers less than approx. 2*10^9.
thank you
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: sci.math
Subject: Re: Finite Field with Hard Division?
Date: Fri, 12 Mar 1999 01:04:11 GMT
In article <[EMAIL PROTECTED]>,
Anonymous <[EMAIL PROTECTED]> wrote:
> Is there a finite field where addition and multiplication
> are easy, but there is no known algorithm for finding
> multiplicative inverses in polynomial time?
No.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: "Luke Herbert" <[EMAIL PROTECTED]>
Subject: Re: How do i compute (a^b) mod n
Date: Fri, 12 Mar 1999 01:44:44 -0000
This way springs to mind:
function xtoymodn(x,y,n:integer):integer;
var result,mult,lp:integer;
begin
mult:= x mod n;
result:=1;
if mult=0 then result:=0
else if mult=1 then result:=1
else if mult=-1 then result:=1-2*(y mod 2)
else for lp:= 1 to y do result:=(result*mult) mod n;
xtoymodn:=result;
end;
I imagine it's not the most efficient implementation possible; perhaps
diving into a number theory textbook would provide some sneakier
methods.
(Note: I think I got the mod syntax right, it's been a while since
I've used it and I don't have a compiler handy to test it.)
------------------------------
From: "Luke Herbert" <[EMAIL PROTECTED]>
Subject: Re: How do i compute (a^b) mod n
Date: Fri, 12 Mar 1999 01:43:50 -0000
solution to my own problem:
As x*x mod n = (x mod n)*(x mod n) the following loop will do it
xmn := x mod n;
result := xmn;
for i := 2 to y do result := (result * xmn) mod n;
there is no owerflow if n^2 is less than maxlongint;
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: sci.chem.organomet,sci.cognitive,sci.comp-aided,sci.cryonics
Subject: NO CREDIT CARD
Date: 11 Mar 1999 23:12:39 GMT
100% ANONYMOUS, NO CREDIT CARD, NO SUBSCRIPTION, NO PASSWORD, NO CENSURING
Italian
www.thirdsex.com
English
www.xxx1on1.com
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: ElGamal vs RSA
Date: Thu, 11 Mar 1999 23:44:31 GMT
In article <[EMAIL PROTECTED]>,
Medical Electronics Lab <[EMAIL PROTECTED]> wrote:
> Sam Simpson wrote:
> >
> > BTW does anyone still use GF(2^n)? It said as long as 14-years
> > ago that GF(2^n) ought to be avoided in all cryptographic
> > applications - who would still consider it in the same breath as
> > GF(p)?
> >
> > Look forward to any pointers to more recent literature you may be
> > able to provide.
>
> Check out "Elliptic Curve Public Key Cryptosystems" for use of
> GF(2^n). Who said it should be avoided? Have you got a reference
> for that?
The discussion is about using GF(2^n) itself for ElGamal, not Elliptic
Curves over GF(2^n). Coppersmith's algorithm applied to the former makes it
unsuitable for cryptographic use.
I am one such reference.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: "F. Arndt" <[EMAIL PROTECTED]>
Subject: Crypto transmission in noisy ambient
Date: Thu, 11 Mar 1999 22:01:28 -0200
A low-power but strongly encrypted (RSA or ElGamal) exchange in the
presence of noise AND interference, such as often prevails in wireless
comm, would seem to be problematical. The conventional approach of
retransmitting until check-sums or CRC are satisfied is probably
standard operating procedure, but are there clever ways of making the
process distinctly more efficient for a given bit error rate (BER)?
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Crypto transmission in noisy ambient
Date: 12 Mar 1999 03:16:35 GMT
F. Arndt <[EMAIL PROTECTED]> wrote:
> A low-power but strongly encrypted (RSA or ElGamal) exchange in the
> presence of noise AND interference, such as often prevails in wireless
> comm, would seem to be problematical. The conventional approach of
> retransmitting until check-sums or CRC are satisfied is probably
> standard operating procedure, but are there clever ways of making the
> process distinctly more efficient for a given bit error rate (BER)?
could one develop and deploy an error correcting code of some kind, and
then simply send the encrypted bits encoded in that system, just like
any other message? I'm not sure if there's any special properties of
RSA that would allow for more efficient codes than normal, but if there
are some, then I'd love to hear about them. I know there's a journal of
designs, codes, and cryptography which may be a worthwhile place to look
for such things...
-David Molnar
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: ElGamal vs RSA
Date: Thu, 11 Mar 1999 19:47:58 -0800
[EMAIL PROTECTED] wrote in message <7c9kgt$3a$[EMAIL PROTECTED]>...
>The discussion is about using GF(2^n) itself for ElGamal, not Elliptic
>Curves over GF(2^n). Coppersmith's algorithm applied to the former makes
it
>unsuitable for cryptographic use.
I don't agree with this. Coppersmith's algorithm has the same asymptotics
as the best factoring method. For a given key size, DH over GF(2^n) is
slight less secure than RSA, but users can compensate for this by
choosing a larger key size. It is analogous to the way RSA users
have to choose a larger key size those using than DH over GF(p),
for equivalent security.
------------------------------
From: [EMAIL PROTECTED] (Michael Curry)
Subject: Re: ZKS Freedom Server
Date: Fri, 12 Mar 1999 04:16:26 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
On Thu, 11 Mar 1999 14:39:56 GMT, [EMAIL PROTECTED] wrote:
>Has anyone used this system? They gave a presentation at last
>year's Defcon. It sounded interested, but in reality it would be
>pretty slow.
>
>Basically it provides a way to use the Internet anonymously by
>having multiple layers of encryption that passes through many
>servers. Each server strips off a layer of encryption eventually
>getting to the data that is being transmitted.
The last I heard from ZKS was that the beta testing of Freedom
was supposed to be starting this month.
Mike
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 5.5.3i for non-commercial use
<http://www.pgpi.com>
Comment: http://www.io.com/~mcurry/pgppublic.html
iQA/AwUBNuiVBlWbm6I2lhO4EQKFAACeLkvl+S9nsJJWiFxnkZVXBYzSr/4AoL3U
FcH/csWEP61mU/4kPPF8KAfN
=eOio
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Chris Monico)
Subject: Re: Crypto transmission in noisy ambient
Date: Fri, 12 Mar 99 03:15:02 GMT
In article <7ca0uj$qmn$[EMAIL PROTECTED]>,
David A Molnar <[EMAIL PROTECTED]> wrote:
>F. Arndt <[EMAIL PROTECTED]> wrote:
>> A low-power but strongly encrypted (RSA or ElGamal) exchange in the
>> presence of noise AND interference, such as often prevails in
wireless
>> comm, would seem to be problematical. The conventional approach of
>> retransmitting until check-sums or CRC are satisfied is probably
>> standard operating procedure, but are there clever ways of making
the
>> process distinctly more efficient for a given bit error rate (BER)?
>
>could one develop and deploy an error correcting code of some kind,
and
>then simply send the encrypted bits encoded in that system, just like
>any other message? I'm not sure if there's any special properties of
>RSA that would allow for more efficient codes than normal, but if
there
>are some, then I'd love to hear about them. I know there's a journal
of
>designs, codes, and cryptography which may be a worthwhile place to
look
>for such things...
>
>-David Molnar
>
Why not just use a McEliece type system instead of RSA? If necessary,
one can always increase the block length to a larger size so that we
can add sufficient errors to make syndrome decoding hard, but still
have enough left-over error correcting capability for the given
channel (Goppa codes are asymptotically good, so this is certainly
possible). Then error correction and encryption are both done at once,
and more quickly than RSA anyway. The only real disadvantages of the
McEliece system are key length and message expansion, but you'd get
message expansion anyway encoding an RSA cipher-text. And the keysize
is a small price to pay for the added speed and simplicity.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Crypto transmission in noisy ambient
Date: Fri, 12 Mar 1999 06:50:48 GMT
"F. Arndt" wrote:
> A low-power but strongly encrypted (RSA or ElGamal) exchange in the
> presence of noise AND interference, such as often prevails in wireless
> comm, would seem to be problematical. The conventional approach of
> retransmitting until check-sums or CRC are satisfied is probably
> standard operating procedure, but are there clever ways of making the
> process distinctly more efficient for a given bit error rate (BER)?
But that's *not* the "conventional approach" for low S/N ratio.
What is normally used in such a situation is a "convolutional code",
originally developed by JPL for use in deep-space telemetry, as I
recall.
The usual convolutional code implements redundancy at the bit level.
What I would like to see is a block convolutional code with tweakable
parameters.
------------------------------
From: [EMAIL PROTECTED] (R. Dale Shipp)
Subject: Re: Certicom Benchmark
Date: Fri, 12 Mar 1999 07:18:40 GMT
Just curious, but two comments on what you are saying.
First -- what computer were the quoted times generated for (the 91.67 ms,
etc.)?
Second -- what were your times for the ECDH used in the comparison?
It may be that you have a more efficient compiler / computer /
implementation or whatever than was used in the Certicom Benchmarks. If
so, then you might well get equivalent improvements on both points on the
comparison and still end up with the same ratio that Certicom quoted.
IMO, you need to make the comparisons on the same playing field.
Dale
In article <lZVF2.1221$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> Concerning the benchmarks provided by Certicom at
> www.certicom.com/ecc/ipsec.html
>
>
> These benchmarks compare standard Diffie-Hellman (DH) with the Elliptic
> curve equivalent (ECDH). It would appear from the benchmarks that the EC
> method is up to 70 times faster than standard Diffie-Hellman for comparable
> levels of security. The text implies that the advantage to ECDH may in fact
> be even greater than that. While not disputing the figures quoted I would
> maintain that they do not accurately reflect the innate speed of each
> method. They compare the best acheived by Certicom with ECDH, with a
> particular 3rd party implementation of DH. So I implemented DH myself on a
> Pentium Pro 200MHz. The timings I get are in brackets after the times quoted
> in the benchmark.
>
>
> Key generation 1024-bit DH - 91.67ms (14ms)
> Shared secret 1024-bit DH - 108.33ms (17ms)
> Key generation 2048-bit DH - 611.67ms (65ms)
> Shared secret 2048-bit DH - 728.33ms (80ms)
>
>
> As you can see the differences are highly significant. It is suggested in
> the text that standard DH benefits from the use of the Pentium Pro
> co-processor. It doesn't, and I didn't use it.
>
>
> When I commented on these benchmarks before, I was surprised that even
> someone as knowledgable as our own patient, persistent and truthful Dr, mike
> was apparently happy to take them at face value. But to do so would in my
> opinion be a mistake.
>
>
> I then checked out the Certicom Whitepaper entitled "The Elliptic Curve
> Cryptosystem for Smart Cards", available from www.certicom.com In it is a
> table which would suggest that on another platform (UltraSPARC) DH is 226
> times slower than ECDH. I laughed so much I nearly fell off my chair. But
> really - I was shocked. And it is not so much that the EC implementation is
> amazingly fast (although it seems moderately impressive), but that the
> implementation that it is compared to is so grindingly slow.
>
>
> For a well-balanced comparison see Michael Weiner's article "Performance
> comparison of Public Key Cryptosystems" in RSA labs Cryptobytes, Vol. 4, No.
> 1, 1998 from www.rsa.com
> After a thoughtful analysis he gives some results (also from a Pentium
> 200MHz) which indicate that certain EC methods are about 50% faster when
> comparing DSA (1024-bits) with ECDSA (168 bits). He states that DH and ECDH
> are comparable speed-wise - which flatly contradicts Certicom's claims. He
> also makes the interesting observation that software implementations of
--
R. Dale Shipp
[EMAIL PROTECTED]
------------------------------
** 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
******************************
