mike@wisdom.BITNET (Mike Trachtman) (07/20/86)
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
phoffman@well.UUCP (Paul Hoffman) (07/21/86)
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.
newton2@ucbtopaz.berkeley.edu (07/23/86)
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
phoffman@well.UUCP (Paul Hoffman) (07/29/86)
>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.
newton2@ucbtopaz.berkeley.edu (07/29/86)
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