From msuinfo!agate!library.ucla.edu!europa.eng.gtefsd.com!MathWorks.Com!blanket.mitre.org!linus.mitre.org!linus!mbunix!eachus Sat Jul 23 09:29:25 1994 Path: msuinfo!agate!library.ucla.edu!europa.eng.gtefsd.com!MathWorks.Com!blanket.mitre.org!linus.mitre.org!linus!mbunix!eachus From: eachus@spectre.mitre.org (Robert I. Eachus) Newsgroups: sci.crypt Subject: BBC signatures (was Re: Non-RSA Public Key Algorithms Wanted) Date: 19 Jul 94 10:35:14 Organization: The Mitre Corp., Bedford, MA. Lines: 49 Distribution: world Message-ID: References: <3045uv$t28@senator-bedfellow.MIT.EDU> <304qvm$9cj@northshore.ecosoft.com> <305i63$gsg@senator-bedfellow.MIT.EDU> <30egvj$fse@senator-bedfellow.MIT.EDU> NNTP-Posting-Host: spectre.mitre.org In-reply-to: solman@athena.mit.edu's message of 18 Jul 1994 18:17:23 GMT In article <30egvj$fse@senator-bedfellow.MIT.EDU> solman@athena.mit.edu (Jason W Solinsky) writes: > Here is a reference from cypherpunks. > >Congratulations! You've just described the Blum-GoldWasser Efficient > >Probabilistic Public-Key Encryption Scheme, first outlined in Crypto 84. > >Nice description in Schneier, who says it's much faster and more secure > >than any other PK scheme, but can obviously only be used one-way as it's > >vulnerable to a chosen plaintext attack. It would be possible to cook up > >a protocol to allow for signatures as well, but it'd be tricky. > I don't agree with this last statement. I've convinced myself that this > is not possible without fundamentally altering the process. > I'd be happy to be proven wrong though. If I send you a BBS message and want to append a signature I can do this: I create a digest of the message, X. I then generate X' = (X)^((2^(N-1) mod ((P-1)(Q-1)))) mod N. Where N is my key and P and Q are its factors. I then send the message (enciphered with my correspondents public key if necessary) with X' appended. (This means that a BBC encrypted and signed message will be 2 x lg2(N) bits longer than the unencrypted message, assuming both keys are the same size.) The recipient takes the message (after decrypting with his secret key if enciphered) and then generates a digest D with the same digest algorithm. The signature is valid iff D^2 = X'^4 mod N. Straighforward and deterministic, but I have to increase the message length. WIth most modern communication methods, this increase will not be noticed. (At even 2400 baud, the increase will be less than one second.) There are potentially four numbers with the same square as D, and the square of X' will be one of them. Technically this means that it is almost four times as likely that a BBC signature can be forged by guessing as that a RSA signature of the same length can be forged the same way. But in either case, factoring N is likely to be the best attack. -- Robert I. Eachus with Standard_Disclaimer; use Standard_Disclaimer; function Message (Text: in Clever_Ideas) return Better_Ideas is... From msuinfo!agate!howland.reston.ans.net!europa.eng.gtefsd.com!MathWorks.Com!blanket.mitre.org!linus.mitre.org!linus!mbunix!eachus Sat Jul 23 09:29:36 1994 Path: msuinfo!agate!howland.reston.ans.net!europa.eng.gtefsd.com!MathWorks.Com!blanket.mitre.org!linus.mitre.org!linus!mbunix!eachus From: eachus@spectre.mitre.org (Robert I. Eachus) Newsgroups: sci.crypt Subject: Re: BBC signatures (was Re: Non-RSA Public Key Algorithms Wanted) Date: 20 Jul 94 19:08:06 Organization: The Mitre Corp., Bedford, MA. Lines: 31 Distribution: world Message-ID: References: <3045uv$t28@senator-bedfellow.MIT.EDU> <304qvm$9cj@northshore.ecosoft.com> <305i63$gsg@senator-bedfellow.MIT.EDU> <30egvj$fse@senator-bedfellow.MIT.EDU> NNTP-Posting-Host: spectre.mitre.org In-reply-to: eachus@spectre.mitre.org's message of 19 Jul 94 10:35:14 I said: > If I send you a BBS message and want to append a signature I can do > this: > I create a digest of the message, X. I then generate X' = > (X)^((2^(N-1) mod ((P-1)(Q-1)))) mod N. Where N is my key and P and Q > are its factors... As David Wagner pointed out to me via e-mail, I meant: (X)^(2^(N - P - Q) mod ((P-1)(Q-1))) or, if you prefer: (X)^(2^(-1) mod ((P-1)(Q-1)) I prefer the second notation, but it hides to some extent the fact that you need P and Q. Also in two places I wrote BBC instead of BBS. Hey, we all have bad days... -- Robert I. Eachus with Standard_Disclaimer; use Standard_Disclaimer; function Message (Text: in Clever_Ideas) return Better_Ideas is...