Re: Idea for the Schmidt-Samoa PK algorithm



Tom St Denis <tom@xxxxxxx> wrote:
I'm writing a wiki article about [among other things] the Schmidt-
Samoa algorithm which works as follows

1. compute two large primes p and q and N = p^2q
2. compute d == 1/N mod lcm(p-1,q-1)

Your public key is N and your private key is (d, pq)

to encrypt

c = m^N mod N

and decrypt

m = c^d mod pq

However, could you not also compute

e = N mod lcm(p-1,q-1)

and then use (N, e) as the public key?

So I guess the question is does revealing the reduced value of 'e'
compromise the system? My hunch is yes since N is known you're
basically now solving for N - a*phi(pq) = e giving

N - e = a*phi(pq)

Suppose I have a multiple t of (p-1)(q-1). Now take a random integer x
relatively prime to N and raise it to the t'th power modulo N. It is now
congruent to 1 modulo pq, but most likely not congruent to 1 modulo N.
Hence, gcd(x^t-1, N) will most likely be pq. Hence, we get p = N /
gcd(x^t-1, N).

In the same way, we get that the one-way-ness of the system is equivalent
to factoring integers of the form p^2q (which _might_ be easier than
factoring integers of the form pq). Take any x, compute c = x^N mod N,
get an N'th root y of c modulo N, with overwhelming probability, x !=
y and then we get p = N / gcd(x-y, N).

--
kg
.