🚀 go-pugleaf

    >    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.