Efficient identification and signature schemes

[Mike Trachtman]

Identification and signature schemes have many commercial and military
applications. The main problem is to enable anyone to verify proofs of
identity without telling him how to generate such proofs by himself
(so he will not be able to misrepresent himself or forge new signatures
later). The RSA public key scheme (developed in 1977 at MIT by Rivest,
Shamir and adleman) provides a possible solution to this problem,
but for many applications its complexity is prohibitive: it requires about 750
modular multiplications of 500 bit numbers, and its software implementations
are quite slow.
A new paper which has just been published by Fiat and Shamir
from the Weizmann Institute provides a novel solution to this problem.
It describes exceptionally simple identification and signature schemes
which require only 1% to 4% of the number of modular multiplications required
by the RSA scheme. The new schemes require no shared or public keys, can
easily scale up to nation-wide networks, and are provably secure against
any known or chosen message attack if factoring large numbers is difficult.
The new schemes are particularly well suited to microprocessor-based
applications since they can be implemented in software in a fraction of
a second. Combined with the emerging technology of smart cards, they
can lead to a new generation of unforgeable ID cards (passports, driver's
licenses, credit cards, access control cards, etc). Other applications
include remote control systems (with verifiable commands), secure operating
systems (with hacker-proof logon procedures), data bases (with an unforgeable
audit trail for any access), and telecomunication devices (to prevent
spoofing).
Copies of the paper "How to Prove Yourself: Practical solutions to
Identification and Signature Problems" by Fiat and Shamir can be obtained
by writing to the secretary of the Applied Mathematics Dept of the Weizmann
Institute of Science, Rehovot 76100, Israel.

mike

[Paul Hoffman]

RSA is not as slow as some think. RSA Data Security, Inc. has just announced
a package for the IBM PC which produces encrypted files very very quickly.
For more info, talk to Jim Bidzos at 415/595-8782.

DISCLAIMER: I wrote the documentation for the package (called Mailsafe) for
RSA Data Security, so I am not an unbiased observer. However, I'm sure that
anyone trying out the demo will probably agree with my comments above.

[new...@ucbtopaz.berkeley.edu]

I'm not absolutely sure, but I believe RSA Data Security's package

just uses RSA to pass DES-like keys, and/or to do signature/authentication
of some portion of the message. I think the decrypt time for a roughly
512-bit block must be on the order of tens of seconds for a stock PC.

If this isn't true, I hope you'll consider it's not because I'm an idiot
but because I'm an NSA DES-information agent :>)

Doug Maisel

[Paul Hoffman]

>I'm not absolutely sure, but I believe RSA Data Security's package
>just uses RSA to pass DES-like keys, and/or to do signature/authentication
>of some portion of the message.

Correct (unless I misunderstood the method when I wrote the manual). It is
really a DES system with public keys; many contend that this is the best of
both worlds.

>I think the decrypt time for a roughly
>512-bit block must be on the order of tens of seconds for a stock PC.

Absolutely incorrect. With a hard disk, a 5K text file encrypts in about 5
seconds on my stock PC.

[new...@ucbtopaz.berkeley.edu]

Gee, if the *author* of Mailsafe's documentation is so easily confused,
God help the reader :>).

One more time: RSA is painful and relatively slow, DES can be fast.
Mailsafe (I think) uses RSA for key passing and authentication/signature.
To the extent that actual file encryption doesn't use RSA, it can be
fast (your 5Kbyte text file in ten seconds); even with fast and
clever schemes, RSA (I'm suggesting) takes tens of seconds to decrypt a
512-bit block (i.e. using a 512-bit modulus) via Mailsafe on a stock
PC. This only happens as semi-fixed overhead for a given transaction,
but the point is relevent to the earlier assertion that RSA Data Security's
products could do RSA orders of magnitude faster than was commonly believed
possible. This isn't true, and they don't claim it.

Doug Maisel

[new...@ucbtopaz.berkeley.edu]

I just read (maybe in *Science*) that Ernie Brickell has developed
a new division algorithm particularly suited to enlisting parallel
architectures in aid of very fast division (and thus managably fast
RSA decryption with very large modulus). I presume a chip is in
the oven even as I peck...

Doug Maisel