Cryptography-Digest Digest #609, Volume #12 Mon, 4 Sep 00 09:13:01 EDT
Contents:
Re: more on that neat prime generator (Mok-Kong Shen)
Re: PGP 6.5.8 test: That's NOT enough !!! ("Michel Bouissou")
Re: RSA public exponent (Paul Schlyter)
Re: PGP Bug: A note from Ralf Senderek ("Michel Bouissou")
Re: Patent, Patent is a nightmare, all software patent shuld not be allowed
(Jonathan Thornburg)
Basic Research Opportunities in Ireland ([EMAIL PROTECTED])
Re: 96-bit LFSR needed (Tim Tyler)
Re: RSA public exponent (Thomas Pornin)
Re: 4x4 s-boxes (Tim Tyler)
Re: New cryption method... (PROdotes)
RSA Patent. ("ajd")
Re: New cryption method... (PROdotes)
Re: RSA public exponent ("Neil McKeeney")
Big numbers (Soeren Gammelmark)
Re: DES weak keys in 3DES (Gisle =?iso-8859-1?Q?S=E6lensminde?=)
Re: DES weak keys in 3DES (Gisle =?iso-8859-1?Q?S=E6lensminde?=)
Re: Big numbers (Anders Thulin)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: more on that neat prime generator
Date: Mon, 04 Sep 2000 12:23:25 +0200
David A Molnar wrote:
>
> [EMAIL PROTECTED] wrote:
[snip]
> BTW, the first time I saw the observation which you made about how
> the existence of a generator implies the number is prime was in
>
> Vaughan R. Pratt. Every prime has a succinct certificate. SIAM Journal on
> Computing, 4(3):214-220, September 1975
A proof I know runs like this: For m>=2 and (a,m)=1
we have ord_m(a)|phi(m) and phi(m)<=m-1. Since
ord_m(g)=m-1, we have phi(m)=m-1 and hence m is prime.
M. K. Shen
------------------------------
From: "Michel Bouissou" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: PGP 6.5.8 test: That's NOT enough !!!
Date: Mon, 4 Sep 2000 12:18:17 +0200
Bj�rn Persson <[EMAIL PROTECTED]> a �crit dans le
message : [EMAIL PROTECTED]
>
> >Reading the Senderek report got me stunned. I was very amazed about the
> >existance of a data part in a public key information record unprotected
> >by a signature. Is there anything that should go into the non-hashed part
> >of a public-key block ? From what I see so far the part not protected by
> >a signature should remain empty and a warning should be issued if
> >anything is in there. Why is there even such a thing as the non-hashed
> >part ?
>
> That's a question that I too would very much like to get answered.
RFC2440 (gotten from http://www.gnupg.org/rfc2440-5.html) states:
(The most interesting part is close to the end ;-)
<<<<<
*>5.2.3. Version 4 Signature Packet Format
*>
*> The body of a version 4 Signature Packet contains:
*>
*> - One-octet version number (4).
*>
*> - One-octet signature type.
*>
*> - One-octet public key algorithm.
*>
*> - One-octet hash algorithm.
*>
*> - Two-octet scalar octet count for following hashed subpacket
*> data. Note that this is the length in octets of all of the hashed
*> subpackets; a pointer incremented by this number will skip over
*> the hashed subpackets.
*>
*> - Hashed subpacket data. (zero or more subpackets)
*>
*> - Two-octet scalar octet count for following unhashed subpacket
*> data. Note that this is the length in octets of all of the
*> unhashed subpackets; a pointer incremented by this number will
*> skip over the unhashed subpackets.
*>
*> - Unhashed subpacket data. (zero or more subpackets)
*>
*> - Two-octet field holding left 16 bits of signed hash value.
*>
*> - One or more multi-precision integers comprising the signature.
*> This portion is algorithm specific, as described above.
*>
*> The data being signed is hashed, and then the signature data from the
*> version number through the hashed subpacket data (inclusive) is
*> hashed. The resulting hash value is what is signed. The left 16 bits
*> of the hash are included in the signature packet to provide a quick
*> test to reject some invalid signatures.
*>
*> There are two fields consisting of signature subpackets. The first
*> field is hashed with the rest of the signature data, while the second
*> is unhashed. The second set of subpackets is not cryptographically
*> protected by the signature and should include only advisory
*> information.
*>
*> The algorithms for converting the hash function result to a signature
*> are described in a section below.
>>>>>
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: RSA public exponent
Date: 4 Sep 2000 11:46:34 +0200
In article <8ovcoe$ur0$[EMAIL PROTECTED]>,
Bryan Olson <[EMAIL PROTECTED]> wrote:
> Paul Schlyter wrote:
>
>> Why can't both the private and the public exponents be long btw?
>> Suppose I would want both the private and the public exponent
>> to be of the same length as the modulus - how would I do that?
>
> They can. The point is that given the current
> best-practice on use of RSA, the sizes you are supposing
> are slower for public key operations and have no known or
> expected security advantages.
>
> How would you do that? I don't understand the question.
> What is stopping you?
What I'm really asking is this:
Normally, when choosing RSA exponent, you first set the public
expinent as either 3, 17 or 65537 -- usually 65537. From that
the private exponent is computed.
If I instead wanted a full-lengtg public exponent too, it must
be selected somehow. How would I do that? Would any odd
random number do? Or any prime? Or would I have to use some
other criterion to select the public exponent?
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: "Michel Bouissou" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: PGP Bug: A note from Ralf Senderek
Date: Mon, 4 Sep 2000 12:25:34 +0200
Bj�rn Persson <[EMAIL PROTECTED]> a �crit dans le
message : [EMAIL PROTECTED]
>
> >I (and not Ralf) was using PGP 6.5.8 that I was evaluating, and that
> >is why Ralf's public key, which I extracted from my own public
> >keyring, shows a 6.5.8 version stamp. This comes from me, not from
> >Ralf.
>
> Hey! What's the point in including a version note in a "public key
> block" if it doesn't tell which version of PGP created the key or which
> version the key's owner is using? Here we have yet another example of
> sloppy design in the user interface.
Every PGP version has always included its OWN version number for each
encrypted message, armored message, signature or key block it generates.
A PGP public-keyblock will thus always display the PGP version that
extracted the key, not the PGP version that created the key.
Note that you can export several different keys, possibly initially made
with different PGP versions, in the same armored "PGP public keyblock". How
would you display the PGP version that made the different keys then ?
The PGP version displayed has nothing to do with the CONTENTS of the
encrypted or armored data. It's just a hint about the PGP version that made
it (and thus possibly shows the PGP version you might need to decrypt or
import the data or check the signature).
GnuPG behaves the same.
Misunderstanding this is a user mistake, not a software fault.
Best regards.
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Jonathan Thornburg)
Subject: Re: Patent, Patent is a nightmare, all software patent shuld not be allowed
Date: 4 Sep 2000 12:26:37 +0200
In article <8oij9n$ipd$[EMAIL PROTECTED]>,
Bill Unruh <[EMAIL PROTECTED]> wrote:
>[[...]] the patent office does not
>appear to be terribly up to date on the state of any field. See the
>recent patent awarded for faster than light communication.
Another patent of a fairly well-known idea:
http://www.patents.ibm.com/details?&pn=US05443036__
US patent #5443036: Method of exercising a cat
filed 2 Nov 1993, issued 22 Aug 1995
Abstract:
A method for inducing cats to exercise consists of directing a beam
of invisible light produced by a hand-held laser apparatus onto the
floor or wall or other opaque surface in the vicinity of the cat,
then moving the laser so as to cause the bright pattern of light to
move in an irregular way fascinating to cats, and to any other animal
with a chase instinct.
No indication of royalties or licensing arrangements...
--
-- Jonathan Thornburg <[EMAIL PROTECTED]>
http://www.thp.univie.ac.at/~jthorn/home.html
Universitaet Wien (Vienna, Austria) / Institut fuer Theoretische Physik
"C++ is to programming as sex is to reproduction. Better ways might
technically exist but they're not nearly as much fun." -- Nikolai Irgens
------------------------------
From: [EMAIL PROTECTED]
Subject: Basic Research Opportunities in Ireland
Date: Mon, 04 Sep 2000 10:28:04 GMT
The Irish Government has put out a call for "world-famous
researchers" to work here, in basic scientific research
that has relevance to "information and communications
technology". It has put up US600 million for this work.
Details are at http://www.sfi.ie/
We at the National University of Ireland would welcome
hosting a research group under this scheme. I have worked
in both Computing & Math Departments, and there is expertise
here in pure & applied math, theoretical physics and many
areas of computing, to mention a few. Cryptography is also
an area of current interest.
If anyone would like more information, or would like to
discuss further possible research topics to propose under
this call, please reply very soon: The closing date
for applications is SEPTEMBER 26.
Regards,
Dr. M. Mc Gettrick,
NUI, Galway
.........................................................................
Michael Mc Gettrick tel: +353-91-524411, ext. 3718
Dept. of Information Technology http://www.nuigalway.ie/mat/gettrick/
National University of Ireland [EMAIL PROTECTED]
IRL - GALWAY fax: +353-91-750501
.........................................................................
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: 96-bit LFSR needed
Reply-To: [EMAIL PROTECTED]
Date: Mon, 4 Sep 2000 10:38:57 GMT
Mack <[EMAIL PROTECTED]> wrote:
[the version currently on Scott's site...]
: The version I have does not have an attribution of
: authorship. I thought it came from Scott Nelsons site. [...]
Aha! ;-) ftp://helsbreth.org/pub/helsbret/random/
has a more recent version than the one I'm looking at in lfsr_src.zip.
I was looking at the lfsr_s.c file instead. Thanks.
: Sounds like the original version used a seive. [...]
It did. It practically ground to a halt around 2^64 on my machine.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: [EMAIL PROTECTED] (Thomas Pornin)
Subject: Re: RSA public exponent
Date: 4 Sep 2000 10:57:35 GMT
According to Paul Schlyter <[EMAIL PROTECTED]>:
> If I instead wanted a full-length public exponent too, it must
> be selected somehow. How would I do that?
Select it at random. All that is required is that it must be relatively
prime to phi(N)=(p-1)(q-1) where N=pq is the modulus.
65537 is useful because it is prime, and therefore has a high probability
of being relatively prime to phi(N) for a randomely chosen N. But there
is no obligation to choose a prime number.
--Thomas Pornin
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: 4x4 s-boxes
Reply-To: [EMAIL PROTECTED]
Date: Mon, 4 Sep 2000 10:45:15 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
: Terry Ritter wrote:
:> While the FT originally defined "bent," most modern treatments use
:> the FWT.
: ? What does the definition of bent function look like in terms
: of Walsh transforms?
Bent function <-> "All entries in the WT have the same magnitude".
: Is it as simple as the FT version?
It's extremely simple.
:> As far as I know, in modern open cryptography, these concepts
:> [maximal nonlinearity and uniform Fourier weights] are the same.
: They can't be the same, because the latter defines a bent function
: but you guys are claiming that bent functions aren't maximally
: nonlinear.
Only Tom's claiming that AFAICS. Everyone else appears to be disagreeing.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Breast is best.
------------------------------
From: PROdotes <[EMAIL PROTECTED]>
Subject: Re: New cryption method...
Date: Mon, 4 Sep 2000 13:29:30 -0700
> HEY EVERYBODY I Got a sick assss crypto method... its unbreakable I SWEAR...
> I don't really want to tell you exactly what it is, but get this... I
> basicaly take some plain text and use some random transformations to
> semi-randomly generate cipher text bits by using huge(!) amounts of
> entropicaly large bits scrambled using a quad-trilinear G-Box, which in turn
> inverts the non-inverted dirty bits, then calculating f(x) for x^n mod y log
> z, and I get like 22.3 X 10 ^ -31337 combinations for scrambling the data...
> the crypto is unbrakable EVEN IF YOU HAVE THE PASSWORD!!!!! if thats not
> good crypto I don't know what the hell it is! Tomorow I am porting it to
> compiled basic for an AS/400, since my atari is way tooo slow to do these
> insane transformations... I bet you its unbreakable and crazy... don't fuck
> with me people my crypto is LEEET
Well... let's put it this way... you took the "piss me off" a bit to
wordly.. I know that I'm a newbie and I don't have much knowledge... I'm
playing with encryption from my 13 life year now... I have seen many
STUPID things in my life... I won't even tell you what some of my friends
tryed to use for encryption (ok... it's better then the Cesar method) but
this attempt was to look at the text from a new point of view... As
picture... At first I had some algorithms as you described them... I
quote: "unbreakable EVEN IF YOU HAVE THE PASSWORD!!!!!", and even this
test that I did... you were partialy right... I used an QB 4.5 compiler
do code it... It works fine... ok... I haven't thought about an divide
and conquer algorithm for breaking it at first... But this approach works
very good and the only problem is that it can be broken if you know the
PRNG code and the number of iterations... else... without having the
"key" or the cleartext it has as many combinations as the key has... if
my formula gives an greater number than the combination of the key of
course...
And if you think you're such an SMARTASS then tell your "ego" and your
"id" to go and visit an skilled psychiatrist. I know that great man
should have an great "ego" but if the "ego" is to great then it's nothing
but a "pain in the ass"
THNX for reading.
P.S. I'm going on a trip this week so I'll get to answering later on.
------------------------------
From: "ajd" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: RSA Patent.
Date: Fri, 1 Sep 2000 15:26:58 +0100
Hi,
I hear that the patent for the RSA encryption algorithm expires at the end
of this month. Does this mean that I can create commercial RSA
software/chips with no licence/royalty issues? Was the patent for USA only
or did it include Europe?
thanks for you help
ajd
------------------------------
From: PROdotes <[EMAIL PROTECTED]>
Subject: Re: New cryption method...
Date: Mon, 4 Sep 2000 13:42:21 -0700
> I think the problem is not that he doesn't WANT to disclose the algorithm.
> He CAN'T find a suitable way to describe it, the reason being probably that
> he is not comfortable with exact sciences in general and math in particular
> (not my opinion, he confessed). I admit it won't help him in a "sci."
> newsgroup.
OK, ok... if you want to know it... I'm going for a trip today... as I
said in another post... I'm going at the university... I think it's going
to be comp. sci. but if I don't make it there is an place waiting for me
at the physics univ.
So not that I'm not very good at science... as I said... I just haven't
gotten very much of the knowledge there is to learn.
> After much talk, I was able to "debabble" the algorithm (that's where being
> a computer scientist - faced every so often with clients "explaining" in
> their own terms what they want - is helpful :-). If you carefully read the
> thread, you'll have it in mostly understandable form.
Sorry... but I'm a bit in a bad mood these days and I didn't want to
write an pseudo code...
> And after all, despite many flaws, that algorithm is not *that* bad. Hey, at
> least, it's not a variation on "get a key, repeat it and xor it with the
> message".
I'm out of this phase... I use it sometimes to tell my younger friends
some better aproaches to encryption that they have... they got ideas
like...
1. Input key (number from 1 to 256)
2. take the "char" number from the cleartext.
3. multiply it with an "key"
4. store the output as an "integer"
5. repeat steps 2. to 4 till end of file...
Scrambeling and binary operations are good things... much can be done
with then...
I think it could be "something" with a little more time... the problem
should, ad said, a new PRNG... If anyone want's to help me... go ahead...
But laughing at me won't do much good....
THNX Stephan...
Till a few days...
------------------------------
From: "Neil McKeeney" <[EMAIL PROTECTED]>
Subject: Re: RSA public exponent
Date: Mon, 4 Sep 2000 14:51:58 +0200
> These smartcards usually encrypt using the private (i.e. slow) key
> anyway. That's the purpose of these cards: to store the private key
> in a secure way, so it only can be executed, but not read.
During an EMV electronic transaction most of the RSA calculations performed
(both by the terminal and the card) are done with the public key (half of
them are just verifications of key certificates).
------------------------------
From: Soeren Gammelmark <[EMAIL PROTECTED]>
Subject: Big numbers
Date: Mon, 04 Sep 2000 14:47:36 +0200
Hi
Is there a fast way to calculate with very large numbers (e.g. 10000
bits) in C or C++. I have a Borland C++ Builder compiler and I would
like to know if there is a support for such large numbers. If no such
exists, I would like to know a fast and effecient division and modulus
funktion.
Thanks
S=F8ren G
------------------------------
From: [EMAIL PROTECTED] (Gisle =?iso-8859-1?Q?S=E6lensminde?=)
Subject: Re: DES weak keys in 3DES
Date: 4 Sep 2000 14:59:23 +0200
In article <8ots2c$iif$[EMAIL PROTECTED]>, Scott Fluhrer wrote:
>
>Mark Wooding <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> Gisle S�lensminde <[EMAIL PROTECTED]> wrote:
>>
>> > DES have a number of weak and semi-weak keys, but in 3DES
>> > (DES-EDE3) tree independent keys is used. How is the securiy if
>> > one (or two) of these keys are weak. Shoud the key be avoided if
>> > any of the DES-keys are weak, or must as least two of them be
>> > weak before it becomes a problem.
>>
>> I believe that rejecting a single weak key is not beneficial. To notice
>> the weak key being used, you'd have to successfully guess the other two
>> keys, which is harder than attacking the full triple encryption (using,
>> e.g., meet-in-the-middle or Lucks' probabilistic attack).
>>
>> I'd reject two weak keys out of three, though, if I were the sort of
>> person who rejects weak keys.
>
>Actually, if you were worried about 3DES "weak keys", it'd worry first about
>keys where either the first and second DES keys were the same, or the second
>and third keys where the same. This has approximately as much likelihood of
>happening by random chance as picking one of the three keys to be a DES weak
>key, however, it reduces the cipher to DES, which would appear to be a more
>severe weakness than using even two weak keys in 3DES...
I so already check that k1 != k2 and k2 != k3, and rejects the key
if that's the case. As you say, this reduce 3DES-EDE to DES, which
not is desirable. By now I reject any weak or semi-weak keys
just in case, but I couldn't find any analysis or advise on the
area of weak keys. Do you know about information about this topic?
--
--
Gisle S�lensminde ( [EMAIL PROTECTED] )
With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going
to land, and it could be dangerous sitting under them as they fly
overhead. (from RFC 1925)
------------------------------
From: [EMAIL PROTECTED] (Gisle =?iso-8859-1?Q?S=E6lensminde?=)
Subject: Re: DES weak keys in 3DES
Date: 4 Sep 2000 15:06:52 +0200
In article <[EMAIL PROTECTED]>, Ragni Ryvold Arnesen wrote:
>Is it possible to distinguish ciphertext produced by DES/3DES using weak
>keys from any other ciphertext?
>
>If not, then weak keys are no problem since you cannot do better than brute
>force anyway.
In the case of three times encryption, I can find problems with
weak keys like you describes. In the case of
encryption-decryption-encryption which is specified to 3des use,
I cannot find any such problems by simple analysis, but that dosen't
mean that they don't exist. I don't trust my own analysis that much.
--
Gisle S�lensminde ( [EMAIL PROTECTED] )
With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going
to land, and it could be dangerous sitting under them as they fly
overhead. (from RFC 1925)
------------------------------
From: Anders Thulin <[EMAIL PROTECTED]>
Subject: Re: Big numbers
Date: Mon, 4 Sep 2000 13:02:39 GMT
Soeren Gammelmark wrote:
> Is there a fast way to calculate with very large numbers (e.g. 10000
> bits) in C or C++.
Try GMP (from any gnu archive), or perhaps MIRACL from http://indigo.ie/~mscott/.
I suspect GMP is about as fast as they come, but there's no C++ API.
MIRACL a bit slower, but does have a C++ API.
--
Anders Thulin [EMAIL PROTECTED] 040-10 50 63
Telia Prosoft AB, Box 85, S-201 20 Malm�, Sweden
------------------------------
** 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
******************************
