# Re: Idea for the Schmidt-Samoa PK algorithm

*From*: Kristian Gjøsteen <kristiag+news@xxxxxxxxxxxx>*Date*: Wed, 4 Aug 2010 22:40:53 +0000 (UTC)

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

.

**References**:**Idea for the Schmidt-Samoa PK algorithm***From:*Tom St Denis

- Prev by Date:
**Re: The Chaocipher algorithm revealed at last!** - Next by Date:
**Re: The Chaocipher algorithm revealed at last!** - Previous by thread:
**Re: Idea for the Schmidt-Samoa PK algorithm** - Next by thread:
**Last CFP - Applied Computing 2010: 3 September 2010** - Index(es):