[4502] in cryptography@c2.net mail archive
Re: RSA patent on ECC
daemon@ATHENA.MIT.EDU (Vin McLellan)
Sun Apr 11 22:01:27 1999
To: "P. J. Ponder" <ponder@freenet.tlh.fl.us>, cryptography@c2.net
From: Vin McLellan <vin@shore.net>
Date: Sat, 10 Apr 1999 01:49:44 -0400
At 10:28 AM 4/9/99 -0400, P. J. Ponder wrote:
>RSA has a note on their web site about a patent issued April 7, 1999,
>which provides a memory efficient means of converting between polynomial
>basis and normal basis stored numbers.
>
>http://www.rsa.com/pressbox/html/990407.html
The actual patent is:
B.S. KALISKI JR. and Y.L. YIN. Methods and Apparatus for Efficient Finite
Field Basis Conversion. U.S. Patent No. 5,854,759, December 29, 1998.
The press release is actually quite informative in suggesting the
potential of this technique for bridging between two ECC vendor/user
communities.
Some may prefer to read the paper submitted to IEEE P1363 by Burt
Kaliski (Chief Scientist at RSA Labs, and Chair of P1363) and Lisa Yin
(with Ron Rivest and Matt Robshaw, one of the inventors of RC6). See:
<http://grouper.ieee.org/groups/1363/contrib.html#papers-schemes>
Title: Storage-efficient finite field basis conversion
Authors: Burton S. Kaliski, Jr. and Yiqun Lisa Yin
Abstract:
" The problem of finite field basis conversion is to convert from the
representation of a field element in one basis to the representation of the
element in another basis. This paper presents new algorithms for the
problem that require much less storage than previous solutions.
" For the finite field GF(2m), for example, the storage requirement
of the new algorithms is only O(m) bits, compared to O(m2) for previous
solutions. With the new algorithms, it is possible to extend an
implementation in one basis to support other bases with little additional
cost, thereby providing the desired interoperability in many cryptographic
applications. "
--------
"Cryptography is like literacy in the Dark Ages. Infinitely potent,
for good and ill... yet basically an intellectual construct, an idea,
which by its nature will resist efforts to restrict it to bureaucrats
and others who deem only themselves worthy of such Privilege."
_A Thinking Man's Creed for Crypto _vbm
* Vin McLellan + The Privacy Guild + <vin@shore.net> *
53 Nichols St., Chelsea, MA 02150 USA <617> 884-5548
