gsmith@BRAHMS.BERKELEY.EDU (02/08/88)
If anyone feels strongly enough about protection against forgeries, one system which does not involve any fixes by anyone but the user himself is to post a large number which is the product of two large enough (say, ~10^30) primes or pseudoprimes. In any subsequent article you wish to authenticate, you give a pointer to the previous article and the factorization. Then you supply a new composite number. I admit it is sort of goofy, but it could easily be automated (maybe when Matthew Wiener gets back I will ask if he wants to put it in "gnews", the posting program he is developing.) Anyway, the number above in "keywords" is my example of an authentication number. I doubt the forger(s) will be desperate enough to want to factor it, although a few people on the net like Bob Silverman might be able to. ucbvax!brahms!gsmith Gene Ward Smith/Brahms Gang/Berkeley CA 94720 Imagine what the world would be like if football was a worthy ritual performed in stadiums but mathematics was a misunderstood activity ignored by almost all.
henry@utzoo.uucp (Henry Spencer) (02/09/88)
> In any subsequent article you wish to authenticate, you give a > pointer to the previous article and the factorization... This will break down immediately, since Usenet provides neither reliable delivery nor reliable sequencing. -- Those who do not understand Unix are | Henry Spencer @ U of Toronto Zoology condemned to reinvent it, poorly. | {allegra,ihnp4,decvax,utai}!utzoo!henry
webber@brandx.rutgers.edu (Webber) (02/12/88)
In article <8802080327.AA02920@jiff>, gsmith@BRAHMS.BERKELEY.EDU writes: > > If anyone feels strongly enough about protection against > forgeries, one system which does not involve any fixes by anyone Hmmm. I think you wasted this posting it to news.admin. The people in sci.crypt should have much more fun with it (usually all they hear about is people who want to use keys as seeds to pseudorandom number generators and xor the result with their messages). > but the user himself is to post a large number which is the > product of two large enough (say, ~10^30) primes or pseudoprimes. > In any subsequent article you wish to authenticate, you give a > pointer to the previous article and the factorization. Then you > supply a new composite number. Of course a faked cancel message can be used to steal your factorization from you and be used against you. Indeed, if someone cancels a message that you try to authenticate off of, shouldn't everyone deduce that you are the forgery? > I admit it is sort of goofy, but it could easily be automated > (maybe when Matthew Wiener gets back I will ask if he wants to > put it in "gnews", the posting program he is developing.) Actually, I think the biggest weakness is in the ``easily automated.'' Once you start generating your random factors automatically, the search space for factorization narrows considerably. As too how much effort people would be willing to put into breaking your scheme. The more effort you put into making your communications reliable, the more ``value'' there is in faking a communication. Then there is always the question of how many people will bother to verify your authentication message. By the time it becomes an issue that they are curious about, it may have already expired on their machine (if it hadn't already been fake-cancelled by whoever is challenging its followup). ---- BOB (webber@athos.rutgers.edu ; rutgers!athos.rutgers.edu!webber)
quisquat@prlb2.UUCP (Jac. Quisquater) (02/20/88)
In article <8802080327.AA02920@jiff> gsmith@brahms.BERKELEY.EDU () writes: > > If anyone feels strongly enough about protection against >forgeries, one system which does not involve any fixes by anyone >but the user himself is to post a large number which is the >product of two large enough (say, ~10^30) primes or pseudoprimes. >In any subsequent article you wish to authenticate, you give a >pointer to the previous article and the factorization. Then you >supply a new composite number. > Incorrect. (1) Your number (1037...183) must be really related to the message you send. Otherwise, If I copy the header of your article using some forgery, your scheme permits also to authenticate my message. That is, you need a true signature scheme with shadow or imprint. (2) I can also forge any message including a large number. In any subsequent article I give a pointer to this article and the factorization. The only thing you can prove is: ``Somebody knows the factorization: nothing else!''. In other words, it is very difficult (impossible?) to imagine an (off-line) identification scheme without any authority. You need this authority to initialize the scheme, not to run the system. (see the works of Shamir, Desmedt, Guillou and Quisquater for the identity-based cryptosystems, and the works of Goldreich, Goldwasser, Micali, Rackoff, Brassard, Chaum, Crepeau, Fiat, Shamir, Feige, Desmedt, Guillou, Quisquater ... for the zero-knowledge -- minimum disclosure -- protocols). Jean-Jacques Quisquater,
gsmith@BOSCO.BERKELEY.EDU (02/21/88)
In article <425@prlb2.UUCP> quisquat@prlb2.UUCP (Jean-Jac. Quisquater) writes: >In article <8802080327.AA02920@jiff> gsmith@brahms.BERKELEY.EDU () writes: >> If anyone feels strongly enough about protection against >>forgeries, one system which does not involve any fixes by anyone >>but the user himself is to post a large number which is the >>product of two large enough (say, ~10^30) primes or pseudoprimes. >>In any subsequent article you wish to authenticate, you give a >>pointer to the previous article and the factorization. Then you >>supply a new composite number. >Incorrect. This can't be incorrect, because it was not a statement of fact, but a proposal. There seems to be a good deal of confusion over what such a scheme would be intended to accomplish: certainly, I did not believe (nor state) that this would give any absolute protection against forgeries, or that the "Gene Smith" for whose continuity of identity this system would attempt to supply publically available evidence was ipso facto and by that test *alone* the "real" one, etc. >(1) Your number (1037...183) must be really related to the message you >send. Otherwise, If I copy the header of your article using some forgery, >your scheme permits also to authenticate my message. That is, you need a true >signature scheme with shadow or imprint. I confess I don't understand you at all. Can you explain, or perhaps demonstrate, your point? Can you show that you are "Gene Smith", in other words? >(2) I can also forge any message including a large number. In any subsequent >article I give a pointer to this article and the factorization. The only >thing you can prove is: ``Somebody knows the factorization: nothing else!''. Again, I don't follow at all. Are you proving you are "Gene Smith" by quoting a factorization I have already published? You really should be located closer to Berkeley than you are for this to work, I would think. Am I missing something? ucbvax!brahms!gsmith Gene Ward Smith/Brahms Gang/Berkeley CA 94720 ucbvax!bosco!gsmith "When Ubizmo talks, people listen."