Re: Idea for the SchmidtSamoa 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(p1,q1)
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(p1,q1)
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 (p1)(q1). 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^t1, N) will most likely be pq. Hence, we get p = N /
gcd(x^t1, N).
In the same way, we get that the onewayness 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(xy, N).

kg
.
 References:
 Idea for the SchmidtSamoa PK algorithm
 From: Tom St Denis
 Idea for the SchmidtSamoa PK algorithm
 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 SchmidtSamoa PK algorithm
 Next by thread: Last CFP  Applied Computing 2010: 3 September 2010
 Index(es):
Relevant Pages
