Cryptography-Digest Digest #730, Volume #13 Wed, 21 Feb 01 19:13:01 EST
Contents:
Re: Question about RSA excryption... (Roland Kaufmann)
Re: MQV implementation (Mike Rosing)
Re: Key expansion. ("Cristiano")
Re: Key expansion. ("Marcin Kurzawa")
Re: Is there an algorithm to sequentially enumerate all transcendental numbers?
(John Savard)
Re: PGP Public Keys (Andrew McDonald)
Re: CipherText patent still pending (Mok-Kong Shen)
Re: Key expansion. ("Thomas White")
Re: Anonymous web surfing? ("Mario Contestabile")
Re: New unbreakable code from Rabin? (wtshaw)
Re: Super strong crypto (wtshaw)
Re: Super strong crypto (wtshaw)
Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and Weep Boys
(wtshaw)
Re: Anonymous web surfing? (Paul Rubin)
Re: New unbreakable code from Rabin? ([EMAIL PROTECTED])
Re: Key expansion. (John Myre)
Re: Question about RSA excryption... (David Hopwood)
----------------------------------------------------------------------------
Subject: Re: Question about RSA excryption...
From: Roland Kaufmann <[EMAIL PROTECTED]>
Date: Wed, 21 Feb 2001 18:03:40 GMT
>>>>> "Jerry" == Jerry Coffin <[EMAIL PROTECTED]> wrote:
Jerry> [.. lots of correct and useful information elided] -- for
Jerry> example, with a 128-bit block size, you'd need to store
Jerry> 2^128 blocks of information, which is substantially more
Jerry> than the number of iron molecules on earth.
I don't think so. There are 6.022e23 iron atoms in a mole (56g)
of iron, so 2^128 iron atoms are about
2^128 * 56 / 6.022e23 g = 3.16e13 kg
or about 3 million 10000-ton battleships. This is probably more than
the NSA can obtain ;-) but it is only the tiny fraction
3.16e13 / 5.9742e24 = 5.29e-12
of earth's mass [1], and since iron is a common element, there are
certainly more than 2^128 iron *atoms* on (or rather in) earth. Now
you said molecules, and one could quibble about the size of iron
molecules, but I just wished people [2] were a bit more carful with their
numbers, even if they do not really matter.
[1] A number of interesting numbers can be found in John McCarthy's
facts file http://www-formal.stanford.edu/jmc/facts.txt
[2] A recent poster claimed that "the energy of the galaxy is needed
to factor a 256-bit RSA modulus" or something close to it.
--
best regards
Roland Kaufmann
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: MQV implementation
Date: Wed, 21 Feb 2001 12:36:38 -0600
Alexander Schmitt wrote:
>
> It hangs in the following part of the opt_inv routine of the fast inversion.
> At the end of the process all elements of g = 0 and so the last element is
> also g.e[LONGWORD] = 0, so that the task never will go out of the loop. So
> it seems that not the signed or unsigned bit is responsible for the infinite
> loop but the last bit is it.
> Any hints?
>
> do {
> i = shift_by[g.e[LONGWORD] & 0xff];
> n+=i;
> /* Shift b left i (multiply by u^i), lengthening it if needed */
> m = 0;
> for ( j=LONGWORD; j>=c_top; j-- ) {
> bits = b.e[j];
> b.e[j] = (bits<<i) | m;
> m = bits >> (WORDSIZE-i);
> }
> if ( m ) b.e[c_top=j] = m;
>
> /* Shift g right i (divide by u^i) */
> m = 0;
> for ( j=f_top; j<=LONGWORD; j++ ) {
> bits = g.e[j];
> g.e[j] = (bits>>i) | ((ELEMENT)m << (WORDSIZE-i));
> m = bits;
> }
> } while ( i == 8 && (g.e[LONGWORD] & 1) == 0 );
:-) g isn't supposed to do that. The reason is that you start with g == M,
the irreducible polynomial for the field, and work it down to 1. If g == 0,
you are trying to invert zero. Division by zero doesn't work in any representation.
But there may be something else wrong that got you there. For example, the
initialization routines that create the shift_by and two_bit arrays needs to
be run before any inversion. Check that the field sizes you are working with
match the ONB Type as well, for Type 1 you need NUMBTIS+1 but for Type 2 you
need NUMBITS*2 + 1. If the overall storage isn't big enough, you may run out
of bits as well.
If you have more problems, maybe we should take this off line. You can send
me e-mail via [EMAIL PROTECTED] (or just reply to this).
Patience, persistence, truth,
Dr. mike
------------------------------
From: "Cristiano" <[EMAIL PROTECTED]>
Subject: Re: Key expansion.
Date: Wed, 21 Feb 2001 20:56:41 +0100
> [...]
> 128-bits: SHA-1 (chop off the last bits)
> 160-bits: SHA-1
> 192 : Tiger-192, or SHA-256 with the last bits chopped off
> 256 : SHA-256
> 384 : SHA-384
> 512 : SHA-512
Can you point me to some c or c++ code for SHA-256 and SHA-512 (I have found
only assembler code)?
> and I'm sure if you need it we can find something larger than that
Thank you very much.
Cristiano
------------------------------
From: "Marcin Kurzawa" <[EMAIL PROTECTED]>
Subject: Re: Key expansion.
Date: Wed, 21 Feb 2001 20:10:43 GMT
"Cristiano" <[EMAIL PROTECTED]> wrote in message
news:9716it$9gl$[EMAIL PROTECTED]...
[snip]
> Can you point me to some c or c++ code for SHA-256 and SHA-512 (I have
found
> only assembler code)?
[snip]
I have an implementation of SHA-256 in Java on my site
http://www.optymalni.com/~marcin . There is also Rijndael in the fcr.zip
package, I know you mentioned that algorithm in your previous posts.
Marcin Kurzawa
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: sci.math
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental
numbers?
Date: Wed, 21 Feb 2001 20:26:04 GMT
On Mon, 19 Feb 2001 10:10:54 -0500, jtnews <[EMAIL PROTECTED]>
wrote, in part:
>Is there an algorithm to sequentially enumerate
>all possible transcendental numbers?
>I want to be able to generate very long
>passphrases but at the same time be able
>to express them succinctly in the form of mathematical
>expressions.
Although there is no way to sequentially enumerate _all transcendental
numbers_, there is a way (called Godel numbering) to sequentially
enumerate all possible mathematical expressions.
That will _not_ help you, however, to find a short mathematical
expression to represent an arbitrary string of digits.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Andrew McDonald)
Subject: Re: PGP Public Keys
Date: Wed, 21 Feb 2001 20:38:08 GMT
On Wed, 21 Feb 2001 07:48:36 -0600,
John Atkins <[EMAIL PROTECTED]> wrote:
> What kind of MIME encoding is used to encode PGP keys? If I wanted to
> decode all the information about a PGP key, how would I do it? Ex:
> Decoding this:
>
> -----BEGIN PGP PUBLIC KEY BLOCK-----
> Version: PGP Desktop Security 7.0.3 Evaluation
PGP Packets aren't MIME encoded (temporarily ignoring PGP/MIME).
RFC2440 specifies the data formats for OpenPGP.
Andrew
--
Andrew McDonald
[EMAIL PROTECTED]
http://www.mcdonald.org.uk/andrew/
OpenPGP DSA/ElG 1024/2048 3EDE 0FBC 6138 DCA0 FC8E C508 FCBB A9C8 F2DE ED36
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: CipherText patent still pending
Date: Wed, 21 Feb 2001 22:23:16 +0100
William Hugh Murray wrote:
>
> Perhaps it would be useful to distinguish between pupil and student,
> amateur and apprentice. Many of the examples that we see here are by
> the cryptographic equivalent of a hacker. That is to say they ar by
> those trying to learn cryptography by experimentation. They are trying
> to do it without benefit of a master or a mentor. They are trying to do
> it without benefit of studying the literature. They are trying to do it
> without first mastering the necessary prerequisite mathematics. They
> are trying to do it without studying the classical worked examples.
>
> Cryptography is a very difficult discipline to learn in this manner. I
> suppose that it is possible. A few hackers do manage to evolve into
> master programmers but it is rare. When one is trying to learn to
> program by experimentaion, one at least enjoys the benefit of prompt
> feedback. One can begin with a closed set of primitives. One also
> enjoys the benefit of sample code that can be understood with a minimum
> of preparation. The amateur crypographer enjoys few of these benefits.
> It is not a field that is easy to enter at the end.
What you say is true. That's why you don't see any success,
or any substantial success, here.
M. K. Shen
------------------------------
From: "Thomas White" <[EMAIL PROTECTED]>
Subject: Re: Key expansion.
Date: Wed, 21 Feb 2001 21:28:57 -0000
Reply-To: "Thomas White" <[EMAIL PROTECTED]>
"Joseph Ashwood" <[EMAIL PROTECTED]> wrote in message
news:OvLSTC5mAHA.278@cpmsnbbsa07...
> > > > There are problems if I withdraw only 128 bits instead of 160
> > > > (I don't want to use MD5)?
> No problem. If you want fewer bits from a cryptographic hash function just
> chop off the last bits
Is it secure to use a sort of EOR system to reduce a longer hash to a more
manageable one?
I mean, if I take a 128-bit MD5 (of a key, for example, for validation) and
need a 32-bit hash, is it OK to split the 128 bits into four blocks of 32
and the EOR them all together? It seems to make more sense to me to use as
much of the longer hash as possible rather than just chopping bits off.
Thomas
------------------------------
From: "Mario Contestabile" <[EMAIL PROTECTED]>
Subject: Re: Anonymous web surfing?
Date: Wed, 21 Feb 2001 16:40:51 -0500
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
> Safeweb's proxy is similar to Anonymizer.com but they did a really
> nice job. Give it a try: www.safeweb.com.
Provided you trust safeweb, and it's html parsing ability to rewrite
urls...
- --
Mario Contestabile
[EMAIL PROTECTED]
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 7.0.3 for non-commercial use <http://www.pgp.com>
iQA+AwUBOpQ14HuiZigL998JEQJ6wQCY2GMUwXcQI4+XRQyvMqpkAZkP3QCfW0tJ
KqgVl+wwTeskcAsyYHyBSyw=
=JrFn
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: New unbreakable code from Rabin?
Date: Wed, 21 Feb 2001 15:50:12 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
> I also conjecture that scheme could be equivalent to one
> using a PRNG to decide whether to send an information bit
> (preferably encrypted) or to send random dummy bits. By
> increasing the proportion of dummy bits, one could eventually
> exceed the capability of the opponent to store the whole
> stream for later examination. (BTW, I implemented such a
> probabilistic scheme.)
>
> M. K. Shen
This is not new as you and I both know. It is not far from the
mulltiseeded aproach I implemented years ago.
About the use of a publically available stream for encryption, I did some
work with that Idea in the sixties, and it works. I did not originate the
technique, but got it directly from a rather well destributed compilation
of technical data, but, you have to recoginize such stuff when you see it.
It seems to me that much is made of little here, the principles are well
known, and the techiques involved are not earth shakeing. So, is the
situation with much of crypto. Of course in grouping so many algorithms
as questionable for their reliance on obscurity of mathematics, Rabin is
right, but that grouping does not include all algorithms.
--
Better to pardon hundreds of guilty people than execute one
that is innocent.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Super strong crypto
Date: Wed, 21 Feb 2001 15:56:45 -0600
In article <96vds4$2en$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (David
Wagner) wrote:
> Gwyn's proposal was, when a symmetric key K is about to expire, to
> generate a new symmetric key K' and send it encrypted under the old
> symmetric key, E_K(K').
>
...
> Anyway, it is possible to implement Gwyn's proposal in a way that defeats
> these chosen-ciphertext attacks, but extra care must be taken.
If you go with the idea that an encryption system should resist chosen
attacks, the system is weaker than it should be, but that is really saying
that the criteria is too picky for some simple real world uses.
--
Better to pardon hundreds of guilty people than execute one
that is innocent.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Super strong crypto
Date: Wed, 21 Feb 2001 16:01:49 -0600
In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote:
> Bryan Olson wrote:
> > The key changes in real systems are there to limit the damage
> > from exposed keys; ...
>
> No.
Would you grant that the changes at least make analysis harder? The goal
would be to turn them around often enough to make analysis impossible?
--
Better to pardon hundreds of guilty people than execute one
that is innocent.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and Weep
Boys
Date: Wed, 21 Feb 2001 16:09:51 -0600
In article <970d4v$rfr$[EMAIL PROTECTED]>, "*"
<[EMAIL PROTECTED]> wrote:
> Just know some people don't have web access, only newsgroup...
>
> Douglas A. Gwyn wrote in message <[EMAIL PROTECTED]>...
> >"." wrote:
> >> From the article at:
> >> http://www.nytimes.com/2001/02/20/science/20CODE.html?pagewanted=all
> >
> >Why are you posting copyrighted material when we already had the
> >URL for it? Very uncool.
I totally agree. This does bring to mind the toothless battle not just
over the spread of information, but the desire to make it all wear
dogtags. What is uncool is using legal methods to make it harder to
obtain that which is already free for the picking. Consider that anything
in cyberspace goes where you cannot control it.
The mechanism for newsgroup dissemination requires what was done for free
debate.
--
Better to pardon hundreds of guilty people than execute one
that is innocent.
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Anonymous web surfing?
Date: 21 Feb 2001 14:44:52 -0800
"Mario Contestabile" <[EMAIL PROTECTED]> writes:
> > Safeweb's proxy is similar to Anonymizer.com but they did a really
> > nice job. Give it a try: www.safeweb.com.
>
> Provided you trust safeweb, and it's html parsing ability to rewrite
> urls...
It seems to do a good job of rewriting url's, though it's more
ambitious than Anonymizer and therefore there's more places to go
wrong (e.g. it tries to rewrite javascript embedded url's, which I'd
have thought was madness). As for trust, I have out-of-band reasons
to think they're legit, though that hardly proves anything. It's
theoretically possible they're forwarding my browsing to the CIA. But
I doubt if they're forwarding it to the random web sites I surf that I
don't want to reveal my IP address to. Since Anonymizer doesn't even
use SSL, anyone who can sniff my ISP's traffic can see everything I
send through it. So while Safeweb *might* be insecure against
government surveillance, Anonymizer is *known* to be insecure against it.
A total paranoid shouldn't trust ANYTHING of this type. But if you've
got to trust something, ZKS Freedom is probably the most secure of the
bunch--but it needs a download, and it's slow, and you have to pay for
it, etc.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New unbreakable code from Rabin?
Date: 21 Feb 2001 18:10:49 -0500
[EMAIL PROTECTED] wrote:
> All one requires is that the weak encryption used to indicate
> how to extract a key from the public pool, be strong enough
> to resist an interceptor's efforts at decryption for a week
> (long enough until the pool has "auto-erased").
I believe you can past this and use a totally insecure encryption
as the first step in boot-strapping to totally secure.
Take a fixed 1024 bit key, k_0, and encrypt a 1024 bit message by XORing
with this fixed key. This is insecure when used for a natural
language but secure as long as it is used on a totally entropic
(n bits of entropy for n bits of message - including repeated
messages ... that is, any bit pattern is equally likely as
a stream of repeated messages) message stream.
Have some known method of converting a 1024 bit "pointer" to
a key from the current public data pool.
Randomly pick a pointer.
Use the fully insecure encryption of XORing that with the fixed
(but secret) k_0 and send that to your recipient (who, knowing
k_0 can extract the pointer and then extract the key from
the random pool using that pointer).
Only USE the key after the pool has vanished.
(this precludes anyone from looking at the encrypted message, say
using a one time pad, and using the known redundancy of natural
languages to obtain some restrictions on the actual key used and
from the pool of keys, back up to knowledge of the pointer
that was chosen and so get information on k_0 - that is impossible
since the pool is no longer available for inspection)
When you need another key, do it again ... pick a random
pointer, XOR with k_0 again, and send that.
I think this may be completely secure (?) as long as one does not
use the key until the pool has vanished.
The point being that one can use an insecure encyrption with
a transient random pool for "session keys" to generate keys
which can be used securely.
(of course, if you and the recipient do not already have such
a shared secret k_0 key, then you could both generate RSA keys
and use that to share the pointer - but then one does need
to worry about how long it takes to break RSA, since, being
a public key encryption algorithm it *can* be broken with
sufficiently long enough time (factoring the modulus) -
once you have done it once, you have gotten a key you can use
for k_0 and you can chain getting one k_0 from the last 1024
bits of a long key obtained from the pool using k_0 as a pointer
... hmmm ... lots of little things to considere ...)
but a transient (and large so it can't be stored) public pool
of random data (to be used as session keys) seems to have its
uses.
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Key expansion.
Date: Wed, 21 Feb 2001 16:42:12 -0700
Thomas White wrote:
<snip>
> Is it secure to use a sort of EOR system to reduce a longer hash to a more
> manageable one?
It should be no less secure than truncation.
<snip>
> It seems to make more sense to me to use as
> much of the longer hash as possible rather than just chopping bits off.
That is the usual intuition, but a "cryptographic" quality
hash is supposed to be so good that extra mixing of this
type (EOR) is pointless. I think of the analogy of physical
mixing: if you stir things up long enough then scooping off
a little from the top gives you just as representive a sample
as if you accumulated portions from several spots.
JM
------------------------------
Date: Thu, 22 Feb 2001 00:06:50 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Question about RSA excryption...
=====BEGIN PGP SIGNED MESSAGE=====
Benjamin Goldberg wrote:
> Taylor Francis wrote:
> > Admittedly, I'm a beginner, but the RSA method, seems to produce the
> > same ciphertext for the same plaintext. Despite the prime numbers and
> > difficultites of factoring, doesn't this just produce a simple
> > substitution cipher?
> >
> > How is this difficulty overcome?
>
> It's true that using pure RSA to encrypt two identical plaintexts
> produces two identical ciphertexts. However, we generally do not use
> pure RSA encryption for sending messages. We generate a random string
> r, encrypt r using RSA, then encrypt our actual message using some block
> cipher with r as the key.
No, that is insecure, or at least does not provide bitlength(r) bits of
security (see [1]). The message should be processed using a randomised
encoding method designed for the purpose, for example OAEP [2,3].
[1] Dan Boneh, Antoine Joux, Phong Q. Nguyen,
"Why Textbook ElGamal and RSA Encryption are Insecure,"
Extended Abstract in Proceedings of ASIACRYPT '2000,
Volume 1976 of Lecture Notes in Computer Science, Springer-Verlag.
http://www.di.ens.fr/~pnguyen/
[2] RSA Security, Inc.,
PKCS #1: RSA Cryptography Standard, version 2.0.
http://www.rsalabs.com/pkcs/pkcs-1/
[3] M. Bellare, P. Rogaway,
"Optimal asymmetric encryption -- How to encrypt with RSA,"
Revised version, 19 November 1995.
http://www-cse.ucsd.edu/users/mihir/papers/pke.html#oae-paper
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOpM5XDkCAxeYt5gVAQHo7gf9HNUfZvJYxuGzafV3BnuVTUIXj2DPbJmM
IsCmPBftQhxhoTCcCu1Tn9obgVtPZHWVecocnKAhArh4eJh78R8VnXYItQ5F5wvG
uo2j8+OmWGUg2/7eOYvbhdrTmF819thf8Ewo7H68nZ8w/BGViDVwwJHGggOT2Wha
lnDLn082Y7lZ9fi8YQeDjCDdHPkqMO1s4HaMHSrHVQQd5iMdaHOvn/a82hGiQCw/
zvJL4aDIswwT1v1JdegDusq/Ha8E44nmPcT9qitkj7Aa29HTy6Nr5xTVlvHfOw2C
thjzOuhevnXBuAoTjSOkkHZmP8dAozLGiitL+gYBHj1uDPUUplpl/w==
=RzVp
=====END PGP SIGNATURE=====
------------------------------
** 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
******************************
