Cryptography-Digest Digest #930, Volume #11 Sat, 3 Jun 00 13:13:01 EDT
Contents:
Evidence Eliminator, is it patented, copyrighted, trademarked ? (jungle)
Re: Contest rule proposal (Mark Wooding)
Re: Notation (was Re: TC3 Update) (Mark Wooding)
Re: TC3 Update (Mark Wooding)
Re: Good ways to test. (Mark Wooding)
Re: http://www.infraworks.com product (Mark Wooding)
Re: Self Shrinking LFSR (Tim Tyler)
Re: Good ways to test. (tomstd)
Re: No-Key Encryption (John Savard)
Re: Good ways to test. ("Trevor L. Jackson, III")
Re: XTR (was: any public-key algorithm) ("Eric Verheul")
Re: XTR independent benchmarks ("Eric Verheul")
Re: Solovay-Strassen primality test ("Axel Lindholm")
Re: Cipher design a fading field? (Jack)
Re: Evidence Eliminator, is it patented, copyrighted, trademarked ? (Lucifer)
Re: Cipher design a fading field? (tomstd)
----------------------------------------------------------------------------
From: jungle <[EMAIL PROTECTED]>
Crossposted-To: alt.privacy,alt.privacy.anon-server,alt.security.pgp
Subject: Evidence Eliminator, is it patented, copyrighted, trademarked ?
Date: Sat, 03 Jun 2000 06:13:12 -0400
Evidence Eliminator, is it patented, copyrighted, trademarked ?
===============================================================
is your company [ you ] using patents, copyrights, trademarks ?
is your software using patents, copyrights, trademarks ?
is your software patented, copyrighted, trademarked ?
when yes, could you please provide details of these "marks" such as :
name, year, mark filing #
thanks for your cooperation ...
alt.privacy, sci.crypt, alt.privacy.anon-server, alt.security.pgp
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Contest rule proposal
Date: 3 Jun 2000 10:35:57 GMT
Terry Ritter <[EMAIL PROTECTED]> wrote:
> The block *transformation*. It is the transformation which is
> streamed. I don't know what it would mean to stream a block.
Hmm. A stream of transformations. That would have type ('a -> 'a)
list, no? A slightly bizarre concept, unless you're deeply into
functional programming. I think it makes more sense to keep the
transformation nailed down where it is and stream data past it. YMMV.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Notation (was Re: TC3 Update)
Date: 3 Jun 2000 10:38:58 GMT
David Hopwood <[EMAIL PROTECTED]> wrote:
> Actually it's normally in stylized italic - Unicode 2118h, FWIW.
> (Oh, for decent Unicode support in mail/newsreaders.) Here is a somewhat
> mangled ASCII-art version:
Nice drawing. I'm sure I've seen a BBB power-set too... Oh, well.
You're right that the caligraphic P is more usual.
Anyway, thanks for picking up the pieces.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: TC3 Update
Date: 3 Jun 2000 11:01:37 GMT
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> Umm, I might be mistaken, but *not* all nonzero elements have
> multiplicative inverses...
Yes they do. That's what separates a field from a ring.
> If an element has a common factor with q that is greater than 1, then
> there is no multiplicative inverse, I think. Consider GF(8), and the
> number 4.
The integer 4 is not an element of GF(2^3) = GF(8). There is a
`natural' mapping N between Z_{p^n} and GF(p^n) represented by
GF(2)[x]/(v(x)), where, if a <- Z_{p^n} = a_0 + a_1 p + a_2 p^2 + ... +
a_i p^i + ... + a_{n-1} p^{n-1}, there is a field element N(a) = a_0 +
a_1 x + a_2 x^2 + ... + a_i x^i + ... + a_{n-1} x^{n-1}; i.e., you
replace powers of p in the integer by powers of x in the polynomial.
So, while 4, not being a member of GF(2), isn't a member of GF(8), we
can map the integer into the field, as the element x^2. Now the inverse
of x^2 in GF(2)[x]/(v(x)) depends on the polynomial v(x) but, since v(x)
is irreducible, the greatest common divisor of x^2 and v(x) may be found
to be 1 using a straightforward modification of the standard Euclidean
algorithm, and the inverse may be found using the extended Euclidean
algorithm.
Let's take v(x) = x^4 + x + 1. (Take it on trust that this is
irreducible.) For compactness, I'll use the inverse `natural' mapping
and binary notation to show my arithmetic: remember that everything is
really coefficients of polynomials. So N^{-1}(v(x)) = 10011_2, and
N^{-1}(x^2) = 100_2. Watch carefully.
10011 = 100 * 100 + 11
100 = 11 * 11 + 1
Well, that's our GCD. Now for the reversal process.
11 = 10011 - 100 * 100
100 - 11 * (10011 - 100 * 100) =
100 - 11 * 10011 + 11 * 100 * 100 =
(11 * 100 + 1) * 100 - 11 * 10011 =
1101 * 100 - 11 * 10011 = 1
So the inverse of x^2 in this particular representation of GF(2^3) is
x^3 + x^2 + 1. Let's check that
1101
100
----
110100
That's the product. Now we do modular reduction
110100
100110
======
10010
10011
-----
1
Bingo! (Phew! I need a program to do this for me.)
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Good ways to test.
Date: 3 Jun 2000 11:06:09 GMT
Dennis Ritchie <[EMAIL PROTECTED]> wrote:
> Mark Wooding wrote:
>
> > The most effective resource is a Good Cryptanalyst. Several of these
> > can be contacted using the Net. They grow on trees.
>
> Actually I think they are more like truffles than fruits.
You find them using a pig? ;-)
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: http://www.infraworks.com product
Date: 3 Jun 2000 11:27:51 GMT
Thomas Kellar <[EMAIL PROTECTED]> wrote:
> I have been receiving advertisements from a company called the
> Infraworks Corporation. They apparently have made a new product they
> cann InTether that they claim can control access to files of any sort.
It's codswallop[1]. Utter codswallop.
If they try to sell this in the UK, they will be liable in law for
misrepresentation of goods.
[1] Lovely word. Don't get much of an opportunity to use it.
-- [mdw]
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Self Shrinking LFSR
Reply-To: [EMAIL PROTECTED]
Date: Sat, 3 Jun 2000 11:06:43 GMT
lordcow77 <[EMAIL PROTECTED]> wrote:
: Mike Rosing <[EMAIL PROTECTED]> wrote:
:> a few months ago someone posted the URL for a paper that showed some
:> efficient methods for checking if polynomials are primitive.
: Could you provide a reference?
I don't know if this is what is being referred to - but I believe that the
ps/pdf document describing the Mersenne Twister RNG
(which can be obtained from http://www.math.keio.ac.jp/~matumoto/emt.html)
has some interesting material relating to testing large polynomials to
see if they are primitive - in the case where for a polynomial of
degree n, 2^n-1 is prime - i.e. Mersenne primes.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Be good, do good.
------------------------------
Subject: Re: Good ways to test.
From: tomstd <[EMAIL PROTECTED]>
Date: Sat, 03 Jun 2000 04:48:09 -0700
In article <[EMAIL PROTECTED]>, Mok-Kong Shen <mok-
[EMAIL PROTECTED]> wrote:
>
>
>tomstd wrote:
>
>>
>>
>> My point was that while we can't state the strength of a
cipher,
>> we can point out what it does right. This can lead to
>> suggestive levels of strength of the function.
>
>Who is the 'authority' that is going to 'point out what it does
right'?
>Aren't 'suggestive' matters subjective and fundamentally
arguable?
>
>> From a medical point of view it's similar. If 5% of the
people
>> get sick with brand A, and only 0.01% with brand B, well we
>> would pick brand B. But that doesn't mean in the long run
brand
>> B is any better. Just over that short period of analysis.
>
>There is nothing parallel to the above in crypto. You may
continue
>to use a cipher without knowing that it has been cracked by some
>mighty opponents. What one can often do is to go conservative,
>e.g. using superencipherment, in the hope that the risk is
somewhat
>reduced. But there can be no absolute assurance.
Again I disagree. You could be using Tylenol for a century not
knowing that it has side effects.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: No-Key Encryption
Date: Sat, 03 Jun 2000 11:45:57 GMT
On Sat, 03 Jun 2000 11:02:35 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>I am not yet convinced of that. Since '*' is assumed to be associative,
>we certainly have M*(A*B)=M*(B*A). If this is true for any M, I
>think that by applying the inverse one should have A*B=B*A, which
>is the commutativity. What is the flaw here?
It's true that there is a right-inverse, so that from M*A, we can
obtain M by doing (M*A)/A. But I don't recall seeing it stated that a
left-inverse exists.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/
------------------------------
Date: Sat, 03 Jun 2000 10:18:57 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Good ways to test.
tomstd wrote:
> What about all the "new" drugs tested in the early 50's/60's
> that caused 'unknown' side effects? What about DDT (the
> pesticide... I may have got the name wrong), what about...
DDT was accused of poisoning the environment and causing the thinning of bird's
eggshells causing a decline in bird population. But it was a not a scientific
conclusion but a hysterical one.
Perhaps the most maligned was dioxin of Bhopal fame. Once considered "the most
carcinogentic pollutant" it's now not even considered dangerous. More hysteria
eventually dispelled by scientific research.
Point is that it is possible to scientifically measure the impact of chemicals
upon living organisms. If you look for changes in the organism and find none it
is reasonable to conclude that there are none.
It is not possible to measure the impact of ciphers upon communication
security. So if you look for communication leaks and find none it is not
reasonable to conclude that there are none.
The limerick that was supposed to have driven Pascal mad is very simple:
Those we found we threw away,
Those we didn't find we kept.
For what were they searching?
The answer is not secure ciphers, but it might as well have been. When you
understand the nature of Pascal's search you'll understand why figures of merit
for ciphers are not as useful as in other disciplines.
------------------------------
From: "Eric Verheul" <[EMAIL PROTECTED]>
Subject: Re: XTR (was: any public-key algorithm)
Date: Sat, 3 Jun 2000 15:56:35 +0200
> >> Why don't you just post some timings of your RSA software on standard
> >> processors? Then people can straightforwardly compare them with the
> >> other good implementations out there (OpenSSL, MIRACL, PGP bnlib, etc).
> >Better still, why don't you make your own timings with the testsoftware
> >(executables)
> >that we provide on www.ecstr.com ?
>
> Now you're just being silly. We're supposed to run some arbitrary
> executable we found on your web site, on _your_ say-so? I don't
> think so. Why don't we see source there? You've described the algorithm
> in detail in your paper, so it's not a secret.
We've just put the source code on www.ecstr.com !
We're not providing any support for it (one of the reason for not posting).
Eric
------------------------------
From: "Eric Verheul" <[EMAIL PROTECTED]>
Subject: Re: XTR independent benchmarks
Date: Sat, 3 Jun 2000 16:14:21 +0200
Wei Dai <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I decided to do a quick XTR implementation to see how well the claims of
low
> computational overhead hold up. Here are the results (time in
milliseconds,
> numbers in parentheses are the claims in the XTR paper):
[...]
> Other observations:
> - XTR suffers if precomputation is possible or prevention of subgroup
attacks
> is needed, otherwise it compares favorably against ECC over GF(p).
First of all, thanks for the effort! You certainly prove that doing an XTR
implementation can be done
quite quickly (even for a relative outsider); and your quick implemenation
is even faster than ECC
over GF(p) already! Doing a fast ECC implementation (including parameter
generation) is lot more work!
Could you please tell me why XTR suffers if precomputation is possible?
Moreover,
testing that sent group elements are indeed elements of the group (to
prevent subgroup
attack; guess this is what you mean) is also required with ECC; just have a
look at the
crypto2000 papers (Differential fault attacks on elliptic curve
cryptosystems).
> - XTR is actually slower than LUCDIF in this test, but again this may be
due to
> the optimization choices in Crypto++.
You've got me puzzeled here (yeah, I did a quick estimate of doing LUC).
First of all, the hard part of parameter generation in LUCDIF consists of
generation a
primenumber p of 512 bits and (and if you're smart a prime number q of about
170 bits, such that
q divides p+1, if you want to be both safe and be able to use subgroups).
The hard part of
parameter generation in XTR consists of generation of two prime numbers of
about 170 bits.
No way, that LUCDIF parameter is faster! It should (theoretically) be about
3^4=81 times slower!
Secondly, if I look at the orginal Asiacrypt94 paper of Smith and Skinner,
then the elements
in the group of order p+1 in GF(p^2) are represented as U_n and V_n in GF(p)
where
p is of size 512 bits, and:
V_2n = ((V_n)^2 + D (U_n)^2)/2 en
U_2n = Un*V*n
V_n+1 = (Vn*U_1 + D*U_n * U_1)/2
U_n+1 = (Un*V_1 + V_n * U1)/2
So if one uses a repeated squaring technique then:
- a "squaring" will cost 2 squarings in GF(p) and 1 mult in GF(p);
- a "mult" will cost 5 mults in GF(p).
Assuming you use some trick to get rid of the division by 2.
If you're smart you use a subgroup of order q (divising p+1), of 170 bits
instead
of the whole group of size p+1, i.e. of 512 bits size. Note XTR uses such a
subgroup
as well.
Typically, you will need log(q) "squarings" en log(q)/2 "mults" for a
exponenation.
That is: 2log(q) squarings en (1 + 2.5)*log(q) mults in GF(p). Now, as the
size of
the basis field in LUCDIF is 3 times larger than in XTR, it reasonable, to
assume that
mults and squarings in the LUCDIF basic field is 3^2 = 9 times slower than
in XTR's basic
field. If we, moreover, assume that a squaring will take 80% time compared
with a multiplication,
then comparitively, one LUC exponentiation will take
9( 2*0.8 + 3.5) *log(q) = 46 * log(q) multiplications in a basis field size
of 170 bits, i.e. an XTR basic field.
XTR, however, only uses a 8 *log(q) multiplications (see the XTR paper).
That is, about 6 times less: XTRDIF should be about
6 times faster than LUCDIF. If you don't use a subgroup, XTRDIF should be
even about 18 times
faster than LUCDIF. Your optimalizations are quite good!
This probably also explains for the difference between your RSA comparisons
and ours.
> - I stand by my earlier remark that XTR's advantages (where they exist)
are
> rather marginal.
>From my point of view, you're only proving them: XTR is faster than ECC of a
GF(p)
and simple to implement.... You've proven them both.
Could you please send me your XTR implementation? We've just put the source
code
on www.ecstr.com .
Best Regards, Eric
------------------------------
From: "Axel Lindholm" <[EMAIL PROTECTED]>
Subject: Re: Solovay-Strassen primality test
Date: Sat, 3 Jun 2000 17:03:23 +0200
I've given it some thought, and I think I've reached a fairly good
conclusion. I might be totally wrong about this and it can hardly pass the
criterions for a mathematical proof, but I felt like sharing my result
anyhow.
A number, 'n', is a pseudoprime with base 'a' if, and only if: a^n mod n =
a, 'n' is a composite number and 'a' > 0. Say that n = x * y, then we can
refrase the above definition to: 'n' is a pseudoprime with base 'a' if, and
only if: a^x mod x = a, a^y mod y = a, 'n' is a composite number and 'a' >
0. Now, x and y can't be more than n/2 because the smallest factor avalible
is 2!
Axel Lindholm
"Marek Futrega" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> The basis of the Solovay-Strassen algorithm is the fact that for any
> given composite number "n", there are at most n/2 values of "a" less than
> "n" for which "n" is an Euler pseudo-prime with base "a".
>
> I'm looking for a proof of this fact. Any ideas where to find it?
>
> thanks,
> M.
>
> ps. If possible, please CC your answer to [EMAIL PROTECTED]
>
>
> ___
> [EMAIL PROTECTED]
> http://rainbow.mimuw.edu.pl/~maf
>
------------------------------
From: [EMAIL PROTECTED] (Jack)
Subject: Re: Cipher design a fading field?
Date: 3 Jun 2000 15:31:56 GMT
[EMAIL PROTECTED] wrote in <8h9c1b$cuv$[EMAIL PROTECTED]>:
>Sci.crypt,
>
>Given the results of the cipher contest, it appears that designing a
>strong block cipher is quite easy. Some 7 or 8 ciphers remain
>unattacked on the contest site. Even assuming that all of the ciphers
>have some weakness, it seems that finding a -practical- weakness is very
>difficult.
>
>That being said, is cipher design an obsolete enterprise? If a group of
>amateurs can design a strong cipher then certainly governments can.
>Since many government ciphers are available, what is the point of
>creating new ones?
The main problem is that the government wants its ciphers to
only have enough security so that it can encrypt messages that
the enemy ( us the people ) can not read. But yet when the enemy
uses the ciphers it can freely read what was sent. The government
is very parinoid about information. Just look at the bloated
size of the NSA that seems to grow forever while the budget for
real defensive items is shrinking. You can be assurred that phony
crypto gods will say we need more speed in encryption rates. I
say let the hardware speed improve but with just faster methods
being proposed I feel it makes us the people more vulnerable to
a evil big brother. That is way scott19u was real slow on my old
486 but seems fast on my k6-III
>
>Speed is one good reason. It seems that AES will answer this
>requirement. Some niches also might need a custom algorithm but
>many of these could be built on a base cipher.
>
>Why else is a new cipher required? Will AES be the -final- cipher?
>
>I study crypto as a fascinating hobby and will continue to do so. My
>question is mostly aimed at commericial/military/government
>requirements.
>
>--Matthew
>
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
------------------------------
Date: 3 Jun 2000 16:13:05 -0000
From: [EMAIL PROTECTED] (Lucifer)
Subject: Re: Evidence Eliminator, is it patented, copyrighted, trademarked ?
Crossposted-To: alt.privacy,alt.privacy.anon-server,alt.security.pgp
On Sat, 03 Jun 2000 06:13:12 -0400 jungle <[EMAIL PROTECTED]> wrote:
>Evidence Eliminator, is it patented, copyrighted, trademarked ?
It's copyrighted when it's written.
No filing is required.
------------------------------
Subject: Re: Cipher design a fading field?
From: tomstd <[EMAIL PROTECTED]>
Date: Sat, 03 Jun 2000 09:51:29 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Jack) wrote:
>[EMAIL PROTECTED] wrote in
<8h9c1b$cuv$[EMAIL PROTECTED]>:
>
>>Sci.crypt,
>>
>>Given the results of the cipher contest, it appears that
designing a
>>strong block cipher is quite easy. Some 7 or 8 ciphers remain
>>unattacked on the contest site. Even assuming that all of the
ciphers
>>have some weakness, it seems that finding a -practical-
weakness is very
>>difficult.
>>
>>That being said, is cipher design an obsolete enterprise? If
a group of
>>amateurs can design a strong cipher then certainly governments
can.
>>Since many government ciphers are available, what is the point
of
>>creating new ones?
>
> The main problem is that the government wants its ciphers to
>only have enough security so that it can encrypt messages that
>the enemy ( us the people ) can not read. But yet when the enemy
>uses the ciphers it can freely read what was sent. The
government
>is very parinoid about information. Just look at the bloated
>size of the NSA that seems to grow forever while the budget for
>real defensive items is shrinking. You can be assurred that
phony
>crypto gods will say we need more speed in encryption rates. I
>say let the hardware speed improve but with just faster methods
>being proposed I feel it makes us the people more vulnerable to
>a evil big brother. That is way scott19u was real slow on my old
>486 but seems fast on my k6-III
>
Hi dave,
To quite the contrary the AES ciphers are faster and more secure
then DES. So your idea of fast != secure is invalid.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
** 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
******************************
