Cryptography-Digest Digest #689, Volume #11 Tue, 2 May 00 19:13:01 EDT
Contents:
Re: A naive question (Bryan Olson)
Re: Any good attorneys? (Mok-Kong Shen)
Re: Any good attorneys? (Mok-Kong Shen)
Re: Cascading Crypto Attack (Mok-Kong Shen)
Re: Any good attorneys? (Tom St Denis)
Re: Cascading Crypto Attack (Richard Heathfield)
Re: German currency checksum question ? (Mike)
Re: Exporting public keys using VSC++ CryptoAPI ("Stou Sandalski")
Re: Exporting public keys using VSC++ CryptoAPI ("Stou Sandalski")
Re: factor large composite ("Dann Corbit")
----------------------------------------------------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: A naive question
Date: Tue, 02 May 2000 21:15:50 GMT
Mok-Kong Shen wrote:
> The problem is that, although I had previously read a few of Shannon's
> papers, I could only understand part of materials there, because of my
> poor background.
No, that is not the problem. The paper, Shannon's
"Communication Theory of Secrecy Systems", assumes very
little background. It builds the theory up from almost
nothing and exemplifies Einstein's maxim that things should
be expressed as simply as possible and no simpler.
It's on-line at:
http://www3.edgenet.net/dcowley/docs.html
> So I was hoping you would be kind enough to render
> help. Further, im my humble opinion, if I were you, who
> apparently have very good knowledge of Shannon's works, would
> at least, with the same or even less time and effort that you
> have put into the two last follow-ups, be easily able to
> instead write something that is a good sketch of the
> solution to my question, which presumably would also be of
> interest to a number of other readers of the group.
I recommend against trying to pick up the background from a
sketch. I cited the paper expecting that it would be of
interest to a number of readers, just as it has already been
for many.
Mr. Shen, if you think I expend time and effort in
unproductive directions, I can assure you the feeling is
mutual.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Any good attorneys?
Date: Wed, 03 May 2000 00:00:07 +0200
Terry Ritter wrote:
> <[EMAIL PROTECTED]> wrote:
>
> >An essential question, I think, is by how much a variant of a patented
> >algorithm must deviate from the patented algorithm before it is no longer
> >considered to be an imfringement of the patent?
>
> To know that one must read the specific claims in the specific patent.
Convincing. However, it indicates that one should have quite an amount
of expertise in interpretations that pertain to laws in general and to
patent laws in particular and should take care to have searched all the
relevant patents. Presumably it is quite tough for a normal private person
to do the task well and the engagement of a patent lawyer is a better
idea, which however can be fairly expensive.
> >Does there exist any
> >precedence cases so that one could at least get an appropriate feeling
> >of that certainly quite difficult issue. Just for an hypothetical example:
> >Suppose DES is patented. Can another algorithm use S-boxes that
> >have 6 input bits and 4 output bits, though the contents of the boxes
> >are not identical?
>
> Almost everything depends upon what the particular patent claims say.
I suppose that the clever patent lawyers who help the patent holders have
done their best to achieve as wide a coverage of the applied patents as
possible. So intuitively I think it might not be too bad an idea for persons
without expertise and without help of patent lawyers to take a largely
'avoidance' stategy, i.e. by all means to do a design such that it is almost
sure to have the maximum distance to all existing patents rather than
taking the risk of eventually coming too near to some of these and hence
getting troubles. (Patients who are allergic to animal hairs likewise always
take greatest pains to keep themselves far away from any pets.)
> >Can another algorithm do what is characteristic
> >of Feistel ciphers, i.e. alternatively process the left and right part of
> >the block? Is use of IP and inverse IP allowed? etc. etc. etc.
>
> Surely everything in DES has been out of patent for almost a decade.
But, for example, there are other algorithms that use S-boxes. Can one
say that, because the S-boxes of DES have currently no more patent
impacts (BTW was DES ever patented?), the S-boxes of a patented
algorithms can be imitated without problems?
Thanks.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Any good attorneys?
Date: Wed, 03 May 2000 00:07:56 +0200
Tom St Denis wrote:
> Eric Lee Green wrote:
> >
> > Mike Rosing wrote:
> > > It's an official "cease and desist" order, or they *can* take you to
> > > court.
> >
> > Hmm, I think you're right, U.S. courts think that all other countries in the
> > world are part the United States. I mean, we had no problem kidnapping Manuel
> > Noriega and putting him on trial in Miami for crimes that occurred in Panama,
> > so why worry about these little things called "international boundaries"?
> >
> > Canada, hmm, isn't that the 51st state? Why, let's sue this Canadian citizen
> > in a U.S. court!
> >
> > [Note: Not saying that Tom should not follow your advice, which obviously he
> > IS doing... just commenting on the sheer ludicrousness of quoting a U.S.
> > patent number to a Canadian citizen living in Canada].
>
> I think it's funny too, but I will just avoid all RSA (tm) products
> (hehehe) from CB in the future.
Do you really fear that you could be Noriega II?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Cascading Crypto Attack
Date: Wed, 03 May 2000 00:35:57 +0200
Richard Heathfield wrote:
> A recent thread (which I can't now find, hence this new thread)
> discussed the possibility of using more than one encryption technique:
>
> C = E2(E1(P))
>
> or even
>
> C = E9(E8(E7(E6(E5(E4(E3(E2(E1(P)))))))))
>
> It was later suggested that this could actually /weaken/ the encryption.
>
> If this is so, I have a suggested attack for any crypto system ever.
>
> Given any ciphertext, progressively weaken it by applying more and more
> encryptions of different kinds to it, until eventually the plaintext is
> revealed.
>
> Like the well-loved 1 == 2 proofs, this is (a) counter-intuitive and (b)
> surely wrong. Yet it proceeds logically from the proposal that
> successive encryptions weaken security.
>
> Where is the flaw?
I guess that there is the following flaw in your argument: the weakening
may tend to a certain limit that is not zero, so you never get the
plaintext.
On the other hand, David Wagner said that cascading never weakens
if independent keys are used. Perhaps he would let us know a rigorous
proof of the claim.
M. K. Shen
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Any good attorneys?
Date: Tue, 02 May 2000 22:32:25 GMT
Paul Rubin wrote:
>
> In article <[EMAIL PROTECTED]>,
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> >I think it's funny too, but I will just avoid all RSA (tm) products
> >(hehehe) from CB in the future.
> >
> >I already have other block ciphers (Blowfish, Twofish, Serpent,
> >CAST-128, Skip-jack, XTEA, GOST), and am adding DH to it now.
>
> I'd say bag RC5 for sure. There's not much reason to care about it.
> However, the RSA public key algorithm is important and your product
> suffers if you don't include it. Even though you're in Canada and
> it's unpatented there, you might want to avoid hassles by leaving it
> out for now. But on September 20 when the US patent expires, please
> put it back.
Hmm well I already deleted the source (I could restore it from backup)
but I seriously want to avoid RSA completely. I don't like getting
emails like that.
At anyrate ElGamal will fill the spot where RSA was quite nicely.
I just need a DH pro to talk to (i.e how to minimize the ciphertext size
but remain relatively secure).
Tom
------------------------------
Date: Tue, 02 May 2000 23:47:22 +0100
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: Cascading Crypto Attack
"David A. Wagner" wrote:
>
> In article <[EMAIL PROTECTED]>,
> Richard Heathfield <[EMAIL PROTECTED]> wrote:
> > It was later suggested that this could actually /weaken/ the encryption.
>
> Only if the keys used in the cascade aren't independent.
> (Or if you care about probable-plaintext attacks.)
>
> > If this is so, I have a suggested attack for any crypto system ever.
> >
> > Given any ciphertext, progressively weaken it by applying more and more
> > encryptions of different kinds to it, until eventually the plaintext is
> > revealed.
>
> Yup. That gedanken-"attack" actually proves that cascading can't
> weaken the cipher, when you use independent keys. Do you see why?
I can certainly see the necessity to use independent keys when one is
'super-encrypting', but I am not wise enough in the ways of cryptology
to see the proof that cascading doesn't weaken the cipher. Not that I
think it does, of course - but there's a difference (if I may extend my
own analogy a little) between my seeing that 1 == 2 is obviously false
and my being able to find the illegal division by (a - b) on which the
fallacy is based, or my understanding why the division is illegal.
>
> (This needs to be made precise, and there is a small tweak
> or two needed to the result when you do that, but roughly speaking,
> it is accurate, and gives a nice intuitive feel for the formal proof.)
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
34 K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html (63
to go)
------------------------------
From: Mike <[EMAIL PROTECTED]>
Subject: Re: German currency checksum question ?
Reply-To: [EMAIL PROTECTED]
Date: Tue, 02 May 2000 22:51:40 GMT
Ed C <[EMAIL PROTECTED]> wrote:
> I am trying to figure out the checksum used on German currency.
> Please contact me if you know the algorithm or a way to determine it.
Hi
Is this it? This came up on this group a few weeks ago:
Message-ID: <[EMAIL PROTECTED]>
Date: Wed, 12 Apr 2000 14:09:57 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Newsgroups: sci.crypt
Subject: Re: Checksum for digits
lordcow77 schrieb:
> Verhoeff's check digit scheme based on the symmetry of the
> dihedral group D_5 catches all single errors, all adjacent
> transpositions, and most twin errors and other transpositions.
Well this is an old piece of code of mine which was taken
from an article of the german magazine ct in 04/1997 (no
its not the april joke ;-) ). Hope it helps :)
__________________________
/*
** dieder.h Mon, Mar 17 1997
**
** Copyright (c) 1997, Runu Knips, Siegen, Germany
** All rights reserved. No warranty.
**
** $Id$
**
** Last Edit: Tue, Mar 18 1997
**
** $Log$
*/
#ifndef INTERFACE_dieder
#define INTERFACE_dieder
#ifdef __GNUG__
#pragma interface
#endif
/*
** Checksum for expanded bcd format numbers. Secound
** argument is always the length. For compute_verhoeff,
** the third argument is the position of the checking
** char as 3rd argument; specify -1 and put the number
** after the last position if you want.
**
** The compute_* functions will return a number between
** 0 and 9, which is the checksum, or -1 for error.
** The check function will return a bool value
** (0 = false, 1 = true).
*/
extern int compute_dieder (const char[], int);
extern int compute_verhoeff (const char[], int, int);
extern int check_verhoeff (const char[], int);
/*
** Check a german money string. This will take
** an ascii string argument (of fixed size 12)
** and return the character which should stand
** at the 12th position (which isn't checked
** by itself).
** Be warned: check_german_money_cksum is an
** macro which evaluates its argument multiple
** times!
*/
extern int compute_german_money_chksum (const char[]);
#define check_german_money_cksum(s) \
((s[11]) == compute_german_money_chksum(s))
#endif /* !def(INTERFACE_dieder) */
__________________________
/*
** dieder.c Mon, Mar 17 1997
**
** Copyright (c) 1997 Runu Knips, Siegen, Germany
** All rigths reserved. No warranty.
**
** Checksum program using dieder groups (and
** especially dieder multiplication). Works for
** decimal numbers only!
**
** Contained is an implementation of a permutated
** dieder group checksum, the algorithm for german
** money, and the verhoeff permutation.
**
** Source: c't april 1997, page 452 (article 448ff).
**
** Last Edit: Tue, Mar 18 1997
**
** $Log$
*/
#ifdef __GNUG__
#pragma implementation "dieder.h"
#endif
#ifndef lint
static char RCSid[] = "$Id$";
#endif
#include <string.h>
#include <ctype.h>
#include "dieder.h"
/******************************************************/
/* dieder multiplication (always mod 10) */
static const int dieder_mult[10][10] = {
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 },
{ 1, 2, 3, 4, 0, 6, 7, 8, 9, 5 },
{ 2, 3, 4, 0, 1, 7, 8, 9, 5, 6 },
{ 3, 4, 0, 1, 2, 8, 9, 5, 6, 7 },
{ 4, 0, 1, 2, 3, 9, 5, 6, 7, 8 },
{ 5, 9, 8, 7, 6, 0, 4, 3, 2, 1 },
{ 6, 5, 9, 8, 7, 1, 0, 4, 3, 2 },
{ 7, 6, 5, 9, 8, 2, 1, 0, 4, 3 },
{ 8, 7, 6, 5, 9, 3, 2, 1, 0, 4 },
{ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }
};
/* permutation for better dieder chksum */
static const int dieder_perm[8][10] = {
{ 1, 5, 7, 6, 2, 8, 3, 0, 9, 4 },
{ 5, 8, 0, 3, 7, 9, 6, 1, 4, 2 },
{ 8, 9, 1, 6, 0, 4, 3, 5, 2, 7 },
{ 9, 4, 5, 3, 1, 2, 6, 8, 7, 0 },
{ 4, 2, 8, 6, 5, 7, 3, 9, 0, 1 },
{ 2, 7, 9, 3, 8, 0, 6, 4, 1, 5 },
{ 7, 0, 4, 6, 9, 1, 3, 2, 5, 8 },
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
};
/* inverse of dieder multiplication */
static const int dieder_mult_inv[10] =
{ 0, 4, 3, 2, 1, 5, 6, 7, 8, 9 };
/* permutation table of verhoeff */
static const int verhoeff_perm [12][10] = {
{ 2, 8, 6, 3, 4, 1, 0, 9, 7, 5 },
{ 3, 1, 2, 0, 4, 5, 6, 7, 8, 9 },
{ 4, 9, 1, 2, 5, 6, 3, 0, 7, 8 },
{ 4, 8, 5, 0, 9, 7, 2, 6, 3, 1 },
{ 1, 2, 6, 9, 4, 5, 7, 8, 3, 0 },
{ 3, 5, 0, 1, 2, 8, 9, 6, 7, 4 },
{ 3, 8, 9, 4, 7, 2, 6, 1, 5, 0 },
{ 2, 4, 8, 6, 9, 0, 7, 1, 3, 5 },
{ 1, 7, 9, 5, 0, 3, 8, 6, 4, 2 },
{ 1, 8, 2, 9, 5, 0, 4, 7, 6, 3 },
{ 4, 3, 2, 6, 8, 7, 0, 1, 5, 9 },
{ 2, 6, 9, 8, 5, 4, 1, 3, 0, 7 }
};
/* inverse permutation table */
static const int verhoeff_inv_perm [12][10] = {
{ 6, 5, 0, 3, 4, 9, 2, 8, 1, 7 },
{ 3, 1, 2, 0, 4, 5, 6, 7, 8, 9 },
{ 7, 2, 3, 6, 0, 4, 5, 8, 9, 1 },
{ 3, 9, 6, 8, 0, 2, 7, 5, 1, 4 },
{ 9, 0, 1, 8, 4, 5, 2, 6, 7, 3 },
{ 2, 3, 4, 0, 9, 1, 7, 8, 5, 6 },
{ 9, 7, 5, 0, 3, 8, 6, 4, 1, 2 },
{ 5, 7, 0, 8, 1, 9, 3, 6, 2, 4 },
{ 4, 0, 9, 5, 8, 3, 7, 1, 6, 2 },
{ 5, 0, 2, 9, 6, 4, 8, 7, 1, 3 },
{ 6, 7, 2, 1, 0, 8, 3, 5, 4, 9 },
{ 8, 6, 0, 7, 5, 4, 1, 9, 3, 2 }
};
/* @@@: fixme: that may not work under strange character systems */
#define to_digit(ch) ((ch) + '0')
#define from_digit(ch) ((ch) - '0')
/******************************************************/
int
compute_dieder (const char arg[], int len)
{
int i, j, res;
for (res = 0, i = 0; i < len; i++) {
j = dieder_perm [i % 8] [arg [i]];
res = dieder_mult [res] [j];
}
return res;
}
/*
** Get the checksum for a german money number.
*/
int
compute_german_money_chksum (const char arg[])
{
int ch, i, j, res;
char tmp[11];
/* at these positions, alphanumeric chars
** are in the string.
*/
static const int alpha_pos[3] = { 0, 1, 9 };
/* we change fields in the string, so.. */
memcpy (tmp, arg, sizeof(tmp));
for (i = (sizeof(alpha_pos) / sizeof(int)); i--;) {
j = alpha_pos[i];
switch (tmp[j]) {
case 'a': case 'A': ch = '0'; break;
case 'd': case 'D': ch = '1'; break;
case 'g': case 'G': ch = '2'; break;
case 'k': case 'K': ch = '3'; break;
case 'l': case 'L': ch = '4'; break;
case 'n': case 'N': ch = '5'; break;
case 's': case 'S': ch = '6'; break;
case 'u': case 'U': ch = '7'; break;
case 'y': case 'Y': ch = '8'; break;
case 'z': case 'Z': ch = '9'; break;
default: return -1; /* error: unallowed char */
}
tmp[j] = ch;
}
res = 0;
for (i = 0; i < sizeof(tmp); i++) {
ch = tmp[i];
if (! isdigit (ch)) {
return -1;
}
j = from_digit (ch);
if (i < 10) {
j = dieder_perm [i % 8] [j];
}
res = dieder_mult [res] [j];
}
return to_digit(res);
}
/*
** If pos < 0, or pos >= len, you may append the
** result to the number.
*/
int
compute_verhoeff (const char arg[], int len, int pos)
{
int i, j, res, left, right;
for (left = 0, i = 0, res = 0; i < len; i++) {
if (i == pos) {
left = res;
res = 0;
continue;
}
j = verhoeff_perm [i % 12] [arg [i]];
res = dieder_mult [res] [j];
}
right = res;
/* force (left * perm[pos+1][res] * right == 0) */
i = dieder_mult [dieder_inv_mult [left]] [dieder_inv_mult [right]];
res = verhoeff_inv_perm [pos % 12] [i];
return res;
}
/* @@@: checkme: This had been cutted from the c't listing,
** but I guess it's correct this way.
*/
int
check_verhoeff (const char arg[], int len)
{
int i, j, res;
for (i = 0, res = 0; i < len; i++) {
j = verhoeff_perm [i % 12] [arg [i]];
res = dieder_mult [res] [j];
}
return res == 0;
}
------------------------------
From: "Stou Sandalski" <tangui [EMAIL PROTECTED]>
Subject: Re: Exporting public keys using VSC++ CryptoAPI
Date: Tue, 2 May 2000 15:54:44 -0700
I very very very seriously discourage use of the MSFT CryptoAPI. Not only is
it microsoft, but there was an issue with an extra private key called NSAkey
which some people suspected can be used by the NSA to install their own app
(it was something like that wasn't it ?) between your app and the cryptoapi
hence capturing your shiznet before it ever gets crypted....
check out www.cryptonym.com for more info on that.
If you absolutley must use cryptoapi try going to msdn.microsoft.com maybe
there you can find info on what you are looking for
Stou
<[EMAIL PROTECTED]> wrote in message news:8endjm$s6a$[EMAIL PROTECTED]...
> Where can I find an example of exporting a public key using
> CryptExportKey? For some reason I don't know the RSAPUBKEY structure
> that my function writes does not contain the RSA1 header. On import
> (CryptImportKey) of this (wrong?) key using the same crypto provider
> and application software on the same computer I get a "Bad version of
> Provider"
>
> Thanks!
>
> Eric
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: "Stou Sandalski" <tangui [EMAIL PROTECTED]>
Subject: Re: Exporting public keys using VSC++ CryptoAPI
Date: Tue, 2 May 2000 15:56:57 -0700
Also peep out
microsoft.public.cryptoapi
<[EMAIL PROTECTED]> wrote in message news:8endjm$s6a$[EMAIL PROTECTED]...
> Where can I find an example of exporting a public key using
> CryptExportKey? For some reason I don't know the RSAPUBKEY structure
> that my function writes does not contain the RSA1 header. On import
> (CryptImportKey) of this (wrong?) key using the same crypto provider
> and application software on the same computer I get a "Bad version of
> Provider"
>
> Thanks!
>
> Eric
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: "Dann Corbit" <[EMAIL PROTECTED]>
Subject: Re: factor large composite
Date: Tue, 2 May 2000 15:57:51 -0700
"Diet NSA" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <AKsP4.3045$d63.2572@client>, "Dann Corbit"
> <[EMAIL PROTECTED]> wrote:
>
> >No one includes yourself, obviously.
>
>
> Yes, Sherlock. The set of "no one" (i.e., no humans) would also
> include myself as a member.
>
>
> >What useful results have been created as far as factoring large
> numbers with
> >QC? [none] If there are none, then it is "pie-in-the-sky"
>
>
> Try telling this to the governments who provide the funding and
> to the researchers in the field. (Of course, the researchers have
> a vested interest in keeping the field alive, and do review each
> other's grant proposals). To gauge more about the potential
> feasibility of QC check out, especially, the journal "Nature" vol
> 404, page 368, or contact various other experts (or look at their
> papers) to see what their *guesses* are.
QC is currently absurdly infeasible for factoring of large numbers and there
are no valid projections as to when it will become feasible, or if it ever
will, for that matter. Have another slice of pie.
> >You obviously don't know what hyperbole means either.
>
>
> "Hyperbole" usually means intentional exaggeration, but I still
> don't know what "FCOL" means.
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. Newsgroup http://www.dejanews.com/~c_a_p
C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
