Cryptography-Digest Digest #58, Volume #14 Mon, 2 Apr 01 02:13:01 EDT
Contents:
AES ("Tom St Denis")
Re: Problematic Patent (Terry Ritter)
Re: efficient rabin signature? (Benjamin Goldberg)
----------------------------------------------------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: AES
Date: Sun, 1 Apr 2001 23:56:37 -0400
When will AES become a final standard?
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Problematic Patent
Date: Mon, 02 Apr 2001 05:35:46 GMT
On 1 Apr 2001 20:34:37 -0000, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (Rich Wales) wrote:
>Sam Simpson wrote:
>
> > Or, to turn your comment on it's head: any use of this
> > scheme previous to 4th Jan 00 would act as prior art?
>
>Well, the application for patent 6,165,072 was filed on 4 January
>2000. However, the patent holders made very similar claims in an
>earlier US patent (6,030,288), filed 2 September 1997 [see claim
>13 in this earlier patent]. So I suppose use of this scheme would
>have to precede that earlier date in order to qualify as prior art.
Note that the phrase "prior art" is a "term of art" in patent law:
"Prior art" does not necessarily refer to an earlier *use* of the
invention, but instead, earlier *publication*. We might think of it
as what the average worker in the field could have known from public
sources. Normally, "a publication" is expected to be available in
public libraries.
Finding a use of an invention buried in some early software probably
would not be considered "prior art" in the patent sense, unless that
software somehow disclosed to the public how to make the invention.
Disclosure to the public of how to make the invention is what this is
all about.
The ideal "prior art" is an earlier patent, or a magazine article, or
a paper given at some scientific meeting and published in the
proceedings, or a book, all of which have nice firm publication dates.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: efficient rabin signature?
Date: Mon, 02 Apr 2001 05:37:29 GMT
Tom St Denis wrote:
>
> This has most likely been proposed before... but here is an idea I was
> just thinking of..
>
> The secret key is <p,q> which are two large primes (congruent to 3 mod
> 4) such that N=pq is a blum integer. To sign a message you perform
> the following.
>
> 1. K = (hash of message) * 65536
> 2. if J(N, K) = 1 then solve for the principal square root of K and
> store it in M and goto step 4
> 3. If J(N, K) = -1 then increment the lower 16 bits of K and goto 2
> 3. Output M
Is J the Jacobi symbol? If so, is J(N, K)==0 possible, and if so, what
happens when then? Nevermind, it only occurs if K is a factor of N.
In psuedo-C code, the above algorithm is:
for( K = H(message)<<16 ; J(N, K) != 1; ++K );
signature = modsqrt(K, p, q)[0];
>
> To verify you simply do
> 1. K = M^2 mod N
> 2. Divide K by 65536
> 3. Compare K against the hash of the message.
verified = ((signature*signature % N) >> 16) == H(message)
>
> Obviously some modifications can be made for example storing the lower
> 16 bits along with M such that they can be compared. Also modifying
> the upper bits of K as (if) required.
AFAIKS, there does not seem to be any harm in modifying the lower bits
of the hash directly. Reserving 16 bits seems silly. Here's my version
of the scheme:
Signing:
for( K = H(message), M = 0 ; J(N, K) != 1; ++K, ++M );
signature = { modsqrt(K, p, q)[0], M };
Verification:
K = signature[0] * signature[0] % N;
M = signature[1];
while( M > 0 ) { // This loop is a test for a subliminal channel in M.
--K, --M;
if( J(N, K) == 1 ) {
verified = false;
return;
}
}
verified == (K-M) == H(message);
Note: modsqrt(K, p, q) returns a vector containing all the sqrts of K
mod pq, with the principle sqrt as the first element. Why not just
write principlesqrt(K, p, q)? 'cause its more letters :) Obviously it
has to get the parameters p and q, not pq, since it can't work without
them.
--
Sometimes the journey *is* its own reward--but not when you're trying to
get to the bathroom in time.
------------------------------
** 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
******************************
