Cryptography-Digest Digest #165, Volume #12 Wed, 5 Jul 00 15:13:00 EDT
Contents:
Re: Diffie Hellman Primes : Speed Tradeoff Q (Mark Wooding)
Re: Public-domain Blowfish (Terry Ritter)
Re: AONT (David Hopwood)
Re: Help programming (Darren New)
Re: multiplication and inversion in finite fields (Mike Rosing)
Re: AONT (Mok-Kong Shen)
Re: Hash and Entropy ("Joseph Ashwood")
Re: Help programming ("Joseph Ashwood")
Prime Numbers? ("Big Boy Barry")
Conway (Quisquater)
elliptic curves, twofish and re-encryptions ("Matthew Bennett")
Re: Diffie Hellman Primes : Speed Tradeoff Q (David P Jablon)
Re: Public-domain Blowfish ("Paul Pires")
Re: Prime Numbers? ("Joseph Ashwood")
Re: elliptic curves, twofish and re-encryptions ("Joseph Ashwood")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Diffie Hellman Primes : Speed Tradeoff Q
Date: 5 Jul 2000 16:53:08 GMT
Anton Stiglic <[EMAIL PROTECTED]> wrote:
> Yes this is was first described by van Oorschot and Wiener, in a
> Eurocrypt 96 paper. It generalizes to using p = Rq + 1 (an attacker
> will have to test R values). It's a good indication that one should
> work in the subgroup of order q.
It extends to the case where R is a smooth composite too, I think.
> Lim-Lee primes, primes of the form p = 2*q_1*q_2*...*q_n + 1, where
> the q_i's are large work fine. You can simply work in one of the
> subgroups of large prime order.
That only partially answers my question. Do we have a problem if we do
arithmetic mod p = q R + 1, where q is a large-ish prime, p is large,
and R is a random composite (therefore possibly having small factors,
but also likely to have fairly large ones), and work in the subgroup of
order q?
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Public-domain Blowfish
Date: Wed, 05 Jul 2000 17:13:28 GMT
On Wed, 5 Jul 2000 09:19:14 -0700, in
<8gJ85.75$[EMAIL PROTECTED]>, in sci.crypt "Paul
Pires" <[EMAIL PROTECTED]> wrote:
>[...]
>2, The inventors wishes are binding.
That depends upon whether we are talking about the "real" inventor, or
just someone who thinks he *should* be the inventor. Simply building
a thing without cribbing from someone else does not make one the real
inventor. Others already may own those rights, through issued or
pending patents. Unless the one expressing "wishes" actually has an
issued patent, and has considered other patents which may apply, any
"wishes" should be taken with a grain of salt.
>If he had full rights to it and if he
>published a clear declaration that the material was declared public domain
>and if the material was clearly disclosed I wouldn't worry about it sticking
>and I don't think the one year thing applies in this case.
But one does not have full rights until the claims of others have been
considered. Even having an issued patent does not mean that the
patent holder has production rights to the described material.
>Any lawyers
>listening it?
I am not any kind of lawyer. But I do hold issued patents on
fundamental cryptographic technology.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
Date: Wed, 05 Jul 2000 03:39:02 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: AONT
=====BEGIN PGP SIGNED MESSAGE=====
Benjamin Goldberg wrote:
>
> What do you people think of the following all-or-nothing-transform
> [good, bad, ugly?]
Ugly, because it takes time proportional to the square of the number
of blocks in the message, and bad, because of the attack given below.
> Start with a hash function H, which outputs N bits.
> Partition the file into M N-bit blocks [it's ok if the last block is
> short, but not-ok if the file is less-than one block]
>
> To transform:
> for i = 1 to M
> // hash of all the data before and after block i
> Z = H( data[1..(i-1)], data[(i+1)..M] )
> data[i] = data[i] XOR Z
> end for
Suppose you have all of the plaintext blocks but one, all of the
corresponding ciphertext blocks, and *some* of the bits of the
remaining ciphertext block. In that case, you can find some of the
unknown plaintext bits; for a secure AONT, it shouldn't be possible
to do this.
For some applications of AONTs this wouldn't matter, but combined with
the poor efficiency, I think it's enough to knock this scheme on the
head.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOWKfizkCAxeYt5gVAQF6qwf9GghpUWjwOSVdOA6PGCSvfY32omuRh1nl
Xg1b/qvC3DlqoXFaAQL1LwzKvbzejuxJzjiCR/HGDm36ihnz/65/wobDEuDb6YTH
68vRjyo2UC63qSeq9np2ZgD86YX7D11wi6yLJskvN84mROeOjuyozb5Z113E+mjP
D7MnyLoWa5rbmacGINDJ0N47cJwkUo0te8CymePoAKjP38Ubcv8/nlk552d16Zq6
0Ic1a+SNGPW69hLCXh91nAAwxrga0z7FVn4nwyOALgPMXNTW0CuNG2a4Pvuhi53h
TDHv5JWd7M9xYDKvygC+7+rnXo/5bI4fUJEFjJr5Z+ZmgyOprnn4bA==
=MZdR
=====END PGP SIGNATURE=====
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Help programming
Date: Wed, 05 Jul 2000 17:26:54 GMT
> I have an idea for an encryption that takes one file to encrypt
> another. So the key is the would be 3 pic files and each byte of the
> pics would change the file to be encrypted.
Shades of Johnny Mnemonic?
--
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"We have large financial earlobes."
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Crossposted-To: sci.math,sci.math.num-analysis
Subject: Re: multiplication and inversion in finite fields
Date: Wed, 05 Jul 2000 12:24:15 -0500
Mark Wooding wrote:
> For large fields, Conway's representation may be a win over polynomial
> representations because the tables are unreasonably large. I'd like to
> know more of the theory, though. I've not found any information on the
> net despite throwing a few choice keywords at Google. For example, is
> there an easy way to identify a generator of the multiplicative group of
> a Conway-represented finite field?
The only thing I found was this web page, which looks like an excellent
place to start: http://users.hol.gr/~xpolakis/jhc/jhc_bib.html
Under 1983 there's a reference to Conway multiplication, so maybe
it contains more references.
> Hmm. Has anyone patented doing cryptography in elliptic curves in
> finite fields using Conway's representation?
No, and if anyone did it would kill all interest!
Patience, persistence, truth,
Dr. mike
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: AONT
Date: Wed, 05 Jul 2000 19:42:30 +0200
Benjamin Goldberg wrote:
> Mok-Kong Shen wrote:
> >
> > Benjamin Goldberg wrote:
> >
> > > Start with a hash function H, which outputs N bits.
> > > Partition the file into M N-bit blocks [it's ok if the last block is
> > > short, but not-ok if the file is less-than one block]
> > >
> > > To transform:
> > > for i = 1 to M
> > > // hash of all the data before and after block i
> > > Z = H( data[1..(i-1)], data[(i+1)..M] )
> > > data[i] = data[i] XOR Z
> > > end for
> > > To detransform:
> > > for i = M to 1
> > > // hash of all the data before and after block i
> > > Z = H( data[1..(i-1)], data[(i+1)..M] )
> > > data[i] = data[i] XOR Z
> > > end for
> >
> > I don't yet see why the second process is the inverse of the first.
> > The elements of the array data are dynamically successivly overwritten
> > by new values in the first process, aren't they? Further, you don't
> > specify H. Can it be any hash function? Can you illustrate with an
> > explicit example with, say, 3 or 4 blocks?
>
> H can be any secure hash function: I haven't chosen to specify it.
> You can use SHA1 or MD5 or pretty much anything you want.
>
> As an example,
> data-o[1..4] is the original data
> data-t[1..4] is the transformed data
>
> Transform:
> data-t[1] = data-o[1] XOR H( data-o[2..4] )
> data-t[2] = data-o[2] XOR H( data-t[1], data-o[3..4] )
> data-t[3] = data-o[3] XOR H( data-t[1..2], data-o[4] )
> data-t[4] = data-o[4] XOR H( data-t[1..3] )
> Inverse Transform:
> data-o[4] = data-t[4] XOR H( data-t[1..3] )
> data-o[3] = data-t[3] XOR H( data-t[1..2], data-o[4] )
> data-o[2] = data-t[2] XOR H( data-t[1], data-o[3..4] )
> data-o[1] = data-t[1] XOR H( data-o[2..4] )
>
> I've changed the labeling slightly, but the algorithm is the same. I
> hope that describing it like this makes it clearer.
>
> As a memory optimization, note that in the transform, at no point after
> data-t[i] is created from data-o[i], do we ever use data-o[i];
> Therefor, we can store data-t[i] in the same block of memory that
> data-o[i] used to be in {so we don't *really* need two arrays, except
> for descriptive purposes).
>
> The inverse transform can be similarly optimized.
O.k. I understand. You are processing at each step using information
of the WHOLE file. I don't see so far weakness in your scheme, except
that it may be computationally quite expansive if the file is large. I am
interested to see what the experts have to say on your scheme.
M. K. Shen
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Hash and Entropy
Date: Wed, 5 Jul 2000 10:35:23 -0700
I forgot to address something in the secure hash definition that is
important. Given a number generator of polynomial complexity, it should be
(close to) impossible to bias the output either towards or away from a
subset of the output buckets (a superset of the previous statements).
Joe
"Joseph Ashwood" <[EMAIL PROTECTED]> wrote in message
news:#y4rnbg5$GA.386@cpmsnbbsa08...
> Let's see if I can get this right, or at least get my own
> errors pointed out.
> A hash is a function that takes an input of an arbitrary
> length, and creates an output of a fixed length. A
> cryptographically secure hash does so in a fashion that
> makes it difficult to find 2 values that generate the same
> output value, difficult to find a value that generates a
> specific value, and generates values that are distributed
> approximately evenly across all possible output values in
> the realm, as a result of this the output passes all
> statistical tests.
>
> Entropy is a measure of non-determinism inherent in a string
> generated by a method. It has so many different necessary
> interprettations that it becomes difficult to consider, in
> spite of the fact that all the (valid) interpretations are
> in fact equivalent. It has such a great number of
> intricasies that it is quite difficult to define briefly. It
> can be defined for some purposes as the predictability of a
> sub-sequence given all other output values of the generator.
> It is also, almost by definition difficult to locate
> dependably, even a coinflip is not purely entropic since the
> coin could, under very rare circumstances, land on the edge,
> also if you check a US penny, it tends to land on one side
> more than the other (tails more than heads IIRC).
> Joe
>
>
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Help programming
Date: Wed, 5 Jul 2000 10:39:52 -0700
> > Why 64bits? That a lot of pictures. The encryption would use all of
> the bytes of three pictures. And would need the same three pictures to
> decrypt. A one bit change in one of the pictures and you get mush for
> an output.
Actually cryptographically speaking 2^64 isn't that big, it actually small
enough that a public effort has been mounted against one (distributed.net
RC5 challenge), I was simply stating that 2^64 is the upper limit of the key
space, more likely the key space is under 2^40.
I wasn't even dealing with the data inside the pictures, from the vantage I
was taking they merely constitute a key schedule, I was addressing the real
size of the key (the choice between which pictures to use). The length of
the key is actually the space from which you choose your keys, Serpent (an
AES finalist) could be easily broken if you knew the key to be one of 10,
and Serpent is very good cryptography. It's misleading to consider the size
of the picture files to be the key for cryptographic purposes simply because
your choices are much more limited (similar to the US Governments view that
you can use whatever cryptographic algorithms you want for export, as long
as there's only x-bits of randomness).
Joe
------------------------------
From: "Big Boy Barry" <[EMAIL PROTECTED]>
Subject: Prime Numbers?
Date: Wed, 05 Jul 2000 17:49:09 GMT
Hello,
As I know, prime numbers are very important to encryption. Is there any
equation or formula that generates prime numbers? Is it a 'Big Thing' if
somebody discovered this equation. And why is it important to generate prime
numbers through an equation not by a prime number generator program... I
appreciate your help. Thanks!
------------------------------
From: Quisquater <[EMAIL PROTECTED]>
Subject: Conway
Date: Wed, 05 Jul 2000 19:57:49 +0200
Guy, Richard K.: Conway's Prime Producing Mmachine.
Math. Mag. 56(1983) 26-33
========
Université de Louvain
UCL Crypto Group
see http://www.dice.ucl.ac.be/crypto
tél. 32.10.47.25.41 (connected to my voicebox and cellular phone)
fax: 32.2.358.55.83 (only for me)
SMS: send an email (only the subject will be transmitted) to
[EMAIL PROTECTED]
------------------------------
From: "Matthew Bennett" <[EMAIL PROTECTED]>
Subject: elliptic curves, twofish and re-encryptions
Date: Wed, 5 Jul 2000 18:55:10 +0100
Hi all
A couple of unrelated questions on encryption to those experts lurking out
there :) For the background, I'm designing an encryption application that
currently offers Blowfish or Twofish (both CBC) methods.
1) Elliptic curves. I understand these (may) offer increased security
against attacks for a given key length. I've heard elliptic curves can be
applied to many block ciphers out there already, and was wondering if it was
possible to implement this in Blowfish and/or Twofish methods? If so, any
clues on how I might go about finding some examples of its use for these
particular algorithms - or how I could add it myself (I'm working with C
source code).
2) Re-encryption. It sounds a bit strange, but why is it not standard to
encrypt a file multiple times? Obviously there are speed considerations,
but would this not make it almost "impossible" (if there ever was such a
thing ;) to obtain the original plaintext from multiple-encrypted
ciphertext? Surely the attacker would be unable to determine if the data
had been successfully decrypted back a stage, since there would be nothing
obvious (like "Dear Sir" it etc.) to show it? Any validation hashes would
obviously be made only in reference to the plaintext, so I presume would not
be of any use to said attacker in "peeling back" the stages.
Any and all comments welcome :)
Matt
------------------------------
From: [EMAIL PROTECTED] (David P Jablon)
Subject: Re: Diffie Hellman Primes : Speed Tradeoff Q
Date: Wed, 5 Jul 2000 18:07:42 GMT
In article <[EMAIL PROTECTED]>,
Mark Wooding <[EMAIL PROTECTED]> wrote:
>> ... primes of the form p = 2*q_1*q_2*...*q_n + 1, where
>> the q_i's are large work fine. You can simply work in one of the
>> subgroups of large prime order.
>
>That only partially answers my question. Do we have a problem if we do
>arithmetic mod p = q R + 1, where q is a large-ish prime, p is large,
>and R is a random composite (therefore possibly having small factors,
>but also likely to have fairly large ones), and work in the subgroup of
>order q?
I think the answer is "No."
The presence of small adjacent subgroups shouldn't affect
the security of working in a big prime order subgroup.
This presumes of course that both parties use the correct group,
which can be easier to verify (in some applications) using the
factors of R.
======================================================
David P. Jablon
[EMAIL PROTECTED]
www.IntegritySciences.com
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Public-domain Blowfish
Date: Wed, 5 Jul 2000 11:24:40 -0700
Terry Ritter <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> On Wed, 5 Jul 2000 09:19:14 -0700, in
> <8gJ85.75$[EMAIL PROTECTED]>, in sci.crypt "Paul
> Pires" <[EMAIL PROTECTED]> wrote:
>
> >[...]
> >2, The inventors wishes are binding.
>
> That depends upon whether we are talking about the "real" inventor, or
> just someone who thinks he *should* be the inventor. Simply building
> a thing without cribbing from someone else does not make one the real
> inventor. Others already may own those rights, through issued or
> pending patents. Unless the one expressing "wishes" actually has an
> issued patent, and has considered other patents which may apply, any
> "wishes" should be taken with a grain of salt.
You betcha. Claims of any kind should always taken with a whole bag of salt,
not just a grain. This was what I was getting at about the patent office not
having a good grip on such grants.
> >If he had full rights to it and if he
> >published a clear declaration that the material was declared public
domain
> >and if the material was clearly disclosed I wouldn't worry about it
sticking
> >and I don't think the one year thing applies in this case.
>
> But one does not have full rights until the claims of others have been
> considered. Even having an issued patent does not mean that the
> patent holder has production rights to the described material.
A release as public domain can only be seen as the authors opinion and could
therefore only apply to the author. The author cannot bind anyone else who
may feel (rightly or wrongly) that they have an interest as an inventor.
Bruce seems like a dillegent fellow and I take his word that his stuff is
public domain. I can't think of anyone else that applies to and I would
certainly verify my own exposure before commercializing anything, public
domain or not.
Be alert, the world needs more lerts.
Paul
>
>
> >Any lawyers
> >listening it?
>
> I am not any kind of lawyer. But I do hold issued patents on
> fundamental cryptographic technology.
>
> ---
> Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
> Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
>
>
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Prime Numbers?
Date: Wed, 5 Jul 2000 11:19:47 -0700
Worse, I believe it's been proven that no algebraic function can generate
exclusively prime numbers. If such a function were to exist, the main
benefit would be that instead of having to algorithmically, and (generally)
fallibly, determine a number to be prime over quite a bit of effort, instead
we could simply compute an algebraic function and a large prime would
magically appear. Also the race to see who could find the largest prime
would become an abusive search with people finding the nth prime with some
absurdly large number for n.
Joe
"Big Boy Barry" <[EMAIL PROTECTED]> wrote in message
news:pyK85.40723$[EMAIL PROTECTED]...
> Hello,
>
> As I know, prime numbers are very important to encryption. Is there any
> equation or formula that generates prime numbers? Is it a 'Big Thing' if
> somebody discovered this equation. And why is it important to generate
prime
> numbers through an equation not by a prime number generator program... I
> appreciate your help. Thanks!
>
>
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: elliptic curves, twofish and re-encryptions
Date: Wed, 5 Jul 2000 11:26:17 -0700
Let's see if I can shed some light on the subjects.
> 1) Elliptic curves. I understand these (may) offer increased security
> against attacks for a given key length. I've heard elliptic curves can be
> applied to many block ciphers out there already, and was wondering if it
was
> possible to implement this in Blowfish and/or Twofish methods? If so, any
> clues on how I might go about finding some examples of its use for these
> particular algorithms - or how I could add it myself (I'm working with C
> source code).
Actually elliptic curve cryptography is useful for key negotiation, in a
public key fashion. The basic method is (taking place over a public
network):
Alice: Which curve are we using today?
Bob: C
Alice: Okay, in curve C my public key is Apk
Bob: Mine is Bpk
Alice & Bob compute values based on their private keys and the public keys
Alice and Bob both now share a secret that no one else can feasibly compute
>
> 2) Re-encryption. It sounds a bit strange, but why is it not standard to
> encrypt a file multiple times? Obviously there are speed considerations,
> but would this not make it almost "impossible" (if there ever was such a
> thing ;) to obtain the original plaintext from multiple-encrypted
> ciphertext? Surely the attacker would be unable to determine if the data
> had been successfully decrypted back a stage, since there would be nothing
> obvious (like "Dear Sir" it etc.) to show it? Any validation hashes would
> obviously be made only in reference to the plaintext, so I presume would
not
> be of any use to said attacker in "peeling back" the stages.
There's actually a problem with doing that, under rare circumstances, but
circumstances that are generally not proven. It can actually be proven that
if you apply an algorithm numerous times at some point each additional
encryption will only weaken the stack. Generally you don't have to worry
about it, so the real reason is that most people don't feel like waiting
that long when there are stronger keyed methods available.
Joe
------------------------------
** 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
******************************
