🚀 go-pugleaf

Thus said stevens@vms.macc.wisc.edu (PAul STevens - MACC - 2-9618):
>In article <1galtnINNhn5@transfer.stratus.com>, cme@ellisun.sw.stratus.com (Carl Ellison) writes...
>
>>I went to the horse's mouth and asked some folks at PKP & RSA to comment
>>on PGP legality.  Here's their reply.  I have permission to post it.
>> 
>>Being aware of the RSA patent makes infringement willful and
>>deliberate. Under patent law, a patent holder is entitled to seek
>>triple damages and legal fees from deliberate infringers.  While the
>
>    Once again.  Talk, talk, talk, talk, talk.  Who is going to do
>    something?  For the record I am going to publish a number I
[ ... ]
>    My point is that *someone* has to test this patent claim!  How 
>    can we force this to happen?  If someone does get sued are we
>    all willing to contribute to the defense or are we all talk, too? 

Whoever goes to court to test the patent claim had better darn well have
the resources and circumstances to mount a strong defense or else he'll
just get creamed and a precedent will be set in favor of PKP.  It's not
something for some random doofus to challenge without significant
backing and knowledge.  Making a frivolous violation and losing in court
does not help your cause; quite the contrary.

That was part of why Mark Riordan quietly withdrew RPEM when it was
challenged even though he didn't believe it infringed PKP's patent.  I
suppose you think him a wimp who does nothing but "talk talk talk"
because of that, but it may have been the right decision for the time.
-- 

    >    For the record I am going to publish a number I
    >    want to keep secret.  I am going to raise it to the power of
    >    three modulo 91 which is the product of two primes.  The
    >    result is 34.  My wife knows the factors of 91 and will be able
    >    to decode this message.  

    Please excuse my ignorance, but, how can "your wife" decode the message
    knowing 34, 91, 7, and 13?

    i.e. I have a number
      (X^3) moulo 77 (product of two primes) = 48
    what is my number? and how did you get the answer?


Generally, given x^3 mod N = y, knowing the factors N = pq,
recover x by the following:
  1. Compute phi(N) = (p-1)(q-1).  For number theorists, this is
     the number of elements of Z^*_N, the (multiplicative mod N) group
     of integers relatively prime to N.
  2. Use the Extended Euclidean Algorithm (see Knuth vol. 2, etc.)
     to compute t, so that 3t == 1, mod phi(N).  This means that
     x^(3t) mod N will be equal to x.
     This is because x^(phi(N)) mod N == 1, from Lagrange's theorem.
  3. Now to decrypt y, simply compute x = y^t mod N.

In the case of N=77 and N=91, phi(N) is a multiple of 3 so no
suitable t exists.  You have to have picked your original primes
p and q to make this not happen.

In <1992Dec14.190615.13954@macc.wisc.edu> stevens@vms.macc.wisc.edu (PAul STevens - MACC - 2-9618) writes:
>    For the record I am going to publish a number I
>    want to keep secret.  I am going to raise it to the power of
>    three modulo 91 which is the product of two primes.  The
>    result is 34.  My wife knows the factors of 91 and will be able
>    to decode this message.  

Please excuse my ignorance, but, how can "your wife" decode the message
knowing 34, 91, 7, and 13?

i.e. I have a number
  (X^3) moulo 77 (product of two primes) = 48
what is my number? and how did you get the answer?

Thanks,
Rudy Crespin

-- 
                                                      _           _
   ---   O       | Rudy Crespin                    | / \ |\ | __ / \ |\ |
   --   <^-      | crespin@nadir.uucp              | \_/ | \|    \_/ | \|
  --  -\/\       | crash!nadir!crespin             | 
  ---     \      |                                 |- No-No, it is On-On.

In <PHR.92Dec16022546@napa.telebit.com> phr@telebit.com (Paul Rubin) writes:
>    Please excuse my ignorance, but, how can "your wife" decode the message
>    knowing 34, 91, 7, and 13?

>    i.e. I have a number
>      (X^3) moulo 77 (product of two primes) = 48
>    what is my number? and how did you get the answer?

[Stuff Deleted]

>In the case of N=77 and N=91, phi(N) is a multiple of 3 so no
>suitable t exists.  You have to have picked your original primes
>p and q to make this not happen.

O.K., now that you've excused my ignorance, I beg you excuse my stupidity.

Same number  X^3(mod, 391) = 133 
(phi(N) is not divisible by 3) What is my number?

I tried to figure out t, but got stumped.
Thanks again,
Rudy Crespin

-- 
                                                      _           _
   ---   O       | Rudy Crespin                    | / \ |\ | __ / \ |\ |
   --   <^-      | crespin@nadir.uucp              | \_/ | \|    \_/ | \|
  --  -\/\       | crash!nadir!crespin             | 
  ---     \      |                                 |- No-No, it is On-On.

In article <r09LrAXKBh107h@nadir.uucp> crespin@nadir.uucp (Rudy Crespin) writes:
>Same number  X^3(mod, 391) = 133 
>(phi(N) is not divisible by 3) What is my number?
>
>I tried to figure out t, but got stumped.
>Thanks again,
>Rudy Crespin

  since n=391 we can find n=p*q=17*23
  (p-1)*(q-1)=352
  you gave e=3 so my guess is d=235 since 3*235 mod 352 = 1

  133^235 mod 391 = 27 , so that is what I got
  to check, 27^3 mod 391 = 133 so all seems well.

  So, is X=27?
_______________________________________________________________________________
orb@ccwf.cc.utexas.edu              "Two roads diverged in a wood, and I -
                                     I chose to climb the nearest tree.
                                     And that has made all the difference."

    As far as I know the most efficient way to solve this is to try different
    values for a until you get a positive integer for b.

Nah.  Modulo N, all integers are positive.  -2 is the same as 350,
mod 352. 

See any algorithms book under "Extended Euclidean Algorithm" for
more description.  Just think of it as the ordinary Euclidean
GCD algorithm, except you keep track of how much of each number
you throw away (sorry if that makes no sense).

In article <r09LrAXKBh107h@nadir.uucp> you write:
>In <PHR.92Dec16022546@napa.telebit.com> phr@telebit.com (Paul Rubin) writes:
>>    Please excuse my ignorance, but, how can "your wife" decode the message
>>    knowing 34, 91, 7, and 13?
>
>>    i.e. I have a number
>>      (X^3) moulo 77 (product of two primes) = 48
>>    what is my number? and how did you get the answer?
>
>[Stuff Deleted]
>
>>In the case of N=77 and N=91, phi(N) is a multiple of 3 so no
>>suitable t exists.  You have to have picked your original primes
>>p and q to make this not happen.
>
>O.K., now that you've excused my ignorance, I beg you excuse my stupidity.
>
>Same number  X^3(mod, 391) = 133
>(phi(N) is not divisible by 3) What is my number?
>
27.

>I tried to figure out t, but got stumped.

t is 235.  Other larger numbers like 587 will also work.
The method is explained in Rivest et al, "A Method for Obtaining Digital
Signatures and Public-Key Cryptosystems," Communications of the ACM,
vol 21, no 2, Feb 1978, pp120ff.
Section VII d and VIII are the most relevant.

Now, that we have gcd(PHI(n), d) = 1, e must be calculated.  This is
done by calculating a series x0, x1, .... with x0 = PHI(n), and x1 = d
(ie 3), and x(i+1) = x(i-1) (mod xi).  For each xi, a pair of numbers ai and
bi must be found that satisfy:
ai*x0 + bi*x1 = xi.
As far as I know the most efficient way to solve this is to try different
values for a until you get a positive integer for b.
My numbers:
    x   a   b
0  352  1   0
1    3  0   1
2    1 -2  235

>Thanks again,

I hope this helps.

>Rudy Crespin
>
>--
>                                                      _           _
>   ---   O       | Rudy Crespin                    | / \ |\ | __ / \ |\ |
>   --   <^-      | crespin@nadir.uucp              | \_/ | \|    \_/ | \|
>  --  -\/\       | crash!nadir!crespin             |
>  ---     \      |                                 |- No-No, it is On-On.

--
;---------------------------------------------------------------------
; Mark Johnson             ; msdos has 6 types of RAM - dos ram,
; My views are my own and  ; upper memory, high memory, extended memory,
; nobody else's.           ; expanded memory, and video ram.
;                          ; YUCKKK!!!!!!!!!!!
;---------------------------------------------------------------------

In <lj1cgbINNemn@kara-kum.cs.utexas.edu> orb@cs.utexas.edu (Norman Richards) writes:
>In article <r09LrAXKBh107h@nadir.uucp> crespin@nadir.uucp (Rudy Crespin) writes:
>>Same number  X^3(mod, 391) = 133 
>>(phi(N) is not divisible by 3) What is my number?
>>
>>I tried to figure out t, but got stumped.
>>Thanks again,
>>Rudy Crespin

>  since n=391 we can find n=p*q=17*23
>  (p-1)*(q-1)=352
>  you gave e=3 so my guess is d=235 since 3*235 mod 352 = 1

>  133^235 mod 391 = 27 , so that is what I got
>  to check, 27^3 mod 391 = 133 so all seems well.

>  So, is X=27?
>_______________________________________________________________________________
>orb@ccwf.cc.utexas.edu              "Two roads diverged in a wood, and I -
>                                     I chose to climb the nearest tree.
>                                     And that has made all the difference."

Yes! I still don't get how you figure out 133^235 without blowing up your PC.
Rudy

-- 
                                                      _           _
   ---   O       | Rudy Crespin                    | / \ |\ | __ / \ |\ |
   --   <^-      | crespin@nadir.uucp              | \_/ | \|    \_/ | \|
  --  -\/\       | crash!nadir!crespin             | 
  ---     \      |                                 |- No-No, it is On-On.