Re: RSA Patent Workaround
According to well-informed sources in Her Majesty's Government, Pete Chown <[EMAIL PROTECTED]> wrote: >This is a bit late since the patent expires in September. However, >what do people think about this scheme? Firstly is it >cryptographically reasonable, and secondly does it genuinely avoid the >scope of the patent? > >Whereas in RSA you form a modulus n as the product of two primes p and >q, in my scheme you set n = pqr, where all three are prime. The order >of the multiplicative group modulo n is now (p - 1)(q - 1)(r - 1). >You choose e and find d such that de is congruent to 1 modulo >(p - 1)(q - 1)(r - 1). > >This will now behave in all respects identically to an RSA key, >although you will have to make the modulus bigger for identical >security. In fact, someone who is given e and n will find it almost >impossible to prove that it is not a genuine RSA key. > >You could make a key like this into an X.509 certificate. The public >side will work with all software, since proving that it is not an RSA >public key involves factoring n and so is computationally infeasible. >The private half should work with just about all software, since it >has no reason to recalculate e and d. It's a nice idea, but it's been around for ages. RSA has always seemed confident that the general description of the RSA mechanism (claim 33, which doesn't ennumerate the number of primes;-) in the Stateside RSA patent covers it. (YMMV) Even if it is not a RSApkc "patent workaround," however, it may be a potentially useful formulation of PKC. [I don't think RSA (or anyone else, AFAIK) has thus far used it in a commercial product or included it in BSAFE or any other toolkits. Dunno why not. I do know that RSA, at least, explored in some depth its potential for speeding up (~X2) crypto calculations at the server in C/S interactions. ] A Compaq crypto team has also done research in this area, using different numbers of primes with RSA. (There may even be an old paper from RSA Labs on it. I'll see if I can find it. If it is not proprietary -- I'll send it along.) Suerte, _Vin "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 + <[EMAIL PROTECTED]>*
Re: RSA Patent Workaround
>>Whereas in RSA you form a modulus n as the product of two primes p and >>q, in my scheme you set n = pqr, where all three are prime. The order >>of the multiplicative group modulo n is now (p - 1)(q - 1)(r - 1). >>You choose e and find d such that de is congruent to 1 modulo >>(p - 1)(q - 1)(r - 1). that may or may not work. i'm not gonna try to work out in my head which way it goes, but a simple change to an encryption algorithm doesn't always work (for example, doubling the block size for idea doesn't work because the 33 bit modulus you'd end up using isn't prime). oh, and it *almost certainly* will not work if any of p, q, or r are equal. >A Compaq crypto team has also done research in this area, using >different numbers of primes with RSA. anything published and available on line? -- ha-ha!
Re: RSA Patent Workaround
It's a nice idea, and it's probably as safe as RSA with a modulus having two prime factors, but it seems like Rivest-Shamir and Adleman already thought about it. Indeed, the Handbook of Applied Cryptography (which by the way is a great book, and is even online: http://cacr.math.uwaterloo.ca/hac/) has a 1 paragraph abstract of the patent, it includes RSA with a modulus n which is a product of three or more primes, and a bunch of other stuff. You can also see for yourself, look at the last claims (>= 33) of the RSA patent: http://www.patents.ibm.com/details?&pn=US04405829__&s_clms=1#clms Anton Pete Chown wrote: [...] Whereas in RSA you form a modulus n as the product of two primes p and q, in my scheme you set n = pqr, where all three are prime. The order of the multiplicative group modulo n is now (p - 1)(q - 1)(r - 1). You choose e and find d such that de is congruent to 1 modulo (p - 1)(q - 1)(r - 1). [...]
Re: RSA Patent Workaround
Pete Chown <[EMAIL PROTECTED]> suggested a PKC formulation: >>>Whereas in RSA you form a modulus n as the product of two primes p and >>>q, in my scheme you set n = pqr, where all three are prime. The order >>>of the multiplicative group modulo n is now (p - 1)(q - 1)(r - 1). >>>You choose e and find d such that de is congruent to 1 modulo >>>(p - 1)(q - 1)(r - 1). Vin McLellan noted that this was not a new idea, and added that in addition to relevant research at RSA Labs over the years... >>A Compaq crypto team has also done research in this area, using >>different numbers of primes with RSA. Andrew Brown <[EMAIL PROTECTED]> asked for a URL that might describe the Compaq research: /> anything published and available on line? Not that I know of. The Compaq work was just something I heard about sometime last year. Maybe someone from Compaq (or elsewhere) can offer more details. Suerte, _Vin
